数据结构复习提纲

队列：它是只允许在表的一端进行插入，另一端进行删除的受限线性表。可以插入的这端叫队尾，可以删除的这端叫队头，遵循先进先出的原则。

第五章。数组通常有两种顺序储存方式：行优先顺序和列优先顺序。

c语言中，二维数组地址的计算函数为loc(aij)=loc(a00)+(i*(d2+1)+j)*d。（d是储存单元）。

三元组表：例：

广义表：深度：指表展开后所含括号的层数，广义表中第一个元素是表头，剩余元素的集合是表尾。取表头head()；取表尾tail()：

第六章。树：是n个结点的有限集合：满足有且只有一个特定的称为根的结点，其余结点可以分为m个互不相交的有限集合，每一集合是原树的子树。

度：一个结点子树的个数称为该结点的度。叶子：度为零的结点。路径：ki到ki结点数列。

层数：从根结点算起。高度（深度）：树中结点的最大层数。

考察二叉树的性质：1、二叉树第i层的结点数目最多为2i-1；2、深度为k的二叉树至多有2i—1个；3、任意二叉树中，若终端结点的个数为n0，度为2，则n0=n2+1（n0为0度结点）；4、具有n个结点的完全二叉树的深度为log2n(向下取整)+1。[,

完全二叉树：若一颗二叉树至多只有最下面的两层上的结点的度数可以小于2，并且结点都集中在最左边的若干位置上，则此二叉树称为完全二叉树。

二叉树的遍历：前序遍历、中序遍历、后序遍历。（简答题的考察）。

线索二叉树：为什么建立：结点结构、可以利用空指针、便于寻找前趋后继。

树、森林到二叉树的互相转换。

树的储存：1、双亲链表表示法：例。

2、孩子链表表示表；3双亲链表表示表。

树与森林的遍历：前序和后序。

将树中结点赋予一个有某种意义的实数，称之为该结点的权，结点的带权路径长度，是该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度，定义为树中所有叶子结点的带权路径长度之和。带权路径长度最小的二叉树称为最优二叉树或哈夫曼树。

哈夫曼树的构造。

第七章图。有向图的边称为弧，边的始点称为弧尾，终点称为弧头。

无向完全图有n*(n-1)/2条边，有向完全图有n*(n-1)条边。

无向图中顶点v的度是关联于该顶点的边的数目，记作d（v）。若g为有向图，则把以顶点v为终点的边的数目，称为v的入度，记作id（v），把以顶点v为始点的边的数目称为v的出度，记作od（v），顶点的度则是入度和出度之和。

在一个有向图之中，若存在一个顶点，从该顶点有路径可以到达图中所有的顶点，则称此有向图为有根图，v称作图的根。

若v（g）中任意两个不同的顶点都连通，则称g为连通图。

7.2：图的储存：邻接矩阵n*n、（算法的时间复杂度为o（n2））邻接表（算法的时间复杂度为o（n+e））。

7.3图的遍历：深度优先搜索（又称dfs序列，类似前序遍历）、广度优先搜索（又称bfs序列，一层层的遍历）；具体根据邻接矩阵和邻接表的情况来遍历，，[

7.4生成树与最小生成树：分为prim算法和kruskal算法。

7.5单源最短路径：参考例题或记录。

7.7关键路径：源点到汇点的最长路径称为关键路径。参考例题，

第八章排序。

n<50时，可采用o（n2）法，即直接选择排序法或者直接插入排序法；

n较大的时候可采用o（nlog2n）法，首选快速排序法，其次堆排序法、归并排序法。

若要关键字基本有序，即稳定的有直接插入排序法和起泡法。

目前公认最好的排序是快速排序。

直接插入排序、起泡算法。

各种排序算法的实现过程

第九章查找。

基于线性表的查找：顺序查找（0(n+1)/2）、*二分查找(log2(n+1)-1)、分块查找(介于两者之间)

基于二叉树的查找：二叉排序树、散列表。

二叉排序树的生成；散列表的构造方法（除余法：解决冲突的两种方法：拉链法（链表）、线性探查法（后移））