数据结构期末复习汇总

绪论

 

线性表

 

头插法

 

尾插法

 

栈和队列

栈：先进后出

队列：先进先出

 

循环队列

树和二叉树

 

二叉树：每个节点最多有两个分支（分支的度小于2）的树结构，可为空树。
根节点：一棵树最上面的节点称为根节点。
左右子树：某个节点的左分支叫做左子树，右分支叫做右子树。
左右孩子：某个节点的左、右分支的根节点叫做该节点的左、右孩子。
兄弟节点：具有相同父节点的节点互为兄弟节点。
节点的度：节点拥有的子树数。
叶子节点：没有任何子节点的节点称为叶子节点。
内部节点：非叶子节点称为内部节点。
根的层次：从根节点开始定义，根为第一层，根的孩子为第二层，如此计数，直到该结点为止。
树的深度和高度：二叉树中节点的最大层次称为二叉树的深度或高度。

森林：由m(m>=0)棵互不相交的树的集合称为森林。如上图只有一个树也是森林。

一般树与二叉树的区别

1. 树的结点个数至少为1，而二叉树的结点个数可以为0；
2. 树的结点最大度数没有限制，而二叉树结点的最大度数为2；
3. 树的结点无左、右之分，而二叉树的结点有左、右之分。

1）、完全二叉树

在一棵二叉树中，除了最后一层，都是满的，并且最后一层或者是满的，或者是右边缺少连续若干节点，成为完全二叉树。

如图所示：

2）、满二叉树

图

几个点 来确定 是否是 连通图 王道里的 ？

无向完全图:边的取值范围 0-n(n-1)/2

有向完全图：边的取值范围 0-n(n-1)

若图中顶点数为n,则它的生成树含n-1条边

若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。

邻接矩阵：适用于稠密图（浪费大量存储空间）

邻接表法：适用于稀疏图（边数少）

 

DFS  深度 先序  栈  时间复杂度     邻接矩阵O（n^2） 邻接表O(n+e)  n个顶点 e条边

BFS 广度  层序 队列  时间复杂度      邻接矩阵O（n^2） 邻接表O(n+e)  n个顶点 e条边

 

最小生成树性质：

1.最小生成树不唯一

2.最小生成树的边的权值之和唯一

3.最小生成树的边数为顶点数减1

Prim算法 ：适用于边稠密的图           像 最短路径 Dijkstra算法  时间复杂度 O（n^2）

Kruskal算法：适用于边稀疏而顶点多的图        时间复杂度 O（eloge）

 

最短路径   时间复杂度 O（n^2）

Floyd算法    时间复杂度 O（n^3） 适用于稠密图 

 

查找

静态查找：只查不改  （顺序查找、二分查找）

动态查找：动态地插或删的表

平均查找长度：ASL

 

顺序查找：在线性表中查找，（在有序表或无序表查找）

查找成功：ASL=(n+1)/2

查找不成功：ASL=n+1

顺序查找缺点：n大时，平均查找长度较大，效率低 优点：对数据元素存储无要求

线性链表只能进行顺序查找

二分查找：时间复杂度 O（long2n）

只适合顺序存储结构，不适合链式存储结构，要先排序。

 

散列表：建立了关键字和存储地址之间的直接映射关系。 时间复杂度 O(1)

再散列法

拉链法

影响散列表查找效率的三个因素：散列函数，处理冲突的方法和装填因子

 

排序

 

都是内部排序

直接插入排序

空间复杂度 O(1)

时间复杂度:最好情况 O(n)

                   最坏情况 O(n^2)

                   平均情况  O(n^2)

稳定性：稳定排序

适用于：顺序存储和链式存储的线性表

冒泡排序

空间复杂度 O(1)

时间复杂度:最好情况 O(n)

                   最坏情况 O(n^2)

                   平均情况  O(n^2)

稳定性：稳定排序

选择排序

空间复杂度 O(1)

时间复杂度:始终是 O(n^2)

                   平均情况  O(n^2)

稳定性：不稳定排序