本章学习目标 .掌握单向链表的创建和增加、删除、修改、查询等功能的实现。 .掌握双向链表的创建和增加、删除、修改、查询等功能的实现。 .理解内核链表的技术原理。 .掌握内核链表在用户程序中的应用。 链表是一种常见的数据结构,由一系列结点组成,结点可以在程序运行时通过动态存储 分配进行创建。每个结点至少包括两个域:数据域和指针域。数据域用于存储数据,指针 域用于存储指向下一个结点的地址,建立与下一个结点的联系。各个结点通过指针链接构 成一个链式结构,即链表。链表有多种类型:单向链表、双向链表和循环链表等。 5.单向链表 1 扫一扫 5.1.1 单链表结构与链表结点类型 单向链表简称单链表,其特点是链表的链接方向是单向的。本节介绍的单链表包含头 结点,因此链表中的结点分为两种:头结点和一般结点(也称数据结点)。这两种结点的类 型一样,都是某种结构体类型,但是头结点的数据域一般不使用,一般结点的数据域存放具 体的用户数据。对单链表的访问要从头结点开始顺序进行。一般结点的第一个结点称为首 结点,最后一个结点称为尾结点。头结点由头指针指向。尾结点的指针域为NULL 。 带头结点的单链表如图5. 1所示 。 单链表结点的类型定义如下 。 图5.带头结点的单链表 1 数据域的数据类型为宏定义ElemType,可根据实际需求定义ElemType的具体数据 类型,比如定义为int型。指针域使用了结构体的自引用,也就是在结构体内部包含了指向 自身类型的指针成员。使用typedef关键字将structslnode类型定义为SLNode,将struct slnode* 类型定义为PSLNode。使用typedef可以给已有类型起一个简短、易记、意义明确 的新名字。后续可以使用SLNode定义结构体变量,使用PSLNode定义指向SLNode结构 体变量的指针。 5.1.2 创建单链表 可以采用头插法或尾插法创建单链表。头插法创建单链表如图5. 2所示。尾插法将一 个新结点链接到已有链表的尾部。尾插法创建单链表如图5. 3所示。 图5.头插法创建单链表图5.尾插法创建单链表 23 本章所有源代码文件在本书配套资源的“src/第5章”目录中。 下面的ListBuildH 和ListBuildR 函数,都是根据含有n个元素的数组a创建带头结点 的单链表。 1. 头插法创建单链表的函数ListBuildH 108 2. 尾插法创建单链表的函数ListBuildR 5.1.3 插入结点 除头插法和尾插法插入结点外,更灵活的插入结点的方法是在指定位置插入结点。插 入结点的示意图如图5. 4所示。在单链表中插入结点的函数如下。 5.1.4 删除结点 删除数据结点的示意图如图5. 5所示。在单链表中删除数据结点的函数如下。 图5.插入结点的示意图图5.删除数据结点的示意图 45 109 5.1.5 读取结点 在单链表中读取指定位置数据结点内容的函数如下。 5.1.6 查找结点 查找函数根据传入的x值,在单链表中进行遍历,查找x值所在的结点,然后返回该结 点的地址。 5.1.7 打印单链表 打印单链表函数从第一个数据结点开始依次将所有数据结点中的数据域值输出。 110 5.1.8 逆转单链表 假设单链表数据结点的数据域值依次为A、B、C、D,那么将单链表逆转后,数据结点的 数据域值依次为D、C、B、A。逆转单链表的函数如下。 5.1.9 构建单向循环链表 带头结点的单向循环链表示意图如图5. 6所示。将单向循环链表构建为单循环链表的 方法:让尾结点的指针域指向头结点。从单向循环链表中的任一结点出发均可找到链表中 的其他结点。构建单向循环链表的函数如下。 图5.带头结点的单向循环链表示意图 6 111 5.1.10 销毁单链表 销毁链表就是将链表中的所有结点占据的内存空间释放掉。销毁链表的函数 ListDestroy如下。如果调用ListDestroy函数销毁由指针L指向的链表后,需要将指针L 置为NULL,否则指针L会成为野指针。 5.1.11 主函数及测试结果 在main函数中通过对上面函数的调用创建、操作单链表。main函数的定义如下。 本小节的所有代码保存在sc文件中。如图5.编译、k。 link.7所示, 运行slin 图5.编译、运行s 7 link 112 双向链 表 5.2 扫一扫 5.2.1 双链表结构与链表结点类型 双向链表简称双链表,其特点是链表的链接方向是双向的。本节介绍的双链表包含头 结点,因此链表中的结点分为两种:头结点和一般结点(也称数据结点)。这两种结点的类 型一样,都是某种结构体类型,但是头结点的数据域一般不使用,一般结点的数据域存放具 体的用户数据。对双链表的访问要从头结点开始顺序进行。一般结点的第一个结点称为首 结点,最后一个结点称为尾结点。头结点由头指针指向。双链表结点有两个指针域,分别称 为前驱指针和后继指针。前驱指针指向当前结点前面的结点,后继指针指向当前结点后面 的结点。头结点的前驱指针为NULL,尾结点的后继指针为NULL 。从双链表中的任意一 个结点开始,都可以很方便地访问它的前驱结点和后继结点。既可以从头到尾遍历,又可 以从尾到头遍历。带头结点的双链表结构示意图如图5. 8所示。 图5.带头结点的双链表结构示意图 8 双链表结点的类型定义如下。 数据域的数据类型为宏定义ElemType,可根据实际需求定义ElemType的具体数据 类型,比如定义为int型。两个指针域都使用了结构体的自引用,也就是在结构体内部包含 了指向自身类型的指针成员。使用typedef关键字将structdlnode类型定义为DLNode,将 structdlnode* 类型定义为PDLNode。后续可以使用DLNode定义结构体变量,使用 PDLNode定义指向DLNode结构体变量的指针。 5.2.2 创建双链表 可以采用头插法或尾插法创建双链表。头插法创建双链表的示意图如图5. 9所示。尾 插法将一个新结点链接到已有链表的尾部。尾插法创建双链表的示意图如图5. 10 所示。 下面的DListBuildH 和DListBuildR 函数,都是根据含有n个元素的数组a创建带头 结点的双链表。 113 图5.头插法创建双链表的示意图 9 图5.尾插法创建双链表的示意图 10 1. 头插法创建双链表的函数DListBuildH 114 2. 尾插法创建双链表的函数DListBuildR 5.2.3 插入结点 除头插法和尾插法插入结点外,更灵活的插入结点的方法是在指定位置插入结点。插 入结点的示意图如图5. 11 所示。在双链表中插入结点的函数如下。 5.2.4 删除结点 删除双链表中的结点时,遍历链表找到要删除结点的前一个结点,然后将其后面结点从 双链表中删除即可。删除数据结点的示意图如图5. 12 所示。在双链表中删除数据结点的 函数如下。 图5.插入结点的示意图图5.删除数据结点的示意图 11 12 115 5.2.5 读取结点 在双链表中读取指定位置数据结点内容的函数如下。 5.2.6 查找结点 查找函数根据传入的x值,在双链表中进行遍历,查找x值所在的结点,然后返回该结 点的地址。 5.2.7 打印双链表 打印双链表函数从第一个数据结点开始依次将所有数据结点中的数据域值输出。 116