11.4 链表

考点4 链表

真考链接

考点4属于重点理解、重点掌握内容。在选择题中的考核概率为60%。操作题中常常考查链表的建立、插入和删除。在操作题中的考核概率为25%。

链表是一种常见的重要的数据结构，它是动态地进行存储单元分配的一种结构。图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指向要插入的前趋节点。

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。