数据结构复习汇编学习教案.pptx

《数据结构复习汇编学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构复习汇编学习教案.pptx（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)复习汇编复习汇编第一页，共93页。n n数据结构(jigu)(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。n n数据结构(jigu)分为逻辑结构(jigu)和存储结构(jigu)（物理结构(jigu)）第1页/共93页第二页，共93页。数据数据数据数据(shj)(shj)(shj)(shj)的逻辑结构：的逻辑结构：的逻辑结构：的逻辑结构：数据数据数据数据(shj)(shj)(shj)(shj)元素之间的逻辑关系，分：元素之间的逻辑关系，分：元素之间的逻辑关系，分：元素之间的逻辑关系，分：集合集合集合集合数据数据

2、数据数据(shj)(shj)(shj)(shj)元素间除元素间除元素间除元素间除“同属于一个同属于一个同属于一个同属于一个集合集合集合集合”外，无其它关系外，无其它关系外，无其它关系外，无其它关系线性结构线性结构线性结构线性结构一个对一个，如线性表、栈、一个对一个，如线性表、栈、一个对一个，如线性表、栈、一个对一个，如线性表、栈、队列队列队列队列树形结构树形结构树形结构树形结构一个对多个，如树一个对多个，如树一个对多个，如树一个对多个，如树图状结构图状结构图状结构图状结构多个对多个，如图或网多个对多个，如图或网多个对多个，如图或网多个对多个，如图或网概念概念概念概念(ginin)(ginin)

3、(ginin)(ginin)及术语及术语及术语及术语第2页/共93页第三页，共93页。数据的存储结构数据的存储结构数据的存储结构数据的存储结构数据的逻辑数据的逻辑数据的逻辑数据的逻辑(lu j)(lu j)(lu j)(lu j)结构在计算机存储设备中的映结构在计算机存储设备中的映结构在计算机存储设备中的映结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。射，分：顺序存储结构、链式存储结构。射，分：顺序存储结构、链式存储结构。射，分：顺序存储结构、链式存储结构。n顺序存储：n以相对的存储位置表示逻辑关系n n链式存储n以以附加指针表示后继(huj)关系 a1 a2 a3a2 a1概

4、念概念概念概念(ginin)(ginin)(ginin)(ginin)及术语及术语及术语及术语第3页/共93页第四页，共93页。2 2算法算法算法算法(sun f)(sun f)和算法和算法和算法和算法(sun f)(sun f)分析分析分析分析1算法算法(sun f)概念概念 对特定问题求解步骤的一种描述，是指令对特定问题求解步骤的一种描述，是指令(zhlng)的有限的有限序列，每条指令序列，每条指令(zhlng)表示一个或多个操作。算法应具备的表示一个或多个操作。算法应具备的特性：特性：（2 2）确定性：指令具有确切的含义，相同的输入有相同的输指令具有确切的含义，相同的输入有相同的输出。出

5、。（1 1）有穷性：对合法的输入值在执行有穷步之后结束。对合法的输入值在执行有穷步之后结束。（3 3）可行性：所有操作可经已实现的基本运算执行有限次所有操作可经已实现的基本运算执行有限次来实现来实现（4 4）输入：0 0个或多个个或多个（5 5）输出：一个或多个一个或多个第4页/共93页第五页，共93页。（2 2）可读性：便于阅读）可读性：便于阅读(yud)(yud)和交流和交流（3 3）健壮性）健壮性：能够对输入的非法数据：能够对输入的非法数据(shj)(shj)作出反应和作出反应和处理处理（4 4）效率与低存储量需求：效率指算法的执行时间；存）效率与低存储量需求：效率指算法的执行时间；存储

6、量需储量需 求指算法执行过程求指算法执行过程(guchng)(guchng)中所需要的最大存中所需要的最大存储空间。储空间。2 2算法设计的要求算法设计的要求算法设计的要求算法设计的要求（1 1）正确性：算法应满足具体问题的需求。算法应满足具体问题的需求。a.a.程序不含语法错误程序不含语法错误b.b.对于几组输入可得满足要求的结果对于几组输入可得满足要求的结果c.c.对于精心选择的几组典型、苛刻、带有刁难性的输入数据对于精心选择的几组典型、苛刻、带有刁难性的输入数据可得满足要求的结果可得满足要求的结果 d.d.对一切合法的输入数据都能得出产生要求的结果对一切合法的输入数据都能得出产生要求的结

7、果 第5页/共93页第六页，共93页。3 3算法效率的度量算法效率的度量4 4算法的时间效率主要由两个因算法的时间效率主要由两个因素决定：素决定：5 5l所需处理问题的数据量大小，所需处理问题的数据量大小，数据量大，所花费的时间就多；数据量大，所花费的时间就多；6 6l在解决问题的过程中，基本操在解决问题的过程中，基本操作的执行次数作的执行次数7 7时间复杂度：算法中基本操作时间复杂度：算法中基本操作重复执行的次数是问题规模重复执行的次数是问题规模n的某的某个函数，个函数，T(n)=O(f(n)8 8 好的算法应该能够在数据量好的算法应该能够在数据量n增长的同时增长的同时(tngsh)，函数，

8、函数T(n)的增长速度比较缓慢。的增长速度比较缓慢。第6页/共93页第七页，共93页。常见常见(chn jin)函数的增长率函数的增长率第7页/共93页第八页，共93页。n n一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。总时间由一个常数(chngsh)(即零次多项式)来限界。一个时间为O(n2)的算法由一个二次多项式来限界。n n以下六种计算算法时间的多项式是最常用的。关系为:n n O(1)O(logn)O(n)n n O(nlogn)O(n2)O(n3)n n指数时间的关系为：O(2n)O(n!)O(nn)第8页/共93页第九页，共93页。第二章第9页/共93页第十页，共

9、93页。1 1线性表：是n0个性质相同的数据元素的有限序列(xli)。线性表可记作（a1,a2,an）n 02 2基本操作：3 3建立、存取、插入、删除、检索、分解、排序等。4 4 第10页/共93页第十一页，共93页。(a1,ai-1,ai,an)改变(gibin)为(a1,ai-1,e,ai,an)a1a2ai-1ai ana1a2ai-1ai ean表的长度(chngd)加12基本运算基本运算3在线性表第在线性表第i（1i n+1）个位置上插入）个位置上插入(ch r)元素元素e第11页/共93页第十二页，共93页。注意：注意：注意：注意：C C语言中的数组下标从语言中的数组下标从语言中

10、的数组下标从语言中的数组下标从“0”“0”开始，因此，若开始，因此，若开始，因此，若开始，因此，若L L是是是是SqlistSqlist类型的顺序表，则表中第类型的顺序表，则表中第类型的顺序表，则表中第类型的顺序表，则表中第i i个元素是个元素是个元素是个元素是l.elemi-1l.elemi-1。status insert_sq(Sqlist&Lstatus insert_sq(Sqlist&L，elemtype eelemtype e，int i)int i)if(iL.length+1)/if(iL.length+1)/检查检查检查检查i i值是否合理值是否合理值是否合理值是否合理 re

11、turn ERROR;return ERROR;if(L.length=ListSize)/if(L.length=ListSize)/判断是否溢出判断是否溢出判断是否溢出判断是否溢出 exit(overflow);exit(overflow);for(j=L.length-1;j=i-1;j-)for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/L.elemj+1=L.elemj;/腾出腾出腾出腾出(tn(tn ch)ch)第第第第i i个个个个位置位置位置位置 L.elemi-1=e;L.elemi-1=e;/插入插入插入插入 L.length+;L.

12、length+;/当前表长加当前表长加当前表长加当前表长加1 1 return OK;return OK;第12页/共93页第十三页，共93页。这里这里这里这里(zhl(zhl)的问题规模是表的长度，设它的值为的问题规模是表的长度，设它的值为的问题规模是表的长度，设它的值为的问题规模是表的长度，设它的值为n n。该算。该算。该算。该算法的时间主要花费在循环的元素后移语句上，所需移动元法的时间主要花费在循环的元素后移语句上，所需移动元法的时间主要花费在循环的元素后移语句上，所需移动元法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。素的次数不仅依

13、赖于表的长度，而且还与插入位置有关。素的次数不仅依赖于表的长度，而且还与插入位置有关。素的次数不仅依赖于表的长度，而且还与插入位置有关。i i位置位置位置位置移动次数移动次数移动次数移动次数 1 1n n 2 2n-1n-1 i in-i+1n-i+1 n+1 n+10 0平均移动次数：平均移动次数：平均移动次数：平均移动次数：时间复杂度：时间复杂度：时间复杂度：时间复杂度：OO（n n）第13页/共93页第十四页，共93页。(a1,ai-1,ai,ai+1,an)改变(gibin)为(a1,ai-1,ai+1,an)ai+1an表的长度(chngd)减1a1a2ai-1aiai+1 ana1

14、a2ai-12.2.在线性表中删除在线性表中删除(shnch)(shnch)第第i i（1 i n1 i n）个元素，使）个元素，使第14页/共93页第十五页，共93页。status delete_sq(Sqlist&L,int i,elemtype&e)if(iL.length)/检查i值是否合理return ERROR;e=L.elemi-1;/C下标从0开始(kish)for(j=i;j=L.length-1;j+)L.elem j-1=L.elem j;/删除 L.length-;return OK;第15页/共93页第十六页，共93页。该算法的时间分析与插入算法相似，结点的移动次数也

15、是由表长该算法的时间分析与插入算法相似，结点的移动次数也是由表长该算法的时间分析与插入算法相似，结点的移动次数也是由表长该算法的时间分析与插入算法相似，结点的移动次数也是由表长n n和位置和位置和位置和位置i i决定决定决定决定(judng)(judng)。i i位置位置位置位置移动次数移动次数移动次数移动次数 1 1n-1n-1 2 2n-2n-2 i in-in-i n n0 0平均移动次数：平均移动次数：平均移动次数：平均移动次数：时间复杂度：时间复杂度：时间复杂度：时间复杂度：OO（n n）第16页/共93页第十七页，共93页。第三章第三章 栈和队列栈和队列(duli)(duli)栈和

16、队列也可以栈和队列也可以(ky)被称被称作为操作受限的线性表。作为操作受限的线性表。第17页/共93页第十八页，共93页。思考：假设有思考：假设有A,B,CA,B,C三个元素进三个元素进S S栈栈的顺序的顺序(shnx)(shnx)是是A,B,CA,B,C，写出所有可能的出栈序列。写出所有可能的出栈序列。CBAACBABCCABBACBCA第18页/共93页第十九页，共93页。1.栈属于加了限制条件的线性结构；栈属于加了限制条件的线性结构；2.栈是后进先出的线性表；栈是后进先出的线性表；3.进栈和出栈只能从栈顶进行；进栈和出栈只能从栈顶进行；4.栈中的元素个数可以是栈中的元素个数可以是0（空栈

17、）；（空栈）；5.栈的元素的个数不能是无穷栈的元素的个数不能是无穷(wqing)多个；多个；6.每个栈中的元素的类型相同每个栈中的元素的类型相同.栈的特性栈的特性(txng)第19页/共93页第二十页，共93页。队列（队列（queuequeue）是一种）是一种(y(y zhn)zhn)只允许在一端进行插入，而只允许在一端进行插入，而在另一端进行删除的线性表，它是在另一端进行删除的线性表，它是一种一种(y zhn)(y zhn)操作受限的线性表。操作受限的线性表。3.2 3.2 队列队列(duli)(Queue)(duli)(Queue)队列队列(duli)(duli)的定义及其运算的定义及其运

18、算第20页/共93页第二十一页，共93页。n n定义n n允许(ynx)删除的一端叫做队头(front)，允许(ynx)插入的一端叫做队尾(rear)。n n特性n n先进先出(FIFO,First In First Out)a0 a1 a2 an-1frontrear第21页/共93页第二十二页，共93页。依次 1 2 3 4 5 6 删除两个元素(yun s)之后的头元素(yun s)是？第22页/共93页第二十三页，共93页。第四章第四章 串串 零个或多个字符(z f)组成的有限序列。一般记S=a1a2.an 其中，S是串名，单引号括起的字符(z f)序列是串值；2 2、串长、串长 串中

19、所包含(bohn)的字符个数3 3、空串、空串长度(chngd)为零的串，它不包含任何字符。1 1、串、串4 4、空格串、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。第23页/共93页第二十四页，共93页。第五章第24页/共93页第二十五页，共93页。5.3 广义表的定义广义表的定义一、广义表（一、广义表（General List）广义表中的元素即可以是单个元广义表中的元素即可以是单个元素（称为原子素（称为原子(yunz)）也可以是）也可以是广义表（称为子表）。广义表（称为子表）。一般表示：一般表示：LS=(a1,a2,an)习惯上广义表名用大写字母，原习惯上广义表名用大写字母

20、，原子子(yunz)用小写字母用小写字母当当LS非空时，非空时，a1称为称为LS 的表头的表头（head），其余元素组成的表（），其余元素组成的表（a2,an）称为表尾（）称为表尾（tail）。）。第25页/共93页第二十六页，共93页。例：例：例：例：A=()A=()B=(e)B=(e)C=(a,(b,c,d)C=(a,(b,c,d)D=(A,B,C)D=(A,B,C)E=(a,E)E=(a,E)F=(a,b,(c,(d)F=(a,b,(c,(d)广义表特点：广义表特点：广义表特点：广义表特点：允许递归，可共享子表允许递归，可共享子表允许递归，可共享子表允许递归，可共享子表元素不仅有先后次序

21、，而且有层次关系元素不仅有先后次序，而且有层次关系元素不仅有先后次序，而且有层次关系元素不仅有先后次序，而且有层次关系(gun x)(gun x)元素的层次：是包括该元素的括号对数元素的层次：是包括该元素的括号对数元素的层次：是包括该元素的括号对数元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次表深：广义表中元素的最大层次表深：广义表中元素的最大层次表深：广义表中元素的最大层次第26页/共93页第二十七页，共93页。2 2广义表的存储结构广义表的存储结构(jigu)（通常用链式）（通常用链式）3 3广义表的扩展线性链表存储广义表的扩展线性链表存储4 4typedef struct

22、 glnode5 5int tag;/0 原子结点；原子结点；1 子子表结点表结点6 6union7 7 atomtype atom;/原子结原子结点的值域点的值域8 8 struct glnode*hp;/子表子表表头指针表头指针9 91010struct glnode*next;/下一下一元素指针元素指针1111*glist;第27页/共93页第二十八页，共93页。例：例：例：例：A=();B=(e);C=(a,(b,c,d);D=(A,B,C);E=(a,E)A=();B=(e);C=(a,(b,c,d);D=(A,B,C);E=(a,E)都设一附加表头都设一附加表头都设一附加表头都设一

23、附加表头(bi(bi o tu)o tu)结点结点结点结点1 A1B0 e 1C0a10 b0 c0 d 11 11D10 a1E第28页/共93页第二十九页，共93页。作业作业作业作业(zuy)(zuy)练习练习练习练习求下列广义表操作求下列广义表操作求下列广义表操作求下列广义表操作(cozu)(cozu)的结果：的结果：的结果：的结果：GetHeadGetHead【(p,h,w)(p,h,w)】；】；】；】；GetTailGetTail【(b,k,p,h)(b,k,p,h)】；】；】；】；GetHeadGetHead【(a,b),(c,d)(a,b),(c,d)】；】；】；】；GetTai

24、lGetTail【(a,b),(c,d)(a,b),(c,d)】；GetHeadGetHead【GetTailGetTail【(a,b),(c,d)(a,b),(c,d)】GetTailGetTail【GetHeadGetHead【(a,b),(c,d)(a,b),(c,d)】GetHeadGetHead【GetTailGetTail【GetHeadGetHead【(a,b),(c,d)(a,b),(c,d)】GetTailGetTail【GetHeadGetHead【GetTailGetTail【(a,b),(c,d)(a,b),(c,d)】第29页/共93页第三十页，共93页。第六章第30

25、页/共93页第三十一页，共93页。ABCDEFGHK例如例如(lr)：先序序列先序序列(xli)：中序序列中序序列(xli)：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A二叉树的遍历层次序列：层次序列：A B E C F D G H K第31页/共93页第三十二页，共93页。根据二叉树的遍历根据二叉树的遍历(bin l)(bin l)构构造二叉树造二叉树3 3结点的结点的5 5棵二叉树的棵二叉树的3 3种遍历种遍历序列如表所示。存在序列如表所示。存在(cnzi)(cnzi)情况情况:ABCABCABCABCCAB第3

26、2页/共93页第三十三页，共93页。因此，对因此，对3 3种遍序序列有结论：种遍序序列有结论：（1 1）由先序遍历序列和中序遍）由先序遍历序列和中序遍历序列能够历序列能够(nnggu)(nnggu)唯一确定一棵二唯一确定一棵二叉树。叉树。（2 2）由后序遍历序列和中序遍）由后序遍历序列和中序遍历序列能够历序列能够(nnggu)(nnggu)唯一确定一棵二唯一确定一棵二叉树。叉树。（3 3）由先序遍历序列和后序遍）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。历序列不能唯一确定一棵二叉树。第33页/共93页第三十四页，共93页。例如：已知二叉树BT的后序(hu x)遍历序列为：CBEHGI

27、FDA，中序遍历序列为：BCAEDGHFI，请构造这棵二叉树T。A ABCBCDEFGHIDEFGHIA ADEFGHIDEFGHIB BC CFGHIFGHIA AB BC CD DE EGHGHA AB BC CD DE EF FI IA AB BC CD DE EF FH HG GI I由中序遍历序列和后序遍历序列构造由中序遍历序列和后序遍历序列构造(guzo)(guzo)二叉树的过程示意二叉树的过程示意第34页/共93页第三十五页，共93页。平衡二叉树或者是一棵空树，或者是具有(jyu)下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值=1。若把左子树

28、与右子树高度之差称为结点x的平衡因子(balance factor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡平衡(pnghng)二叉二叉树的定义树的定义第35页/共93页第三十六页，共93页。91000065504741853060727842-330-202141853060727842-1110010a.非平衡非平衡(pnghng)二叉树二叉树 b.平衡平衡(pnghng)二叉树二叉树 所有结点的平衡因子所有结点的平衡因子(ynz)(ynz)只能取只能取-1-1，0 0，1 1三个值之一。三个值之一。第36页/共93页第三十七页，共93页。6

29、.2 堆排序堆排序堆是一棵顺序存储的完全二叉树，堆是一棵顺序存储的完全二叉树，若每个结点若每个结点(ji din)(ji din)的关键字都不小的关键字都不小（大）于其孩子结点（大）于其孩子结点(ji din)(ji din)的关键字，的关键字，则称为大（小）根堆。则称为大（小）根堆。968338112791236854724305391第37页/共93页第三十八页，共93页。堆排序的基本思想是：首先，按堆排序的基本思想是：首先，按堆的定义将堆的定义将R1.nR1.n调整为堆（这个过调整为堆（这个过程称为初始建堆），交换程称为初始建堆），交换R1R1和和RnRn；然后，将然后，将R1.n-1R

30、1.n-1调整为堆，交换调整为堆，交换R1R1和和Rn-1Rn-1；如此反复进行；如此反复进行(jnxng)(jnxng)，直到交换了，直到交换了R1R1和和R2R2为为止。止。第38页/共93页第三十九页，共93页。6.3.1 哈夫曼树的定义哈夫曼树的定义(dngy)设二叉树具有设二叉树具有(jyu)n(jyu)n个带权个带权值的叶子结点，那么从根结点到各个值的叶子结点，那么从根结点到各个叶子结点的路径长度叶子结点的路径长度lili与相应结点权与相应结点权值值wiwi的乘积的和，称为二叉树的带权的乘积的和，称为二叉树的带权路径长度，记作：路径长度，记作：WPL=13+33+22+41=20W

31、PL=13+33+22+41=20。第39页/共93页第四十页，共93页。6.3.2 哈夫曼树的构造哈夫曼树的构造(guzo)（1 1）由给定的）由给定的n n个权值个权值W1,W2,WnW1,W2,Wn构造构造n n棵只有一个叶子结点棵只有一个叶子结点(ji din)(ji din)的二叉树，从而得到一个二叉的二叉树，从而得到一个二叉树的集合树的集合F=T1,T2,TnF=T1,T2,Tn。（2 2）在）在F F中选取根结点的权值最中选取根结点的权值最小和次小的两棵二叉树作为小和次小的两棵二叉树作为(zuwi)(zuwi)左、左、右子树构造一棵新的二叉树，新二叉树右子树构造一棵新的二叉树，新

32、二叉树根结点的权值为其左、右子树根结点权根结点的权值为其左、右子树根结点权值之和。值之和。第40页/共93页第四十一页，共93页。（3 3）在集合）在集合F F中删除作为左、右子中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加树的两棵二叉树，并将新建立的二叉树加入到集合入到集合F F中。中。（4 4）重复（）重复（2 2）、（）、（3 3）两步，当）两步，当F F中只剩下中只剩下(shn xi)(shn xi)一棵二叉树时，这一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。棵二叉树便是所要建立的哈夫曼树。注：如此建造的二叉树，没有度为注：如此建造的二叉树，没有度为1 1的结点。如有的结点

33、。如有n n个叶子，必有个叶子，必有m=2n-1m=2n-1个结个结点。点。第41页/共93页第四十二页，共93页。9例如(lr):已知权值 W=5,6,2,9,7 562752769767139527第42页/共93页第四十三页，共93页。67139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子(y zi)2.分层计算3.路径长为层数减1第43页/共93页第四十四页，共93页。快速远距传输电文时，为使电文尽量短，采用不等长编码，且使用频高的字符用较短的码。并且使任何(rnh)一个字符的编码都不是同一字符集中另一个

34、字符的编码的前缀。利用赫夫曼树可以构造利用赫夫曼树可以构造(guzo)出出一种最优前缀编码使所传电文的总长一种最优前缀编码使所传电文的总长度最短度最短,这种编码就是赫夫曼编码。这种编码就是赫夫曼编码。6.3.3 赫夫曼编赫夫曼编码码(bin m)第44页/共93页第四十五页，共93页。例：已知某通信息流只用8种字符(zf)，出现频率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。设W=(5,29,7,8,14,23,3,11),n=8,则m=15.351123714291111111000000082300291011010141105011

35、301117111081111第45页/共93页第四十六页，共93页。哈夫曼树和编码的代码哈夫曼树和编码的代码(di m)实现实现序号权重父号左子右子172193246532637218109101112131415W=7,19,2,6,32,3,21,10N=8 m=2*8-1=159953610101194111117181212281011131340271414601251515100131410010210300000400015016000017118001112345678第46页/共93页第四十七页，共93页。第第7章章 图图 7.1 图的基本概念图的基本概念 7.1.1 图的

36、定义图的定义(dngy)图是一种非线性结构图是一种非线性结构,它比树形结它比树形结构更复杂构更复杂(fz).(fz).图中的数据元素之间图中的数据元素之间是多对多关系是多对多关系,每一个元素都可能与其每一个元素都可能与其他元素有关他元素有关.图是由一个非空的顶点集合和一图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的个描述顶点之间关系即边（或者弧）的集合组成集合组成.第47页/共93页第四十八页，共93页。7.2 图的存储图的存储(cn ch)结构结构 7.2.1 邻接矩阵邻接矩阵邻接矩阵是表示顶点之间相邻关系邻接矩阵是表示顶点之间相邻关系(gun x)(gun x)的矩阵。设的

37、矩阵。设G=(V,E)G=(V,E)是具有是具有n n个顶点个顶点的图，则的图，则G G的邻接矩阵是的邻接矩阵是n n阶方阵定义阶方阵定义A A：若若G G是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为：第48页/共93页第四十九页，共93页。Aij=0(i,j)VR1(i,j)VRBACDFE例如例如(lr):矩阵的元素为矩阵的元素为ABCDEFABCDEF无向无向(w xin)(w xin)图图-对对称矩阵，半存即可，节省称矩阵，半存即可，节省空间。每行空间。每行(列列)数字和即数字和即是顶点的度是顶点的度第49页/共93页第五十页，共93页。有向图的邻接矩有向图的邻接矩阵阵(j zh

38、n)为非为非对称矩阵对称矩阵(j zhn)ABECDABCDEABCDE行和为出度行和为出度列和为入度列和为入度第50页/共93页第五十一页，共93页。有向网的邻接矩有向网的邻接矩阵阵(j zhn)为非为非对称矩阵对称矩阵(j zhn)ABECDABCDEABCDE1217315第51页/共93页第五十二页，共93页。7.3.2 深度深度(shnd)优优先搜索先搜索深度优先搜索的基本思想是：深度优先搜索的基本思想是：从图从图G G中某个顶点中某个顶点vivi出发，访问出发，访问vivi，然后选择一个与，然后选择一个与vivi相邻且没被访相邻且没被访问过的顶点问过的顶点v v访问，再从访问，再从

39、v v出发选择一出发选择一个与个与v v相邻且未被访问的顶点相邻且未被访问的顶点vjvj访问，访问，依次依次(yc)(yc)继续。继续。第52页/共93页第五十三页，共93页。如果当前已访问过的顶点的如果当前已访问过的顶点的所有邻接顶点都已被访问，则回退所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个到已被访问的顶点序列中最后一个拥有未被访问的相邻拥有未被访问的相邻(xin ln)(xin ln)顶顶点点w w，从，从w w出发按同样方法向前遍历。出发按同样方法向前遍历。直到图中所有顶点都被访问。直到图中所有顶点都被访问。第53页/共93页第五十四页，共93页。从图中某个顶点V0出

40、发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须(bx)设置访问标志。一、连通图的深度一、连通图的深度(shnd)优先搜索遍历优先搜索遍历第54页/共93页第五十五页，共93页。achdekf8234570F F F F F F F F F012345678TTTTTTTachdkfe achkfed访问访问(fngwn)(fngwn)标志标志:访问访问(fngwn)(fngwn)次序次序:例如例如(lr):achdkfe第55页/共93页第五十六页，共93页。7.4 最小生成最小生成(shn chn)树树在一

41、个无向连通图在一个无向连通图G G中，如果取它中，如果取它的全部的全部(qunb)(qunb)顶点和一部分边构成一顶点和一部分边构成一个子图个子图GG，即：，即：V(G)=V(G)V(G)=V(G)和和 E(G)E(G)E(G)E(G)若边集若边集E(G)E(G)中的边，既将图中的边，既将图G G中中的所有顶点连通，又不形成回路，则称的所有顶点连通，又不形成回路，则称子图子图GG是原图是原图G G的一棵生成树。的一棵生成树。产生最小生成树主要有两个算法，产生最小生成树主要有两个算法，即普里姆算法和克鲁斯卡尔算法。即普里姆算法和克鲁斯卡尔算法。第56页/共93页第五十七页，共93页。7.4.2

42、普里姆算法普里姆算法(sun f)普里姆普里姆(Prim)(Prim)算法的思路是：算法的思路是：假设假设G=(V,E)G=(V,E)是一个具有是一个具有n n个顶点的个顶点的连通网，连通网，T=(U,TE)T=(U,TE)是是G G的最小生成的最小生成(shn chn)(shn chn)树，其中树，其中U U是是T T的顶的顶点集，点集，TETE是是T T的边集，的边集，U U和和TETE的初值的初值均为空。均为空。第57页/共93页第五十八页，共93页。算法开始时，首先从算法开始时，首先从V V中任取一个中任取一个(y)(y)顶点（假定取顶点（假定取v0v0），将它并入），将它并入U U中

43、，此时中，此时U=v0U=v0，然后只要，然后只要U U是是V V的真子的真子集（即集（即U U V V），就从那些其一个），就从那些其一个(y)(y)端点已在端点已在T T中，另一个中，另一个(y)(y)端点仍在端点仍在T T外的所有边中，找一条最短（即权值外的所有边中，找一条最短（即权值最小）边，假定为最小）边，假定为(vi,vj)(vi,vj)，其中，其中 viUviU，vjV-UvjV-U，并把该边，并把该边(vi,vj)(vi,vj)和和顶点顶点vjvj分别并入分别并入T T的边集的边集TETE和顶点集和顶点集U U。第58页/共93页第五十九页，共93页。V0V3V5V2V1V46

44、453821756V01V2closedge i12345AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如(lr)：UV-U第59页/共93页第六十页，共93页。7.7 AOE网与关键网与关键(gunjin)路径路径若在带权的有向图中，以顶若在带权的有向图中，以顶点表示事件，有向边表示活动，边点表示事件，有向边表示活动，边上的权值表示完成该活动的开销上的权值表示完成该活动的开销（如该活动所需的时间（如该活动所需的时间(shjin)(shjin)），），则

45、称此带权的有向图为用边表示活则称此带权的有向图为用边表示活动的网络，简称动的网络，简称AOEAOE网（网（Activity Activity On Edge networkOn Edge network）。）。第60页/共93页第六十一页，共93页。在一个表示工程的在一个表示工程的AOEAOE网中，网中，应该不存在回路，网中仅存在一应该不存在回路，网中仅存在一个入度为个入度为0 0的顶点（事件），称为的顶点（事件），称为开始开始(kish)(kish)顶点（源点），它顶点（源点），它表示了整个工程的开始表示了整个工程的开始(kish)(kish)；网中也仅存在一个出度为网中也仅存在一个出度为0

46、 0的顶点（事件），称为结束顶点的顶点（事件），称为结束顶点（汇点），它表示整个工程的结（汇点），它表示整个工程的结束。束。第61页/共93页第六十二页，共93页。在寻找关键活动时所用到的几个在寻找关键活动时所用到的几个参量的定义：参量的定义：（1 1）事件）事件vkvk的最早发生的最早发生(fshng)(fshng)时间时间（2 2）事件）事件vkvk的最迟发生的最迟发生(fshng)(fshng)时间时间（3 3）活动）活动aiai的最早开始时间的最早开始时间（4 4）活动）活动aiai的最迟开始时间的最迟开始时间第62页/共93页第六十三页，共93页。因AOV网中的活动可以并行(bngx

47、ng)，故工程完成的最短时间为从源点到汇点的最长路径(关键路径)。abcdefghk64521187244例如例如(lr):(lr):“关键活动(hudng)”是：关键路径上的活动(hudng)，权值增加将使有向图上的最长路径的长度增加。源点汇点6174关键路径a-b-e-h-k第63页/共93页第六十四页，共93页。把从源点到顶点j的最长路径(ljng)长度叫做事件(顶点)的最早发生时间ve(j);它是可能发生的最早时间。把从顶点k到汇点的最短路径长度叫做(jiozu)事件(顶点)的最迟发生时间vl(k).它是在不推迟工期的前提下最迟必须开始的时间。第64页/共93页第六十五页，共93页。事

48、件发生(fshng)时间的计算公式:ve(源点)=0;ve(k)=Maxve(j)+dut()例如：ve(k)=18,ve(h)=14,ve(f)=7;vl(汇点)=ve(汇点);vl(j)=Minvl(k)dut()例如:vl(k)=18,vl(h)=14,vl(f)=10。第65页/共93页第六十六页，共93页。设第i条弧为则对第i项活动言,“活动(弧)”的最早开始(kish)时间e(i)e(i)=ve(j);e()=14;e()=7;“活动(弧)”的最迟开始(kish)时间l(i)l(i)=vl(k)dut();l()=14;e()=10。jkdut第66页/共93页第六十七页，共93页

49、。什么(shnme)是“关键活动”？该活动的最早开始该活动的最早开始(kish)(kish)时间时间 =该活动的最迟开始该活动的最迟开始(kish)(kish)时间时间在关键(gunjin)路径上,e(h,k)=l(h,k),不在关键(gunjin)路径上e(f,h)=7,l(f,h)=10，推迟开始或延迟3天均不影响工期。第67页/共93页第六十八页，共93页。abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓扑拓扑(tu p)有序序列有序序列:a-d-f-c-b-e-h-g-k第68页/共93

50、页第六十九页，共93页。06457715 14 181814161078660000645777151414160236688710第69页/共93页第七十页，共93页。算法的实现算法的实现(shxin)要点要点:显然，求ve的顺序应该是按拓扑(tup)有序的次序;而求vl的顺序应该是按拓扑(tup)逆序的次序;因为拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。第70页/共93页第七十一页，共93页。8.2 二二 分分 查查 找找n所谓有序表,即表中的各元素按关键字的值升序(或降序)存放。n折半查找又称二分查找,是查找有序表的简单、