双向链表的实现
学习完双链表的定义与基础操作之后，我们用C语言来实现一个双链表。此双向链表所具有的功能如下所示：
● 创建双向链表。
● 获取双向链表的长度。
● 判断双向链表是否为空。
● 插入、删除、查找元素。
● 销毁双向链表。
● 打印双向链表。
在学习单链表时，每一种操作算法都有详细的描述与实现代码，双向链表与单链表有很多操作是相似的，不再详细描述，只给出案例代码。具体如例1所示。
例1
dlist.h //头文件
1 #ifndef _DLIST_H_
2 #define _DLIST_H_
3
4 struct Node;
5 typedef struct Head* pHead; //头结点类型
6 typedef struct Node* pNode; //数据结点类型
7 //定义头结点
8 struct Head
9 {
10 int length;
11 pNode next; //指向下一个结点的指针
12 };
13 //定义数据结点
14 struct Node
15 {
16 int data;
17 pNode pre; //指向前驱结点的指针
18 pNode next; //指向后继结点的指针
19 };
20
21 pHead DlistCreate(); //创建双向链表
22 int getLength(pHead ph); //获取双向链表的长度
23 int IsEmpty(pHead ph); //判断链表是否为空
24 int DlistInsert(pHead ph, int pos, int val); //在链表的pos位置插入元素val
25 pNode DlistDelete(pHead ph, int val); //删除双向链表ph中的元素val
26 pNode DlistFind(pHead ph, int val); //查找双向链表中是否有值为val的元素
27 void DlistDestory(pHead ph); //销毁链表
28 void printFront(pHead ph); //打印双向链表中的元素
29 void printLast(pHead ph);
30 #endifdlist.c //函数实现文件
31 #include "dlist.h"
32 #include <stdio.h>
33 #include <stdlib.h>
34
35 pHead DlistCreate() //创建双向链表
36 {
37 pHead ph = (pHead)malloc(sizeof(struct Head)); //为头结点分配空间
38 if (ph == NULL)
39 printf("分配头结点失败！"); //为了方便运行结果查看，不设置return返回
40 //创建好头结点后，初始化头结点中数据
41 ph->length = 0;
42 ph->next = NULL;
43 return ph; //将头结点返回
44 }
45 int getLength(pHead ph) //获取双向链表的长度
46 {
47 //先对传入进来的链表作健壮性检查
48 if (ph == NULL)
49 printf("传入的双链表有误！");
50 return ph->length;
51 }
52
53 int IsEmpty(pHead ph) //判断双链表是否为空
54 {
55 if (ph == NULL)
56 printf("传入的双链表有误！");
57 if (ph->length == 0) //如果长度为0，则链表为空
58 return 1;
59 else
60 return 0;
61 }
62
63 int DlistInsert(pHead ph, int pos, int val) //在链表的pos位置插入元素val
64 {
65 pNode pval = NULL;
66 //先作健壮性判断
67 if (ph == NULL || pos < 0 || pos > ph->length)
68 printf("插入元素时，参数传入有误！");
69
70 //如果参数无误，就要为元素分配结点空间
71 pval = (pNode)malloc(sizeof(struct Node));
72 pval->data = val; //将值val保存到此结点中
73
74 //接下来要判断在哪个位置插入元素，先判断链表是否为空
75 if (IsEmpty(ph)) //如果链表为空
76 {
77 ph->next = pval; //直接将结点插入到头结点后
78 pval->next = NULL;
79 pval->pre = NULL; //第一个结点不回指头结点
80 }
81 else //如果双链表不为空，则要判断是插入哪个位置
82 {
83 pNode pCur = ph->next;
84 if (pos == 0) //在第一个位置（头结点后）插入
85 {
86 ph->next = pval; //头结点指向pval
87 pval->pre = NULL;
88 pval->next = pCur; //pval的后继指针指向pCur
89 pCur->pre = pval; //pCur前驱指针指向pval
90 }
91 else //如果不是插入到第一个位置
92 {
93 for (int i = 1; i < pos; i++) //就要遍历链表找到要插入的位置
94 {
95 pCur = pCur->next; //pCur指针向后移
96 }
97 //循环结束后，此时pCur指向的是要插入的位置
98 pval->next = pCur->next; //指针断开再连接的过程
99 pCur->next->pre = pval;
100 pval->pre = pCur;
101 pCur->next = pval;
102 }
103 }
104 ph->length++;
105 return 1;
106 }
107
108 pNode DlistDelete(pHead ph, int val) //删除双向链表ph中的元素val
109 {
110 if (ph == NULL || ph->length == 0)
111 {
112 printf("参数传入有误！");
113 }
114 //如果参数无误，则遍历找到值为val的元素，然后将其删除
115 pNode pval = DlistFind(ph, val); //找到值所在的结点
116 if (pval == NULL)
117 {
118 return NULL;
119 }
120 printf("将其删除\n");
121 //因为双链表中的结点既有前驱结点又有后继结点
122 pNode pRe = pval->pre; //pRe指向pval结点的前驱结点
123 pNode pNext = pval->next; //pNext指向pval结点的后继结点
124
125 pRe->next = pNext;
126 pNext->pre = pRe;
127 return pval;
128 }
129
130 pNode DlistFind(pHead ph, int val) //查找某个元素
131 {
132 if (ph == NULL)
133 {
134 printf("参数传入有误！");
135 }
136 //如果参数无误，则需要遍历双链表，查找要找的元素
137 pNode pTmp = ph->next; //此过程与单链表无异
138 do
139 {
140 if (pTmp->data == val)
141 {
142 printf("有此元素！\n");
143 return pTmp;
144 }
145 pTmp = pTmp->next;
146 } while (pTmp->next != NULL); //循环条件是直到链表结尾
147
148 printf("没有值为%d的元素!\n", val);
149 return NULL;
150 }
151
152 void DlistDestory(pHead ph) //销毁链表
153 {
154 pNode pCur = ph->next;
155 pNode pTmp;
156 if (ph == NULL)
157 printf("参数传入有误！");
158
159 while (pCur->next != NULL)
160 {
161 pTmp = pCur->next;
162 free(pCur); //将结点释放
163 pCur = pTmp;
164 }
165 ph->length = 0; //回到初始化状态
166 ph->next = NULL;
167 }
168
169 void printFront(pHead ph) //打印双向链表中的元素，从前往后打印
170 {
171 if (ph == NULL)
172 {
173 printf("参数传入有误！");
174 }
175 pNode pTmp = ph->next;
176 while (pTmp != NULL)
177 {
178 printf("%d ", pTmp->data);
179 pTmp = pTmp->next;
180 }
181 printf("\n");
182 }
183
184 void printLast(pHead ph) //倒序打印，从链表末尾开始向前打印
185 {
186 if (ph == NULL)
187 {
188 printf("参数传入有误！");
189 }
190 pNode pTmp = ph->next;
191 while (pTmp->next != NULL)
192 {
193 pTmp = pTmp->next; //先将指针pTmp移动到末尾结点
194 }
195 for (int i = --ph->length; i >= 0; i--) //从末尾结点向前打印元素
196 {
197 printf("%d ", pTmp->data);
198 pTmp = pTmp->pre;
199 }
200 printf("\n");
201 }main.c //测试文件
202 #define _CRT_SECURE_NO_WARNINGS
203 #include "dlist.h"
204 #include <stdio.h>
205 #include <stdlib.h>
206 int main()
207 {
208 //创建一个双向链表
209 pHead ph = NULL;
210 ph = DlistCreate();
211
212 //向链表中插入元素
213 int num;
214 printf("请输入要插入的元素，输入0结束：\n");
215 while (1)
216 {
217 scanf("%d", &num);
218 if (num == 0)
219 break;
220 DlistInsert(ph, 0, num); //本测试程序从头部插入
221 }
222
223 printf("双链表长度：%d\n", getLength(ph));
224 printFront(ph); //从前往后打印双链表的元素
225 DlistInsert(ph, 3, 99); //在3位置插入新元素99
226 printFront(ph); //然后再从前往后打印双链表的元素
227 printLast(ph); //从后往前打印元素
228
229 int val;
230 printf("请输入要查找的元素：\n");
231 scanf("%d", &val);
232 DlistFind(ph, val); //查找元素
233
234 int del;
235 printf("请输入要删除的元素：\n");
236 scanf("%d", &del);
237 DlistDelete(ph, del); //删除元素
238 printFront(ph); //打印删除元素后的链表
239
240 DlistDestory(ph); //销毁链表
241 printf("双链表销毁成功！\n此时链表长度为：%d\n", ph->length);
242
243 system("pause");
244 return 0;
245 }运行结果如图1所示。
图1 例1运行结果
在例1双链表的实现中，只实现了双链表的增删改查几个基本功能。双向链表的插入删除操作，实现起来比单链表的稍微复杂一些，其他操作都无大的改动。双链表是可以倒序遍历的，为了测试该双链表的功能，我们在最后的打印链表元素时，增加了一个倒序打印函数printLast()，从后往前打印链表的元素。
相对于单链表来说，双向链表要复杂一些，因为它多了一个前驱指针，所以对于插入和删除操作的实现要格外小心。另外，因为双链表中的每个结点要记录两个指针，所以空间消耗要略多一些。不过由于它良好的对称性，使得对某个结点的前后两个结点操作更灵活，也使算法的时间效率得到了提高，说到底，就是用空间换时间。
点击此处
隐藏目录
隐藏目录
