yunme / datastructure Goto Github PK

1. Install VSCode.
2. Follow the guide CMake Tools for Visual Studio Code.
   1. Install C/C++ extension for VS Code.
   2. Install CMake Tool extension for VS Code.
   3. Install MinGW-w64 via MSYS2 follow this guide

      1. Download MSYS2 and install.

      2. Open MSYS2 terminal and install MinGW-w64 toolchain by running

         pacman -S --needed base-devel mingw-w64-ucrt-x86_64-toolchain

      3. Add the MinGW-w64 folder to System PATH.

   4. install CMake and add CMake to System PATH.
3. Open project in VS Code.
4. From the command palette in VS Code, run the CMake: Configure command.
5. From the command palette, run the CMake: Select a Kit.
6. From the command palette, run the CMake: Run or click Run button from the status bar.

包含顺序表和链表。

1. 插入元素
2. 删除元素
3. 查找元素：按索引查找，按值查找
4. 遍历等。

1. 插入元素：头插法，尾插法
2. 删除元素
3. 查找元素：按索引查找，按值查找
4. 遍历等。

• 双向链表（前驱指针）
• 双向循环链表（头结点的前驱指向尾结点，尾结点后继指向头结点）

1. 线性表的合并
   • 顺序表实现
   • 链表实现
2. 有序线性表的合并
   • 顺序表实现
   • 链表实现

后进新出

• 栈顶插入元素：入栈
• 栈顶删除元素：出栈

1. 顺序栈（顺序表实现）
2. 链栈（链表实现）
   • push 元素入栈
   • pop 元素出栈
   • top 返回栈顶元素

使用：

• 数值转换
• 表达式求值
• 括号匹配检验
• 八皇后问题
• 函数调用
• 递归调用实现

栈与递归：

• 递归定义的数学函数（阶乘，斐波拉契数列）
• 具有递归特性的数据结构（二叉树）
• 可递归求解的问题（迷宫问题，汉诺塔问题）

先进先出

• 队尾插入元素：入队
• 队头删除元素：出队

1. 顺序队列（顺序表实现）
2. 链队（链表实现）
   • push 元素入队
   • pop 元素出队
   • front 返回队头元素

循环队列

使用：

• 脱机打印
• 多用户排队
• 不同优先级队列
• 接收先后处理问题

内容是字符的线性表

1. 串比较
2. 串赋值
3. 串相连
4. 求子串
5. 子串替换
6. 子串插入
7. 子串查找

操作方便，存储密度低

子串、前缀 匹配算法 KMP

• 根结点：无前驱结点的结点
• 结点的度：结点拥有的子树数。
• 叶子：终端结点，度= 0
• 分支结点：根结点以外的度 != 0
• 双亲结点，孩子结点。
• 兄弟结点：共同的双亲
• 结点的祖先：从根到该结点所经分支的所有结点
• 结点的子孙：以某结点为根的子树中任一结点
• 树的深度：结点的最大层次。

1. 深度遍历
   • 先序：根左右
   • 中序：左根右
   • 后序：左右根
2. 层次遍历

遍历应用：

• 建立二叉树
• 复制二叉树
• 计算二叉树深度
• 计算二叉树结点总数
• 计算二叉树叶子结点

• 无向图：每条边无方向
• 有向图：每条边有方向
• 完全图：任意两个点都有一条边相连
• 网：边/弧带权的图
• 邻接：有边/弧相连的两个顶点之间的关系
• 顶点的度：与该顶点相关联的边的数目
• 路径：持续的边构成的顶点序列
• 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
• 连通图（强连通图）任意两顶点存在路径
• 权与网 图中边或弧所具有的相关数称为权，表明一个顶点到另一个顶点的距离
• 带权的图称为网
• 子图
• 连通分量 无向图 G 的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是G连通子图，将G的任何不在孩子图中的顶点加入，子图不再连通。
• 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，该子图不再连通。
• 生成树：包含无向图G所有顶点的极小连通子图。不存在回路

• 查找顶点是否存在
• 查找边是否存在
• 顶点的邻接顶点
• 新增顶点
• 删除顶点（及相关的边）
• 新增边
• 删除边
• 深度优先遍历 DFS
• 广度优先遍历 BFS

使用：

1. Prim 算法构造最小生成树
   • 邻接矩阵表示
2. Kruskal 算法构造最小生成树
   • 邻接矩阵表示
   • 邻接表表示
3. Dijkstra 算法 求有向网的单源点最短路径
   • 邻接矩阵表示
   • 邻接表表示
4. Floyd 算法求有向网各个顶点间的最短路径
   • 邻接矩阵表示
   • 邻接表表示
5. 拓扑排序判断有向图中是否有环
   • 邻接矩阵表示
   • 邻接表表示
6. 关键路径
   • 邻接矩阵表示
   • 邻接表表示

有序表：二分查找

• 二叉搜索树 BST

  定义：左子树小于根结点；根结点小于右子树；中序遍历有序。

  • 查找时间复杂度 O(logN)，最坏 O(N);
  • 插入结点
  • 生成 BST: 插入每个元素。
  • 删除结点

• AVL 平衡二叉树

  为解决 BST 形态不均时查找效率O(N); 定义：每个结点平衡因子（左右子树高度差）绝对值小于等于1。

  • 失衡调整

• 红黑树

  自平衡二叉树，性质：

  1. 结点是红色或黑色；
  2. 根是黑色；
  3. 不能有连续的红色结点
  4. 从任一结点到每个叶子结点路径包含相同数量的黑色结点。
  5. 结论: 如果某结点只有一个子树，那么一定子树一定是红色的（如果是黑色的不满足4）
  6. 同5，红色结点不可能只有一个子树。

• 插入及失衡调整

• 删除及失衡调整

记录的存储位置与关键字之间存在对应关系，对应关系：hash 函数

1. 散列函数构造（直接定址法，除留余数法等）
2. 冲突解决 (开放定址法，拉链法)

• 插入排序

  每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

  • 直接插入排序 O(n^2)（采用顺序查找法查找插入位置）
  • 二分插入排序 O(n^2)（采用二分查找法查找插入位置）
  • 希尔排序

• 交换排序

  两两排序，如果发生逆序则交换，直到所有记录都排好序为止

  • 冒泡排序 O(n^2)（每趟不断将记录两两比较，并按“前小后大”规则交换。）
  • 快速排序 O(nlogN)
    • 任取一个元素为中心 pivot
    • 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
    • 对各子表重新选择中心元素依此规则调整
    • 直到每个子表中剩一个元素

• 选择排序

  每一趟从待排序的记录中选出最小的记录，按顺序放在已排序的记录最后，直到排完。

  • 简单选择排序 O(n^2)（在待排序的数据中选出最小的元素放在其最终位置。）
  • 堆排序 O(nlogN)
    • 根大于左右孩子：大根堆，根小于左右孩子：小根堆
    • 堆的调整
    • 堆的建立

• 归并排序 O(nLogN)

  将两个或两个以上的有序子序列归并为一个有序序列。

  • 2路归并排序

• 基数排序 O(k*(n + m))

  分配 + 收集。设置若干个箱子，将关键字为k的记录放入第k个箱子，然后再按序号将非空的箱子连接。