C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 雙向鏈表的建立與基本操作
雙向鏈表比單鏈表有更好的靈活性，其大部分操作與線性表相同。下面總結(jié)雙向鏈表與單鏈表之間的不同之處及我在實(shí)現(xiàn)過(guò)程中所遇到的問(wèn)題。
1.雙向鏈表的建立
雙向鏈表在初始化時(shí)，要給首尾兩個(gè)節(jié)點(diǎn)分配內(nèi)存空間。成功分配后，要將首節(jié)點(diǎn)的prior指針和尾節(jié)點(diǎn)的next指針指向NULL，這是十分關(guān)鍵的一步，因?yàn)檫@是之后用來(lái)判斷空表的條件。同時(shí)，當(dāng)鏈表為空時(shí)，要將首節(jié)點(diǎn)的next指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的prior指向首節(jié)點(diǎn)。
2.雙向鏈表的插入操作
由于定義雙向鏈表時(shí)指針域中多了一個(gè)prior指針，插入操作相應(yīng)變得復(fù)雜，但基本操作也并不難理解。只需記住在處理前驅(qū)和后繼指針與插入節(jié)點(diǎn)的關(guān)系時(shí)，應(yīng)始終把握好“有序原則”，即若將插入節(jié)點(diǎn)與兩個(gè)已存在的節(jié)點(diǎn)構(gòu)成三角形，則應(yīng)先處理“向上”的指針，再處理“向下”的指針。下面用代碼描述其過(guò)程:
|
1
2
3
4
|
pinsert->prior=p;pinsert->next=p->next;p->next->prior=pinsert;p->next=pinsert; |
3.雙向鏈表的刪除操作
理解了雙向鏈表的插入操作后，刪除操作便十分容易理解。下面用代碼描述其過(guò)程:
|
1
2
3
|
p->prior->next=p->next; p->next->prior=p->prior; free(p); |
雙向鏈表的其他操作與單鏈表類(lèi)似，在此不再贅述，完整的代碼如下:
|
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; /*這一步很關(guān)鍵*/ (*head)->prior=NULL; (*tail)->next=NULL; /*鏈表為空時(shí)讓頭指向尾*/ (*head)->next=(*tail); (*tail)->prior=(*head);}/*判定是否為空*/status emptylinklist(dlinklist head,dlinklist tail){ if(head->next==tail) return TRUE; else return FALSE;} /*尾插法創(chuàng)建鏈表*/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;} /*頭插法創(chuàng)建鏈表*/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");}/*返回第一個(gè)值為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;}/*返回表長(zhǎng)*/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個(gè)位置的元素，并用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("輸入數(shù)據(jù)非法\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("鏈表為空\(chéng)n"); else printf("鏈表不為空\(chéng)n"); printf("頭插法創(chuàng)建鏈表\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("表長(zhǎng)為%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("鏈表為空\(chéng)n"); else printf("鏈表不為空\(chéng)n"); printf("尾插法創(chuàng)建鏈表\n"); for(i=0;i<10;i++){ //inserttail(head,tail,i); createdlinklisttail(head,tail,i); } traverselist(head,tail); printf("逆序打印鏈表"); inverse(head,tail);} |
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/kelvinmao/article/details/51044928
