3数据描述讲解.ppt

传智播客数据结构算法教程（3）;第3章 数据描述;学习内容;3.1 引言;什么是数据结构？;3.2 线性表（Linear List）;线性表的例子;需支持的操作;抽象数据类型（ADT）;3.3 公式化(formula-based)描述;关键——元素存储位置的映射;C++类定义;3.3.2 内存分配失败处理;3.3.3 操作的实现;Find操作;Search操作;删除元素——Delete;Delete的实现;插入元素——Insert;插入操作示意;Insert函数的实现;输出函数的实现;使用线性表的例子;程序;程序（续）;运行结果;3.3.4 评价;多个表共享空间;新元素插入表i的位置k之后;插入操作（续）;3.4 链表描述;线性表的链表描述;线性表的链表描述（续）;3.4.1 类ChainNode;类Chain;3.4.2 操作;length操作——确定链表长度;查找操作;有哪些信誉好的足球投注网站操作;输出函数;删除元素的方法;删除操作的实现;Delete函数实现;插入元素的方法;插入操作的实现;插入操作的实现（续）;链表描述引出的新操作;Zero操作;Append操作;3.4.4 遍历器;遍历器的基本思想;链表遍历器实现;使用遍历器输出链表;3.4.5 循环链表;两种改进形式的结构;优化的Search函数;3.4.7 双向链表;双向链表类实现;双向链表类实现（续）;3.4.6 链表的主要比较;3.4.6 与公式化描述的比较;与公式化描述的比较（续）;提高指针使用安全性;问题一：对象销毁?垃圾内存;问题二：对象赋值问题;对象赋值问题（续）;解决办法：重载赋值运算符;重载赋值运算符（续）;问题三：拷贝构造函数;安全的拷贝构造函数;小结;3.5 间接寻址;间接寻址描述方式;元素i的定位方式;间接寻址列表类定义;间接寻址列表类定义（续）;构造函数和析构函数;Find函数的实现;删除操作;插入操作;3.6 模拟指针描述;模拟链表的数据组织定位方式;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;插入排序模拟指针版本;模拟内存的动态分配和释放;可用列表示例;SimNode类;SimSpace类;构造函数：初始化存储池;空间分配函数;空间释放函数;改进;改进后的分配、释放操作;改进后的初始化???数;新的Allocate函数;新版本是否提高了性能？;多节点的快速分配;循环链表的快速完全释放;用模拟指针方式描述列表;Destroy函数;Length函数;Find函数;Find函数（续）;Delete函数;Delete函数（续）;Insert函数;Insert函数;各种操作与链表描述的相似性;使用SimChain;3.7 几种描述方法的比较;3.8 应用;箱子排序例;箱子排序实现方法;箱子排序实现方法;链表数据域——Node类;实现!=操作的另一种方法;两种方式的结合;箱子排序实现;箱子排序实现（续）;优化：作为Chain类的成员函数;优化：作为Chain类的成员函数;优化：作为Chain类的成员函数;优化：作为Chain类的成员函数;更复杂的排序;更好的方法;按不同域进行排序;按不同域进行排序（续）;3.8.2 基数排序（radix sort）;基数排序的思想;基数排序例;基数的选定;稳定性;3.8.3 等价类*;等价关系例;等价类例;在线等价类问题;任务调度问题;任务调度例;利用等价类实现任务调度算法;利用等价类实现任务调度算法;利用等价类解任务调度例;布线问题;布线问题例;在线等价类问题解法一;在线等价类问题解法一;解法二;解法二;新版本初始化函数;新版本Union;新版本Union;新版本Find;提高体现在哪？;提高体现在哪？（续）;提高体现在哪？（续）;3.8.4 凸包问题;凸包问题;极角;极点夹角的性质;寻找极点（凸包）算法;寻找极点（凸包）算法;传智播客创始人张孝祥老师的理念就是帮助每一位学员都成功。帮助每一位学员都少走弯路。