第十章C高级程序应用.ppt

第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例 链表是具有相同数据类型的对象的有序集合。其对象的类型为结构类型，链表中的对象一般称为“结点”。每个结点在内存中的存放位置是随机的。可以是连续的，也可以是不连续的，每一个结点对象通过其链指针成员和集合中的另一个结点关联。由此，好像一个“链”一样将整个链表集合中的所有结点对象连起来，所以称为“链表”。链表的实现涉及到动态内存分配和引用自身的结构类型。 10.1 链表的基本概念 10.1.1 动态内存分配函数： 动态内存分配是指在程序运行过程中，根据需要而分配内存空间的方式。在C系统的函数库中提供了动态分配和释放内存空间的函数，详见教材P269 例10.1 在C++编译系统中则使用C++内置的操作符new和delete来动态分配和释放内存空间。当我们使用操作符new在内存中动态申请一片存储空间时，它实际上做了两件事：获得一块内存空间和返回该片内存空间的首地址。new和delete操作符是配对使用的。详见教材P271 10.1 链表的基本概念 10.1.2 用于动态内存分配的操作符 —new和delete操作符： 例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 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 单向链表中结点的插入： 图10-2-4在单向链表中插入一个结点 （b）插入后 （a）插入前 101101 101103 NULL p q s 101101 101103 NULL p q 101102 head …… head