数据结构(王红梅).ppt

《数据结构(王红梅).ppt》由会员分享，可在线阅读，更多相关《数据结构(王红梅).ppt（166页珍藏版）》请在三一办公上搜索。

1、考试题型,一、填空 10题，每题一分，共10分二、选择 10题，每题一分，共10分三、解答题 6题，共55分四、算法设计 3题，共25分,成绩组成卷面成绩：100*70%=70平时成绩：20实验成绩：10,题型示例,已知一个连通图如图1所示，试给出图的邻接矩阵存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。,图1 连通图,题型示例,已知一个连通图如图1所示，试给出图的邻接矩阵存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。,深度优先遍历序列:v1 v2 v3 v5 v4 v6广度优先遍历序列:v1

2、v2 v4 v3 v5 v6,题型示例,设计算法，计算采用邻接矩阵存储有向图中出度为零的顶点个数。,int SumZero(AdjMatrix A)count=0;for(i=0;iA.vertexNum;i+)tag=0;for(j=0;jA.vertexNum;j+)if(arcsij!=0)tag=1;break;if(tag=0)count+;return count;,第一章 知识结构图,通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。,1.3 数据结构的基本概念,数据结构的基本概念,通常有两种存储结构：1.顺

3、序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2.链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。,例：（bat,cat,eat）,1.3 数据结构的基本概念,数据结构的基本概念,bat0200,cat0325,eat,数据的操作：插入、删除、修改、检索、排序等,1.3 数据结构的基本概念（小结）,算法分析,算法分析（Algorithm Analysis）：对算法所需要的计算机资源时间和空间进行估算。时间复杂性（Time Complexity）空间复杂性（Space Complexity）,1.4 算法及算法

4、分析,问题规模：输入量的多少。基本语句：是执行次数与整个算法的执行次数成正比的操作指令。,问题规模：n基本语句：x+,1.4 算法及算法分析,算法分析,for(i=1;i=n;i+)for(j=1;j=n;j+)x+;,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,1.4 算法及算法分析,算法分析大O符号,线 性 表,逻辑结构,存储结构,基本概念,抽象数据类型定义,线性表定义逻辑特征,ADT定义基本操作,顺序存储,链接存储,其他存储,顺序表的特点顺序表类定义基本操作的实现

5、及时间性能,单链表的特点单链表类定义基本操作的实现及时间性能,比 较,循环链表双链表静态链表间接寻址,第二章 知识结构图,线性表：简称表，是n（n0）个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L（a1,a2,ai-1,ai,an),2.1 线性表的逻辑结构,线性表的定义,其中，ai（1in）称为数据元素；下角标 i 表示该元素在线性表中的位置或序号。,2.1 线性表的逻辑结构,线性表的图形表示,线性表（a1,a2,ai-1,ai,an)的图形表示如下：,2.2 线性表的顺序存储结构及实现,顺序表线性表的顺序存

6、储结构,例：（34,23,67,43）,34,23,67,43,4,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空闲,长度,Loc(ai)=Loc(a1)+(i-1)c,随机存取：在O(1)时间内存取数据元素,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：,单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链表,头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,2.3 线性表的链接存储结构及实现,单链表,

7、非空表,单链表的实现按位查找,操作接口：T Get(int i);,核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。,2.3 线性表的链接存储结构及实现,first,a1,a2,an,ai,单链表的实现插入,操作接口：void Insert(int i,T x);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1、x和ai之间逻辑关系的变化？,算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;,静态链表：用数组来表示单链表，用数组元素的下标来模拟单链表

8、的指针。,静态链表,2.5 线性表的其它存储方法,data：存储放数据元素；next：也称游标，存储该元素的后继在数组的下标。,数组元素（结点）的构成：,数据域,指针域,例：线性表(张，王，李，赵，吴)的静态链表存储,012345678,2.5 线性表的其它存储方法,data next,静态链表,first,avail,first：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点；avail：空闲链表头指针，空闲链表由于只在表头操作，所以不带头结点；,特殊线性表,栈,队 列,串,栈的定义操作特性ADT定义,队列定义操作特性ADT定义,串的定义基本概念ADT定义,顺序栈,链栈,循环队

9、列,链队列,顺序存储,链接存储,逻辑结构,存储结构,逻辑结构,逻辑结构,存储结构,存储结构,比 较,模式匹配,比较,比较,基本操作的实现时间性能,基本操作的实现时间性能,第三章 知识结构图,特殊线性表栈,栈的逻辑结构,栈：限定仅在表尾进行插入和删除操作的线性表。,线性结构：栈元素具有线性（即前驱后继）关系。限制操作：限制了线性表插入和删除的位置。单向延伸性：栈底是固定的，栈顶随着插入和删除操作的进行而变化。插入：也称进栈、压栈、入栈；删除：也称出栈、弹栈。,特殊线性表栈,a,出栈序列：a,出栈序列：a、b,出栈序列：a、b、c,b,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一

10、次栈，则可能的出栈序列有多少种？,栈的逻辑结构,情况5：,c,注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。,c b a,、b c a,、b a c,、a c b,、a b c,栈的顺序存储结构及实现,顺序栈栈的顺序存储结构,如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,特殊线性表栈,附设指针top指示栈顶元素在数组中的位置。,栈的链接存储结构及实现,栈顶,栈底,链栈：栈的链接存储结构,特殊线性表栈,两种示意图在内存中对应同一种状态,栈顶,栈底,特殊线性表队列,队列的逻辑结构,空队列：不含任何数据元素的队列。,队列：只允许在一端进行插

11、入操作，而另一端进行删除操作的线性表。,允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。,（a1,a2,an）,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,特殊线性表队列,队列的顺序存储结构及实现,继续入队会出现什么情况？,a3,a4,a5,循环队列：将存储队列的数组头尾相接。,特殊线性表队列,队列的顺序存储结构及实现,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,特殊线性表队列,不存在物理的循环结构，用软件方法实现。求模：（41）mod 50,队列的顺序存

12、储结构及实现,如何实现循环队列？,0 1 2 3 4,入队,出队,a3,a4,a6,a5,队满的条件：(rear+1)mod QueueSize=front,队列的顺序存储结构及实现,特殊线性表队列,第五章 知识结构图,树的定义,树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,5.1 树的逻辑结构,树的定义是采用递归方法,树的定义,5.1 树的逻辑结构,下标 data parent,5.2 树的存

13、储结构,双亲表示法,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,5.2 树的存储结构,孩子兄弟表示法,如何查找兄弟结点？时间性能？,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.3 二叉树的逻辑结构,问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。,研究二叉树的意义？,完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的

14、位置完全相同。,5.3 二叉树的逻辑结构,特殊的二叉树,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,5.3 二叉树的逻辑结构,前序（根）遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。,5.3 二叉树的逻辑结构,前序遍历序列：A B D G C E F,二叉树的遍历操作,中序（根）遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。,5.3 二叉树的逻辑结构,中序遍历序列：D G B A E C

15、F,二叉树的遍历操作,后序（根）遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；,5.3 二叉树的逻辑结构,后序遍历序列：G D B E F C A,二叉树的遍历操作,层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.3 二叉树的逻辑结构,层序遍历序列：A B C D E F G,二叉树的遍历操作,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHF

16、I，如何构造该二叉树呢?,5.3 二叉树的逻辑结构,二叉树的遍历操作,前序：A B C D E F G H I中序：B C A E D G H F I,前序：B C中序：B C,5.3 二叉树的逻辑结构,前序：D E F G H I中序：E D G H F I,前序：F G H I中序：G H F I,5.3 二叉树的逻辑结构,前序：D E F G H I中序：E D G H F I,顺序存储结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以

17、唯一地反映出结点之间的逻辑关系。,5.4 二叉树的存储结构及实现,完全二叉树的顺序存储,5.4 二叉树的存储结构及实现,以编号为下标,二叉链表,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。,5.4 二叉树的存储结构及实现,二叉链表,5.4 二叉树的存储结构及实现,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系 树：兄弟关系二叉树：双亲和右孩子 树：双亲和长子二

18、叉树：双亲和左孩子,5.5 树、森林与二叉树的转换,2.保留双亲与第一孩子连线,删去与其他孩子的连线,树和二叉树之间的对应关系,1.兄弟加线,3.顺时针转动,使之层次分明,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,2.保留双亲与第一孩子连线,删去与其他孩子的连线,1.兄弟加线,A,B,C,D,E,F,G,3.顺时针转动,使之层次分明,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,2.保留双亲与第一孩子连线,删去与其他孩子的连线,1.兄弟加线,5.5 树、森林与二叉树的转换,二叉树转换为树或森林,加线若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、，

19、都与结点y用线连起来；去线删去原二叉树中所有的双亲结点与右孩子结点的连线；层次调整整理由、两步所得到的树或森林，使之层次分明。,5.5 树、森林与二叉树的转换,5.5 树、森林与二叉树的转换,哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。,例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。,5.6 哈夫曼树及哈夫曼编码,WPL=32 WPL=41 WPL=30,第1步：初始化,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,第2步：选取与合并,第3步：删除与加入,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈

20、夫曼编码,重复第2步,5,4,3,2,5,重复第3步,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,重复第2步,重复第3步,5.6 哈夫曼树及哈夫曼编码,前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可能。,例：一组字符A,B,C,D,E,F,G出现的频率分别是9,11,5,7,8,2,3，设计最经济的编码方案。,哈夫曼树应用哈夫曼编码,9,11,5,5.6 哈夫曼树及哈夫曼编码,哈夫曼树应用哈夫曼编码,A,B,C,D,E,F,G,9,11,5,7,8,2,3,5.6 哈夫曼树及哈夫曼编码,编码方案：A：00B：10C：010D

21、：110E：111F：0110G：0111,哈夫曼树应用哈夫曼编码,第六章 知识结构图,连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。,6.1 图的逻辑结构,图的基本术语,如何求得一个非连通图的连通分量?,6.1 图的逻辑结构,V1,V2,V3,V4,V5,V6,V7,图的基本术语,连通分量是对无向图的一种划分。,强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图

22、。强连通分量：非强连通图的极大强连通子图。,6.1 图的逻辑结构,图的基本术语,如何求得一个非连通图的连通分量?,6.1 图的逻辑结构,图的基本术语,V1,V2,生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。,生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。,如何理解极小连通子图?,6.1 图的逻辑结构,图的基本术语,6.1 图的逻辑结构,1.深度优先遍历,基本思想：,访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。,

23、6.1 图的逻辑结构,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1 图的逻辑结构,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V5,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1 图的逻辑结构,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,V8,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1 图的逻辑结构,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1 图的逻辑结构,V1,遍历序列：,V1,V7,V2,V4,V5,V8,V

24、3,V3,V6,V6,V7,2.广度优先遍历,基本思想：,访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。,6.1 图的逻辑结构,广度优先遍历序列?入队序列?出队序列?,6.1 图的逻辑结构,遍历序列：,V1,V1,广度优先遍历序列?入队序列?出队序列?,6.1 图的逻辑结构,遍历序列：,V1,V2,V2,V3,V3,广度优先遍历序列?入队序列?出队序列?,6.1 图的逻辑结构,遍历序列：,V1,V2,V3,V3,

25、V4,V4,V5,V5,广度优先遍历序列?入队序列?出队序列?,6.1 图的逻辑结构,遍历序列：,V1,V2,V3,V4,V4,V5,V5,V6,V6,V7,V7,广度优先遍历序列?入队序列?出队序列?,6.1 图的逻辑结构,遍历序列：,V1,V2,V3,V4,V5,V5,V6,V6,V7,V7,V8,V8,邻接矩阵（数组表示法）,基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。,6.2 图的存储结构及实现,假设图G(V，E)有n个顶点，则邻接矩阵是一个nn的方阵，定义为：,无向图的邻接矩阵的特点？,无向图的邻接矩阵,6.2 图的存储结构

26、及实现,主对角线为 0 且一定是对称矩阵。,6.2 图的存储结构及实现,无向图的邻接表,边表中的结点表示什么？,每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。,基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U=u0（u0V），TE=，重复执行下述操作：在所有uU，vV-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。,关键:是如何找到连接U和V-U的最短边。,普里姆（Prim）算法,应用举例最小生成树,利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的

27、最短边。,U=A V-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19,25,12,34,19,26,46,38,17,25,应用举例最小生成树,Prim算法,Prim算法,应用举例最小生成树,25,12,34,19,26,46,38,17,25,U=A,F V-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26,Prim算法,应用举例最小生成树,25,12,34,19,26,46,38,17,25,U=A,F,C V-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26,Prim算

28、法,应用举例最小生成树,25,12,34,19,26,46,38,17,25,U=A,F,C,D V-U=B,Ecost=(A,B)34,(F,E)26,Prim算法,应用举例最小生成树,25,12,34,19,26,46,38,17,25,U=A,F,C,D,E V-U=Bcost=(E,B)12,Prim算法,应用举例最小生成树,25,12,34,19,26,46,38,17,25,U=A,F,C,D,E,B V-U=,克鲁斯卡尔（Kruskal）算法,基本思想：设无向连通网为G(V,E)，令G的最小生成树为T(U,TE)，其初态为UV，TE，然后，按照边的权值由小到大的顺序，考察G的边集

29、E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。,应用举例最小生成树,25,12,34,19,26,46,38,17,25,应用举例最小生成树,连通分量A,B,C,D,E,F,25,12,34,19,26,46,38,17,25,应用举例最小生成树,连通分量A,B,C,D,E,F,连通分量A,B,E,C,D,F,25,12,34,19,26,46,38,17,25,应

30、用举例最小生成树,连通分量A,B,E,C,D,F,连通分量A,F,B,E,C,D,25,12,34,19,26,46,38,17,25,应用举例最小生成树,连通分量A,F,B,E,C,D,连通分量A,F,B,E,C,D,25,12,34,19,26,46,38,17,25,应用举例最小生成树,连通分量A,F,B,E,C,D,连通分量A,F,C,D,B,E,25,12,34,19,26,46,38,17,25,应用举例最小生成树,连通分量A,F,C,D,B,E,连通分量A,F,C,D,B,E,应用举例最短路径,最短路径,在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。,AE：100

31、ADE：90 ADCE：60 ABCE：70,问题描述：给定带权有向图G(V,E)和源点vV，求从v到G中其余各顶点的最短路径。,单源点最短路径问题,应用举例最短路径,应用实例计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。,迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。,基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,vk，就将vk加入集合S中，并将路径v,vk,vi与原来的假设相比较，

32、取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。,Dijkstra算法,应用举例最短路径,10,50,30,10,100,20,60,S=AAB:(A,B)10AC:(A,C)AD:(A,D)30AE:(A,E)100,应用举例最短路径,Dijkstra算法,10,50,30,10,100,20,60,应用举例最短路径,Dijkstra算法,S=AAB:(A,B)10AC:(A,C)AD:(A,D)30AE:(A,E)100,10,50,30,10,100,20,60,S=A,BAB:(A,B)10AC:(A,B,C)60AD:(A,D)30AE:(A,E)100

33、,应用举例最短路径,Dijkstra算法,10,50,30,10,100,20,60,应用举例最短路径,Dijkstra算法,S=A,BAB:(A,B)10AC:(A,B,C)60AD:(A,D)30AE:(A,E)100,10,50,30,10,100,20,60,S=A,B,DAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,E)90,应用举例最短路径,Dijkstra算法,10,50,30,10,100,20,60,应用举例最短路径,Dijkstra算法,S=A,B,DAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,E)90,

34、10,50,30,10,100,20,60,S=A,B,D,CAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60,应用举例最短路径,Dijkstra算法,10,50,30,10,100,20,60,Dijkstra算法,S=A,B,D,C,EAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60,应用举例最短路径,AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。,应用举例拓扑排序,AOV网,什么是工程？工程有什么共性？,拓扑序列：设G=

35、(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序。,应用举例拓扑排序,拓扑排序,拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。,应用举例拓扑排序,拓扑排序,拓扑序列：,C1,C2,C3,C4,C5,C6,C7,AOE网,AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始

36、点（或源点），没有出边的顶点称为终点（或汇点）。,AOE网的性质：只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。,应用举例关键路径,事件 事件含义 v1 开工 v2 活动a1完成，活动a4可以开始 v3 活动a2完成，活动a5可以开始 v9 活动a10 和a11完成，整个工程完成,AOE网,应用举例关键路径,要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。,关键路径,应用举例关键路径,首先计算以下与关键活动有关的量：,事件的最早发生时间vek 事件的最迟发生时间vlk 活动的最早开始时间ei

37、活动的最晚开始时间li,最后计算各个活动的时间余量 lk-ek，时间余量为0者即为关键活动。,vek是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。,应用举例关键路径,ve1=0vek=maxvej+len(pk)pk表示所有到达vk的有向边的集合,事件的最早发生时间vek,vek,0,6,4,5,7,7,16,14,18,应用举例关键路径,vek=maxvej+len,vlk是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。,事件的最迟发生时间vlk,应用举例关键路径,aj,vj,vk,vln=venvlk=minvlj-len（sk

38、）sk为所有从vk发出的有向边的集合,vek,vlk,0,6,4,5,7,7,16,14,18,18,14,16,10,7,8,6,6,0,应用举例关键路径,vlk=minvlj-len,活动的最早开始时间ei,应用举例关键路径,若活动ai是由弧表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：ei=vek,vek,0,6,4,5,7,7,16,14,18,a2,a7,a6,a5,a4,a1,a3,a9,a8,ei,0,0,0,6,4,5,7,7,7,a10,a11,16,14,应用举例关键路径,ei=vek,活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开

39、始的最晚时间。若ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：li=vlj-len,活动的最晚开始时间li,应用举例关键路径,vlk,18,14,16,10,7,8,6,6,0,li,10,7,7,8,6,6,3,2,0,16,14,应用举例关键路径,a2,a7,a6,a5,a4,a1,a3,a9,a8,a10,a11,vlk,18,14,16,10,7,8,6,6,0,li=vlj-len,a2,a7,a6,a5,a4,a1,a3,a9,a8,ei,li,0,0,0,6,4,5,7,7,7,10,7,7,8,6,6,3,2,0,a10,a11,16,14,1

40、6,14,应用举例关键路径,v2,v1,v3,v4,v5,v8,v6,v7,v9,a1=6,a4=1,a7=9,a10=2,a11=4,a8=7,a9=4,a5=1,a6=2,a3=5,a2=4,关键活动：li=ei的活动,第七章 知识结构图,查找的基本概念,查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。,7.1 概述,查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：,其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第

41、i个记录所需的关键码的比较次数。,结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。,7.1 概述,查找算法的性能,顺序查找（线性查找）,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,7.2 线性表的查找技术,例：查找k35,折半查找,使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。,基本思想：在有序表中，

42、取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,7.2 线性表的查找技术,二叉排序树,二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左右子树也都是二叉排序树。,7.3 树表的查找技术,二叉排序树的定义采用的是递归方法。,例：在二叉排序树中查

43、找关键字值为35，95的过程：,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,二叉排序树的查找,50,30,20,80,90,85,88,40,35,32,平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：根结点的左子树和右子树的深度最多相差1;根结点的左子树和右子树也都是平衡二叉树。,平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。,平衡二叉树,7.3 树表的查找技术,最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。,7.3 树表的查找技术,4,平衡二叉树,设

44、结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：1.LL型 2.RR型 3.LR型 4.RL型,7.3 树表的查找技术,平衡二叉树,概 述,散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。,7.3 散列表的查找技术,关键码集合,ki,ri,H(ki),H,散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找，换言之，在散列表中，我们不可能找到最大或最小关键码的记录，也不可能找到在某一范围内的记录。散列技术最适合回答的问题是：如果有的话，哪个记录的关键码等于待查值。

45、,概 述,7.3 散列表的查找技术,冲突：对于两个不同关键码kikj，有H(ki)H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。,7.3 散列表的查找技术,概 述,关键码集合,ki,ri,H(ki),kj,H(kj),处理冲突的方法开放定址法,由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。,如何寻找下一个空的散列地址?,7.3 散列表的查找技术,（1）线性探测法（2）二次探测法（3）随机探测法,基本思想：将所有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指

46、针。,用拉链法处理冲突构造的散列表叫做开散列表。,设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为n/m。,7.3 散列表的查找技术,处理冲突的方法拉链法（链地址法）,例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造的开散列表为：,7.3 散列表的查找技术,基本思想：散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比较，若相等，则查找成功；否则，再到溢出表中进行顺序查找。,7.3 散列表

47、的查找技术,处理冲突的方法公共溢出区,第八章 知识结构图,第八章 排序技术,本章的基本内容是：排序的基本概念插入排序交换排序选择排序归并排序,插入排序,插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。,（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？,插入排序,需解决的关键问题?,基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。,希尔排序,希尔插入排序过程示例,1 2

48、3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,插入排序,30,08,13,交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。,交换排序,反序则 交换,起泡排序,基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。,交换排序,快速排序的基本思想,首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有

49、序。,交换排序,如何选择轴值？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？,需解决的关键问题?,13,65,27,50,38,49,55,交换排序,关键问题：如何实现一次划分？,选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。,选择排序,简单选择排序,基本思想：第i 趟在n-i+1（i=1,2,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。,选择排序,需解决的关键问题?,如何在待排序序列中选出关键码最小的记录？如何确定待排序序列中关键码最小的记录在有序序列中的位置？,堆排序,

50、改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。,选择排序,减少关键码间的比较次数,查找最小值的同时，找出较小值,堆的定义,堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。,选择排序,1.大根堆的根结点是所有结点的最大者。2.较大结点靠近根结点，但不绝对。,堆和序列的关系,选择排序,将堆用顺序存储结构来存储，则堆对应一组序列。,堆调整,堆调整：在一棵完全二叉树