数据结构复习汇编.ppt

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

1、数据结构数据结构韩萍n数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。n数据结构分为逻辑结构和存储结构（物理结构）数据的逻辑结构：数据的逻辑结构：数据的逻辑结构：数据的逻辑结构：数据元素之间的逻辑关系，分：数据元素之间的逻辑关系，分：数据元素之间的逻辑关系，分：数据元素之间的逻辑关系，分：集合集合集合集合数据元素间除数据元素间除数据元素间除数据元素间除“同属于一个集合同属于一个集合同属于一个集合同属于一个集合”外，外，外，外，无其它关系无其它关系无其它关系无其它关系 线性结构线性结构线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、

2、栈、队列一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列 树形结构树形结构树形结构树形结构一个对多个，如树一个对多个，如树一个对多个，如树一个对多个，如树 图状结构图状结构图状结构图状结构多个对多个，如图或网多个对多个，如图或网多个对多个，如图或网多个对多个，如图或网概念及术语概念及术语概念及术语概念及术语数据的存储结构数据的存储结构数据的存储结构数据的存储结构数据的逻辑结构在计算机存储设备中的映射，分：顺序数据的逻辑结构在计算机存储设备中的映射，分：顺序数据的逻辑结构在计算机存储设备中的映射，分：顺序数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。存储结构

3、、链式存储结构。存储结构、链式存储结构。存储结构、链式存储结构。n顺序存储：以相对的存储位置表示逻辑关系以相对的存储位置表示逻辑关系以相对的存储位置表示逻辑关系以相对的存储位置表示逻辑关系 n链式存储以以附加指针表示后继关系以以附加指针表示后继关系以以附加指针表示后继关系以以附加指针表示后继关系 a1 a2 a3a2 a1概念及术语概念及术语概念及术语概念及术语2算法和算法分析算法和算法分析1算法概念算法概念 对特定问题求解步骤的一种描述，是指令的有限序列，对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。每条指令表示一个或多个操作。算法应具备的特性算法应具备的特性：

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

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

6、所需处理问题的数据量大小，数据量大，所花费的时间就多；l在解决问题的过程中，基本操作的执行次数 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，T(n)=O(f(n)好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。常见函数的增长率常见函数的增长率n一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。总时间由一个常数(即零次多项式)来限界。一个时间为O(n2)的算法由一个二次多项式来限界。n以下六种计算算法时间的多项式是最常用的。关系为:n O(1)O(logn)O(n)n O(nlogn)O(n2)O(n3)n指数时间的关系为：O(2n)O(n!

7、)O(nn)第二章1线性表：是n0个性质相同的数据元素的有限序列。线性表可记作（a1,a2,an）n 0基本操作：建立、存取、插入、删除、检索、分解、排序等。(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an)a1a2ai-1ai ana1a2ai-1ai ean表的长度加12基本运算基本运算1.在线性表第在线性表第i（1i n+1）个位置上插入元素）个位置上插入元素e注意：注意：C语言中的数组下标从语言中的数组下标从“0”开始，因此，若开始，因此，若L是是Sqlist类型的顺序表，则表中第类型的顺序表，则表中第i个元素是个元素是l.elemi-1。status insert

8、_sq(Sqlist&L，elemtype e，int i)if(iL.length+1)/检查检查i值是否合理值是否合理 return ERROR;if(L.length=ListSize)/判断是否溢出判断是否溢出 exit(overflow);for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/腾出第腾出第i个位置个位置 L.elemi-1=e;/插入插入 L.length+;/当前表长加当前表长加1 return OK;这里的问题规模是表的长度，设它的值为这里的问题规模是表的长度，设它的值为n。该算。该算法的时间主要花费在循环的元素后移语句上，所需

9、移法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位动元素的次数不仅依赖于表的长度，而且还与插入位置有关。置有关。i位置位置移动次数移动次数 1n 2n-1 in-i+1 n+10平均移动次数：平均移动次数：时间复杂度：时间复杂度：O（n）(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an)ai+1 an表的长度减1a1a2ai-1aiai+1 ana1a2ai-12.2.在线性表中删除第在线性表中删除第i i（1 i n1 i n）个元素，使）个元素，使status delete_sq(Sqlist&L,int i,ele

10、mtype&e)if(iL.length)/检查i值是否合理return ERROR;e=L.elemi-1;/C下标从0开始 for(j=i;j=L.length-1;j+)L.elem j-1=L.elem j;/删除 L.length-;return OK;该算法的时间分析与插入算法相似，结点的移动次数也是由表该算法的时间分析与插入算法相似，结点的移动次数也是由表长长n和位置和位置i决定。决定。i位置位置移动次数移动次数 1n-1 2n-2 in-i n0平均移动次数：平均移动次数：时间复杂度：时间复杂度：O（n）第三章 栈和队列栈和队列也可以被称作为操作栈和队列也可以被称作为操作受限的

11、线性表。受限的线性表。思考：假设有思考：假设有A,B,CA,B,C三个元素进三个元素进S S栈的顺序是栈的顺序是A,B,CA,B,C，写出所有可能的出栈序列。写出所有可能的出栈序列。CBAACBABCCABBACBCA1.栈属于加了限制条件的线性结构；栈属于加了限制条件的线性结构；2.栈是后进先出的线性表；栈是后进先出的线性表；3.进栈和出栈只能从栈顶进行；进栈和出栈只能从栈顶进行；4.栈中的元素个数可以是栈中的元素个数可以是0（空栈）；（空栈）；5.栈的元素的个数不能是无穷多个；栈的元素的个数不能是无穷多个；6.每个栈中的元素的类型相同每个栈中的元素的类型相同.栈的特性栈的特性队列（队列（q

12、ueuequeue）是一种只允许）是一种只允许在一端进行插入，而在另一端进行在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限删除的线性表，它是一种操作受限的线性表。的线性表。3.2 3.2 队列队列 (Queue)Queue)3.2.1 3.2.1 队列的定义及其运算队列的定义及其运算n n定义u u允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。n n特性u u先进先出(FIFO,First In First Out)a0 a1 a2 an-1frontrear依次 1 2 3 4 5 6 删除两个元素之后的头元素是？第四章第四章 串串 零个或多个字符组

13、成的有限序列。一般记S=a1a2.an 其中，S是串名串名，单引号括起的字符序列是串值串值；2 2、串长、串长 串中所包含的字符个数3 3、空串、空串长度为零的串，它不包含任何字符。1 1、串、串4 4、空格串、空格串由一个或多个空格组成的串，其长度为串中空格字符的个数。第五章5.3 广义表的定义广义表的定义一、广义表一、广义表（General List）1.广义表中的元素即可以是单个元素（称为原子）广义表中的元素即可以是单个元素（称为原子）也可以是广义表（称为子表）。也可以是广义表（称为子表）。2.一般表示：一般表示：LS=(a1,a2,an)3.习惯上广义表名用大写字母，原子用小写字母习惯

14、上广义表名用大写字母，原子用小写字母4.当当LS非空时，非空时，a1称为称为LS 的表头（的表头（head），其余），其余元素组成的表（元素组成的表（a2,an）称为表尾（）称为表尾（tail）。）。例：例：A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)F=(a,b,(c,(d)广义表特点：广义表特点：允许递归，可共享子表允许递归，可共享子表元素不仅有先后次序，而且有层次关系元素不仅有先后次序，而且有层次关系元素的层次：是包括该元素的括号对数元素的层次：是包括该元素的括号对数表深：广义表中元素的最大层次表深：广义表中元素的最大层次2广义表的存储结构（通常用链式）广义

15、表的存储结构（通常用链式）广义表的扩展线性链表存储typedef struct glnodeint tag;/0 原子结点；1 子表结点union atomtype atom;/原子结点的值域 struct glnode*hp;/子表表头指针struct glnode*next;/下一元素指针*glist;例：例：A=();B=(e);C=(a,(b,c,d);D=(A,B,C);E=(a,E)都设一附加表头结点都设一附加表头结点1 A1B0 e 1C0a10 b0 c0 d 11 11D10 a1E作业练习作业练习求下列广义表操作的结果：求下列广义表操作的结果：GetHead【(p,h,w)

16、】；GetTail【(b,k,p,h)】；GetHead【(a,b),(c,d)】；GetTail【(a,b),(c,d)】；GetHead【GetTail【(a,b),(c,d)】GetTail【GetHead【(a,b),(c,d)】GetHead【GetTail【GetHead【(a,b),(c,d)】GetTail【GetHead【GetTail【(a,b),(c,d)】第六章ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：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二叉树的遍历层次序列

17、：层次序列：A B E C F D G H K5.3.2根据二叉树的遍历构造二叉树3 3结点的结点的5 5棵二叉树的棵二叉树的3 3种遍历序种遍历序列如表所示。存在情况列如表所示。存在情况:ABCABCABCABCCAB因此，对因此，对3 3种遍序序列有结论：种遍序序列有结论：（1 1）由先序遍历序列和中序遍历）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一确定一棵二叉树。（2 2）由后序遍历序列和中序遍历）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。序列能够唯一确定一棵二叉树。（3 3）由先序遍历序列和后序遍历）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。序

18、列不能唯一确定一棵二叉树。例如：已知二叉树BT的后序遍历序列为：CBEHGIFDA，中序遍历序列为：BCAEDGHFI，请构造这棵二叉树T。A ABCBCDEFDEFGHIGHIA ADEFDEFGHIGHIB BC CFGHFGHI IA AB BC CD DE EGHGHA AB BC CD DE EF FI IA AB BC CD DE EF FH HG GI I由中序遍历序列和后序遍历序列构造二叉树的过程示意由中序遍历序列和后序遍历序列构造二叉树的过程示意平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：(1)左、右子树都是平衡二叉树；(2)左、右子树高度差的绝对值=1。若把左

19、子树与右子树高度之差称为结点x的平衡因子(balance factor)，用bf(x)表示。则由平衡二叉树定义知:Bf(x)=x左子树深度-x右子树深度1.平衡二叉树的定义91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉树非平衡二叉树 b.平衡二叉树平衡二叉树 所有结点的平衡因子只能所有结点的平衡因子只能取取-1-1，0 0，1 1三个值之一。三个值之一。6.2 堆排序堆是一棵顺序存储的完全二叉树，堆是一棵顺序存储的完全二叉树，若每个结点的关键字都不小（大）于其若每个结点的关键字都不小（大）于其孩子结点的关键字，则

20、称为大（小）根孩子结点的关键字，则称为大（小）根堆。堆。968338112791236854724305391堆排序的基本思想是：首先，按堆排序的基本思想是：首先，按堆的定义将堆的定义将R1.nR1.n调整为堆（这个过调整为堆（这个过程称为初始建堆），交换程称为初始建堆），交换R1R1和和RnRn；然后，将；然后，将R1.n-1R1.n-1调整为堆，交换调整为堆，交换R1R1和和Rn-1Rn-1；如此反复进行，直到；如此反复进行，直到交换了交换了R1R1和和R2R2为止。为止。6.3.1 哈夫曼树的定义哈夫曼树的定义设二叉树具有设二叉树具有n n个带权值的叶子结个带权值的叶子结点，那么从根结点

21、到各个叶子结点的点，那么从根结点到各个叶子结点的路径长度路径长度l li i与相应结点权值与相应结点权值w wi i的乘积的的乘积的和，称为二叉树的带权路径长度，记和，称为二叉树的带权路径长度，记作：作：WPL=1WPL=13+33+33+23+22+42+41=201=20。6.3.2 哈夫曼树的构造哈夫曼树的构造（1 1）由给定的）由给定的n n个权值个权值WW1 1,W,W2 2,W,Wn n 构造构造n n棵只有一个叶子结棵只有一个叶子结点的二叉树，从而得到一个二叉树的集点的二叉树，从而得到一个二叉树的集合合F=TF=T1 1,T,T2 2,T,Tn n。（2 2）在）在F F中选取根

22、结点的权值最小中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点权值之和。权值为其左、右子树根结点权值之和。（3 3）在集合）在集合F F中删除作为左、右子中删除作为左、右子树的两棵二叉树，并将新建立的二叉树树的两棵二叉树，并将新建立的二叉树加入到集合加入到集合F F中。中。（4 4）重复（）重复（2 2）、（）、（3 3）两步，当）两步，当F F中只剩下一棵二叉树时，这棵二叉树便中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。是所要建立的哈夫曼树。注：如

23、此建造的二叉树，没有度为注：如此建造的二叉树，没有度为1 1的结点。如有的结点。如有n n个叶子，必有个叶子，必有m=2n-1m=2n-1个个结点。结点。9例如:已知权值 W=5,6,2,9,756275276976713952767139527952716671329WPL=(6+7+9)*2+(5+2)*3=22*2+7*3=44+21=65注意：1.只算叶子2.分层计算3.路径长为层数减1快速远距传输电文时，为使电文尽量短，采用不等长编码，且使用频高的字符用较短的码。并且使任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造出一种最优前缀编码使所传电文的总长度

24、最短,这种编码就是赫夫曼编码。6.3.3 赫夫曼编码例：已知某通信息流只用8种字符，出现频率为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.351123714291111111000000082300291011010141105011301117111081111哈夫曼树和编码的代码实现序号权重父号左子右子172193246532637218109101112131415W=7,19,2,6,32,3,21,10N=8 m=2*8-1=159953610101194111

25、117181212281011131340271414601251515100131410010210300000400015016000017118001112345678第7章 图 7.1 图的基本概念 7.1.1 图的定义图的定义图是一种非线性结构图是一种非线性结构,它比树形结它比树形结构更复杂构更复杂.图中的数据元素之间是多对图中的数据元素之间是多对多关系多关系,每一个元素都可能与其他元素每一个元素都可能与其他元素有关有关.图是由一个非空的顶点集合和一个图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集描述顶点之间关系即边（或者弧）的集合组成合组成.7.2 图的存储结构

26、7.2.1 邻接矩阵邻接矩阵邻接矩阵是表示顶点之间相邻关系的邻接矩阵是表示顶点之间相邻关系的矩阵。设矩阵。设G=(V,E)G=(V,E)是具有是具有n n个顶点的图，则个顶点的图，则G G的邻接矩阵是的邻接矩阵是n n阶方阵定义阶方阵定义A A：若若G G是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为：Aij=0(i,j)VR1(i,j)VRBACDFE例如例如:矩阵的元素为矩阵的元素为ABCDEFABCDEF无向图无向图-对称矩阵，半对称矩阵，半存即可，节省空间。每行存即可，节省空间。每行(列列)数字和即是顶点的度数字和即是顶点的度有向图的邻接矩有向图的邻接矩阵为非对称矩阵阵为非对称矩阵

27、ABECDABCDEABCDE行和为出度行和为出度列和为入度列和为入度有向网的邻接矩有向网的邻接矩阵为非对称矩阵阵为非对称矩阵ABECDABCDEABCDE121731 57.3.2 深度优先搜索深度优先搜索深度优先搜索的基本思想是：深度优先搜索的基本思想是：从图从图G G中某个顶点中某个顶点vivi出发，访出发，访问问vivi，然后选择一个与，然后选择一个与vivi相邻且没相邻且没被访问过的顶点被访问过的顶点v v访问，再从访问，再从v v出发出发选择一个与选择一个与v v相邻且未被访问的顶相邻且未被访问的顶点点vjvj访问，依次继续。访问，依次继续。如果当前已访问过的顶点的如果当前已访问过

28、的顶点的所有邻接顶点都已被访问，则回所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点一个拥有未被访问的相邻顶点w w，从从w w出发按同样方法向前遍历。直出发按同样方法向前遍历。直到图中所有顶点都被访问。到图中所有顶点都被访问。从图中某个顶点顶点V0出发，访问此顶点，然后依次从依次从V0的的各个未被访问各个未被访问的的邻接点出发深度优先搜索遍历图邻接点出发深度优先搜索遍历图，直至图中所有都被访问到。为确定每一个结点是否被访问，必须设置访问标志。一、连通图的深度优先搜索遍历一、连通图的深度优先搜索遍历achdekf8234570F F

29、 F F F F F F F012345678TTTT TT Tach d kfe achkfed访问标志访问标志:访问次序访问次序:例如例如:achdkfe7.4 最小生成树在一个无向连通图在一个无向连通图G G中，如果取它中，如果取它的全部顶点和一部分边构成一个子图的全部顶点和一部分边构成一个子图GG，即：，即：V(G)=V(G)V(G)=V(G)和和 E(G)E(G)E(G)E(G)若边集若边集E(GE(G)中的边，既将图中的边，既将图G G中中的所有顶点连通，又不形成回路，则称的所有顶点连通，又不形成回路，则称子图子图GG是原图是原图G G的一棵生成树。的一棵生成树。产生最小生成树主要

30、有两个算法，产生最小生成树主要有两个算法，即普里姆算法和克鲁斯卡尔算法。即普里姆算法和克鲁斯卡尔算法。7.4.2 普里姆算法普里姆算法普里姆普里姆(PrimPrim)算法的思路是：算法的思路是：假设假设G=(V,E)G=(V,E)是一个具有是一个具有n n个顶点的个顶点的连通网，连通网，T=(U,TE)T=(U,TE)是是G G的最小生成树，的最小生成树，其中其中U U是是T T的顶点集，的顶点集，TETE是是T T的边集，的边集，U U和和TETE的初值均为空。的初值均为空。算法开始时，首先从算法开始时，首先从V V中任取一个中任取一个顶点（假定取顶点（假定取v0v0），将它并入），将它并入

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

32、5AdjvexLowcostV0V1V2V3V4V5V0V1V2V3V4V5v06v01v070v25v26v2440V5v55v5220V350V1v1330V41+4+2+5+3=15例如：UV-U7.7 AOE网与关键路径若在带权的有向图中，以顶点若在带权的有向图中，以顶点表示事件，有向边表示活动，边上表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如的权值表示完成该活动的开销（如该活动所需的时间），则称此带权该活动所需的时间），则称此带权的有向图为用边表示活动的网络，的有向图为用边表示活动的网络，简称简称AOEAOE网（网（Activity On Edge Activity

33、On Edge networknetwork）。）。在一个表示工程的在一个表示工程的AOEAOE网中，网中，应该不存在回路，网中仅存在一应该不存在回路，网中仅存在一个入度为个入度为0 0的顶点（事件），称为的顶点（事件），称为开始顶点（源点），它表示了整开始顶点（源点），它表示了整个工程的开始；个工程的开始；网中也仅存在一个出度为网中也仅存在一个出度为0 0的的顶点（事件），称为结束顶点顶点（事件），称为结束顶点（汇点），它表示整个工程的结（汇点），它表示整个工程的结束。束。在寻找关键活动时所用到的几个在寻找关键活动时所用到的几个参量的定义：参量的定义：（1 1）事件）事件vkvk的最早发生时

34、间的最早发生时间（2 2）事件）事件vkvk的最迟发生时间的最迟发生时间（3 3）活动）活动aiai的最早开始时间的最早开始时间（4 4）活动）活动aiai的最迟开始时间的最迟开始时间因AOV网中的活动可以并行，故工程完成的最短时间为从源点源点到汇点汇点的最长路径(关键路径关键路径)。abcdefghk64521187244例如例如:“关键活动”是：关键路径上的活动，权值增关键路径上的活动，权值增加加将使有向图上的最长路径的长度增加。最长路径的长度增加。源点汇点6174关键路径a-b-e-h-k把从源点到顶点j的最长路径长度叫做事件(顶点)的最早发生时间ve(j);它是可能发生的最早时间。把从

35、顶点k到汇点的最短路径长度叫做事件(顶点)的最迟发生时间vl(k).它是在不推迟工期的前提下最迟必须开始的时间。事件发生时间的计算公式: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。设第i条弧为则对第i项活动言,“活动(弧)”的最早开始时间e(i)e(i)=ve(j);e()=14;e()=7;“活动(弧)”的最迟开始时间l(i)l(i)=vl(k)dut();l()=14;e()=10。jkdut什

36、么是“关键活动关键活动”？该活动的该活动的最早最早开始时间开始时间 =该活动的该活动的最迟最迟开始时间开始时间在关键路径上,e(h,k)=l(h,k),不在关键路径上e(f,h)=7,l(f,h)=10，推迟开始或延迟3天均不影响工期。abcdefghk645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k06457715 14 181814161078660000645777 15 14141602366887 10 算法的实现要点算法的实现要点:显然

37、，求ve的顺序应该是按拓扑有序拓扑有序的次序;而求vl的顺序应该是按拓扑逆序拓扑逆序的次序;因为拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。8.2 二 分 查 找n所谓有序表有序表,即表中的各元素按关键字的值升序(或降序)存放。n折半查找又称二分查找,是查找有序表的简单、有效的常用方法。n基本思想：设低高端指针为L、H,则选取中间记录M=(L+H)/2,将其关键字与给定关键字k进行比较,若相等,则查找成功；n否则,若k值比表中关键字值大,则令L=M+1,H不变,在表的后半部分继续对右子表进行折半查找；若k值比表中关键字值小,则令H

38、=M-1,L不变,继续对左子表进行折半查找。每进行一次比较,要么找到要查找的元素,要么将查找的范围缩小一半。如此递推,直到查找成功或把要查找的范围缩小为空（查找失败）。LHMK=210 1 2 3 4 5 6 7 8 9 10 2.指针：L=0 H=4 M=(L+H)/2=2HM3.指针：L=3 H=4 M=(L+H)/2=3LM查找过程构成描述折半查找的判定树，当查找过程构成描述折半查找的判定树，当前的前的M M作根，左子表的作根，左子表的M M作为左子树的根，右子作为左子树的根，右子表的表的M M作为右子树的根，作为右子树的根，若，若n=11n=11，则判定树，则判定树如下。可看出中序遍历

39、判定树与表序相同，其如下。可看出中序遍历判定树与表序相同，其查找次数恰好等于层数。查找次数恰好等于层数。528036914710L=0,H=10M=5L=6,H=10M=8L=0,H=4M=2L=0,H=1M=0L=9,H=10M=9L=3,H=4M=3L=6,H=7M=6L=1,H=1M=1L=4,H=4M=4L=7,H=7M=7L=10,H=10M=10例:5,13,19,21,37,56,64,75,80,88,92）例:5,13,19,21,37,56,64,75,80,88,92）1.指针：L=0 H=10 M=(L+H)/2=5LHMK=850 1 2 3 4 5 6 7 8 9

40、10 2.指针：L=6 H=10 M=(L+H)/2=8M3.指针：L=9 H=10 M=(L+H)/2=9L4.指针：L=9 H=8 HL失败LM不难看出：如果把建造的描述折半查找的不难看出：如果把建造的描述折半查找的判定树中所有结点的空指针域上加一个指向称判定树中所有结点的空指针域上加一个指向称为外部结点的方形结点的指针。则失败时必指为外部结点的方形结点的指针。则失败时必指向外部指针，所以比较次数也不会超过层数。向外部指针，所以比较次数也不会超过层数。52803691471010 折半查找算法折半查找算法int BinSearch(LineList R,int n,KeyType k)in

41、t low=0,hight=n-1,mid;while(low=hight)mid=(low+hight)/2;if(k=Rmid.key)return mid;else if(kRmid.key)hight=mid-1;else low=mid+1;return-1;/Search_Bin 算法分析：在二分查找过程中，关键算法分析：在二分查找过程中，关键字与字与k每比较一次查找范围就缩小一半。每比较一次查找范围就缩小一半。因为比较次数等于元素所在层数因为比较次数等于元素所在层数 h，而而h层最多有层最多有2h-1个元素，设有序表中元素个元素，设有序表中元素个数为个数为n，则有，则有则二分查找

42、的最大查找长度为：则二分查找的最大查找长度为：二分查找的平均查找长度为二分查找的平均查找长度为O(log2n)，比顺序查找速度快。比顺序查找速度快。因故课本错误，请照课本错误，请照此修改此修改p168中中7.5 哈希表查找 7.5.1 哈希表查找的基本概念哈希表查找的思想，它通过哈希表查找的思想，它通过对元素的关键字值进行某种运算，对元素的关键字值进行某种运算，直接求出元素的地址，即使用关直接求出元素的地址，即使用关键字到地址的直接转换方法，而键字到地址的直接转换方法，而不需要反复比较。不需要反复比较。因此，哈希表查找法又叫杂因此，哈希表查找法又叫杂凑法或散列法。凑法或散列法。用一个函数用一个

43、函数H H把数据集中的把数据集中的n n个个结点的关键字唯一地转换成结点的关键字唯一地转换成0.m-10.m-1范围内的数值，即对任意结点的关范围内的数值，即对任意结点的关键字键字kiki，有：，有：0H(ki)m-1 0H(ki)m-1（0in-10in-1）H(ki)H(ki)是表与元素关键字之间是表与元素关键字之间映射关系的函数，称为哈希函数。映射关系的函数，称为哈希函数。构造哈希函数和建立解决冲突构造哈希函数和建立解决冲突的方法是两个主要任务。的方法是两个主要任务。假定某教室有假定某教室有3535个座位，哈希个座位，哈希法则要限定学生所坐的位置应与其法则要限定学生所坐的位置应与其学号的

44、末两位相同，则学号为学号的末两位相同，则学号为06016050601605的学生应坐编号为的学生应坐编号为5 5的座位。的座位。这样我们要找某个学生时只需根据这样我们要找某个学生时只需根据其学号的末两位到相应座位上去找其学号的末两位到相应座位上去找即可，不必一一比较了。即可，不必一一比较了。在这个例子里，学生好比记录，在这个例子里，学生好比记录，学号则为关键字，对关键字进行的学号则为关键字，对关键字进行的操作操作-哈希函数则是取其末两位，哈希函数则是取其末两位，用以确定记录的位置。用以确定记录的位置。n不同的关键字可能得到同一哈希不同的关键字可能得到同一哈希地址，这种现象称冲突。具有同一地地址

45、，这种现象称冲突。具有同一地址的关键字称作同义词。应该尽可能址的关键字称作同义词。应该尽可能地避免冲突的发生。地避免冲突的发生。n总之，哈希表就是根据设定的哈总之，哈希表就是根据设定的哈希函数和处理冲突的方法将一组关键希函数和处理冲突的方法将一组关键字映像到一个有限的连续地址上，并字映像到一个有限的连续地址上，并以此地址作为存储地址的表。这一映以此地址作为存储地址的表。这一映像过程称为哈希造表或散列，所得存像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。储位置称哈希地址或散列地址。7.5.2 7.5.2 哈希函数的构造方法哈希函数的构造方法一个好的哈希函数能将给定的数一个好的哈希函

46、数能将给定的数据集均匀地映射到给定的地址区间中。据集均匀地映射到给定的地址区间中。构造哈希函数的常用方法：构造哈希函数的常用方法：1.1.直接定值法直接定值法 H(kH(ki i)=a*k)=a*ki i+b,+b,例如按序号的若干例如按序号的若干倍加上一个常数存储。倍加上一个常数存储。2.2.数字分析法数字分析法取关键字中某些取值较分散的数取关键字中某些取值较分散的数字位作为散列地址。字位作为散列地址。再如取下列各元素的第再如取下列各元素的第6 6位和第位和第7 7位：位：100011211100011211，100011322100011322，100011413100011413，100

47、011556100011556，100011613100011613，100011756100011756，100011823100011823的散列地的散列地址分别是：址分别是：1212，1313，1414，1515，1616，1717，1818。3.3.除留余数法除留余数法 H H（k k）=k mod m,=k mod m,如学号后两位。如学号后两位。4.4.平方取中法平方取中法取关键字平方的中间几位。取关键字平方的中间几位。5.5.折叠法折叠法把关键字分割成位数相同的几段，把关键字分割成位数相同的几段，求叠加和，舍去进位。例如书号求叠加和，舍去进位。例如书号0-0-442-20586-

48、4442-20586-4折叠折叠5864+0224+04=60925864+0224+04=60927.5.3 哈希冲突的解决方法在哈希表中，虽然冲突很难避免，但在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。发生冲突的可能性却有大有小。这主要与三个因素有关：这主要与三个因素有关：（1 1）与装填因子）与装填因子 有关。有关。（2 2）与所采用的哈希函数有关。）与所采用的哈希函数有关。（3 3）与哈希冲突函数有关。）与哈希冲突函数有关。n-已填，已填，m-空间空间几种常用的解决哈希冲突的方法：几种常用的解决哈希冲突的方法：1开放地址法开放地址法（1）线性探测再散列）线性探测再散列（

49、2）二次探测再散列）二次探测再散列（3）随机探测再散列）随机探测再散列2链地址法链地址法3.性能分析性能分析查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查查找长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列的位置上要插入新元素时为找到空位置的次数，它是表中所有可能散列的位置上要插入新元素时为找到空位

50、置的探查次数的平均值。探查次数的平均值。表表7.2列出了用几种不同的方法解决冲突时哈希表的平均查找长度。列出了用几种不同的方法解决冲突时哈希表的平均查找长度。从中可以看到，哈希表的平均查找长度不是对象个数从中可以看到，哈希表的平均查找长度不是对象个数n的函数，而是装填的函数，而是装填因子因子 的函数。因此，在设计哈希表时可选择的函数。因此，在设计哈希表时可选择 控制哈希表的平均查找长度。控制哈希表的平均查找长度。8.4.2 快速排序快速排序是由冒泡排序改进而得的，快速排序是由冒泡排序改进而得的，它的基本思想是：在待排序的它的基本思想是：在待排序的n n个记录中个记录中任取一个记录（通常取第一个