数据结构 A数据结构总结学习课件

《数据结构与算法基础》课程回顾与总结第一章绪论A数据结构研究对象信息数据数据元素数据项数据结构数据对象数据类型B数据结构逻辑结构存储结构（物理结构）数据结构分类C数据结构发展概况D抽象数据型(ADT)

数据型、数据结构与抽象数据型抽象数据型的规格描述（语法、语义）抽象数据型的实现抽象数据型的优点多层次抽象技术E算法什么叫算法？算法的特征“好”的算法的评价标准对算法的正确性的要求算法的描述类语言F算法分析算法的时间特性时间复杂度T(n)空间复杂度S(n)①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)①MAKENULL(S)②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)①MAKENULL(Q)②FRONT(Q)③ENQUEUE(x,Q)④DEQUEUE(Q)⑤EMPTY(Q)①EMPTY(BT);②ISEMPTY(BT);③CREATEBT(V,LT,RT);④LCHILD(BT);⑤RCHILD(BT);⑥DATA(BT);①NodeNewNode(G,v)②VoidDelNode(G,v)③VoidSetSucc(G,v1,v2)④VoidDelSucc(G,v1,v2)⑤ListofnodeSucc(G,v)⑥LisyofnodePred(G,v)⑦IntIsEdge(G,v1,v2)⑧NodeFirstAdjVex(G,v)⑨NodeNextAdjVex(G,v,w)①stringNULL();②booleanISNULL(S);③VoidIN(S,a);④intLEN(S);⑤VoidCONCAT(S1,S2);⑥stringSUBSTR(S,m,n);⑦booleanINDEX(S,S1);①CREATE（）；建立一个空数组②RETRIEVE（array，index）；返回第index个元素③

STORE（array，index，value）；在数组array中，为第index个元素赋值value第二章线性表A线性表的概念什么叫线性表抽象数据型线性表B线性表的实现静态数据结构动态数据结构顺序存储（数组实现）链式存储（指针）游标（静态链表）C线性链表表头结点单向链表双向链表单向循环量表双向循环链表D限定性数据结构：栈&队列E栈栈的概念ADT栈栈的存储结构栈的应用:栈与递归迷宫求解表达式转换与求值F队列队列的概念ADT队列队列的存储结构循环队列G线性表的应用：多项式的表示多项式相加运算H串串的基本概念ADT串串的存储结构存储密度I数组数组的概念ADT数组数组的存储结构数组的压缩存储：特殊矩阵、对角或带状矩阵、稀疏矩阵J广义表基本概念广义表的存储结构第三章树与二叉树A树的基本术语树子树结点分支度路叶子非终结（端）结点终结（端）结点儿子父亲兄弟堂兄弟祖先子孙结点；层高度（深度）结点的顺序层序有序树无序树森林B二叉树二叉树的定义，ADT二叉树，满二叉树，完全二叉树二叉树的遍历：先序遍历、中序遍历和后序遍历，层序遍历二叉树遍历的非递归算法（先序、中序和后序）二叉树的性质：（1～5）二叉树的存储结构：顺序存储、链式存储（二叉链表）线索二叉树：基本概念，先序、中序与后序线索求线索二叉树的（先序、中序、后序）前驱与后继结点线索二叉树的遍历线索二叉树中插入、删除结点的讨论性质1：在二叉树中的第i层的结点数最多为：2i-1。性质2：高度为k的二叉树其结点总数最多为2k－1(k≥1)

。性质3：对任意的非空二叉树T

，如果叶结点的个数为n0，而其度为2

的结点数为n2，则：n0=n2+1

。性质4：具有n

个结点的完全二叉树的深度为log2n+1。性质5：如果对一棵有n个结点的二叉树的结点按层序编号，则对任一结点i有：

⑴如果i=1，则结点i是二叉树的根，无双亲；如果i＞1，则其双亲结点是i/2；

⑵如果2i＞n，则结点i无左孩子结点，否则其左孩子结点是2i；

⑶如果2i+1＞n，则结点i无右孩子结点，否则其右孩子结点是2i+1。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分快查找EAVL树FB-树B+树G二叉查找树：什么叫二叉查找树、插入结点、删除结点、查找结点H散列法：哈稀函数冲突哈希表的长度哈希函数：直接定址法质数除余法平方取中法折叠法数字分析法随机法处理冲突：开放定址法（线性探测、二次探测）再散列法链地址法建立公共溢出区第五章查找A基本概念查找（检索）查找表关键字静态查找动态查找平均查找长度二次探测法再散列法链地址法线性探测法查找失败（插入记录）查找成功处理冲突方法L几种处理冲突方法的平均查找长度装填因子α标志着哈希表的装满程度，α越小，发生冲突的可能性越小，反之，发生冲突的可能性越大。J成功查找平均查找长度：ASLs

查找到散列表中已存在结点的平均比较次数。K失败查找平均查找长度：ASLu

查找失败，但找到插入位置的平均比较次数。I装填因子：α=表中装入的记录数哈希表的长度查找分块查找折半查找线性查找地址散列法/哈希表检索平衡二叉树/AVL树减小二叉树的高度，提高查找效率m-路查找树增加宽度，减小高度，减少读盘次数平衡树B-/B+树平衡m-路查找树/BalancedTree二叉查找树/二叉排序树/二叉检索树动态查找理解概念掌握结构阅读算法C简单的分类算法：气泡排序插入排序冒泡（选择）排序

O(n2)DShell分类：缩小增量法E快速分类:快速分类的递归算法与非递归算法F归并分类G堆分类：堆的概念整理堆的算法H基数分类（多关键字）第六章内部排序（分类）A排序（分类）排序内部排序外部排序稳定与不稳定的排序方法B影响分类性能的因素：比较关键字的次数—当关键字是字符串时，是主要因素；交换记录位置和移动记录的次数—当记录很大时，是主要因素。各种排序的比较排序方法平均时间最好情况最坏情况辅助空间稳定性简单排序O(n2)O（n）O(n2)O(1)稳定希尔排序O（n1.3）------O(1)不稳定快速排序O(n·log2n)O(n·log2n)O(n2)O(1)不稳定堆排序O(n·log2n)O(n·log2n)O(n·log2n)O(1)不稳定归并排序O(n·log2n)O(n·log2n)O(n·log2n)O(n)稳定基数排序O(d·(n+r·d))O(d·(n+r·d))O(d·(n+r·d))O(n+r·d)稳定分析：(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(n·log2m)，与k无关。A归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段（已有序）进行多遍合并（归并），最后形成一个有序序列。C磁带文件的归并分类：k路平衡归并分类。第八章文件A文件及文件操作文件的概念