双向链表

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
  1 // 线性表的双向链表存储结构  2 typedef struct DuLNode {  3     ElemType data;  4     struct DuLNode *prior, *next;  5 } DuLNode, *DuLinkList;  6   7 // 带头结点的双向循环链表的基本操作(14个)  8 void InitList(DuLinkList *L) {  9     // 产生空的双向循环链表L 10     *L = (DuLinkList)malloc(sizeof(DuLNode)); 11     if (*L) 12         (*L)->next = (*L)->prior = *L; 13     else 14         exit(OVERFLOW); 15 } 16  17 void DestroyList(DuLinkList *L) { 18     // 操作结果：销毁双向循环链表L 19     DuLinkList q, p = (*L)->next; // p指向第一个结点 20     while (p != *L) { // p没到表头 21         q = p->next; 22         free(p); 23         p = q; 24     } 25     free(*L); 26     *L = NULL; 27 } 28  29 void ClearList(DuLinkList L) { // 不改变L 30     // 初始条件：L已存在。操作结果：将L重置为空表 31     DuLinkList q, p = L->next; // p指向第一个结点 32     while (p != L) { // p没到表头 33         q = p->next; 34         free(p); 35         p = q; 36     } 37     L->next = L->prior = L; // 头结点的两个指针域均指向自身 38 } 39  40 Status ListEmpty(DuLinkList L) { 41     // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE 42     if (L->next == L && L->prior == L) 43         return TRUE; 44     else 45         return FALSE; 46 } 47  48 int ListLength(DuLinkList L) { 49     // 初始条件：L已存在。操作结果：返回L中数据元素个数 50     int i = 0; 51     DuLinkList p = L->next; // p指向第一个结点 52     while (p != L) { // p没到表头 53         i++; 54         p = p->next; 55     } 56     return i; 57 } 58  59 Status GetElem(DuLinkList L, int i, ElemType *e) { 60     // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR 61     int j = 1; // j为计数器 62     DuLinkList p = L->next; // p指向第一个结点 63     while (p != L && j < i) { // 顺指针向后查找，直到p指向第i个元素或p指向头结点 64         p = p->next; 65         j++; 66     } 67     if (p == L || j > i) // 第i个元素不存在 68         return ERROR; 69     *e = p->data; // 取第i个元素 70     return OK; 71 } 72  73 int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { 74     // 初始条件：L已存在，compare()是数据元素判定函数 75     // 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 76     // 若这样的数据元素不存在，则返回值为0 77     int i = 0; 78     DuLinkList p = L->next; // p指向第1个元素 79     while (p != L) { 80         i++; 81         if (compare(p->data, e)) // 找到这样的数据元素 82             return i; 83         p = p->next; 84     } 85     return 0; 86 } 87  88 Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) { 89     // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， 90     // 否则操作失败，pre_e无定义 91     DuLinkList p = L->next->next; // p指向第2个元素 92     while (p != L) { // p没到表头 93         if (p->data == cur_e) { 94             *pre_e = p->prior->data; 95             return TRUE; 96         } 97         p = p->next; 98     } 99     return FALSE;100 }101 102 Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) {103     // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，104     // 否则操作失败，next_e无定义105     DuLinkList p = L->next->next; // p指向第2个元素106     while (p != L) { // p没到表头107         if (p->prior->data == cur_e) {108             *next_e = p->data;109             return TRUE;110         }111         p = p->next;112     }113     return FALSE;114 }115 116 DuLinkList GetElemP(DuLinkList L, int i) { // 另加117     // 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，118     // 返回NULL119     int j;120     DuLinkList p = L; // p指向头结点121     if (i < 0 || i > ListLength(L)) // i值不合法122         return NULL;123     for (j = 1; j <= i; j++)124         p = p->next;125     return p;126 }127 128 Status ListInsert(DuLinkList L, int i, ElemType e) {129     // 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1130     // 改进算法2.18，否则无法在第表长+1个结点之前插入元素131     DuLinkList p, s;132     if (i < 1 || i > ListLength(L) + 1) // i值不合法133         return ERROR;134     p = GetElemP(L, i - 1); // 在L中确定第i个元素前驱的位置指针p135     if (!p) // p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)136         return ERROR;137     s = (DuLinkList)malloc(sizeof(DuLNode));138     if (!s)139         return OVERFLOW;140     s->data = e;141     s->prior = p; // 在第i-1个元素之后插入142     s->next = p->next;143     p->next->prior = s;144     p->next = s;145     return OK;146 }147 148 Status ListDelete(DuLinkList L, int i, ElemType *e) {149     // 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长150     DuLinkList p;151     if (i < 1) // i值不合法152         return ERROR;153     p = GetElemP(L, i); // 在L中确定第i个元素的位置指针p154     if (!p) // p = NULL,即第i个元素不存在155         return ERROR;156     *e = p->data;157     p->prior->next = p->next; // 此处并没有考虑链表头，链表尾158     p->next->prior = p->prior;159     free(p);160     return OK;161 }162 163 void ListTraverse(DuLinkList L, void(*visit)(ElemType)) {164     // 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit()165     DuLinkList p = L->next; // p指向头结点166     while (p != L) {167         visit(p->data);168         p = p->next;169     }170     printf("\n");171 }172 173 void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) {174     // 由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()175     DuLinkList p = L->prior; // p指向尾结点176     while (p != L) {177         visit(p->data);178         p = p->prior;179     }180     printf("\n");181 }