数据结构
基本概念
- 数据
- 数据元素：数据的基本单位
- 数据对象：相同数据元素的集合
- 数据类型
- 数据结构：逻辑结构、存储结构和数据的运算
ADT抽象数据类型描述了逻辑结构和抽象运算，从而构成一个完整的数据结构定义
注
数据的逻辑结构：线性结构和非线性结构
又可以分为：集合、线性结构、树形结构、图状结构
存储结构
顺序存储、链式存储、索引存储和散列存储
算法
- 有穷性：每一步有限时间完成，总也是有限时间
- 确定性：每条指令含义固定，相同输入一定相同输出
- 可行性：可以通过基本运算通过有限次执行实现
- 输入：0-多个输入
- 输出：1或多个输出
优秀的算法：正确、可读、健壮、高效率与低存储量需求
效率的度量
注
时间复杂度
0≤T(N)≤Cf(n)：若*T(n）和f(n)*是定义在正整数集合上的两个函数，则存在正常数C和n,满足该表达式。
最坏时间复杂度：最坏情况下，算法时间复杂度
平均时间复杂度：所有可能输入在等概率情况下，算法的期望运行时间复杂度
最好时间复杂度：与最坏类似。
空间复杂度
算法所需的存储空间。
线性表
有相同数据类型的n个数据元素的有限序列，其中n是表长。
顺序表拥有优点：可以随机访问，存储密度高。
缺点：插入与删除需要移动大量元素，需要分配连续的空间。
顺序表的操作
增：好:O(1)、坏O(n)、平均O(n)时间复杂度
删：与增相同
改：值查找的情况下与增删相同
链式存储
一般有数据域和指针域，避免了开闭大量连续空间的缺点，但是附加的指针域也浪费存储空间。
引入头节点的优点：首数据也被放到指针域里面，所以整个链上节点的操作方式一致，无论链表是否为空，其头指针都是指向头节点的非空指针，空表与非空表的处理也得到了统一。
静态链表：
用数组来描述线性表的链式存储结构，节点有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标)，也称为游标。静态链表也要预先分配一块连续的内存空间。
静态链表以next == -1作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。静态链表没有单链表使用起来方便。
链表常见的：
重要
头插法
// newnode head
newnode->next = head->next;
head->next = newnode;尾插
// newnode head
newnode->next = NULL;
node *tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = newnode;还有双指针、结合栈(逆置)、归并等方法
栈、队列、数组
栈
栈是只允许在一段进行插入或删除操作的线性表。注意，栈是一种线性表。
- InitStack
- StackEmpty
- Push
- Pop
- GetTop
- DestroyStack
当n个不同元素入栈时，出栈元素不同排列的个数是
卡特兰数的定义：
这个公式叫做卡特兰数公式。
栈的顺序存储结构
顺序栈，利用连续的存储单元存到从栈底到栈顶的数据元素，同时带一个top指针表示当前栈顶的位置。
栈空的判断就是依据top的值进行，栈满也是按照top的值进行判断。具体的判断条件依据栈本身的实现而有所不同。
共享栈
栈的链式存储结构
采用链式存储的栈，便于多个栈共享存储空间和提高效率，不存在栈满上溢的情况。对于具有头节点和不带有头节点的链栈，具体实现会有所区别。
队列
队列也是一种操作受限的线性表，只能在一端对表进行插入，而在另一端删除。FIFO
采用循环队列的方式解决假溢出的问题，将表看作逻辑上的还，当队首指针=最大容量-1，再插入以为就会到0。
判空条件，首尾指针相等，判满条件，尾指针 + 1 % 最大容量 (前提是队列的实现方式是牺牲了一个单元)
输出受限的双端队列：允许在一端进行插入和删除，但是另一端只允许插入的双端队列。
输入受限的双端队列：允许一端插入删除，但是另一端只允许删除的双端队列。
栈的一些使用
在算术表达式中的应用：
中缀表达式转换后缀表达式：
- 操作数，直接加入后缀表达式
- 界限符，左括号入栈，右括号，弹出运算符并计入后缀表达式，直到左括号
- 遇到运算符，如果高于栈顶运算符或者栈顶是左括号，直接入栈，若其优先级低于或等于栈顶运算符，弹出战中的运算符并加入后缀表达式，直到遇到低优先级或遇到左括号或者栈空，就可以把运算符入栈
后缀表达式计算：
从左到右进行扫描遇到操作数入栈然后，遇到操作符取出两个操作数计算然后再入栈。
数组与矩阵
特殊矩阵的压缩存储
多个值相同的元素只分配一个存储空间，对零元素不分配空间
特殊矩阵：指具有相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律的矩阵。
特殊矩阵的压缩储存方法：找出特殊矩阵中相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个存储空间中。
对称矩阵、三角矩阵、上三角矩阵、三对角矩阵、稀疏矩阵等的矩阵压缩关系，都采用行优先的顺序存储。
//三对角矩阵压缩存储的下标对应关系
k = 2 * i + j -3;// 求压缩矩阵下标
i = [(k+1)/3+1]; j =k - 2*i +3;
//稀疏矩阵：矩阵中非零个数t, 相对矩阵元素个数s来说非常少，叫做稀疏矩阵，因此稀疏矩阵采用三元组的方式进行存储，保存信息包括（行、列、值）串
int i =0, j =0;
while(i <= s.len() && j <m.len()) {
if (s[i] == m[j]) {
++i;
++j;
} else {
i = i - j + 1;
j = 0;
}
if (j > = m.len()) {
return true;
} else {
return false;
}
}KMP算法
ababa
//a
//ab
//aba
//abab
//ababa
//依次计算出其前缀以及后缀从而算出其最长相等前后缀长度
//在匹配的过程中发现主串和子串不匹配的情况，那么就查看上一个匹配的字符，并且查看模式串匹配表按照
//右滑 = 匹配个数 - 对应的部分匹配值
//关键在于next[j]的数值，意味着失效时候模式串需要跳转的位置
//对于模式串s
void get_next(char *str, int* next)
{
next [1] = 0;
int i = 1, j = 0;
while(i < str.len()) {\
if (j == 0 || str[i] == str[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
//nextval
void getnextval(char *str, int *nextval)
{
int i = 1;
int j = 0;
while(i < str.len()) {
if (j ==0 || str[i] == str[j]) {
++i;
++j;
if (str[i] != str[j]) {
nextval[i] = j;
} else {
nextval[i] = nextval[j];
}
} else {
j = nextval[j];
}
}
}树和二叉树
树一种递归的数据结构，同时也是一种分层结构，在n个结点的树中，有N-1条边。
结点的层次：从树根开始，以树根为1.
结点的深度：结点所在的层次
树的高度：树中结点的最大层数
结点的高度：以该节点为根节点的子树的高度。
结点的度：一个结点的孩子个数叫做结点的度
树的度：树中结点最大的度叫做树的度。
分支结点：度大于0的结点
叶结点：度为0的结点
有序树：结点个子树从左到右是有序的
无序树：非有序树
路径：两个结点之间的路径就是结点之间所经过的结点序列构成
路径长度：路径上的边的个数
树的一些性质
树的结点数 = 所有结点的度数和 +1
度为m的树中第i层上至多有mi-1 个结点
高度为h的m叉树最多有(mh -1)(m-1)个结点
度为m,具有n个结点的树的最小高度h为[logm(n(m+1) + 1)]
度是m,具有n个结点的最大高度n-m +1
总结点数 = 总分支数 + 1
总分支数 = 1*n1+2 * n2 …..+n * nn
二叉树
二叉树和度为2的有序树的区别
度为2的树至少三个结点，二叉树可以是空。
度为2的有序树的孩子的左右次序是相对于另一个孩子而言，二叉树的结点次序不是相对于另一结点而言的。
满二叉树
二叉树的每层都有最多结点
完全二叉树
h-1层的所有结点是满的，h层从左到右依次排好
二叉排序树
左子树所有结点的值小于根节点的值，右子树所有结点的关键字大于根节点的值。
平衡二叉树
树中任意一个结点的左子树和右子树的高差不超过一
正则二叉树
树的每个分支结点都有两个孩子，也就是说树的度只有0 或 2 的结点
非空二叉树的叶结点数等于度为2的结点数加一，即 n0=n2+1
非空二叉树的第k层最多有2k-1个结点
高度为h的二叉树最多有2h-1个结点
对完全二叉树从上到下，从左到右的顺序依次编号1,2…n则有以下关系：
1️⃣：最后一个分支结点编号为【n/2】，则结点i为分支结点，否则为叶结点。
2️⃣：叶结点只可能在最后两层出现(相当于在相同高度的满二叉树最底层，最右边减少一些连续叶结点)
3️⃣：若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子
4️⃣：按层序编号后，一旦出现某结点（如编号 i）为叶结点或只有左孩子的情况，则编号大于i的结点均为叶结点
5️⃣：若n为奇数，则每个分支结点都有左、右孩子；若n为偶数，则编号最大的分支结点只有左孩子没有右孩子
6️⃣：当i > 1时，结点i的双亲结点的编号为[i/2]
7️⃣：当结点i有左、右孩子，则左孩子编号2i，右孩子编号为2i+1
8️⃣：结点i所在层次为[log2n] + 1
顺序存储结构
对于一般二叉树要用数组存储，需要传入空节点进行占位。
链式存储
链式存储包括数值域以及指针域
在n个结点个二叉链表中有n +1 个空链域
二叉树遍历以及线索二叉树
先序、中序、后序遍历：关键在于根节点的遍历次序
层次遍历：按照从左到右，每层处理完成之后再处理余下层的遍历方法
如果知道中序遍历再知道其他三种遍历方式的任何一种就可以唯一确定一个二叉树。
有先序和中序确定二叉树
由先序的第一个一定是根节点，然后去中序里面找，找到之后将中序分割，在先序找到长度相等的子序列。通过递归的方式一次处理下去就可以构造出整个二叉树。
后序和中序构造二叉树
同样的方式，后序的最后一个一定是根节点，通过相同的方式去分割中序，然后采用递归的方式进行处理。
层次遍历和中序构造二叉树
采用层次遍历的第一个节点一定是根节点，这样就将中序序列分割。如果存在左子树，那个层序遍历的第二个节点一定是左子树的根节点，进一步可以划分左子树。
线索二叉树
若没有左树，那么起左节点指向前驱节点，如果没有右树，那么其有节点指向其后驱节点，此外添加两个标志域来表示指针域指向的是左右还是前后驱节点
后序线索二叉树中的线索的指向
在后序线索二叉树中找节点的后继较为复杂，可分为三种：若节点x是二叉树的根节点，那么后继是空的，如果节点x是双亲的右孩子，或者是双亲的左孩子且双亲没有右子树，那么后继就是双亲。如果节点是双亲的左孩子，且双亲有右子树，那么后继是双亲的右子树按后序遍历列出的第一个节点。
在后序线索二叉树中，必须要知道其结点双亲，才能找到后继。
树、森林
树可以采用顺序存储也可以采用链式存储。
- 双亲表示法
采用连续空间存储每个结点，同时在每个结点总增设一个伪指针，指示其双亲节点在数组中的位置。例如根结点下标0，伪指针域-1
image-20250813215226622 指针指示的是其双亲的节点号
- 孩子表示法
将每个结点的孩子节点当做一个线性表，以单链表形式存储，n个结点就有n个孩子链表
image-20250813215920884
- 孩子兄弟表示法
结点有几部分内容：结点值、指向节点第一个孩子结点的指针以及指向下一个兄弟节结点的指针。
树等的转换
树转二叉树
每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。
左孩子右兄弟规则，得到的二叉树是没有右子树的。
将右边的节点和自己连接上，然后将所有结点的除第一个子节点以外的连线全部删除，挂号之后进行旋转。
森林转二叉树
将森林里面每棵树按照树转二叉树先转换成二叉树再合起来
每棵树的根看作兄弟关系，在每棵树的根之间加一个连线，以第一颗树的根为轴心瞬时针旋转45°。
二叉树转森林
若二叉树非空，二叉树的根以及其左子树的第一颗树的二叉树形式，将根的右链断开，二叉树根的右子树可以看作一颗新的二叉树依次递推下去。
树和森林的遍历
树的遍历主要有两种方式：
1、先根遍历，如果不空就按照先根，再一次遍历节点的每颗子树，遍历子树时仍遵循先根后子树的规则
2、后根遍历，若树非空，按照以下顺序：先依次遍历根节点的每颗子树，遍历子树时仍遵循先子树后根。
森林的遍历：也是有两种方法
1、先遍历森林
访问第一棵树的根节点，先序遍历第一颗树中根节点的子树森林
先序遍历除去第一颗树之后剩余的树构成的森林
2、中序遍历森林
中序遍历森林中第一棵树的根节点的子树森林
访问第一棵树的根节点
中序遍历出去第一颗树后剩余的树构成的森林
森林雨二叉树遍历方法的对应关系
当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，森林的先序遍历和中序遍历对应的是二叉树的先序以及中序遍历。
树和二叉树的应用
哈夫曼树以及哈夫曼编码
树中结点的值，称为结点的权。
从树的根到一个结点的路径长度与该结点上的权值的乘积，叫做结点的带权路径长度。
树所有结点的带权路径长度之和叫做树的带权路径长度。
再n个带权叶结点的二叉树中，其中权路径长度(WPL)最小的树就叫做哈夫曼树，也叫最优二叉树。
给定n个权值的结点，构造哈夫曼树的算法描述：
将N个结点分别作为n颗仅含有一个结点的二叉树，构成森林。
构造出一个新结点，从F中选取两颗结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左、右子树根结点权值之和。
从F中删除刚刚选出的两棵树，并将刚刚构造出来的新树，添加到F里面去。
一直重复上述步骤知道只剩下一棵树。
哈夫曼树具有以下特点：
每个初始结点都称为叶结点，且权值越小的结点到根节点的路径越长。
构造过程中一共创建了n-1个结点，因此哈夫曼树的结点总数为2n-1.
每次构造都选择了两颗子树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
哈夫曼编码
若没有一个编码是另一个编码的前缀，这样的编码为前缀编码
并查集
并查集支持是那种操作
1、Initial:将集合s中的每个元素都初始化为只有一个单元素的子集合
2、Union(S, Root1, Root2):将集合s中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。
3、Find(S,x):查找集合S中单元素x所在的子结合，并返回该子集合的根节点。
并查集的存储结构
通常用树的双亲表示作为并查集的存储结构，每个子集合用一棵树表示。所有表示子集合的书，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根节点的下标代表子集合名，根节点的双亲域为负数。
//并查集初始化
void initial(int *s)
{
for(int i = 0; i < size; ++i) {
s[i] = -1;
}
}
//并查集的find操作
int find(int *s, intx) {
while(s[x] >= 0) {
x = s[x];
}
return x;
}
//并查集的Union操作
void Union(int *s, int rtool, int rtool2) {
if (rtool == rtool2) {
s[rtool2] = rtool;
}
}
//并查集优化,在union之前，首先判别子集的成员数量，然后令成员少的根指向成员多的根。
void union(int *s, int rtool, int rtool2)
{
if (rtool == rtool2) return;
if (s[rtool2] > s[rtool]) {
s[rtool] +=s[rtool2]; //说明结点树的结点总数
s[rtool2] = root1;
} else {
s[rtool2] += s[rtool];
s[rtool] = rtool2;
}
}
//find优化，当进一步减少确定元素所在集合时间，可以对find进行优化，当所查元素x不在树的第二层时，增加压缩路径功能。
int find(int *s, int x) {
int root = x;
while(s[root] >= 0) {
root = s[root];
}
while(x != root) {
int t = s[x];
s[x] = root;
x = t;
}
return root;
}
#include <stdio.h>
#define N 10 // 假设我们有数字 0~9
// 父节点数组，初始时每个节点的父节点是自己
int parent[N];
// 秩数组（记录树的深度），用于按秩合并优化
int rank[N];
// 初始化并查集
void init() {
for (int i = 0; i < N; i++) {
parent[i] = i; // 每个节点的父节点是自己
rank[i] = 0; // 初始秩为0（树的高度为1）
}
}
// 查找根节点（带路径压缩优化）
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩：让x直接指向根节点
}
return parent[x];
}
// 合并两个集合（按秩合并优化）
void union_sets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return; // 已经在同一个集合，无需合并
}
// 按秩合并：小树合并到大树
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
// 如果秩相同，合并后秩+1
parent[rootY] = rootX;
rank[rootX]++;
}
}
// 打印并查集状态（用于调试）
void print_sets() {
printf("Parent array: ");
for (int i = 0; i < N; i++) {
printf("%d ", parent[i]);
}
printf("\n");
printf("Rank array: ");
for (int i = 0; i < N; i++) {
printf("%d ", rank[i]);
}
printf("\n");
}
int main() {
init(); // 初始化并查集
// 示例：合并一些集合
union_sets(0, 1); // 合并 0 和 1
union_sets(2, 3); // 合并 2 和 3
union_sets(4, 5); // 合并 4 和 5
union_sets(6, 7); // 合并 6 和 7
union_sets(8, 9); // 合并 8 和 9
union_sets(1, 2); // 合并 1 和 2（间接合并 0,1,2,3）
print_sets();
// 测试查找
printf("Find(0) = %d\n", find(0)); // 应该返回根节点（可能是 0 或 2）
printf("Find(3) = %d\n", find(3)); // 应该和 Find(0) 相同
printf("Find(4) = %d\n", find(4)); // 应该是 4 或 5 的根
printf("Find(9) = %d\n", find(9)); // 应该是 8 或 9 的根
return 0;
}图
图的基本概念
图G是由顶点集V和边集E组成。图的顶点集一定是非空，图的边集可以是空。
- 有向图
若E是有向边的有限集合，则图G为有向图，弧是顶点的有序对，<v.w>其中v,w是顶点，v叫做弧尾，w叫做弧头，<v,w>称为v到w的弧，也称v邻接到w。
- 无向图
E是无向边的有限集合，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)。
- 简单图、多重图
一个图G若满足：不存在重复边，不存在顶点到自身的边，则称为图G为简单图。
若某个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，称为多重图。
无向图全部顶点的度之和等于边数的2倍。
有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，出度是以顶点v为起点的有向边的数目。
路径上的边的数目称为路径长度，第一个顶点和最后一个顶点相同的路径叫做回路或环。
距离 顶点之间的最短距离，从u 到 v不存在路径，那么距离就是无穷。
子图
连通、连通图和连通分量
如果顶点和顶点之间有路径存在，就说明是连通的。如果图中任何两个顶点是连通的就叫做联通图。否则就是非连通图，无向图的极大连通子图叫做连通分量，无向图可以分成两种连通的无向图、不连通的无向图，连通的无向图只有一个极大连通子图，不连通的无向图可以拆分为若干连通的无向图。若再多包含一个点或边变成不连通，叫做极大连通子图。
极小连通子图值存在于连通的无向图中，也就是说图只有一个连通分量。极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边，也就是说如果极小连通子图任意两个顶点间加入一条边，必有环。
强连通，有向图互相指向。
强连通分量，图里面任何一个顶点都是强连通的就是强连通分量。
生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。生成树砍掉一条边，就会变成非连通图，如果加上一条边就会形成一个回路。
边的权、网和带权路径长度：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值，带权的图就是带权图，也叫网。
完全图：对于无向图，有n(n-1)/2条边的无向图就叫做完全图，在完全图的任意两个顶点之间都存在边。有向图中，n(n-1)条弧的有向图叫做有向完全图。
稠密图、洗漱图：边数很少的图叫做稀疏图，反正就是稠密图
有向树：一个顶点的入度为0，其余顶点的入度为1的有向图叫做有向树
图的存储以及基本操作
邻接矩阵法
采用A[I][J]如果=1说明这两个顶点是连通的，为0就说明不连通。
对于带权的图而言，如果顶点v和v之间有边相连，则邻接矩阵中对应存放着该边对应的权值，也即A[i][j]=权值
该方法具有以下特点：
无向图的邻接矩阵一定是一个对称矩阵并且唯一，因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素
对于无向图，邻接矩阵的第i行非零元素的个数正好是顶点I的度。
对于有向图，邻接矩阵的第i行非零元素的个数正好是顶点i的出度，第i列非零元素正好是顶点i的入度1.
用邻接矩阵存储图，很容易确定顶点之间的相连关系，但是要确定图中有多少边，必须按照行、按照列进行遍历。
稠密图适合采用邻接矩阵的方法进行表示
图的邻接矩阵AN元素
A^N^[i][j]等于从顶点i到顶点j的长度为n的路径的数目。
邻接表法
当一个图为稀疏图额是偶，使用邻接矩阵将浪费大量空间，使用图的邻居表结合了顺存存储和链式存储方法，减少了空间的浪费。
先创建一个顶点表，每个顶点建立一个单链表，单链表的结点表示的是依附于顶点v的边，对于有向图就是指的是从当前顶点出去的弧。
typedef struct arcnode{
struct arcnode *next;
int p_data;
}
typedef struct {
int top_data;
struct arcnode *next;
}NODE_LIST[NODE_NUM];
struct neighber_table{
NODE_LIST table;
int vexnum, arcnum;
}graph;在无向图需要的空间是V + 2E,若G是有向图需要空间是V + E