双向链表

//线性表的双向链表存储结构
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;  //直接前驱指针
    struct DulNode *next;   //直接后继指针
}DulNode , *DuLinkList;

s->prior = p;           //把p赋值给s的前驱，如图中1所示
s->next = p->next;      //把p->next赋值给s的后继，如图中2所示
p->next->prior = s;     //把s赋值给p->next的前驱，如图中3所示
p->next = s;            //把s赋值给p的后继，如图中4所示

p->prior->next = p->next;       //把p->next赋值给p->prior的后继，如图中1所示
p->next->prior = p->prior;      //把p->prior赋值给p->next的前驱，如图中2所示
free(p);                        //释放结点

  1 //双链循环线性表的表示与实现
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 /******************************************************************************
  6 /* 数据类型和常量定义
  7 /******************************************************************************/
  8 #define TURE         1
  9 #define FALSE        0
 10 #define OK           1
 11 #define ERROR        0
 12 #define OVERFLOW    -2
 13 
 14 typedef int Status;
 15 typedef int ElemType;
 16 
 17 /******************************************************************************
 18 /* 数据结构声明
 19 /******************************************************************************/
 20 /* 线性表的双向链表存储结构 */
 21 typedef struct DuLNode {
 22     ElemType data;
 23     struct DuLNode *prior;
 24     struct DuLNode *next;
 25 } DuLNode, *DuLinkList;
 26 
 27 //初始化双链循环线性表
 28 Status InitList_DuL(DuLinkList &L) {
 29     L = (DuLinkList)malloc(sizeof(DuLNode));
 30     L->next = L->prior = L;
 31     return OK;
 32 }
 33 
 34 //获取双链循环线性表中的元素
 35 DuLNode * GetElemP_Dul(DuLinkList L, int i) {
 36     int j;    struct DuLNode *p = L;
 37     if (i < 1)   //非法i值
 38         return NULL;
 39     if (p->next == L) //空双向循环链表
 40         return L;
 41     p = L->next; j = 1;   //初始化, p指向第一个结点, j为计数器
 42     while(p != L && j < i) {  //顺指针向后查找, 直到p指向第i个元素或p指向头结点
 43         p = p->next; ++j;
 44     }
 45     return p;
 46 }
 47 
 48 //插入元素
 49 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
 50     //在带头结点的双链循环线性表L中第i个位置之前插入元素e
 51     //i的合法值为1 <= i <= 表长 + 1
 52     struct DuLNode *p = NULL;
 53     struct DuLNode *s = NULL;
 54     if (!(p = GetElemP_Dul(L, i)))
 55         return ERROR;
 56     if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
 57     s->data = e;
 58     s->prior = p->prior; p->prior->next = s;
 59     s->next = p;         p->prior = s;
 60     return OK;
 61 }
 62 
 63 //删除元素
 64 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
 65     //在带头结点的双链线性表L中, 删除第i个元素, 并由e返回其值
 66     //i的合法值为1 <= i <= 表长
 67     struct DuLNode *p = NULL;
 68     if (!(p = GetElemP_Dul(L, i)) || L == GetElemP_Dul(L, i))
 69         return ERROR;
 70     e = p->data;
 71     p->prior->next = p->next;
 72     p->next->prior = p->prior;
 73     free(p); return OK;
 74 }
 75 
 76 //遍历线性表
 77 Status ListTraverse_DuL(DuLinkList &L, Status (*Visit)(ElemType)) {
 78     printf("traverse list: ");
 79     struct DuLNode *p = L->next; //略过头结点
 80     while (p != L) {
 81         Visit(p->data);
 82         p = p->next;
 83     }
 84     return OK;
 85 }
 86 
 87 //访问线性表中的元素
 88 Status Visit(ElemType e)
 89 {
 90     printf("%d ", e);
 91     return OK;
 92 }
 93 
 94 //测试函数
 95 void main()
 96 {
 97     DuLinkList L;  ElemType e;
 98     InitList_DuL(L);
 99     
100     //插入元素
101     if (OK == ListInsert_DuL(L, 0, 55)) printf("insert 55 succeed!\n");
102     if (OK == ListInsert_DuL(L, 1, 56)) printf("insert 56 succeed!\n");
103     ListTraverse_DuL(L, Visit); printf("\n");
104     if (OK == ListInsert_DuL(L, 2, 57)) printf("insert 57 succeed!\n");
105     if (OK == ListInsert_DuL(L, 1, 58)) printf("insert 58 succeed!\n");
106     ListTraverse_DuL(L, Visit); printf("\n");
107 
108     //删除元素
109     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
110     if (OK == ListDelete_DuL(L, 3, e)) printf("the %drd elem deleted!\n", 3);
111     if (OK == ListDelete_DuL(L, 4, e)) 
112         printf("the %dth elem deleted!\n", 4);
113     else
114         printf("delete the %dth elem failed!\n", 4);
115     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
116     ListTraverse_DuL(L, Visit); printf("\n");
117     if (OK == ListDelete_DuL(L, 1, e)) printf("the %dst elem deleted!\n", 1);
118     ListTraverse_DuL(L, Visit); printf("\n");
119 }