3064 字

15 分钟

数据结构笔记

2026-03-01

数据结构

全部笔记

/

考研

/

数据结构

数据结构#

1.绪论#

1. 数据结构的基本概念#

可以用==抽象数据类型==定义一个完整的数据结构
与数据存储结构无关的术语是==栈==， ==循环队列==是用顺序表表示的队列，是一种数据结构
==数据的逻辑结构独立于其存储结构==
在存储数据时，不仅要存储数据元素的值，还要存储==数据元素之间的关系==
链式存储设计时，节点内的存储单元地址==一定连续==

不同节点的存储单元地址可以不连续，节点内的存储单元地址必须连续

2. 算法和算法评价#

一个算法应该是==问题求解的步骤==
算法原地工作是指==算法所需的辅助空间是常量==

2. 线性表#

1. 线性表的顺序表示#

==存储密度大==是顺序存储结构的优点
线性表的顺序存储结构是一种==随机存取的存储结构==
==线性表的序号是从一开始==

2. 线性表的链式表示#

==链式存储结构比顺序存储结构能更方便的表示各种逻辑结构==
==静态链表需要分配较大的连续空间，插入和删除不需要移动元素==
单链表中，增加一个头结点的目的是方便运算的实现
==单链表中，删除最后一个元素与链表长度有关，其他操作均无关==
==在尾结点插入和删除数据，带头结点的双循环链表最节省时间==

3. 栈，队列和数组#

1. 栈#

栈和队列具有相同的==逻辑结构==
向一个栈顶指针为top的链栈（不带头结点）中插入一个X节点，则执行==x->next=top;top=x==
采用共享栈的好处是==节省存储空间，降低发生上溢的可能==

2. 栈和队列的应用#

栈在==括号应用，表达式求值，递归，进制转换，迷宫求解==等中有应用
队列在==层序遍历，bfs，缓冲区，页面替换算法等==中有应用

4. 串#

==简单的模式匹配算法时间复杂度为O(mn)，KMP算法的时间复杂度为O(m+n)==
KMP算法求next数组（重点），视频P36

5. 树与二叉树#

1. 树的基本概念#

树的路径长度是==从树根到每个节点的路径长度的总和==
树中所有节点的度数之和 = 树的所有分支 = 树的节点数目 - 1
设树中度为 i 的节点数为 ni

1
节点数 = 各个度的节点数之和 = 1 + 分支数
2
n=n0+n1+n2+n3 = 1+n1+2n2+3n3

2. 二叉树的概念#

非空二叉树上的叶子节点数等于度为2的节点数加1，即 ==n0= n2+1==
非空二叉树第k层上至多有 ==2^(k-1)== 个节点
高度为h的二叉树至多有 ==2^h -1== 个节点
在含有n个节点的二叉链表中，含有 ==n+1== 个空链域

3. 二叉树的遍历与线索二叉树#

在二叉树中，m是n的祖先，使用==后序遍历==可以找到 m 到 n的路径
在二叉树的前序，中序，后序遍历中，所有叶子节点的先后顺序==完全相同==
二叉树的先序和后序完全相反，二叉树一定满足==只有一个叶子节点==
==唯一不能确定一颗二叉树的是先序遍历和后序遍历==
线索二叉树是一种==物理结构==，==tag为0时指向孩子节点，为1时指向线索节点==
==二叉树在线索化后，仍不能有效求解后序线索二叉树求后序后继==
==后序线索树==遍历仍需要栈的支持

3. 树，森林#

将树转变成二叉树：==左孩子右兄弟==
将森林F转换为对应的二叉树T，F中叶节点的个数等于 ==T中左孩子指针为空的节点个数==

在一颗二叉树中，如果某个节点的左指针为NULL，就说明这个节点在原来的森林中没有孩子，是叶子节点

4. 树与二叉树的应用#

若没有编码是另一个编码的前缀，则称这样的编码为==前缀编码==
==在哈夫曼树中只有叶子结点才能作为字符编码==
对应一组权值构造出的哈夫曼树不是惟一的
哈夫曼树的度只有0和2，没有1
并查集的结构是一种 ==双亲表示法存储的树==
==并查集查找操作的时间复杂度为 O(n)==

6.图#

1. 图的基本概念#

图中有关路径的定义：==由顶点和相邻顶点序偶构成的边所形成的序列==
==无向图的全部顶点的度的和等于边数的两倍==
==强连通有向图至少有 n 条边==（构成环）

2. 图的存储及基本操作#

无向图的度为==邻接矩阵中第i行或第i列非零元素之和==
一个图的邻接矩阵表示唯一，邻接表表示不唯一
在有向图的邻接表存储结构中，顶点 v 在边表中出现的次数为 ==顶点v的入度==

解释：这里的边表不包含顶点表（即出度）

假设有n个顶点，e条边的有向表用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为==O(n+e)==
==十字链表是有向图的链式存储结构==
==邻接多重表是无向图的链式存储结构==

3. 图的遍历#

当各边的权值相等时，广度优先算法可以解决==单源最短路径问题==
==图的广搜使用队列，深搜使用栈==
==图的深搜相当于树的先序遍历==
判断有向图中是否存在回路，除了利用拓扑排序外，还可以利用 ==深度优先遍历，求关键路径==（求最短路径不行）
使用DFS算法递归的遍历一个有环无向图，在退出递归时输出相应顶点，这样得到的顶点序列是==逆拓扑有序==

4. 图的应用#

==只要无向连通图中没有权值相同的边，则其最小生成树唯一==、
==最短路径一定是简单路径==
若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图==含有顶点数大于1的强连通分量==
若一个有向图具有==有序==的拓扑排序序列，则它的邻接矩阵必定为 ==三角==
最小生成树代价唯一（形状可能不唯一）

7.查找#

1. 顺序查找和折半查找#

折半查找过程所对应的判定树是一棵==平衡二叉树==
折半查找和二叉排序树的时间性能==有时不相同==

二叉排序树的查找性能和数据的输入顺序有关，最坏情况形成单支树，查找长度为O(n)

对表长为n的有序表进行折半查找，判定树的高度为 ==log2(n+1)向上取整==

2. 树形查找#

平衡二叉树（AVL）左子树与右子树的高度差称为平衡因子（-1,0,1）
==节点数最少的平衡二叉树节点数的递推公式（重要）==

1
n1=1  n2=2
2
n3=n1+n2+1
3
...

AVL中所有非叶子节点的平衡因子均为1，说明它的叶子节点数最少
平衡树的查询效率一般优于红黑树
一棵含有n个节点的红黑树的高度至多为 ==2log(n+1)==
==红黑树任意节点的左右子树的高度之差不超过两倍==
==如果红黑树的所有节点都是黑色的，那么它一定是一棵满二叉树==

3. B树，B+树#

B+树不同于B树的特点之一是==能支持顺序查找==
B树和B+树都可以用于文件索引结构
B+树更加适用于实际应用中的==操作系统中的文件索引和数据库索引==

4. 散列表#

==散列表查找成功的平均查找长度与散列因子有关，与表长无关==
若在散列表中删除一个元素，不能简单地将该元素删除（在删除地方做删除标记）
==采用再散列法处理冲突时不易产生聚集==
==使用链地址法不会引起聚集现象==

8. 排序#

1. 排序的基本概念#

==排序算法的稳定性是指经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变==
拓扑排序不属于内部排序方法
==使用链表也可以进行排序，只不过有些排序算法不在适用==
==对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同==
对任意n个关键字排序的比较次数至少为 ==log2(n!) 向上取整==

2. 插入排序#

插入排序：直接插入排序，折半插入排序，希尔排序
对n个元素的顺序表进行直接插入排序算法，==最坏情况下所需的比较次数是n(n-1)/2 , 最好情况下是（n-1）==
与直接插入排序相比，折半插入排序减少了比较元素的次数，元素的移动次数并未改变

3.交换排序#

交换排序：冒泡排序，快速排序
==快速排序：当每次枢轴都把表等分位长度相近的两个子表时，速度是最快的；当表本身已经有序或者逆序时，速度最慢==
递归次数与每次划分后得到的分区的处理顺序无关
==快速排序的阶段性特点是：第 i 趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，右边的数都比它大==

4. 选择排序#

选择排序：简单选择排序，堆排序
==简单选择排序的比较次数和移动次数分别为O(n^2)，O(n)==
==通常，取一大堆数据中的K个最大（最小）元素时，都优先采用堆排序==
向具有n个元素的堆中插入一个元素的时间复杂度为 O(logn),删除一个元素的时间复杂度为 O(logn)
构建 n 个记录的初始堆，时间复杂度为 O(n) , 进行堆排序，最坏情况下，时间复杂度为 O(nlogn)

5. 归并排序和基数排序#

基数排序不需要进行关键字的比较
平均情况下空间复杂度为O(n)的是==归并排序==，最坏情况下空间复杂度为O(n)的是 ==归并排序，快速排序==
对10TB的数据文件进行排序，应使用的方法是==归并排序==

6.各个排序算法比较#

排序算法名称	时间复杂度	空间复杂度	稳定性	适用性
直接插入排序	O(n^2)	O(1)	稳定	顺序存储和链式存储
折半插入排序	O(n^2)		稳定	顺序存储
希尔排序	O(n^2)	O(1)	不稳定	顺序存储
冒泡排序	O(n^2)	O(1)	稳定	顺序存储
快速排序	O(nlogn)	O(logn)	不稳定	顺序存储
简单选择排序	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(n)	稳定
基数排序	O(d（n+r）)	O(r)	稳定