软件设计师笔记——（第三章：数据结构）

一、时间复杂度（⭐⭐）二、线性结构（⭐⭐⭐）1、线性表2、栈3、队列4、串三、数组和矩阵（⭐⭐）1、数组2、矩阵四、树（⭐⭐⭐）1、树2、二叉树3、最优二叉树（哈夫曼树）4、二叉排序树5、平衡二叉树五、图（⭐⭐）1、图的遍历2、最小生成树3、拓扑排序六、查找（⭐⭐）1、静态查找2、动态查找七、排序（⭐⭐⭐）1、快速排序2、归并排序3、直接插入排序4、其他排序

大小胖虎

1481人浏览 · 2023-09-25 18:02:35

大小胖虎 · 2023-09-25 18:02:35 发布

一、时间复杂度（⭐⭐）

O(1）<O(log2n）<O(n）<O(nlog2n）<O(n²）<O(n^3）<O(2^n）<O(n！）

1、递归主方法：（根据公式）

2、经典例题

二、线性结构（⭐⭐⭐）

1、线性表

一、顺序存储结构（常量级=O(1)，只要没说最好、最坏复杂度均取平均复杂度）

顺序存储：（静态存储结构）

元素在存储空间的相对位置来表示元素间的逻辑关系
优点：可以访问任意指定序号的元素
缺点：插入和删除需要移动大量元素

顺序表	时间复杂度	时间复杂度
插入操作	最好：O(1) 最坏：O(n)	平均：O(n/2)，即O(n)
删除操作	最好：O(1) 最坏：O(n)	平均：O((n-1)/2)，即O(n)
按值查找	最好：O(1) 最坏：O(n)	平均：O(n/2)，即O(n)
按下标查找	O(1)	O(1)

二、链式存储结构（链式存储不需要移动元素，仅改变指向就行）

链式存储：静态存储结构

数据元素之间的关系需要占用存储空间，存储密度不高
优点：插入和删除不需要移动元素
缺点：不能随机访问，会造成空间浪费

1、链表删除结点：

删除尾结点：时间复杂度O(n)。（需要找到倒数第二个结点，此时复杂度为O(n))
删除头结点：时间复杂度O(1)。
平均情况：时间复杂度O(n)。

2、链表插入结点：

尾部插入结点：时间复杂度O(n)。
头部插入结点：时间复杂度O(1)。
平均情况：时间复杂度O(n)。

3、链表查找指定值的结点的时间复杂度为O(n)。

三、经典例题

2、栈

1、栈：（先进后出的线性表）

只有打印所有元素需要遍历，其余不需要
在函数的实现或者递归的调用中需要栈

2、栈的存储结构

顺序存储：入栈时需要先判断是否栈满，是否出现溢出
链式存储：无头结点，链表的头指针就是栈顶元素

3、栈的应用

表达式求值、括号匹配、汉诺塔等。

4、经典例题

1、入队的序列和出队的序列只可能有一种情况。

2、出栈，可能进一个出一个，也可能进完才出，也有可能......，所以可能对应多个序列。

3、队列

1、队列：（先进先出的线性表）

入队和出队都不需要移动队列中的其他元素（队尾、对头指针的存在）
用循环单链表做队列时，头部有头结点，尾部有尾结点，所以都不需要遍历。
若队列的数据规模确定，则采用顺序存储比链式存储的效率更高。

2、循环队列（先看头尾指针，再看长度，二者可能有偏差，以头尾指针为主）

3、经典例题

根据已知的条件，进行数值代入，最终求解。（顺时针）

+M：防止下溢出
%M ：防止上溢出

1、入队的序列和出队的序列只可能有一种情况，所以一定相同。

2、出栈，可能进一个出一个，也可能进完才出，也有可能进一半出一半，等等一类的，所以可能对应多个序列。因此并不一定相同，也并不一定互逆。

4、串

1、串：（仅由字符构成的有限序列，是一种线性表）

空格也算长度，里面不包含任何字符才是空串(长度为零)
子串：串中任意长度的连续字符构成的
在串比较、求子串、串连接中都不会改变串的内容，而串替换改变内容，因此在链式存储中最不方便。

2、朴素的模式匹配

时间复杂度最好情况O(m)，
最坏情况比较(n-m+1)×m次，即O(m*n)
平均情况O(n+m)

3、KMP算法

前缀：包含第一个字符并且不包含最后一个字符的子串。例：b，bb，bbc，bbca，bbcab（以bbcabem为例）
后缀：包含最后一个字符并且不包含第一个字符的子串。例：e，be，abe，cabe，bcabe（以bbcabem为例）

4、求模式串中next[]的值（动下标，字符不动）

下标	1	2	3	4	5	6	7	8	9	10	11
模式串	a	b	c	a	a	b	b	c	a	b	c
next[j]	0	1	1	1	2	2	3	1	1	2	3

求解方法

1.第一位的next值为0。

2.第二位的next值为1后面求解每一位的next值时，根据前一位进行比较。

3.第三位的next值:看第二位的模式串为b，对应的next值为1，则将第二位的模式串b与j=1的模式串进行比较，不同，则没有相同的字符串，值为1。

4.第四位的next值:看第三位的模式串为c，对应的next值为1，则将第三位的模式串c与j=1的模式串进行比较，不同，则没有相同的字符串，值为1。

5.第五位的next值:看第四位的模式串为a，对应的next值为1，则将第四位的模式串a与j=1的模式串进行比较，相同，则第五位的next值为第四位加1，也就是2。

6.第六位的next值:看第五位的模式串为a，对应的next值为2，则将第五位的模式串a与j=2的模式串进行比较，不同。继续比较，j=2对应的next值为1，将第五位模式串的a再与j=1的模式串比较，相同，则第六位的next值为第二位的next值再加1，也就是2。

7.第七位的next值:看第六位的模式串为b，对应的next值为2，则将第六位的模式串b与j=2的模式串进行比较，相同，则第七位的next值为第六位的nxet值加1，也就是3。

8.第八位的next值:看第七位的模式串为b，对应的next值为3，则将第七位的模式串b与j=3的模式串进行比较，不同。继续比较，j=3对应的next值为1，则将第七位的模式与j=1的模式串进行比较，也不同，则没有相同的字符串，值为1。

9.第九位的next值:看第八位的模式串为c，对应的next值为1，则将第八位的模式串c与j=1的模式串进行比较，不同，则没有相同的字符串，值为1。

10.第10位的next值:看第九位的模式串为a，对应的next值为1，则将第九位的模式串a与j=1的模式串进行比较，相同，则第10位的next值为第九位的next值加1，也就是2。

11.第11位的next值:看第10位的模式串为b，对应的next值为2，则将第10位的模式串b与j=2的模式串进行比较，相同，则第11位的next值为第10位的next值加1，也就是3。

5、经典例题

三、数组和矩阵（⭐⭐）

1、数组

1、数组：（a[0]→a数组本身）（特定值代入即可）

一维数组：Loc(i)=Loc+(i-1)*L（下标从1开始）
二维数组以行为主序（m行n列）：Loc(ij)=Loc+((i-1)*n+(j-1))*L（下标从1开始）
二维数组以列为主序（m行n列）：Loc(ij)=Loc+((j-1)*m+(i-1))*L（下标从1开始）

2、经典例题

2、矩阵

1、对称矩阵（特定值代入即可）

矩阵中的元素Aij=Aji

2、三对角矩阵：矩阵的上(下)三角(不包括对角线)中的元素均为常数或0。

就是只有三条斜对角线，旁边的三角形(都是0)不要，也不需要存储
按行存储从(0,0)开始存储：Aij=2i+j+1
按行存储从(0,0)开始存储：Aij=2j+i+1

3、稀疏矩阵

矩阵很大，存储的东西很少
存储方式：三元顺序表和十字链表

4、经典例题

四、树（⭐⭐⭐）

1、树

度就是子节点的个数，度为0的结点为叶子结点。
树中结点总数=所有节点的度数之和+1
一棵树的最大层数记为树的高度，最大的度数记为树的度
度为m的树中第i层至多有m^(i-1)个结点
高度为h的m次树最多有（m^h-1）/（m-1）个结点

2、二叉树

1、二叉树：每个根节点最多只有两个孩子节点（节点最大的度为2）。

二叉树第i层（i>=1）上至多有2^(i-1)个结点。（不能确定最少，可能存在单支树）
深度为k的二叉树至多有2^k-1个结点（k>=1）
对任何一颗二叉树，n0 = n2+1。(由n=n0+n1+n2、n=e+1、e=2n2+n1推得)（e：分支个数）
具有n个节点的完全二叉树深度为（lgn+1）或者（lg(n+1)）
有n个结点的二叉树根据卡特兰数可得有 $C_{2n}^{n}\div \left ( n+1 \right )$ 种可能

2、完全二叉树

除去最后一层其余都满，结点从左至右依次放置，最后一层不一定满
完全二叉树适合采用顺序存储结构，二叉树适合采用链式存储

3、满二叉树

每层都是满节点

4、二叉树的存储结构

顺序存储需要维护结点和左、右子树的关系，结点为n，左子树则为2n，右子树则为2n+1
链式存储有二叉链表和三叉链表，n个结点的二叉树，二叉链表的空指针为n+1，三叉链表的空指针为n+2。

5、二叉树的遍历

先序遍历、中序遍历、后序遍历、层次遍历
只有先序遍历＋后序遍历不能确定树。

6、经典例题

3、最优二叉树（哈夫曼树）

1、最优二叉树（哈夫曼树）：带权路径长度最短的树

左零右一，几位数*几，贪心策略
总节点数 == 2n - 1 (n为T中元素的个数)
只有度数为2、0 的节点没有度数为1的节点

2、压缩比

压缩比=(等长编码-哈夫曼编码)/等长编码
等长编码x：2的x次方>=几个字符，就是几位
哈夫曼编码：几位*出现频率

3、经典例题

4、二叉排序树

1、二叉排序树：

根节点的关键字大与所有左子树的关键字，小于所有右子树的关键字。
同一层的关键字大小从左至右递增
中序遍历得到的是有序序列
单支树的效率最差
若进行均衡化处理，左右子树的高度差不超过1

2、经典例题

5、平衡二叉树

1、平衡二叉树

任何一个结点左、右子树高度之差的绝对值不超过1
完全二叉树一定是平衡二叉树，但平衡二叉树不一定是完全二叉树。

五、图（⭐⭐）

1、图的遍历

1、图：（线性表和树都是图的一个特例）

完全图（每个顶点都和剩余的顶点有一条边）更适合采用邻接矩阵存储
若n个顶点，无向完全图共有n(n-1)/2条边，有向完全图共有n(n-1)边。
度：顶点的度是指关联该顶点边的数目
有向图(无向图)的边数=总度数/2
无向连通图：每个顶点都是连通的。（最少有n-1条边，最多n(n-1)/2）
有向强连通图：每个顶点都可以来回连通。（最少n边，最多n(n-1)）
非零元素个数=无向图的边数×2=有向图的边数

2、存储结构

邻接矩阵表示法：顶点之间的关系，适用稠密图存(边多)。
邻接链表表示法：适用于稀疏图存(边少)。

3、图的遍历

深度优先遍历DFS（栈）：（回溯，不适用于有向图）（时间复杂度：邻接矩阵O(n^2)，邻接表O(n+e)）
广度优先遍历BFS（队列）：（时间复杂度：邻接矩阵O(n^2)，邻接表O(n+e)）

4、经典例题

2、最小生成树

1、最小生成树：包含所有顶点的树，有且只有n-1条边，权值最小。

普里姆算法(prim)：适用于稠密图，O(n^2)
克鲁斯卡尔算法(kruskal)：适用于稀疏图，O(elge)

3、拓扑排序

在有向无环图中，顶点Vi在Vj之前：

则可能存在弧<Vi,Vj>，一定不存在<Vi,Vj>
则可能存在Vi到Vj的路径，一定不存在Vj到Vi的路径

1、经典例题

六、查找（⭐⭐）

1、静态查找

1、顺序查找：即适用于顺序存储，也适用于链式存储

最多比较n次，平均查找（n+1)/2

2、折半查找（二分）：要求顺序存储，元素有序排列（下取整）

最多比较lgn+1次，平均查找lg(n+1)-1

3、分块查找

2、动态查找

1、哈希表：（可以动态创建）

哈希构造方法:除留取余法，H(key)=key%m=地址，m一般取接近n(n个元素)但不大于n的质数，尽可能使用关键字的所有组成部分都能起作用。
冲突：是指关键字不同的元素映射到相同的存储位置。（常见的解决冲突方法：开放地址法、链地址法、再哈希法）
冲突是不可避免的，只能尽量的避免。
需要比较的个数取决因素:哈希函数、处理冲突的方法、哈希表的装填因子a。（a越小，冲突可能性就越小，反之同理）

2、B-树

3、二叉排序树

4、平衡二叉树

5、经典例题

七、排序（⭐⭐⭐）

排序法	最好时间	平均时间	最坏时间	空间复杂度	稳定度	备注
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定	大部分已排序时较好
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	n小时较好(最垃圾的)
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定	n小时较好
希尔排序	——	O(n^1.25)	——	O(1)	不稳定	插入排序的优化
快速排序	O(nlgn)	O(nlgn)	O(n^2)	O(nlgn)	不稳定	越乱效率越高，有序效率最差
堆排序	O(nlgn)	O(nlgn)	O(nlgn)	O(1)	不稳定	时间复杂度均为O(nlogn)
归并排序	O(nlgn)	O(nlgn)	O(nlgn)	O(n)	稳定	先分再合
基数排序	O(d(n+rd))	O(d(n+rd))	O(d(n+rd))	O(rd)	稳定	B是真数(0-9)， R是基数(个十百)

1、快速排序

基于分治的算法
越乱效率越好O(nlgn)，基本有序时效率最差O(n^2)。空间复杂度O(n)
取尾元素和取首元素算法过程基本类似，取中间元素运用了swap()互换

1、经典例题

2、归并排序

先分再合

1、经典例题

3、直接插入排序

将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

1、经典例题

4、其他排序

1、简单选择排序：每⼀趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列，n个元素的简单选择排序需要 n-1 趟处理。

2、堆排序：堆排序是一种选择排序，它的最坏最好，平均时间复杂度均为O(nlogn)，他也是不稳定排序。（大根堆、小根堆）

3、冒泡排序：左到右，相邻元素进行比较，每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

4、希尔排序：是对插入排序的优化。

5、基数排序：适合于序列中只有0-9的数字，统计每个数的个数