# data_structure **Repository Path**: chenmingyanghhxx/data_structure ## Basic Information - **Project Name**: data_structure - **Description**: 王道数据结构习题代码 提供解析，欢迎勘误 联系方式：cmyhhxx@gmail.com qq: 2644287459 - **Primary Language**: C++ - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2022-06-23 - **Last Updated**: 2022-12-07 ## Categories & Tags **Categories**: Uncategorized **Tags**: 考研 ## README # 王道数据结构习题 ## 环境准备 因为dev-c++ 调试功能较差，所以这里选择vscode作为开发环境。 主要需要完成如下配置： 1. mingw64安装，配置环境变量 2. cmake安装，配置环境变量 3. vscode安装，插件安装 --- 对于mingw64和cmake，可以去官网下载，我这里提供下载好的软件。解压，放在c盘ProgramFiles目录下，配置环境变量即可。 vscode需要安装的插件如下： ![image-20220622224159008](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220622224159008.png) 至此，基础环境已经配置好，可以开始写代码了。 ## 线性表--顺序表 在main函数上方，有每个代码的题目解释，具体的函数实现我统一放在了下方。按ctrl + 函数名即可跳转查看。 ![image-20220623212822311](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220623212822311.png) 重点： 1. 归并思想 3. 删除节点 4. 翻转 ### 归并 习题7、11、14都是归并的思想。其实二路归并就是双指针，多路归并就是多路指针。后面排序会讲归并排序，这里主要演示一下大致思路： 1. 双指针指，小的拿下来，并向后移动一位 2. 退出循环时，一定是一个数组走完了，故进行"扫尾"工作 ![image-20220623220054645](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220623220054645.png) ### 删除 顺序表的删除要进行移位，注意**从后往前**移元素的覆盖。从前往后会丢失数据。 顺序表的删除我认为有个通法，设置一个计数器k，扫描一遍顺序表，合法的值重新放入，待删除的值不管。最后长度等于 k。这样做有几个优点： 1. 保序 2. 不存在移动顺序表 > 如果您发现了这里面不严谨的地方，麻烦您务必发一份勘误给我。 ### 翻转 翻转就按照王道给的记比较好，因为形式对称。注意这里下标从0开始。 ```c void reverse(SqList &L, int start, int end) { int mid = (start + end) / 2; // 逆置取中点（下取整），交换首尾即可，王道的这个写法比较推荐，不容易错 for (int i = 0; i <= mid - start; i ++ ) swap(L.data[start + i], L.data[end - i]); } ``` ## 线性表--链表 主要分为： 1. 单链表：带头结点、不带头结点、循环、非循环 2. 双链表：带头结点、不带头结点、循环、非循环 3. 静态链表(数组)：在上机题里一般用静态链表 ### T1 链表递归删除 ```c void del_x_recursively(LinkList &L, int x) { LinkList node; if (L == nullptr) return; // 递归出口条件 if (L->data == x) { node = L; L = L->next; // 思考为何这里不会断链，readme里有解释 free(node); del_x_recursively(L, x); } else del_x_recursively(L->next, x); } ``` ![image-20220627201235393](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220627201235393.png) 为何没有断链的原因就在图中，如果能自己调试建议自己调试，调试的时候注意看两个地方，一个是**上方变量的地址**，一个是**下方调用的堆栈**。实际上，比如单链表```5 4 3 2 1```删除值为1的元素。在执行```L = L->next```时，修改的是0x10401a70这个地址，这个地址本就是值为2的结点的next指针域，修改了这个指针值就相当于将2指向了```L->next```，这里是null。故递归删除虽然看起来像断链，但实则没有。 ### T6 链表的插入排序 少解释 ```c void sort_linklist(LinkList &L) { LinkList p = L->next, pre, rear = p->next; p->next = nullptr; p = rear; while (p) { rear = p->next; //每次都要保存后继 pre = L; // 每次从头找 while (pre->next->data < p->data && pre->next) { pre = pre->next; // 如果满足当前前驱后面的元素比插入的值要小，就说明这个前驱后面的元素要被更新作为新的前驱 } p->next = pre->next; // 把当前值插入到前驱后面 pre->next = p; p = rear; } } ``` ### T8 两个链表的公共结点 少一张图 ```c LinkList find_common_node(LinkList &L1, LinkList &L2) { LinkList p1 = L1->next, p2 = L2->next; while (p1 != p2) { if (p1) p1 = p1->next; else p1 = L2; if (p2) p2 = p2->next; else p2 = L1; } return p1; } ``` ### T17 判断循环双链表是否对称 少图 ```c bool is_symmetry(DLinkList &L) { DLinkList p = L->next; DLinkList q = L->pre; while (p != q && p->next != q) { if (p->data == q->data) { p = p->next; q = q->pre; } else return false; } return true; } ``` ### T21 判断单链表是否有环 少证明 ```c bool has_loop(LinkList &L) { LinkList slow = L, fast = L; while (slow && fast) { slow = slow->next; fast = fast->next; if (fast) fast = fast->next; // 每次走两步 else return false; // 快指针走到null，说明没有环 if (slow == fast) // 慢指针和快指针在环中相遇 { slow = L; // 慢指针后移至起点 while (slow != fast) { slow = slow->next; fast = fast->next; } return true; // 环的入口就是slow或者fast } } return false; } ``` ### T25 重排链表 少图 ```c void rearrange_linklist(LinkList &L) { int len = 0; for (LinkList p = L->next; p; p = p->next) len ++; // 求得链表长度 int left = (len + 1) >> 1; // 找到分割的左端点 LinkList end1 = L->next; // end1代表第一个链表的尾结点 for (int i = 0; i < left - 1; i ++ ) end1 = end1->next; // 找到第一个链表的尾结点 LinkList start2 = end1->next; // start2表示第二个链表的尾结点 LinkList next2 = start2->next; // 翻转需要保存后继，以免丢失地址 end1->next = start2->next = nullptr; // 第一个链表已经处理好，第二个链表准备翻转 while (next2) // 翻转操作，前驱节点是start2， 后继是next2， 修改完指针后，两者一起向后移动 { LinkList tmp = next2->next; next2->next = start2; start2 = next2, next2 = tmp; } LinkList p = L->next, q = start2; // 重排链表，把第二个链表走完代表重排完成 while (q) { LinkList tmp = q->next; // tmp节点防止断链 q->next = p->next; p->next = q; p = p->next->next; // p要向后走两步 q = tmp; } } ``` ## 栈和队列 ### 表达式求值 1. 设置两个栈，一个数栈，一个运算符栈 2. 遇到左括号直接压入运算符栈，遇到数字直接压入数栈 3. 遇到右括号，一直操作到左括号为止，然后弹出左括号 4. 遇到加减乘除，操作到**左括号**或者操作到栈顶运算符优先级**小于**当前运算符优先级 > 操作就是处理数栈，将运算的结果重新压入数栈 > > 最后操作完运算符栈，数栈顶就是表达式的答案 #### code ```c #include #include #include #include #include using namespace std; stack op; stack num; void eval() { int b = num.top(); num.pop(); int a = num.top(); num.pop(); char c = op.top(); op.pop(); int x = 0; if (c == '+') x = a + b; else if (c == '-') x = a - b; else if (c == '*') x = a * b; else x = a / b; num.push(x); } int main() { string s; cin >> s; unordered_map pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; for (int i = 0; i < s.size(); i ++ ) { if (isdigit(s[i])) { int j = i, x = 0; while (j < s.size() && isdigit(s[j])) x = x * 10 + s[j ++] - '0'; num.push(x); i = j - 1; } else if (s[i] == '(') op.push(s[i]); else if (s[i] == ')') { while (op.size() && op.top() != '(') eval(); op.pop(); } else { while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]]) eval(); op.push(s[i]); } } while (op.size()) eval(); cout << num.top() << endl; return 0; } ``` ## KMP > 一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己 上面那句话是我在找解析的时候看到的一句，很有道理。 核心问题： 找到长串中短串出现的位置 kmp对于暴力的优化在于：将暴力匹配问题转化为**前后缀相等**的问题(空间换时间) ```c #include #include using namespace std; const int N = 1000010, M = 100010; char s[N]; // 长串s char p[M]; // 短串p int ne[M]; // next数组，next[i]代表前i个字母中最长的与前缀相等的后缀长度 /** * @brief KMP算法 * 详细解析见readme * kmp是模式串匹配算法，用短串匹配长串，找出短串在长串中出现的位置 */ int main() { int n, m; // 长串长度n, 短串长度m scanf("%d%s%d%s", &m, p + 1, &n, s + 1); // 为了公式简洁，下标从1开始 // 预处理next数组, 自己和自己匹配 注意：i从2开始，j从0开始 for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++; ne[i] = j; // 把匹配的位置记录到next数组里 } // 匹配过程 注意：i从1开始，j从0开始 for (int i = 2, j = 0; i <= n; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; // 当j不在起点并且长串的i和短串的j + 1 位置失配了，我要移动短串，移动到next[j]的位置 if (s[i] == p[j + 1]) j ++; if (j == m) { // 匹配成功 输出在长串中匹配的位置 printf("%d ", i - m + 1); j = ne[j]; // 继续往下匹配 } } for (int i = 1; i <= m; i ++ ) cout << ne[i] << ' '; // 若题目要求下标从0开始，next数组整体加上1 return 0; } ``` 至于kmp的进一步优化，其实在做算法题的时候没必要进一步优化了，因为从时间复杂度上来说，二者的时间量级是一致的，都是线性的，```O(n)```的，故没必要研究。但是王道出了一道nextval的选择题，也不排除考的可能性吧，毕竟考试就是不会什么专门考什么。将next数组求出来以后，观察```p[j] 是否等于 p[next[j]]``` 1. 相等，令```next[j] = next[next[j]] ``` 2. 不相等，不变 对于解题，只要会两个方面的内容就行： 1. **next数组的求解** 2. **匹配过程的模拟** 重要说明：本解析中next数组的含义与王道有着微妙的不同，经过一整个下午的斟酌与探索，将next数组理解成最长的与前缀相等的后缀长度，既方便模拟，也方便实现。而王道书上的next数组，如果下标从1开始，```next[1] = 0, next[2] = 1```这是固定的。与我这里next数组的值**偏移1相差1**，如下图： ![image-20220708170650472](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220708170650472.png) 若用王道代码的next数组，其实并不方便模拟，如下图： ![image-20220708171708237](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220708171708237.png) ## 树与二叉树 ### 树 有关节点数的计算 1. n个节点的树有**n-1**条边 $$ n - 1 = 0 \times n_0 + 1 \times n_1 + 2 \times n_2 + {...} + i \times n_i $$ 2. 节点数等于度数从0到n的节点数之和 $$ n = n_0 + n_1 + n_2 + ... + n_i $$ 以上两个结论可以推得**二叉树**中一个重要公式： $$ n_0 = 1 + n_2 $$ ### 二叉树 常考性质： 1. 非空二叉树上，第i层的节点数 $$ 节点数 = 2 ^{i - 1}\quad i为层数(深度) $$ 2. 深度为k的二叉树的节点数 $$ 节点数至多 = 2 ^k - 1\quad k为深度 $$ 3. 对于任何一个二叉树，叶子节点与度为2的节点之间的关系 $$ n_0 = 1 + n_2 $$ 4. n个节点的完全二叉树的深度 $$ 深度 = \lfloor log_2n \rfloor + 1 $$ 5. 二叉树的堆式存储 $$ 左儿子 = 2 \times x \\ 右儿子 = 2 \times x + 1 $$ 二叉树的遍历 1. 前序遍历：根左右 2. 中序遍历：左根右 3. 后序遍历：左右根 重建二叉树： 1. 利用**前序遍历+中序遍历**构造二叉树(递归) 2. 利用中序遍历+后序遍历可以构造二叉树(递归) 3. 利用层次遍历+中序遍历可以构造二叉树(了解) 线索二叉树：前中后序线索二叉树 1. 若有左儿子，左指针指向左儿子(tag == 0)，否则指向对应前中后序遍历的前驱(tag == 1) 2. 若有右儿子，右指针指向右儿子(tag == 0)，否则指向对应前中后序遍历的后继(tag == 1) ### 二叉树与森林 左儿子右兄弟存储方式：用二叉树存储森林(本质上就是邻接表--左儿子的右链) 重要结论： 1. 森林的前序遍历就是二叉树的前序遍历 2. 森林的后序遍历就是二叉树的中序遍历 3. 二叉树中叶子结点数 = 转换后的森林中有右儿子的数量 + 1 ### 二叉排序树(查找) 定义：中序遍历是有序的 操作：插入、删除、查找 #### code ```c #include #include using namespace std; const int N = 20010; int l[N], r[N], v[N], idx, root; void insert(int &u, int w) { if (!u) u = ++ idx, v[u] = w; else if (w > v[u]) insert(r[u], w); else insert(l[u], w); } void del(int &u, int w) { if (!u) return; if (w > v[u]) del(r[u], w); else if (w < v[u]) del(l[u], w); else { if (!l[u] && !r[u]) u = 0; else if (!l[u]) u = r[u]; else if (!r[u]) u = l[u]; else { int p = l[u]; while (r[p]) p = r[p]; v[u] = v[p]; del(l[u], v[p]); } } } int get_pre(int u, int w) { if (!u) return -1e8; if (v[u] >= w) return get_pre(l[u], w); return max(v[u], get_pre(r[u], w)); } int get_suc(int u, int w) { if (!u) return 1e8; if (v[u] <= w) return get_suc(r[u], w); return min(v[u], get_suc(l[u], w)); } void inorder(int u) { if (!u) return; inorder(l[u]); cout << v[u] << ' '; inorder(r[u]); } int main() { int n; cin >> n; while (n -- ) { int t, x; cin >> t >> x; if (t == 1) insert(root, x); else if (t == 2) del(root, x); else if (t == 3) cout << get_pre(root, x) << endl; else if (t == 4) cout << get_suc(root, x) << endl; else inorder(root); } return 0; } ``` ### 表达式树 输出一棵树的中序遍历，加括号 按照中序遍历的顺序**左根右**写递归函数，如下图所示： ![image-20220715165029257](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220715165029257.png) ### 平衡树 平衡因子：一个节点的左子树高度减去右子树高度 左旋、右旋：**保持中序遍历不变**，动态维护这棵树 出现最小不平衡子树需要旋转 1. LL型 2. RR型 3. LR型（图中画错了，应该是左旋2） 4. RL型（图中画错了，应该是右旋4） ![image-20220715171509169](https://raw.githubusercontent.com/cmy-hhxx/cloudpic/main/img/image-20220715171509169.png) #### code ```c #include #include using namespace std; const int N = 30; int l[N], r[N], h[N], v[N], idx, root; int n; void update(int u) { h[u] = max(h[l[u]], h[r[u]]) + 1; } int get_balanced(int u) { return h[l[u]] - h[r[u]]; } void L(int &u) { int p = r[u]; r[u] = l[p], l[p] = u; update(u), update(p); u = p; } void R(int &u) { int p = l[u]; l[u] = r[p], r[p] = u; update(u), update(p); u = p; } void insert(int &u, int w) { if (!u) u = ++ idx, v[u] = w; else if (w > v[u]) { insert(r[u], w); if (get_balanced(u) == -2) { if (get_balanced(r[u]) == -1) L(u); else R(r[u]), L(u); } } else { insert(l[u], w); if (get_balanced(u) == 2) { if (get_balanced(l[u]) == 1) R(u); else L(l[u]), R(u); } } update(u); } int main() { cin >> n; while (n -- ) { int w; cin >> w; insert(root, w); } cout << v[root] << endl; return 0; } ``` ### 哈夫曼树 用**01前缀编码**来给字符编码，用该编码将每个字符替换掉 > 前缀编码：任意两个编码都不会互为前缀 $$ 总长度 = \sum_{i=1}^{n} 每个字符出现的次数 \times 编码长度 $$ 每个编码都可以对应一棵二叉树，所有**字符**都仅仅对应**叶节点** 解码：解码方案唯一，从根遍历二叉树，走到叶节点输出，回到根 上述的**总长度**可以定义为**树的带权路径和**，求一棵二叉树，使得WPL最小？？ 哈夫曼编码：从下往上构造一棵树，每次选择权值最小的两个点，将这两个点合并。(*证明略*) #### code ```c #include #include #include using namespace std; int main() { int n; cin >> n; priority_queue, greater> heap; while (n -- ) { int x; cin >> x; heap.push(x); } int res = 0; while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); res += a + b; heap.push(a + b); } cout << res << endl; return 0; } ``` ### 扩展哈夫曼树 用**k进制**编码，对应一棵**k叉树** 拓展哈夫曼编码：**每次选最小的k个数合并** > 注：如果k - 1 不能整除 n - 1，需要补0，直到 **k - 1** 能够整除 **n - 1**(证明略) > > 0对答案没有影响 #### code ```c #include #include #include using namespace std; typedef long long LL; typedef pair PLI; int main() { int n, k; cin >> n >> k; priority_queue, greater> heap; while (n --) { LL w; scanf("%lld", &w); heap.push({w, 0}); } while ((heap.size() - 1) % (k - 1)) heap.push({0, 0}); LL res = 0; while (heap.size() > 1) { LL s = 0; int depth = 0; for (int i = 0; i < k; i ++ ) { PLI t = heap.top(); heap.pop(); s += t.first, depth = max(depth, t.second); } res += s; heap.push({s, depth + 1}); } cout << res << endl << heap.top().second << endl; return 0; } ``` *** ## 图论 ### 图的存储 1. 邻接矩阵：稠密图(无法存重边) 2. 邻接表：稀疏图(可存重边) 3. 邻接多重表 4. 十字链表 5. 三元组表 ### 图的遍历 1. 深度优先遍历 2. 宽度优先遍历 ### 拓扑排序 拓扑序列：针对有向图，对于每条边，**起点都在终点前面**，称这样的序列是拓扑序列(所有的边都是**从前指向后**的) 一个有向无环图一定至少存在一个入度为0的点(反证法) **存在拓扑排序等价于图中没有环**，拓扑序列并不唯一 基于**宽搜**：把**入度为0**的点入队，每次从队列中任取一点，将这个点删除，将这个点到达的所有点入度为0的点入队，如此迭代 > 宽搜判断是否存在拓扑序：如果所有点都被遍历过，则存在拓扑序；否则不存在 基于**深搜**：在dfs回溯前输出，就是拓扑排序的逆序 >深搜判断是否存在拓扑序：存在环会搜到递归路径上的点，用```st[]```数组记录 #### code ```c #include #include #include using namespace std; const int N = 100010, M = 100010; // 最大的点数N，边数M struct Node { int id; Node *next; Node(int _id): id(_id), next(nullptr) {} }*head[N]; int n, m; int d[N], q[N]; // d[] 存储的是每个点的入度数量、 q[] 手动开队列，存储的就是拓扑排序的结果 void add(int a, int b) // 头插法 { Node *p = new Node(b); p->next = head[a]; head[a] = p; } bool topsort() { int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) if (!d[i]) // 将入度为0的点入队 q[++ tt] = i; while (hh <= tt) { int t = q[hh ++]; for (Node *p = head[t]; p; p = p->next) if (-- d[p->id] == 0) // 将这个点相邻的点入度减1，如果为0，入队 q[++ tt] = p->id; } return tt == n - 1; } int main() { cin >> n >> m; while (m -- ) { int a, b; scanf("%d%d", &a, &b); add(a, b); d[b] ++; // 维护每个点的入度， b这个点的入度++ } if (!topsort()) puts("-1"); else { for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); } return 0; } ``` ### 最小生成树 最小生成树：无向图中，选$ n-1 $条边连通$n$个点，要求总边权和最小(最大边权最小) 最小生成树不一定唯一 ### Prim算法 任取一个起点，每一次找到和当前连通块连接的边权最小的一条边，这条边一定可以在生成树当中。(不唯一) ```c #include #include #include using namespace std; const int N = 510, INF = 0x3f3f3f3f; /** * g[][] 存储的是邻接矩阵 * dist[] 存储的是每个点的最小边权 * st[] 存储的是该点是否被遍历过 */ int g[N][N], dist[N]; int n, m; bool st[N]; int prim() { memset(dist, 0x3f, sizeof dist); // 初始化dist数组为正无穷 dist[1] = 0; // 选择第一个点 int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) // 每次选择最短的边加进来 t = j; if (dist[t] == INF) return INF; // 代表不连通 st[t] = true; res += dist[t]; // 加进来的每条边的长度 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); // 用该点更新其他点到当前集合的最短距离 } return res; } int main() { memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); while (m -- ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); g[a][b] = g[b][a] = min(g[a][b], w); // 重边取最小 } int res = prim(); if (res == INF) puts("impossible"); else cout << res << endl; return 0; } ``` ### Kruskal算法 将所有边按权重从小到大排序，枚举每条边，如果说a、b不连通(并查集)，将这条边加入集合 ### 朴素版Dijkstra 本质：贪心算法--当前距离起点最近的点一定是最优解 1. 先初始化距离，起点为0，其余为正无穷 2. n次迭代 1. 每次找到不在s中的距离起点最近的点t 2. 把t加入集合s中，标记t 3. 用t更新其他所有点的距离 ```看一下是否dist[x] > dist[t] + w，大于需要更新``` > 集合s：当前已经确定最短路径的点 ```st[i] == true``` 时间复杂度$O(n^2)$ tips: Dijkstra 得到的最短路径一定是严格递增的， 故一定是按照从小到大排序之后的顺序 ```c #include #include #include using namespace std; const int N = 510, INF = 0x3f3f3f3f; int g[N][N], dist[N]; bool st[N]; int n, m; int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); } return dist[n]; } int main() { memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); g[a][b] = min(g[a][b], w); } int res = dijkstra(); if (res == INF) puts("-1"); else cout << res << endl; return 0; } ``` ### Floyd多源汇最短路 本质：动态规划，利用第三个点来更新点与点之间的最短距离 时间复杂度$o(n^3)$ ### 关键路径 每条边被称为活动，每个点称为事件 源点 汇点 关键路径：最少需要多长时间完成整个工程--**最长路**，也就是源点到汇点边权和最大的路径 AOE网络必须没有环 事件最早开始时间 事件最晚开始时间 活动最早开始时间 活动最晚开始时间：求该活动的边的终点到整个工程的最长路，用总工期减去该最长路，再减去该活动的长度 *** ## 查找 $平均查找长度ASL(成功) = \sum p_i \times c_i$ $平均查找长度ASL(失败) = \sum\limits_{区间} p_i \times c_i $ > $p_i$是概率， $c_i$是查找该元素的比较次数 决策树 ### 顺序查找 无序表： $ASL(成功) =\frac{1}{n} \times (1 + 2 + ... + n) = \frac{(n+ 1)}{2}$ $ASL(失败) = n$ 有序表： $ASL(成功) =\frac{1}{n} \times (1 + 2 + ... + n) = \frac{(n+ 1)}{2}$ $ASL(失败) = \frac{n}{2} + \frac{n}{n + 1}$ ### 折半查找 > 注意：之前的二分代码不要用了， 考试按教材考 $ASL(成功) =log_2(n + 1) - 1$ ### 分块查找 块内无序，块间有序 1. 顺序查找法：$ASL(success) = \frac{\frac{n}{s} + 1}{2} + \frac{s+1}{2} , s = \sqrt n \space取最小值$ 2. 折半查找法：$ASL(success) = log(\frac {s}{n} + 1) - 1 + \frac {s + 1}{2}$ ### B树与B+树 > 其实完全可以不用学啊，但是它考试要考，所以需要学 为了读写性能 B树：每一个内部节点关键字有信息 B+树： 所有信息全部存在叶节点(内部节点不存信息) > B+ 树为了更好局部性， 缓存命中率高 *** B树概念： 1. m阶B树： 每个节点最多有m个孩子，每个节点可以分成m - 1个关键字 2. 所有叶节点都在同一层 B树操作： 1. 查找 2. 删除 ### 哈希表 做映射方便查找 处理冲突 1. 开散列方法(拉链法) 2. 闭散列方法(开放寻址法)：聚集和二级聚集 ### 红黑树 1. 插入 红黑树本身是一棵二叉排序树，将节点插入后仍是二叉排序树。也就意味着，树的中序遍历仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉排序树，旋转之后它一定还是二叉排序树。这也就意味着，**任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉排序树的事实**。 2. 删除 *** ## 排序 ### 插入排序 ### 折半插入排序 ### 冒泡排序 ### 选择排序 ### 希尔排序 每组内的下标为等差数列，公差称为增量。 插入排序对于部分有序序列效率很高 ### 快速排序 如果第一层分界点不是端点，那么至少有3个点在正确的位置上 如果第一层分界点是端点，那么至少有2个点在正确的位置上 ### 堆排序 堆是一棵完全二叉树 采用顺序存储 注意：将序列**调整成堆**和**不断插入数据形成堆**是不一样的 调整的复杂度$O(n)$ 形成堆的复杂度$nlogn$ ### 归并排序 ### 桶排序(计数排序) 一个数$a_i$的位置 = 小于$a_i$的元素数量 + 等于$a_i$且在$a_i$左边的数的数量 ### 基数排序 > 比较排序的下界是$nlogn$ 若干遍桶排序 ### 外部排序 1. 预处理：利用内存生成m个有序串 2. 多路归并：将m个有序段合并 ### code ```c #include #include #include using namespace std; const int N = 100010; int q[N]; int n, sz; /** * @brief 直接插入排序(比较次数O(n)) * 1. 时间复杂度 * 1. 最好情况： O(n) * 2. 平均情况： O(n^2) * 3. 最坏情况： O(n^2) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：稳定 */ void insert_sort() { for (int i = 1; i < n; i ++ ) { int t = q[i], j = i; while (j && q[j - 1] > t) { q[j] = q[j - 1]; j --; } q[j] = t; } } /** * @brief 折半插入排序(比较次数为logn) * 1. 时间复杂度 * 1. 最好情况： O(n) * 2. 平均情况： O(n^2) * 3. 最坏情况： O(n^2) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：稳定 */ void binary_search_insert_sort() { for (int i = 1; i < n; i ++ ) { int t = q[i]; if (q[i - 1] <= t) continue; int l = 0, r = i - 1; while (l < r) { int mid = l + r >> 1; if (q[mid] > t) r = mid; else l = mid + 1; } for (int j = i - 1; j >= r; j -- ) q[j + 1] = q[j]; q[l] = t; } } /** * @brief 冒泡排序 * 1. 时间复杂度 * 1. 最好情况： O(n) * 2. 平均情况： O(n^2) * 3. 最坏情况： O(n^2) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：稳定 */ void bubble_sort() { for (int i = 0; i < n; i ++ ) { bool has_swap = false; for (int j = n - 1; j > i; j -- ) { if (q[j] < q[j - 1]) { swap(q[j], q[j - 1]); has_swap = true; } } if (!has_swap) break; } } /** * @brief 选择排序 * 1. 时间复杂度 * 1. 最好情况： O(n^2) * 2. 平均情况： O(n^2) * 3. 最坏情况： O(n^2) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：不稳定 */ void select_sort() { for (int i = 0; i < n; i ++ ) { int k = i; for (int j = i + 1; j < n; j ++ ) if (q[j] < q[k]) k = j; swap(q[i], q[k]); } } /** * @brief 希尔排序 * 1. 时间复杂度： O(n^(3/2)) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：不稳定 */ void shell_sort() { for (int d = n / 2; d; d /= 2) { for (int start = 0; start < d; start ++ ) { for (int i = start + d; i < n; i += d) { int t = q[i], j = i; while (j > start && q[j - d] > t) { q[j] = q[j - d]; j -= d; } q[j] = t; } } } } /** * @brief 快速排序 * 1. 时间复杂度 * 1. 最好情况： O(nlogn) * 2. 平均情况： O(nlogn) * 3. 最坏情况： O(n^2) * 2. 辅助空间复杂度： O(logn) 系统栈 * 3. 稳定性：不稳定 */ void quick_sort(int l, int r) { if (l == r) return; int left = l - 1, right = r + 1, x = q[l + r >> 1]; while (left < right) { do left ++; while (q[left] < x); do right --; while (q[right] > x); if (left < right) swap(q[left], q[right]); } quick_sort(l, right); quick_sort(right + 1, r); } /** * @brief 堆排序(下标需要从1开始) * 1. 时间复杂度 * 1. 最好情况： O(nlogn) * 2. 平均情况： O(nlogn) * 3. 最坏情况： O(nlogn) * 2. 辅助空间复杂度： O(1) * 3. 稳定性：不稳定 */ void down(int u) { int t = u; if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2; if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1; if (u != t) { swap(q[u], q[t]); down(t); } } void heap_sort() { sz = n; for (int i = n / 2; i; i -- ) down(i); for (int i = 0; i < n - 1; i ++ ) { swap(q[1], q[sz]); sz --; down(1); } } /** * @brief 归并排序 * 1. 时间复杂度 * 1. 最好情况： O(nlogn) * 2. 平均情况： O(nlogn) * 3. 最坏情况： O(nlogn) * 2. 辅助空间复杂度： O(n) * 3. 稳定性：稳定 */ int tmp[N]; void merge_sort(int l, int r) { if (l == r) return; int mid = l + r >> 1; merge_sort(l, mid), merge_sort(mid + 1, r); int left = l, right = mid + 1, cnt = 0; while (left <= mid && right <= r) { if (q[left] < q[right]) tmp[cnt ++] = q[left ++]; else tmp[cnt ++] = q[right ++]; } while (left <= mid) tmp[cnt ++] = q[left ++]; while (right <= r) tmp[cnt ++] = q[right ++]; for (int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; } /** * @brief 桶排序 * 1. 时间复杂度 * 1. 最好情况： O(n + m) * 2. 平均情况： O(n + m) * 3. 最坏情况： O(n + m) * 2. 辅助空间复杂度： O(n + m) * 3. 稳定性：稳定 */ int pos[N], cnt[N]; void bucket_sort() { for (int i = 0; i < n; i ++ ) cnt[q[i]] ++; for (int i = 1; i < N; i ++ ) cnt[i] += cnt[i - 1]; for (int i = n - 1; i >= 0; i -- ) pos[-- cnt[q[i]]] = q[i]; for (int i = 0; i < n; i ++ ) q[i] = pos[i]; } /** * @brief 基数排序 * * 1. 时间复杂度 * 1. 最好情况： O(d*(n + r)) * 2. 平均情况： O(d*(n + r)) * 3. 最坏情况： O(d*(n + r)) * 2. 辅助空间复杂度： O(n + r) * 3. 稳定性：稳定 */ void radix_sort(int d, int r) { int radix = 1; for (int i = 1; i <= d; i ++ ) { for (int j = 0; j < n; j ++ ) cnt[j] = 0; for (int j = 0; j < n; j ++ ) cnt[q[j] / radix % r] ++; for (int j = 1; j < r; j ++ ) cnt[j] += cnt[j - 1]; for (int j = n - 1; j >= 0; j -- ) pos[-- cnt[q[j] / radix % r]] = q[j]; for (int j = 0; j < n; j ++ ) q[j] = pos[j]; radix *= r; } } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); // insert_sort(); // binary_search_insert_sort(); // bubble_sort(); // select_sort(); // shell_sort(); // quick_sort(0, n - 1); // heap_sort(); // merge_sort(0, n - 1); // bucket_sort(); radix_sort(10, 10); for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); return 0; } ```