雙向鏈表比單鏈表有更好的靈活性，其大部分操作與線性表相同。下面總結雙向鏈表與單鏈表之間的不同之處及我在實現過程中所遇到的問題。
1.雙向鏈表的建立
雙向鏈表在初始化時，要給首尾兩個節點分配內存空間。成功分配后，要將首節點的prior指針和尾節點的next指針指向NULL，這是十分關鍵的一步，因為這是之后用來判斷空表的條件。同時，當鏈表為空時，要將首節點的next指向尾節點，尾節點的prior指向首節點。
2.雙向鏈表的插入操作
由于定義雙向鏈表時指針域中多了一個prior指針，插入操作相應變得復雜，但基本操作也并不難理解。只需記住在處理前驅和后繼指針與插入節點的關系時，應始終把握好“有序原則”，即若將插入節點與兩個已存在的節點構成三角形，則應先處理“向上”的指針，再處理“向下”的指針。下面用代碼描述其過程:
|
1
2
3
4
|
pinsert->prior=p;pinsert->next=p->next;p->next->prior=pinsert;p->next=pinsert; |
3.雙向鏈表的刪除操作
理解了雙向鏈表的插入操作后，刪除操作便十分容易理解。下面用代碼描述其過程:
|
1
2
3
|
p->prior->next=p->next; p->next->prior=p->prior; free(p); |
雙向鏈表的其他操作與單鏈表類似，在此不再贅述，完整的代碼如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
#include<stdio.h>#include<stdlib.h>#include<time.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int status;typedef int elemtype;typedef struct node{ elemtype data; struct node * next; struct node * prior;}node;typedef struct node* dlinklist;status visit(elemtype c){ printf("%d ",c);}/*雙向鏈表初始化*/status initdlinklist(dlinklist * head,dlinklist * tail){ (*head)=(dlinklist)malloc(sizeof(node)); (*tail)=(dlinklist)malloc(sizeof(node)); if(!(*head)||!(*tail)) return ERROR; /*這一步很關鍵*/ (*head)->prior=NULL; (*tail)->next=NULL; /*鏈表為空時讓頭指向尾*/ (*head)->next=(*tail); (*tail)->prior=(*head);}/*判定是否為空*/status emptylinklist(dlinklist head,dlinklist tail){ if(head->next==tail) return TRUE; else return FALSE;} /*尾插法創建鏈表*/status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){ dlinklist pmove=tail,pinsert; pinsert=(dlinklist)malloc(sizeof(node)); if(!pinsert) return ERROR; pinsert->data=data; pinsert->next=NULL; pinsert->prior=NULL; tail->prior->next=pinsert; pinsert->prior=tail->prior; pinsert->next=tail; tail->prior=pinsert;} /*頭插法創建鏈表*/status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){ dlinklist pmove=head,qmove=tail,pinsert; pinsert=(dlinklist)malloc(sizeof(node)); if(!pinsert) return ERROR; else{ pinsert->data=data; pinsert->prior=pmove; pinsert->next=pmove->next; pmove->next->prior=pinsert; pmove->next=pinsert; }}/*正序打印鏈表*/status traverselist(dlinklist head,dlinklist tail){ /*dlinklist pmove=head->next; while(pmove!=tail){ printf("%d ",pmove->data); pmove=pmove->next; } printf("\n"); return OK;*/ dlinklist pmove=head->next; while(pmove!=tail){ visit(pmove->data); pmove=pmove->next; } printf("\n");}/*返回第一個值為data的元素的位序*/status locateelem(dlinklist head,dlinklist tail,elemtype data){ dlinklist pmove=head->next; int pos=1; while(pmove&&pmove->data!=data){ pmove=pmove->next; pos++; } return pos;}/*返回表長*/status listlength(dlinklist head,dlinklist tail){ dlinklist pmove=head->next; int length=0; while(pmove!=tail){ pmove=pmove->next; length++; } return length;}/*逆序打印鏈表*/status inverse(dlinklist head,dlinklist tail){ dlinklist pmove=tail->prior; while(pmove!=head){ visit(pmove->data); pmove=pmove->prior; } printf("\n");}/*刪除鏈表中第pos個位置的元素，并用data返回*/status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){ int i=1; dlinklist pmove=head->next; while(pmove&&i<pos){ pmove=pmove->next; i++; } if(!pmove||i>pos){ printf("輸入數據非法\n"); return ERROR; } else{ *data=pmove->data; pmove->next->prior=pmove->prior; pmove->prior->next=pmove->next; free(pmove); }}/*在鏈表尾插入元素*/status inserttail(dlinklist head,dlinklist tail,elemtype data){ dlinklist pinsert; pinsert=(dlinklist)malloc(sizeof(node)); pinsert->data=data; pinsert->next=NULL; pinsert->prior=NULL; tail->prior->next=pinsert; pinsert->prior=tail->prior; pinsert->next=tail; tail->prior=pinsert; return OK;} int main(void){ dlinklist head,tail; int i=0; elemtype data=0; initdlinklist(&head,&tail); if(emptylinklist(head,tail)) printf("鏈表為空\n"); else printf("鏈表不為空\n"); printf("頭插法創建鏈表\n"); for(i=0;i<10;i++){ createdlinklisthead(head,tail,i); } traverselist(head,tail); for(i=0;i<10;i++){ printf("表中值為%d的元素的位置為",i); printf("%d位\n",locateelem(head,tail,i)); } printf("表長為%d\n",listlength(head,tail)); printf("逆序打印鏈表"); inverse(head,tail); for(i=0;i<10;i++){ deleteelem(head,tail,1,&data); printf("被刪除的元素為%d\n",data); } traverselist(head,tail); if(emptylinklist(head,tail)) printf("鏈表為空\n"); else printf("鏈表不為空\n"); printf("尾插法創建鏈表\n"); for(i=0;i<10;i++){ //inserttail(head,tail,i); createdlinklisttail(head,tail,i); } traverselist(head,tail); printf("逆序打印鏈表"); inverse(head,tail);} |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/kelvinmao/article/details/51044928
