《程序设计基础》课程教学资源（教材讲义）3、链表

第13章链表 在程序设计的基本工具中，可以实现批量数据存储的结构主要有两类，一是前面介绍 过的数组，可以通过连续的地址空间来存放批量数据：二是链表，通过其所包含的多个结 点实现对批量数据的存储。 用数组来存储批量数据，必须预先指定数组的大小（即定义数组的长度），如果事先 不能确定元素的个数，就必须要定义一个尽可能大些的数组，以便能够满足可能的存储需 求。但这样做又会带来另一个问题：如果实际数组元素没有那么多的话，便造成了大量的 存储空间的浪费。 如果用链表来存储批量数据，就可以避免数组空间使用带来的问题，因为链表本身是 一种动态的存储结构，不需要预先指定空间大小，可以根据运行的需要动态地分配与释放 内存。 本章在介绍动态内存分配的基础上，重点介绍单链表的概念、操作以及基本的应用。 13.1动态内存分配 13.1.1C程序的内存划分 一个由C编译的程序占用的内存分为以下几个部分。 (1)栈区(stack):由编译器自动分配、 释放，通常用于存放函数的参数值、局部 内存高端 变量的值等。 →型 (2)堆区(heap):一般由程序员分配， 释放，若程序员不释放，程序结束时可能 → 由操作系统回收。 (3)全局区（静态区）(static):全局 个 变量和静态变量的存储是放在一块的，初 推(heco) →身动内在 始化的全局变量和静态变量在一块区域， 未初始化的全局变最和未初始化的静态变 静态存储区(s做d → 量在相邻的另一块区域。程序结束后由系 统释放。 常里存转区 今字符闲常量 (4)文字常量区：常量字符串放在这 程序代码区 个区域里，程序结束后由系统释放。 →程序指代 (5)程序代码区：存放函数体的二进 内存低 制代码。 图13.1C程序的内存映像

第 13 章 链 表 在程序设计的基本工具中，可以实现批量数据存储的结构主要有两类，一是前面介绍 过的数组，可以通过连续的地址空间来存放批量数据；二是链表，通过其所包含的多个结 点实现对批量数据的存储。 用数组来存储批量数据，必须预先指定数组的大小（即定义数组的长度），如果事先 不能确定元素的个数，就必须要定义一个尽可能大些的数组，以便能够满足可能的存储需 求。但这样做又会带来另一个问题：如果实际数组元素没有那么多的话，便造成了大量的 存储空间的浪费。 如果用链表来存储批量数据，就可以避免数组空间使用带来的问题，因为链表本身是 一种动态的存储结构，不需要预先指定空间大小，可以根据运行的需要动态地分配与释放 内存。 本章在介绍动态内存分配的基础上，重点介绍单链表的概念、操作以及基本的应用。 13.1 动态内存分配 13.1.1 C 程序的内存划分 一个由 C 编译的程序占用的内存分为以下几个部分。 （1）栈区（stack）：由编译器自动分配、 释放，通常用于存放函数的参数值、局部 变量的值等。 （2）堆区（heap）：一般由程序员分配、 释放，若程序员不释放，程序结束时可能 由操作系统回收。 （3）全局区（静态区）（static）：全局 变量和静态变量的存储是放在一块的，初 始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变 量在相邻的另一块区域。程序结束后由系 统释放。 （4）文字常量区：常量字符串放在这 个区域里，程序结束后由系统释放。 （5）程序代码区：存放函数体的二进 制代码

13.1.2内存分配方式 在程序运行期间，变量常用的内存分配方式有三种。 (1)从静态存储区域分配：内存在程序编译的时候就已经分配好，这块内存在程序的 整个运行期间都存在，在程序执行结束之后内存空间才会被释放。例如全局变量、static 变量。 (2)在栈区创建：在执行函数时，函数内局部变量的内存单元都可以在栈区创建，所 在的函数执行结束时这些内存单元自动被释放。栈内存分配运算内置于处理器的指令集中， 效率很高，但是分配的内存容量有限。 (3)从堆区分配（亦称动态内存分配）：程序在运行的时候用malloc或new申请内存， 由程序员自己负责用free或delete释放这部分内存。动态内存的生存期由程序员决定，使 用非常灵活。 在之前的程序设计实验中，大家已经发现在定义一个比较大的数组时，用栈区的分配 (即局部数组)时经常会出错，原因是栈区的空间比较小，不能满足太大的数组空间需求。 改用从静态存储区或者堆区分配虽然都可以解决此问题，但相对来说，由于堆区分配可以 做到动态分配与释放，是一种更高效的内存使用方式。 13.1.3动态内存分配函数 对堆内存的动态分配与释放是通过系统提供的一组库函数来实现的，它们在sdib.h (或malloc.h)头文件中声明，主要有malloc、.calloc、.free、realloc函数。 1,malloc函数 函数原型为： void malloc (unsigned int size): 该函数执行后，从堆内存中分配一块sz心大小的内存，并且返回指向该内存起始位置 的指针值，该内存中的内容是未知的。如果分配失败，返回值为NULL。 例如，下面的程序通过动态分配从堆中获取一个整型数组的内存空间 Winclude #include int main() int i,i: int arrav=订U工工： )malloc(isizeof(int)); for(j-0:j<i;j++) scanf ("sd",sarray[j]) for(i=0:i<i:i++) printf("8d\n",array[j]); 2

2 13.1.2 内存分配方式 在程序运行期间，变量常用的内存分配方式有三种。 （1）从静态存储区域分配：内存在程序编译的时候就已经分配好，这块内存在程序的 整个运行期间都存在，在程序执行结束之后内存空间才会被释放。例如全局变量、static 变量。 （2）在栈区创建：在执行函数时，函数内局部变量的内存单元都可以在栈区创建，所 在的函数执行结束时这些内存单元自动被释放。栈内存分配运算内置于处理器的指令集中， 效率很高，但是分配的内存容量有限。 （3）从堆区分配（亦称动态内存分配）：程序在运行的时候用 malloc 或 new 申请内存， 由程序员自己负责用 free 或 delete 释放这部分内存。动态内存的生存期由程序员决定，使 用非常灵活。 在之前的程序设计实验中，大家已经发现在定义一个比较大的数组时，用栈区的分配 （即局部数组）时经常会出错，原因是栈区的空间比较小，不能满足太大的数组空间需求。 改用从静态存储区或者堆区分配虽然都可以解决此问题，但相对来说，由于堆区分配可以 做到动态分配与释放，是一种更高效的内存使用方式。 13.1.3 动态内存分配函数 对堆内存的动态分配与释放是通过系统提供的一组库函数来实现的，它们在 stdlib.h （或 malloc.h）头文件中声明，主要有 malloc、calloc、free、realloc 函数。 1．malloc 函数 函数原型为： void * malloc（unsigned int size）； 该函数执行后，从堆内存中分配一块 size 大小的内存，并且返回指向该内存起始位置 的指针值，该内存中的内容是未知的。如果分配失败，返回值为 NULL。 例如，下面的程序通过动态分配从堆中获取一个整型数组的内存空间： #include #include int main() { int i,j; int *array=NULL; scanf("%d",&i); array=(int*)malloc(i*sizeof(int)); for(j=0;j<i;j++) scanf("%d",&array[j]); for(j=0;j<i;j++) printf("%d\n",array[j]);

return 0: 1 对于malloc函数来说，其分配的堆内存的大小是由参数给定的字节数来确定的，该宁 节数通常由要分配的元素数量以及每个元素所占的字节两个因素构成，i*siz心of(int)即表示 分配i个整型的空间。 由于malloc函数返回的是一个指向void类型的指针，而通常接受堆地址的指针变量 都是有确定的类型指向的，因此在返回之后赋值之前，通常需要把“vod*”指针强制转换 为与赋值号左边的指针变量相同的指针类型，例如： array-(int*)malloc(iesizeof(int)): 中“(int*)”即把返回的地址类型强制转换为整型类型指针，与array的类型相一致。 2.free函数 动态内存使用的特色是在需要时才分配内存，在使用结束后可以释放内存，这样才能 保证高效地使用内存。C程序动态内存的释放是通过fir©cO函数实现的。 free()函数的原型为： void free(void p): 函数的作用是释放指针变量P所指向的动态空间，该空间应该是之前通过动态分配（如 执行malloc(O函数)所获取的堆空间。已分配的堆空间通过free()函数执行后被释放，被释 放的空间能够被之后的变量申请再次使用。 通常，freO函数与malloc()函数成对在程序中使用，以保证动态分配的内存可以及时 得到动态地释放。因此，对上面的程序可以做如下的补充： int main() int i,j; int arrayeNULL: ge月nFtm暴d无31： array=(int*)malloc(isizeof(int)): for(j=0:j<i;j++) scanf("9d",Garray[j]); for(j=0;j<i;j++) printf("8d\n",array[j]); free(array)i return 0: 3.calloc函数 函数原型为： void calloc(unsigned n,unsigned size); 3

3 return 0; } 对于 malloc 函数来说，其分配的堆内存的大小是由参数给定的字节数来确定的，该字 节数通常由要分配的元素数量以及每个元素所占的字节两个因素构成，i*sizeof(int)即表示 分配 i 个整型的空间。 由于 malloc 函数返回的是一个指向 void 类型的指针，而通常接受堆地址的指针变量 都是有确定的类型指向的，因此在返回之后赋值之前，通常需要把“void*”指针强制转换 为与赋值号左边的指针变量相同的指针类型，例如： （array=(int*)malloc(i*sizeof(int))； 中“（int*）”即把返回的地址类型强制转换为整型类型指针，与 array 的类型相一致。. 2．free 函数 动态内存使用的特色是在需要时才分配内存，在使用结束后可以释放内存，这样才能 保证高效地使用内存。C 程序动态内存的释放是通过 free()函数实现的。 free()函数的原型为： void free(void *p); 函数的作用是释放指针变量 p 所指向的动态空间，该空间应该是之前通过动态分配（如 执行 malloc()函数）所获取的堆空间。已分配的堆空间通过 free()函数执行后被释放，被释 放的空间能够被之后的变量申请再次使用。 通常，free()函数与 malloc()函数成对在程序中使用，以保证动态分配的内存可以及时 得到动态地释放。因此，对上面的程序可以做如下的补充： #include #include int main() { int i,j; int *array=NULL; scanf("%d",&i); array=(int*)malloc(i*sizeof(int)); for(j=0;j<i;j++) scanf("%d",&array[j]); for(j=0;j<i;j++) printf("%d\n",array[j]); free(array); return 0; } 3．calloc 函数 函数原型为： void *calloc(unsigned n,unsigned size);

功能是在堆内存区通过动态分配方式分配n个长度为si2e的连续空间。一般用于动态 数组的空间中请。例如，上面的 array=(int*)malloc(isizeof(int)); 就可以用 array=(int*)calloc(i,sizeof(int)); 来代替。 4.realloc函数 如果已经动态分配的内存空间过大或者过小，欲改变已经分配的内存空间的大小，则 可以通过realloc函数来实现。 函数的原型是 void+realloc(void p,unsigned int newsize); 作用是将指针所指的动态内存空间的大小改变为newsizo,如果缩小空间则返回的地址 是原地址：如果扩大空间，则有三种可能：①如果原空间位置有足够的空间可以扩充，返 回的地址与扩充前的地址相同：②如果原位置无足够的空间而其他位置有足够的空间，则 按照newsize心指定的大小重新分配空间，将原有数据从头到尾拷贝到新分配的内存区域， 而后释放原来指针所指内存区域，同时返回新分配的内存区域的首地址：③否则说明内存 无足够的空间可以分配，分配失败，返回值为NULL。 例如，下面的程序利用realloc扩充内存： #include #include int sain( int i (int)ml(f (in)) printf ("8p\n",pn); for(i=0:i<5:i++) scanf ("&d",6pn[i]) pn=(int *)realloc(pn,100*sizeof(int)); printf ("8p\n",pn): for(i=0:i<5:1++) free(pn】 return 0; 13.2单链表概述 链表是实现批量数据存储表示的重要结构，链表有多种形式，这里主要介绍最基本的 4

4 功能是在堆内存区通过动态分配方式分配 n 个长度为 size 的连续空间。一般用于动态 数组的空间申请。例如，上面的 array=(int*)malloc(i*sizeof(int)); 就可以用 array=(int*)calloc(i，sizeof(int)); 来代替。 4．realloc 函数 如果已经动态分配的内存空间过大或者过小，欲改变已经分配的内存空间的大小，则 可以通过 realloc 函数来实现。 函数的原型是： void * realloc(void *p,unsigned int newsize); 作用是将指针所指的动态内存空间的大小改变为 newsize，如果缩小空间则返回的地址 是原地址；如果扩大空间，则有三种可能：① 如果原空间位置有足够的空间可以扩充，返 回的地址与扩充前的地址相同；② 如果原位置无足够的空间而其他位置有足够的空间，则 按照 newsize 指定的大小重新分配空间，将原有数据从头到尾拷贝到新分配的内存区域， 而后释放原来指针所指内存区域，同时返回新分配的内存区域的首地址；③ 否则说明内存 无足够的空间可以分配，分配失败，返回值为 NULL。 例如，下面的程序利用 realloc 扩充内存： #include #include int main() { int i; int *pn=(int *)malloc(5*sizeof(int)); printf("%p\n",pn); for(i=0;i<5;i++) scanf("%d",&pn[i]); pn=(int *)realloc(pn,100*sizeof(int)); printf("%p\n",pn); for(i=0;i<5;i++) printf("%3d",pn[i]); printf("\n"); free(pn); return 0; } 13.2 单链表概述 链表是实现批量数据存储表示的重要结构，链表有多种形式，这里主要介绍最基本的

链表结构一一单链表。 单链表中的每一个数据元素是通过一个称之为“结点”的结构来存储表示的，每个结 点占据一个内存空间，多个结点所占的存储空间是离散的，结点之间通过专门的指针相互 链接构成一个整体。从本质上看，链表就是一个结点的序列。 13.2.1结点的结构 结点是链表中存放数据元素的基本单元，用一个结构体的形式来表示。一个结点至少 应该包含两部分：一是数据域(data),用以存放该结点需要存放的数据元素的数据值：二 是指针域(ext),通常用以存放下一个结点的存储地址，由此将多个结点构成一个整体， 如图13.2所示。 假设一个链表结点的数据域只存放一个整数值，该结点结构可以如下定义： struct node int data: data next struct node *next; 数据城指针城 1 图13.2结点的结构 13.2.2单链表的结构 链表是一个结点的序列，或者说链表是由多个结构相同的结点通过指针域相互链接构 成的一个整体。比如以上面的结点结构形成的链表如图13.3所示。 w一日-2 图13.3简单的链表结构 该链表由4个结点构成，每个结点都包含一个整型的数据域，用以存放本结点的数据 元素值，同时每个结点还都包含一个指针域，用来存放下一个结点的地址，最后一个结点 的指针域为NWLL,记作A。 在该链表中，给出了一个指针变量head,用以存放链表中第一个结点的地址，通过该 指针，可以找到第一个结点，然后再顺着每一个结点的指针域，可以找到其下一个结点， 这样可以依次取得并访问链表中的每一个结点。可见，在链表结构中，head指针有着非常 重要的作用，和数组结构里的数组名标识数组类似，该指针可以起到链表的标识作用。通 常把链表中指向第一个结点的指针称为链表的头指针。 对链表中的每一个结点是通过其指针来实现访问的，可以定义一个指向结点的指针变 5

5 链表结构——单链表。 单链表中的每一个数据元素是通过一个称之为“结点”的结构来存储表示的，每个结 点占据一个内存空间，多个结点所占的存储空间是离散的，结点之间通过专门的指针相互 链接构成一个整体。从本质上看，链表就是一个结点的序列。 13.2.1 结点的结构 结点是链表中存放数据元素的基本单元，用一个结构体的形式来表示。一个结点至少 应该包含两部分：一是数据域（data），用以存放该结点需要存放的数据元素的数据值；二 是指针域（next），通常用以存放下一个结点的存储地址，由此将多个结点构成一个整体， 如图 13.2 所示。 假设一个链表结点的数据域只存放一个整数值，该结点结构可以如下定义： struct node { int data; struct node *next; }; 13.2.2 单链表的结构 链表是一个结点的序列，或者说链表是由多个结构相同的结点通过指针域相互链接构 成的一个整体。比如以上面的结点结构形成的链表如图 13.3 所示。 图 13.3 简单的链表结构 该链表由 4 个结点构成，每个结点都包含一个整型的数据域，用以存放本结点的数据 元素值，同时每个结点还都包含一个指针域，用来存放下一个结点的地址，最后一个结点 的指针域为 NULL，记作  。 在该链表中，给出了一个指针变量 head，用以存放链表中第一个结点的地址，通过该 指针，可以找到第一个结点，然后再顺着每一个结点的指针域，可以找到其下一个结点， 这样可以依次取得并访问链表中的每一个结点。可见，在链表结构中，head 指针有着非常 重要的作用，和数组结构里的数组名标识数组类似，该指针可以起到链表的标识作用。通 常把链表中指向第一个结点的指针称为链表的头指针。 对链表中的每一个结点是通过其指针来实现访问的，可以定义一个指向结点的指针变 图 13.2 结点的结构

量，依次指向链表的每一个结点，从而实现对每一个结点的访问，这样的一个指针变量常 常被称为游动指针。与数组中通过下标的变化来实现对数组中存放的批量数据元素的访问 类似，链表中是通过游动指针的变化，依次指向不同的结点，来实现对其存放的批量数据 元素的访问的。 为了更简洁地表示链表的操作过程，有时需要对前述单链表的结构做一点改动，在单 链表的第一个实际结点之前增加一个虚结点，该虚结点数据域不存放任何实际数值，其指 针域指向单链表的第一个实际结点。该结点被称为单链表的头结点。引入头结点之后，指 向头结点的指针称为头指针。如无特别说明，之后的各种操作均针对带头结点的单链表。 8正一正一a 头指针 头结点 图13.4带头结点的单链表 一个带头结点的单链表如果只包含头结点，称为空链表。 当然，不管是头指针还是游动指针，都是存放结点地址的指针变量，应该是指向结点 的指针类型的变量，如上所定义的结点，其对应链表头指针与 游动指针可以如下定义： struct node head,p; 图135带头结点的空链表 13.3单链表结点的基本操作 单链表结点的操作有很多，其中最基本的操作主要有三个：查找、插入与删除。这三 个操作是链表其他操作功能实现的基础，因此在这里作重点介绍。 13.3.1单链表结点的查找 虽然都用来存储批量数据元素，但从结构特点上看，单链表与数组还是有着很大的差 别。数组由于是用地址连续的空间存放元素，利用“数组名+下标”的方式可以实现对元 素的随机查找：单链表是用地址离散的空间存放元素的，不能直接指向每一个结点的存放 地址，只能从头指针所指结点开始逐个往后找到要访问的结点，因此也称单链表是一种“顺 序存取”的结构。 单链表的查找过程也是基于这样的存取原则，即必须要从头指针所指结点开始往后逐 个查找，才能找到要找的结点信息。因此该过程要用到前面提到的两个重要指针：头指针 与游动指针。其中头指针提供了在链表中查找的起始位置，游动指针从该起始位置开始逐 个往后“游走”，直到找到要找的结点，或者到了链表结束处停止查找。 【例13.1】写一个函数，找到指定单链表中值为k©y的结点，并返回该结点的地址。 6

6 量，依次指向链表的每一个结点，从而实现对每一个结点的访问，这样的一个指针变量常 常被称为游动指针。与数组中通过下标的变化来实现对数组中存放的批量数据元素的访问 类似，链表中是通过游动指针的变化，依次指向不同的结点，来实现对其存放的批量数据 元素的访问的。 为了更简洁地表示链表的操作过程，有时需要对前述单链表的结构做一点改动，在单 链表的第一个实际结点之前增加一个虚结点，该虚结点数据域不存放任何实际数值，其指 针域指向单链表的第一个实际结点。该结点被称为单链表的头结点。引入头结点之后，指 向头结点的指针称为头指针。如无特别说明，之后的各种操作均针对带头结点的单链表。 图 13.4 带头结点的单链表 一个带头结点的单链表如果只包含头结点，称为空链表。 当然，不管是头指针还是游动指针，都是存放结点地址的指针变量，应该是指向结点 的指针类型的变量，如上所定义的结点，其对应链表头指针与 游动指针可以如下定义： struct node *head，*p; 13.3 单链表结点的基本操作 单链表结点的操作有很多，其中最基本的操作主要有三个：查找、插入与删除。这三 个操作是链表其他操作功能实现的基础，因此在这里作重点介绍。 13.3.1 单链表结点的查找 虽然都用来存储批量数据元素，但从结构特点上看，单链表与数组还是有着很大的差 别。数组由于是用地址连续的空间存放元素，利用“数组名+下标”的方式可以实现对元 素的随机查找；单链表是用地址离散的空间存放元素的，不能直接指向每一个结点的存放 地址，只能从头指针所指结点开始逐个往后找到要访问的结点，因此也称单链表是一种“顺 序存取”的结构。 单链表的查找过程也是基于这样的存取原则，即必须要从头指针所指结点开始往后逐 个查找，才能找到要找的结点信息。因此该过程要用到前面提到的两个重要指针：头指针 与游动指针。其中头指针提供了在链表中查找的起始位置，游动指针从该起始位置开始逐 个往后“游走”，直到找到要找的结点，或者到了链表结束处停止查找。 【例 13.1】 写一个函数，找到指定单链表中值为 key 的结点，并返回该结点的地址。 图 13.5 带头结点的空链表

如果有多个值为ky的结点，返回找到的第一个结点的地址：如果没有值为key结点，返 回为NULL。 程序如下： struct node in年da+a: struct node next: struct node search(struct node head,int key) /head为单链表的头指针 struct node pi 1/p为游动指针 p=head->next; //游动指针指向第一个实际结点 while (p!=NULL) /P为NULL表示链表已经访问结束 if(p->data==key) ceturn(p); 1/找到，返回该结点的地址 else p=p->next; 11未找到，指向下一个结点继续查找 return NULL /循环正常结束，说明不存在该结点 本函数由于要返回找到结点的地址，所以返回值的类型为指针，即在指针一章所介绍 的函数是返回指针值的函数。在main函数调用时实参给定单链表的头指针以及要查找的元 素值，便可得到查找的结点的地址信息。其中的语句： p-p->next: 是链表操作中最常用的语句形式，作用是使指针发生改变，由指向当前结点，转而指向 其下一个结点。p与p>next的关系如图13.6所示。 w日正日-□-2 p->next 图13.6p与p->next所指结点 13.3.2单链表结点的插入 单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分 配空间，用完后马上释放空间。而且，与数组做元素插入、删除需要移动元素不同，单链 表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。 要在单链表中插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只 7

7 如果有多个值为 key 的结点，返回找到的第一个结点的地址；如果没有值为 key 结点，返 回为 NULL。 程序如下： struct node { int data; struct node *next; }; struct node *search(struct node *head,int key) //head 为单链表的头指针 { struct node *p; //p 为游动指针 p=head->next; //游动指针指向第一个实际结点 while(p!=NULL) //p 为 NULL 表示链表已经访问结束 { if(p->data==key) return(p); //找到，返回该结点的地址 else p=p->next; //未找到，指向下一个结点继续查找 } return NULL; //循环正常结束，说明不存在该结点 } 本函数由于要返回找到结点的地址，所以返回值的类型为指针，即在指针一章所介绍 的函数是返回指针值的函数。在 main 函数调用时实参给定单链表的头指针以及要查找的元 素值，便可得到查找的结点的地址信息。其中的语句： p=p->next; 是链表操作中最常用的语句形式，作用是使指针 p 发生改变，由指向当前结点，转而指向 其下一个结点。p 与 p->next 的关系如图 13.6 所示。 图 13.6 p 与 p->next 所指结点 13.3.2 单链表结点的插入 单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分 配空间，用完后马上释放空间。而且，与数组做元素插入、删除需要移动元素不同，单链 表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。 要在单链表中插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只

有两点：一是为要插入的元素分配空间，生成一个新结点：二是通过指针域的修改，把新 结点插入到链表中 比如对于图13.5中p所指结点之后插入一个值为10的新结点，过程如下。 (1)开辟新结点 struct node·g q=(struct node *malloc (sizeof(struct node)); q->data=10; g->next■NULL: 完成后状态如图13.7所示。 }E-2a p->next 90 图13.7开辟新结点 (2)修改指针域，将新结点插入链表： 执行上面的第一个语句后，链表的状态如图13.8所示。 ✉□一□ p 图13.8修改指针域（一） 执行上面的第二个语句后，链表的状态如图13.9所示。 8

8 有两点：一是为要插入的元素分配空间，生成一个新结点；二是通过指针域的修改，把新 结点插入到链表中。 比如对于图 13.5 中 p 所指结点之后插入一个值为 10 的新结点，过程如下。 （1）开辟新结点 struct node * q; q=(struct node *) malloc (sizeof(struct node)); q->data=10; q->next=NULL; 完成后状态如图 13.7 所示。 图 13.7 开辟新结点 （2）修改指针域，将新结点插入链表： q->next=p->next; p->next=q; 执行上面的第一个语句后，链表的状态如图 13.8 所示。 图 13.8 修改指针域（一） 执行上面的第二个语句后，链表的状态如图 13.9 所示

图13.9修改指针域（二） 【例13.2】根据上述步骤写出一个在链表的p结点之后插入一个值为ky的结点的函数。 程序如下： void insert(struct node p,int key) struct node eq: q=(struct node *malloc(sizeof(struct node)); if(!q) printf("不能分配内存空间！")： exit (0); g->data=key q->next=NULL: 1->next■p->next: p->next=q: 可见，链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。首先修 改新结点的指针域，指向下一个元素：再修改前一个元素的指针域，指向新元素。并且这 两者的顺序是不能颠倒的，请读者想一想为什么。 13.3.3单链表结点的删除 与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即 可。并且作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所 占的内存空间释放。 要刑除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的 修改操作。比如，要删除图13.10中链表值为6的结点，应该先找到其前一个结点。 图13.10找到欲删结点的前结点 删除过程的指针修改如下： q->p->next; p->next-q->nexti free(q); 9

9 图 13.9 修改指针域（二） 【例 13.2】 根据上述步骤写出一个在链表的 p 结点之后插入一个值为 key 的结点的函数。 程序如下： void insert(struct node *p,int key) { struct node *q; q= (struct node *) malloc(sizeof(struct node)); if(!q) { printf("不能分配内存空间!"); exit(0); } q->data=key; q->next=NULL; q->next=p->next; p->next=q; } 可见，链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。首先修 改新结点的指针域，指向下一个元素；再修改前一个元素的指针域，指向新元素。并且这 两者的顺序是不能颠倒的，请读者想一想为什么。 13.3.3 单链表结点的删除 与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即 可。并且作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所 占的内存空间释放。 要删除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的 修改操作。比如，要删除图 13.10 中链表值为 6 的结点，应该先找到其前一个结点。 图 13.10 找到欲删结点的前驱结点 删除过程的指针修改如下： q->p->next; p->next=q->next; free(q);

执行上面的第一个语句后，链表的状态如图13.11所示 a日一一aA p 图13.11找到欲刚结点 执行上面的第二个语句后，链表的状态如图13.12所示 m日日日6Eaa p 图13.12修政前驱结点的指针域 执行上面的第三个语句后，链表的状态如图13.13所示： a☐s 2 图13.13释放被删结点 【例13.3】写出删除带头结点的单链表中第一个值为ky的结点的函数。 分析：删除该结点是通过修改其前驱结点的指针域来实现的，因此，在删除之前首先 应找到被删结点的前驱结点。 程序如下： int del(struct node thead,int key) { struct node p,q; int flag=0; p=head; while (p->next!=NULL) if(p->next->data==key) flag=l: break: else p=p->next: 回

10 执行上面的第一个语句后，链表的状态如图 13.11 所示： 图 13.11 找到欲删结点 执行上面的第二个语句后，链表的状态如图 13.12 所示： 图 13.12 修改前驱结点的指针域 执行上面的第三个语句后，链表的状态如图 13.13 所示： 图 13.13 释放被删结点 【例 13.3】 写出删除带头结点的单链表中第一个值为 key 的结点的函数。 分析：删除该结点是通过修改其前驱结点的指针域来实现的，因此，在删除之前首先 应找到被删结点的前驱结点。 程序如下： int del(struct node *head,int key) { struct node *p,*q; int flag=0; p=head; while (p->next!=NULL) { if(p->next->data==key) { flag=1; break; } else p=p->next;