第二章 线性表.ppt

《第二章 线性表.ppt》由会员分享，可在线阅读，更多相关《第二章 线性表.ppt（96页珍藏版）》请在麦多课文档分享上搜索。

1、,第二章 线性表,线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现,本章的基本内容是：,学生成绩登记表,2.1 线性表的逻辑结构,姓 名,英语,数据结构,高数,学号,丁一,96,78,87,0101,李二,87,90,78,0102,张三,67,86,86,0103,孙红,69,81,96,0104,王冬,87,74,66,0105,职工工资登记表,2.1 线性表的逻辑结构,姓 名,岗位津贴,基本工资,奖金,职工号,丁一,600,278,200,0101,李二,300,190,100,0102,张三,300,186,100,0103,孙红,

2、500,218,200,0104,王冬,300,190,100,0105,数据元素之间的关系是什么？,线性表：简称表，是n（n0）个具有相同类型的数据元素的有限序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L（a1, a2 , , ai-1, ai , , an),2.1 线性表的逻辑结构,线性表的定义,其中，ai（1in）称为数据元素； 下角标 i 表示该元素在线性表中的位置或序号 。,2.1 线性表的逻辑结构,线性表的图形表示,线性表（a1, a2 , , ai-1, ai , , an)的图形表示如下：,2.1 线性表的逻辑结构

3、,线性表的特性,1.有限性：线性表中数据元素的个数是有穷的。,2.相同性：线性表中数据元素的类型是同一的。,3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的后继；a1 无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。,线性表的抽象数据类型定义,ADT List Data线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系 Operation InitList 前置条件：表不存在输入：无功能：表的初始化输出： 无后置条件：建一个空表,2.1 线性表的逻辑结构,DestroyList前置条件：表已存在

4、输入：无功能：销毁表输出：无后置条件：释放表所占用的存储空间 Length 前置条件：表已存在输入：无功能：求表的长度输出：表中数据元素的个数 后置条件：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Get前置条件：表已存在输入：元素的序号i功能：在表中取序号为i的数据元素输出：若i合法，返回序号为i的元素值，否则抛出异常后置条件：表不变 Locate前置条件：表已存在输入：数据元素x功能：在线性表中查找值等于x的元素输出：若查找成功，返回x在表中的序号，否则返回0后置条件：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Insert前置条件：表已存在输入：插入i；待

5、插x功能：在表的第i个位置处插入一个新元素x输出：若插入不成功，抛出异常后置条件：若插入成功，表中增加一个新元素 Delete前置条件：表已存在输入：删除位置i功能：删除表中的第i个元素输出：若删除成功，返回被删元素，否则抛出异常后置条件：若删除成功，表中减少一个元素,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Empty前置条件：表已存在输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0后置条件：表不变 ADT,进一步说明: （1）线性表的基本操作根据实际应用是而定； （2）复杂的操作可以通过基本操作的组合来实现； （3）对不同的应用，操作的接口可能不同。,2.1 线性表

6、的逻辑结构,线性表的抽象数据类型定义,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,用什么属性来描述顺序表？,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,如何实现顺序表的内存分配？,如何求得任意元素的存储地址？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,长度,2.2

7、线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：,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 线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：,2.2 线性表的顺序存储结构及实现,存储结构是数据及其逻辑结构在计算机中的表示； 存取结构是在一个数据结构上对查找操作的时间性能的一种描述。,存储结构和存取结构,“顺序表是一种随机存取的存储结构”的含

8、义为：在顺序表这种存储结构上进行的查找操作，其时间性能为O(1)。,顺序表类的声明,const int MaxSize=100; template /模板类 class SeqList public:SeqList( ) ; /构造函数SeqList(T a , int n); SeqList( ) ; /析构函数int Length( );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 线性表的顺序存储结构及实现

9、,操作接口：SeqList( ),算法描述： SeqList:SeqList( ) length=0; ,2.2 线性表的顺序存储结构及实现,顺序表的实现无参构造函数,0,操作接口：SeqList(T a , int n),顺序表的实现有参构造函数,2.2 线性表的顺序存储结构及实现,5,35,12,24,33,42,template SeqList:SeqList(T a , int n) if (nMaxSize) throw “参数非法“;for (i=0; in; i+ +) datai=ai;length=n; ,2.2 线性表的顺序存储结构及实现,顺序表的实现有参构造函数,算法描述

10、：,操作接口： void Insert(int i, T x) 插入前：(a1, , ai-1, ai, , an) 插入后：(a1, , ai-1, x , ai, , an),顺序表的实现插入,2.2 线性表的顺序存储结构及实现,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（35，12，24，42），在i=2的位置上插入33。,表满：length=MaxSize 合理的插入位置：1ilength+1（i指的是元素的序号）,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,4,35,12,24,42,a1,a2,a3,a4,0 1

11、 2 3 4,42,24,12,33,什么时候不能插入？,1. 如果表满了，则抛出上溢异常; 2. 如果元素的插入位置不合理，则抛出位置异常; 3. 将最后一个元素至第i个元素分别向后移动一个位置； 4. 将元素x填入位置i处； 5. 表长加1；,算法描述伪代码,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,template 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

12、-1=x;length+; ,算法描述C+描述,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,基本语句？,最好情况（ i=n+1）：基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=1）：基本语句执行n+1次，时间复杂度为O(n)。 平均情况（1in+1）：时间复杂度为O(n)。,时间性能分析,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,操作接口： T Delete(int i) 删除前：(a1, , ai-1,ai,ai+1,an) 删除后：(a1,ai-1,ai+1, ,an),顺序表的实现删 除,2.2 线性表的顺序存储结构及实现,ai-1和ai之间的逻辑关系发

13、生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（35, 33, 12, 24, 42），删除i=2的数据元素。,仿照顺序表的插入操作，完成： 1. 分析边界条件； 2. 分别给出伪代码和C+描述的算法； 3. 分析时间复杂度。,2.2 线性表的顺序存储结构及实现,顺序表的实现删 除,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,顺序表的实现按位查找,操作接口： T Get(int i),2.2 线性表的顺序存储结构及实现,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,n,算法描述： t

14、emplate T SeqList:Get( int i ) if (i=1 ,时间复杂度？,顺序表的实现按值查找,操作接口： int Locate(T x ),2.2 线性表的顺序存储结构及实现,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,例：在（35, 33, 12, 24, 42） 中查找值为12的元素，返回在表中的序号。,template int SeqList:Locate(T x) for (i=0; ilength; i+)if (datai=x) return i+1; return 0; ,2.2 线性表的顺序存储结构及实现,顺序表的实

15、现按值查找,算法描述：,时间复杂度？,顺序表的优缺点,顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 随机存取：可以快速地存取表中任一位置的元素。,顺序表的缺点： 插入和删除操作需要移动大量元素； 表的容量难以确定，表的容量难以扩充； 造成存储空间的碎片。,2.2 线性表的顺序存储结构及实现,单链表：线性表的链接存储结构。 存储思想：用一组任意的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链表,存储特点： 逻辑次序和物理次序不一定相同。 2.元素之间的逻辑关系用指针表示。,2.3 线性表的链接存储结构及实现,例：(a1, a2 ,a3, a4)的存

16、储示意图,单链表,a1 0200,a2 0325,a3 0300,a4,2.3 线性表的链接存储结构及实现,单链表,数据域,指针域,单链表是由若干结点构成的； 单链表的结点只有一个指针域。,data：存储数据元素 next：存储指向后继结点的地址,template struct Node T data;Node *next; ;,2.3 线性表的链接存储结构及实现,单链表,如何申请一个结点？,s=new Node ;,template struct Node T data;Node *next; ;,2.3 线性表的链接存储结构及实现,单链表,s=new Node ;,2.3 线性表的链接存储

17、结构及实现,单链表,如何引用数据元素？,data,如何引用指针域？,next,s-next;,2.3 线性表的链接存储结构及实现,单链表,重点在数据元素之间的逻辑关系的 表示，所以，将实际存储地址抽象。,什么是存储结构？,2.3 线性表的链接存储结构及实现,单链表,头指针：指向第一个结点的地址。 尾标志：终端结点的指针域为空。,2.3 线性表的链接存储结构及实现,单链表,空表和非空表不统一，缺点？ 如何将空表与非空表统一？,头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,2.3 线性表的链接存储结构及实现,单链表,非空表,template class

18、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 线性表的链接存储结构及实现,单链表的实现按位查找,操作接口： T Get(int i);,核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链

19、表“审视”一遍的方法称为扫描（或遍历）。,2.3 线性表的链接存储结构及实现,first,a1,a2,an,ai,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述伪代码,template T LinkList:Get(int i) p=first-next; j=1; while (p ,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述C+描述,单链表的实现插入,操作接口： void Insert(int i, T x);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1、x和ai之间逻辑关系的变化？,算法描述： s=new Node; s-data

20、=x; s-next=p-next; p-next=s;,注意分析边界情况表头、表尾。,单链表的实现插入,2.3 线性表的链接存储结构及实现,first,a1,an,ai,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,算法描述伪代码,1. 工作指针p初始化；累加器j清零； 2. 查找第i-1个结点并使工作指针p指向该结点；3. 若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，3.1 生成一个元素值为x的新结点s；3.2 将新结点s插入到结点p之后；,2.3 线性表

21、的链接存储结构及实现,单链表的实现插入,template void LinkList:Insert(int i, T x) p=first ; j=0; while (p ,2.3 线性表的链接存储结构及实现,算法描述C+描述,单链表的实现插入,if (!p) throw “位置“;else s=new Node; s-data=x; s-next=p-next; p-next=s; ,，,基本语句？时间复杂度？,单链表的实现删除,操作接口： T Delete(int i);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1和ai之间逻辑关系的变化？,算法描述： q=p-next; x

22、=q-data; p-next=q-next; delete q;,单链表的实现删除,2.3 线性表的链接存储结构及实现,算法描述： q=p-next; x=q-data; p-next=q-next; delete q;,注意分析边界情况表头、表尾。,表尾的特殊情况： 虽然被删结点不存在，但其前驱结点却存在。,p-next=NULL,算法描述伪代码,1.工作指针p初始化；累加器j清零；2. 查找第i-1个结点并使工作指针p指向该结点；3. 若p不存在或p不存在后继结点，则抛出位置异常；否则，3.1 暂存被删结点和被删元素值；3.2 摘链，将结点p的后继结点从链表上摘下；3.3 释放被删结点；

23、3.4 返回被删元素值；,2.3 线性表的链接存储结构及实现,单链表的实现删除,template T LinkList:Delete(int i) p=first ; j=0; while (p ,2.3 线性表的链接存储结构及实现,算法描述C+描述,单链表的实现删除,if (!p | | !p-next) throw “位置”; else q=p-next; x=q-data; p-next=q-next; delete q; return x;,单链表的实现构造函数,操作接口：LinkList(T a , int n),头插法：将待插入结点插在头结点的后面 。,算法描述： first=ne

24、w Node; first-next=NULL;,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(T a , int n),头插法：将待插入结点插在头结点的后面 。,2.3 线性表的链接存储结构及实现,算法描述： s=new Node; s-data=a0; s-next=first-next; first-next=s;,插入第一个元素结点,first,单链表的实现构造函数,操作接口：LinkList(T a , int n),头插法：将待插入结点插在头结点的后面 。,2.3 线性表的链接存储结构及实现,算法描述： s=new Node; s-data=

25、a1; s-next=first-next; first-next=s;,依次插入每一个结点,template LinkList: LinkList(T a , int n) first=new Node; first-next=NULL; for (i=0; i; s-data=ai; s-next=first-next; first-next=s;,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,算法描述：,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(T a , int n),算法描述： firs

26、t=new Node; rear=first;,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(T a , int n),算法描述： s=new Node; s-data=a0; first-next=s; rear=first;,插入第一个元素结点,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(T a , int n),算法描述： s=new Node; s-data=a1; first-next=s; rear=first;,依次

27、插入每一个结点,35,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：LinkList(T a , int n),算法描述： rear-next=NULL;,最后一个结点插入后,template LinkList: LinkList(T a , int n) first=new Node ; rear=first; for (i=0; i ; s-data=ai; rear-next=s;rear=s; rear-next=NULL; ,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,算法描述：,启示：算法设计的一般过程,

28、算法设计的一般步骤： 第一步：确定入口（已知条件）、出口（结果）； 第二步：根据一个小实例画出示意图； 第三步： 正向思维：选定一个思考问题的起点，逐步提出问题、解决问题； 逆向思维：从结论出发分析为达到这个结论应该先有什么； 正逆结合； 第四步：写出顶层较抽象算法，分析边界情况； 第五步：验证第四步的算法； 第六步：写出具体算法； 第七步：进一步验证，手工运行。,单链表的实现析构函数,析构函数将单链表中所有结点的存储空间释放。,2.3 线性表的链接存储结构及实现,操作接口：LinkList( );,first,a1,a2,an,ai,算法描述： q=p; p=p-next; Delete q

29、;,注意：保证链表未处理的部分不断开,单链表的实现析构函数,template LinkList: LinkList( ) p=first; while (p)q=p; p=p-next; delete q; ,2.3 线性表的链接存储结构及实现,算法描述：,存储分配方式比较,顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。 单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。,2.4 顺序表和单链表的比较,2.4 顺序表和单链表的比较,时间性能比较,时间性能是指实现基于某种存储

30、结构的基本操作（即算法）的时间复杂度。,按位查找： 顺序表的时间为(1)，是随机存取； 单链表的时间为(n)，是顺序存取。 插入和删除： 顺序表需移动表长一半的元素，时间为(n)； 单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为(1)。,2.4 顺序表和单链表的比较,空间性能比较,空间性能是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度：,2.4 顺序表和单链表的比较,空间性能比较,结点的存储密度： 顺序表中每个结点的存储密度为1（只存储数据元素），没有浪费空间； 单链表的每个结点的存储密度1（包括数据域和指针域），有指针的结构性开销。 整体结构：

31、顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢； 单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。,结论,若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。 当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。,2.4 顺序表和单链表的比较,总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的

32、优缺点加以综合平衡，才能最终选定比较适宜的实现方法。,2.5 线性表的其它存储方法,循环链表,first,a1,ai-1,an,ai,从单链表中某结点p出发如何找到其前驱？,将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。,2.5 线性表的其它存储方法,循环链表,first,a1,ai-1,an,ai,2.5 线性表的其它存储方法,循环链表插入,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,template void LinkList:Insert(int i, T x) p=first ;

33、 j=0; while (p!=first ,if (!p) throw “位置“;else s=new Node; s-data=x; s-next=p-next; p-next=s; ,2.5 线性表的其它存储方法,循环链表插入,与单链表的插入操作相比，差别是什么？,循环条件： p!=NULLp!=first p-next!=NULLp-next!=first,2.5 线性表的其它存储方法,循环链表,如何查找开始结点和终端结点？,2.5 线性表的其它存储方法,循环链表,开始结点：first-next 终端结点：将单链表扫描一遍，时间为O(n),开始结点：rear-next-next 终端结

34、点：rear,2.5 线性表的其它存储方法,循环链表,带尾指针的循环链表,一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。,双链表,2.5 线性表的其它存储方法,如何求结点p的直接前驱，时间性能？,为什么可以快速求得结点p的后继？,如何快速求得结点p的前驱？,双链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。,双链表,结点结构：,data：数据域，存储数据元素； prior：指针域，存储该结点的前趋结点地址； next：指针域，存储该结点的后继结点地址。,2.5 线性表的其它存储方法,template struct DulNode T data;D

35、ulNode *prior, *next; ;,2.5 线性表的其它存储方法,双链表,启示？,时空权衡空间换取时间,定义结点结构：,双链表的操作插入,s-prior=p;,s-next=p-next;,p-next-prior=s;,p-next=s;,2.5 线性表的其它存储方法,ai-1,ai,操作接口： void Insert(DulNode *p, T x);,注意指针修改的相对顺序,双链表的操作删除,(p-prior)-next=p-next;,(p-next)-prior=p-prior;,2.5 线性表的其它存储方法,操作接口： T Delete(DulNode *p);,ai-

36、1,ai,ai,结点p的指针是否需要修改？,delete p;,静态链表：用数组来表示单链表，用数组元素的下标来模拟单链表的指针。,静态链表,2.5 线性表的其它存储方法,data：存储放数据元素； next：也称游标，存储该元素的后继在数组的下标。,数组元素（结点）的构成：,数据域,指针域,例：线性表(张，王，李，赵，吴)的静态链表存储,0 1 2 3 4 5 6 7 8,2.5 线性表的其它存储方法,data next,静态链表,first,avail,first：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点； avail：空闲链表头指针，空闲链表由于只在表头操作，所以不带

37、头结点；,在线性表(张，王，李，赵，吴)中“王”之后插入“孙”,0 1 2 3 4 5 6 7 8,2.5 线性表的其它存储方法,data next,静态链表,在线性表(张，王，李，赵，吴)中删除“赵”,0 1 2 3 4 5 6 7 8,2.5 线性表的其它存储方法,data next,静态链表,在线性表(张，王，李，赵，吴)中删除“赵”,0 1 2 3 4 5 6 7 8,2.5 线性表的其它存储方法,data next,静态链表,0 1 2 3 4 5 6 7 8,data next,2.5 线性表的其它存储方法,静态链表,相对于顺序表而言，静态链表有什么优点？,优点：在执行插入和删除操

38、作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。 缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；静态链表不能随机存取。,间接寻址,间接寻址：是将数组和指针结合起来的一种方法，它将数组中存储数据元素的单元改为存储指向该元素的指针 。,2.5 线性表的其它存储方法,插入操作移动的不是元素而是指向元素的指针。当元素占用的空间较多时，比顺序表的插入操作快得多。,本章总结,线 性 表,逻辑结构,存储结构,基本概念,抽象 数据 类型 定义,线性表定义 逻辑特征,ADT定义 基本操作,顺序存储,链接存储,其他存储,顺序表

39、的特点 顺序表类定义 基本操作的实现及时间性能,单链表的特点 单链表类定义 基本操作的实现及时间性能,比 较,循环链表 双链表 静态链表 间接寻址,构造函数,构造函数的作用是初始化一个对象的成员变量。 构造函数的特点: 1. 构造函数必须与类名相同； 2. 必须声明为类的公有成员函数； 3. 不可以有返回值也不得指明返回类型； 4. 构造函数可以重载。,构造函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？,析构函数,析构函数用于在一个对象被撤消时删除其成员变量，其标志是在类的名字前面加上“”。 析构函数特点: 1.析构函数没有参数和返回值; 2.一个类只能有一

40、个析构函数; 3. 析构函数不允许重载。,析构函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？,C+通过下列语句实现异常处理机制：throw抛出一个异常，供try捕获；try检测/捕获异常；catch处理try所捕获的异常。,异常处理,模板类,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，支持不同类型的参数和返回值？,本课程选用 主教材 王红梅.数据结构（C版）.清华大学出版社本课程辅导及实验教材 王红梅.数据结构学习辅导与实验指导.清华大学出版社本课程课件 在课程教材所自带课件基础上，根据大纲需要进行修改。,关于教材及课件,