返回

数据结构

nothing here

数据结构

数据结构包括:逻辑结构、存储结构和数据的运算。一个算法的设计取决于所选择的逻辑结构,而算法的实现依赖于所采用的存储结构。

逻辑结构主要如下图:

image-20220722214044594

存储结构分为:顺序存储、链式存储、索引存储(索引表)、散列存储(哈希)

算法具有5个特性:有穷性、确定性、可行性、输入和输出

算法的效率用时间复杂度和空间复杂度度量,其中时间复杂度一般考虑最坏的情况下的时间复杂度。原地工作指辅助空间为常量。

线性表:个数有限、逻辑上顺序、数据元素、类型相同、抽象

线性表的位序从1开始,数组下标从0开始

顺序表特点:随机访问、存储密度高

单链表存在一定的存储空间浪费,有无头指针在很大程度上会改变指针的各项操作(有头指针可以视空链表和正常链表为同仁)。

单链表、双向链表、循环链表、静态链表

栈是单口线性表:栈顶是允许插入删除的一端,栈底是固定的不允许插入删除的一端。

注意文字游戏:n个不同元素进栈的出栈个数有$\frac{1}{n+1}C_{2n}^n$

注意栈顶元素初始化值为-1还是0

共享栈:

image-20220722223545590
image-20220722223545590

栈可以链式存储,但是头结点同样会对操作造成较大的区别

队列的队头出队列,队尾入队列。正常的队列会出现假溢出情况。

队头指针front必然是顺序表开始的位置,但是队尾不同,有可能是顺序表结束的位置,也有可能是下一个位置,操作同样不同。

循环队列的队头和队尾变化:

初始 front=rear=0

入队front=(front+1)%maxsize

出队rear=(rear+1)%maxsize

满的情况比较复杂,三种解决方案:牺牲一个位置区分,此时判满:(rear+1)%maxsize == front。令size=maxsize为满。增加tag,插入时满为tag=1,删除时空tag=0.

队列的链式存储,队头为链头。还有双端队列(两端均可以出入队列)

栈可以用于表达式求值,构建的输后续遍历即为后缀表达式,对应的也可以根据后缀表达式构建出原本的计算方式(从头往后,遇到操作符,出栈两个元素计算后入栈直至所有的元素被计算完成)。

栈还可以用于实现非递归(麻了),队列可以用于层序遍历(入队,出队时将元素的子节点入队)。

矩阵有较多表达形式,为了压缩矩阵的存储空间,这里设计了多种矩阵:

对称矩阵(存于一维数组)对应的$$k=\frac{i(i-1)}{2}+j-1$$下三角和主对角线;$k=\frac{j(j-1)}{2}+i-1$上三角区元素。上下三角矩阵类似。三对角矩阵则按行存取$k=2i+j-3$。稀疏矩阵可以使用索引记录(后面还有比较离谱的存储方式)

串给我爬

树应该是较难的一部分了,加上查找部分的红黑树,估计能和图两个人当老流氓了。不过DS好就好在理解就能解决绝大多数问题。

几个基础概念,树的高度、深度、度、层次、路径、森林

树的几个等式:树的结点数=度数和+1

二叉树是考察最多的内容,满二叉树和完全二叉树(注意两者不一样)、二叉排序树(左孩子小根,右孩子大根)、平衡二叉树

二叉树的几个等式:$n_0=n_2+1$完全二叉树的高度、结点数判定和计算

二叉树的存储分为顺序存储和链式存储,前者层次遍历,空节点设为0,后者是通常采用的方式,这里主要学习链式二叉树

链式的二叉树的先序中序后序遍历和如何转化为非递归算法(都是用栈),层次遍历用队列。遍历节点确定二叉树:知道先序和后序无法唯一确定,知道中序和层序可以确定

线索二叉树在二叉树的基础上加了ltag和rtag分别表示左右节点是前驱还是后继(0表示孩子、1表示后继),注意的一点是只有空结点需要用上tag标志,线索二叉树的线索如何指则取决于遍历方式。

树和森林的重点在于存储结构和转换(二叉树的存储结构不一定能用来存树)。树的存储通常有:双亲表示法(用顺序表存储)、孩子表示法、孩子兄弟表示法(这种方法常用于转二叉树)。

树与森林与二叉树的转换就没什么好说的了。

遍历方式:(通用方法就是将树和森林转为二叉树后遍历)

森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历(后根遍历) 中序遍历

哈夫曼和并查集(建议理解一手原理)

图是第二个流氓,有向图,无向图,简单图、多重图(不讨论)、完全图、子图(又有所有节点即可)、连通、连通图、连通分量(注意,连通分量指子图不是量),强连通(对应于有向图),生成树、生成森林(极小连通子图只有单边连接)、顶点的度、入度、出度

图的存储方式也有一车:邻接矩阵法(A[i][j]来表示i和j节点之间的边),邻接表法(解决邻接矩阵的稀疏问题,使用链表),十字链表(存有向图的,弧节点有5个域而顶点节点有3个域,关于这部分的细节建议好好看书)

图的遍历有深度优先和广度优先

图的应用更是重量级:最小生成树(kruskal、prim),最短路径(dijkstra、floyd),拓扑排序,关键路径(每个都能一道大题)

生成树:Prim取点集合,找距离最小的点。Kruskal,找能使连通的最小边

最短路径:Dijkstra(动态的贪心)从源点开始,每次选择最小的路径更新其它点,O($V^2$),不适用于负权值。Floyd求出全部的之间的最短,$O(V^3)$允许负权值,主对角线扫描

拓扑排序:依次删除入度为0的点

关键路径:事件最早的发生时间ve,事件最迟发生时间vl,活动最早开始事件e,活动最迟开始时间l,d=l-e。

image-20220731162302039
image-20220731162302039

关键路径不唯一,e正求,l反求,d=0即为关键路径

查找有新增了个重量级——红黑树

时间复杂度:

查找 时间复杂度 原理 备注
顺序查找 $O(n)$ 扫一遍 可以设置哨兵
二分(折半)查找 $O(logn)$ 每次从中间开始,大往后,小往前
分块(索引顺序)查找 自己算 块内无序,块间有序。块间二分,块内顺序 要求太苛刻了
二叉排序树(BST) $O(n)$ 左节点小于根节点,右节点大于根节点 难在插入(不考虑插入相同元素)和删除(三种情况)
平衡二叉树(AVL) $O(logn)$ 左右高度差不能大于1,插入和删除时调整最小不平衡子树 相当蛋疼
红黑树(RBT) $O(logn)$ 究极难
B树 也不容易
B+树
散列查找 $O(1)$ 全场最佳

平衡二叉树单拉出来,调整时有四种方式:LL(右单),RR(左单),LR(先左后右),RL(先右后左),L和R分别表示插入的顺序,LL就是左子树的左子树,类推。

尽管红黑树和二叉排序树的,平衡二叉树很容易被插入和删除破坏,所以要找平衡因子,而且需要重新计算。而红黑树不容易破坏红黑树特性,插入和删除时间开销很小(所以只查不插删就使用AVL,否则RBT)

红黑树首先是二叉排序树:

image-20220731165842955
image-20220731165842955

image-20220731165919285
image-20220731165919285

第5个性质就是堪比AVL的地方。黑高bh表示一个节点到达任意空叶节点的路径上的黑节点的数量。

image-20220731170730435
image-20220731170730435

image-20220731171212265
image-20220731171212265

插入只会破坏相邻不红的特性

image-20220731173211813
image-20220731173211813

image-20220731173347357
image-20220731173347357

B树n叉就有被n-1和关键字分为n个范围。为了使得查找和存储效率较高,一般我们通过认为m叉查找树中除根节点外至少有[m/2]个分叉,即m/2-1个关键字,且需要所有子树高度相同

叶子节点就是失败节点而终端结点指最后一层。

image-20220731180010775
image-20220731180010775

n个关键字必有n+1个叶子节点

image-20220731180344094
image-20220731180344094

B+树相较于B树,把区间换成了关键字。B+树支持顺序查找,也可以通过树查找,非叶子节点都仅做索引,且为叶子节点中的最大值。

散列查找速度最佳,主要是处理冲突和散列函数(直接定址法、余数法、数则分析、平方取中)处理冲突有开放定址(线性探测法、平方探测法、双散列法)和拉链法

装填因子的概念

常见的排序就没什么好说的了,关键是一些新的排序方式

排序 复杂度和稳定性 原理 备注
直接插入排序 $O(n^2)$ 稳定 从前往后找元素,从后往前比,插入后后面的后移
折半插入排序 $O(n^2)$ 稳定 查找的时候使用二分查找
希尔排序(缩小增量排序) $O(n^{1.3})O(n^2)$ 不稳定 跨增量先排序,到最后一轮就相当于插入排序了 仅适用于顺序表
冒泡排序 $O(n^2)$ 稳定 将最小的放前面或最大的放后面 每趟排序都会有一个回到自己的位置上
快速排序 $O(n^2)$ 不稳定 分治法,每层找中间元素划分直到最底层 平均性能最优,每趟排序都会有一个回到自己的位置上
选择排序 $O(n^2)$ 不稳定 找最小,次小元素逐渐往后排
堆排序 建堆$O(n)$+排序$O(nlogn)$=$O(nlogn)$ 不稳定
归并排序 $O(nlogn)$ 稳定 对相邻两组元素排序并合并,递归的进行
基数排序 $O(d(n+r))$ 稳定 根据数的特性进行,每次根据某个特性创造链并排序重整

堆:顺序的完全二叉树,非叶子节点比左右孩子节点值大(大根堆)或小(小根堆)。处理非叶子节点从后往前,逐渐交换从而变为堆。排序的时候每次将堆顶和堆底交换,并重新调整堆。插入时放到最底然后调整,删除时将最后一个填充删除元素然后调整

image-20220803150251501
image-20220803150251501

外部排序:指数据量太大内存放不下需要外存和内存多次交换。由于磁盘IO时间多于排序时间,因此时间主要考虑访问磁盘的次数。

通常使用归并排序,增大归并路数或者减少初始归并的段数能够提高速度

image-20220803154228115
image-20220803154228115

增加归并的段数会导致关键字比较次数的增加,所以可以考虑使用败者树:

image-20220803160106077
image-20220803160106077

其中叶子节点实际并不存在而非叶子节点存储着索引

置换选择排序用于减少段数。若工作区中的所有元素均小于构件的归并段中的最大值,那么停止归并段的构造。

由于置换选择排序减少了归并段的数量,当使用归并树对归并段进行排序时,读写的数量取决于归并段的块数,在这种情况下,建议使用哈夫曼树进行处理。但是在多路归并的时候会遇到最后一层结点数不够的情况,这时候需要设置长度为0的虚段,从而减少读写次数。需要补充的虚段的数量就是k叉树缺的结点数

image-20220803161354012
image-20220803161354012

Licensed under CC BY-NC-SA 4.0
豫ICP备2021032923号
Built with Hugo
Theme Stack designed by Jimmy