快速掌握数据结构

admin123

2021 年 02 月 24 日

2597 次浏览

暂无评论

加载中

1932字数

学习笔记

# 1 线性表

# 2 栈与队列

# 3 串

1. 串的定义：
   
   > 限制元素为字符的线性表
2. 串的匹配算法：
   
   > - 简单模式匹配算法
   > - KMP算法（线性算法）O(m+n)
   > - KMP算法的改进

# 4 数组、矩阵和广义表

# 5 树与二叉树

1. 概念：树的度、节点的度、高度
   
   > 树的度：树中各节点度的最大值
   > 节点的度：节点拥有的子树个数或分支的个数
   > 高度：树中节点的最大层次
2. 二叉树的先序、中序、后序和层次遍历
   
   > 先序遍历过程（递归）（也可使用栈）：
   > 如果二叉树为空树，则什么都不做；否则
   > 
   > 1) 访问根节点
   > 2) 先序遍历左子树
   > 3) 先序遍历右子树
   
   > 中序、后序遍历类似，只是访问根节点操作分别位于中间、后面。
   
   > 层序遍历过程：
   > 建立一个循环队列，将二叉树头节点入队列，然后出队列，访问该节点，如果它有左子树，则将左子树的根节点入列，如果有右子树，则右子树根节点入列，然后出列，对出队节点访问，如此，直到队列为空。
   
   > 应用：
   > 后序：求表达式的值
   > 中序：求二叉树的深度
3. 哈弗曼树和哈弗曼编码
4. 平衡二叉树

# 6 图

1. 图的遍历操作
   
   > DFS（递归、栈）
   > 类似于二叉树的先序遍历。基本思想：首先访问出发点v，并将其标注为已访问过；然后选取与v邻接的未被访问的任意一个顶点w，并访问，再选取与w邻接的未被访问的任意一个顶点，重复。当一个顶点的所有邻接顶点都被访问过时，依次退回最近被访问过的顶点。直到图中所有节点都被访问为止。
   
   > BFS（队列）
   > 类似与二叉树的层次遍历。
2. 最小生成树
   
   > 普利姆算法：
   > 从图中任意取出一个顶点，把它作为一颗树，然后从与这棵树相邻的边中选取一条最短的边，加入这棵树......重复直到所有节点加入树中。
   > 复杂度：n^2，适用于稠密图
   
   > 克鲁斯卡尔算法：
   > 每次从候选边（与当前树不构成回路的边）中选中权值最小的边，加入生成树，直到所有的边都被检查完。
   > 适用于：稀疏图
3. 最短路径
   
   > **迪杰斯特拉算法：** n^2
   > 通常用来求图中某一顶点到其余各顶点的最短路径。
   > **思想：**
   > 设有两个顶点集合S和T，**集合S中存放图中已找到最短路径的顶点**，集合T存放图中剩余顶点。
   > 初始状态，S只含有源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点vu并入S中。
   > 集合S每并入一个新的顶点，**都要修改顶点v0到集合T中顶点的最短路径长度值(即是否通过vu到达vo路径更短)**。
   > 不断重复，直达T顶点全部并入S中为止。
   
   > **弗洛伊德算法：** n^3
   > 动态规划，代码较简单，
   > 关键代码:
   
   ```
   for k in range(len(distance)):
       for i in range(len(distance)):
           for j in range(len(distance)):
               if distance[i][j] > distance[i][k] + distance[k][j]:
                   distance[i][j] = distance[i][k] + distance[k][j]
   ```

# 7 排序

[查看博客](https://blog.csdn.net/qq_39041210/article/details/99690378)

# 8 查找

[查看博客](https://blog.csdn.net/qq_39041210/article/details/99690378)

---
转载至CSDN博主：[[李唐敏民](https://blog.csdn.net/qq_39041210 "李唐敏民")]
-----------------------
---

快速掌握数据结构