数据结构与算法基础(第三版)第九章数据结构总结ppt课件

数据结构与算法基础课程回顾与总结,第一章绪论,A数据结构研究对象信息数据数据元素数据项数据结构数据对象数据类型,B数据结构逻辑结构存储结构（物理结构）数据结构分类,C数据结构发展概况,D抽象数据型(ADT)数据型、数据结构与抽象数据型抽象数据型的规格描述（语法、语义）抽象数据型的实现抽象数据型的优点多层次抽象技术,E算法什么叫算法？算法的特征“好”的算法的评价标准对算法的正确性的要求算法的描述类语言F算法分析算法的时间特性时间复杂度T(n)空间复杂度S(n),第二章线性表,A线性表的概念什么叫线性表抽象数据型线性表,B线性表的实现静态数据结构动态数据结构顺序存储（数组实现）链式存储（指针）游标（静态链表）,C线性链表表头结点单向链表双向链表单向循环链表双向循环链表,D限定性数据结构：栈&队列,E栈栈的概念ADT栈栈的存储结构栈的应用:栈与递归迷宫求解表达式转换与求值,F队列队列的概念ADT队列队列的存储结构循环队列,G线性表的应用：多项式的表示多项式相加运算,H串串的基本概念ADT串串的存储结构存储密度,I数组数组的概念ADT数组数组的存储结构数组的压缩存储：特殊矩阵、对角或带状矩阵、稀疏矩阵,J广义表基本概念广义表的存储结构,第二章树与二元树,A树的基本术语树子树结点分支度路叶子非终结（端）结点终结（端）结点儿子父亲兄弟堂兄弟祖先子孙结点；层高度（深度）结点的顺序层序有序树无序树森林,B二元树二元树的定义，ADT二元树，满二元树，完全二元树二元树的遍历：先序遍历、中序遍历和后序遍历，层序遍历二元树遍历的非递归算法（先序、中序和后序）二元树的性质：（15）二元树的存储结构：顺序存储、链式存储（二叉链表）线索二元树：基本概念，先序、中序与后序线索求线索二元树的（先序、中序、后序）前驱与后继结点线索二元树的遍历线索二元树中插入、删除结点的讨论,D树ADT树树的存储结构：双亲表示法，孩子表示法（邻接表），树的左右链表示树与二元树的转换，森林与二元树的转换树的遍历：先序、中序和后序遍历树,E树的应用用树表示集合、判定树、哈夫曼树及其应用、最优编码,C二元树的相似与等价，二元树的复制算法,第四章图以及与图有关的算法,A图的基本概念图的定义ADT图有向图无向图弧边顶点邻接点相邻依附环路权子图带标号的图（网）路径简单路径连通图强连通图连通分量强连通分量完全图稀疏图稠密图度入度出度生成树,B图的表示（存储结构）：邻接矩阵邻接表,C图的遍历（搜索）算法：先深搜索（DFS）先广搜索（BFS）,D图与树的关系生成树先深生成森林先广生成森林树边与回退边开放树最小生成树及其算法（MST性质、Prim、Kruskal算法）,E无向图的双连通性关结点双连通图双连通分量,F有向图的搜索生成树生成森林如何区别树边、向前边、回退边和横边,G强连通性：强连通分量，归约图，图的中心点的概念及求解方法,H拓扑分类有向无环图及其应用拓扑分类拓扑分类算法,I关键路径事件活动AOE网AOV网路径长度关键活动关键路径AOE网：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？关键路径算法中的关键变量：事件Vj的最早可能发生时间VE(j)；活动ai的最早可能开始时间E(k)；事件Vk的最迟发生时间VL(k)；活动ai的最迟允许开始时间L(i)；时间余量L(i)-E(i)。,J最短路径问题单源最短路径：Dijkstra算法任意顶点间的最短路径：Floyd算法、Warshall算法,B线性查找C折半查找：条件D分快查找E二元查找树：什么叫二元查找树、插入结点、删除结点、查找结点E散列法：哈稀函数冲突哈希表的长度哈希函数：直接定址法质数除余法平方取中法折叠法数字分析法随机法处理冲突：开放定址法（线性探测、二次探测）再散列法链地址法建立公共溢出区,第五章查找,A基本概念查找（检索）查找表关键字静态查找动态查找平均查找长度,装填因子标志着哈希表的装满程度，越小，发生冲突的可能性越小，反之，发生冲突的可能性越大。,G成功查找平均查找长度：ASLs查找到散列表中已存在结点的平均比较次数。H失败查找平均查找长度：ASLu查找失败，但找到插入位置的平均比较次数。,C简单的分类算法：气泡排序插入排序冒泡（选择）排序O(n2)DShell分类：缩小增量法E快速分类:快速分类的递归算法与非递归算法F归并分类G堆分类：堆的概念整理堆的算法H基数分类（多关键字）,第六章内部排序（分类）,A排序（分类）排序内部排序外部排序稳定与不稳定的排序方法,B影响分类性能的因素：比较关键字的次数当关键字是字符串时，是主要因素；交换记录位置和移动记录的次数当记录很大时，是主要因素。,各种排序的比较,分析：(1)平均时间性能；(2)当序列“基本有序”时，简单排序中的插入排序最佳；(3)基数排序适用于n值很大而关键字较小的序列；(4)稳定性以基数排序为最佳；,第七章外部排序（分类）,B磁盘文件的归并分类(1)多路归并减少归并遍数(2)并行操作的缓冲区处理使输入、输出和CPU处理尽可能重叠(3)初始归并段的生成m个初始段进行2路归并，需要log2m遍归并；一般地，m个初始段，采用k路归并，需要logkm遍归并。显然，k越大，归并遍数越少，可提高归并的效率。在k路归并时，从k个关键字中选择最小记录时，要比较K-1次。若记录总数为n，每遍要比较的次数为：n*(k-1)log2m/log2k选择树或败者树，k路归并时间O(nlog2m)，与k无关。,A归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段（已有序）进行多遍合并（归并），最后形成一个有序序列。,C磁带文件的归并分类：k路平衡归并分类。,第八章文件,A文件及文件操作文件的概念关键字主关键字次关键字文件的逻辑结构和物理结构文件的操作：InsertDeleteModifyRetrieve检索方式：实时or成批更新方式：实时or成批查询方式：Q1:简单查询，Q2:范围查询，Q3:函数查询，Q4:布尔查询,B文件的组织顺序方式，索引方式，散列方式，链接方式，倒排方式,复习时注意几个问题,知识的连贯性：认真读书、尊重教材、要注意参考其它教材,注意基本概念：名词的理解、问题的研究对象,算法：（1）遍历算法（线性表、树与二元树、图）；（2）（结点）插入与删除算法（线性表、线索二元树、二元排序树）；（3）注意图中解决同一个问题的不同算法之间的区别；（4）递归算