自考02331数据结构重点总结最终修订

1、自考 02331 数据结构重点总结 ( 最终修订 )第一章 概论1. 瑞士计算机科学家沃思提出：算法 +数据结构 =程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储 结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大 程度上取决于描述实际问题的数据结构。2. 数据 是信息的载体。 数据元素 是数据的基本单位。一个数据元素可以由若干个数据项 组成， 数据项 是具有独立含义的最小标识单位。 数据对象 是具有相同性质的数据元素的集合。3. 数据结构 指的是数据元素之间的相互关系，即数据的组织形式。 数据结构一般包括以下三方面内容：数据的逻辑

2、结构、数据的存储结构、数据的运算 数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。 数据的逻辑结构分类 : 线性结构和非线性结构。线性表 是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 数据元素及其关系在计算机内的存储方式，称为数据的存储结构(物理结构)。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。 数据的运算 。最常用的检索、插入、删除、更新、排序等。4. 数据的四种基本存储方法 : 顺序存储、链接存储、索引存储、散列存储( 1 )( 2 )( 3 ) ( 4 )顺序存储 链接存储 索引存

3、储 散列存储通常借助程序设计语言的 数组 描述。 通常借助于程序语言的指针来描述。 索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。5 个准则： 输入 ， 0 个或多个数据作为输入； 输出 ，产生一个或多个输出； 有穷性 ，算法执行有限 可行性 ，算法是可行的。5. 算法必须满足 步后结束； 确定性 ，每一条指令的含义都明确；算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal 和类 C。6

4、. 评价算法的优劣：算法的 正确性 是首先要考虑的。此外，主要考虑如下三点： 执行算法所耗费的时间，即时间复杂性； 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。7. 算法求解问题的 输入量称为问题的规模，用一个正整数n表示。8. 常见的时间复杂度按数量级递增排列依次为： 常数阶 0(1) 、对数阶 0(log 2n) 、线性阶 0(n) 、线性对数阶 0(nlog 2n) 、 平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2)和阶乘阶0(n!

5、)。9. 一个算法的空间复杂度 S(n) 定义为该算法所耗费的存储空间，它是问题规模 n 的函数 ， 它包括存储算法本身所占 的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章 线性表1. 数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。2. 只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。3. 常见的线性表的基本运算 :(1) 置空表 InitList ( L) 构造一个空的线性表 L。 求表长ListLength ( L)求线性表L中的结点个数，即求表长。(3)GetNode ( L

6、， i ) 取线性表 L 中的第 i 个元素。LocateNode ( L, x)在L中查找第一个值为x的元素，并返回该元素在L中的位置。若L中没有元素的值为 x ,则返回 0 值。InsertList( L, i , x)在线性表L的第i个元素之前插入一个值为 x的新元素，表L的长度加1。(6)DeleteList( L， i )删除线性表 L 的第 i 个元素，删除后表 L 的长度减 1。4. 顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表( Sequential List )：用顺序存储方法存储的线性表称为顺序表。 顺序表 是一种 随机存取结构

7、 ， 顺序表的特 点是逻辑上相邻的结点其物理位置亦相邻。顺序表中结点 ai的存储地址：LOC ( a) = LOC (a) + (i-1 ) *c Ki data和p- next 指针变量p和结点变量*p的关系：指针变量p的值一一结点地址，结点变量*p的值一一结点内容7. 建立单链表：(1) 头插法建表：算法：p=(ListNode *)malloc(sizeof(ListNode);/ 生成新结点(2) 尾插法建表： 算法： p=(ListNode *)malloc(sizeof(ListNode);/ 生成新结点p-data=ch; II将读入的数据放入新结点的数据域中if (head=N

8、ULL) head=p;/ 新结点插入空表else rear-next=p;/将新结点插到*r之后rear=p;/尾指针指向新表尾hmil(3) 尾插法建带头结点的单链表： 头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点：1由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上操作一致，无须进行特殊处理；2无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空表的处理也就统一了。在有的应用头结点数据域的阴影表示该部分不存储信息。 中可用于存放表长等附加信息。data=ch;/将读入的数据放入新

9、结点的数据域中r-n ext=s; r=s;r- next=NULL; 终端结点的指针域置空，或空表的头结点指针域置空 以上三个算法的时间复杂度均为8.单链表上的查找：(带头结点)(1)按结点序号查找：序号为0的是头结点。算法：p=head;j=0; 从头结点开始扫描顺指针向后扫描，直到0(n)。while(p- next&jn ext;j+;if(i=j) return p;/ else return NULL;/找到了第i个结点当i0时，找不到第时间复杂度：在等概率假设下，平均时间复杂度为：为 (2 )按结点值查找：具体算法：ListNode *p=head- next;/while(p&

10、p-data!=key)p-next 为 NULL或 i=j 为止i个结点n/2=0( n)表非空，p初始值指向开始结点从开始结点比较。直到p为NULL或p-data 为key为止p=p- next;/扫描下一结点return p;/ 若p=NULL则查找失败，否则p指向值为key的结点时间复杂度为：0(n)9.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到an与a之间。hrnd0(n)。s=(ListNode Un ir13. 循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若 在尾指针表示的单循环链表上实现，则只需

11、修改指针，无须遍历，其执行时间是)malloc(sizeof(ListNode); s-data=x; s-n ext=p-n ext; p-n ext=s; 算法的时间主要耗费在查找结点上，故时间复杂度亦为10. 删除运算*订 I! 朴I 內 -f* 丿 4任卑腿無l lllt络心利gr=p-next;/使r指向被删除的结点ai p-next=r-next;/将ai从链上摘下free(r);给存储池算法的时间复杂度也是 0(n) .p指向被删除的前一个结点。 链表上实现的插入和删除运算，无须移动结点，仅需修改指针。11. 单循环链表一在单链表中，将终端结点的指针域NULL改为指向表头结点或开

12、始结点即可。head=head-n ext;12. 仅设尾指针的单循环链表：用尾指针rear表示的单循环链表对开始结点a1和终端结点/释放结点ai的空间判断空链表的条件是an查找时间都是0(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为 rear=rear- n ext;rwi. f0(1)。卜W讣H悩代怙押馥氓fl .:汕具体算法：LinkList Connect(LinkList A,LinkList B)/ 假设 A, B为非空循环链表的尾指针LinkList p=A-next;/保存A表的头结点位置A-n ext=B- next-

13、next;/B表的开始结点链接到 A表尾free(B-next);/释放B表的头结点B- next=p;return B;/返回新循环链表的尾指针循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p- next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单 循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。14. 双向链表：双(向)链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增

14、加一个指向其直接刖趋的指针域prior。 双链表由头指针 head惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双(向)循环链表。15. 双向链表的前插和删除本结点操作 双链表的前插操作void DinsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为 x的新结点插入*p之前，设pz NULLDListNode *s=malloc(sizeof(DListNode);s-data=x;/ s-prior=p-prior;/ s-n ext=p;/p-prior- n ext=s;/p-prior=s;/mI双链

15、表上删除结点 *p自身的操作M应I那晾1+1void DDeleteNode(DListNode *p)/在带头结点的双链表中，删除结点*p，设*p为非终端结点p-prior- n ext=p-n ext;/p_n ext-prior=p-prior;free(p); /data ilclI与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为16.顺序表和链表比较0(1)。时间性能：a、线性表：经常性的查找；b、链式存储结构：经常插入删除操作；空间性能：a、对数据量大小事先能够知道的用线性表；b、数据量变化较大的用链式存储结构。存储

16、密度越大，存储空间的利用率越高。显然，顺序表的存储密度是1,链表的存储密度肯定小于1。第三章栈和队列1. 栈称为后进先出（Last In First Out）的线性表，简称为 LIFO表。栈是运算受限的线性表，顺序栈也是用数组表示的。进栈操作：进栈时，需要将 S- top加1,S- top=StackSize-1 表示栈满 上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。Fitnekl 中有 4亍天幸5- iki (J)退栈操作：退栈时，需将 S- top减1,S- topfront=Q-rear=0; 判队空：return Q-rear=Q-front; 判队满：return (Q-re

17、ar+1)%QueueSize=Q-front; 入队 Q-dataQ-rear=x;/新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; 出队 temp=Q-dataQ-front;Q-front=(Q-front+1)%QueueSize;/ 循环意义下的头指针加1return temp; 取队头元素return Q-dataQ-fro nt;6. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。UHfroTl AQf如N |-H.卜H1Hrear=Q-front ； Q-rea

18、r-next=NULL;(2) 判队空：return Q-rear=Q-fro nt;( 3 ) 入队： QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申请新结点p-data=x; p-next=NULL;Q-rear-next=p; /*p 链到原队尾结点后 Q-rear=p; / 队尾指针指向新的尾(4) 出队：当队列长度大于 1 时，只需修改头结点指针，尾指针不变 s=Q-front-next; Q-front-next=s-next;x=s-data; free(s); return x; 当队列长度等于 1 时，不仅要修改头结

19、点指针，还要修改尾指针 s=Q-front-next; Q-front-next=NULL; Q-rear=Q-front;x=s-data; free(s); return x;( 5) 取队头元素： return Q-front-next-data;因为有头结点，所以用了 next 和链栈类似，无须考虑判队满的运算及上溢。 在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点 时亦需修改尾指针，且删去此结点后队列变空。7. 用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。第四章 多维数组和广义

20、表1. 数组的顺序存储方式 : 一般采用顺序存储方法表示数组。1）行优先顺序a 11 ,a 12,a in,a 21 ,a 22,a2n,ami,am2,，amn2）列优先顺序a 11,a 21,a m1,a 12,a 22,am2,a1 n,a2n,，amnPascal和C语言是按行优先顺序存储的，而Fortran语言是按列优先顺序存储的。按行优先顺序存储的二维数组Amn地址计算公式LOC(aj )=L0C(a11)+(i-1) x n +j -1 xd (注：此公式下界为 1，如下界为0，则公式变为i x n +j )按列优先顺序存储的二维数组Amn地址计算公式LOC(aij )=LOC(

21、a11)+(j-1)xm+i-1xd ( 注：此公式下界为 1，如下界为 0，则公式变为 j x m+i)按行优先顺序存储的三维数组Amnp地址计算公式LOC(aijk )=LOC(a111)+(i-1)xnxp+(j -1)xp+k- 1xd ( 注 ： 此 公 式 下 界为 1 ， 如 下 界 为 0 ， 则 公 式 变 为i x nx p+j x p+k)2. 为了节省存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。 特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。(1 )对称矩阵 在一个n阶方阵A中，若元素满足下述性质：a

22、ij =aji 0 i , j j 0kn(n+1) /2-1k=jx(j+1)/2+i i vj 0kj 下三角矩阵中 aij 和 sak 之间的对应关系k=i x (i+1) /2+j 当 i j k=nx(n+1)/2 当 i v j三角矩阵的压缩存储结构是随机存取结构 。3. 稀疏矩阵：设矩阵Am冲有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。为了节省存储单元，可用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须 存储非零元素所在的行、列位置,所以可用三元组 (i , j , aij )来确定非零元素。稀疏矩阵进行压缩存储

23、通常有两类方法： 顺序存储 ( 三元组表 )和链式存储 (十字链表 ) 。稀疏矩阵的压缩存储会失去 随机存取功能。4. 广义表是线性表的推广，又称列表。广义表是n(n 0)个元素ai, a2,，a,，an的有限序列。其中ai或者是原子或者是一个广义表。 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示 原子。 若广义表Ls非空(n 1)，贝U ai是LS的表头，其余元素组成的表(ai, a2,，an)称为Ls的表尾。 广义表具有递归和共享的性质广义表的深度：一个表展开后所含括号的层数称为广义表的深度。19.广义表是一种多层次的线

24、性结构，实际上这就是一种树形结构。广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls).任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。head=(a , b)=a , tail(a , b)=(b)对非空表 A和(y)，也可继续分解。注意：广义表()和()不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为I的由空表作元素的广义表，可以分解得到的表头和表尾均是空表()。广义表是一种有层次的非线性结构，通常采用链式存储结构，每个元素用一个结点表示，结点由3个域构成，其中一个是tag标志位，用来区分结点是原子还是子表，当tag为零时

25、结点是子表，第二个域为 slink，用以存放子表的地址；当tag为1时结点是原子，第二个域为 data，用以存放元素值。第五章树和二叉树1. 树的表示法：最常用的是树形图表示法；还有3种嵌套集合、凹形、广义表。树结构的基本术语(1 )结点的度(Degree)树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。度为零的结点称为 叶子(Leaf)或终端结点。度不为零的结点称 分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。(2)路径(path )若树中存在一个结点序列k1,k2,，ki,使得ki是ki+1的双亲(1 i

26、1)。例如5层的二叉树，第5层上的结点数目最多为24=16k5性质2深度为k的二叉树至多有2 -1个结点(k 1)。例如深度为 5的二叉树，至多有 2 -仁31个结点性质3在任意-棵二叉树中，若终端结点的个数为n0,度为2的结点数为n2,则no=n?+1。例如一棵深度为4的二叉树(a),其终端结点数no为8,度为2的结点树为7,则8=7+1, n=n2+1成立(b)其终端结点数no为6,度为2的结点树为5,则6=5+1, n=n2+1成立满二叉树：一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：(1) 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树

27、。(2) 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。完全二叉树：若一棵深度为k的二叉树，其前 k-1层是一棵满二叉树，而最下面一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：(1) 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。(2) 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。(3) 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。性质4 具有n个结点的完全二叉树的深度为。？ logn? +1或？ log(n+1) ?例，具有 100 个结

28、点的完全二叉树的深度为：？ lg100? +1=7,2 6=64 2 7=128 所以？ lg100 ? =6 , ? lg(100+1) ? =74. 完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子等结点的编号。编号从0开始 若i=0，贝U q为根结点，无双亲；否则， qi的双亲编号为？ (i-1)/2 ?。 若2i+1n，则qi的左孩子的编号是 2i+1 ;否则，qi无左孩子，即q必定是叶子。 若2i+2n，则qi的右孩子的编号是 2i+2 ;否则，q无右孩子。对于完全二叉树而言，使

29、用顺序存储结构既简单又节省存储空间。但对于一般二叉树来说，采用顺序存储时，为了 使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。5. 链式存储结构：二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild 和rchild ，分别指向该结点的左孩子和右孩子。结点的结构为：lh,IJl 11 4二叉链表是一种常用的二叉树存储结构。建立二叉链表方法：a、按广义表方法，靠近左括号的结点是在左子树上，而逗号右边结点是在右子树上。b、按完全二叉树的层次顺序建立结点。具有n个结点的二叉链表中，共

30、有2n个指针域。其中有 n-1个用来指示结点的左、右孩子，其余的 n+1个为空。二叉树遍历算法中的递归终止条件是二叉树为空。中序遍历的递归算法定义：(1)遍历左子树；(2)访问根结点；遍历右子树。先序遍历的递归算法定义：(1)访问根结点；(2)遍历左子树；遍历右子树。后序遍历得递归算法定义：(1)遍历左子树；(2)遍历右子树；访问根结点。递归工作栈中包括两项：一项是递归调用的语句编号，另一项则是指向根结点的指针。已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列，可唯一确定一棵二叉树。具体方法如下： 首先根据前序或后序遍历序列确定二叉树的各子树的的根，然后根据中序遍历序列确定各子树根的左右

31、子树。6. 线索二叉树：n个结点的二叉链表必定存在n+1个空指针域，可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为”线索”，这种加上线索的二叉链表称为线索链表，相应的二叉树称为 线索二叉树(ThreadedBinaryTree)。线索链表的结点结构:lrhiId】琢datartagrrhi1d疋圭馄奥中的8丛壽肯为；其中:ltag 和rtag是增加的两个标志域，用来区分结点的左、右指针 域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。-I图中的实线表示指针，虚线表示线索。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均

32、是1。7. 二叉树的线索化：把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，线索化的算法时间复杂度为 0(n)。NULLI_401A 04Q二更线噸话畫NULL8. 树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。将树转换成二叉树：在所有兄弟结点之间加一道连线；对每个结点，除了保留与其长子的连线外，去掉该结点 与其它孩子的连线。由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。树到二叉树的转换h罰A（；D|1 J对*汁皓点，除

33、了保SjJC的长子的连钱外.点可用他孫子的将一个森林转换为二叉树将森林中的每棵树转化成二叉树，然后再将二叉树的根节点看做兄弟连在一起，形成一棵二叉树讲一涉；九豺飲朴中的何棵 树箜沖二叉榔第二步为兄弟从左住右连在 起.就形脈丁一棵一义9.二叉树到树、森林的转换方式是：若二叉树中结点 x是双亲y的左孩子，则把 x的右孩子，右孩子的右孩子，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。h下标JeLn1710. 树的存储结构：1. 双亲表示法：双亲链表表示法利用树中每个结点的双亲唯一性， 在存储结点信息的同时，为每个结点附设一个指向其双亲的指针 pare nt ,惟一地表示任何-棵树。（1 ）双

34、亲链表表示法的实现分析：E和F所在结点的双亲域是 1，它们的双亲结点在向量中的位 置是1，即卩B是它们的双亲。注意： 根无双亲，其pare nt域为-1。双亲链表表示法中指针 pare nt向上链接，适合求指定结 点的双亲或祖先（包括根）；求指定结点的孩子或其它后代时，可能 要遍历整个数组。2. 孩子链表法：孩子链表表示法是为树中每个结点设置一个孩子链 表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。d- I Il I Id注意： 孩子结点的数据域仅存放了它们在向量空间的序号。 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 将双亲链

35、表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。3. 孩子兄弟表示法： 在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的| .忙 Jj孩子兄弟链表表示。这种存储结构的最大优点是：它和二叉树的二 叉链表表示完全一样。可利用二叉树的算法来实现对树的 操作。11. 树的遍历:一般都只给出两种次序遍历树的方法：前序（先根次序）遍历和后序（后根次序）遍历。 前序遍历一棵树等价于前序遍历该树对应的二叉树 后序遍历一棵树等价于中序遍历该树对应的二叉树。对下面（a）图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJH和B

36、DCAIFJGHE而（b）图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH BDCAIFJGHE 前序遍历森林等同于前序遍历该森林对应的二叉树 后序遍历森林等同于中序遍历该森林对应的二叉树12. 从根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树种所有叶子结点的带权路径长度之和称为树的带权路径长度。带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。哈夫曼树不一定是二叉树。哈夫曼树又称为最优树，是一类带权路径长度最短 的树。完全二叉树就是这种 路径长度最短的二叉树。 只有叶结点上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉

37、树。 最优二叉树中，权越大的叶子离根越近。 最优二叉树的 形态不唯一， WPL最小。13哈夫曼算法：基本思想是：(1)根据给定的n个权值w , W2,，Wn构成n棵二叉树的森林 F=，T2,，Tn，其中每棵二叉树 T中都只有一个权值为 w的根结点，其左右子树均空。(2) 在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。(3) 对新的森林F重复，直到森林F中只剩下一棵树为止。这

38、棵树便是哈夫曼树。 注意： 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 n个叶子的哈夫曼树要经过 n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 哈夫曼树是严格的二叉树，没有度数为1的分支结点。14哈夫曼编码：数据压缩过程称为编码，反之，解压缩的过程称为解码。设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。可以利用二叉树来设计二进制的前缀编码，其左分支表示字符0，右分支表示字符1,则以根结点到叶结点路径上的分支字符组成的串作为该叶节点的字符编码。因此设计电文总长最短的二进制前缀编码，就是以n

39、种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。译码过程是从树根结点出发，逐个读入电文中的二进制码。第六章图1. 图G由两个集合构成，顶点集合和边集合，也可以图G只有顶点而没有边。用尖括号表示图的有向边,有向边又称为弧，起点称为弧尾，终点称为弧头。无向图的顶点对用圆括号表示(Vi,Vj)。在无向图中，称 Vi和Vj相邻接，在有向图中称顶点Vi邻接到Vj ,顶点Vj邻接于Vi在无向图中，n的取值范围是0-n(n-1)/2 ，将具有n(n-1)/2 条边的无向图称为无向完全图。 在有向图中，n的取值范围是0-n(n-1)，将具有n(n-1)条边的有向图称为有向完全图。无

40、向图中，顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。在无向图中，任意两顶点都有路径，则称两顶点连通。若图G中的任意两个顶点都连通，称G为连通图。无向图的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量。在有向图中，图 G中任意两顶点连通，称为强连通图，极大连通子图称为强连通分量。若在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图，带权的连通图称为网络。2. 图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从0开始。邻接矩阵表示法：或(v i ,v j)是边，则值为1,不是边则值为 0

41、。无向图的邻接矩阵是按主对角线对称的。若G是带权图，只要把 1换成相应边上的权值即可，0的位置上可以不动2 或将其换成无穷大表示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素，时间复杂度为0( n)邻接表表示法： 邻接表是图的一种链式存储结构。将无向图的邻接表称为边表，将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。若无向图有n个顶点和e条边，则它的邻接表共有n个头结点和2e个表结点。建立邻接表的时间复杂度是0(n+e)。图的邻接表表示不是唯一的，这是因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。3. 图的遍历：遍历图的算

42、法是求解图的连通性、图的拓扑排序等算法的基础。 图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。深度优先搜索遍历(DFS)类似于前序(先根)遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历序列，或简称为 DFS序列。共需要搜索 n2个矩阵元素，时间复杂度为邻接矩阵0(n2)或邻接表0(n+e)。I“无訂国5 5的視燈优先擾囁彫历过程示点广度优先搜索遍历(BFS)类似于树的按层次遍历，先被访问的顶点，其邻接点也先被访问，就是先进先出。 时间复杂度为邻接矩阵 0(n2)或邻接表0(n+e)，空间复杂度都是 0(n)。4. 生成树是连通图的包含图中所有顶点的一个极小连通子图，

43、一个图的极小连通子图恰为一个无回路的连通图，也 就是说，若图中任意添加一条边，就会出现回路，若去掉任意一条边，都会使之成为非连通图。因此，一个具有 n个顶点的生成树有且仅有 n-1条边，但有n-1条边的图不一定是生成树，同一个图可以有不同 的生成树。生成树定义为：若从图的某顶点出发，可以系统的访问到图的所有顶点，则遍历时经过的边和图的所有顶点所构 成的子图，称为该图的生成树。最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树(MST。构造最小生成树的算法：普里姆Prim算法的时间复杂度为 0( n2)与网中边数无关适于稠密图。克鲁斯卡尔Kruskal算法的时间复杂度为 0( elo

44、ge )，主要取决于边数，较适合于稀疏图。【例&3】利用脅里姆算迄给出求图6J7(d)Cc)(f)圍KI*克魯斯卡尔盂小主成树的生成过程5. 最短路径：Dijkstra 迪杰斯特拉算法，提出了按路径长度递增的顺序产生诸顶点的最短路径算法。拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动的先后关系。这样的有向无环图DAG称为顶点活动网，简称为AOV网。将有向无环图G中所有顶点排成一个线性序列，若 E (G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。由AOV网构造拓扑序列的过程称为拓扑排序。检测的方法是：对有向图构造其顶点的拓扑序列，若网中所有顶点都在他的拓扑序列中，则AOV网必定

45、不存在环。AOV网的拓扑序列不是唯一的。拓扑排序的描述思想：a、在有向图中选一个没有前趋 (入度为零)的顶点，且输出之。b、从有向图中删除该顶点及其与该顶点有关的所有边。c、重复上述步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。d、输出剩余的无前趋结点。拓扑排序实际上是对邻接表表示的图G进行遍历的过程。时间复杂度是O(n+e)。图6J2 iS杰斯特拉算法求圏6J1的单源最顼蜡怪示蕙图第七章排序1.如果待排序文件中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不 变，该排序方法是稳定的；反之，则是不稳定的。排序在内存中处理，不涉及数据的内外存交换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、 选择、交换、归并和分配排序。在排序过程中需进行两种操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身，而待排序记录的 存储形式一般有三种：顺序结构、链式结构和辅助