数据结构顺序表的实现.ppt

析构函数 析构函数用于在一个对象被撤消时删除其成员变量，其标志是在类的名字前面加上“~”。 析构函数特点: 1.析构函数没有参数和返回值; 2.一个类只能有一个析构函数; 3. 析构函数不允许重载。 析构函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？ C++通过下列语句实现异常处理机制： throw——抛出一个异常，供try捕获； try——检测/捕获异常； catch——处理try所捕获的异常。 异常处理 模 板 template class T //模板的标志 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，支持不同类型的参数和返回值？ 例如：模板函数 * template class DataType DataType LinkListDataType :: Delete(int i) { p = first ; count = 0; while (p != NULL count i - 1) { p = p-next; count++; } if (p == NULL || p-next == NULL) throw 位置; else { q = p-next; x = q-data; p-next = q-next; delete q; return x; } } 2.3 线性表的链接存储结构及实现 单链表的实现———删除 单链表的实现——析构函数 析构函数将单链表中所有结点的存储空间释放。 2.3 线性表的链接存储结构及实现 操作接口：~LinkList( ); first a1 a2 an ∧ ai q 算法描述： q = first; first = first-next; delete q; first 注意：保证链表未处理的部分不断开 单链表的实现——析构函数 template class DataType LinkListDataType :: ~LinkList( ) { while (first != NULL) { q = first; first = first-next; delete q; } } 2.3 线性表的链接存储结构及实现 算法描述： 循环链表 first a1 ai-1 an ∧ ai p 从单链表中某结点p出发如何找到其前驱？ 将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。 2.3 线性表的链接存储结构及实现 循环链表 空表和非空表的处理一致 附设头结点 first 空循环链表 first a1 ai-1 an ai 非空循环链表 2.3 线性表的链接存储结构及实现 first a1 ai-1 an ai 循环链表——插入 x s p x s p x s p 算法描述： s=new NodeDataType; s-data=x; s-next=p-next; p-next=s; 2.3 线性表的链接存储结构及实现 与单链表的插入操作相比，差别是什么？ 循环条件： p != NULL?p != first p-next != NULL?p-next != first 循环链表 循环链表中没有明显的尾端 如何避免死循环 2.3 线性表的链接存储结构及实现 如何查找开始结点和终端结点？ 循环链表 first a1 ai-1 an ai 开始结点：first-next 终端结点：将单链表扫描一遍，时间为O(n) 2.3 线性表的链接存储结构及实现 rear a1 ai-1 an ai 开始结点：rear-next-next 终端结点：rear 循环链表 带尾指针的循环链表 一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。 2.3 线性表的链接存储结构及实现 双链表 如何求结点p的直接前驱，时间性能？ first a1 ai-1 an ai p 为什么可以快速求得结点p的后继？ 如何快速求得结点p的前驱