# 数据结构 **Repository Path**: su-ziguang/data-structure ## Basic Information - **Project Name**: 数据结构 - **Description**: 数据结构学习仓库 - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-01-15 - **Last Updated**: 2026-02-06 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README - 环境: linux-ubuntu 20.x.x - 内容: 数据结构学习仓库 下面是大纲, 帮助快速定位内容 # 数据结构学习大纲 ## 复杂度 ### 数据结构与数据库的概念区别 - 共同点：是一种数据的组织方式，是一种数据的存储管理方式 - 区别 - 数据库：在磁盘(硬盘)中管理数据 - 数据结构：在内存中管理数据 - 延伸：内存与磁盘的简单认知 - 内存：速度快，带电存储，一般单价比较高 - 磁盘：速度慢，不带电存储，一般单价比较便宜 ### 衡量算法的效率 -> 复杂度 - 为什么不直接使用时间来衡量算法效率？ - 因为同一个算法/程序对于不同的机器运行时间完全不同！ - 如何衡量算法的效率？-> 用复杂度来衡量 - 时间复杂度 - 空间复杂度 ### 时间复杂度原则 - 练习题：见课件 - 结论1：取影响最大的项 - 结论2：不明确O(N)中未知数的数量关系前提下，不能直接去掉O(N)中的未知数 - 结论3：常数次统一时间复杂度是O(1) - 结论4：我们时间复杂度取的是最坏的情况 - 结论5：当我们进行复杂度计算的时候，不要看循环嵌套了几层(语法层面)，而是要看思想！！！ ### 时间复杂度的应用举例 > 写代码时提前在不同思路中选取效率高的(而非写完代码再挨个测试) - 消失的数字 - 题目：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。 - 思路1：先冒泡排序，再遍历一遍数组(当前数+1 != 下一个数) -> O(N^2) - 思路2：C语言异或法(要求对异或有一定了解) - 思路3：等差数列求和法(等差数列求和) ### 空间复杂度原则 - 练习题：见课件 - 结论1：空间是临时额外占用存储空间大小的量度 - 结论2：递归空间复杂度计算，也是空间累加，但是不同的是空间可以重复利用 ### 空间复杂度相关的例题 -> 以空间换时间思想 - 消失的数字 - 题目：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。 - 思路：建立一个数组，然后遍历一遍数组，把数组中的数放到对应的下标中，最后遍历一遍数组，找到下标和数不对应的数 - 旋转的数组 - 题意：给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。 - 思路1：挨个暴力挪动覆盖 - 思路2：先逆置前n-k个数字，再逆置后k个数字，再整体逆置 - 思路3：以空间换时间，创建临时数组 - 感受空间换时间 -> 移除元素 - 描述：给你一个数组nums和一个值val，原地移除nums中所有等于val的元素，并返回数组的新长度 - 思路1：借助temp数组 - 思路2：双指针，cur去遍历，dest去维护有效数字即可 ## 顺序表 ### 顺序表是什么？ - 是一种逻辑结构是线性，物理结构也是线性的特殊线性表 ### 顺序表的实现 - 静态顺序表 - 动态顺序表 ### 顺序表相关练习题 - 删除有效数组中的重复项 - 题意：非严格递增的数组，可能会有重复项，原地删除 - 思路1：双指针去重算法 - 思路2：辅助数组 - 合并两个有序数组 - 题意：给你两个有序数组，将num2合并到num1成为一个新的有序数组 - 思路1：临时数组合并 - 思路2：数组从右向左合并 ### 数组顺序表的缺陷 - 头部/中间插入删除效率比较差 - 满了之后，只能扩容，扩容有一定时间消耗且存在空间浪费，且扩容力度与扩容后空间浪费存在不可调和的矛盾。 ## 链表 ### 链表的意义 - 数组顺序表的缺陷 - 头部/中间插入删除效率比较差 - 满了之后，只能扩容，扩容有一定时间消耗且存在空间浪费 -> 扩容力度与扩容后空间浪费存在不可调和的矛盾。 - 为了解决顺序表缺陷，补充了"链表"，但也存在一定问题 - 优点：随机插入随机删除效率很高 - 优点：单次扩容小且管理灵活。 - 缺点：比如链表地址不连续，注定了随机读取成本就会上升~ ### 链表的接口实现 ### 链表相关练习题 1. 链表的中间节点 - 题意：返回链表的中间节点(偶数个返回中右) - 思路1：遍历两遍 - 思路2：快慢指针法 2. 移除链表元素 - 题意：删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 - 思路1：原地暴力 -> 两个指针删除(prev记录前驱指针，cur遍历) - 思路2：遍历原链表，不是val的节点尾插到新链表 3. 链表分割 - 题意：编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序 - 思路：先把小于x的链表单独组成一个链表，再接起来即可~ 4. 反转链表 - 题意：链表逆置 - 思路1：三指针思路，p1 = NULL，p2 = node1，p3 = node2，建立p1和p2的连接~ - 思路2：头插(带个哨兵位比较好弄) 5. 链表中倒数第k个节点 - 题意：返回链表中倒数第k个节点 - 思路：双指针，fast先走k步，统一移动 6. 链表相交 - 题意：给你两个链表，返回他们的交点(有可能不存在) - 思路1：暴力求解，把A链表所有节点依次去B中找一遍(用节点的地址去比对) - 思路2：分别找到尾节点(不要找到NULL，因为需要确定是否相交)，统计每个链表的长度，然后重新遍历两个链表，较长的链表提前走差值个节点。 7. 环形链表 - 思路1：快慢指针 8. 找环的入口点 - 结论：慢指针从入口开始走，快指针从相遇点开始走，两个指针会在环入口处相遇 - 思路1：快慢指针 9. 合并两个有序链表 - 思路：选小的尾插~ 10. 链表的回文结构 - 思路：找到中间节点(偶数第二个中间节点)，逆置第二段链表，然后比对 - 细节：不需要完全分割前后链表；偶数情况可分割，奇数若分割反而需要特殊处理，第一个链表指向中间节点更好处理~ 11. 随机链表的复制 - 思路1：先拷贝，再根据原链表的random指向第几个，然后拷贝链表指向自己链表第几个节点 -> N^2 - 唯一问题：复杂度太高，确定每个节点random指向的位置复杂度是O(N^2) - 思路2：先在原链表中复制，然后依靠拷贝链表与原链表每个节点的位置前后关系实现O(N)的copy_random指向，复杂度是O(N) - 思路3：unordered_map<原链表random指向, 拷贝链表random指向> ### 链表的分类 -> 共8种链表 - 指向：单项，双向 - 是否带头 - 是否循环 ### 实现带头双向循环链表 ### 顺序表和链表的区别 ### 了解：为什么链表缓存利用率比较低？顺序表比较高？ - 缓存利用率参考存储体系结构 以及 局部原理性 ## 栈 ### 栈是什么？ - 栈是一种特殊的线性表，只允许在固定的一端插入/删除(栈顶)，另一端称为栈底，遵循**先进后出**的特点 ### 栈的实现 - 数组栈：数组尾是栈顶(实现简单，缓存命中效率高) - 链式栈：单链表(栈顶是头)、双链表均可~(无法预估节点的多少，需要频繁开空间/释放) - 概念选择题 见课件 ### 有效的括号 - 题意：检查括号字符串是否匹配 - 思路：左括号进栈，右括号出栈匹配，若不匹配返回false，最后检查栈是否为空 ## 队列 ### 什么是队列？ - **先进先出**的特殊线性表 ### 用什么线性表实现队列比较合适？实现队列 - 数组：不合适，因为要求一端入，一端出 - 双向链表：合适，相比于单链表有些冗余~ - 单链表：适合，链表尾插入，链表头删除 ### 队列相关练习题 1. 用队列实现栈 - 题意：用队列实现栈 - 核心：一个队列存数据，另一个队列用来出数据时导出数据 2. 用栈实现队列 - 题意：用栈实现队列 - 思路：导入两个栈，负负得正实现队列的特性~ 3. 设计循环队列 - 什么是循环队列？ - 与队列相同：都遵循先进先出 - 与队列不同：空间固定，循环利用 - 设计：[front, back)，多开一个空间(或者用size标记) - 空：front = back - 满：(back + 1) % size = front ## 二叉树 ### 树的概念以及结构 - 树：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合 - 树的相关概念 - 树的表示 - 左孩子右兄弟 - 孩子表示法(孩子用顺序表存储) - 树的应用 -> Linux文件系统 ### 二叉树概念以及结构 - 二叉树构成：空 或者 根加上左右子树构成 - 二叉树的特征 - 度<=2 - 顺序性：左右子树有区分，次序不能颠倒，是有序树 - 特殊二叉树 - 完全二叉树 - 满二叉树 ### 二叉树的性质 - 满二叉树节点个数：2^h - 1 - 完全二叉树节点个数：[2^(h-1), 2^h - 1] - 完全二叉树度为1的节点个数不是0就是1 - n0 = n2 + 1 - 空树：无节点度的数量关系讨论 - 只有根的树：满足n0(1) = n2(0) + 1 - 增加节点给度为0的节点：no++(新增)，n0--，n1++(原0度变1度) - 增加节点给度为1的节点：n0++(新增)，n1--，n2++(原1度变2度) - 练习：相关性质选择题，见课件 ### 顺序存储二叉树 - 堆的实现 - 建堆：从倒数第一个非叶子节点 + 向下调整算法 - 思考：为什么向上调整算法建堆时间复杂度比向下调整算法高logN？ - 堆上面节点少，下面节点多 - 调整数量：向下调整最后一行不调整，向上调整第一行不调整 - 调整高度：向下调整大部分节点靠下、调整高度少，向上调整则相反~ - 堆的意义 - topK问题 - 思路：建k大小的"反堆"，遍历整个数组进行替换，堆中的结果就是答案 - 堆排序 - 思路：建"反堆"，堆删除思想排序 ### 链式二叉树 1. 二叉树的构造 - 二叉树是递归定义的(根，左子树，右子树) 2. 二叉树的遍历 - 深度优先遍历 - 前序遍历：根，左子树，右子树 - 中序遍历：左子树，根，右子树 - 后序遍历：左子树，右子树，根 - 层序遍历：按层遍历树 - 根节点入队列，出节点的时候带孩子(如果存在的话) 3. 节点个数以及高度 - 二叉树节点个数 - 思路1：静态size - 思路2：全局size - 思路3：分治思想，当前树的节点个数 = 左子树节点个数 + 右子树节点个数 + 根(1) - 二叉树叶子节点个数 - 思想：叶子返回1，空节点返回0，非叶子节点返回左子树节点个数 + 右子树节点个数 - 求树的高度 - 思想：当前子树的高度 = max(左子树高度, 右子树高度) + 当前层的高度(1)，空树高度为0 - 坑点：只比较不记录，会导致时间复杂度大增！O(N) -> O(2^N)（N是树的节点个数） - 例题：树的高度 - 二叉树第k层节点个数 - 思想：分治思想，用k标识层数；k=1返回1，空节点返回0，k>1返回左子树k-1层 + 右子树k-1层 - 二叉树查找值为x的节点 - 思路：先找根，找到则返回；再去左子树找，找到则返回；最后去右子树找，找到则返回，否则返回NULL 4. 二叉树基础OJ练习 - 单值二叉树 - 题意：检查一棵树是否只有一个val值 - 思路：检查每个根和其孩子是否相等 -> 检查根与左孩子、根与右孩子，递归 - 相同的树 - 题意：检查两棵树是否val和结构完全一致 - 思路：根和根比，左子树和左子树比，右子树和右子树比 - 对称二叉树 - 题意：给你一颗树，检查是否为对称树 - 思路：根和根比较，左子树和右子树比较，右子树和左子树比较（类比：相同的树） - 二叉树的前序/中序/后序遍历 - 题意：遍历一颗树，将结果值放到数组中返回 - 思路：C语言实现需先获取size，再执行对应遍历 - 另一棵树的子树 - 题意：判断第一棵树是否包含第二棵树 - 思路：枚举第一颗树中所有节点，匹配第二课树的结构~ 5. 二叉树的创建和销毁 - 通过前序遍历的数组构建二叉树 - 题意：给一个前序字符串，构建二叉树 - 思路：递归构建 -> 遇到NULL返回NULL，遇到非空构建节点，继续构建其左子树和右子树~ - 时间复杂度：O(N) - 判断是否为完全二叉树 - 题意：判断一个二叉树是否为完全二叉树 - 思路：节点入队列，出到空时直接break，检查队列中是否还有非空节点；全为空则为完全二叉树 - 二叉树的销毁 - 题意：销毁一颗二叉树 - 思路：建议使用后序销毁；也可使用前序/中序，需额外保存右子树指向 ## 排序 ### 概念 - 排序：经过操作，将一串记录按照某种指定的规则排列起来 - 稳定性/非稳定性：待排数组中存在多个相同关键字记录，排序后相对位置保持不变则为**稳定性排序**，否则为**非稳定性排序** - 内部排序/外部排序：排序时数据元素全部在内存中进行则为**内部排序**；元素过多导致部分在内存、部分在外存进行则为**外部排序** ### 插入排序 1. 直接插入排序 - 思想：把待排序的记录按其关键码值的大小逐个插入到一个已排好序的有序序列中，直到所有记录插入完，得到新的有序序列。 - 思路：将待插入元素保存为tmp，逐个与end值比较(升序) - tmp > end -> end + 1 = tmp - tmp < end -> end + 1 = end，end-- - 时间复杂度：O(N^2) - 空间复杂度：O(1) - 特性1：对数据的适应性比较好，越接近有序效率越高，有序时时间复杂度为O(N) - 特性2：**稳定性排序** 2. 希尔排序 - 思想：多组预排序(让数据接近有序，避免直接插入排序最坏情况) + 直接插入排序 - 为什么比直接插入排序快？ - 用较少的比较次数，将距离目标位置较远的数快速移动到位置相近，最后通过直接插入排序保证严格有序。 - 时间复杂度：O(N^(1.3)) ≈ O(N*logN) - **非稳定性排序** ### 选择排序 1. 直接选择排序 - 思想：选一个待排区间的最值，放到对应位置 - 优化：一次选待排元素的最小值和最大值 - 时间复杂度：O(N^2) - 空间复杂度：O(1) - 优化写法坑：begin/end/mini/maxi，先交换小再交换大时，若maxi == begin，交换小会导致真实的maxi被换走~ - **非稳定性排序** 2. 堆排序 - 思想：利用堆的特性实现排序 - 时间复杂度：O(N*logN) - 空间复杂度：O(N) - **非稳定性排序** ### 交换排序 1. 冒泡排序 - 思想：每次选一个待排区间的最值冒到对应存放位置 - 思路：每次冒泡一个数，共需冒n-1个数 - 优化：一趟冒泡无交换则认为数组已有序，直接break；最好时间复杂度为O(N) - 时间复杂度：O(N^2) - 空间复杂度：O(1) - 特性：**稳定性排序** - 对比：直接插入排序更好 - 原因：直接插入大概率不会达到最差时间复杂度，而冒泡大概率会达到 2. 快速排序 - 思想：分治思想，选取keyi值，使keyi左侧keyi，分治递归(迭代)处理，直到完全有序~ - 单趟排序：选取key值，使key左侧比key小、右侧比key大 - hoare版本 - 思想：确定keyi后，R先向左找比key小的值，L向右找比key大的值，找到后L和R交换，直至相遇，最后LR和key交换 - 坑1：每次交换都需要判断边界 - 坑2：遇到=key的值要掠过，否则会死循环 - 坑3：left从begin开始而非begin+1；若从begin+1开始，两个数时会导致LR在begin+1位置相遇，交换错误！ - 挖坑法 - 思想：将最左值保存形成坑位，右侧找小值填入坑位，右侧形成新坑；循环直至相遇，将最左值填入相遇坑位 - 优势：比hoare版本好理解，本质原理一致 - 前后指针法 - 思想：cur遍历数组，prev保证[0, prev]的数字均比key小~ - 优势：区别于hoare思想，属于双指针思想~ - 特征：**非稳定性排序** - 问题1：为什么快排在有序情况下效率低？ - 原因：一直取左值作为key，导致效率退化~ O(N*logN) -> O(N^2) - 解决：**三数取中** - 问题2：为什么hoare相遇位置一定比key小？ - 原因：右边先走，相遇分两种情况 - R -> L：L存储的是交换后比key小的值 或者 直接走到key位置 - L -> R：此情况R一定先找到小值，L遇到R时，相遇点必比key小~ - 问题3：递归层次越深，划分区间越细，排序最后几个数字会产生大量递归？ - 解决：**小区间优化** -> 插入排序 - 实际：release编译下，编译器对栈帧消耗的优化足够，小区间优化效果有限 - 非递归写法 - 写法：利用栈控制区间，出一个区间则入其分割后的子区间(一般两个，也可能一个) ### 归并排序 - 思想：分治思想，**分**：不断将区间划分为小区间；**治**：将有序的小区间归并为大的有序区间~ - 时间复杂度：O(N*logN) - 特性：**稳定性排序** - 非递归形式 - 思路：忽略"分割"，直接对原数组按指定步长进行"归并" - 坑1：处理好归并过程中的越界问题 - 特性：**可实现外排序** - 示例：40GB数据每次读入内存1GB - 用内部排序算法将内存中1GB数据排序，写入独立小文件，共生成40个小文件 - 对小文件进行归并：打开两个小文件，读取首元素比较，尾插到新文件；循环直至所有小文件合并为一个有序大文件 - 为什么可外排？归并排序不需要交换数据！其他排序需交换数据，外存中数据交换成本极高(难以操作) ### 非比较排序 -- 计数排序 - 思想：计数排序又称鸽巢原理，是对哈希直接定址法的变形应用。 - 步骤 1. 处理空数组或只有一个元素的情况 2. 找到数组中的最大值，确定计数数组的大小 3. 创建计数数组，并初始化为0 4. 统计原数组中每个元素出现的次数 5. 遍历计数数组，重构排序后的原数组 - 时间复杂度：O(N(数据量) + hash_N(数值范围)) - 空间复杂度：O(hash_N(数值范围)) - 局限性 - 不适合数值分散的数据，要求数据相对集中 - 不适合浮点数、字符串、结构体数据排序，仅适合数字排序 - 优化：**相对映射(哈希映射)** ，缩小计数数组的大小 ### 外排序(了解) - 思路：将大文件分片读入内存，用快排对内存数据排序后输出到小文件，最后归并所有小文件得到有序大文件 - 步骤 1. 生成模拟大文件 - 打开大文件 -> 生成随机数写入 -> 关闭大文件 2. 分块排序生成小文件 - 打开大文件 -> 读适量数据到内存，快排后输出到磁盘小文件 -> 管理所有小文件的文件名 3. 归并所有小文件 - 采用归并排序的非递归形式 - logN轮归并，每轮将小文件两两合并输出新文件并管理，下一轮对新文件继续两两合并 - 最终剩下一个大文件，即为排序好的结果 4. 打印最终有序结果 ### 顺序表和链表的区别 | 对比维度 | 顺序表 | 链表 | |------------------|----------------------------|----------------------------| | 存储结构 | 连续的内存空间 | 离散的内存空间，节点间通过指针连接 | | 随机访问 | 支持，O(1)时间复杂度 | 不支持，需遍历，O(N)时间复杂度 | | 插入/删除操作 | 头部/中间操作效率低，O(N)；尾部操作O(1) | 头部/中间操作效率高，O(1)；尾部操作需遍历找尾节点(O(N))，带头双向循环链表尾部O(1) | | 空间利用率 | 预分配内存，易产生空间浪费；扩容有时间消耗 | 按需申请节点，无空间浪费；每次申请/释放节点有微小开销 | | 缓存命中率 | 高，符合局部性原理 | 低，节点地址离散，易缓存失效 | | 实现复杂度 | 实现简单，无需处理指针 | 实现复杂，需处理指针指向问题 | | 适用场景 | 频繁随机访问，少量插入/删除 | 频繁插入/删除，少量随机访问 |