数据结构与算法 教学课件 作者 张晓蕾 第四章.ppt

《数据结构与算法 教学课件 作者 张晓蕾 第四章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章链表链表存储结构的基本知识4.1简易的单链表类4.2循环链表和双向链表4.3标准模板双向链表类4.4模板链表容器的测试类4.54.1链表存储结构的基本知识4.1.1单链表与指针线性表链表存储结构的特点是：可用内存中一组任意的存储单元（地址可以不连续）来存储线性表的数据元素。链表由一串结点组成，分配给每个结点的存储单元一般分为两个域：数据域用来存储数据元素的信息指针域用来存储后继结点的地址这样，n个结点就被链接成一个链表，称为单链表。^hha0a1……an-1^（a）（b）图4-1线性表的单链表存储结构结点的存储结构定义为：structnode{ELEMTYPEdata;//数据域s

2、tructnode*next;//指针域};为了简化structnode表示结点引入型定义：typedefstructnodenodeL;如果要使指针p指向一个新分配的结点，则用语句p=newnodeL;如果p指针归还给系统，即释放它，则用语句delete(p);假定已声明头结点指针：nodeL*head;1．插入（1）在已知p指针所指向的结点后插入一个元素x，操作如图4-3所示。4.1.2单链表的基本运算apbxs（a）插入前apbxs（b）插入后图4-3单链表的简单插入（2）在已知p指针所指向的结点前插入一个元素x，操作如图4-4所示。head……x……^qps图4-4单链表的“前”

3、插入先设一指针q从附加头指针开始向后查找，直到p的前驱结点为止。然后在q指针所指结点之后、p指针所指结点之前，进行插入操作。heada0…apos-1xapos…^qps（3）在链表中位置为pos的元素前插入一个元素x，位置总假定从0开始，操作如图4-5所示。heada0…apos-1xapos…^qps图4-5单链表的一般插入算法思路：先设一指针p从附加头结点的下一个结点开始向后查找位置为pos的结点,同时还需用另一个q指针从附加头结点开始紧跟在p指针之后。当p指针到位时，q指向位置为pos-1的结点。（1）删除p指针所指向结点的后继结点。假设要删除线性表中p所指向结点（元素a）的后继

4、结点（元素b），操作如图4-6所示。首先使q指向p的后继结点；然后修改p结点的指针域，以删除q结点。2．删除ab…c…pq图4-6删除指针指向结点的后继结点（2）在链表中删除位置为pos的元素，位置总假定从0开始。算法思路如下：为了便于删除，先设一p指针从表头开始向后查找位置为pos的结点，同时还需使用另一个q指针从附加头结点开始紧跟在p指针之后。当p指针到位时，则令q->next=p->next，并且用delete(p)删除p结点，操作如图4-7所示。heada0…apos-1aposqp^apos+1…图4-7删除指定位置的元素如果位置pos超过表尾，q指针最终将移到尾结点，p指针将

5、取空值（NULL），这时输出信息“位置超过表末!”。3．单链表的建立建立单链表算法是按照原始数据的先后顺序一一输入，新结点在表尾插入。遍历是指依次访问单链表所有结点且仅访问一次，这里用于显示结点的数据域的值。算法思路如下：先声明一个指针p，指向已知链表head附加头结点之后的结点head->next；然后通过一个while(p!=NULL)循环使用p=p->next语句遍历单链表。4．遍历单链表4.2简易的单链表类4.2.1单链表类源代码简易单链表类的私有数据成员仅包含链表头结点head指针，成员函数由两个构造器、插入操作、删除操作和访问链表操作组成。简易单链表类miniList编写在名

6、为“minilist.h”的头文件中，其接口源代码如下：#include#defineELEMTYPEintclassminiList{private://链表头结点指针typedefstructnode{ELEMTYPEdata;//数据域structnode*next;//指针域}nodeL;nodeL*head;public://构造器1：初始化为空链表miniList();//构造器2：按给定数组初始化链表miniList(ELEMTYPEarr[],intn);//插入操作voidinsert(intpos,ELEMTYPEx);//删除操作voider

7、ase(intpos);//输出链表voidprint();};测试程序利用构造器建立不同的单链表，然后分别调用插入操作和删除操作，最后访问链表并输出结果。例4-1单链表类的测试程序。4.2.2单链表类的测试本例先用构造器创建链表对象，然后调用单链表对象的插入成员函数（test1()模块），或调用单链表对象的删除成员函数（test2()模块），最后调用单链表对象的print()成员函数输出链表。源代码见教材p.81。4.3循环链表和