weixin_40725706

这个屌丝很懒，什么也没留下！

热门标签

【保研复习】数据结构复习笔记_保研数据结构

作者：weixin_40725706 | 2024-08-09 22:28:39

踩

保研数据结构

基于王道数据结构进行的保研面试复习

文章目录

数据结构绪论
一、线性表
二、栈、队列和数组
三、串
四、树
五、图
六、查找
七、排序
问题

数据结构绪论

数据结构

数据结构的三要素分别为：逻辑结构、存储结构、数据的运算

1. 逻辑结构

线性结构

线性表

栈

队列

非线性结构

树

图

集合（无序）

2. 存储结构

顺序存储

优点：可以实现随机存取

缺点：存储空间必须连续，可能产生外部碎片

链式存储

优点：不会产生外部碎片

缺点：每个节点要储存指向下一个节点的指针，指针会占用存储空间

索引存储

又称哈希存储

方法：设置索引表，索引表重存储关键字和对应节点的地址

优点：检索速度快

缺点：索引表会占用空间，每次增删的时候除了增删元素还要增删索引表表项

散列存储

方法：设置散列函数，直接根据关键字计算出应存放的地址

优点：检索速度快、增删也很快

缺点：如果散列函数设置不合理，会导致出现存储单元冲突，处理冲突会浪费大量时间

3. 数据的运算

施加在数据之上的运算的定义和实现。运算的定义是针对数据逻辑结构的，指出运算的功能；运算的实现是针对数据的存储结构的，指出运算的具体实现步骤。

算法

特点

有穷性：算法需要在有穷步骤、有穷时间内完成

确定性：算法指令含义明确，对于指定输入，其输出结果确定

可行性：算法描述的操作可以实现

输入

输出

效率度量

时间复杂度

最坏情况下所需时间的数量级

计算：
$O (T (n)) + O (G (n)) = O (ma x (T (n) + G (n)))$

$O (T (n)) * O (G (n)) = O (T (n) * G (n))$

常见循环的时间复杂度：

O(log₂n)

int i = 1;
while(i < n){
    i = i * 2;
}
1
2
3
4

O(n²)

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= i; j++)
        do-something;
1
2
3

如果有三层循环for(int k = 1; k <= j; k++)则为O(n³)

两个for循环嵌套，其时间复杂度相乘，两个for循环并列，其时间复杂度取max
利用递推公式求时间复杂度

空间复杂度

一、线性表

顺序存储

特点：存储空间连续，逻辑位序与物理位序相同

地址分配方式：

静态分配：在编译时即确定存储空间大小
动态分配：在运行时才确定存储空间大小

动态内存分配：

C语言：

int *data = malloc(sizeof(int) * init_size);
1

C++:

int *data = new int[init_size];
1

访问某位置元素：O(1)

在指定位置插入元素：O(n)

删除指定位置元素：O(n)

查找指定值元素：O(n)

链式存储

单链表

数据结构

struct list_node{
    int data; //数据域
    struct list_node *next;
};
1
2
3
4

头指针：是一个指针，类型是struct list_node *，指向链表的第一个节点

头结点：是一个结点，类型是struct list_node，有的链表会放置一个不存储数据信息的结点作为第一个结点，用于存储表长等信息

对于有头结点的链表，头指针指向头结点

建立链表

头插法（每次将结点插在最前面）

list_node *head;
int temp;
head = (list_node*)malloc(sizeof(list_node));
head->next = NULL;
scanf("%d", &x);
while(x != 9999){
    list_node *s;
    s->data = x;
    s->next = L->next;
    L->next = s;
    scanf("%d", &x);
}
1
2
3
4
5
6
7
8
9
10
11
12

尾插法

list_node *head;
int x;
scanf("%d", &x);
head = (list_node*)malloc(sizeof(list_node));
list_node *r = head;
while(x != 9999){
    list_node *s;
    s = (list_node*)malloc(sizeof(list_node));
    s->data = x;
    r->next = s;
    r = s;
    scanf("%d", &x);
}
r->next = NULL;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

增删改查

按序号查找：O(n)

按值查找：O(n)

插入元素：查找O(n)，插入O(1)

删除元素：查找O(n)，删除O(1)

双链表

每个结点存放其前序、后序结点的指针

struct list_node{
    int data;
    list_node *prior;  // 前一个结点
    list_node *next;   // 后一个结点
};
1
2
3
4
5

循环链表

循环单链表与单链表的区别在于，循环单链表的最后一个结点的next指向第一个结点

循环双链表与双链表的区别在于，循环单链表的最后一个结点的next指向第一个结点，循环单链表的第一个结点的prior指向最后一个结点

构成一个环

静态链表

静态链表借助数组实现。

typedef struct{
    int data;
    int next;  // 下一个元素的数组下标
}SLinkList[MaxSize];
1
2
3
4

反转链表的四种方法

借助栈，将链表元素逐个放入栈中，再取出
头插法：遍历链表中的每个元素，并采用头插法新建一个链表
就地反转：

遍历链表的每个元素，将该元素的next改为prev

遍历链表的每个元素{
    temp_next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = temp_next;
}
1
2
3
4
5
6

递归法

二、栈、队列和数组

栈

顺序栈：使用顺序存储的栈

typedef struct{
    int data[50];
    int top;   // 栈顶指针
}SqStack;
1
2
3
4

初始化：栈顶指针为-1

入栈：栈顶指针++，元素入栈

出栈：元素出栈，栈顶指针–

共享栈

两个顺序栈共用一个数据空间，栈A的栈底为0，元素入栈的操作为topA++；栈B的栈底为MaxSize-1，元素入栈的操作为topB–。当topA==topB时，说明栈满。

链栈：使用链式存储的栈

规定栈顶为链表的第一个结点，入栈时采用栈的头插法，出栈时弹出第一个结点

队列

栈和队列的逻辑结构是一样的，都是属于线性结构，其区别在于数据的运算不同

队列的顺序存储结构

只能从队尾入队，从队头出队

front指向队列队头的元素，rear指向队列的下一个元素

typedef struct{
    int data[50];
    int front, rear; // 队头和队尾指针
}SqQueue;
1
2
3
4

初始化：front=rear=0

进队：front不变，将元素放在rear处，rear++

出队：rear不变，将front处元素弹出，front++

循环队列

将队列想象为首尾相接

初始化：front=rear=0

入队：( rear + 1 ) % MaxSize

出队：( front + 1 ) % MaxSize

队列长度：( rear + MaxSize - front ) % MaxSize

当rear==front时无法判断是队空还是队满，可以增设一个代表队列长度的变量size，用以判断队空还是队满

队列的链式存储结构

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;  // 链表的结点结构体
typedef struct{
    LinkNode *front, *rear;  // 链式队列的队头和队尾指针
}LinkQueue;
1
2
3
4
5
6
7

初始化：设置一个头结点，front和rear都指向该结点

入队：front不变，头结点的next指向新结点，rear也指向该节点

出队：rear不变，存储front的next，并将front的next修改为front->next->next

双端队列

队列两端分别命名为前端和后端，两端都可以进行入队和出队

卡特兰公式？

栈的应用

栈与括号匹配

栈与表达式求值

矩阵压缩

压缩目的：对多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。

对称矩阵

所有元素都满足a_ij = a_ji

存储方式：只存储下三角区和对角线上的元素，将其按行存储在数组中。则矩阵第一行有一个元素需要存储，第二行有2个，第三行有3个……

对于下三角区或对角线上的元素a_ij，它的前面的元素个数为((i-1)×i)/2+j-1，故它在数组中的位置k等于该值

对于上三角区的元素a_ij，相当于a_ji，将i、j互换即可

上（下）三角矩阵

对于下三角矩阵，其上三角区全部为一个常量，将其存储在数组的(n×(n+1))/2位置，而其下三角区和对角线上元素与对称矩阵相同

对角矩阵

对角矩阵，只存储对角线上元素即可

三对角矩阵元素a_ij，其前面的元素个数为：

3 × (i - 1) - 1 + j - (i - 1)

每行3个元素（除了第一行只有两个之外），所以前i-1行元素个数为3 × (i - 1) - 1 ；

对于第i行，元素a_ij前面的元素个数为j - (i - 1)

故元素在压缩后的数组中的下标为2i + j - 3

稀疏矩阵

对于元素个数非常少的稀疏矩阵，其存储方式是存储一个三元组，记录非零元素的行、列和其值

三、串

串的存储结构

定长顺序存储
堆分配存储
块链存储

模式匹配算法KMP

算法原理：

命名：模式串为pattern、文本串为text、next表中next[i]存放的是该元素之前子串的最长公共前后缀

算法实现：当pattern的第j位与text的第i位匹配失败时，将pattern的j指针跳到next[j]处与第i位重新匹配

原因：因为next[j]存放的是pattern[0, j-1]部分的最长公共前后缀，已知pattern的[0, j-1]部分与text匹配，而pattern的前缀与自己的后缀相同，则pattern的前缀与text该部分的后缀匹配，因此无需再次比较，只需继续比较第next[j]位即可。

pattern各位最长公共前后缀的计算方法（构造法）TODO：

next[i]表示的是[0, i-1]子串的最长公共前后缀长度

计算pattern前后缀，i为前缀末尾，j为后缀末尾，当pattern[i] == pattern[j]时，i和j都++，next[j] = i

当pattern[i] != pattern[j]时，将i修改为next[i]继续和j处元素匹配。因为对于[0, j -1]的子串，其公共前后缀长度为next[j-1]，

则前缀[0, i-1]和后缀[j-1-i, j-1]完全相同，又因为前缀[0, i-1]本身也有公共前后缀，长度为next[i]，则前缀[0, i -1]的前缀[0, next[i] - 1]和后缀[j-1-i, j-1]的后缀[j-next[i], j-1]相同，不用重复比较，继续比较next[i]和j即可

例如：

a b a c a b a b

i = 2，j = 6时匹配，前后缀都为a b a

i = 3，j = 7时不匹配，此时通过next[3] = 1可知，前缀a b a和前缀pattern[0]=a与后缀a b a和后缀pattern[6]=a匹配，下一步比较next[3]=1和j=7是否匹配即可，不需要再比较0和6

四、树

概念

树的高度：树有几层

结点的度：该结点儿子的数量

树的度：树中结点最大度数

树的结点数=树的所有结点的度数之和+1

度大于0的结点（有儿子的结点）称为分支节点，度为0的结点（无儿子的结点）称为叶子节点

结点的深度：从根结点开始累加结点在第几层深的位置（从上往下）

结点的高度：从结点的叶子节点开始累加（从下往上）

有序树：树中结点各子树从左到右是有顺序的

无序树：无顺序

路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，路径长度是路径上经过的边的个数

（因为树中分支是有方向的，只能从父指向子，所以树种的路径是从上到下的，同一父亲的两个儿子之间不存在路径）

森林：多棵树

存储：顺序存储、链式存储

存储普通树的方法：

双亲表示法

每个节点存储当前节点的父亲节点在数组中的位置

struct node{
    int data;  // 当前节点的值
    int parent;  // 当前节点的父亲节点的下标
};
struct Tree{
    node node_list[MAX_N]; // 存储所有节点的数组
    int r; // 根的位置下标
    int n; // 结点数
};
1
2
3
4
5
6
7
8
9

孩子表示法

每个结点用一个链表存储当前节点的所有孩子是数组中的位置

struct child{   // 孩子链表的结点
    int position;
    struct child *next;
};
struct node{   // 树中的结点
    int data; // 当前节点的值
    struct child * first_child;
};
struct Tree{
    node node_list[MAX_N];
    int r;
    int n;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

孩子兄弟表示法

每个节点存储当前节点的第一个孩子和当前节点的下一个兄弟

struct node{
    int data;
    struct node *first_child, *next_brother;
};
1
2
3
4

二叉树

左右子树不能颠倒且树的度小于等于2

二叉树与度为2的有序树的区别：

二叉树度小于等于2，即二叉树可以为空，也可以度为1，而后者必须度为2，即至少有3个节点
有序树只有在有两个孩子的情况下才有孩子顺序的问题，一个孩子则无所谓顺序，而二叉树在只有一个孩子的时候也有左右之分

性质：

具有n个结点的非空二叉树共有n-1个分支
非空二叉树的第i层最多有2^i-1个节点
深度为h的二叉树最多有2^h-1个节点
非空二叉树有n0个叶节点，n2个度为2的节点，则n0=n2+1
具有n个节点的完全二叉树的高度为⌊log₂n+1⌋

二叉树的顺序存储：

将普通二叉树补充虚结点补成完全二叉树，然后逐行编号存放在线性表中

链式存储：

二叉链表：每个结点有lchild、rchild两个指针
三叉链表：每个结点有parent、lchild、rchild三个指针

完全二叉树的编号：

编号为i的节点的父节点为⌊n/2⌋
编号为i的左孩子编号为2i，如果2i>n说明该节点无左子树
编号为i的右孩子编号为2i+1，如果2i+1>n说明该节点无右子树

树、二叉树、森林之间的转换

普通树转二叉树
- 在所有兄弟节点之间加连线
- 除了长子之外其他儿子连线都删除
（这样转化出的二叉树没有右孩子）
森林转二叉树
- 首先将森林中每棵树都转为二叉树
- 从最后一棵树开始，将后面树的根结点作为前面树的右孩子
二叉树还原成普通树
- （这是什么绕口令没看懂

二叉树的遍历

前序、中序、后序（递归、栈）
层次遍历（队列）

递归前、中、后序：

void postOrder(TreeNodePoint root){
    if(root != NULL){
        visit(root);
        postOrder(root->lchild);
        postOrder(root->rchild);
    }
}
1
2
3
4
5
6
7

栈进行前中后序遍历：

中序：从根节点开始，一路将左孩子入栈，直到左孩子为空，然后开始从栈中弹出元素，访问弹出的元素，如果弹出元素的右孩子不为空，则将右孩子入栈，然后一路将其左孩子入栈，重复这一操作

void postOrderByStack(TreeNodePoint root){
    stack<TreeNodePoint> node_stack;
    TreeNodePoint temp = root;
    while(temp != NULL || !node_stack.empty()){
        if(temp != NULL){
            // temp不为空，一路将其左孩子入栈
            node_stack.push(temp->lchild);
            temp = temp->lchild;
        }
        else{
            temp = node_stack.top();
            node_stack.pop();
            visit(temp);
            temp = temp->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

前序：从根节点开始，一路访问左孩子，并将左孩子入栈，直到左孩子为空。从栈顶弹出元素，若其右节点不为空，则将右孩子入栈，然后一路将其左孩子入栈。与前序遍历的区别只在于访问节点在入栈前进行。
后序：

队列进行层次遍历：

思路：将根节点入队，然后出队，访问出队节点，将其左、右孩子分别入队，等本层遍历完后再将下一层节点依次出队，重复操作。

void levelOrder(TreeNodePoint root){
    queue<TreeNodePoint> node_queue;
    TreeNodePoint temp;
    node_queue.push(root);
    while(!node_queue.empty()){
        temp = node_queue.front();
        node_queue.pop();
        visit(temp);
        if(temp->lchild != NULL)
            node_queue.push(temp->lchild);
        if(temp->rchild != NULL)
            node_queue.push(temp->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

根据遍历序列恢复二叉树

前序/后序再加上一个中序即可恢复二叉树

前序+中序：

前序的第一个元素即为根节点，在中序序列中寻找这个根节点，即可区分左右子树

满二叉树

除最后一层外，其他每个节点度都为2，高为h的满二叉树节点个数为2^h-1

完全二叉树

除最后一层外都是满的，最后一层的节点集中于左侧

（注意最后一层和倒数第二层都有叶子节点，不只在最后一层）

线索二叉树

如果二叉树某节点左儿子指针空闲，将其用于存放前驱节点，右儿子指针空闲，将其用于存放后继节点。并设置左、右两个标志变量，用以标记其存放的是儿子节点还是线索。

线索二叉树有前序、中序、后序三种。此处以中序为例：

线索二叉树的建立：

对二叉树进行中序遍历，并在遍历时记录当前节点t的前一个结点prev
- 如果t的左指针为空，则t->lchild = prev, l_tag = 1
- 如果prev的右指针为空，则prev->rchild = t, r_tag = 1

线索二叉树的使用：

利用线索二叉树寻找节点x的后继
- 如果x的右子指针是线索，则其后继即为右子指针指向的节点；
- 如果x的右子指针是指针，则沿着x右儿子的左子树方向查找，直到找到一个左子指针是线索的节点，该节点即为x的直接后继

二叉排序树/搜索树/查找树

所有节点其左子树上的节点小于自己，右子树上的节点大于自己

对二叉排序树进行中序遍历，得到的是单调递增的序列

二叉排序树的建立：逐点找位置插入即可

二叉排序树的查找：递归或循环

平均查找长度ASL：所有节点查找所需比较次数的和

删除：

如果是叶节点，直接删除；
如果有一颗子树，将该节点删除后将子树连到父节点上
如果有两颗子树，则用左子树中最大的点或右子树中最小的点来代替该节点

哈夫曼树

每个叶子节点带权，带权路径长度WPL=sum(叶子节点权值*该叶节点深度)

使WPL最小的树为哈夫曼树

哈夫曼树的构造：

将所有节点视为一棵树，则所有树构成森林
在森林中选择两棵权值最小的树，分别将其作为左右子树，根节点权值为二者之和
将新树放入森林中，继续进行上述操作，直到森林中只有一棵树

这样得到的树可以保证权值大的叶子节点深度低，从而使得WPL最小

哈夫曼编码：

当编码长度不一致时，出现频率高的字符赋以短编码、出现频率低的字符赋以长编码，有利于缩短编码长度

前缀编码：没有任何一个字符的二进制编码是其他字符的前缀，这样不会造成误解，哈夫曼编码就是一种前缀编码

由哈夫曼树得到哈夫曼编码：

统计所有字符的出现频率作为其权值，根据这一权值构建哈夫曼树，左边为0、右边为1，得到最终编码。WPL即为最终编码长度。

五、图

图的相关概念

图G、顶点集V、边集E

相关概念
- 有向图、无向图：边是否有方向
- 简单图、多重图：简单图指不存在重复边、不存在顶点到自身的边的图
- 完全图：对于无向图，任意两个不相同的顶点之间都存在边；对于有向图，任意两个不相同的顶点之间都存在方向相反的两条弧
- 子图
  - V’是V的子集，E’是E的子集，则G’=(V’, E’)是G的子图
  - 生成子图：V=V’的子图
- 连通（无向图概念）
  - 连通：无向图中，若两个顶点之间有路径存在，则他们是连通的
  - 连通图：任意两点间都有路径存在的无向图是连通图
  - 连通分量：无向图的极大连通子图称为连通分量
- 强连通（有向图概念）
  - 强连通：有向图中，若两个顶点v、w之间，既存在v->w的路径，也存在w->v的路径，则他们是强连通的
  - 强连通图：任意两点都强连通的有向图称为强连通图（有n个顶点的强连通图最少有n条边，构成一个环路）
  - 强连通分量：有向图的极大强连通子图称为强连通分量
- 生成树
  - 生成树：对于连通图，生成树是包含图中全部顶点的极小连通子图，其边数为n-1（再减一条边不连通，再加一条边成回路）
  - 生成森林：对于非连通图，其所有连通分量的生成树构成生成森林
- 顶点的度TD、入度ID、出度OD
- 边的权和网/带权图：边上可以带权，带权的边称为网
- 稠密图、稀疏图：边很多的是稠密图、边很少的是稀疏图|E|<|V|*log|V|
- 回路/环：若n个点的图有大于n-1条边，则这个图一定有回路
- 简单路径、简单回路：顶点不重复

图的存储

邻接矩阵法

用一维数组存储V，用二维矩阵存储E

对于无权图，若<i, j>之间存在边，则E[i, j] = 1，否则E[i, j] = 0；（无向图应把E[i, j]和E[j, i]都赋为1）

对于有权图，若<i, j>之间存在边，则E[i, j] = 权值，否则E[i, j] = ∞；

对于无向图，第i行或第i列中非零元素的个数是顶点i的TD；对于有向图，第i行中非零元素的个数是顶点i的OD，第j列中非零元素的个数是顶点j的ID；
对于稠密图适用，对于稀疏图浪费空间

// 邻接矩阵
int data[MAX_V];             // 存点
int edge[MAX_V][MAX_V];      // 用矩阵存i, j之间是否有边

// 稀疏矩阵
typedef struct edge{
    int v1, int v2;
    int weight;
}Edge;
int data[MAX_V];  // 存点
Edge G[MAX_E];    // 存边
1
2
3
4
5
6
7
8
9
10
11

邻接表法

每个顶点v用一个单链表表示与该节点相连的边

typedef struct edge{
    int adjvex;  // 位置域（该边终点的位置）
    int weight;  // 权值域
    struct edge *next;
}Elink;   // 以某结点起始的边的链表中的一个
typedef struct ver{
    int vervex;
    Elink *first_link;
}Vlink;   // 结点结构体
Vlink G[MAX_V];
1
2
3
4
5
6
7
8
9
10

C++中可以用vector来存储

struct edge{
    int to;
    int weigth;
};
vector<edge> graph[MAX_V_NUM];  // graph[i]是一个vector，存储所有以i为起点的边
1
2
3
4
5

十字链表

对于顶点，其存放的信息包括：顶点信息data、以该顶点为弧头的第一个弧first_in、以该顶点为弧尾的第一个弧first_out

对于弧，其存放的信息包括：

尾域tailvex、头域headvex：分别指向本弧的弧尾和弧头两个顶点
hlink：指向与本弧弧头相同的下一条弧，tlink：指向与本弧弧尾相同的下一条弧
info：弧的相关信息

邻接多重表

针对无向图的链式存储结构

对于顶点，其存放的信息包括：顶点信息data，依附于该顶点的第一条边的指针firstedge

对于边，其存放的信息包括：标志域mark，ivex、jvex表示边依附的两个点，ilink、jlink表示下一条依附于ivex、jvex的边

图的遍历

广度优先搜索（邻接矩阵O(n²)，邻接表O(n+m)）

队列

typedef struct edge{
    int adjvex;
    int weight;
    struct edge *next;
}Elink;
typedef struct ver{
    int vervex;
    Elink *first;
}Vlink;
typedef struct graph{
    Vlink g[MAX_V_NUM];
    int v_num;
}Graph;
1
2
3
4
5
6
7
8
9
10
11
12
13

bool visited[MAX_V_NUM];
queue<int> Q;
void BFS_graph(Graph G){
    for(int i = 0; i < G.v_num; i++)
        visited[i] = false;
    for(int i = 0; i < G.v_num; i++)
        if(!visited[i])
            BFS_ver(G, i);
}
void BFS_ver(Graph G, int v){
    visit(v);
    visited[v] = true;
    Q.push(v);
    while(!Q.empty()){
        int temp = Q.front();
        Q.pop();
        for(Elink *i = G.g[temp].first; i != NULL; i = i -> next){
            visit(i->adjvex);
            visited[i->adjvex] = true;
            Q.push(i->adjvex);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

深度优先搜索（邻接矩阵O(n²)，邻接表O(n+m)）

递归或栈

bool visited[MAX_V_NUM];
void DFS_graph(Graph G){
    for(int i = 0; i < G.v_num; i++)
        visited[i] = false;
    for(int i = 0; i < G.v_num; i++)
        if(!visited[i])
            DFS_ver(G, i);
}
void DFS_ver(Graph G, int v){
    visit(v);
    visited[v] = true;
    for(Elink *i = G.g[v].first; i != NULL; i = i -> next){
        if(!visited[i->adjvex])
            DFS_ver(G, i->adjvex);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对于连通图，在BFS_graph()、DFS_graph()函数中调用一次BFS_ver()或DFS_ver()即可遍历完成，对于非连通图，调用BFS_ver()或DFS_ver()的次数即为其连通分量的个数。

图的算法

最短路算法

BFS（无权图的单源最短路）

BFS可以用于解决单源最短路问题，因为BFS遍历总是从近到远的。

方法是：

int distance[MAX_V_NUM];
bool visited[MAX_V_NUM];
queue<int> Q;
void BFS_ver(Graph G, int begin){
    for(int i = 0; i < G.v_num; i++){
        distance[i] = MAX_MUM;
        visited[i] = false;
    }
    distance[begin] = 0;
    visited[begin] = true;
    Q.push(begin);
    while(!Q.empty()){
        int temp = Q.front();
        Q.pop();
        for(Elink *i = G.g[temp].first; i != NULL; i = i->next){
            if(!visited[i->adjvex]){
                distance[i->adjvex] = distance[temp] + 1;
                visited[i->adjvex] = true;
                Q.push(i->adjvex);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Dijkstra算法（有权图的单源最短路）O(n²)

基于贪心策略

集合S：存储已经找到最短路径的结点，初始时将v0放入其中

集合T：V-S

dist[]：记录源点v0到其他所有点的最短距离，初始时将与v0直接连通的点写入

path[]：记录到v0的最短路径中的前驱节点

不优化：O(V²)

优先队列优化：O(ElogV)

算法：

初始时S中只包含v0，每次从T中选取一个距离v0最近的点u加入S中，并对与u相连的所有点进行松弛操作。

注意：Dijkstra算法的权值不能为负

struct Edge{
    int to;         // 边的终点
    int length;     // 边的长度
    Edge(int t, int l): to(t), length(l){}
};
struct Point{
    int number;     // 点的编号
    int distance;   // 点到源点的距离
    Point(int n, int d): number(n), distance(d){}
    bool operator< (const Point& p) const{
        return distance > p.distance;   // 距离小的优先级高
    }
};
vector<Edge> graph[MAX_V_NUM]; // 邻接表 graph[i]是一个存储所有与i相邻的
int distance[MAX_V_NUM];
int path[MAX_V_NUM];

void dijkstra(int s){
    priority_queue<point> priorityQ;
    dis[s] = 0;
    priorityQ.push(Point(s, dis[s]));
    while(!priorityQ.empty()){
        int u = priorityQ.top().number;
        priorityQ.pop();
        for(int i = 0; i < graph[u].size; i++){
            int v = graph[u][i].to;
            int d = graph[u][i].length;
            if(dis[v] > dis[u] + d){
                dis[v] = dis[u] + d;
                priorityQ.push(Point(v, dis[v]));
                path[v] = u;
            }
        }
    }
}

int main(){
    int n, m; // n为点的个数，m为边的个数
    scanf("%d %d", &n, &m);
    memset(graph, 0, sizeof(graph));
    fill(dis, dis+n+1, INT_MAX); // 编号从1到n+1
    while(m--){
        int from, to, length;
        scanf("%d %d %d", &from, &to, &length);
        graph[from].push_back(Edge(to, length));
        graph[to].push_back(Edge(from, length));
    }
    int s, t;  // 起点和终点
    Dijkstra(s);
    if(dis[t] == INF)
        dis[t] = -1;
    printf("%d\n", dis[t]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Floyd算法（有权图的多源最短路）O(n³)

k是中间结点，i、j是两边的结点。算法思路是，尝试在所有i、j之间加入中间结点k，看是否会得出更近的路径。遍历所有结点让其作为中间结点，并在确定k后遍历所有i、j。

const int max_n = 505;
int dis[max_n][max_n];

void Floyd(int n){
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

int main(){
    int n, m;
    int u, v;
    scanf("%d %d", &n, &m);
    fill(dis, dis + max_n * max_n, INT_MAX);
    for(int i = 0; i < m; i++){
        scanf("%d %d", &u, &v);
        scanf("%d", &dis[u][v]);
    }
    Floyd(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

并查集

并查集的处理对象：多个无交集的集合的合并和查询问题，要求将集合在逻辑上表示为树结构

并查集的两个功能：

判断两个元素是否在同一个集合中
按要求合并两个集合

查找：对于每个元素，不断向上查找，直到找到它的根，根据根是否相同来判断两个元素是否在同一个集合中

合并：将一棵树作为另一棵树的子树，从而将两棵树变成一棵更大的树

注意，是树合并的过程中如果不加约束，有可能导致树高越来越高，这样查找时就会面临不便，因此在合并时需要进行路径压缩

使用方法：一开始所有结点都单独成树（Initial函数），如果两个结点连通，就将两个结点Union，最后得到一个并查集

int father[MAX_N];    // 每个结点的父亲节点
int height[MAX_N];    // 以顶点x为根的树的高度

void Initial(int n){
    for(int i = 0; i <= n; i++){
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int x){
    if(x != father[x]){
        father[x] = Find(father[x]);  // 路径压缩过程，将该结点直接放入根节点的一级孩子中
    }
    return father[x];
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x != y){ // 如果传入的两个点不是一个集合中的
        // 矮树作为高树的子树
        if(height[x] < height[y]){
            // x并入y，x的父亲是y，由于y高度比x高，height[y]的高度并不会变
            father[x] = y;
        }
        else if(height[x] > height[y]){
            // y并入x，y的父亲是x，由于x高度比y高，height[x]的高度并不会变
            father[y] = x;
        }
        else{
            // y并入x，y的父亲是x，由于x、y一样高，y并入x后x的高度加一
            father[y] = x;
            height[x]++;
        }
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

最小生成树问题

生成树：包含所有顶点和n-1条边的子树，若加一条会导致回路，若减一条会导致不连通

最小生成树：边权值和最小的生成树

Prim算法（适使用稠密图）O(n²)

首先任取一个顶点加入S，然后每次选取一个与S中元素距离最近的点及边加入S中，最后得到最小生成树。

算法如下，其中priorityQ存的是所有T到所有S的点对及其距离，每次选一个T中最小的。priorityQ中的点可能重复，因为对于同一个点，它的距离是与多个S中的点之间的，只需在某一次作为最近的点被找出来即可。

struct Edge{
    int pos;
    int length;
    Edge(int p, int l): pos(p), length(l) {}
};
vector<Edge> graph[MAX_N];
struct Point{
    int to;
    int length;
    Point(int t, int l): to(t), length(l) {}
    bool operator< (const Point& p) const{
        return length > p.length;
    }
};
bool S[MAX_N];

int Prim(int n){
    int cost = 0, cnt = 0;
    priority_queue<Point> pointQ;
    pointQ.push(Point(1, 0));
    while(!pointQ.empty()){
        int u = pointQ.top().to;          // 22~28行：选取一个离S中点u最近的点加入S
        int d = pointQ.top().length;
        pointQ.pop();
        if(S[u]) continue;  // 如果该点已经被加入S了，只将其pop出去而不进行下面的操作
        S[u] = true;
        cnt++;
        cost += d;
        if(cnt == n) break; // 如果所有点都已经加入了S，结束算法
        for(int i = 0; i < graph[u].size(); i++){
            // 找到u后，将所有与u相连且不在S中的点加入优先队列，等待在以后的寻找中作为最近的点被加入S
            int v = graph[u][i].pos;
            int c = graph[u][i].length;
            if(S[v]) continue;
            priorityQ.push(Point(v, c));
        }
    }
    return total;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    while(m--){
        int a, int b, int d;
        scanf("%d %d %d", &a, &b, &d);
        graph[a].push_back(Edge(b, d));
        graph[b].push_back(Edge(a, d));
    }
    fill(S, S+n+1, false);
    printf("%d", Prim(n));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Kruskal算法（适用稀疏图）O(mlogm)

初始时S中包含所有的点，不包含任何一条边，每次选取一条权值最小的边，如果加入该边后S不含回路，则加入，如果含回路，则舍弃

struct Edge{
    int from;
    int to;
    int length;
    bool operator< (const Edge& e) const{
        return length < e.length;
    }
};

Edge edge_graph[MAX_N * MAX_N];
int father[MAX_N];
int height[MAX_N];   // height[x]存的是以结点x为根的树的高度

void Initial(int n){
    for(int i = 0; i <= n; i++){
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int x){
    if(x != father[x])
        father[x] = Find(father[x]);
    return father[x];
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(height[x] > height[y]){
        father[y] = x;
    }
    else if(height[x] < height[y]){
        father[x] = y;
    }
    else{
        father[y] = x;
        height[x]++;
    }
}

int Kruskal(int n, int m){
    Initial(n);
    sort(edge_graph, edge_graph + m); // 对所有边的长度进行排序
    int sum = 0;
    for(int i = 0; i < m; i++){
        Edge temp = edge_graph[i];
        if(Find(temp.from) != Find(temp.to)){  // 如果from和to目前不在同一个集合中，即不连通，则加入该边不会成环
            Union(temp.from, temp.to);
            sum += temp.length;
        }
    }
    return sum;
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        if(n == 0) break;
        int m = n * (n - 1) / 2;
        for(int i = 0; i < m; i++)
            scanf("%d %d %d", &edge_graph[i].from, &edge_graph[i].to, &edge_graph[i].length);
        printf("%d\n", Kruskal(n, m));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

拓扑排序

AOV网

DAG图：有向无环图

若用DAG图表示一个工程，用<V_i, V_j>表示V_i必须在V_j之前完成的这样一种关系，则称这种有向图为顶点表示活动的网络，即AOV网

拓扑排序：

从AOV网中选择一个没有前驱的顶点并输出
从网中删除该顶点和所有以它为起点的有向边
重复上述步骤直到网为空或网中不存在无前驱的顶点（后一种情况说明网中有环）

用拓扑排序来判断图是否有环（邻接矩阵O(n²)，邻接表O(n+m)）

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

vector<int> graph[MAX_N];  // 存储图，graph[i]是一个vector，存储所有i直接到达的顶点
int in_degree[MAX_N];   // degree[i]存储i的入度

bool TopologicalSort(int n){
    // 拓扑排序，如果有环返回True，否则返回False
    vector<int> topology;
    queue<int> node_in0; // 存储入度为0的结点
    for(int i = 1; i <= n; i++)
        if(in_degree[i] == 0)
            node_in0.push(i);
    // int remain_num = n;
    while(!node_in0.empty()){
        int temp = node_in0.front();
        node_in0.pop();
        topology.push_back(temp);
        // remain_num--;
        for(int i = 0; i < graph[temp].size(); i++){
            int v = graph[temp][i];
            inDegree[v]--;
            if(inDegree[v] == 0)
                node_in0.push(v);
        }
    }
    // return remain_num == 0;
    return topology.size() == n;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    memset(in_degree, 0, sizeof(in_degree));
    while(m--){
        int from, to;
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
        in_degree[to]++;
    }
    if(TopologicalSort(n))
        printf("有环\n");
    else
        printf("无环\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

AOE网与关键路径

以顶点表示事件，以有向边表示活动，以边上权值表示该活动持续的时间。

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。

每个活动的

最早开始时间：该活动的前序活动完成，该活动可以开始进行的时间
最晚开始时间：该活动的后序活动需按时完成，该活动必须开始的时间

非关键活动可以拖延，不会影响整个工程的完成。而关键活动的拖延会影响整个工程的完成。因此求关键路径可以转化为求所有活动的最早和最晚开始时间，判断二者是否相等。

计算方式是：通过拓扑排序找出活动的前序和后序活动，那么活动的最早开始时间就是其所有前序活动的最晚完成时间，活动的最晚开始时间就是其所有后序活动的最早开始时间减去该活动所需时间。

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

vector<int> graph[MAX_N];  // graph[i]存放结点i的后序结点
int inDegree[MAX_N];
long long earliest[MAX_N]; // 最早开始时间
long long latest[MAX_N];   // 最晚开始时间
long long time[MAX_N];     // 花费时间

long long CriticalPath(int n){
    vector<int> topology;  // 拓扑序列
    queue<int> node_in0;   // 存入度为0的点
    long long total_time = 0;
    for(int i = 1; i <= n; i++)
        if(inDegree[i] == 0)
            node_in0.push(i);
    while(!node_in0.empty()){
        int u = node_in0.front();
        topology.push_back(u);
        node_in0.pop();
        for(int i = 0; i < graph[u].size(); i++){
            // 遍历u的所有后序结点
            int v = graph[u][i];
            earliest[v] = max(earliest[v], earliest[u] + time[u]);
            inDegree[v]--;
            if(inDegree[v] == 0){
                node_in0.push(v);
                totalTime = max(totalTime, earliest[v] + time[v]);
            }
        }
    }
    for(int i = topology.size() - 1; i >= 0; i--){
        int u = topology[i];
        if(graph[u].size() == 0){
            // 如果u是最后的结点，在totalTime最后完成可以不耽误工期
            latest[u] = totalTime - time[u];
        }
        else{
            // 如果u不是最晚结点，将其初始化为INT_MAX
            latest[u] = INT_MAX;
        }
        // 遍历u的所有后序结点，寻找其中要求最早的
        for(int j = 0; j < graph[i].size(); j++){
            int v = graph[u][j];
            latest[u] = min(latest[u], latest[v] - time[u]);
        }
    }
    return totalTime;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    memset(inDegree, 0, sizeof(inDegree));
    memset(earliest, 0, sizeof(earliest));
    memset(latest, 0, sizeof(latest));
    for(int i = 1; i <= n; i++)
        scanf("%lld", &time[i]);
    while(m--){
        int from, to;  // from是to的前序结点
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
        inDegree[to]++;
    }
    long long total_time = CriticalPath(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

算法总结

算法	算法作用	时间复杂度	存储结构
BFS	深搜（可以用来解决无权图的单源最短路问题）	邻接矩阵O(n²)，邻接表O(n+m)	邻接表
DFS	广搜	邻接矩阵O(n²)，邻接表O(n+m)	邻接表
Dijkstra	有权图的单源最短路问题	O(n²)	邻接表
Floyd	有权图的多源最短路问题	O(n³)	邻接矩阵
Prim	稠密图的最小生成树	O(n²)	邻接表
Kruskal	稀疏图的最小生成树	O(mlogm)	边数组
AOV拓扑排序	判断有向图是否有环，对图中活动进行拓扑排序	邻接矩阵O(n²)，邻接表O(n+m)	邻接表
AOE	求带权有向图的关键路径		邻接表

六、查找

线性结构

顺序查找

二分查找

int arr[MAXN];
int BinarySearch(int n, int target){
    int left = 0;
    int right = n - 1;
    while(left <= right){
        int middle = left + (right - left) / 2;
        if(arr[middle] < target){
            left = middle + 1;
        }
        else if(arr[middle] > target){
            right = middle - 1;
        }
        else
            return middle;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分块查找

又称索引顺序查找。其基本思路是，将整个表分成几个块，每块选取一个代表值，将所有块的代表值与块的起始地址放在一起构建索引表。

ASL为索引查找的平均查找长度L_I和块内查找的长度L_S两部分构成。

若对索引表采用二分查找，还可以进一步加速。

树形结构

二叉排序树BST

左子树上所有结点小于根节点，右子树上所有节点大于根节点

BST的查找

BSTNode *BST_search(Tree T, int key){
    while(T != NULL && T->data != key){
        if(T->data > key) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}
1
2
3
4
5
6
7

BST的插入（递归）

bool BST_insert(Tree T, int k){
    if(T == NULL){
        T = (Tree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return True; // 插入成功
    }
    else if(k == T->data)
        return False; // 树中存在相同关键词，插入失败
    else if(k < T->data)
        return BST_insert(T->lchild, k);
    else if(k > T->data)
        return BST_insert(T->rchild, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

BST的构造

Tree create_BST(int arr[], int n){
    Tree T = NULL;
    for(int i = 0; i < n; i++){
        BST_insert(T, arr[i]);
    }
    return T;
}
1
2
3
4
5
6
7

BST的删除

如果该节点是叶子节点，直接删除
如果该节点左右子树有一个不为空，将不为空的子树提上来代替该节点
如果该节点左右子树都不为空，将该节点的直接前驱（或直接后继）单独提上来代替该节点，并将原来的直接前驱或后继删除

平衡二叉树

平衡因子：左右子树的高度差

平衡二叉树的平衡因子只能是-1、0或1

平衡二叉树的插入：

如果插入后导致二叉树不平衡，那么寻找最小不平衡二叉树，对其进行旋转操作：

LL旋转：在结点A的左孩子的左子树上插入了结点，左孩子变根
RR旋转：在结点A的右孩子的右子树上插入了结点，右孩子变根
LR旋转：在结点A的左孩子的右子树上插入了结点，左孩子的右孩子变根
RL旋转：在结点A的右孩子的左子树上插入了结点，右孩子的左孩子变根

平衡二叉树的删除：

按照二叉排序树的方式进行结点的删除
从删除位置向上回溯找出最小不平衡二叉树，进行调整

如果左孩子的左子树高度最高，进行LL旋转
如果右孩子的右子树高度最高，进行RR旋转
如果左孩子的右子树高度最高，进行LR旋转
如果右孩子的左子树高度最高，进行RL旋转

红黑树

B树、B+树

算法	时间复杂度	要求	ASL
顺序查找	O(n)	无特殊要求	查找成功的ASL是(n+1)/2，不成功是n+1
二分查找	O(logn)	要求表有序，且物理结构是可以随机存取的顺序存储	log₂(n+1)-1
分块查找		块内不要求有序，块之间要求有序
二叉排序树
平衡二叉树

七、排序

插入排序

将每一个待排序元素插入前面已经排好的元素序列中

直接插入排序

void insertSort(int[] arr, int n){
    for(int i = 2; i < n; i++){
        if(arr[i] < arr[i - 1]){
            for(int j = i - 1; j >= 0; j++){
                A[j + 1] = A[j];
                if(A[j] <= A[i]) break;
            }
            A[j + 1] = A[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

折半插入排序

void BinaryInsertSort(int[] arr, int n){
    int i, j, low, high, mid;
    for(int i = 2; i <= n; i++){
        low = 1;
        high = i - 1;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(arr[mid] > arr[i])
                high = mid - 1;
            else low = mid + 1;
        }
        // 插入high+1位置，从high+1到i-1统一后移一个位置
        for(int j = i - 1; j >= high + 1; j--){
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = arr[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

与直接插入排序相比，比较次数减少，但是后移操作导致时间复杂度仍然为O(n²)

希尔排序

先将待排序列表分为若干等长子表，对各子表进行直接插入排序，当所有子表完成排序后，整个表已呈“基本有序”，此时再对全体记录进行一次插入排序。

void ShellSort(int[] arr, int n){
    for(dk = n / 2; dk >= 1; dk = dk / 2){
        for(i = dk + 1; i <= n; i++){
            if(A[i] < A[i - dk]){
                for(j = i - dk; j >= 0 && A[i] < A[j]; j -= dk)
                    A[j + dk] = A[j];
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10

交换排序

冒泡排序

冒泡排序的基本思想是：第一趟排序时，从后往前两两比较相邻元素值，若为逆序则交换他们，最终结果是将最小的元素放在了序列最前面；第二趟排序时，比较范围是n-1到1，最终结果是将次小元素放在序列第二位；依次这样进行直到本轮遍历没有发生交换，说明表已经有序。

在冒泡排序中，关键字小的元素像气泡一样依次向上漂浮到水面上。

void BubbleSort(int[] arr, int n){
    bool flag;
    for(int i = 0; i < n; i++){
        flag = false; // 标识本轮遍历是否发生交换
        for(int j = n - 1; j > i; j-){
            if(arr[j] < arr[j - 1]){
                // 逆序
                swap(arr[j], arr[j - 1]);
                flag = true;
            }
        }
        if(flag == false) // 如果本轮遍历没有发生交换，说明表已经有序
            return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

快速排序

快速排序是基于分治法的排序，其思路是：首先选择一个元素，通过一趟排序找出比它小的所有元素[0, k-1]和比它大的元素[k, n-1]，则该元素应该放在arr[k]的位置。然后分别对左右两个序列再进行这个操作。

void QuickSort(int[] arr, int low, int high){
    if(low < high){
        int pivotpos = Partition(arr, low, high);  // 对表进行划分
        QuickSort(arr, low, pivotpos - 1);
        QuickSort(arr, pivotpos + 1, high);
    }
}
int Partition(int[] arr, int low, int high){
    int pivot = arr[low]; // 将序列第一个元素作为枢轴
    while(low < high){
        while(low < high && arr[high] >= pivot) high--; // 从后往前找到第一个比枢轴小的元素
        arr[low] = arr[high]; // 放在枢轴左边
        while(low < high && arr[low] <= pivot) low++; // 从前往后找到第一个比枢轴大的元素
        arr[high] = arr[low]; // 放在枢轴右边
    }
    A[low] = pivot;
    return low;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

选择排序

第i趟排序时，选择[i, n - 1]之间最小的元素与arr[i]交换，获得arr[i]位置应当存放的元素。直到i=n-1，排序完成。

简单选择排序

void SelectSort(int[] arr, int n){
    int min_pos;
    for(int i = 0; i < n - 1; i++){
        min_pos = i;
        for(int j = i + 1; j < n; j++)
            if(arr[j] < arr[min]) min = j;
        if(min != i)
            swap(arr[i], arr[min]);
    }
}
1
2
3
4
5
6
7
8
9
10

堆排序

大根堆：对于树及其中所有子树，最大元素放在根上

小根堆：对于树及其中所有子树，最小元素放在根上

堆排序的基本思路是：首先将序列构建为初始堆，输出堆顶元素（即最大值），然后将堆底元素送入堆顶，此时堆已经不符合大根堆要求，因此将堆顶元素向下调整，调整后再次输出堆顶元素，即第二大的值，如此重复进行。

构建初始大根堆：

首先按照层次构建一颗完全二叉树，然后从根节点[n / 2]的子树开始，一直到根节点为1的整棵树，逐步调整树（如果根节点是最大的，不需要再调整，否则将它较大的孩子拿上来作为根节点）。

堆排序：

将最大元素根节点输出，然后将最底层的叶节点提上来作为根节点，最后对堆进行调整，调整方法是，从上到下依次判断该节点是否大于它的两个孩子，如果不是，将其较大的孩子拿上来作为根节点。

堆插入：

插入元素时，先将该元素放在堆的末端，然后再对这个新的节点逐步向上调整。

堆排序适合在一亿个数中选取最大的一百个的情况，方法是：

取前一百个元素建立小顶堆，然后依次读入剩下的数，如果小于堆顶则舍弃，否则就用该数代替堆顶并调整堆，读入完成后堆中一百个元素即为所求。（如果一个数小于堆顶，那么它一定也小于堆中其他元素，那么它不可能是最大的前一百个）

归并排序

将一个表分为两个子表，分别排序后归并

// 调用
MergeSort(arr, 0, n - 1);
void MergeSort(int[] arr, int low, int high){
    if(low <= high){
        int mid = low + (high - low) / 2;
        MergeSort(arr, low, mid); // 对左侧子表进行递归
        MergeSort(arr, mid + 1, high);
        Merge(arr, low, mid, high);
    }
}

int *temp = (int*)malloc((n + 1) * sizeof(int)); // 辅助数组temp
void Merge(int[] arr, int low, int mid, int high){
    // 左子表是[low, mid]，右子表是[mid+1, high]
    for(int i = low; i <= high; i++)
        temp[i] = arr[i];
    int i, j, k;
    for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++){
        if(temp[i] <= temp[j])
            arr[k] = temp[i++];
        else
            arr[k] = temp[j++];
    }
    while(i <= mid) arr[k++] = temp[i++];
    while(j <= high) arr[k++] = temp[j++];
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

基数排序

排序算法	时间复杂度	空间复杂度	稳定性	适用的物理结构
直接插入排序	O(n²)	O(1)	稳定	适用顺序存储和链式存储
折半插入排序	O(n²)	O(1)	稳定
希尔排序	最好情况O(n^1.3)最坏情况O(n²)	O(1)	不稳定
冒泡排序	O(n²)	O(1)	稳定
快速排序	最好情况O(nlogn)最坏情况O(n²)	O(log₂n)	不稳定
简单选择排序	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(n)	稳定
基数排序		O(n+rd)

问题

数据结构的三要素：

逻辑结构（线性结构（线性表、栈、队列）、非线性结构（树、图））

存储结构（顺序存储、链式存储、索引存储、散列存储）

数据的运算
链表增加头结点的作用：便于对首结点的处理，便于空链表与非空链表的统一处理
顺序存储和链式存储：

顺序存储可以随机存取，按位置访问元素复杂度为O(1)，但插入、删除时需移动后面元素，复杂度为O(n)

链式存储按位置访问元素需要从头开始遍历，复杂度为O(n)，但一旦找到后插入、删除操作复杂度为O(1)
一个递归算法必须包含终止条件和递归部分
描述KMP算法的思路，以及next数组的计算方法 TODO
树的性质：
- m叉树第i层最多有m^i-1个结点
- 高度为h的m叉树最多有(m^h-1)/(m-1)个结点
- 具有n个节点的m叉树最小高度为⌈log_m(n(m-1)+1)⌉
二叉树的性质：
- 二叉树的第i层最多有2^i-1个元素
- 高为h的二叉树最多有2^h-1个元素
- 树中共有n₀个度为0的点，n₂个度为2的点，则n₀ = n₂ + 1
- 具有n个结点的完全二叉树，其高为⌈log₂(n+1)⌉
- 对完全二叉树编号：
  - 编号为i的结点的父节点为⌊i/2⌋
  - 编号为i的结点的左孩子为2i，右孩子为2i+1
  - 除编号为1的父节点外，奇数编号为右孩子，偶数编号为左孩子
  - 结点i所在的层次为⌊log₂i⌋+1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/955412

【保研复习】数据结构复习笔记_保研数据结构

文章目录

数据结构绪论

数据结构

1. 逻辑结构

线性结构

线性表

栈

队列

非线性结构

树

图

集合（无序）

2. 存储结构

顺序存储

链式存储

索引存储

散列存储

3. 数据的运算

算法

特点

效率度量

时间复杂度

空间复杂度

一、线性表

顺序存储

链式存储

单链表

数据结构

建立链表

增删改查

双链表

循环链表

静态链表

反转链表的四种方法

二、栈、队列和数组

栈

顺序栈：使用顺序存储的栈

共享栈

链栈：使用链式存储的栈

队列

队列的顺序存储结构

循环队列

队列的链式存储结构

双端队列

卡特兰公式？

栈的应用

栈与括号匹配

栈与表达式求值

矩阵压缩

对称矩阵

上（下）三角矩阵

对角矩阵

稀疏矩阵

三、串

串的存储结构

模式匹配算法KMP

算法原理：

pattern各位最长公共前后缀的计算方法（构造法）TODO：

四、树

概念

二叉树

树、二叉树、森林之间的转换

二叉树的遍历

根据遍历序列恢复二叉树

满二叉树

完全二叉树

线索二叉树

二叉排序树/搜索树/查找树

哈夫曼树

五、图

图的相关概念

图的存储

邻接矩阵法

邻接表法

十字链表

邻接多重表

图的遍历

广度优先搜索（邻接矩阵O(n2)，邻接表O(n+m)）

深度优先搜索（邻接矩阵O(n2)，邻接表O(n+m)）

广度优先搜索（邻接矩阵O(n²)，邻接表O(n+m)）

深度优先搜索（邻接矩阵O(n²)，邻接表O(n+m)）

Dijkstra算法（有权图的单源最短路）O(n²)

Floyd算法（有权图的多源最短路）O(n³)

Prim算法（适使用稠密图）O(n²)

用拓扑排序来判断图是否有环（邻接矩阵O(n²)，邻接表O(n+m)）