复习.

Presentation on theme: "复习."— Presentation transcript:

1 复习

2 第1章 主要内容： 数据结构基本概念和术语 算法概念和特点 算法分析的衡量标准 重点：计算时间复杂度（习题）

3 第2章 主要内容： 线性表的定义和特点 线性表的顺序存储及查找、插入和删除 线性链表的链式存储及查找、插入和删除操作
插入删除时元素的平均移动次数 线性链表的链式存储及查找、插入和删除操作

4 第3章-第5章 主要内容: 栈的定义及实现 队列的定义及基本操作 串（基本概念、朴素模式匹配算法） 数组的定义 矩阵的压缩存储 栈的定义
实现入栈，出栈 队列的定义及基本操作 循环队列求长度、入队、出队 串（基本概念、朴素模式匹配算法） 数组的定义 矩阵的压缩存储 特殊矩阵 稀疏矩阵

5 例1： 对于一个栈，给出输入项A、B、C，如果输入项序列 由ABC组成，试给出所有可能的输出序列。 A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB

6 例2：设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。

7 分析：本题算法思想是引入形式参数flag，当形式参数flag的值为1时表示对栈1进行操作，flag的值为2时表示对栈2进行操作。
typedef struct {int s[m]; int top1; int top2;} sqstack; void push(sqstack &stack , int x,int flag) { if (stack.top1+1==stack.top2) printf(“stack is full\n”); else { if (flag==1) {stack.top1++; stack.s[stack.top1]=x;} else if(flag==2){stack.top2--; stack.s[stack.top2]=x;}else printf(“input error\n”); } void pop(sqstack &stack , int &y, int flag) { if (flag==1) if(stack.top1<0) printf(“empty\n”); else { y=stack.s[stack.top1];stack.top1--; } else if(flag==2) if(stack.top2>=m) printf(“empty\n”); else { y=stack.s[stack.top2];stack.top2++; } else printf(“input error\n”);

8 例3：设二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m
例3：设二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m*n个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为1000+(i*n+j)*L。

9 第6章 树 主要内容: Huffman树 树的定义及相关术语 二叉树的定义、性质、存储结构（顺序、二叉链表）
第6章 树 主要内容: 树的定义及相关术语 二叉树的定义、性质、存储结构（顺序、二叉链表） 二叉树的遍历方法及递归遍历算法的实现 森林与二叉树的转换 Huffman树

10 二叉树的定义及性质 定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。
逻辑结构： 一对二（1：2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒（有序树）。 基本形态： 问：具有3个结点的二叉树可能有几种不同形态？普通树呢？ 5种/2种

11 二叉树的存储结构 T[0] T[1] T[2] T[3] T[4] T[5] T[6] T[7] T[8] 1 2 3 4 5 6 7 8
9 2 3 4 5 6 7 8 9 顺序存储结构 按二叉树的结点“自上而下、 从左至右”编号，用一组连续 的存储单元存储.

12 A 先序遍历的结果是： A B D E C B C 中序遍历的结果是： D B E A C D E 后序遍历的结果是： D E B C A
口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根

13 例6-1：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。
分析： ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

14 中序遍历：B D C E A F H G 后序遍历：D E C B H G F A

15 例6-2 树的存储方式：孩子兄弟表示法 以二叉链表作为存储结构。 结点结构： fch data nsib fch:指向该结点的第一个孩子结点 nsib：指向该结点的下一个兄弟结点 typedef struct csNode{ ElemType data; struct csNode *firstchild,*nextsibling; }csNode,*csTree; 表示：

16 A ^ B ^ E D ^ F ^ ^ H ^ ^ C ^ G ^ M ^ 例： G B D C E F H M A 二叉链表： A ^ B ^ E D ^ F ^ ^ H ^ ^ C ^ G ^ M ^

17 例6-3 森林与二叉树之间的相互转化 森林转二叉树举例：
例6-3 森林与二叉树之间的相互转化 森林转二叉树举例： A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I A 兄弟相连 长兄为父 孩子靠左 头根为根

18 即B={root, LB, RB} F={T1, T2, …,Tm}
二叉树如何还原为森林？ 即B={root, LB, RB} F={T1, T2, …,Tm} 要点：把最右边的子树变为森林，其余右子树变为兄弟 G H J I A B C D E F G H J I A B C D E F A B C D E F G H J I

19 例6-4 Huffman树 以数据集{7, 19, 2, 6, 32, 3, 21, 10}为结点权值，画出Huffman树，并计算其带权路径长度。 5 6 11 10 7 32 17 28 21 19 40 60 100 1 Huffman码的WPL＝2( ) + 4(7+6+10) +5(2+3) =261 2 3

20 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用

21 度：与每个顶点相连的边的数叫该点的度。记为TD(V) 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度
7.1 图的定义和术语 有向图：0 ≤ e ≤ n(n-1) 有向完全图 e = n(n-1) 无向图：0 ≤ e ≤ ½ n(n-1) 完全图 e = ½ n(n-1) 度：与每个顶点相连的边的数叫该点的度。记为TD(V) 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目，记为ID(V) 出度：以该顶点为尾的弧的数目，记为OD(V)

22 7.2 图的存储结构 邻接矩阵 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2
无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和

23 题型：图、邻接矩阵、邻接表三者之间的转化
从无向图的邻接表可以得到如下结论： 无向图中顶点Vi的度为第i个单链表中的结点数 所有链表中结点数目的一半为图中边数； 占用的存储单元数目为n+2e 。 从有向图的邻接表可以得到如下结论： 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 所有链表中结点数目为图中弧数； 占用的存储单元数目为n+e 。 题型：图、邻接矩阵、邻接表三者之间的转化

24 7.3 图的遍历 深度优先遍历(DFS) 广度优先遍历(BFS)

25 V0 V1 V3 V4 V2 V6 V5 V7 例 深度遍历：V0 V2  V6  V5  V1  V3  V7  V4 1 2 3 v0 v2 v3 v1 vexdata firstarc 6 7 ^ adjvex next 4 v4 5 v5 v6 v7

26 7.4 求最小生成树 普里姆算法（归并顶点，适用于稠密网） 克鲁斯卡尔（kruskal）算法

27 例如:克鲁斯卡尔算法 a a b b c c e e g g d d f f 19 19 5 5 12 12 14 14 7 7 18 18
16 16 8 8 3 3 g g d d 27 21 21 f f

28 例如:普里姆(prim)算法 a a b b c c e e g g d d f f 所得生成树权值和
19 a a b b 5 5 12 14 14 c c 7 18 e e 8 8 16 16 3 3 g g d d 27 21 21 f f 所得生成树权值和 = = 67

29 7.5 1 拓扑排序 AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网

30 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8 或 ：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 一个AOV网的拓扑序列不是唯一的

31 5 1 6 4 3 2 8 30 13 7 17 32 9 终点 从V0到各终点的最短路径及其长度 V1 V2 V3 V4 V5 V6 Vj
8 30 13 7 17 32 9 2. 最短路径的求法：迪杰斯特拉(Dijkstra)算法 终点 从V0到各终点的最短路径及其长度 V1 V2 V3 V4 V5 V6 Vj 13 <V0,V1> 8 <V0,V2>  30 <V0,V4> 32 <V0,V6> V2:8 13 <V0,V1> <V0,V2,V3> 30 <V0,V4>  32 <V0,V6> V1:13 13 <V0,V2,V3> 30 <V0,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V3:13 19 <V0,V2,V3,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V4:19 21 <V0,V2,V3,V4,V5> 20 <V0,V1,V6> V6:20 <V0, V1,V6>

32 作业 已知无向图G的邻接矩阵， 按要求完成下列各题。 给出无向图G中各顶点的度数； 给出无向图G的邻接表；
分别给出应用Kruskal和Prim算法构造最小生成树的过程。 答案：TD(v1)=TD(v2)=TD(v3)=TD(v4)=3，TD(v5)=4 v1->1->3->4；v2->0->2->4；v3->1->3->4；v4->0->2->4；v5->0->1->2->3 Prim算法：(v1，v2)，(v2，v3)，(v2，v5)，(v5，v4) Kruskal算法：(v2，v5)，(v2，v3)，(v2，v1)，(v5，v4)

33 考研题 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： ①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点； ②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v； ③重复步骤②，直到u是目标顶点时为止。 请问（1）上述方法能否求得最短路径？（2）若该方法可行，请证明之；否则，请举例说明。

34 该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。

35 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 顺序查找（线性查找） 折半查找（二分或对分查找） 二叉排序树
第9章 查找 9.1 静态查找表 顺序查找（线性查找） 折半查找（二分或对分查找） 9.2 动态查找表 二叉排序树 平衡二叉树 9.3 哈希表

36 9.1 静态查找表 顺序查找（线性查找） 把待查关键字key存入表头或表尾（俗称“哨兵”），目的在于免去查找过程中每一步都要检测整个表是否查找完毕，这样可以加快执行速度。

37 9.1 静态查找表 折半查找（二分或对分查找） 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 设定3个辅助标志: low,high,mid Low指向待查元素所在区间的下界 high指向待查元素所在区间的上界 mid= (low+high)/2

38 9.2 动态查找表 二叉排序树、平衡二叉树 基本概念 二叉排序树的插入和查找操作 构造一棵平衡二叉排序树

39 例：输入待查找的关键字序列=（45，24，53，45，12，24，90）
2. 二叉排序树的插入和查找操作 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90）， 查找成功，返回 查找成功，返回 24 则生成的二叉排序树形态不同： 12 53 90 45

40 例：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53）
例：请将下面序列构成一棵平衡二叉排序树： （ 13，24，37，90，53） 需要RL平衡旋转 (绕C先顺后逆） 13 37 24 -1 24 13 -2 13 -1 13 24 37 90 53 -1 37 -2 37 -1 24 需要RR平衡旋转 (绕B逆转,B为根） 90 37 1 90 53 90 53 37

41 9.3 哈希表 哈希表的概念 哈希函数的构造方法 冲突处理方法 除留余数法 开放定址法（开地址法）：线性探测法
特点：取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址。H (key)=key mod p (p是一个整数) 技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是不包含小于20质因子的合数）。 冲突处理方法 开放定址法（开地址法）：线性探测法

42 第7章 排序 直接插入排序 冒泡排序 折半插入 简单选择排序 题型：已知一序列，给出排序过程。

43 算法题 线性表的链式存储结构 二叉树的操作 数据类型定义 基本操作：创建、插入、删除、查找 二叉链表数据类型定义 二叉树的递归遍历算法
前序、中序、后序 构造二叉树/求二叉树的叶子结点数、交换二叉树等。