本页使用了标题或全文手工转换

双向链表

维基百科,自由的百科全书
跳转至: 导航搜索

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

  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     // 返回NULL
119     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≤表长+1
130     // 改进算法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个元素前驱的位置指针p
135     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个元素的位置指针p
154     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 }