我的书签
添加书签
移除书签6.5 传统链表的实现方法及注意事项
可能有不少人会疑惑链表还分什么传统链表和非传统链表吗？在此简单解释一下，这里所说的传统链表，是相对下一节所要讲解的Linux内核中的双向循环链表而言的。由于Linux内核中双向循环链表的特殊性，在此把以往在C语言中所学习的链表统称为传统链表。
我们知道，数组是由数组元素所组成的，链表同样是由链表元素所组成的，但是链表元素的特殊性在于，它是由不连续的内存单元块按照一种逻辑顺序所组成的数据结构。链表中的每个元素被称为结点，所以结点是构成链表的最小单元，结点中包含两部分信息，一部分是在结点中存储的数据信息，另一部分是相邻结点的地址信息。
如图6-4所示为单向链表，在单向链表中，结点之间的指向是单向的，其中的结点由两部分组成，一部分是数据域，用来存储数据信息；另一部分是指针域，用来存储下一个结点的地址。需要注意的是，在单向链表中有一个头结点，它仅含有指针域，没有数据域；而在链表的尾结点中将指针域赋值为NULL。
图 6-4 单向链表
如果是单向循环链表，那么尾结点的指针域就不再为NULL，而是与头结点的指向相同，指向链表的第一个结点，如图6-5所示。
图 6-5 单向循环链表
如图6-6所示为双向链表，双向链表与单向链表的不同之处在于结点多了一个指针域，在单向链表中只有一个指针域用来存储后一个结点的地址信息，而双向链表中多了一个指针域用来存储前一个结点的地址。在此，将保存前一个结点地址信息的指针域称为前指针域，将保存后一个结点地址信息的指针域称为后指针域。这两个指针域使得通过当前结点不仅可以访问后一个结点，还可以访问前一个结点。注意，双向链表的尾结点的后指针域为NULL。
图 6-6 双向链表
如果是双向循环链表，那么尾结点的后指针域不再为NULL，如图6-7所示，此时尾结点的后指针域指向的是头结点所指向的结点。
链表的创建大致可以分为以下几步：
1）创建链表头。
2）创建结点。
3）将链表头指向链表的第一个结点。
4）继续创建结点，同时将结点加入到链表中适当的位置。
图 6-7 双向循环链表
接下来通过上面的步骤创建一个单链表。
include＜stdio.h＞
include＜stdlib.h＞
include＜string.h＞
define N 3
struct Stu
{
struct Stu*next；
char name[10]；
int score；
}；
struct Stu_head
{
struct Stu*head；
}；
struct Stu_head*head_create（）
{
struct Stu_head*single_link；
if（（single_link=（struct Stu_head*）malloc（sizeof（struct Stu_head）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（single_link！=NULL）
{
single_link-＞head=NULL；
}
return single_link；
}
struct Stu*node_create（）
{
struct Stu*node；
if（（node=（struct Stu*）malloc（sizeof（struct Stu）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（node！=NULL）
{
node-＞next=NULL；
printf（"请输入学生的姓名、成绩："）；
scanf（"%s%d"，＆node-＞name，＆node-＞score）；
}
return node；
}
void node_append（struct Stu_head*single_link）
{
struct Stu*node=NULL；
struct Stu*cursor=NULL；
node=node_create（）；
if（single_link-＞head==NULL）
{
single_link-＞head=node；
}
else
{
cursor=single_link-＞head；
while（cursor！=NULL＆＆cursor-＞next！=NULL）
{
cursor=cursor-＞next；
}
cursor-＞next=node；
}
return；
}
void node_print（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
while（iter！=NULL）
{
printf（"%s的成绩为：%d\n"，＆iter-＞name,iter-＞score）；
iter=iter-＞next；
}
return；
}
void node_destroy（struct Stu*node）
{
if（node！=NULL）
{
node-＞next=NULL；
free（node）；
}
return；
}
void single_link_destroy（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
struct Stu*next=NULL；
while（iter！=NULL）
{
next=iter-＞next；
node_destroy（iter）；
iter=next；
}
single_link-＞head=NULL；
free（single_link）；
return；
}
int main（）
{
int i；
struct Stu_head*single_head=head_create（）；
for（i=0；i＜N；i++）node_append（single_head）；
node_print（single_head）；
single_link_destroy（single_head）；
return 0；
}
运行结果：
请输入第1个人的姓名、成绩：张晓燕236
请输入第2个人的姓名、成绩：王大鹏369
请输入第3个人的姓名、成绩：方小军458
张晓燕的成绩为236
王大鹏的成绩为369
方小军的成绩为458
在上面的代码中，把结点的信息分为两部分，一部分是数据域，即学生姓名name和成绩score，另一部分是指针域next，其中保存的是下一个结点的地址。按照上面创建链表的操作步骤，先通过head_create（）函数创建一个链表头，接下来通过node_create（）函数创建结点，创建结点的操作在node_append（）函数中进行，该函数的功能是将创建好的结点插入到链表的末端，作为链表的末端结点。注意，这里需要将链表头指向第一个创建的结点。
为了验证是否成功地实现链表的创建，最后通过一个node_print（）函数打印出每个结点所携带的信息，输出结果表明已经成功实现了链表的创建。
由于结点都是动态申请的，因此最后还要对每个结点申请的内存空间进行释放。释放动态分配的结点空间分为两部分，一部分是含信息结点的释放，另一部分是链表头结点的释放。先调用single_link_destroy（）函数，在该函数中通过一个while循环来判断当前结点是否为有效的链表结点，如果是，先将链表的指针域赋值为NULL，然后释放该链表结点。释放完所有的链表结点之后退出循环体，要注意链表头同样是动态分配的，所以最后也需要通过free（）函数来释放为其分配的内存空间。
上面代码是在单向链表的末端插入结点，在头结点插入的方法与尾结点类似，在此介绍在两个普通结点之间插入新结点的方法，如图6-8所示。
图 6-8 单向链表中结点的插入
注意插入结点前后的变化，插入前，结点n的指针域指向结点n+1，插入之后，结点n的指针域指向的是新插入结点，而原来的结点n+1变为结点n+2，新加入的结点的指针域指向加入新结点前的结点n+1，这样就实现了在单向链表中插入结点。
接下来通过图6-9来说明在单向链表中两个普通结点之间删除结点的方法。
从图6-9中可以看到删除前后链表的变化，删除结点n+1后，原来链表中的结点n+2变为结点n+1，结点n的指针域指向了原结点n+2。需要注意的是，要将删除的结点的指针域赋值为NULL，同时，如果这个结点是动态分配的结点，那么还应该采用free（）函数将其分配的空间释放掉。下面修改上面的代码来实现插入结点和删除结点的操作。
图 6-9 单向链表中结点的删除
include＜stdio.h＞
include＜stdlib.h＞
include＜string.h＞
define N 3
struct Stu
{
struct Stu*next；
char name[10]；
int score；
}；
struct Stu_head
{
struct Stu*head；
}；
struct Stu_head*head_create（）
{
struct Stu_head*single_link；
if（（single_link=（struct Stu_head*）malloc（sizeof（struct Stu_head）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（single_link！=NULL）
{
single_link-＞head=NULL；
}
return single_link；
}
struct Stu*node_create（）
{
struct Stu*node；
if（（node=（struct Stu*）malloc（sizeof（struct Stu）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（node！=NULL）
{
node-＞next=NULL；
printf（"请输入学生的姓名、成绩："）；
scanf（"%s%d"，＆node-＞name，＆node-＞score）；
}
return node；
}
void node_append（struct Stu_head*single_link）
{
struct Stu*node=NULL；
struct Stu*cursor=NULL；
node=node_create（）；
if（single_link-＞head==NULL）
{
single_link-＞head=node；
}
else
{
cursor=single_link-＞head；
while（cursor！=NULL＆＆cursor-＞next！=NULL）
{
cursor=cursor-＞next；
}
cursor-＞next=node；
}
return；
}
struct Stunode_search（struct Stu_headsingle_link,char*name）
{
struct Stu*pos=NULL；
pos=single_link-＞head；
while（pos！=NULL）
{
if（strcmp（pos-＞name,name）==0）
return pos；
else
pos=pos-＞next；
}
if（pos==NULL）
{
printf（"没有查找到该数据！"）；
exit（0）；
}
return NULL；
}
void node_insert（struct Stu*pos）
{
struct Stu*new_node；
printf（"插入信息："）；
new_node=node_create（）；
new_node-＞next=pos-＞next；
pos-＞next=new_node；
return；
}
void node_print（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
while（iter！=NULL）
{
printf（"%s的成绩为：%d\n"，＆iter-＞name,iter-＞score）；
iter=iter-＞next；
}
return；
}
void delete_node（struct Stu_headsingle_link,struct Stunode）
{
struct Stunode_prev，tmp；
tmp=single_link-＞head；
if（tmp==node）
single_link-＞head=tmp-＞next；
else
{
while（tmp！=node）
{
node_prev=tmp；
tmp=tmp-＞next；
}
node_prev-＞next=tmp-＞next；
}
tmp-＞next=NULL；
free（tmp）；
return；
}
void node_destroy（struct Stu*node）
{
if（node！=NULL）
{
node-＞next=NULL；
free（node）；
}
return；
}
void single_link_destroy（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
struct Stu*next=NULL；
while（iter！=NULL）
{
next=iter-＞next；
node_destroy（iter）；
iter=next；
}
single_link-＞head=NULL；
free（single_link）；
return；
}
int main（）
{
int i；
char name[10]；
struct Stu*search_node；
struct Stu_head*single_head=head_create（）；
for（i=0；i＜N；i++）
node_append（single_head）；
node_print（single_head）；
printf（"请输入你要查找结点中的人名："）；
scanf（"%s"，name）；
search_node=node_search（single_head,name）；
node_insert（search_node）；
printf（"\n插入结点后\n"）；
node_print（single_head）；
delete_node（single_head,search_node）；
printf（"\n删除结点后\n"）；
node_print（single_head）；
single_link_destroy（single_head）；
return 0；
}
运行结果：
请输入学生的姓名、成绩：王小欢78
请输入学生的姓名、成绩：张晓笑88
请输入学生的姓名、成绩：王大鹏99
王小欢的成绩为：78
张晓笑的成绩为：88
王大鹏的成绩为：99
请输入你要查找结点中的人名：王小欢
插入信息：请输入学生的姓名、成绩：唐雪梅89
插入结点后
王小欢的成绩为：78
唐雪梅的成绩为：89
张晓笑的成绩为：88
王大鹏的成绩为：99
删除结点后
唐雪梅的成绩为：89
张晓笑的成绩为：88
王大鹏的成绩为：99
上面的代码成功地实现了单向链表中结点的插入和删除操作，先来看结点的查找和插入。先通过结点信息中的人名来查找结点，查找成功就返回结点地址，查找失败就退出。如果查找成功，那么接下来就调用node_insert（）函数将创建的新结点插入到查找到的结点后，插入方法参见图6-8。插入结束之后，就可以根据要求删除查找到的结点。需要注意的是，在删除结点时需要判断删除的结点是否为头结点所指向的结点，如果是，那么要移动头结点，否则就按如图6-9所示的方法进行删除。
对于单向循环链表，它的特殊之处就在于链表尾结点的指针域指向链表的头一个结点。单向循环链表的一般操作方法与单向链表类似，在此就不一一讲解，接下来介绍双向链表。
双向链表比单向链表多了一个指向前结点的前指针域，其实现步骤与前面讲解的单向链表完全相同。下面的代码实现的是双向链表的插入。
include＜stdio.h＞
include＜stdlib.h＞
include＜string.h＞
define N 3
struct Stu
{
struct Stunext，prev；
char name[10]；
int score；
}；
struct Stu_head
{
struct Stu*head；
}；
struct Stu_head*head_create（）
{
struct Stu_head*single_link；
if（（single_link=（struct Stu_head*）malloc（sizeof（struct Stu_head）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（single_link！=NULL）
{
single_link-＞head=NULL；
}
return single_link；
}
struct Stu*node_create（）
{
struct Stu*node；
if（（node=（struct Stu*）malloc（sizeof（struct Stu）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（node！=NULL）
{
node-＞next=NULL；
node-＞prev=NULL；
printf（"请输入学生的姓名、成绩："）；
scanf（"%s%d"，＆node-＞name，＆node-＞score）；
}
return node；
}
void node_append（struct Stu_head*single_link）
{
struct Stu*node=NULL；
struct Stu*cursor=NULL；
node=node_create（）；
if（single_link-＞head==NULL）
{
single_link-＞head=node；
}
else
{
cursor=single_link-＞head；
while（cursor！=NULL＆＆cursor-＞next！=NULL）
{
cursor=cursor-＞next；
}
cursor-＞next=node；
node-＞prev=cursor；
}
return；
}
void node_print（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
while（iter！=NULL）
{
printf（"%s的成绩为：%d\n"，＆iter-＞name,iter-＞score）；
iter=iter-＞next；
}
return；
}
void node_destroy（struct Stu*node）
{
if（node！=NULL）
{
node-＞next=NULL；
free（node）；
}
return；
}
void single_link_destroy（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
struct Stu*next=NULL；
while（iter！=NULL）
{
next=iter-＞next；
node_destroy（iter）；
iter=next；
}
single_link-＞head=NULL；
free（single_link）；
return；
}
int main（）
{
int i；
struct Stu_head*single_head=head_create（）；
for（i=0；i＜N；i++）
node_append（single_head）；
node_print（single_head）；
single_link_destroy（single_head）；
return 0；
}
运行结果：
请输入学生的姓名、成绩：王美清32
请输入学生的姓名、成绩：张梅梅45
请输入学生的姓名、成绩：彭晓倩78
王美清的成绩为：32
张梅梅的成绩为：45
彭晓倩的成绩为：78
双向链表的实现与前面单向链表的实现几乎完全相同，不同之处在于双向链表的结点多了一个前指针域，所以在向链表中添加结点时多了一个对前指针域的操作，这个指针域指向的是前一个结点。在上面的代码中，node_append（）函数中的“node-＞prev=cursor；”语句使前指针域指向当前加入结点的前一个结点。
在上面的代码中采用的是在双向链表的末端插入结点，在末端插入结点的方法与在头结点处插入结点的方法类似，接下来通过图6-10来了解如何在双向链表的两个普通结点之间插入一个结点。
图 6-10 双向链表中结点的插入
在图6-10中，向双向链表中插入结点与前面介绍的向单向链表中插入结点的不同之处在于，多了一个前指针域的操作。接下来再通过图6-11来了解如何在双向链表中删除一个结点。
在图6-11中，注意删除结点前后的变化，在删除结点前，将其前指针域和后指针域赋值为NULL，对于动态分配的结点，需要将其申请的内存空间释放掉；删除结点后，原来的结点n+2就变为了当前链表的结点n+1。
图 6-11 双向链表中结点的删除
对于双向链表中的任何一个结点，可以通过前后指针域对整个链表进行遍历，如：
include＜stdio.h＞
include＜stdlib.h＞
include＜string.h＞
define N 5
struct Stu
{
struct Stunext，prev；
char name[10]；
int score；
}；
struct Stu_head
{
struct Stu*head；
}；
struct Stu_head*head_create（）
{
struct Stu_head*single_link；
if（（single_link=（struct Stu_head*）malloc（sizeof（struct Stu_head）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（single_link！=NULL）
{
single_link-＞head=NULL；
}
return single_link；
}
struct Stu*node_create（）
{
struct Stu*node；
if（（node=（struct Stu*）malloc（sizeof（struct Stu）））==NULL）
{
printf（"分配空间失败！"）；
exit（0）；
}
if（node！=NULL）
{
node-＞next=NULL；
node-＞prev=NULL；
printf（"请输入学生的姓名、成绩："）；
scanf（"%s%d"，＆node-＞name，＆node-＞score）；
}
return node；
}
void node_append（struct Stu_head*single_link）
{
struct Stu*node=NULL；
struct Stu*cursor=NULL；
node=node_create（）；
if（single_link-＞head==NULL）
{
single_link-＞head=node；
}
else
{
cursor=single_link-＞head；
while（cursor！=NULL＆＆cursor-＞next！=NULL）
{
cursor=cursor-＞next；
}
cursor-＞next=node；
node-＞prev=cursor；
}
return；
}
struct Stunode_search（struct Stu_headsingle_link,char*name）
{
struct Stu*pos=NULL；
pos=single_link-＞head；
while（pos！=NULL）
{
if（strcmp（pos-＞name,name）==0）
return pos；
else
pos=pos-＞next；
}
if（pos==NULL）
{
printf（"没有查找到该数据！"）；
exit（0）；
}
return NULL；
}
void node_print（struct Stu*cursor,int mark）
{
struct Stu*iter=cursor；
while（iter！=NULL）
{
if（0==mark）
iter=iter-＞next；
else
iter=iter-＞prev；
if（NULL！=iter）
printf（"%s的成绩为：%d\n"，＆iter-＞name,iter-＞score）；
}
return；
}
void node_destroy（struct Stu*node）
{
if（node！=NULL）
{
node-＞next=NULL；
free（node）；
}
return；
}
void single_link_destroy（struct Stu_head*single_link）
{
struct Stu*iter=single_link-＞head；
struct Stu*next=NULL；
while（iter！=NULL）
{
next=iter-＞next；
node_destroy（iter）；
iter=next；
}
single_link-＞head=NULL；
free（single_link）；
return；
}
int main（）
{
int i；
char name[10]；
struct Stu*search_node；
struct Stu_head*single_head=head_create（）；
for（i=0；i＜N；i++）
node_append（single_head）；
printf（"请输入所有查找结点的人名："）；
scanf（"%s"，name）；
search_node=node_search（single_head,name）；
printf（"\n查找结点后面的结点信息\n"）；
node_print（search_node，0）；
printf（"\n查找结点前面的结点信息\n"）；
node_print（search_node，1）；
single_link_destroy（single_head）；
return 0；
}
运行结果：
请输入学生的姓名、成绩：张晓敏34
请输入学生的姓名、成绩：萧大鹏67
请输入学生的姓名、成绩：范德萨89
请输入学生的姓名、成绩：田晓梅99
请输入学生的姓名、成绩：庞大天23
请输入所有查找结点的人名：范德萨
查找结点后面的结点信息
田晓梅的成绩为：99
庞大天的成绩为：23
查找结点前面的结点信息
萧大鹏的成绩为：67
张晓敏的成绩为：34
上面的运行结果表明成功地实现了通过双向链表中的任何一个结点遍历整个链表。
对双向循环链表的操作，与前面所讲的双向链表的操作类似，最大的区别在于双向循环链表是首尾相连的一个“闭环”，如图6-12所示，所以从其中任何一个结点开始可以单方向遍历整个链表。在构成双向循环链表的过程中需要注意的一个重点就是首尾相连，即尾结点的后指针域指向首结点，而首结点的前指针域指向末结点。
图 6-12 双向循环链表
