《第2章 线性表》由会员分享，可在线阅读，更多相关《第2章 线性表（95页珍藏版）》请在金锄头文库上搜索。
1、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ第二章第二章第二章第二章 线性表线性表线性表线性表线性表的定义线性表的定义 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ学生成绩登记表学生成绩登记表2.1 2.1 线性表的定义线性表的定义线性表的定义线性表的定义姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二
2、8790780102张三张三6786860103孙红孙红6981960104王冬王冬8774660105数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ职工工资登记表职工工资登记表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构姓姓 名名岗位津贴岗位津贴基本工资基本工资奖金奖金职工号职工号丁一丁一6002782000101李二李二3001901000102张三张三3001861000103孙红孙红5002182000104王冬王冬3001901000105数据元素之间的关系是什么？数据元素之间的关系是什么？数据结构（数据结构（C+版）版）清华大
3、学出版社清华大学出版社WQJ线性表：线性表：简称表，是简称表，是n（n0）个具有）个具有相同类型相同类型的数据的数据元素的元素的有限序有限序列列。线性表的长度：线性表的长度：线性表中数据元素的个数。线性表中数据元素的个数。空表：空表：长度等于零的线性表，长度等于零的线性表，记为：记为：L=( )。非空表非空表记为：记为：L（a1, a2 , , ai-1, ai , , an)2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的定义线性表的定义其中，其中，ai（1in）称为数据元素；）称为数据元素；下角标下角标 i 表示该元素在线性表中的位置或序号表示该元素
4、在线性表中的位置或序号 。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJa1a3a4ana22.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的图形表示线性表的图形表示线性表线性表（a1, a2 , , ai-1, ai , , an)的图形表示如下：的图形表示如下：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJa1a3a4ana22.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的特性线性表的特性1.有限性：线性表中数据元素的个数是有穷的。有限性：线性表中数据元素的个数是有穷的。2
5、.相同性：线性表中数据元素的类型是同一的。相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素顺序性：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1, ai)，即，即ai-1是是ai的前驱，的前驱， ai是是ai-1的后继；的后继；a1 无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ线性表的抽象数据类型定义线性表的抽象数据类型定义ADT ListData 线性表中的数据元素具有相同类型，线性表中的数据元
6、素具有相同类型， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系OperationInitList 前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出： 无无 后置条件后置条件：建一个空表：建一个空表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJDestroyList 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占用的存储空间：释放表所占用的存储空间Length
7、 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJGet 前置条件前置条件：表已存在：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，返回序号为i的元素值，否则抛出异常的元素值，否
8、则抛出异常 后置条件后置条件：表不变：表不变Locate 前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素x 功能功能：在线性表中查找值等于：在线性表中查找值等于x的元素的元素 输出输出：若查找成功，返回：若查找成功，返回x在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJInsert前置条件前置条件：表已存在：表已存在输入输入：插入：插入i；待插待插x功
9、能功能：在表的第：在表的第i个位置处插入一个新元素个位置处插入一个新元素x输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后置条件后置条件：若插入成功，表中增加一个新元素：若插入成功，表中增加一个新元素Delete前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，返回被删元素，否则抛出异常：若删除成功，返回被删元素，否则抛出异常 后置条件后置条件：若删除成功，表中减少一个元素：若删除成功，表中减少一个元素2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象
10、数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJEmpty 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变ADT进一步说明进一步说明: :（1 1）线性表的基本操作根据实际应用而定；）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。对不同的应用，操作的接口可能不同。2.1 2.1
11、线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743 4存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺
12、序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743存储空间的起始位置存储空间的起始位置 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34, 23, 67, 43）34236743 4如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组数据结构（数据
13、结构（C+版）版）清华大学出版社清华大学出版社WQJ如何求得任意元素的存储地址？如何求得任意元素的存储地址？ 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+版）版）清华大学出版社清华大学出版社WQJ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1) + (i - -1)
14、l随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现存储结构是数据及其逻辑结构在计算机中的表示；存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对查找操作的时间性存取结构是在一个数据结构上对查找操作的时间性能的一种描述。能的一种描述。存储
15、结构和存取结构存储结构和存取结构 “顺序表是一种顺序表是一种随机存取随机存取的的存储存储结构结构”的含义为：的含义为：在顺序表这种存储结构上进行的查找操作，其时间在顺序表这种存储结构上进行的查找操作，其时间性能为性能为O(1)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ 顺顺序序表表类类的的声声明明const int MaxSize=100; template /模板类模板类class SeqList public: SeqList( ) ; /构造函数构造函数 SeqList(T a , int n); SeqList( ) ; /析构函数析构函数 int Lengt
16、h( ); T Get(int i); int Locate(T x ); void Insert(int i, T x); T Delete(int i); private: T dataMaxSize; int length;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ操作接口：操作接口：SeqList( )( ) 算法描述：算法描述：SeqList:SeqList( ) length=0; 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现无参构造函数无参构造函数 data
17、length0数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ操作接口：操作接口：SeqList( (T a , int n) )顺序表的实现顺序表的实现有参构造函数有参构造函数2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表 数组数组a351224334253512243342数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate SeqList:SeqList( (T a , int n) ) if ( (nMaxSize) ) throw 参数非法参数非法; for ( (i=0; i=MaxSize合理的插入位置：合
18、理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ1. 如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常;2. 如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常;3. 将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动
19、一个位置；4. 将元素将元素x填入位置填入位置i处；处；5. 表长加表长加1；算法描述算法描述伪代码伪代码2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate void SeqList:Insert( (int i, T x) ) if ( (length=MaxSize) ) throw 上溢上溢; if ( (ilength+1) ) throw 位置位置; for ( (j=length; j=i; j-)-) dataj=dataj- -1; datai- -1=x
20、; length+;算法描述算法描述C+描述描述2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入基本语句基本语句？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ最好最好情况（情况（ i=n+1）：）： 基本语句执行基本语句执行0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（ i=1）：）： 基本语句执行基本语句执行n+1次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）： 时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实
21、现顺序表的实现顺序表的实现插入插入 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn2n=O(n)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ操作接口：操作接口： T Delete(int i)删除前：删除前：( (a1, , ai- -1, ,ai, ,ai+1,an) )删除后：删除后：( (a1,ai- -1, ,ai+1, ,an) ) 顺序表的实现顺序表的实现删删 除除2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储
22、位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ例：（例：（35, 33, 12, 24, 42），），删除删除i=2的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1. 分析边界条件；分析边界条件；2. 分别给出伪代码和分别给出伪代码和C+描述的算法；描述的算法；3. 分析时间复杂度。分析时间复杂度。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现删删 除除 535a1a2a3a40 1 2 3 4422412334
23、a5122442数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ顺序表的实现顺序表的实现按位查找按位查找操作接口：操作接口： T Get(int i) 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 n算法描述：算法描述：template T SeqList:Get( int i ) if (i=1 & i=length) return i-1; 时间复杂度时间复杂度？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ顺序表的实现顺序表的实现按值查找按值查找操作接口：操
24、作接口： int Locate(T x ) 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35, 33, 12, 24, 42） 中查找值为中查找值为12的元素，的元素，返回在表中的序号。返回在表中的序号。iii注意序号和下标之间的关系注意序号和下标之间的关系数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate int SeqList:Locate( (T x) ) for ( (i=0; ilength; i+) ) if ( (datai=x) ) return i+1
25、; return 0; 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现按值查找按值查找算法描述：算法描述：时间复杂度时间复杂度？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ顺序表的优缺点顺序表的优缺点 顺序表的优点：顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的无需为表示表中元素之间的逻辑关系而增加额外的存储空间；存储空间； 随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。 顺序表的缺点：顺序表的缺点： 插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素； 表的容量难以
26、确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充； 造成存储空间的造成存储空间的碎片碎片。 2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表：单链表：线性表的链接存储结构。线性表的链接存储结构。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的元素。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间运行时分配空间 连续连续不连续
27、不连续零散分布零散分布数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ0200020803000325存储特点：存储特点：1.逻辑次序和物理次序逻辑次序和物理次序 不一定相同。不一定相同。 2.元素之间的逻辑关系元素之间的逻辑关系 用指针表示。用指针表示。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现例：例：(a1, a2 ,a3, a4)的存储示意图的存储示意图单链表单链表 a10200 a20325 a30300 a4 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0
28、200020803000325 a10200 a20325 a30300 a4 结点结点数据域数据域指针域指针域单链表是由若干结点构成的；单链表是由若干结点构成的；单链表的结点只有一个指针域。单链表的结点只有一个指针域。data：存储数据元素存储数据元素next：存储指向后继结点的地址存储指向后继结点的地址 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate struct Node T data; Node *next; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链
29、表单链表 data next单链表的结点结构：单链表的结点结构：如何申请一个结点如何申请一个结点？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJs=new Node ;template struct Node T data; Node *next; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表 data next单链表的结点结构：单链表的结点结构： sNode数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJs=new Node ;2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表 data next sNo
30、de如何引用数据元素如何引用数据元素？s-data ;*s.data ;data如何引用指针域如何引用指针域？nexts-next;数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表重点在数据元素之间的逻辑关系的重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。表示，所以，将实际存储地址抽象。什么是存储结构什么是存储结构？数据结构（数据结构（C+版）版）
31、清华大学出版社清华大学出版社WQJ2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志：尾标志：终端结点的指针域为空。终端结点的指针域为空。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表0200020803000325 a10200 a20325 a30300 a4 first
32、a1a2an非空表非空表first=NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ头结点：头结点：在在单链表的第以一个元素结点之前附设一个单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。类型相同的结点，以便空表和非空表处理统一。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表单链表非空表非空表firsta1a2an空表空表first数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate
33、 class LinkList public: LinkList( )( )； LinkList( (T a , int n) ); LinkList( )( ); int Length( )( ); T Get( (int i) ); int Locate( (T x) ); void Insert( (int i, T x) ); T Delete( (int i) ); void PrintList( )( ); private: Node *first; ;单单链链表表类类的的声声明明2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数据结构（数据结构（C+版）版）清华大学出
34、版社清华大学出版社WQJ单链表的实现单链表的实现按位查找按位查找操作接口：操作接口： T Get(int i);v核心操作（关键操作）：核心操作（关键操作）：工作指针后移工作指针后移。从头结点。从头结点（或开始结点）出发，通过工作指针的反复后移而将（或开始结点）出发，通过工作指针的反复后移而将整个单链表整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1pa2panaipp查找成功查找成功p查找失败查找失败数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ1. 工作指针工作指
35、针p初始化初始化; 累加器累加器j初始化初始化;2.1 工作指针工作指针p后移后移;2.2 累加器累加器j加加1;2. 循环直到循环直到p为空或为空或p指向第指向第i个结点个结点3. 若若p为为空空，则则第第i个个元元素素不不存存在在，抛抛出出查查找找位位置置异常；否则查找成功，返回结点异常；否则查找成功，返回结点p的数据元素；的数据元素；2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按位查找按位查找算法描述算法描述伪代码伪代码数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate T LinkList:Get(int i) p
36、=first-next; j=1; while (p & jnext; j+; if (!p) throw 位置位置; else return p-data; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现按位查找按位查找算法描述算法描述C+描述描述p+ +能否完成指针后移？能否完成指针后移？a1a2ppp数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现插入插入操作接口：操作接口： void Insert(int i, T x); 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现如何实现结点如何实现结点
37、ai-1、x和和ai之间逻辑关系的变化？之间逻辑关系的变化？pxsfirsta1ai-1anai算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 单链表的实现单链表的实现插入插入2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现firsta1anaipxs算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;pxs由于单链表带头结点，由于单链表带头
38、结点，表头、表中、表尾三种表头、表中、表尾三种情况的操作语句一致。情况的操作语句一致。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ算法描述算法描述伪代码伪代码 1. 工作指针工作指针p初始化；累加器初始化；累加器j清零；清零； 2. 查找第查找第i- -1个结点并使工作指针个结点并使工作指针p指向该结点；指向该结点； 3. 若若查查找找不不成成功功，说说明明插插入入位位置置不不合合理理，抛抛出出插插入入位置异常；否则，位置异常；否则， 3.1 生成一个元素值为生成一个元素值为x的新结点的新结点s； 3.2 将新结点将新结点s插入到结点插入到结点p之后；之后；2.3 线性
39、表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现插入插入数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ template void LinkList:Insert( (int i, T x) ) p=first ; j=0; while ( (p & j-next; j+; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述算法描述C+描述描述单链表的实现单链表的实现插入插入 if (!p) throw 位置位置; else s=new Node; s-data=x; s-next=p-next; p-next=s; ，基本语句？时
40、间复杂度？基本语句？时间复杂度？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现删除删除操作接口：操作接口： T Delete(int i); 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现p如何实现结点如何实现结点ai-1和和ai之间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;q数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现删除删除2.3 线性表的链接存储结构及实
41、现线性表的链接存储结构及实现算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;注意分析注意分析边界边界情况情况表头、表尾。表头、表尾。 pqpq表尾的特殊情况：表尾的特殊情况：虽然被删结点不存在，虽然被删结点不存在，但其前驱结点却存在。但其前驱结点却存在。 p-next=NULLfirsta1ana2数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零； 2. 查找第查找第i-1个结点并使工作指针个结点并使工作指针p指向该结点；指向该
42、结点； 3. 若若p不存在或不存在或p不存在后继结点，则抛出位置异常；不存在后继结点，则抛出位置异常； 否则，否则， 3.1 暂存被删结点和被删元素值；暂存被删结点和被删元素值； 3.2 摘链，将结点摘链，将结点p的后继结点从链表上摘下；的后继结点从链表上摘下； 3.3 释放被删结点；释放被删结点； 3.4 返回被删元素值；返回被删元素值； 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现删除删除数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate T LinkList:Delete(int i) p=first ; j=0;
43、while (p & jnext; j+; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述算法描述C+描述描述单链表的实现单链表的实现删除删除 if (!p | | !p-next) throw “位置位置”; else q=p-next; x=q-data; p-next=q-next; delete q; return x; 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。算
44、法描述：算法描述：first=new Node; first-next=NULL; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342初始化初始化first 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342算法描述：算法描述：s=new Node; s-data=a0;s-
45、next=first-next;first-next=s; 插入第一个元素结点插入第一个元素结点first35s数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现数组数组a3512243342算法描述：算法描述：s=new Node; s-data=a1;s-next=first-next;first-next=s; 依次插入每一个结点依次插入
46、每一个结点12sfirst35数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate LinkList: LinkList(T a , int n) first=new Node; first-next=NULL; for (i=0; in; i+) s=new Node; s-data=ai; s-next=first-next; first-next=s; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ尾插法：尾插法：将待插
47、入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)算法描述：算法描述：first=new Node; rear=first;数组数组a3512243342初始化初始化firstrear数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造
48、函数操作接口：操作接口：LinkList(T a , int n)算法描述：算法描述：s=new Node; s-data=a0;rear-next=s;rear=s;数组数组a3512243342插入第一个元素结点插入第一个元素结点firstrear35srear数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)算法描述：算法描述：s=
49、new Node; s-data=a1;rear-next=s;rear=s;数组数组a3512243342依次插入每一个结点依次插入每一个结点firstrear35rear12srear数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(T a , int n)算法描述：算法描述：rear-next=NULL;数组数组a3512243342最后一个结点插入后最后
50、一个结点插入后firstrear35rear42srear数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate LinkList: LinkList( (T a , int n) ) first=new Node ; rear=first; for ( (i=0; in; i+) ) s=new Node ; s-data=ai; rear-next=s; rear=s; rear-next=NULL; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：数据结构（数据结构（C+版）版）清华大学出
51、版社清华大学出版社WQJ启示：算法设计的一般过程启示：算法设计的一般过程算法设计的一般步骤：算法设计的一般步骤：第一步：确定第一步：确定入口入口（已知条件）、（已知条件）、出口出口（结果）；（结果）；第二步：根据一个小实例画出第二步：根据一个小实例画出示意图示意图；第第三三步步： 正正向向思思维维：选选定定一一个个思思考考问问题题的的起起点点，逐逐步步提提出出问问题题、解解决决问问题题； 逆逆向向思思维维：从从结结论论出出发发分分析为达到这个结论应该先有什么；析为达到这个结论应该先有什么； 正逆结合正逆结合；第四步：写出第四步：写出顶层顶层较抽象算法，分析较抽象算法，分析边界边界情况；情况；第
52、五步：第五步：验证验证第四步的算法；第四步的算法；第六步：写出第六步：写出具体具体算法；算法；第七步：第七步：进一步进一步验证，手工运行。验证，手工运行。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现析构函数析构函数析构函数将单链表中所有结点的存储空间释放。析构函数将单链表中所有结点的存储空间释放。 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现操作接口：操作接口：LinkList( );firsta1a2anaipq算法描述：算法描述：q=p; p=p-next;Delete q;p注意：保证链表未处理的部分不断开注意：保证链表未处理
53、的部分不断开 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ单链表的实现单链表的实现析构函数析构函数template LinkList: LinkList( )( ) p=first; while ( (p) ) q=p; p=p-next; delete q; 2.3 线性表的链接存储结构及实现线性表的链接存储结构及实现算法描述：算法描述：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ存储分配方式比较存储分配方式比较顺序表采用顺序存储结构，即用一段地址顺序表采用顺序存储结构，即用一段地址连续连续的的存储单元存储单元依次依次存储线性表的数据元素，数据元素
54、之存储线性表的数据元素，数据元素之间的逻辑关系通过间的逻辑关系通过存储位置存储位置来实现。来实现。单链表采用链接存储结构，即用一组单链表采用链接存储结构，即用一组任意任意的存储的存储单元存放线性表的元素。用单元存放线性表的元素。用指针指针来反映数据元素之来反映数据元素之间的逻辑关系。间的逻辑关系。2.4 顺序表和单链表的比较顺序表和单链表的比较数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.4 顺序表和单链表的比较顺序表和单链表的比较时间性能比较时间性能比较 时间性能时间性能是指实现基于某种存储结构的基本操作（即是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。算
55、法）的时间复杂度。 按位查找：按位查找：顺序表的时间为顺序表的时间为(1)，是随机存取；，是随机存取；单链表的时间为单链表的时间为(n)，是顺序存取。，是顺序存取。插入和删除：插入和删除：顺序表需移动表长一半的元素，时间为顺序表需移动表长一半的元素，时间为(n)；单链表不需要移动元素，在给出某个合适位置的指单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为针后，插入和删除操作所需的时间仅为(1)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.4 顺序表和单链表的比较顺序表和单链表的比较空间性能比较空间性能比较 空间性能空间性能是指某种存储结构
56、所占用的存储空间的大小。是指某种存储结构所占用的存储空间的大小。 定义结点的存储密度：定义结点的存储密度： 数据域占用的存储量数据域占用的存储量整个结点占用的存储量整个结点占用的存储量存储密度存储密度数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.4 顺序表和单链表的比较顺序表和单链表的比较空间性能比较空间性能比较 结点的存储密度：结点的存储密度：顺序表中每个结点的存储密度为顺序表中每个结点的存储密度为1（只存储数据元素）（只存储数据元素），没有浪费空间；，没有浪费空间；单链表的每个结点的存储密度单链表的每个结点的存储密度1（包括数据域和指（包括数据域和指针域），有指针的
57、结构性开销。针域），有指针的结构性开销。整体结构：整体结构：顺序表需要预分配存储空间，如果预分配得过大，顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。配，单链表中的元素个数就没有限制。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ结论结论若线性表需若线性表需频繁查找频繁查找却很少进行插入和删除操作，却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺或其操作和
58、元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需序表作为存储结构；若线性表需频繁插入和删除频繁插入和删除时，时，则宜采用单链表做存储结构。则宜采用单链表做存储结构。当线性表中元素当线性表中元素个数变化个数变化较大或者未知时，最好使较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。度，使用顺序表的空间效率会更高。2.4 顺序表和单链表的比较顺序表和单链表的比较总之总之，线性表的顺序实现和链表实现各有其优缺点，不，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据
59、实际问题的具体需能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。比较适宜的实现方法。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法循环链表循环链表循环链表循环链表firsta1ai-1anaip从单链表中某结点从单链表中某结点p出发如何找到其前驱？出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针将单链表的首尾相接，将终端结点的指针域由空指针改为指向
60、头结点，构成改为指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法循环链表循环链表循环链表循环链表空表和非空表的处理一致空表和非空表的处理一致附设头结点附设头结点first空循环链表空循环链表firsta1ai-1anai非空循环链表非空循环链表数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJfirsta1ai-1anai2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性
61、表的其它存储方法循环链表循环链表循环链表循环链表插入插入插入插入xspxspxsp算法描述：算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ循环条件：循环条件：p-next!=NULLp-next!=first2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法循环链表循环链表循环链表循环链表循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQ
62、J如何查找开始结点和终端结点？如何查找开始结点和终端结点？2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法循环链表循环链表循环链表循环链表firsta1ai-1anai开始结点：开始结点：开始结点：开始结点：first-next first-next 终端结点：将单链表扫描一遍，时间为终端结点：将单链表扫描一遍，时间为终端结点：将单链表扫描一遍，时间为终端结点：将单链表扫描一遍，时间为O O( (n n) )数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJreara1ai-1anai开始结点：开始结点：开始结点：开始结点：rea
63、r-next-nextrear-next-next终端结点：终端结点：终端结点：终端结点：rearrear2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法循环链表循环链表循环链表循环链表带尾指针的循环链表带尾指针的循环链表一个存储结构设计得是否合理，取决于基于该存储结一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。构的运算是否方便，时间性能是否提高。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ双链表双链表双链表双链表2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方
64、法线性表的其它存储方法如何求结点如何求结点p的直接前驱，时间性能？的直接前驱，时间性能？firsta1ai-1anaip为什么可以快速求得结点为什么可以快速求得结点p的后继？的后继？如何快速求得结点如何快速求得结点p的前驱？的前驱？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ双链表：双链表：在在单链表的每个结点中再设置一个指向其前单链表的每个结点中再设置一个指向其前驱结点的指针域驱结点的指针域。双链表双链表双链表双链表结点结构：结点结构：priordatanextdata：数据域，存储数据元素；数据域，存储数据元素；prior：指针域，存储该结点的前趋结点地址；指针域，存
65、储该结点的前趋结点地址；next：指针域，存储该结点的后继结点地址。指针域，存储该结点的后继结点地址。2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJtemplate struct DulNode T data; DulNode *prior, *next; 2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法双链表双链表双链表双链表启示？启示？时空权衡时空权衡空间换取时间空间换取时间priordatanext定义结点结构：定义结点结构：
66、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ双链表的操作双链表的操作插入插入s-prior=p; s-next=p-next;p-next-prior=s;p-next=s; 2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法ai-1ai操作接口：操作接口： void Insert(DulNode *p, T x); pxs注意指针修改的注意指针修改的相对相对顺序顺序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ双链表的操作双链表的操作删除删除( (p-prior) )-next=p-next; ( (p-
67、next) )-prior=p-prior; 2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法操作接口：操作接口： T Delete(DulNode *p); ai-1aipai结点结点p的指针是否需要修改？的指针是否需要修改？delete p; 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ静态链表：静态链表：用用数组来表示单链表，用数组元素的下标数组来表示单链表，用数组元素的下标来模拟单链表的指针。来模拟单链表的指针。静态链表静态链表2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存
68、储方法data：存储放数据元素；：存储放数据元素；next：也称游标，存储该元素的后继在数组的下标。：也称游标，存储该元素的后继在数组的下标。数组元素（结点）的构成：数组元素（结点）的构成： data next数据域数据域指针域指针域数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ例：线性表例：线性表(张，王，李，赵，吴张，王，李，赵，吴)的静态链表存储的静态链表存储张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 12.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法data next静态链表静态链表fi
69、rstavailfirst：静态链表头指针，为了方：静态链表头指针，为了方便插入和删除操作，通常静态链便插入和删除操作，通常静态链表带头结点；表带头结点；avail：空闲链表头指针，空闲链：空闲链表头指针，空闲链表由于只在表头操作，所以不带表由于只在表头操作，所以不带头结点；头结点；数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ在线性表在线性表(张，王，李，赵，吴张，王，李，赵，吴)中中“王王”之后插入之后插入“孙孙”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 12.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性
70、表的其它存储方法data next静态链表静态链表张张 2王王 6李李 4赵赵 5吴吴 -1012345678孙孙 3 8 -1 1data next王之后王之后插入孙插入孙数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ在线性表在线性表(张，王，李，赵，吴张，王，李，赵，吴)中删除中删除“赵赵”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 12.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法data next静态链表静态链表张张 2王王 3李李 5赵赵 5吴吴 -1012345678 7 8 -1
71、1data next删除赵删除赵摘链摘链数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ在线性表在线性表(张，王，李，赵，吴张，王，李，赵，吴)中删除中删除“赵赵”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 12.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法data next静态链表静态链表张张 2王王 3李李 5 6吴吴 -1012345678 7 8 -1 1data next删除赵删除赵归还空间归还空间数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ2.5 2.5 线性表的
72、其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法静态链表静态链表相对于顺序表而言，静态链表有什么优点？相对于顺序表而言，静态链表有什么优点？ 优点：在执行插入和删除操作时，只需修改游标，优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。入和删除操作需要移动大量元素的缺点。缺点：没有解决连续存储分配带来的表长难以确定缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；的问题；静态链表还需要维护一个空闲链；静态链静态链表不能随机
73、存取。表不能随机存取。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ间接寻址间接寻址间间接接寻寻址址：是是将将数数组组和和指指针针结结合合起起来来的的一一种种方方法法，它它将将数数组组中中存存储储数数据据元元素素的的单单元元改改为为存存储储指指向向该该元元素的指针素的指针 。2.5 2.5 线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法线性表的其它存储方法0 1 2 i-1 n-1 Max-1 空闲空闲 长度长度 a1 ai an a2插入操作移动的不是元素而是指向元素的指针。当元插入操作移动的不是元素而是指向元素的指针。当元素占用的空间较多时，比顺序表的插
74、入操作快得多。素占用的空间较多时，比顺序表的插入操作快得多。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ练习题练习题用单链表实现线性表的就地逆置算法p=first;q=p-next;while (q!=NULL)nf=q-next;if (p=first) q-next=NULL;else q-next=p;p=q;q=nf;if (p!=first) first-next=p;firsta1a2an空表空表first数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ本章总结本章总结线线线线 性性性性 表表表表逻辑结构逻辑结构逻辑结构逻辑结构存储结构存储
75、结构存储结构存储结构基基本本概概念念抽象抽象数据数据类型类型定义定义线性表定义线性表定义逻辑特征逻辑特征ADT定义定义基本操作基本操作顺顺序序存存储储链链接接存存储储其其他他存存储储顺序表的特点顺序表的特点顺序表类定义顺序表类定义基基本本操操作作的的实实现及时间性能现及时间性能单链表的特点单链表的特点单链表类定义单链表类定义基基本本操操作作的的实实现及时间性能现及时间性能 比比 较较循环链表循环链表双链表双链表静态链表静态链表间接寻址间接寻址数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ构造函数构造函数构造函数的作用是初始化一个对象的成员变量。构造函数的作用是初始化一个对象
76、的成员变量。构造函数的特点构造函数的特点:1. 构造函数必须与类名相同；构造函数必须与类名相同；2. 必须声明为类的公有成员函数；必须声明为类的公有成员函数；3. 不可以有返回值也不得指明返回类型；不可以有返回值也不得指明返回类型；4. 构造函数可以重载。构造函数可以重载。构造函数的作用构造函数的作用是什么是什么（What）？）？什么时候什么时候（When）调用？）调用？由由谁谁（Who）来调用？）来调用？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ析构函数析构函数析构函数用于在一个对象被析构函数用于在一个对象被撤消撤消时删除其成时删除其成员变量，其标志是在类的名字前面加
77、上员变量，其标志是在类的名字前面加上“”。析构函数特点析构函数特点:1.析构函数没有参数和返回值析构函数没有参数和返回值;2.一个类只能有一个析构函数一个类只能有一个析构函数;3. 析构函数不允许重载析构函数不允许重载。 析构函数的作用析构函数的作用是什么是什么（What）？）？什么时候什么时候（When）调用？）调用？由由谁谁（Who）来调用？）来调用？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJC+通过下列语句实现异常处理机制：通过下列语句实现异常处理机制： throw抛出一个异常，供抛出一个异常，供try捕获；捕获； try检测检测/捕获异常；捕获异常； catch处理处理try所捕获的异常。所捕获的异常。异常处理异常处理数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社WQJ模板类模板类template /模板的标志模板的标志T Max(T x, T y) return x=y? x: y; int i=Max(1, 2); double x=Max(1.2, 2.5); 函数函数Max 要返回两个不同类型参数中的最大者，要返回两个不同类型参数中的最大者，如何定义一个具有通用功能的函数如何定义一个具有通用功能的函数Max，支持不，支持不同类型的参数和返回值？同类型的参数和返回值？
