1 线性表

2 栈与队列

3 串

  1. 串的定义:

限制元素为字符的线性表

  1. 串的匹配算法:
  • 简单模式匹配算法
  • KMP算法(线性算法)O(m+n)
  • KMP算法的改进

4 数组、矩阵和广义表

5 树与二叉树

  1. 概念:树的度、节点的度、高度

树的度:树中各节点度的最大值
节点的度:节点拥有的子树个数或分支的个数
高度:树中节点的最大层次

  1. 二叉树的先序、中序、后序和层次遍历

先序遍历过程(递归)(也可使用栈):
如果二叉树为空树,则什么都不做;否则

1) 访问根节点
2) 先序遍历左子树
3) 先序遍历右子树

中序、后序遍历类似,只是访问根节点操作分别位于中间、后面。

层序遍历过程:
建立一个循环队列,将二叉树头节点入队列,然后出队列,访问该节点,如果它有左子树,则将左子树的根节点入列,如果有右子树,则右子树根节点入列,然后出列,对出队节点访问,如此,直到队列为空。

应用:
后序:求表达式的值
中序:求二叉树的深度

  1. 哈弗曼树和哈弗曼编码
  2. 平衡二叉树

6 图

  1. 图的遍历操作

DFS(递归、栈)
类似于二叉树的先序遍历。基本思想:首先访问出发点v,并将其标注为已访问过;然后选取与v邻接的未被访问的任意一个顶点w,并访问,再选取与w邻接的未被访问的任意一个顶点,重复。当一个顶点的所有邻接顶点都被访问过时,依次退回最近被访问过的顶点。直到图中所有节点都被访问为止。

BFS(队列)
类似与二叉树的层次遍历。

  1. 最小生成树

普利姆算法:
从图中任意取出一个顶点,把它作为一颗树,然后从与这棵树相邻的边中选取一条最短的边,加入这棵树......重复直到所有节点加入树中。
复杂度:n^2,适用于稠密图

克鲁斯卡尔算法:
每次从候选边(与当前树不构成回路的边)中选中权值最小的边,加入生成树,直到所有的边都被检查完。
适用于:稀疏图

  1. 最短路径

迪杰斯特拉算法: 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 排序

查看博客

8 查找

查看博客


转载至CSDN博主:[李唐敏民]


最后修改:2021 年 02 月 24 日 02 : 11 PM
如果觉得我的文章对你有用,请随意赞赏