- Install VSCode.
- Follow the guide CMake Tools for Visual Studio Code.
- Install C/C++ extension for VS Code.
- Install CMake Tool extension for VS Code.
- Install MinGW-w64 via MSYS2 follow this guide
-
Download MSYS2 and install.
-
Open MSYS2 terminal and install MinGW-w64 toolchain by running
pacman -S --needed base-devel mingw-w64-ucrt-x86_64-toolchain
-
Add the MinGW-w64 folder to System PATH.
-
- install CMake and add CMake to System PATH.
- Open project in VS Code.
- From the command palette in VS Code, run the CMake: Configure command.
- From the command palette, run the CMake: Select a Kit.
- From the command palette, run the CMake: Run or click Run button from the status bar.
包含顺序表和链表。
顺序表 SqList
- 插入元素
- 删除元素
- 查找元素:按索引查找,按值查找
- 遍历等。
单链表 LinkList
- 插入元素:头插法,尾插法
- 删除元素
- 查找元素:按索引查找,按值查找
- 遍历等。
- 双向链表(前驱指针)
- 双向循环链表(头结点的前驱指向尾结点,尾结点后继指向头结点)
后进新出
- 栈顶插入元素:入栈
- 栈顶删除元素:出栈
使用:
- 数值转换
- 表达式求值
- 括号匹配检验
- 八皇后问题
- 函数调用
- 递归调用实现
栈与递归:
- 递归定义的数学函数(阶乘,斐波拉契数列)
- 具有递归特性的数据结构(二叉树)
- 可递归求解的问题(迷宫问题,汉诺塔问题)
先进先出
- 队尾插入元素:入队
- 队头删除元素:出队
循环队列
使用:
- 脱机打印
- 多用户排队
- 不同优先级队列
- 接收先后处理问题
内容是字符的线性表
- 串比较
- 串赋值
- 串相连
- 求子串
- 子串替换
- 子串插入
- 子串查找
操作方便,存储密度低
子串、前缀 匹配算法 KMP
- 根结点:无前驱结点的结点
- 结点的度:结点拥有的子树数。
- 叶子:终端结点,度= 0
- 分支结点:根结点以外的度 != 0
- 双亲结点,孩子结点。
- 兄弟结点:共同的双亲
- 结点的祖先:从根到该结点所经分支的所有结点
- 结点的子孙:以某结点为根的子树中任一结点
- 树的深度:结点的最大层次。
- 深度遍历
- 先序:根左右
- 中序:左根右
- 后序:左右根
- 层次遍历
遍历应用:
- 建立二叉树
- 复制二叉树
- 计算二叉树深度
- 计算二叉树结点总数
- 计算二叉树叶子结点
- 无向图:每条边无方向
- 有向图:每条边有方向
- 完全图:任意两个点都有一条边相连
- 网:边/弧带权的图
- 邻接:有边/弧相连的两个顶点之间的关系
- 顶点的度:与该顶点相关联的边的数目
- 路径:持续的边构成的顶点序列
- 简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径。
- 连通图(强连通图)任意两顶点存在路径
- 权与网 图中边或弧所具有的相关数称为权,表明一个顶点到另一个顶点的距离
- 带权的图称为网
- 子图
- 连通分量 无向图 G 的极大连通子图称为G的连通分量。 极大连通子图意思是:该子图是G连通子图,将G的任何不在孩子图中的顶点加入,子图不再连通。
- 极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,该子图不再连通。
- 生成树:包含无向图G所有顶点的极小连通子图。不存在回路
邻接矩阵(顺序表实现)
邻接表(链表实现)
- 查找顶点是否存在
- 查找边是否存在
- 顶点的邻接顶点
- 新增顶点
- 删除顶点(及相关的边)
- 新增边
- 删除边
- 深度优先遍历 DFS
- 广度优先遍历 BFS
使用:
- Prim 算法构造最小生成树
- Kruskal 算法构造最小生成树
- Dijkstra 算法 求有向网的单源点最短路径
- Floyd 算法求有向网各个顶点间的最短路径
- 拓扑排序判断有向图中是否有环
- 关键路径
有序表:二分查找
-
二叉搜索树 BST
定义:左子树小于根结点;根结点小于右子树;中序遍历有序。
-
为解决 BST 形态不均时查找效率O(N); 定义:每个结点平衡因子(左右子树高度差)绝对值小于等于1。
-
自平衡二叉树,性质:
- 结点是红色或黑色;
- 根是黑色;
- 不能有连续的红色结点
- 从任一结点到每个叶子结点路径包含相同数量的黑色结点。
- 结论: 如果某结点只有一个子树,那么一定子树一定是红色的(如果是黑色的不满足4)
- 同5,红色结点不可能只有一个子树。
操作 | BST | AVL 树 | 红黑树 |
---|---|---|---|
搜索 | 平均:O(log n) | 平均:O(log n) | 平均:O(log n) |
最坏:O(n) | 最坏:O(log n) | 最坏:O(log n) | |
插入 | 平均:O(log n) | 平均:O(log n) | 平均:O(log n) |
最坏:O(n) | 最坏:O(log n) | 最坏:O(log n) | |
删除 | 平均:O(log n) | 平均:O(log n) | 平均:O(log n) |
最坏:O(n) | 最坏:O(log n) | 最坏:O(log n) | |
平衡维护 | 不适用 | 平均:O(log n) | 不适用 |
最坏:O(log n) | |||
空间复杂度 | 平均:O(n) | 平均:O(n) | 平均:O(n) |
最坏:O(n) | 最坏:O(n) | 最坏:O(n) |
记录的存储位置与关键字之间存在对应关系,对应关系:hash 函数
- 散列函数构造(直接定址法,除留余数法等)
- 冲突解决 (开放定址法,拉链法)