最新军队文职-计算机类计算机类-数据结构与算法知识点总结

精品文档 一个孩子 一个兄弟 树的遍历

树的结构：①根，②根的子树。

先根遍历：①②。例：ABCDEFGHIJK。 后根遍历：②①。例：CEDFBHGJKIA。 遍历森林

森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。 先序遍历：①②③。例：ABCDEFGHIJ。 中序遍历：②①③。例：BDCEAGFIJH。

注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。

A B C D E 树的结构划

森林的结构划分

F G H J ① I ② K ② ① B A C D E F G I H J ③ 孩子 孩子 遍历树、森林与遍历二叉树的关系 遍历树、森林和二叉树的关系 树 森林 根遍历

根遍历 8.

序遍历 序遍历

二叉树 序遍历 序遍历

哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树

构造赫夫曼树

每次取两个最小的树组成二叉树 赫夫曼编码(前缀码)

向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。

五、 图

精品文档

精品文档

1．

完全图：有1\\2 n(n-1)条变得无向图

有向完全图：具有n（n-1）条弧的有向图。 权：与图的边或弧相关的数。

顶点v的度：和v相关联的边的数目。 入度：以顶点v为头的弧的数目 出度：以顶点v为尾的弧的数目

回路或环：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 2. 图的存储结构

·邻接矩阵：

A 0 1 1 0 0 B 0 0 1 1 0 C 0 0 0 1 0 D 1 0 0 0 0 E 1 0 0 1 0 ·邻接表： typedef struct ArcNode { // 弧结点 int adjvex; struct ArcNode *nextarc; } ArcNode;

typedef struct VexNode { // 顶点结点 VertexType data;

ArcNode *firstarc; // 第一个邻接点 } VexNode;

const int MAX_VERTEX = 最大顶点个数; typedef struct Graph { // 图 VexNode vexs[MAX_VERTEX]; int vexnum, arcnum; } Graph;

// 邻接点

// 下一个邻接点

// 顶点信息

// 顶点向量

// 顶点和弧的个数

边(弧)多则需要存储空间多。

0 A 1 2 /\\ 1 B 2 3 /\\ 2 C 3 /\\ 3 D 0 /\\ 4 E 0 3 /\\

·十字链表：

十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。

精品文档

精品文档 ·邻接多重表 3. 图的遍历

1) 深度优先（DFS）搜索

访问方式：从图中某顶点v出发： a）访问顶点v；

b）从v的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束。 2) 广度（宽度，BFS）优先搜索 a）访问顶点v ；

b）访问同v相邻的所有未被访问的邻接点w1,w2, …wk；

c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 4. 生成树和最小生成树

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。 1) 最小生成树 ·Kruskal算法 一句话，“不构成环的情况下，每次选取最小边”。

5 B 3 1 A 3 E 3 C 5 B 3 1 A 3 E 3 C 2 6 7 D (d) B 2 6 7 D (a) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (e) B 2 6 7 D (b) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (f) 2 6 7 D (c) ·普里姆算法

记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。 普里姆算法：

(a) 开始时，U={v0}，TE=Φ；

(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE； (c) 重复(b)直到U=V。

普里姆算法和克鲁斯卡尔算法的比较 法 里姆算法 鲁斯卡尔算法 间复杂度 点

)

与顶点个数n有关 边的数目e无关 用于稠密图

loge)

与边的数目e有关 顶点个数n无关 用于稀疏图

精品文档

精品文档

5. AOV-网

用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。 拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。 拓扑排序的方法

(1)在有向图中选一个没有前驱的顶点且输出之 (2)从图中删除该顶点和所有以它为尾的弧

6. 关键路径 AOE网，关键路径

AOE网(Activity On Edge)——带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。

7. 最短路径

(1) 迪杰斯特拉算法

求一个顶点到其他各顶点的最短路径。

算法：(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；

(c) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。 (d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。

(2) 弗洛伊德算法

求每对顶点之间的最短路径。

依次计算A(0)，A(1)，…，A(n)。A(0)为邻接矩阵，计算A(k)时，A(k)(i,j)=min{A(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)}。 技巧：计算A(k)的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)与A(i,k)+A(k,j) （“行+列”），如果后者更小则替换A(i,j)，同时修改路径。

六、 查找

1. 查找分为：静态查找表、动态查找表、哈希查找表 2. 静态查找表：对查找表只作查找操作的查找表。

动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。

3. 顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链

表。

4. 二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递

精品文档