第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例

10.1 链表的基本概念 链表是具有相同数据类型的对象的有序集合。其对象的类型为结构类型，链表中的对象一般称为“结点”。每个结点在内存中的存放位置是随机的。可以是连续的，也可以是不连续的，每一个结点对象通过其链指针成员和集合中的另一个结点关联。由此，好像一个“链”一样将整个链表集合中的所有结点对象连起来，所以称为“链表”。链表的实现涉及到动态内存分配和引用自身的结构类型。 10.1.1 动态内存分配函数： 动态内存分配是指在程序运行过程中，根据需要而分配内存空间的方式。在C系统的函数库中提供了动态分配和释放内存空间的函数，详见教材P269 例10.1

10.1 链表的基本概念 10.1.2 用于动态内存分配的操作符 —new和delete操作符： 在C++编译系统中则使用C++内置的操作符new和delete来动态分配和释放内存空间。当我们使用操作符new在内存中动态申请一片存储空间时，它实际上做了两件事：获得一块内存空间和返回该片内存空间的首地址。new和delete操作符是配对使用的。详见教材P271 例10.2

10.1 链表的基本概念 10.1.3 引用自身的结构类型： 引用自身的结构类型 是一种特殊的结构类型，即该结构类型的成员中包含有指向该结构类型自身的指针成员。 struct TeacherNode { Datatype data; // 数据成员 TeacherNode *next; // 指向结构类型自身的指针 }; 该结构中定义了两个成员，第一个是数据成员data；其类型为Datatype（Datatype可以是C支持的任何数据类型），用来存放一个TeacherNode结构类型的对象的基本信息；第二个是指针成员next，这是指向TeacherNode自身的指针。

10.1 链表的基本概念 10.1.3 引用自身的结构类型（续）： 引用自身的结构类型 是一种特殊的结构类型，即该结构类型的成员中包含有指向该结构类型自身的指针成员。 struct TeacherNode { Datatype data; // 数据成员 TeacherNode *next; // 指向结构类型自身的指针 }; 由于每一个该类型的结构变量都可以通过其next成员找到另一个该类型的结构变量，因此，使用引用自身的结构类型，可以将存放在内存中随机位置的结构变量从逻辑上链接起来，在逻辑上形成一个有序的集合——链表。通常把next成员称为链指针。

10.2 单向链表 单向链表 是由称为结点的对象构成的。每个结点，除需要存储数据值外还需要存储一个直接指向相应后继结点存放位置的指针信息(即后继结点的内存存储地址)。所以，结点是含有数据成员和链指针成员的结构类型。链指针用来指向后继结点(即存放指向结点的地址)。 10.2.1 单向链表的建立： 由于访问单向链表中的任一结点都必须是从链表的头开始，所以，我们设置一个专门的指针变量用来指向链表的开头，这个专门的指针变量称为表头指针（head）。 实际中，为了操作方便，链表一般都会设一个头结点，将表头指针head指向这个头结点。头结点的的数据域是没有用处的。头结点的后继所指向的结点才是链表的第一个结点。 图10-2-1 单向链表结构 头结点 head 空表 NULL 指针 数据 例10.3

10.2 单向链表 10.2.2 单向链表中结点的遍历： void browseTeacherList(TeacherList teacherList) { ……  TeacherNode *p = teacherList->next; // 指向当前教师结点的指针 int n = 0; // 教师人数 while(p != NULL) // 循环后移指针，至p指向最后一个教师为止 { writelnTeacher(p->data); // 输出当前教师信息 p = p->next; // 指针后移 n++; } ……

10.2 单向链表 10.2.3 单向链表中结点的插入： TeacherNode *s = NULL; 图10-2-4在单向链表中插入一个结点 （b）插入后 （a）插入前 101101 101103 NULL p q s 101102 head …… TeacherNode *s = NULL; s = new TeacherNode; s->data = xxxx; s->next = q; p->next = s;

10.2 单向链表 10.2.4 单向链表中结点的删除： 图10-2-5 在单向链表中删除一个结点 （a）删除节点前 xxx pre NULL （b）删除节点后 p head …… pre->next = p->next; // 或pre->next=pre->next->next; delete p; // 释放当前结点指针p所指向的空间

10.2 单向链表 10.2.5 由单向链表构成循环链表： 图10-2-6 单向循环链表 data rear 如果将单向链表的最后一个结点的链指针指向单向链表的第一个结点，就构成了一个单向循环链表，如图10-2-6所示 从循环链表中任意给定结点出发，都可以访问到循环链表中的其它结点。 在一个循环链表中，通常要定义一个指向尾结点的指针rear（表尾指针）。指针rear的作用类似于单链表中的表头指针head。

10.3 双向链表 双向链表是指链表中的每个结点共有两个指针域：一个是向后进行链接的指针，另一个是向前进行链接的指针。这样，一个结点至少有三个域，即数据域（data）、前指针域（prior）和后指针域（next）。图10-3-1表示了双向链表的结构。 图10-3-1 双向链表 head data NULL end 使用双向链表的主要优点是： ① 能从两个方向对链表进行操作。不仅简化了排序，而且使用户能从两个方向检索链表。 ② 由于可以从正向或反向读链表。当其中一个链被破坏时，可以使用另一个链重建链表。

10.3 双向链表（续） 双向链表的结点类型： struct TeacherNode { TeacherInfo data; // 数据域 图10-3-1 双向链表 head data NULL end 双向链表的结点类型： struct TeacherNode { TeacherInfo data; // 数据域 TeacherNode *next; // 后继指针 TeacherNode *prior; // 前驱指针 };

10.3 双向链表（续） 在双向链表中，将new指向的新结点插入到双向链表遍历指针p指向结点之后。操作过程如图10-3-2所示 图10-3-2 新结点插入到指定结点前后的示意图 （a）插入结点前 head data NULL end （b）插入结点后 new p new->next = p->next; new->prior = p p->next->prior = new; p->next = new

10.3 双向链表（续） 在双向链表中，删除指针p指向的结点，其操作过程如图10-3-3所示。 p->next->prior = p->prior; p->prior->next = p->next; delete p

10.4 应用举例 例10.5 例10.4