Jeffrey Wang
文章70
标签131
分类16
【软考知识总结】数据结构和算法

【软考知识总结】数据结构和算法

前言

这一部分的内容除了选择题会出现,还有最后的大题涉及到算法设计和实现,主要内容就是大学时期讲的数据结构相关的内容,数组、链表、栈、队列、串以及常见的排序和搜索算法。

数据结构

数组

连续的存储空间,顺序的分配给数据结构,地址计算,本质是起始地址+前面的元素数量*长度

特殊矩阵

  • 对称矩阵,a[i][j]=a[j][i],相当于对角线对称

  • 对角矩阵,非零元素集中在对角线中心

  • 三角矩阵,主对角线上方全是非零,下方全是零,或者反过来

稀疏矩阵

  • 非零元素个数远少于零元素个数,且不规律

  • 存的时候,可以直接存非零元素

广义表

普通线性表的元素只能是单元素或者单个子表,广义表可以部分元素是单元素,部分元素是子表

一般记为 LS = (a1, a2, …, an),深度就是最深的括号的个数,比如 LS = (1, (2, {3})),深度就是3,原子深度为0,空表深度为1

表头可能是单元素或者表,但表尾只能是表,因为表尾的定义是除去表头之外的其他元素组成的表

树的定义是,其中每一个元素可以有两个或以上的直接后继元素

二叉树

线索二叉树

线索二叉树,以比特标记位,利用那些空闲的指针保存前驱和后继,前驱和后继由遍历形式决定,比如前中后三种遍历方式中,前驱和后继的定义并不一致。

哈夫曼树

哈夫曼树代价的计算,叶子节点的权值*根节点到叶子节点的路径长度,并求和

构建哈夫曼树的重点是,找两个最小的权值节点,加起来作为其父节点,然后把父节点放到集合中,再找两个最小的权值节点,循环往复即可。

哈夫曼树编码的规则是往 左走是0,往右走是1,注意左边小右边大, 构造出来的哈夫曼树是唯一的,所以编码和解码也是唯一的。

树和森林

树和二叉树转换需要掌握

三叉树,主要是把最左边的节点单独拧出来,然后兄弟节点接到最左节点的右边顺着排,然后每个节点的左边就是其下最左的节点,右边就是兄弟,最左节点的规律等同。

还原的时候,也是先把左节点拧出来,然后兄弟列出来,再以同样的方式遍历兄弟节点的最左节点及其兄弟。

查找二叉树,根节点的选择很重要,树的深度影响效率

先序和中序反推树,先序确认根节点,中序确认左右子树,一定不要搞反了,确认根节点后,中序中在根节点前的位于其左边,内部的结构同样的,按照先序找到根节点,然后同样的规律求解。

图的定义:

  • 无向图:无箭头,不分方向

  • 有向图:有方向

  • 完全图:无向完全图和有向完全图,无向完全图中,每个节点两两间都有连线,连线数量为 (n-1) + (n-2)+….1 = n*(n-1)/2,有向完全图的连线数量为无向完全图连线数量的两倍,n*(n-1)

  • 度:顶点的度指的是与顶点相关的边的数量,有向图中由顶点指出以及指入顶点的边分别被称为出度和入度,顶点的度为两者之和。

  • 路径:从一个顶点到另一个顶点的通路,有向图的路径带方向

  • 连通图:如果无向图中所有顶点都是连通的就是连通图

  • 连通分量:无向连通图中最大的连通子图就是连通分量

  • 强连通图:有向图中所有顶点都是连通的图

  • 强连通分量:有向连通图中最大的强连通子图就是连通分量

  • 网:边带权值的图称为网

图的存储

  • 邻接矩阵,arr[i][j] 表示节点 i 到 节点 j 有单向的通路,所以无向图是延对角线对称的,其数组对应的值也可自定义存储权值等信息

  • 邻接表,arr[i] 表示节点 i 到其他节点有单向通路的链表,可附带存储权值等信息

适合采用什么形式,跟图的类型无关,跟节点数和连接数有关

图的遍历

  • 深度遍历,遍历到底,所以遍历结果不一定是一致的

  • 广度遍历,一层层访问所有节点

图的最小生成树

用一个树把所有顶点连起来,树的边权值之和最小,那么这个树就是最小生成树

克鲁斯卡尔算法:把边按照权值排序,依次引用,碰到环的就排除,直到所有的节点被连接起来

普里姆算法:从任意顶点出发,找到最小边,然后把这条边对应的另一个顶点与初始顶点放入集合中,再从这个集合中找最小的边,重复操作直到把所有的顶点都连接起来

克鲁斯卡尔算法和普里姆算法都用了贪心的思维,普利姆算法因为每次都是从集合中的点往外扩散找新的点,所以所有的顶点只会有一个入度,就不会成环。

图的拓扑结构

其诞生是为了解决活动序列成环检测,因为作为一个活动执行计划来说,不能出现活动 A 依赖活动B 执行完毕,而活动 B 反向依赖活动 A 执行完毕,那不就死锁了

构造方法:找到入度为0的节点,然后删掉这个节点和这个节点所对应的边(表示执行这个节点的活动),然后继续找入度为0的节点,循环往复,如果能把所有的节点都删完,说明所有的活动都可以执行完毕,反之就存在环。

算法分析

重要特性

  • 有穷性,有穷步骤,有穷时间
  • 确定性,相同输入得到相同输出
  • 可行性,算法中的操作需可行
  • 输入,零个或多个输入
  • 输出,一个或多个输出

查找

  • 顺序查找,O(n)
  • 二分查找,已排序的情况,O(logn)
  • hash查找

排序

  • 稳定,不稳定
  • 内和外

排序算法

  • 插入排序,顺序序列找到比较合理的位置插入,稳定排序

  • 希尔排序,对大量数据进行分组(按照增量序列分组),每个组内进行插入排序,然后所有的组再进行大的插入排序,同时操作的数据量级可控,适合大量数据排序

  • 简单选择排序,找到合理的数据进行交换,不稳定排序

  • 堆排序,初始化一个大/小顶堆,然后不停的取堆顶,调整堆结构,进而得到顺序的序列,适用于得出仅前几名的场景,效率比较高

  • 冒泡排序,看起来比简单选择交换的数据多,但这是稳定排序

  • 快速排序,给一个基准,左边小于基准,右边大于基准

    • 两个指针,尽可能减少基准和指针数据的交换
  • 归并排序,从子序列长度为1的分组归并开始,一步步的把所有数据排到一个集合内,适合线性表,大文件的排序等

  • 基数排序,多关键字排序,一般是数据特别庞大的时候适用,比如个位、十位、百位做三轮排序,然后从大到小找出结果

推排序的重点

先用二叉树把元素顺序排列好,然后通过大/小顶堆的规则初始化一个堆,取堆顶元素就是一个最值,然后把叶子节点放到堆顶 ,再根据大/小堆的规则进行调整,直到取出自己想要的数量。

只有插入、冒泡、归并和基数是稳定排序,其他的都是不稳定排序

算法理论

分治法:分解为多个独立子问题进行处理,子问题互相独立,并与原问题形式相同

回溯法:系统性的搜索所有的解,深度优先搜索可能解的树

动态规划法:划分子问题,并保证每一个子问题最优,且全局最优

贪心法:划分子问题,子问题是最优的,不考虑全局,不用穷举所有解,但相对性能比较好,不一定能得到最优解

分支限界法:跟回溯法的区别在于,列出所有子情况并抛弃不合理的情况,并非回溯法走深度遍历,相当于广度优先遍历

概率算法:随机选择下一步,能接受一定的错误,能很快出解

近似算法:放弃最优解,使用近似最优解,换取时间和空间复杂度

数据挖掘

爆炸式增长的数据进行分析和信息挖掘,核心是算法

主要功能包含,分类,回归,关联和聚类

考点:

分类是有监督的学习过程

聚类是无监督的学习过程

频繁模式和关联规则挖掘,从频繁模式出发,找到其中关联规则,进而发现交叉销售机会

智能优化算法

以数学为基础,求解工程中优化解的应用技术,包括:

  • ANN,人工神经网络

  • 深度学习

  • 遗传算法,基于自然的演化机制

  • SA,退火算法,求解全局优化算法,模拟加温、等温、冷却

  • TS,禁忌搜索算法,有点贪心的思维,局部近邻搜索的扩展

  • 蚁群算法,寻找优化路径的概率型算法,模拟蚁群寻找食物最短路径,留下类似信息素的信号,形成一个类似正反馈的机制

  • 鸟群觅食法,模拟鸟群飞行时整体方向一致

    • 跟踪个体/全局的极值,通过迭代找到最优解

总结

数据结构需要掌握其原理和多种表现形式,算法需要了解其核心逻辑以及特点

本文作者:Jeffrey Wang
本文链接:https://blog.wj2015.com/2022/06/03/%E3%80%90%E8%BD%AF%E8%80%83%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93%E3%80%91%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×