2022年数据结构期末复习资料知识 .pdf

《2022年数据结构期末复习资料知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末复习资料知识 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构 (Data Structure) ：相互之间存在一种或多种特定关系的数据元素的集合。2、数据结构的形式定义：二元组 Data_Structure=(D,S) 其中， D 是数据元素的有限集，S 是 D 上关系的有限集。3、数据元素之间关系的映像：、顺序映像(顺序存储结构 )：以相对的存储位置表示后继关系。2、非顺序映像 (链式存储结构 )：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于数据(逻辑 )结构，其实现取决于物理结构。4、 算法的定义： 对特

2、定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性： 有穷性、确定性、可行性、输入、输出5、 算法的评价 衡量算法优劣的标准正确性 (correctness): 满足具体问题的需求可读性 (readability) ：易读、易理解健壮性 (robustness):当输入数据非法时，算法能够做出反应或进行处理效率与低存储量:执行时间短、存储空间小作业的答案：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。第二章1、线性表是一种最简单的线性结构。线性结构是一个数据元素的有序（次序）关系特点：存在唯一的一个 第一个 的数据元素；存在唯一的一个

3、最后一个 的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继2、线性表类型的实现 顺序映像定义：用一组地址连续的存储单元依次存放线性表中的数据元素。以“ 存储位置相邻” 表示有序对 ，则有： LOC(ai) = LOC(ai-1) + l其中l是一个数据元素所占存储量LOC(ai) = LOC(a1) + (i-1)l 特点： 1、实现逻辑上相邻物理地址相邻2、实现随机存取3 、 若 假 定 在 线 性 表 中 任 何 一 个 位 置 上 进 行 插 入 的 概 率 都 是 相 等 的 ， 则 移 动 元 素 的 期 望 值 为 ：11)1(11niisinn

4、E2n若 假 定 在 线 性 表 中 任 何 一 个 位 置 上 进 行 删 除 的 概 率 都 是 相 等 的 ， 则 移 动 元 素 的 期 望 值 为 ：nidlinnE1)(121n4、 线性表类型的实现 链式映像线性链表特点：用一组地址任意的存储单元存放线性表中的数据元素。5、在单链表中第i 个结点之前进行插入的基本操作为：找到线性表中第i-1 个结点，然后修改其指向后继的指针。s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入在单链表中删除第i 个结

5、点的基本操作为:找到线性表中第i-1 个结点，修改其指向后继的指针。q = p-next; p-next = q-next;e = q-data; free(q);5、 循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。和单链表的差别仅在于：判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。6、 双向链表的操作特点：1、 查询 和单链表相同；2、 插入 和 删除 时需要同时修改两个方向上的指针 插入 ：s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; （s是插入的结点）删除： p-nex

6、t = p-next-next; p-next-prior = p; （要删除的是p 的下一个结点）课后作业P13: 2.3、2.5 P15: 2.8、2.9(2) 第三章名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 1、栈、队列的特点：从数据元素间的逻辑关系看是线性表从操作方式与种类看不同于线性表：栈与队列是操作受限的线性表2、栈的基本概念栈-是限制仅在线性表的一端进行插入和删除运算的线性表。栈顶（ TOP ）-允许插入和

7、删除的一端。栈底（ bottom)-不允许插入和删除的一端。空栈 -表中没有元素。栈 -又称为后进先出的线性表3、 栈中元素的特性：1、具有线性关系2、后进先出4、 栈的进栈出栈规则：a)按序进栈：有n 个元素 1， 2， ,n，它们按1,2, , n的次序进栈 (i 进栈时， 1(i-1)应该已经进栈)；b)栈顶出栈：栈底最后出栈；c)时进时出：元素未完全进栈时，即可出栈。5、栈的表示与实现顺序栈即栈的顺序存储结构：一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。1、 附设一个栈底指针base ，总是指向栈底。2、 附设一个栈顶指针top。空栈时， top=base；非空栈时，总是指向

8、栈顶元素1 的位置。插入一个栈顶元素，指针top 增 1；删除一个栈顶元素，指针top 减 1；非空栈中的栈顶指针始终在栈顶元素的下一个位置上链栈：注意 : 链栈中指针的方向指向前驱结点！6、队列队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。队尾 (rear) 允许插入的一端队头 (front) 允许删除的一端队列特点：先进先出(FIFO) 7、队列类型的实现链队列 队列的链式表示和实现顺序队列 队列的顺序表示和实现用一组连续的存储单元依次存放队列中的元素8、顺序队列运算时的头、尾指针变化设两个指针front,rear, 约定： rear 指示队尾元素；front 指示队头元

9、素前一位置初值front=rear=0 空队列条件： Q.front=Q.rear 队列满： Q.rear-Q.front=m 入队列：Q.baserear+=x; 出队列： x=Q.base+front;存在问题：设数组维数为M ，则：当 rear-front=m 时，再有元素入队发生溢出 真溢出当 rear 已指向队尾，但队列前端仍有空位置时，再有元素入队发生溢出假溢出！9、 循环队列：将数组首尾相接（即：base0连在 basem-1之后 )。入 /出队列运算利用 模运算 ，则：入队： Q.rear=(Q.rear+1)%m 出队： Q.front=(Q.front+1)%m 队满和队空

10、判断条件：少用一个元素空间：队空： Q.rear=(Q.front) 队满： (Q.rear+1)%m=Q.front 10、栈和队列是限定插入和删除只能在表的“端点”进行的线性表。a)栈具有 后进先出 的特性；b)队列具有 先进先出 的特性。11、栈的链式存储不需头结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 课后作业1. 用栈结构计算中缀式2+(4-3)*6 ，画出计算过程栈的结构。2. 简述以下算法的功能(栈和队

11、列的元素类型均为int) void algo3 (Queue &Q) Stack S; int d; InitStack(S); while (!QueueEmpty(Q) DeQueue(Q, d); Push(S, d); while (!StackEmpty(S) Pop(S, d); EnQueue(Q, d); 第四章一、 1、串的基本概念串-由零个或多个字符组成的有限序列，一般记为：s=a1a2.an (n0) 串中字符的个数n 称为串的长度；零个字符，即长度为零的串称为空串，用或表示。空串不等于空格串，空格串：由一个或多个空格组成的串子串：串中任意个连续的字符组成的子序列主串：包

12、含子串的串相应地称为主串相等：两个串的长度相等，并且对应位置的字符都相同。2、串结构与线性表结构的比较：逻辑结构：极为相似，区别仅在于串的数据对象约束为字符集。基本操作：有很大差别1、线性表大多以 单个元素 作为操作对象2、串通常以 串的整体 作为操作对象3、串类型定义4、 串赋值 StrAssign 、 串复制 Strcopy 、 串比较 StrCompare、 求串长 StrLength、 串联接 Concat 以及求子串SubString等六种操作构成串类型的最小操作子集。1、 StrAssign (&T, chars) 初始条件： chars 是字符串常量。操作结果：把chars 赋为

13、T 的值。等价于C语言中的 strset函数2、 StrCopy (&T, S) 初始条件：串S 存在。操作结果：由串S 复制得串T。等价于C 语言中的strcpy函数3、 StrCompare (S, T) 初始条件：串S 和 T 存在。操作结果：若ST，则返回值 0； 若 ST，则返回值 0； 若 ST，则返回值 0。等价于C 语言中的strcmp 函数 (按 ASCII 码值进行大小比较) 4、 StrLength (S) 初始条件：串S 存在。操作结果：返回S 的元素个数，称为串的长度。等价于C 语言中的 strlen 函数5、 Concat (&T, S1, S2) 初始条件：串S1

14、 和 S2 存在。操作结果：用T 返回由 S1 和 S2 联接而成的新串。例如：Concate( T, man , kind ) 求得T = mankind等价于 C 语言中的strcat 函数6、 SubString (&Sub, S, pos, len) 初 始 条 件 ： 串S 存 在 ， 1 pos StrLength(S) 且0 lenStrLength(S)-pos+1。 操作结果：用Sub 返回串 S 的第 pos个字符起长度为len 的子串。子串为“串”中的一个字符子序列。例如：SubString( sub, commander, 4, 3) ，求得 sub = man ；Su

15、bString( sub, commander, 1, 9) ，求得 sub = commander ；SubString( sub, commander, 9, 1) ，求得 sub = r ；起始位置 pos和子串长度len 之间存在约束关系，pos+len=StrLength(S)+1 SubString(student, 5, 0) = ? 长度为 0 的子串为 合法 串5、Index (S, T, pos) 初始条件：串S和 T 存在， T 是非空串，1posStrLength(S)。操作结果：若主串S 中存在和串T 值相同的子串 , 则返回它在主串S 中第 pos个字符之后第一次出

16、现的位置;否则函数值为0。“子串在主串中的位置”指子串中的第一个字符在主串中的位序。假设S = abcaabcaaabc , T = bcaIndex(S, T, 1) =2 Index(S, T, 3) = 6 Index(S, T, 8) = 0 6、Replace (&S, T, V) 初始条件：串S, T 和 V 均已存在，且T 是非空串。操作结果：用V 替换主串S 中出现的所有与（模式串）T 相等的不重叠的子串。例如：假设S = abcaabcaaabca ，T = bca 若 V = x ， 则经置换后得到S = abcaabcaaabca名师资料总结 - - -精品资料欢迎下载

17、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 7、StrInsert (&S, pos, T) 初始条件：串S 和 T 存在，1pos StrLength(S) 1。操作结果：在串S的第 pos个字符之前插入串T 例如： S = chater ，T = rac ，则执行StrInsert(S, 4, T) 之后得到S = cha racter二、串的表示和实现1、定长顺序存储表示：用一组地址连续的存储单元存储串值的字符序列，称为顺序串。可用一个数组来表示。特点：串的

18、实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为 截断 。按这种串的表示方法实现的串运算时，其基本操作为 字符序列的复制顺序存储结构中，串操作的基本操作为字符序列的复制 ，其时间复杂度基于复制的字符序列的长度。2、堆分配存储表示：特点：仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。3、串的模式匹配算法课堂练习已知： a=?THIS , f=?A SAMPLE, c=?GOOD , d=?NE, b=? ?, 1、s=Concat(a, Conc

19、at(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2), 2、t=Replace(f, SubString(f, 3, 6), c), 3、u=Concat(SubStr ing(c, 3, 1), d), g=?IS,4、v=Concat(s, Concat(b, Concat(t, Concat(b, u), 试问： s, t, v, StrLength(s), Index(v, g), Index(u, g) 各是什么？1、?THIS SAMPLE IS 2、?A GOOD 3、?ONE 4、v=?THIS SAMPLE IS A GOOD

20、 ONE 课后作业P28：4.5(要求：写出每一个函数执行后的结果) 1. 已知： s=?(XYZ)+* ，t=?(X+Z)*Y。试利用联接、求子串和置换等基本操作，将s转化为 t。SubString(&s1, s, 3, 1); Y SubString(&s2, s, 6, 1); + SubString(&s3, s, 7, 1);* Replace(&s, s1, s2); (X+Z)+* Concat(&s4, s3, s1);*Y Concat(&t, SubString(&s5, s, 1, 5), s4);(X+Z)*Y 第五章本章小结数组的两种存储映像方式：行序为主列序为主特殊

21、矩阵的压缩存储，关键要确定下标之间的映射关系式。稀疏矩阵的三元组顺序表、行逻辑链接的顺序存储和十字链表存储，它们分别应用于矩阵的不同运算中。要注意分析区别使用的场合。广义表的递归定义和存储结构。1、 数组 -线性表的扩展，其表中的数据元素本身也是一个数据结构。2、数组的顺序表示和实现数组类型的特点:只有引用型操作，没有加工型操作(插入和删除 )，即不作插入和删除操作数组是多维的结构，而存储空间是一个一维的结构有两种顺序映象的方式：以行序为主序(低下标优先 ) 二维数组 A 中任一元素ai,j 的存储位置LOC(i,j) = LOC(0,0) + (b2ij)L 其中 LOC(0,0) 称为基地

22、址或基址n 维数组数据元素存储位置的映象关系：LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji 其中cn = L ，ci-1 = bi ci , 1 =0) 个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2 的结点， 并且二叉树的子树有左子树和右子树之分。2、 二叉树的五种基本形态：空树只含根结点右子树为空树左子树为空树左右子树均不为空树3、二叉树的性质性质 1 ：在二叉树的第i 层上至多有2i-1 个结点 (i1)。其中 2i-1 为 2 的 i-1 次方性质 2：深度

23、为k 的二叉树上至多含2k-1 个结点 (k1)。其中 2k-1 为 2的 k 次方减一性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、 n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。证明： 设二叉树上结点总数n = n0 + n1 + n2， 二叉树上分支总数b = n1+2n2， 而 b = n-1 = n0 + n1 + n2 1 由，n0 = n2 + 1 。除根结点外，其余结点都有一个分支进入，设b 为分支总数，则n=b+1 性质 4：具有 n 个结点的完全二叉树的深度为 log2n +1。其中 log2n 为不大于log2n 的最大整数性质5：若对含n 个结点

24、的完全二叉树从上到下且从左至右进行1 至 n 的编号，则对完全二叉树中任意一个编号为i 的结点：(1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若 2in，则该结点无左孩子，否则，编号为2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。4、 两类特殊的二叉树：满二叉树：指的是深度为k 且含有 2k-1 个结点的二叉树。其中2k-1 为 2 的 k 次方减一特点：是每一层上的结点数都是最大结点数。完全二叉树：树中所含的n 个结点和满二叉树中编号为1 至 n 的结点一一对应。特点：叶子结点

25、只可能在层次最大的两层出现；对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l 或 l+1。性质练习：1. 一棵二叉树在其第五层中有17 个结点，可不可能？第 i 层上至多有2i-1 个结点，则25-1=16。所以，不可能。2. 二叉树的根结点属于第0 层还是属于第1 层？第 1 层3. 已知一棵二叉树有20 个结点，其中 6 个结点为叶子， 则该树中度为2 的结点数为5 ？度为 0 的结点为6 ？由性质 3：n0=n2+1，则 n2=n0-1=6-1=5 。4. 已知一棵完全二叉树中编号为101 的结点有LC 和 RC 结点，则其LC 结点编号为202 ，RC 结

26、点编号为203 ？由性质 5，可知左孩子为2i，右孩子为2i+1 5. 一棵深度为h 的完全 k 叉树，如果按层次自顶向下、同一层自左向右、顺序从1 开始对全部结点进行编号，试问：该树上最多有多少个结点？最少有多少个结点？由性质 1 和定义，可知除第h 层外，其余各层都是满的，所以：1+k+k2+.+kh-2=(kh-1-1)/(k-1)，则最多有：(kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)；最少有： (kh-1-1)/(k-1)+1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

27、 - - - - 第 6 页，共 12 页 - - - - - - - - - 三、二叉树的存储结构1、顺序存储结构：特点：一组地址连续的存储单元存储各结点(定义一个一维数组)；自根而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。缺点：空间利用率太低！2、 链式存储结构：二叉链表：结点结构至少包含：数据域和左右孩子指针域lchild data rchild 三叉链表：结点结构至少包含：数据域、左右孩子指针域、双亲指针parent lchild data rchild 四、遍历二叉树和线索二叉树1、遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅

28、被访问一次。基本操作是访问结点先 (根)序的遍历算法：若二叉树为空树，则空操作；否则，访问根结点；先序遍历左子树；先序遍历右子树。中 (根)序的遍历算法：若二叉树为空树，则空操作；否则，中序遍历左子树；访问根结点；中序遍历右子树。后 (根)序的遍历算法：若二叉树为空树，则空操作；否则，后序遍历左子树；后序遍历右子树；访问根结点。2、建立二叉树的存储结构：基本要点：以 遍历 为基本出发点；不同的遍历方法相应地有不同的建立算法代码如何由二叉树的先序和中序序列建树？3、 线索二叉树指向该线性序列中的 前驱 和 后继 的指针，称作 线索 。包含“线索”的存储结构，称作“线索链表” 。与其相应的二叉树，

29、称作“线索二叉树”遍历二叉树的结果是，求得结点的一个线性序列。线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索，而前驱或者后续的信息只有在遍历时才能得到，因而线索化的过程即为在遍历的过程中修改空指针的过程。四、树和森林1、树的存储结构双亲表示法：用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。其中根节点的值为-1 孩子链表表示法：树结点表和孩子结点表为了快速查找每个结点的孩子结点树的二叉链表(孩子 -兄弟 )存储表示法：又称二叉树表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向结点的第一个孩子结点和下一个兄弟结点。左边孩子右边兄弟与孩子兄弟链表对应

30、的二叉树：转化后，二叉树的右子树必为空！2、森林与二叉树的转换给定一棵树，可以找到惟一的一棵二叉树与之对应。 用二叉链表作为存储结构（依据）把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，即作为二叉树的右子树，则同样可以导出森林和二叉树的对应关系。注意：和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。3、树和森林的遍历两种遍历树的方法：先根 (次序 )遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根 (次序 )遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。森林的遍历：森林由三部分构成：森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树

31、构成的森林。遍历森林：先序遍历：若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中 (除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中 (除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。五、哈夫曼树及其应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 -

32、- - - - - - - - 1、最优二叉树 (哈夫曼树 ) 结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度：树中每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和WPL(T) = wklk (对所有叶子结点) 在所有含n 个叶子结点、 并带相同权值的m 叉树中，必存在一棵其带权路径长度取最小值的树，称为 最优树 。2、 如何构造最优树？(赫夫曼算法 ) 以二叉树为例：根据给定的n 个权值w1, w2, , wn ，构造n 棵二叉树的集合F = T1, T2, , Tn ，其中每棵二叉树中均只含一个带权值为wi 的根结点，其左、右子树为空树；在F

33、中选取其根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；从 F 中删去这两棵树，同时加入刚生成的新树；重复(2) 和 (3) 两步，直至F 中只含一棵树为止。3、采用二叉树设计二进制前缀编码规定：左分支用0表示；右分支用 1表示。4、算法实现：由于哈夫曼树中没有度为1 的结点，则一棵有n 个叶子结点的哈夫曼树共有2n-1 个结点（因n2=n0-1)，可以存储在一个大小为2n-1 的一维数组中。5、编码需要从叶子到根；译码需要从根到叶子课后作业P38：6.5 P39：6.6(要求：写出推导过程) 1. 某二叉树的先

34、序遍历结点访问顺序是abdgcefh，中序遍历的访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（） 。2. P41： 6.23 P41：6.23，然后将该树转化为对应的二叉树。6.26 第 7 章 图本章小结图是一种复杂的非线性结构。图的存储表示方法：邻接矩阵邻接表十字链表 有向图邻接多重表 无向图图的遍历：深度优先、广度优先图的遍历的应用：最小生成树、拓扑排序及关键路径、最短路径等问题各种算法思想！一、图的定义和基本术语1、图的定义图形结构：较线性表和树更为复杂的数据结构。结点之间的关系是任意的，图中任意两个数据元素都可能相关。图的结构定义：图：是由一个顶点集V 和一个顶点间的关系

35、集合组成的数据结构。Graph = (V , VR) 其中， V = x | x 某个数据对象 ，是顶点的有穷非空集合；2、顶点之间关系的有穷集合，也叫做边(edge)或弧 (Arc)集合。“弧”是有方向的，3、由顶点集和弧集构成的图为有向图。由顶点集和边集构成的图称作无向图基本术语有 (无)向网：弧 (边)上带权的图假设图中有n个顶点， e 条边，则含有e=n(n-1)/2 条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数en-1 时，则形成环；边数n-1时则不连通五、最小生成树构造网的一棵最小生成树，即：在e 条带权的边中选取n-1 条边（不构成回路）

36、 ，使 权值之和 为最小。1、普里姆算法：基本思想：第一步：取图中任意一个顶点v 作为生成树的根；第二步：往生成树上添加新的顶点w。在添加的顶点w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点v 和 w 之间的边中取值最小；第三步：继续往生成树上添加顶点，直至生成树上含有n 个顶点为止。构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。2、 克鲁斯卡尔算法：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。基本思想：第一步：构造一个只含n 个顶点的子图SG；第二步：从权值最小的边开始，若它的添加不使SG 中

37、产生回路，则在SG 上加上这条边；第三步：如此重复，直至加上n-1 条边为止比较两种算法：普里姆算法： O(n2)、适用于稠密图克鲁斯卡尔算法：O(eloge)、适用于稀疏图六、有向无环图及其应用定义：一个无环的有向图称作有向无环图1、拓扑排序检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network) ，简称 AOV- 网。在 AOV- 网中不应该出现有向环。对给定的AOV- 网需首先判断网中是否有环。如何进行拓扑排序？从有向图中选取一个没有前驱的顶点，并输出之；从有向

38、图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。在算法中需要用定量的描述替代定性的概念：没有前驱的顶点入度为零的顶点；删除顶点及以它为尾的弧弧头顶点的入度减1。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 为避免每次都要搜索入度为零的顶点，在算法中设置一个 栈 ，以保存 入度为零 的顶点2、关键路径“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。3、最短路

39、径从某顶点出发，沿图的弧到达另一顶点所经过的路径中，各边上权值之和最小的一条路径 最短路径。注意：和关键路径区别！课后作业P47：7.3 2. 假设图 G 采用邻接表存储，设计一个算法，输出图G 中从顶点u 到 v 的长度为1 的所有简单路径。1. P47： 7.7(2) P48：7.10、 7.11 第 9 章 查找本章小结查找表是由同一类型的数据元素(或记录 )构成的集合。对查找表经常进行的操作：查询检索插入删去静态查找表：顺序表有序表：等概率：折半查找判定树不等概率：静态树表的查找次优二叉查找树动态查找表：二叉排序树和平衡二叉树B-树哈希表查找的方法取决于查找表的结构一、静态查找1、顺序

40、表的查找以顺序表表示静态查找表, 称为顺序查找表。 哨兵 的作用：免去查找过程中每一步都要检测整个表是否查找完毕。分析顺序查找的时间性能：在等概率查找的情况下，顺序表查找的平均查找长度为：当查找不成功的情况不能忽视时，且等概率情况下=3(n+1)/4 2、有序表的查找折半查找若以有序表表示静态查找表，则查找过程可以基于“折半”进行。注意：折半查找只适用于有序表，且限于顺序存储结构！静态树表的查找在不等概率查找的情况下，折半查找不是有序表最好的查找方法。次优二叉树的构造方法请看 PPT 第九章幻灯片203、动态查找表特点：表结构本身在查找过程中动态生成。二叉排序 (查找 )树：或者是一棵空树；或

41、者是具有如下特性的二叉树，若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也都分别是二叉排序树。如何构造二叉排序树是重点平衡二叉树 (又称 AVL 树)树中每个结点的左、右子树深度之差(称为平衡因子BF)的绝对值不大于1 AVL 树的平均查找长度和logn 是同数量级的！B-树 定义：是一种平衡的多路查找树。一棵 m 阶(结点的最大分支数)的 B-树上：多叉树的特性：非终端结点结构为：(n, A0 ,K1 ,A1 ,K2 , A2 ,K3 , A3 ,Kn , An )每个非终端结点可能含有：至多 n 个关键字

42、Ki ，n m-1；至少含有m/2 -1 个关键字 Ki，即m/2 -1n;n+1 个指向子树的指针Ai(0in); 查找树的特性：非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn; 且 Ai-1 所指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于Ki; 21111n)i(nnASLnissnPi1)1(111nP)i(nPASLniusnisss名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - -

43、平衡树的特性：树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少含有两棵子树 (至少有一个关键字);其余所有非叶结点均至少含有m/2 棵子树，至多含有m 棵子树 ; 课堂练习其他答案请看PPT 第九章1. 有一个长度为12 的有序表R0.11，按折半查找法对表进行查找，在表中各元素等概率情况下查找成功所需的平均比较次数为。2. 有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,99 ，当采用折半查找法查找关键字为82 的元素时，4 次比较后查找成功。构造判定树如下：3. 顺序查找含n 个元素的顺序表，若查找成功，则比较关键字的次数最多为n

44、 次；若查找不成功，则比较关键字的次数为n+1 次。4. 如图所示的二叉排序树，其成功的平均查找长度是；不成功的平均查找长度是。5. 一棵深度为k 的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有个结点。由于每个非叶子结点的平衡因子均为0，也即每个非终端结点都有左子树和右子树且高度相等；因此，这样的AVL 树即为满二叉树，而高度为h 的满二叉树的结点数为 2h-1。则本题答案为2k-1。6.高度为 5(除叶子层之外 )的三阶 B-树至少有个结点。由 m 阶 B-树性质可知：根结点至少有两颗子树、根结点之外的所有非叶子结点至少有m/2棵子树；则三阶B-树的形状至少类似于一棵满二叉树，也

45、即高度为5 的三阶 B-树至少有 25-1=31 个结点。本题答案为31。二、哈希表这个是重点查找的过程为：给定值依次和关键字集合中各个关键字进行比较；查找的效率取决于和给定值进行比较的关键字个数建立关键字与记录在表中的存储位置之间的函数关系，以 f(key) 作为关键字为key 的记录在表中的位置，通常称这个函数f(key)为哈希函数。关键要素：哈希函数H(key)处理冲突的方法假设哈希表的地址集为0 至(n-1)：冲突是指由关键字得到的哈希地址为j 的位置上已存有记录。 处理冲突 就是为该关键字的记录找到另一个 空 的哈希地址。开放定址法：为产生冲突的地址H(key) 求得一个地址序列H0

46、, H1, H2, , Hs1 sm-1 其中： H0 = H(key) Hi = ( H(key) + di ) MOD m ， i=1, 2, , s链地址法：将所有哈希地址相同的记录都链接在同一链表中。排序中的基本操作：比较关键字大小和 移动记录不同的具体实现方法导致不同的算法描述：直接插入排序 (基于顺序查找 ) 折半插入排序(基于折半查找) 表插入排序 (基于链表存储) 希尔排序 (基于逐趟缩小增量 ) 1、直接插入排序利用“顺序查找”实现 在 R1.i-1 中查找 Ri的插入位置 。算法的实现要点：从Ri-1 起向前进行顺序查找，监视哨设置在R0 n 个元素需进行n-1 趟排序。最

47、好情况 : 关键字在排序前已递增有序。 比较 的次数： 移动 的次数： 0 最坏情况 : 关键字在排序前为递减有序。 比较 的次数： 移动 的次数：直接插入排序是一种稳定的排序方法2、折半插入排序因为R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在 R1.i-1 中查找 Ri的插入位置” ，如此实现的插入排序为折半插入排序。3、表插入排序利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都112nni2)1)(2()(2nnini2)1)(4()1(2nnini名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

48、- - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 调整到它们所应该在的位置上。4、希尔排序又称缩小增量排序( 希尔排序是一种不稳定的排序方法基本思想： 对待排记录序列先作 宏观 调整， 再作 微观 调整。所谓 宏观 调整，指的是， 跳跃式 的插入排序。具体做法：将记录序列分成若干子序列，分别对每个子序列进行插入排序。5、交换排序起泡排序基本思想：注意：起泡排序的结束条件为，最后一趟没有进行 交换记录 ；一般情况下，每经过一趟 起泡 ，i 减1 ，但并不是每趟都如此。时间性能分析：最好的情况 (关键字

49、在记录序列中顺序有序)：只需进行一趟起泡。 比较 的次数： n-1 移动 的次数： 0 最坏的情况 (关键字在记录序列中逆序有序)：需进行n-1 趟起泡。 比较 的次数： 移动 的次数：(每次移动记录3 次) 起泡排序方法是稳定的。快速排序一趟快速排序 (一次划分 )：目标：找一个记录，以它的关键字作为 枢轴 ，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后快速排序是不稳定的排序方法。6、选择排序基本原理：将待排序的记录分为已排序(初始为空 )和未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。简单选择排序和堆排序堆排序：堆排序只需要一个

50、记录大小的辅助空间。堆排序分为两个步骤：根据初始输入，形成初始堆。建堆通过一系列的记录交换和重新调整进行排序。筛选如何 筛选 ？ 筛选 指的是，对一棵左/右子树均为堆的完全二叉树， 调整 根结点使整个二叉树也成为一个堆。如何 建堆 ？建堆是一个从下往上进行 筛选 的过程。从最后一个非终端结点，即第n/2个元素开始 筛选 ！堆排序的时间复杂度分析：对深度为k 的堆， 筛选 所需进行的关键字比较的次数至多为2(k-1)； 对 n 个关键字，建成深度为h(= log2n +1)的堆，所需进行的关键字比较的次数至多4n；堆排序的时间复杂度为O(nlogn)。空间复杂性为O(1) 堆排序是不稳定的排序方