《程序设计基础》课程教学资源（教材讲义）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<stdio.h> #include<stdlib.h> 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<stdio.h> #include<stdlib.h> 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<stdio.h> #include<stdlib.h> 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<stdio.h> #include<stdlib.h> 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<stdio.h> #include<stdlib.h> 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 结点的结构