11.4 链表
考点4 链表
真考链接
考点4属于重点理解、重点掌握内容。在选择题中的考核概率为60%。操作题中常常考查链表的建立、插入和删除。在操作题中的考核概率为25%。
链表是一种常见的重要的数据结构，它是动态地进行存储单元分配的一种结构。图11.1所示是一种简单的链表。
图11.1 链表示意图
从图11.1所示的链表示意图可以看出，链表中的各元素在内存中不一定是连续存放的。要找链表中某一元素，必须先找到上一个元素，根据该元素提供的下一元素的地址才能找到下一个元素。所以，如果没有头指针（head），则整个链表便无法访问。另外，这种链表的数据结构，必须利用指针变量才能实现。即一个节点中应包含一个指针变量，用它存放下一节点的地址。当然也可以不通过指针变量，用其他方式也可以构建简单链表，请参考有关数据结构的教材。
下面通过一个例子来说明如何建立和输出一个简单链表。
＃include ＜string.h＞
＃include ＜stdio.h＞
struct node
｛ int data；
struct node *next；
｝；
typedef struct node NODETYPE；
main（）
｛ NODETYPE s1，s2，s3，*begin，*p；
s1.data=100；／*给变量中的data域赋值*／
s2.data=200；
s3.data=300；
begin=&s1；
s1.next=&s2； ／*使s1的域next指向s2*／
s2.next=&s3；
s3.next=NULL；
p=begin；／*移动p，使之依次指向s1、s2、s3，输出它们data域中的值*／
while（p）
｛ printf（＂% d＂，p-＞data）；
p=p-＞next；／* p顺序后移 *／
｝
printf（＂\n＂）；
｝
main（）函数中定义的变量s1、s2、s3都是结构体变量，它们都含有data和next两个成员。变量begin和p是指向NODETYPE结构体类型的指针变量，它们与结构体变量s1、s2、s3中的成员变量next类型相同。执行赋值语句后，begin中存放s1变量的地址，变量s1的成员s1.next中存放变量s2的地址……最后一个变量s3的成员s3.next置成NULL，从而把同一类型的结构体变量s1、s2、s3“链接”到一起，形成“链表”。
在此例中，链接到一起的每个节点（结构体变量s1、s2、s3）都是通过定义，由系统在内存中开辟了固定的存储单元（不一定连续）。在程序执行的过程中，不可能人为地再产生新的存储单元，也不可能人为地使已开辟的存储单元消失。从这一角度出发，可称这种链表为“静态链表”。在实际中，使用更广泛的是一种“动态链表”。
小提示
但链表最后一个节点的指针域不再存放地址时，就置成NULL值，标志着链表的结束，链表的每个节点只有一个指针域，每个指针域存放下一个节点的地址。
每一个链表都用一个“头指针”变量来指向链表的开始，称为head指针。在head指针中存放了链表第一个节点的地址。
真题精选
下列给定程序中，函数fun（）的功能是：计算一个带头节点的单向链表中各节点的数据域中数值之和，结果作为函数值返回。
请在标号处填入正确的内容，使程序得出正确的结果。
注意：部分源程序给出如下。不得增行或删行，也不得更改程序的结构。
试题程序
＃include ＜stdio.h＞
＃include ＜stdlib.h＞
＃define N 8
typedef struct list
｛ int data；
struct list *next；
｝SLIST；
SLIST *creatlist（int *）；
void outlist（SLIST *）；
int fun（SLIST *h）
｛ SLIST *p；int s=0；
p=h-＞next；
while（p）
｛ s+ = p-＞【1】；
p=p-＞【2】；
｝
return s；
｝
main（）
｛ SLIST *head；
int a[N] =｛12，87，45，32，91，16，20，48｝；
head=creatlist（a）；outlist（head）；
printf（＂\nsum=% d\n＂，fun（【3】））；
｝
SLIST *creatlist（int a[]）
｛ SLIST *h，*p，*q；int i；
h = p =（SLIST *）malloc（sizeof （SLIST））；
for（i=0；i＜N；i++）
｛ q =（SLIST *）malloc（sizeof （SLIST））；
q-＞data=a[i]；p-＞next=q；p=q；
｝
p-＞next=NULL；
return h；
｝
void outlist（SLIST *h）
｛ SLIST * p；
p=h-＞next；
if（p==NULL）
printf（＂The list is NULL！\n＂）；
else
｛ printf（＂\nHead ＂）；
do
｛ printf（＂-＞% d＂，p-＞data）；
p=p-＞next；
｝
while（p！=NULL）；
printf（＂-＞End\n＂）；
｝
｝
【答案】【1】 data 【2】 next 【3】 head
【解析】本题考查：链表数据结构，节点的表示方法；掌握链表数据结构的基本思想。
本题考查的是链表的数据结构，需利用指针变量才能实现，一个节点中应包含一个指针变量，用来存放下一个节点的地址。
建立单向链表的一般步骤是：建立头指针→建立第一个节点→头指针指向第一个节点→建立第二个节点→第一个节点的指针指向第二个节点→……→最后一个节点的指针指向NULL。
标号【1】：变量s用来累加各节点的数据域，因此该处应为data。
标号【2】：每次循环结束时，指针p指向下一个节点，即p=p-＞next；。
标号【3】：由被调用函数的形参列表可知，此处应为指针类型变量，因为要对链表的数据域求和，所以将链表的头指针传给被调用函数。
考点5 建立单向链表
真考链接
考点5难度适中，属于需重点掌握的内容。在选择题中的考核概率为10%。操作题中对此知识点的考查常在程序填空题中出现，考核概率为15%。
单向链表中，每个节点应该由两个成员组成：一个是数据成员；另一个是指向自身结构的指针类型成员。
节点的类型定义如下：
structslist
｛ intdata；
structslist*next；
}；
typedefstructslistSLIST；
（1）建立单向链表的主要操作步骤如下。
①读取数据。
②生成新节点。
③将数据存入节点的成员变量中。
④将新节点插入到链表中。重复上述操作直至输入结束。
（2）顺序访问链表中各节点的数据域。
（3）在单向链表中插入节点。在单向链表中插入节点，首先要确定插入的位置。当插入节点插在指针所指的节点之前，称为“前插”，当插入节点插在指针所指的节点之后，称为“后插”。
当进行“前插”操作时，需要3个工作指针（假设为s1、s2和s3）。用s1来指向新开辟的节点；用s2指向插入的位置；用s3指向s2的前趋节点（由于是单向链表，没有指针s3，就无法通过s2去指向它所指的前趋节点）。
（4）删除单向链表中的节点。为了删除单向链表中的某个节点，首先要找到待删节点的前趋节点，然后将此前趋节点的指针域去指向待删节点的后续节点，最后释放被删节点所占存储空间即可。
真题精选
【例1】以下函数creat（）用来建立一个带头节点的单向链表，新产生的节点总是插在链表的末尾，节点数据域中的数值从键盘输入，以字符“？”作为输入结束标识。单向链表的头指针作为函数值返回。请填空。
试题程序
＃include ＜stdio.h＞
struct list
｛ char data；
struct list *next；
｝；
struct list * creat（）
｛ struct list *h，*p，*q；
char ch；
h=______malloc（sizeof（______））；
p=q=h；
ch=getchar（）；
while（ch！= ＇？ ＇）
｛ p=______malloc（sizeof（______））；
p-＞data=ch；
q-＞next=p；
q=p；
ch=getchar（）；
｝
p-＞next= ＇ \0＇；
return______；
｝
【答案】（structlist*） structlist （structlist*） structlis th
【解析】前4个空处要求填入的内容是相同的，都是为了开辟一个链表节点的动态存储单元。由说明语句可知，节点的类型为structlist，因此在第一空处和第三空处应填指针强制类型转换（structlist*），在第二空处和第四空处应填节点的类型名structlist。函数的最后应当把所建链表的头指针作为函数值返回，而且函数的类型也是structlist*要求返回一个地址，在函数中，链表的头节点放在h中，所以在第五空处应填h。
【例2】下列给定程序中已建立了一个带头节点的单向链表，在main（）函数中将多次调用fun（）函数，每调用一次，输出链表尾部节点中的数据，并释放该节点，使链表缩短。
请在标号处填入正确的内容，使程序得出正确的结果。
注意：部分源程序给出如下。不得增行或删行，也不得更改程序的结构。
试题程序
＃include ＜stdio.h＞
＃include ＜stdlib.h＞
＃define N 8
typedef struct list
｛ int data；
struct list *next；
｝SLIST；
void fun（SLIST *p）
｛ SLIST *t，*s；
t=p-＞next；s=p；
while（t-＞next！= NULL）
｛ s=t；
t=t-＞【1】；
｝
printf（＂% d ＂，【2】）；
s-＞next=NULL；
free（【3】）；
｝
SLIST *creatlist（int *a）
｛ SLIST *h，*p，*q；int i；
h = p =（SLIST *）malloc（sizeof （SLIST））；
for（i=0；i＜N；i++）
｛ q =（SLIST *）malloc（sizeof （SLIST））；
q-＞data=a[i]；p-＞next=q；p=q；
｝p-＞next=NULL；
return h；
｝
void outlist（SLIST *h）
｛ SLIST *p；
p=h-＞next；
if（p==NULL）
printf（＂\nThe list is NULL！\n＂）；
else
｛ printf（＂\nHead＂）；
do ｛printf（＂-＞% d＂，p-＞data）；
p=p-＞next；｝while（p！=NULL）；
printf（＂-＞End\n＂）；
｝
｝
main（）
｛ SLIST *head；
int a[N] =｛11，12，15，18，19，22，25，29｝；
head=creatlist（a）；
printf（＂\nOutput from head：\n＂）；
outlist（head）；
printf（＂\nOutput from tail：\n＂）；
while（head-＞next！= NULL）｛
fun（head）；
printf（＂\n\n＂）；
printf（＂\nOutput from head again：\
n＂）；
outlist（head）；
｝
｝
【答案】【1】 next 【2】 t-＞data 【3】 t
【解析】本题考查：malloc函数、free函数、链表数据结构、节点的表示方法，掌握链表数据结构的基本思想；释放内存空间函数free。
标号【1】：因为是链表操作，所以要使t逐一往后移动，语句为t=t-＞next；。
标号【2】：输出链表节点的数据域，即t-＞data。
标号【3】：使用free函数将t所指向的内存空间释放。释放内存空间函数free的调用形式为：free（void*p）；。
功能：释放p所指向的一块内存空间，p是一个任意类型的指针变量，它指向被释放区域的首地址。被释放区应该是由malloc或calloc函数所分配的区域。
考点6 顺序访问链表中各节点的数据域
真考链接
考点6难度偏大，属于需重点理解的内容。在选择题中的考核概率为10%。操作题对此知识点的考查常在程序修改题中出现，考核概率为15%。
所谓“访问”，可以理解为取各节点的数据域中的值进行各种运算，修改各节点的数据域中的值等一系列的操作。
输出单向链表各节点数据域中内容的算法比较简单，只需利用一个工作指针（p），从头到尾依次指向链表中的每个节点，当指针指向某个节点时，就输出该节点数据域中的内容，直到遇到链表结束标识为止。如果是空链表，就只输出提示信息并返回调用函数。
函数如下：
void printlist（NODETYPE *head）
｛ NODETYPE *p；
p=head-＞next； ／*指向头节点后的第一个节点*／
if（p== ＇\0＇） ／*链表为空时*／
printf（＂Linklist is null\n＂）；
else ／*链表不为空时*／
｛ printf（＂head＂）；
do
｛ printf（＂-＞% d＂，p-＞data）； ／*输出当前节点数据域中的值*／
p=p-＞next； ／*move指向下一个节点*／
｝while（p！ = ＇\0＇）； ／*未到链表尾，继续循环下去*／
｝
printf（＂-＞end\n＂）；
｝
真题精选
下列给定程序中，函数fun（）的功能是：在带头节点的单向链表中，查找数据域中值为ch的节点。找到后通过函数值返回该节点在链表中所处的顺序号；若不存在值为ch的节点，函数返回0值。
请在标号处填入正确的内容，使程序得出正确的结果。
注意：部分源程序给出如下。不得增行或删行，也不得更改程序的结构。
试题程序
＃include ＜stdio.h＞
＃include ＜stdlib.h＞
＃define N 8
typedef struct list
｛ int data；
struct list *next；
｝SLIST；
SLIST *creatlist（char *）；
void outlist（SLIST *）；
int fun（SLIST *h，char ch）
｛ SLIST *p；int n=0；
p=h-＞next；
while（p！=【1】）
｛ n++；
if（p-＞data==ch）return【2】；
else p=p-＞next；
｝
return 0；
｝
m ain（）
｛ SLIST *head；int k；char ch；
char a[N] =｛＇m＇， ＇p＇， ＇g＇， ＇a＇， ＇w＇， ＇x＇， ＇r＇， ＇d＇｝；
head=creatlist（a）；
outlist（head）；
printf（＂Enter a letter：＂）；
scanf（＂% c＂，&ch）；
k=fun（【3】）；
if（k ==0） printf（＂\nNot found！\n＂）；
else
printf（＂The sequence number is：%d\n＂，k）；
｝
SLIST *creatlist（char *a）
｛ SLIST *h，*p，*q； int i；
h = p =（SLIST *）malloc（sizeof （SLIST））；
for（i=0；i＜N；i++）
｛ q =（SLIST *）malloc（sizeof （SLIST））；
q-＞data=a[i]；p-＞next=q；p=q；
｝
p-＞next=0；
return h；
｝
void outlist（SLIST *h）
｛ SLIST *p；
p=h-＞next；
if（p==NULL）
printf（＂\nThe list is NULL！\n＂）；
else
｛ printf（＂\nHead＂）；
do
｛ printf（＂-＞% c＂，
p-＞data）；
p=p-＞next；
｝while（p！=NULL）；
printf（＂-＞End\n＂）；
｝
｝
【答案】【1】 NULL 【2】 n 【3】 head，ch
【解析】本题考查：链表相关知识；while循环语句；函数返回值。
标号【1】：while循环语句判断是否到达链表结尾，链表结尾节点指针域是NULL。
标号【2】：若找到指定字符，则通过return语句将该节点在链表的顺序号返回给main（）函数。
标号【3】：函数调用语句，其形式是：函数名（实际参数表），因此根据函数定义语句填入head，ch。
考点7 在链表中插入和删除节点
真考链接
考点7 属于重点理解重点掌握的内容。在选择题中的考核概率为30%。操作题对此知识的考查常在编程题中出现，考核概率为20%。
1.在链表中插入节点
在单向链表中插入节点，首先要确定插入的位置。插入节点在指针p所指的节点之前称为“前插”，插入节点在指针p所指的节点之后称为“后插”。“前插”操作中各指针的指向如图11.2所示。
当进行前插操作时，需要3个工作指针：用s指向新开辟的节点，用p指向插入的位置，用q指向要插入的前趋节点。
图11.2 “前插”操作中各指针的指向
2.删除链表中的节点
为了删除单向链表中的某个节点，首先要找到待删除的节点的前趋节点（即当前要删除节点的前面一个节点），然后将此前趋节点的指针域指向待删除节点的后续节点（即当前要删除节点的下一个节点），最后释放被删除节点所占的存储空间即可。
常见问题
动态链表中，节点有何特点？
在动态链表中，每个节点元素均没有自己的名字，只能靠指针维系节点元素之间的连续关系。一旦某个元素的指针“断开”，后续元素就再也无法找寻。
真题精选
下列给定程序中已建立了一个带头节点的单向链表，请向链表中插入一个整数，使插入后的链表仍然有序。请在标号处填入正确的内容，使程序得出正确的结果。
注意：部分源程序给出如下。不得增行或删行，也不得更改程序的结构。
试题程序
＃include ＜stdio.h＞
＃include ＜stdlib.h＞
＃define N 8
typedef struct list
｛ int data；
struct list *next；
｝SLIST；
void fun（SLIST *P，int m）
｛ SLIST *t，*s；
s=（SLIST *）malloc（sizeof（SLIST））；
S-＞data= 【1】 ；
t=p-＞next；
while（t！=NULL&&t-＞data＜m）
｛p=t；t= 【2】 ；｝
【3】
｝
SLIST *creatlist（int *a）
｛ SLIST *h，*p，*q；int i；
h = p =（SLIST *）malloc（sizeof （SLIST））；
for（i=0；i＜N；i++）
｛ q =（SLIST *）malloc（sizeof （SLIST））；
q-＞data=a[i]；p-＞next=q；p=q；
｝p-＞next=0；
return h；
｝
void outlist（SLIST *h）
｛ SLIST *p；
p=h-＞next；
if（p==NULL）
printf（＂\nThe list is NULL！\n＂）；else
｛ printf（＂\nHead＂）；
do
｛ printf（＂-＞% d＂，p-＞data）；
p=p-＞next；
｝while（p！=NULL）；
printf（＂-＞End\n＂）；
｝
｝
main（）
｛ SLIST *head；
int a[N] = ｛11，12，15，18，19，22，25， 29｝，n；
head=creatlist（a）；
printf（＂\nThe list before inpreeing：\n＂）；
outlist（head）；
printf（＂Intput a integer：＂）；
scanf（＂% d＂，&n）；
printf（＂\n The list afeer inputting：\n＂）；
fun（head，n）；
outlist（head）；
｝
【答案】【1】 m 【2】 t-＞next 【3】 s-＞next=t；p-＞next=s；
【解析】标号【1】：申请一个节点空间，并将形参m中的值存入新节点的数据域中。
标号【2】：使用循环语句遍历链表，查找待插入的位置，指针p和t依次向后移动。
标号【3】：将新节点插入到链表中，插入时先将节点的指针域指向t，再将节点p的指针域指向s。