当前位置:   article > 正文

数据结构期末复习汇总

数据结构期末

绪论

 

线性表

 

头插法

 

尾插法

 

栈和队列

栈:先进后出

队列:先进先出

 

循环队列

树和二叉树

 

在这里插入图片描述

二叉树:每个节点最多有两个分支(分支的度小于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)

稳定性:不稳定排序

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/169383
推荐阅读
相关标签
  

闽ICP备14008679号