本文共 4982 字，大约阅读时间需要 16 分钟。

创建一个cpp文件代码如下就可以实现双向链表的基本操作了（熬夜使我脱发，呜呜呜，代码使我入迷）

#include 
   
    #include 
    
     #include 
     
      #define OVERFLOW -3#define true 1#define false 0#define ok 1#define error -1using namespace std;typedef struct DuLNode{    int data;    struct DuLNode *prior;    struct DuLNode *next;} * DuLinkList;//产生空的双向循环链表void InitList(DuLinkList &L){    L = (DuLinkList)malloc(sizeof(DuLNode));    if (L)        L->next = L->prior = L;    else        exit(OVERFLOW);}//销毁双向循环链表void DestroyList(DuLinkList &L){    DuLNode *q, *p = L->next; //p指向第一个节点    while (p != L)            //p还未达到表头    {        q = p->next;        free(p);        p = q;    }    free(L);    L = NULL;}//将L置为空表void ClearList(DuLNode *L){    DuLNode *q, *p = L->next;    while (p != L)    {        q = p->next;        free(p);        p = q;    }    L->next = L->prior = L; //头节点的两个指针域均指向自身}//是空表返回1不是返回0int ListEmpty(DuLNode *L){    if (L->next == L && L->prior == L)        return true;    else        return false;}//返回表长度int ListLength(DuLNode *L){    int i = 0;    DuLNode *p = L->next;    while (p != L)    {        i++;        p = p->next;    }    return i;}//得到指定位置上的元素，赋值给e然后返回int GetElem(DuLNode *L, int i, int &e){    int j = 1;    DuLNode *p = L->next;    while (p != L && j < i) //指针向后查找，直至找到第i个元素或者是p指向表头    {        p = p->next;        j++;    }    if (p == L || j < i)        return error;    e = p->data;    return ok;}//判断指定元素是否在链表中，在的话返回位置int LocateElem(DuLNode *L, int e){    int i = 0;    DuLNode *p = L->next; //指向链表第一个节点位置    while (p != L)    {        i++;        if (p->data == e) //对比找到这个位置            return i;        p = p->next;    }    return 0;}//返回给定元素前面一个位置的元素int PriorElem(DuLNode *L, int cur, int &pre){    DuLNode *p = L->next->next; //p指向第二个节点    while (p != L)              //p不到表头的时候    {        if (p->data == cur)        {            pre = p->prior->data;            return true;        }        p = p->next;    }    return false;}//返回给定元素位置的下一个位置的元素int NextElem(DuLNode *L, int cur, int &next){    DuLNode *p = L->next->next; //p指向第二个元素    while (p != L)              //p未到表头    {        if (p->prior->data == cur)        {            next = p->data;            return true;        }        p = p->next;    }    return false;}//返回指定位置的地址DuLinkList GetElemP(DuLNode *L, int i){    int j;    DuLNode *p = L;                 //p指向表头    if (i < 0 || i > ListLength(L)) //i值不合法        return NULL;    for (j = 1; j <= i; j++)        p = p->next;    return p;}//在链表指定位置插入元素int ListInsert(DuLNode *L, int i, int e){    DuLNode *p, *s;    if (i < 0 || i > ListLength(L) + 1)        return error;    p = GetElemP(L, i - 1); //指定位置的前驱指针    if (!p)        return error;    s = (DuLNode *)malloc(sizeof(DuLNode));    if (!s)        return OVERFLOW;    s->data = e;    s->prior = p; //在i-1个元素之后插入    s->next = p->next;    p->next->prior = s;    p->next = s;    return ok;}//删除带头节点的链表的第i个位置的元素int ListDelete(DuLNode *L, int i, int &e){    DuLNode *p;    if (i < 1)        return ok;    p = GetElemP(L, i); //确定第i个位置的元素指针p    if (!p)        return error;    e = p->data;    p->prior->next = p->next;    p->next->prior = p->prior;    free(p);    return ok;}//正向遍历链表void ListTraverse(DuLNode *L){    DuLNode *p = L->next; //指向头节点    while (p != L)    {        cout << p->data << "   ";        p = p->next;    }    cout << endl;}//反向遍历链表void ListTraverseBack(DuLNode *L){    DuLNode *p = L->prior; //指向尾节点    while (p != L)    {        cout << p->data << "   ";        p = p->prior;    }    cout << endl;}int main(){    DuLNode *L;    int i, n, j, e;    InitList(L);    for (i = 1; i <= 5; i++)        ListInsert(L, i, i);    cout << "output the list in Positive sequence:";    ListTraverse(L);    cout << endl;    cout << "output the list in The reverse:";    ListTraverseBack(L);    cout << endl;    n = 2;    ListDelete(L, n, e);    cout << "delete the " << n << "th and it worth:" << e << " the teft is:";    ListTraverse(L);    cout << endl;    cout << "the length of list is:" << ListLength(L) << endl;    cout << "whether the list is empty or not(1:yes 0:no):" << ListEmpty(L) << endl;    ClearList(L);    cout << "after clear up whether the list is empty or not(1:yes 0:no):" << ListEmpty(L) << endl;    for (i = 1; i <= 5; i++)    {        ListInsert(L, i, i);    }    ListTraverse(L);    n = 3;    j = GetElem(L, n, e);    if (j)        cout << "the " << n << "th of the list is:" << e << endl;    else        cout << "the nmber do not exit" << endl;    n = 4;    i = LocateElem(L, n);    if (i)        cout << "the " << n << "th of the list is:" << i << endl;    else        cout << "the nmber do not exit" << endl;    j = PriorElem(L, n, e);    if (j)        cout << "the number before" << n << "  is:" << e << endl;    else        cout << "the nmber do not exit" << endl;    j = NextElem(L, n, e);    if (j)        cout << "the number after" << n << "  is:" << e << endl;    else        cout << "the nmber do not exit" << endl;    DestroyList(L);    system("pause");}
     
    
   

结果如下

转载地址：http://jptmb.baihongyu.com/