数据结构期末复习资料

第一章

1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。

2、数据结构的形式定义：二元组Data_Structure=(D,S) 其中，D是数据元素的有限集，S是D上关系的有限集。

3、数据元素之间关系的映像：

１、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。

2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。 任何一个算法的设计取决于数据(逻辑)结构，其实现取决于物理结构。

4、 算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一

个或多个操作。

特性：有穷性、确定性、可行性、输入、输出 5、 算法的评价——衡量算法优劣的标准 正确性(correctness):满足具体问题的需求 可读性(readability)：易读、易理解

健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理 效率与低存储量:执行时间短、存储空间小

第二章

1、线性表是一种最简单的线性结构。

线性结构 是一个数据元素的有序（次序）关系

特点：存在唯一的一个―第一个‖的数据元素；存在唯一的一个―最后一个‖的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继

2、线性表类型的实现——顺序映像 定义：用一组地址连续的存储单元依次存放线性表中的数据元素。

以―存储位置相邻‖表示有序对，则有：LOC(ai) = LOC(ai-1) + l其中l是一个数据元素所占存储量

LOC(ai) = LOC(a1) + (i-1)×l 特点：1、实现逻辑上相邻—物理地址相邻2、实现随机存取

3、若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：

1n1Eis(ni1)

n1i1n 2若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

n11n Edl(ni)2ni14、 线性表类型的实现——链式映像 线性链表 特点：用一组地址任意的存储单元存放线性表中

的数据元素。

5、在单链表中第 i 个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。

s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e; s->next = p->next; p->next = s; // 插入

在单链表中删除第 i 个结点的基本操作为:找到线性表中第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->next = p->next->next; p->next->prior = p;（要删除的是p的下一个结点） 课后作业 P13: 2.3、2.5 P15: 2.8、2.9(2)

第三章

1、栈、队列的特点：

 从数据元素间的逻辑关系看是线性表

 从操作方式与种类看不同于线性表：栈与队列是操作受限的线性表

2、栈的基本概念 栈---是限制仅在线性表的一端进行插入和删除运算的线性表。

栈顶（TOP）--允许插入和删除的一端。 栈底（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；非空栈时，总是指向栈顶元素＋1的位置。

 插入一个栈顶元素，指针top增1；  删除一个栈顶元素，指针top减1；

 非空栈中的栈顶指针始终在栈顶元素的下一个位置上

链栈 ：注意: 链栈中指针的方向指向前驱结点！ 6、队列

 队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。

 队尾(rear)——允许插入的一端  队头(front)——允许删除的一端

 队列特点：先进先出(FIFO) 7、队列类型的实现

 链队列——队列的链式表示和实现

 顺序队列——队列的顺序表示和实现 用一组连续的存储单元依次存放队列中的元素 8、顺序队列运算时的头、尾指针变化

设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=0 空队列条件：Q.front==Q.rear 队列满：Q.rear-Q.front=m 入队列： Q.base[rear++]=x; 出队列：x=Q.base[++front]; 存在问题：设数组维数为M，则：

 当rear-front=m时，再有元素入队发生溢出——真溢出

 当rear已指向队尾，但队列前端仍有空位置时，再有元素入队发生溢出——

假溢出！

9、 循环队列：将数组首尾相接（即：base[0]连在base[m-1]之后)。 入/出队列运算

利用―模运算‖，则：

 入队：Q.rear=(Q.rear+1)%m  出队：Q.front=(Q.front+1)%m 队满和队空判断条件： 少用一个元素空间：

队空：Q.rear=(Q.front) 队满：(Q.rear+1)%m=Q.front 10、

栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 a) 栈具有―后进先出‖的特性； b) 队列具有―先进先出‖的特性。 11、

栈的链式存储不需头结点。

课后作业

1. 用栈结构计算中缀式2+(4-3)*6，画出计算过程栈的结构。 2. 简述以下算法的功能(栈和队列的元素类型均为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' (n≥0)

 串中字符的个数n称为串的长度；零个字符，即长度为零的串称为空串，用或''表示。 空串不等于空格串，空格串：由一个或多个空格组成的串 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串相应地称为主串

相等：两个串的长度相等，并且对应位置的字符都相同。 2、串结构与线性表结构的比较：

逻辑结构：极为相似，区别仅在于串的数据对象约束为字符集。

基本操作：有很大差别1、线性表大多以―单个元素‖作为操作对象2、串通常以―串的整体‖作为操作对象 3、串类型定义

4、 串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。

1、 StrAssign (&T, chars) 初始条件：chars 是字符串常量。操作结果：把 chars 赋为 T 的值。

等价于C语言中的strset函数

2、 StrCopy (&T, S) 初始条件：串 S 存在。操作结果：由串 S 复制得串 T。等价于C语言中

的strcpy函数

3、 StrCompare (S, T) 初始条件：串 S 和 T 存在。操作结果：若S＞T，则返回值＞0； 若S

＝T，则返回值＝0； 若S＜T，则返回值＜0。等价于C语言中的strcmp函数(按ASCII码值进行大小比较)

4、 StrLength (S) 初始条件：串 S 存在。操作结果：返回 S 的元素个数，称为串的长度。等

价于C语言中的strlen函数

5、 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。操作结果：用T返回由S1和S2联接而

成的新串。

例如： Concate( T, man, kind) 求得 T = mankind 等价于C语言中的strcat函数 6、 SubString (&Sub, S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S) 且 0≤len≤

StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”中的一个字符子序列。例如：SubString( sub, 'commander', 4, 3)，求得sub = 'man'；

SubString( 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是非空串， 1≤pos≤StrLength(S)。操作结果：若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置;否则函数值为0。

“子串在主串中的位置”指子串中的第一个字符在主串中的位序。

假设 S = abcaabcaaabc, T = bca Index(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 7、StrInsert (&S, pos, T) 初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T

例如：S = 'chater'，T = 'rac'，则执行 StrInsert(S, 4, T)之后得到S = 'cha racter' 二、串的表示和实现

1、定长顺序存储表示：用一组地址连续的存储单元存储串值的字符序列，称为顺序串。可用一个数组来表示。

特点：①串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为―截断‖ 。②按这种串的表示方法实现的串运算时，其基本操作为 ―字符序列的复制‖ 顺序存储结构中，串操作的基本操作为―字符序列的复制‖，其时间复杂度基于复制的字符序列的长度。

2、堆分配存储表示：特点：仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。

串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。 3、串的模式匹配算法 课堂练习

已知：a=‗THIS‘, f=‗A SAMPLE‘, c=‗GOOD‘, d=‗NE‘, b=‗ ‗,

1、s=Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))), 2、t=Replace(f, SubString(f, 3, 6), c), 3、u=Concat(SubString(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 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);Concat(&s4, s3, s1);

'*'

'(X+Z)*Y'

第五章

Replace(&s, s1, s2); '(X+Z)+*'

'*Y'

Concat(&t, SubString(&s5, s, 1, 5), s4);

本章小结

 数组的两种存储映像方式：

 行序为主  列序为主

 特殊矩阵的压缩存储，关键要确定下标之间的映射关系式。

 稀疏矩阵的三元组顺序表、行逻辑链接的顺序存储和十字链表存储，它们分别应用于矩阵的

不同运算中。要注意分析区别使用的场合。  广义表的递归定义和存储结构。

1、 数组---线性表的扩展，其表中的数据元素本身也是一个数据结构。 2、数组的顺序表示和实现

数组类型的特点:①只有引用型操作，没有加工型操作(插入和删除)，即不作插入和删除操作

②数组是多维的结构，而存储空间是一个一维的结构

有两种顺序映象的方式：①以行序为主序(低下标优先) 二维数组A中任一元素ai,j 的存储位置

LOC(i,j) = LOC(0,0) + (b2×i＋j)×L 其中LOC(0,0)称为基地址或基址 n维数组数据元素存储位置的映象关系：

LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + ∑ ci ji 其中 cn = L，ci-1 = bi ×ci , 1 < i  n。称式(5-2)为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。

例如：设按低下标优先存储整数数组A9×3×5×8时，第一个元素的字节地址是100，每个整数占四个字节。则LOC(a1111)=？ LOC(a3125)=？

解：由题可知，b1=9，b2=3，b3=5，b4=8。又L=4(字节)，则 c4=4，c3=b4×c4=8×4=32，

c2=b3×c3=5×32=160，c1=b2×c2=3×160=480 LOC(a1111)= 100+(480*1+160*1+32*1+4*1)=776 LOC(a3125)= 100+(480*3+160*1+32*2+4*5)=1784 ②以列序为主序(高下标优先) 3、矩阵的压缩存储

⑴特殊矩阵 定义：值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵。 若n阶矩阵A中的元素满足下述性质：aij=aji 1≤i, j≤n则称为n阶对称矩阵。 存储方式：以行序为主序存储矩阵的下三角(包括对角线)中的元。 存储空间：n(n+1)/2 一维数组sa[n(n+1)/2]中元素sa[k]和矩阵元aij的对应关系：

i(i1)j1 k{2j(j1)i12⑵三角矩阵：下(上)三角矩阵：矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的矩阵。 ⑶对角矩阵：所有的非零元素都集中在以主对角线为中心的带状区域中。 4、广义表的定义

广义表是递归定义的线性结构： LS = (α1, α2, ..., αn )

LS：广义表的名称 α1：表头 α2, ..., αn： 表尾 αi可以是单个元素(原子)，也可以是广义表(子表)

约定：用大写字母表示广义表的名称，用小写字母表示原子。 例如: A = ( )——长度为0；深度为1

F = (d, (e))——长度为2；深度为2 D = ((a,(b,c)), F)——长度为2；深度为3 C = (A, D, F)——长度为3；深度为4 B = (a, B) = (a, (a, (a, ... , ) ) )——长度为2 广义表是一个多层次的线性结构：

 广义表的结构特点：①广义表中的数据元素有相对次序；广义表的长度定义为最外层包含的

元素个数；广义表的深度定义为所含括弧的重数；广义表可以共享；广义表可以是一个递归的表。

注意:1. ―原子‖的深度为 0 2. ―空表‖的深度为 1 3. 递归表的深度是无穷值，长度是有限值。 任何一个非空广义表LS = (α1, α2, …, αn)均可分解为：表头：Head(LS) = α1和表尾：Tail(LS) = (α2, …, αn) 两部分。例如: D = ( E, F ) = ((a, (b, c))，F )，则 Head( D ) = E Tail( D ) = ( F ) ； Head( E ) = a Tail( E ) = ( ( b, c) )；5、 广义表的存储结构 ：通常采用头、尾指针的链表结构。

两种结构的结点：表结点：tag=1 hp tp 用以表示列表 原子结点：tag=0 data 用以表示原子

构造存储结构的两种分析方法：

表头、表尾分析法：空表 ls=NIL若表头为原子，则为tag=0 data 课堂练习

画出下列广义表的存储结构，并求出它的深度： L=((( )), a, ((b, c), ( ), d), (((e)))) 课后作业

1. 给出广义表(a, (b), ((), c, d))的存储结构。

Head( (( b, c)) ) = ( b, c)

Tail( (( b, c)) ) = ( )；Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )；Head( ( c ) ) = c Tail( ( c ) ) = ( )

第六章

本章小结

 二叉树的结构特性，各性质相应的证明方法。  二叉树的各种存储结构的特点及适用范围。

 遍历二叉树是二叉树各种操作的基础，遍历的具体算法与所采用的存储结构有关。  树和森林与二叉树的转换。

 最优二叉树的特性，掌握建立最优树和哈夫曼编码的方法。 -、树的定义

1、树型结构：（非线性结构）至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构。

树的定义：是n(n≥0)个结点的有限集合T，对于任意一棵非空树，它满足：有且仅有一个特定的称为根(root)的结点；当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2，….，Tm，其中每个集合本身又是一棵树，称为根的子树。上述树的定义是一个递归定义。 2、基本术语

结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数。叶子(或终端)

结点：度为零的结点。分支(或非终端)结点：度大于零的结点 树的度：树中所有结点的度的最大值 结点的层次：根结点的层次为1，第l层的结点的子树的根结点的层次为l+1。 树的深度：树中叶子结点所在的最大层次。

任何一棵非空树是一个二元组Tree = (root，F)其中：root 被称为根结点 F 被称为子树森林 二、二叉树

1、二叉树的定义是n(n>=0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。 2、 二叉树的五种基本形态：

空树 只含根结点 右子树为空树 左子树为空树 左右子树均不为空树 3、二叉树的性质

性质1 ：在二叉树的第 i 层上至多有2i-1 个结点(i≥1)。其中2i-1为2的i-1次方 性质2：深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。其中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 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

(1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点； (2)若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3)若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。 4、 两类特殊的二叉树：

满二叉树：指的是深度为k且含有2k-1个结点的二叉树。其中2k-1为2的k次方减一 特点：是每一层上的结点数都是最大结点数。

完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。

特点：⑴叶子结点只可能在层次最大的两层出现；⑵对任一结点，若其右分支下的子孙的最大层次为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结点编号为 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 三、二叉树的存储结构 1、顺序存储结构：

特点：一组地址连续的存储单元存储各结点(定义一个一维数组)；自根而下、自左而右存储结点；按

完全二叉树上的结点位置进行编号和存储。 缺点：空间利用率太低！ 2、 链式存储结构：

二叉链表：结点结构至少包含：数据域和左右孩子指针域 lchild data rchild

三叉链表：结点结构至少包含：数据域 、左右孩子指针域 、双亲指针 parent lchild data rchild

四、遍历二叉树和线索二叉树

1、遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 基本操作是访问结点

先(根)序的遍历算法：若二叉树为空树，则空操作；否则， ⑴访问根结点；⑵先序遍历左子树；⑶

先序遍历右子树。

中(根)序的遍历算法：若二叉树为空树，则空操作；否则，⑴中序遍历左子树；⑵访问根结点；⑶中序遍历右子树。

后(根)序的遍历算法：若二叉树为空树，则空操作；否则，⑴后序遍历左子树；⑵后序遍历右子树；⑶访问根结点。

2、建立二叉树的存储结构：

基本要点： 以―遍历‖为基本出发点；不同的遍历方法相应地有不同的建立算法代码 如何由二叉树的先序和中序序列建树？？？ 3、 线索二叉树

指向该线性序列中的―前驱‖和 ―后继‖ 的指针，称作―线索‖。包含“线索”的存储结构， 称作“线索链表”。与其相应的二叉树，称作“线索二叉树” 遍历二叉树的结果是，求得结点的一个线性序列。

线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索，而前驱或者后续的信息只有在遍历时才能得到，因而线索化的过程即为在遍历的过程中修改空指针的过程。 四、树和森林 1、树的存储结构

①双亲表示法：用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。其中根节点的值为-1

②孩子链表表示法：树结点表和 孩子结点表为了快速查找每个结点的孩子结点

③树的二叉链表 (孩子-兄弟)存储表示法：又称二叉树表示法，即以二叉链表作树的存储结构。链表

中结点的两个链域分别指向结点的第一个孩子结点和下一个兄弟结点。左边孩子右边兄弟 与孩子－兄弟链表对应的二叉树：转化后，二叉树的右子树必为空！ 2、森林与二叉树的转换

给定一棵树，可以找到惟一的一棵二叉树与之对应。——用二叉链表作为存储结构（依据） 把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，即作为二叉树的右子树，则同样可以导出森林和二叉树的对应关系。

注意：和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。 3、树和森林的遍历

两种遍历树的方法：

①先根(次序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。 ②后根(次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。 森林的遍历：

森林由三部分构成：森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树构成的森林。 遍历森林：

先序遍历：若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。

中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。 五、哈夫曼树及其应用 1、最优二叉树(哈夫曼树)

结点的路径长度：从根结点到该结点的路径上分支的数目。 树的路径长度：树中每个结点的路径长度之和。

树的带权路径长度：树中所有叶子结点的带权路径长度之和 WPL(T) = ∑wklk (对所有叶子结点)

在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为―最优树‖。

2、 如何构造最优树？(赫夫曼算法) 以二叉树为例：

⑴根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合F = {T1, T2, … , Tn}，其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；

⑵在 F 中选取其根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； ⑶从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. 某二叉树的先序遍历结点访问顺序是abdgcefh，中序遍历的访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。 2. P41：6.23

P41：6.23，然后将该树转化为对应的二叉树。 6.26

第七章 图

本章小结

 图是一种复杂的非线性结构。

 图的存储表示方法：邻接矩阵 邻接表 十字链表——有向图 邻接多重表——无向图  图的遍历：深度优先、广度优先

 图的遍历的应用：最小生成树、拓扑排序及关键路径、最短路径等问题各种算法思想！ 一、图的定义和基本术语 1、图的定义

图形结构：较线性表和树更为复杂的数据结构。结点之间的关系是任意的，图中任意两个数据元素都可能相关。

图的结构定义：图：是由一个顶点集 V 和一个顶点间的关系集合组成的数据结构。Graph = (V , VR)

其中，V = { x | x  某个数据对象}，是顶点的有穷非空集合；

2、顶点之间关系的有穷集合，也叫做边(edge)或弧(Arc)集合。“弧”是有方向的， 3、由顶点集和弧集构成的图为有向图。由顶点集和边集构成的图称作无向图 基本术语

①有(无)向网：弧(边)上带权的图

②假设图中有n个顶点，e条边，则含有 e=n(n-1)/2条边的无向图称作完全图；含有 e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数 e对有向图来说，顶点的出度: 以顶点v为弧尾的弧的数目； 顶点的入度: 以顶点v为弧头的弧的数目。

顶点的度(TD)=出度(OD)+入度(ID)

④ 若图G中任意两个顶点之间都有路径相通，则称此图为连通图； 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。

对有向图来说，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各

个强连通子图称作它的强连通分量。

假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。

比较：连通分量和生成树！连通分量：非连通图的极大连通子图 而生成树：连通图的极小连通子图

二、图的存储结构 对图中所有顶点使用一个一维数组来存放 1、图的数组(邻接矩阵)存储表示

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。

借助于邻接矩阵容易求得顶点的度：①在无向图中,统计第i行(列)1的个数可得顶点i的度。②在有向图中统计第i行1的个数可得顶点i的出度;统计第j列1的个数可得顶点j的入度。 2、图的邻接表存储表示

单链表中每个结点由三个域组成 邻接点域(adjvex):指示与顶点vi邻接的点在图中的位置；链域(nextarc):指示下一条边或弧的结点；数据域(info):存储和边或弧相关的信息，如权值等。 3、有向图的十字链表存储表示

将有向图的邻接表和逆邻接表结合起来的一种链表 从横向上看是邻接表，从纵向上看是逆邻接表。

4、无向图的邻接多重表存储表示 三、图的遍历

从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 1、深度优先搜索

连通图的深度优先搜索遍历：深度优先搜索遍历连通图的过程类似于树的先根遍历 非连通图的深度优先搜索遍历

深度优先遍历图的实质：对每个顶点查找其邻接点的过程！ 2、广度优先搜索

广度优先遍历图的实质：通过边或弧找邻接点的过程！ 四、图的连通性问题

1、无向图的连通分量和生成树

生成树的特点：n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边(但有n-1条边的图不一定是生成树)。生成树中任意两个顶点间的路径是唯一的。注：边数>n-1时，则形成环；边数构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使―权值之和‖为最小。 1、普里姆算法： 基本思想：

第一步：取图中任意一个顶点 v 作为生成树的根；

第二步：往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定

存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小； 第三步：继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。 构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。

2、 克鲁斯卡尔算法：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每

一条边的权值尽可能地小。基本思想： 第一步：构造一个只含 n 个顶点的子图 SG；

第二步：从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边； 第三步：如此重复，直至加上 n-1 条边为止 比较两种算法：

 普里姆算法：O(n2)、适用于稠密图  克鲁斯卡尔算法：O(eloge)、适用于稀疏图

六、有向无环图及其应用

定义： 一个无环的有向图称作有向无环图

1、拓扑排序 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。

①用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV-网。在AOV-网中不应该出现有向环。对给定的AOV-网需首先判断网中是否有环。

②如何进行拓扑排序？

 从有向图中选取一个没有前驱的顶点，并输出之；  从有向图中删去此顶点以及所有以它为尾的弧；

 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

③在算法中需要用定量的描述替代定性的概念：

没有前驱的顶点  入度为零的顶点；删除顶点及以它为尾的弧  弧头顶点的入度减1。 ④为避免每次都要搜索入度为零的顶点，在算法中设置一个―栈‖，以保存―入度为零‖的顶点 2、关键路径

“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。 3、最短路径

从某顶点出发，沿图的弧到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。

注意：和关键路径区别！

第八章 查找

本章小结

 查找表是由同一类型的数据元素(或记录)构成的集合。  对查找表经常进行的操作：查询 检索 插入 删去  静态查找表：

顺序表

有序表：等概率：折半查找——判定树 不等概率：静态树表的查找——次优二叉查找树  动态查找表：

二叉排序树和平衡二叉树 B-树 哈希表

查找的方法取决于查找表的结构 一、静态查找

1、顺序表的查找 以顺序表表示静态查找表, 称为顺序查找表。 ―哨兵‖的作用：免去查找过程中每一步都要检测整个表是否查找完毕。 分析顺序查找的时间性能：

11nn1PASL(ni1)iss在等概率查找的情况下 n ，顺序表查找的平均查找长度为：

ni12当查找不成功的情况不能忽视时，且等概率情况下 n n =3(n+1)/4

ASLssPs(ni1)Pus(n1)i1i12、有序表的查找

 ⑴折半查找 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 注意：折半查找只适用于有序表，且限于顺序存储结构！ 静态树表的查找

 ⑵在不等概率查找的情况下，折半查找不是有序表最好的查找方法。 次优二叉树的构造方法 请看PPT第九章幻灯片20 3、动态查找表

特点：表结构本身在查找过程中动态生成。

二叉排序(查找)树：或者是一棵空树；或者是具有如下特性的二叉树，

 若它的左子树不空，则左子树上所有结点的值均小于根结点的值；  若它的右子树不空，则右子树上所有结点的值均大于根结点的值；  它的左、右子树也都分别是二叉排序树。

如何构造二叉排序树是重点 平衡二叉树(又称AVL树)1

 AVL树的平均查找长度和logn是同数量级的！

B-树 定义：是一种平衡的多路查找树。 一棵m阶(结点的最大分支数)的B-树上：

多叉树的特性：非终端结点结构为：(n, A0 ,K1 ,A1 ,K2 , A2 ,K3 , A3 ,…,Kn , An ) 每个非终端结点可能含有：

 至多n个关键字Ki，n ≤ m-1；

 至少含有m/2-1个关键字Ki，即m/2-1≤n;  n+1个指向子树的指针Ai(0≤i≤n);

查找树的特性：非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < … < Kn;且 Ai-1 所

树中每个结点的左、右子树深度之差(称为平衡因子BF)的绝对值不大于

指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于Ki;

平衡树的特性：树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少含有两棵子树(至少有一个关键字);其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;

课堂练习

1. 有一个长度为12的有序表R[0..11]，按折半查找法对表进行查找，在表中各元素等概率情况下查找成功所需的平均比较次数为 。

2. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99}，当采用折半查找法查找关键字为82的元素时， 4 次比较后查找成功。 构造判定树如下：

3. 顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次；若查找不成功，则比较关键字的次数为 n+1 次。

4. 如图所示的二叉排序树，其成功的平均查找长度是 ；不成功的平均查找长度是 。 5. 一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有 个结点。 由于每个非叶子结点的平衡因子均为0，也即每个非终端结点都有左子树和右子树 且高度相等；因此，这样的AVL树即为满二叉树，而高度为h的满二叉树的结点数 为2h-1。则本题答案为2k-1。

6.高度为5(除叶子层之外)的三阶B-树至少有 个结点。

由m阶B-树性质可知：根结点至少有两颗子树、根结点之外的所有非叶子 结点至少有m/2 棵子树；则三阶B-树的形状至少类似于一棵满二叉树， 也即高度为5的三阶B-树至少有25-1=31个结点。本题答案为31。 二、哈希表 这个是重点

查找的过程为：给定值依次和关键字集合中各个关键字进行比较； 查找的效率取决于和给定值进行比较的关键字个数

建立关键字与记录在表中的存储位置之间的函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数f(key)为哈希函数。 关键要素：哈希函数H(key) 处理冲突的方法

假设哈希表的地址集为0至(n-1)：冲突是指由关键字得到的哈希地址为j的位置上已存有记录。―处理冲突‖就是为该关键字的记录找到另一个―空‖的哈希地址。

 开放定址法：为产生冲突的地址 H(key) 求得一个地址序列H0, H1, H2, …, Hs 1≤ s≤

m-1

其中：H0 = H(key) Hi = ( H(key) + di ) MOD m， i=1, 2, …, s

 链地址法：将所有哈希地址相同的记录都链接在同一链表中。 排序中的基本操作：比较关键字大小 和 移动记录 不同的具体实现方法导致不同的算法描述：

直接插入排序(基于顺序查找) 折半插入排序(基于折半查找) 表插入排序(基于链表存储) 希尔排序(基于逐趟缩小增量) 1、直接插入排序

 利用“顺序查找”实现―在R[1..i-1]中查找R[i]的插入位置‖。  算法的实现要点：从R[i-1]起向前进行顺序查找，监视哨设置在R[0] n个元素需进行n-1趟排序。

最好情况: 关键字在排序前已递增有序。 n―比较‖的次数： 1  n  1 ―移动‖的次数：0

i2最坏情况: 关键字在排序前为递减有序。

(n2)(n1)2in2(n4)(n1)(i1) ―移动‖的次数： 2i2 ―比较‖的次数：

(i)n 直接插入排序是一种稳定的排序方法 2、折半插入排序

因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。 3、表插入排序

 利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将

每个记录都调整到它们所应该在的位置上。

4、希尔排序又称缩小增量排序( 希尔排序是一种不稳定的排序方法

基本思想：对待排记录序列先作―宏观‖调整，再作―微观‖调整。所谓―宏观‖调整，指的是，―跳跃式‖的插入排序。

具体做法：将记录序列分成若干子序列，分别对每个子序列进行插入排序。 5、交换排序 起泡排序

 基本思想：

 注意：起泡排序的结束条件为，最后一趟没有进行―交换记录‖；一般情况下，每经过一趟―起泡‖，―i 减1‖，但并不是每趟都如此。

时间性能分析：

最好的情况(关键字在记录序列中顺序有序)：只需进行一趟起泡。  ―比较‖的次数：n-1  ―移动‖的次数：0

 最坏的情况(关键字在记录序列中逆序有序)：需进行n-1趟起泡。 2 ―比较‖的次数： (i1)inn(n1)2

 1 ―移动‖的次数： 3 n ( n ) (每次移动记录3次)

3(i1)in22

 起泡排序方法是稳定的。 快速排序

一趟快速排序(一次划分)：目标：找一个记录，以它的关键字作为―枢轴‖，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后 快速排序是不稳定的排序方法。 6、选择排序

基本原理：将待排序的记录分为已排序(初始为空)和未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。 简单选择排序和堆排序 堆排序：堆排序只需要一个记录大小的辅助空间。

堆排序分为两个步骤：根据初始输入，形成初始堆。——建堆通过一系列的记录交换和重新调整进行排序。——筛选

如何―筛选‖？―筛选‖指的是，对一棵左/右子树均为堆的完全二叉树，―调整‖根结点使整个二叉树也成为一个堆。

如何―建堆‖？建堆是一个从下往上进行―筛选‖的过程。 从最后一个非终端结点，即第n/2个元素开始―筛选‖！

堆排序的时间复杂度分析：对深度为 k 的堆，―筛选‖所需进行的关键字比较的次数至多为2(k-1)； 对 n 个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多 4n； 堆排序的时间复杂度为O(nlogn)。空间复杂性为 O(1) 堆排序是不稳定的排序方法 归并排序

归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列合并为一个有序序列。 各种排序方法的综合比较 时间性能：平均的时间性能：

时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序 时间复杂度为 O(n): 基数排序

基于―关键字间的比较‖进行排序的方法可以按排序过程所依据的不同原则分为： 插入排序 交换排序 选择排序 归并排序 基数排序