type
status
date
slug
summary
tags
category
icon
password
专业课复习-数据结构
1.哈夫曼编码,哈夫曼树,等长编码
在含有n个带权叶结点的二叉树中,带权路径长度()最小的二叉树称为哈夫曼树,也成为最优二叉树。
哈夫曼树的构造过程:
- 将n个节点分别作为n棵仅含一个结点的二叉树,构成森林F;
- 构造一个新结点,从F中选取两颗根节点权值最小的树作为新结点的左、右子树,并将新结点的权值置为左、右子树上根结点的权值之和;
- 从F中删除刚才选中的两棵树,同时将新得到的树加入F中;
- 重复步骤2和3,直到F中只剩下一棵树。
在数据通信中,若对每个字符用相等长度的二进制表示,称这种编码方式为固定长度编码,若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码,对出现频率高的字符赋以短编码,对出现频率低的字符赋以长编码,起到压缩数据的效果。
若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。从哈夫曼树到哈夫曼编码:首先,将每个出现的字符当作一个独立的结点,其权值为它出现的频度,构造哈夫曼树。将字符的编码解释为从根至该字符的路径上边标记的序列,其中边标记为0表示“转向左孩子”,标记为1表示“转向右孩子”。
2.快速排序,堆排序,基数排序和归并排序
快速排序:
基本思想是分治法:在待排序表L[1...n]中任取一个元素pivot 作为枢轴(或称基准,通常取首元素),通过一趟快速排序将带排序表划分为独立的两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中的所有元素小于pivot,L[k+1...n]中的所有元素大于或等于pivot,则pivot放在其最终位置L(k)上,这个过程称为一个划分。每次划分可以确定一个元素的位置。然后分别递归地对两个子表重复上述过程,直到每部分内只有一个元素或空为止。
有很多方法可以提高算法的效率:一种是尽量选取一个可以将数据中分的枢轴元素,如从序列的头尾及中间选取三个元素,再取这三个元素的中间值作为枢轴元素;或者随机地从当前表中选取枢轴元素,这样可以使得最坏情况在实际排序中几乎不会发生。
堆排序:
- 构建最大堆:将待排序的序列构建成一个最大堆。最大堆的定义是,父节点的值大于或等于其子节点的值。通过从最后一个非叶子节点开始,依次向上调整每个子树,使得整个序列满足最大堆的性质。
- 堆排序:将最大堆的根节点(即序列中的最大元素)与最后一个元素交换位置,并将序列长度减一。交换后,原最大元素位于序列的最后位置。然后对剩余的元素重新进行最大堆调整。重复执行这个过程,直到序列长度为1,即完成排序。
归并排序:
一种基于分治法的经典排序算法。它的基本思想是将待排序的序列划分成两个子序列,分别对这两个子序列进行递归排序,然后将两个有序的子序列合并成一个有序的序列。
- 分解:将待排序的序列递归地分解成较小的子序列,直到每个子序列只有一个元素,即认为这些子序列是有序的。
- 合并:将两个有序的子序列合并成一个有序的序列。合并过程中,比较两个子序列的首个元素,将较小(或较大)的元素放入合并后的序列中,然后将相应子序列的指针后移,重复该过程,直到一个子序列的元素全部放入合并后的序列中。
- 递归:对合并后的序列重复进行分解和合并操作,直到整个序列排序完成。
基数排序:
非比较型的整数排序算法,根据元素的位值将待排序的数字序列分配到不同的"桶"中,然后按顺序收集这些桶中的元素,从而完成排序。包括分配和收集两个步骤。
3.排序算法性能比较
- 插入排序:直接插入排序,折半插入排序,希尔排序
- 直接插入排序:时间复杂度,空间复杂度,稳定算法
- 折半插入排序:时间复杂度,空间复杂度,稳定算法
- 希尔排序:当n在某个范围时,时间复杂度,最坏情况下为,空间复杂度,不稳定算法
- 交换排序:冒泡排序,快速排序
- 冒泡排序:时间复杂度,空间复杂度,稳定算法
- 快速排序:时间复杂度,空间复杂度(栈的深度为O(logn)),不稳定算法
- 选择排序:简答选择排序,堆排序
- 简单选择排序:时间复杂度,空间复杂度,不稳定算法
- 堆排序:时间复杂度,空间复杂度,不稳定算法
- 归并排序:时间复杂度,空间复杂度,稳定算法
- 基数排序:时间复杂度(d趟分配和收集,一趟收集需要O(r),一趟分配需要O(n)),空间复杂度,稳定算法
4.散列表,哈希查找与二分查找
散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(Key)=Addr(数组下标、索引和内存地址等)。散列表建立了关键字和存储地址之间的一种直接映射关系。
常用的散列函数:
- 直接定址法:
- 除留余数法:,关键在于选好质数p
- 数字分析法:选取数码分布较为均匀的若干位作为散列地址
- 平方取中法:选取关键字的平方值的中间几位作为散列地址
冲突处理方法:
- 开放定址法:
- 线性探测法:发生冲突时顺序查看下一个单元,直到找到一个空闲单元
- 平方探测法:,但是不能探测到所有单元,但至少能够探测到一半单元。
- 双散列法:
- 伪随机法:
- 拉链法:将冲突的关键字用线性链表存储。
散列表的平均查找长度依赖于散列表的填装因子, ,不直接依赖于n或者m。直观来看,填装因子越大,发生冲突的可能性越大,反之发生冲突的可能性越小。
5.图的基本概念
简单图:不存在重复边,不存在顶点到自身的边
完全图(简单完全图):有条边的无向图
连通图:图G中任意两个顶点都是连通的(有路径)
强连通图:有向图中,任意两个顶点u,v,存在u到v的路径,也存在v到u的路径,则此图为强连通图
简单路径:在路径序列中,顶点不重复出现的路径。除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路。
6.图的存储方式
- 邻接矩阵:适合于稠密图,空间复杂度为
- 邻接表:适合于稀疏图,对于无向图复杂度为,有向图为
- 十字链表:当需要同时考虑顶点的出度和入度时,适用于大规模有向图,。
- 邻接多重表:无向图的链式存储结构。
7.图的最短路径算法(Dijkstra算法和Floyd算法)
Dijkstra算法:求解单源点最短路径的经典算法,基于贪心策略,在加权有向图或无向图中找到从源点到其他结点的最短路径。基本思想是从源节点开始,逐步扩展到其他节点,通过不断选择当前距离源节点最近的节点,更新其相邻节点的距离值,直到找到源节点到其他节点的最短路径。具体步骤如下:
- 初始化:集合S初始化为{0},dist[]的初始值
dist[i]=arcs[0][i], i = 1,2,...,n-1
。
- 从顶点集合
V-S
(未访问过的顶点集合)中选出,满足,就是当前求得的一条从出发的最短路径的终点,令。
- 修改从出发到集合V-S上任意一个顶点可达的最短路径长度:若
dist[j]+arcs[j][k] < dist[k]
,则更新dist[k]=dist[j]+arcs[j][k]
。
- 重复步骤2,3共n-1次,直到所有的顶点都包含在S中。
时间复杂度为。
Floyd算法:求解每对顶点间的最短路径。基本思想是通过动态规划的方式逐步更新节点之间的距离,以求得最短路径。时间复杂度为。注意,如果图中存在负权回路,则Floyd算法无法正确工作,因为负权回路中存在无限小的路径,算法无法收敛。实际使用中可以将算有权值加上一个数,将其转化为正权值。
8.图的最小生成树算法(Prime算法和Kruskal算法)
Prime算法:贪心算法,基本思想是从一个起始顶点开始,逐步扩展生成树,每次选择当前生成树到非生成树顶点的最小权重边,直到生成树包含了图中的所有顶点为止。
初始时从图中任取一顶点加入树T,此时树中只有一个顶点,之后选择一个与当前T中顶点集合距离最近的顶点,并将该顶点和相应的边加入T,每次操作后T中的定点数和边数都增1。以此类推,直到图中所有的顶点都并入T,得到的T就是最小生成树。此时T中必然有n-1条边。
算法复杂度为,不依赖于,因此它适用于求解稠密图的最小生成树。
Kruskal算法:按权值的递增次序选择合适的边来构造最小生成树。
初始时只有n个顶点而无边的非连通图,每个顶点自成一个连通分量,然后按照边的权值由小到大的顺序,不断选取当前未被选取过且权值最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入T,否则舍弃此边而选择下一条权值最小的边。依次类推,直到T中所有顶点都在一个连通分量上。
算法复杂度为,适合于边稀疏而顶点较多的图。
9.图的遍历
- 广度优先搜索先访问离起点近的顶点,然后访问远的顶点。图的遍历,图最短路径,连通性检测,网络广播等可以通过队列来实现。
- 选择一个起始顶点,将其标记为已访问,并将其加入到一个队列中。
- 从队列中取出一个顶点,访问该顶点,并将其所有未访问的邻接顶点加入队列。
- 重复执行步骤2,直到队列为空。
- 深度优先搜索从图的某个起始顶点开始,沿着一条路径一直深入直到无法继续或达到目标顶点,然后回溯到前一个节点,继续探索其他路径,直到遍历完整个图。可以实现图的遍历,拓扑排序,环检测,连通性检测等。可以通过递归或者栈来实现。
- 选择一个起始顶点,将其标记为已访问。
- 访问当前顶点,并遍历其未访问的邻接顶点。如果存在未访问的邻接顶点,则选择其中一个作为下一个当前顶点,并重复步骤2。
- 如果当前顶点没有未访问的邻接顶点,或者已经遍历了所有的邻接顶点,则回溯到上一个顶点,并继续探索其他未访问的邻接顶点。
- 重复执行步骤2和步骤3,直到遍历完整个图。
10.平衡二叉树、完全二叉树
平衡二叉树:树上任意一个结点的左子树和右子树的深度之差不超过1。
完全二叉树:当且仅当每个结点都与高为h的满二叉树中编号1~n的结点一一对应时,称为完全二叉树。
二叉排序树:左子树上所有结点的关键字均小于根结点的关键字,右子树上的所有结点的关键字均大于根结点的关键字,左子树和右子树又各是一颗二叉排序树。
11.二叉树的遍历
- 先序遍历:访问根节点,先序遍历左子树,先序遍历右子树。
- 中序遍历:中序遍历左子树,访问根结点,中序遍历右子树。
- 后序遍历:后序遍历左子树,后序遍历右子树,访问根结点。
三种遍历算法中,递归遍历左、右子树的顺序都是固定的,只是访问根结点的顺序不同。时间复杂度都为。中序+先序、中序+后序、中序+层序可以唯一确定一颗二叉树。
12.栈、队列、循环队列
- 栈:后进先出(Last-In-First-Out,LIFO)原则,操作受限的线性表,只能在一端进行插入和删除。栈的应用有函数调用,表达式求值,括号匹配,编译器和解释器中的语法分析和运行时环境管理等。
- 队列:先进先出(First-In-First-Out,FIFO)原则,操作受限的线性表,只能在表的一端进行插入操作(入队),在另一端进行删除操作(出队)。队列的应用有线程调度,网络通信,缓冲区管理,广度优先搜索,打印机。
- 循环队列:当队列的尾部到达数组的尾部时,可以循环回到数组的开头继续存储,形成循环的效果,避免数据迁移和浪费。
- 作者:JsingMog
- 链接:https://jsingmog.top/article/note3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。