C++数据结构(第2版)课件第2章 线性表.ppt

《C++数据结构(第2版)课件第2章 线性表.ppt》由会员分享，可在线阅读，更多相关《C++数据结构(第2版)课件第2章 线性表.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C+数据结构(第2版)课件第2章线性表数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据元素之间的关系是什么？数据元素之间的关系是什么？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社线性表的抽象数据类型定义线性表的抽象数据类型定义ADT ListData 线性表

2、中的数据元素具有相同类型，线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系OperationInitList 前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出：无无 后置条件后置条件：建一个空表：建一个空表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社DestroyList 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占用的存

3、储空间：释放表所占用的存储空间Length 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Get 前置条件前置条件：表已存在：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，

4、返回序号为i的元素值，否则抛出异常的元素值，否则抛出异常 后置条件后置条件：表不变：表不变Locate 前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素x 功能功能：在线性表中查找值等于：在线性表中查找值等于x的元素的元素 输出输出：若查找成功，返回：若查找成功，返回x在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Insert前置条件前置条件：表已

5、存在：表已存在输入输入：插入：插入i；待插待插x功能功能：在表的第：在表的第i个位置处插入一个新元素个位置处插入一个新元素x输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后置条件后置条件：若插入成功，表中增加一个新元素：若插入成功，表中增加一个新元素Delete前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，返回被删元素，否则抛出异常：若删除成功，返回被删元素，否则抛出异常 后置条件后置条件：若删除成功，表中减少一个元素：若删除成功，表中减少一个元素2.1 2.1 线性表的逻辑结构线性表的逻

6、辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社Empty 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变ADT进一步说明进一步说明:（1 1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不

7、同。对不同的应用，操作的接口可能不同。2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）34236743 4存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.2 线性

8、表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）34236743存储空间的起始位置存储空间的起始位置 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）34236743 4如何实现顺序表的内存分配？如何实现顺序表的内存

9、分配？顺序表顺序表一维数组一维数组数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：的顺序存储：数组的长度数组的长度Max线性表的长度线性表的长度Length数组的长度大于等于当前线性表的长度数组的长度大于等于当前线性表的长度 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社如何求得任意元素的存储地址？如何求得任意元素的存

10、储地址？0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1)+(i-1)c随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2.2 线性表的顺序存储结构及实现线性表的顺序存储

11、结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现存储结构是数据及其逻辑结构在计算机中的表示；存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对查找操作的时间性存取结构是在一个数据结构上对查找操作的时间性能的一种描述。能的一种描述。存储结构和存取结构存储结构和存取结构 “顺序表是一种顺序表是一种随机存取随机存取的的存储存储结构结构”的含义为：的含义为：在顺序

12、表这种存储结构上进行的查找操作，其时间在顺序表这种存储结构上进行的查找操作，其时间性能为性能为O(1)。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 顺顺序序表表类类的的声声明明const int MaxSize=100;template /模板类模板类class SeqList public:SeqList();/构造函数构造函数 SeqList(DataType a,int n);SeqList();/析构函数析构函数 int Length();DataType Get(int i);int Locate(DataType x);void Insert(int i

13、,DataType x);DataType Delete(int i);private:DataType dataMaxSize;int length;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社操作接口：操作接口：SeqList()()算法描述：算法描述：SeqList:SeqList()length=0;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现无参构造函数无参构造函数 datalength0数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社操

14、作接口：操作接口：SeqList(DataType a,int n)顺序表的实现顺序表的实现有参构造函数有参构造函数2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表 数组数组a351224334253512243342数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template SeqList:SeqList(DataType a,int n)if(n MaxSize)throw 参数非法参数非法;for(i=0;i=MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）2.2 线性表的顺序存

15、储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社1.如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常;2.如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常;3.将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动一个位置；4.将元素将元素x填入位置填入位置i处；处；5.表长加表长加1；算法描述算法描述伪代码伪

16、代码2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template void SeqList:Insert(int i,DataType x)if(length=MaxSize)throw 上溢上溢;if(i length+1)throw 位置位置;for(j=length;j=i;j-)-)dataj=dataj-1;datai-1=x;length+;算法描述算法描述C+描述描述2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入基本语

17、句基本语句？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社最好最好情况（情况（i=n+1）：）：基本语句执行基本语句执行0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（i=1）：）：基本语句执行基本语句执行n+1次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）：时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入+-+=11)=1(niiinp+-+=11)=1(11niinn2n=O(n)数据结构（数据结构（C+版）第版）第2

18、版版清华大学出版社清华大学出版社操作接口：操作接口：DataType Delete(int i)删除前：删除前：(a1,ai-1,ai,ai+1,an)删除后：删除后：(a1,ai-1,ai+1,an)顺序表的实现顺序表的实现删删 除除2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社例：（例：（35,33,12,24,42），），删除删除i=2

19、的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1.分析边界条件；分析边界条件；2.分别给出伪代码和分别给出伪代码和C+描述的算法；描述的算法；3.分析时间复杂度。分析时间复杂度。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现删删 除除 535a1a2a3a40 1 2 3 4422412334a5122442数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序表的实现顺序表的实现按位查找按位查找操作接口：操作接口：DataType Get(int i)2.2 线性表的顺序存储结构及实现线性表的顺序存储

20、结构及实现 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 n算法描述：算法描述：template DataType SeqList:Get(int i)if(i=1&i=length)return i-1;时间复杂度时间复杂度？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序表的实现顺序表的实现按值查找按值查找操作接口：操作接口：int Locate(DataType x)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35,33,12,24,42

21、）中查找值为中查找值为12的元素，的元素，返回在表中的序号。返回在表中的序号。iii注意序号和下标之间的关系注意序号和下标之间的关系数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template int SeqList:Locate(DataType x)for(i=0;i length;i+)if(datai=x)return i+1;return 0;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现按值查找按值查找算法描述：算法描述：时间复杂度时间复杂度？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社顺序表

22、的优缺点顺序表的优缺点 顺序表的优点：顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的无需为表示表中元素之间的逻辑关系而增加额外的存储空间；存储空间；随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：顺序表的缺点：插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素；表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充；造成存储空间的造成存储空间的碎片碎片。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表：单链表：线性

23、表的链接存储结构。线性表的链接存储结构。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的元素。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间运行时分配空间 连续连续不连续不连续零散分布零散分布数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社0200020803000325存储特点：存储特点：1.逻辑次序和物理次序逻辑次序和物理次序 不一定相同。不一定相同。2.元素之间的逻辑关系元素之间的逻辑关

24、系 用指针表示。用指针表示。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现例：例：(a1,a2,a3,a4)的存储示意图的存储示意图单链表单链表 a10200 a20325 a30300 a4 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 结点结点数据域数据域指针域指针域单链表是由若干结点构成的；单链表是由若干结点构成的；单链表的结点只有一个指针域。单链表的结点只有一个指针域。data：存储数据元素存储数

25、据元素next：存储指向后继结点的地址存储指向后继结点的地址 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template struct Node DataType data;Node*next;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表 data next单链表的结点结构：单链表的结点结构：如何申请一个结点如何申请一个结点？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社s=new Node;template struct Node Da

26、taType data;Node*next;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表 data next单链表的结点结构：单链表的结点结构：sNode数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社s=new Node;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表 data next sNode如何引用数据元素如何引用数据元素？s-data;*s.data;data如何引用指针域如何引用指针域？nexts-next;数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.3 线性表的链接存储结构

27、及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表重点在数据元素之间的逻辑关系的重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。表示，所以，将实际存储地址抽象。什么是存储结构什么是存储结构？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表

28、first=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版

29、社头结点：头结点：在在单链表的第以一个元素结点之前附设一个单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。类型相同的结点，以便空表和非空表处理统一。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表非空表非空表firsta1a2an空表空表first数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template class LinkList public:LinkList()()；LinkList(DataType a,int n);LinkList()();int Length()();DataType Get(in

30、t i);int Locate(DataType x);void Insert(int i,DataType x);DataType Delete(int i);void PrintList()();private:Node*first;单单链链表表类类的的声声明明2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现遍历操作遍历操作操作接口：操作接口：void PrintList();v核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点。从头结点（或开始结点）出发，

31、通过工作指针的反复后移而将（或开始结点）出发，通过工作指针的反复后移而将整个单链表整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1pa2panaippp数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现遍历操作遍历操作操作接口：操作接口：void PrintList();2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现template void LinkList:PrintList()p=first-next;while(p!=NU

32、LL)cout data;p=p-next;p+能否完成指针后移？能否完成指针后移？a1a2pp+p-next数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现按位查找按位查找操作接口：操作接口：DataType Get(int i);2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1a2anaipp查找失败查找失败1.工作指针工作指针p初始化初始化;累加器累加器count初始化初始化;2.重复执行下述操作，直到重复执行下述操作，直到p为空：为空：2.1 工作指针工作指针p后移后移;2.2 count+;3.返回累加器返回累加

33、器count的值；的值；pcount=1pcount=2p查找成功查找成功count=i数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template int LinkList:Length()p=first-next;count=0;while(p!=NULL)p=p-next;count+;return count;/注意注意count的初始化和返回值之间的关系的初始化和返回值之间的关系2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按位查找按位查找算法描述算法描述C+描述描述数据结构（数据结构（C+版）第版）第2版版清华大学出版

34、社清华大学出版社template int LinkList:Locate(DataType x)p=first-next;count=1;while(p!=NULL)if(p-data=x)return count;/查找成功，返回序号查找成功，返回序号 p=p-next;count+;return 0;/退出循环表明查找失败退出循环表明查找失败2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按值查找按值查找算法描述算法描述C+描述描述数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现插入插入操作接口：操作接口：v

35、oid Insert(int i,DataType x);2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现如何实现结点如何实现结点ai-1、x和和ai之间逻辑关系的变化？之间逻辑关系的变化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。单链表的实现单链表的实现插入插入2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1anaipxs算法描述：

36、算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;pxs由于单链表带头结点，由于单链表带头结点，表头、表中、表尾三种表头、表中、表尾三种情况的操作语句一致。情况的操作语句一致。数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；初始化；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点；3.若查找不成功，则插入位置不合理，抛出插入位置异常；若查找不成功，则插入位置不合理，抛出插入位置异常；否则，否则，3.1 生成一个元素值为生成一个元素值为

37、x的新结点的新结点s；3.2 将新结点将新结点s插入到结点插入到结点p之后；之后；2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现插入插入数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社 template void LinkList:Insert(int i,DataType x)p=first;count=0;/工作指针工作指针p应指向头结点应指向头结点 while(p!=NULL&count next;count+;if(p=NULL)throw 位置位置;/没有找到第没有找到第i 1个结点个结点 else s=new Node;s

38、-data=x;/申请一个结点申请一个结点s s-next=p-next;p-next=s;/结点结点s插入结点插入结点p之后之后 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现插入插入基本语句？时间复杂度？基本语句？时间复杂度？数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。算法描述：算法描述：first=new Node;first-next=NU

39、LL;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342初始化初始化first 数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342算法描述：算法描述：s=new Node;s-data=a0;s-next=first-next;first-next=s;插入第一个

40、元素结点插入第一个元素结点first35s数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342算法描述：算法描述：s=new Node;s-data=a1;s-next=first-next;first-next=s;依次插入每一个结点依次插入每一个结点12sfirst35数据结构（数据结构（C+版）第版

41、）第2版版清华大学出版社清华大学出版社template LinkList:LinkList(DataType a,int n)first=new Node;first-next=NULL;for(i=0;i data=ai;s-next=first-next;first-next=s;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链

42、表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)算法描述：算法描述：first=new Node;rear=first;数组数组a3512243342初始化初始化firstrear数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)算法描述：算法描述：s=new Nod

43、e;s-data=a0;rear-next=s;rear=s;数组数组a3512243342插入第一个元素结点插入第一个元素结点firstrear35srear数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)算法描述：算法描述：s=new Node;s-data=a1;rear-next=s;rear=s;数组数组a3512

44、243342依次插入每一个结点依次插入每一个结点first35rear12srear数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a,int n)算法描述：算法描述：rear-next=NULL;数组数组a3512243342最后一个结点插入后最后一个结点插入后first3542srear数据结构（数据结构（C+版）第版）第2版版清华大学

45、出版社清华大学出版社template LinkList:LinkList(DataType a,int n)first=new Node;/生成头结点生成头结点 r=first;/尾指针初始化尾指针初始化 for(i=0;i data=ai;r-next=s;r=s;r-next=NULL;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现删除删除操作接口：操作接口：DataType Delete(int i);2.3 线性表的链接

46、存储结构及实现线性表的链接存储结构及实现p如何实现结点如何实现结点ai-1和和ai之间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next;x=q-data;p-next=q-next;delete q;q数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现删除删除2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述：算法描述：q=p-next;x=q-data;p-next=q-next;delete q;注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。pqpq表尾的特殊情

47、况：表尾的特殊情况：虽然被删结点不存在，虽然被删结点不存在，但其前驱结点却存在。但其前驱结点却存在。p-next=NULLfirsta1ana2数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；初始化；2.查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点；3.若若p不存在或不存在或p不存在后继结点，则抛出位置异常；不存在后继结点，则抛出位置异常；否则，否则，3.1 暂存被删结点和被删元素值；暂存被删结点和被删元素值；3.2 摘链，将结点摘链，将结点p的后继结点从链表上摘下；的后继结点从

48、链表上摘下；3.3 释放被删结点；释放被删结点；3.4 返回被删元素值；返回被删元素值；2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现删除删除数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社template DataType LinkList:Delete(int i)p=first;count=0;while(p!=NULL&count next;count+;if(p=NULL|p-next=NULL)throw 位置位置;else q=p-next;x=q-data;p-next=q-next;delete q;return x

49、;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现删除删除数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现析构函数析构函数析构函数将单链表中所有结点的存储空间释放。析构函数将单链表中所有结点的存储空间释放。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现操作接口：操作接口：LinkList();firsta1a2anaiq算法描述：算法描述：q=first;first=first-next;delete q;first注意：保证链表未处理的部分不断开注意：保证链表未处理的部分不断开 数据结构（数据结构

50、（C+版）第版）第2版版清华大学出版社清华大学出版社单链表的实现单链表的实现析构函数析构函数template LinkList:LinkList()while(first!=NULL)q=first;first=first-next;delete q;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述：算法描述：数据结构（数据结构（C+版）第版）第2版版清华大学出版社清华大学出版社启示：算法设计的一般过程启示：算法设计的一般过程算法设计的一般步骤：算法设计的一般步骤：第一步：确定第一步：确定入口入口（已知条件）、（已知条件）、出口出口（结果）；（结果）；第二步：根据一个小实例