双向链表
在线性链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋，则需从表头指针出 发。换句话说，在单链表中，NextElem的执行时间是o(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双 向链表。
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
//线性表的双向链表存储结构 typedef struct DulNode { ElemType data; struct DulNode *prior; //直接前驱指针 struct DulNode *next; //直接后继指针 }DulNode , *DuLinkList;
双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。
插入操作
插入操作，其实并不复杂，不过顺序很重要，千万不能写反了。假设存储元素e的结点s，要实现将结点s插入到结点p和p->next之间需要下面几步，如下图所示。
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所示
关键在于他们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作玩不成。所以不妨把上面这种图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。
删除操作
如要删除结点p，只需要下面两个步骤，如下图所示。
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 }
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
