数据结构与算法-数据结构-总结

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

数据型、数据结构与抽象数据型抽象数据型的规格描述（语法、语义）抽象数据型的实现抽象数据型的优点多层次抽象技术E算法什么叫算法？算法的特征“好”的算法的评价标准对算法的正确性的要求算法的描述类语言F算法分析算法的时间特性时间复杂度T(n)空间复杂度S(n)数据结构与算法-数据结构-总结全文共23页，当前为第2页。①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);③CeeateBT(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数据结构与算法-数据结构-总结全文共23页，当前为第3页。第二章线性表A线性表的概念什么叫线性表抽象数据型线性表B线性表的实现静态数据结构动态数据结构顺序存储（数组实现）链式存储（指针）游标（静态链表）C线性链表表头结点单向链表双向链表单向循环量表双向循环链表D限定性数据结构：栈&队列E栈栈的概念ADT栈栈的存储结构栈的应用:栈与递归迷宫求解表达式转换与求值F队列队列的概念ADT队列队列的存储结构循环队列G线性表的应用：多项式的表示多项式相加运算数据结构与算法-数据结构-总结全文共23页，当前为第4页。H串串的基本概念ADT串串的存储结构存储密度I数组数组的概念ADT数组数组的存储结构数组的压缩存储：特殊矩阵、对角或带状矩阵、稀疏矩阵J广义表基本概念广义表的存储结构数据结构与算法-数据结构-总结全文共23页，当前为第5页。第三章树与二叉树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。数据结构与算法-数据结构-总结全文共23页，当前为第6页。D树

ADT树树的存储结构：双亲表示法，孩子表示法（邻接表），树的左右链表示树与二叉树的转换，森林与二叉树的转换树的遍历：先序、中序和后序遍历树E树的应用用树表示集合、判定树、哈夫曼树及其应用、最优编码C二叉树的相似与等价，二叉树的复制算法数据结构与算法-数据结构-总结全文共23页，当前为第7页。第四章图以及与图有关的算法A图的基本概念图的定义ADT图有向图无向图弧边顶点邻接点相邻依附环路权子图带标号的图（网）路径简单路径连通图强连通图连通分量强连通分量完全图稀疏图稠密图度入度出度生成树B图的表示（存储结构）：邻接矩阵邻接表C图的遍历（搜索）算法：先深搜索（DFS）先广搜索（BFS）D图与树的关系生成树先深生成森林先广生成森林树边与回退边开放树最小生成树及其算法（MST性质、Prim、Kruskal算法）E无向图的双连通性关结点双连通图双连通分量F有向图的搜索生成树生成森林如何区别树边、向前边、回退边和横边G强连通性：强连通分量，归约图，图的中心点的概念及求解方法数据结构与算法-数据结构-总结全文共23页，当前为第8页。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算法数据结构与算法-数据结构-总结全文共23页，当前为第9页。B线性查找C折半查找：条件D分快查找EAVL树FB-树B+树G二叉查找树：什么叫二叉查找树、插入结点、删除结点、查找结点H散列法：哈稀函数冲突哈希表的长度哈希函数：直接定址法质数除余法平方取中法折叠法数字分析法随机法处理冲突：开放定址法（线性探测、二次探测）再散列法链地址法建立公共溢出区第五章查找A基本概念查找（检索）查找表关键字静态查找动态查找平均查找长度数据结构与算法-数据结构-总结全文共23页，当前为第10页。二次探测法再散列法链地址法线性探测法查找失败（插入记录）查找成功处理冲突方法L几种处理冲突方法的平均查找长度装填因子α标志着哈希表的装满程度，α越小，发生冲突的可能性越小，反之，发生冲突的可能性越大。J成功查找平均查找长度：ASLs

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

查找失败，但找到插入位置的平均比较次数。I装填因子：α=表中装入的记录数哈希表的长度数据结构与算法-数据结构-总结全文共23页，当前为第11页。查找分块查找折半查找线性查找地址散列法/哈希表检索平衡二叉树/AVL树减小二叉树的高度，提高查找效率m-路查找树增加宽度，减小高度，减少读盘次数平衡树B-/B+树平衡m-路查找树/BalancedTree二叉查找树/二叉排序树/二叉检索树动态查找理解概念掌握结构阅读算法数据结构与算法-数据结构-总结全文共23页，当前为第12页。……514112114522525824828^………5112522828^5522^数据结构与算法-数据结构-总结全文共23页，当前为第13页。redis和levelDB都是用了它；他在有序链表的基础上进行扩展；解决了有序链表结构查找特定值困难的问题；查找特定值的时间复杂度为O(logn)；一种可以代替平衡树的数据结构；SkipList又称跳跃表简称跳表数据结构与算法-数据结构-总结全文共23页，当前为第14页。C简单的分类算法：气泡排序插入排序冒泡（选择）排序

O(n2)DShell分类：缩小增量法E快速分类:快速分类的递归算法与非递归算法F归并分类G堆分类：堆的概念整理堆的算法H基数分类（多关键字）第六章内部排序（分类）A排序（分类）排序内部排序外部排序稳定与不稳定的排序方法B影响分类性能的因素：比较关键字的次数—当关键字是字符串时，是主要因素；交换记录位置和移动记录的次数—当记录很大时，是主要因素。数据结构与算法-数据结构-总结全文共23页，当前为第15页。各种排序的比较排序方法平均时间最好情况最坏情况辅助空间稳定性简单排序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)稳定性以基数排序为最佳；数据结构与算法-数据结构-总结全文共23页，当前为第16页。算法简单性比较：从算法简单性看，一类是简单算法，包括直接插入排序、直接选择排序和起泡排序；另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。待排序的记录个数比较：从待排序的记录个数n的大小看n越小，采用简单排序方法越合适；n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。关键字值的分布情况比较当待排序记录按关键的值有序时，插入排序和起泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。数据结构与算法-数据结构-总结全文共23页，当前为第17页。不同条件下，排序方法的选择：

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；且以直接插入排序最佳。

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏况。这两种排序都是不稳定的。基数排序适用于n值很大而关键字较小的序列。若要求排序稳定，则可选用归并排序，基数排序稳定性最佳。数据结构与算法-数据结构-总结全文共23页，当前为第18页。第七章外部排序（分类）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路平衡归并分类。数据结构与算法-数据结构-总结全文共23页，当前为第19页。第八章文件A文件及文件操作文件的概念关键字主关键字次关键字文件的逻辑结构和物理结构文件的操作：InsertDeleteModifyRetrieve

检索方式：实时or成批更新方式：实时or成批查询方式：Q1:简单查询，Q2:范围查询，Q3:函数查询，Q4:布尔查询B文件的组织顺序方式，索引方式，散列方式，链接方式，倒排方式数据结构与算法-数据结构-总结全文共23页，当前为第20页。复习时注意几个问题知识的连贯性：认真读书、尊重教材、要注意参考其它教材注意基本概念：名词的理解、问题的研究对象算法：（1）遍历算法（线性表、树与二叉树、图）；（