9. 数据结构(Data Structure):是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型,如图1-3所示。
① 集合:结构中的数据元素除了“同属于一个集合”外,没有其它关系。
② 线性结构:结构中的数据元素之间存在一对一的关系。
③ 树型结构:结构中的数据元素之间存在一对多的关系。
④ 图状结构或网状结构:结构中的数据元素之间存在多对多的关系。
17. 抽象数据类型(Abstract Data Type ,简称ADT):是指一个数学模型以及定义在该模型上的一组操作。
ADT的定义仅是一组逻辑特性描述, 与其在计算机内的表示和实现无关。因此,不论ADT的内部结构如何变化,只要其数学特性不变,都不影响其外部使用。
ADT的形式化定义是三元组:ADT=(D,S,P)
其中:D是数据对象,S是D上的关系集,P是对D的基本操作集。1.2 抽象数据类型
20. 1.3.1 算法
算法(Algorithm):是对特定问题求解方法(步骤)的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。
算法具有以下五个特性
① 有穷性: 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
② 确定性:算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
③ 可行性: 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。1.3 算法分析初步
28. 定理:若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式,则A(n)=O(n m)
例5 for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x; a[i,j]=x; }
语句频度为: 1+2+3+…+n-2=(1+n-2) ×(n-2)/2
=(n-1)(n-2)/2 =n2-3n+2
∴时间复杂度为O(n2),即此算法的时间复杂度为平方阶。
一个算法时间为O(1)的算法,它的基本运算执行的次数是固定的。因此,总的时间由一个常数(即零次多项式)来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。
34. ⑴
Sum1( int n )
{ int p=1, sum=0, m ;
for (m=1; m<=n; m++)
{ p*=m ; sum+=p ; }
return (sum) ;
}⑵
Sum2( int n )
{ int sum=0, m, t ;
for (m=1; m<=n; m++)
{ p=1 ;
for (t=1; t<=m; t++) p*=t ;
sum+=p ;
}
return (sum) ;
}⑶ 递归函数
fact( int n )
{ if (n<=1) return(1) ;
else return( n*fact(n-1)) ;
}
35. 第2章 线性表 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中:
① 存在一个唯一的被称为“第一个”的数据元素;
② 存在一个唯一的被称为“最后一个”的数据元素;
③ 除第一个元素外,每个元素均有唯一一个直接前驱;
④ 除最后一个元素外,每个元素均有唯一一个直接后继。
108. 3.1 栈3.1.1 栈的基本概念1 栈的概念
栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom):是固定端,又称为表头。
空栈:当表中没有元素时称为空栈。
129. 3.2.1 数制转换 十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。
转换法则:该转换法则对应于一个简单算法原理:
n=(n div d)*d+n mod d
其中:div为整除运算,mod为求余运算
例如 (1348)10= (2504)8,其运算过程如下:
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
130. 采用静态顺序栈方式实现
void conversion(int n , int d)
/*将十进制整数N转换为d(2或8)进制数*/
{ SqStack S ; int k, *e ;
S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ; }
/* 求出所有的余数,进栈 */
while (S.top!=0) /* 栈不空时出栈,输出 */
{ pop(S, e) ;
printf(“%1d” , *e) ;
}
}
159. 6 一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ,入栈Push(S,i,x),出栈Pop(S,i,x)算法,其中i为0或1 ,用以表示栈号。
7 设Q[0,6]是一个静态顺序队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入对,请指出其元素,并说明理由。
a, b, c, d入队
a, b, c出队
i , j , k , l , m入队
d, i出队
n, o, p, q, r入队
160. 8 假设Q[0,5]是一个循环队列,初始状态为front=rear=0,请画出做完下列操作后队列的头尾指针的状态变化情况,若不能入对,请指出其元素,并说明理由。
d, e, b, g, h入队
d, e出队
i , j , k , l , m入队
b出队
n, o, p, q, r入队
169. 1 串的联结操作
Status StrConcat ( StringType s, StringType t)
/* 将串t联结到串s之后,结果仍然保存在s中 */
{ int i, j ;
if ((s.length+t.length)>MAX_STRLEN)
Return ERROR ; /* 联结后长度超出范围 */
for (i=0 ; i
170. 2 求子串操作
Status SubString (StringType s, int pos, int len, StringType *sub)
{ int k, j ;
if (pos<1||pos>s.length||len<0||len>(s.length-pos+1))
return ERROR ; /* 参数非法 */
sub->length=len-pos+1 ; /* 求得子串长度 */
for (j=0, k=pos ; k<=leng ; k++, j++)
sub->str[j]=s.str[i] ; /* 逐个字符复制求得子串 */
return OK ;
}
175. 串的块链式存储的类型定义包括:
⑴ 块结点的类型定义
#define BLOCK_SIZE 4
typedef struct Blstrtype
{ char data[BLOCK_SIZE] ;
struct Blstrtype *next;
}BNODE ;a b c e p c g @ @ ⋀ ⋯⋯head图4-1 串的块链式存储结构示意图
235. 3 十字链表 对于稀疏矩阵,当非0元素的个数和位置在操作过程中变化较大时,采用链式存储结构表示比三元组的线性表更方便。
矩阵中非0元素的结点所含的域有:行、列、值、行指针(指向同一行的下一个非0元)、列指针(指向同一列的下一个非0元)。其次,十字交叉链表还有一个头结点,结点的结构如图5-10所示。图5-10 十字链表结点结构row col value down right rn cn tn down right(a) 结点结构(b) 头结点结构
270. abcdhiejklfg(a) 完全二叉树(b) 非完全二叉树abcdefghØØØ1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l (c) 完全二叉树的顺序存储形式1 2 3 4 5 6 7 8 9 10 11a b c d e Ø h Ø Ø f g(d) 非完全二叉树的顺序存储形式图6-6 二叉树及其顺序存储形式
272. ② 三叉链表结点。除二叉链表的三个域外,再增加一个指针域,用来指向结点的父结点,如图6-7(b)所示。
typedef struct BTNode_3
{ ElemType data ;
struct BTNode_3 *Lchild , *Rchild , *parent ;
}BTNode_3 ; Lchild data RchildLchild data parent Rchild(a) 二叉链表结点(b) 三叉链表结点图6-7 链表结点结构形式
273. (2) 二叉树的链式存储形式
例有一棵一般的二叉树,如图6-8(a)所示。以二叉链表和三叉链表方式存储的结构图分别如图6-8(b) 、 6-8(c)所示。图6-8 二叉树及其链式存储结构(a) 二叉树afedcbg(c) 三叉链表 a ⋀ ⋀ b⋀ c ⋀ d⋀ e⋀ f ⋀⋀ g ⋀T(b) 二叉链表 a ⋀ b⋀ c ⋀ d⋀ e⋀ g ⋀⋀ f ⋀T
309. 0 A 0 0 B 1 0 C 0⋀ 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 ⋀(e) 中序线索树的链表结构图6-11 线索二叉树及其存储结构说明:画线索二叉树时,实线表示指针,指向其左、右孩子;虚线表示线索,指向其直接前驱或直接后继。
在线索树上进行遍历,只要先找到序列中的第一个结点,然后就可以依次找结点的直接后继结点直到后继为空为止。
339. 3 森林转换成二叉树
当一般的树转换成二叉树后,二叉树的右子树必为空。若把森林中的第二棵树(转换成二叉树后)的根结点作为第一棵树(二叉树)的根结点的兄弟结点,则可导出森林转换成二叉树的转换算法如下:
设F={T1, T2,⋯,Tn}是森林,则按以下规则可转换成一棵二叉树B=(root,LB,RB)
① 若n=0,则B是空树。
② 若n>0,则二叉树B的根是森林T1的根root(T1),B的左子树LB是B(T11,T12, ⋯,T1m) ,其中T11,T12, ⋯,T1m是T1的子树(转换后),而其右子树RB是从森林F’={T2, T3,⋯,Tn}转换而成的二叉树。
340. 转换步骤:
① 将F={T1, T2,⋯,Tn} 中的每棵树转换成二叉树。
② 按给出的森林中树的次序,从最后一棵二叉树开始,每棵二叉树作为前一棵二叉树的根结点的右子树,依次类推,则第一棵树的根结点就是转换后生成的二叉树的根结点,如图6-21所示。ACBDGMLHK(a) 森林图6-21 森林转换成二叉树的过程(b) 森林中每棵树
对应的二叉树ABCDGLKHM(c) 森林对应的二叉树ABCDGLKHM
341. 4 二叉树转换成森林
若B=(root,LB,RB)是一棵二叉树,则可以将其转换成由若干棵树构成的森林:F={T1, T2,⋯,Tn} 。
转换算法:
① 若B是空树,则F为空。
② 若B非空,则F中第一棵树T1的根root(T1)就是二叉树的根root, T1中根结点的子森林F1是由树B的左子树LB转换而成的森林;F中除T1外其余树组成的的森林F’={T2, T3,⋯,Tn} 是由B右子树RB转换得到的森林。
上述转换规则是递归的,可以写出其递归算法。以下给出具体的还原步骤。
342. ① 去连线。将二叉树B的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉,得到若干棵孤立的二叉树,每一棵就是原来森林F中的树依次对应的二叉树,如图6-22(b)所示。
② 二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树,如图6- 22(c)所示。图6-22 二叉树还原成森林的过程ACBDMGLHK(c) 还原成森林(a) 二叉树ABCDGLKHM(b) 去连线后ABCDMGLKH
350. 236736726723(a)(b)(c)图6-24 具有相同叶子结点,不同带权路径长度的二叉树2 Huffman树的构造
① 根据n个权值{w1, w2, ⋯,wn},构造成n棵二叉树的集合F={T1, T2, ⋯,Tn},其中每棵二叉树只有一个权值为wi的根结点,没有左、右子树;
351. ② 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且新的二叉树根结点权值为其左、右子树根结点的权值之和;
③ 在F中删除这两棵树,同时将新得到的树加入F中;
④ 重复②、③,直到F只含一颗树为止。
构造Huffman树时,为了规范,规定F={T1,T2, ⋯,Tn}中权值小的二叉树作为新构造的二叉树的左子树,权值大的二叉树作为新构造的二叉树的右子树;在取值相等时,深度小的二叉树作为新构造的二叉树的左子树,深度大的二叉树作为新构造的二叉树的右子树。
357. (2) Huffman树的生成
算法实现
void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m)
/* 创建一棵叶子结点数为n的Huffman树 */
{ unsigned int w ; int k , j ;
for (k=1 ; k
358. HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;
} /* 初始化向量HT */
for (k=n+1; k
359. else if (HT[j].Weight
360. (3) Huffman编码算法
根据出现频度(权值)Weight,对叶子结点的Huffman编码有两种方式:
① 从叶子结点到根逆向处理,求得每个叶子结点对应字符的Huffman编码。
② 从根结点开始遍历整棵二叉树,求得每个叶子结点对应字符的Huffman编码。
由Huffman树的生成知,n个叶子结点的树共有2n-1个结点,叶子结点存储在数组HT中的下标值为1∽n。
① 编码是叶子结点的编码,只需对数组HT[1…n]的n个权值进行编码;
② 每个字符的编码不同,但编码的最大长度是n。
361. 求编码时先设一个通用的指向字符的指针变量,求得编码后再复制。
算法实现
void Huff_coding(unsigned n , Hnode HT[] , unsigned m)
/* m应为n+1,编码的最大长度n加1 */
{ int k , sp ,fp ;
char *cd , *HC[m] ;
cd=(char *)malloc(m*sizeof(char)) ;
/* 动态分配求编码的工作空间 */
cd[n]=‘\0’ /* 编码的结束标志 */
for (k=1 ; k
364. ⑵ 一棵深度为h的满k叉树有如下性质: 第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号,问:
① 各层的结点数是多少?
② 编号为i的结点的双亲结点(若存在)的编号是多少?
③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
365. ⑶ 设有如图6-27所示的二叉树。
① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。
② 写出该二叉树的先序、中序、后序遍历序列。
⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树,然后给出该树的后序遍历序列。⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ,请画出这棵二叉树,然后给出该树的先序序列。图6-27 二叉树adebfgchkmn
366. ⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca,请画出这棵二叉树对应的中序线索树和后序线索树。
⑺ 以二叉链表为存储结构,请分别写出求二叉树的结点总数及叶子结点总数的算法。
⑻ 设图6-27所示的二叉树是森林F所对应的二叉树,请画出森林F。
⑼ 设有一棵树,如图6-28所示。
① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。
② 请给出该树的先序遍历序列和后序遍历序列。
③ 请将这棵树转换成二叉树。
367. ⑽ 设给定权值集合w={3,5,7,8,11,12} ,请构造关于w的一棵huffman树,并求其加权路径长度WPL 。
⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成, 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。
① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。
② 求出每个字符的huffman编码。adebfgmhkcn图6-28 一般的树
480. 手工实现
如图7-23是一个有向图的拓扑排序过程,其拓扑序列是: (v1,v6,v4,v3,v2,v5)
2 拓扑排序算法
算法思想
① 在AOV网中选择一个没有前驱的顶点且输出;
② 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ;
③ 重复①、②,直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。
514. printf(“最短路径长度为: %d\n”,A[j][k]) ;
}
} /* end of Floyd */
void prn_pass(int j , int k)
{ if (Path[j][k]!=-1)
{ prn_pass(j, Path[j][k]) ;
printf(“, %d” , Path[j][k]) ;
prn_pass(Path[j][k], k) ;
}
}
515. 习 题 七⑴ 分析并回答下列问题:
① 图中顶点的度之和与边数之和的关系?
② 有向图中顶点的入度之和与出度之和的关系?
③ 具有n个顶点的无向图,至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示,则该矩阵的大小是多少?
④ 具有n个顶点的有向图,至少应有多少条弧才能确保是强连通图的? 为什么?
⑵ 设一有向图G=(V,E),其中V={a,b,c,d,e} , E={, , , , , ,, , }
516. ① 请画出该有向图,并求各顶点的入度和出度。
② 分别画出有向图的正邻接链表和逆邻接链表。
⑶ 对图7-27所示的带权无向图。
① 写出相应的邻接矩阵表示。
② 写出相应的边表表示。
③ 求出各顶点的度。
⑷ 已知有向图的逆邻接链表如图7-28所示。
① 画出该有向图。
② 写出相应的邻接矩阵表示。
③ 写出从顶点a开始的深度优先和广度优先遍历序列。
④ 画出从顶点a开始的深度优先和广度优先生成树。
518. ⑸ 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一?
⑹ 对于图7-27所示的带权无向图。
① 按照Prime算法给出从顶点2开始构造最小生成树的过程。
② 按照Kruskal算法给出最小生成树的过程。
⑺ 已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,给出相应的求解步骤。
⑻ 已知带权有向图如图7-30所示,请利用Floyd算法求出每对顶点之间的最短路径及路径长度。
⑼ 一个AOV网用邻接矩阵表示,如图7-31。用拓扑排序求该AOV网的一个拓扑序列,给出相应的步骤。
519. ⑽ 拓扑排序的结果不是唯一的,请给出如图7-32所示的有向图的所有可能的拓扑序列。
⑾ 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。
⑿ 设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径,设图采用邻接链表作为存储结构。
⒀ 假设一个工程的进度计划用AOE网表示,如图7-33所示。
① 求出每个事件的最早发生时间和最晚发生时间。
② 该工程完工至少需要多少时间?
③ 求出所有关键路径和关键活动。
534. 8.3 边界标识法 边界标识法(Boundary Tag Method)是操作系统中一种常用的进行动态分配的存储管理方法。
系统将所有的空闲块链接成一个双重循环链表,分配可采用几种方法(前述) 。
系统的特点
每个内存区域的头部和底部两个边界上分别设置标识,以标识该区域为占用块或空闲块,在回收块时易于判别在物理位置上与其相邻的内存区域是否为空闲块,以便于将所有地址连续的空闲存储区合并成一个尽可能大的空闲块。
535. 8.3.1 可利用空闲表结点结构Llink tag size rlinkuplink tag spaceheadfoottypedef struct word
{ Union
{ struct word *llink;
struct word *uplink;
};
int tag;
int size;
struct word *rlink;OtherType other;
}WORD, head, foot, *Space;
#define FootLoc(p) p+p->size-1
536. 8.3.2 分配算法 分配算法比较简单,可采用前述三种方法中的任一种进行分配。设采用首次拟合法,为了使系统更有效地运行,在边界标识法中还做了两条约定:
① 选定适当常量e,设待分配空闲块、请求分配空间的大小分别为m 、 n 。
◆ 当m-n≤e时:将整个空闲块分配给用户;
◆ 当m-n>e时:则只分配请求的大小n给用户;
作用:尽量减少空闲块链表中出现小碎片(容量≤e) ,提高分配效率;减少对空闲块链表的维护工作量。为了避免修改指针,约定将高地址部分分配给用户。
537. ② 空闲块链表中的结点数可能很多,为了提高查找空闲块的速度和防止小容量结点密集,每次查找时从不同的结点开始——上次刚分配结点的后继结点开始。
Space AllocBoundTag( Space *pav, int n )
{ p = pav ;
for ( ; p &&p->sizerlink!=pav; p=p->rlink )
if ( !p || p->sizerlink ;
if ( p->size–n<=e )
570. int Block_search(RecType ST[] , Index ind[] , KeyType key , int n , int b)
/* 在分块索引表中查找关键字为key的记录 */
/*表长为n ,块数为b */
{ int i=0 , j , k ;
while ((ib) { printf("\nNot found"); return(0); }
j=ind[i].startpos ;
while ((j
574. ① 相等: 查找成功;
② 大于:待查记录在区间的前半段(区间长度为F(j-1)-1),修改上界指针: High=Mid-1,转⑴ ;
③ 小于:待查记录在区间的后半段(区间长度为F(j-2)-1),修改下界指针:Low=Mid+1,转⑴ ;
直到越界(Low>High),查找失败。
2 算法实现
在算法实现时,为了避免频繁计算Fibonacci数,可用两个变量f1和f2保存当前相邻的两个Fibonacci数,这样在以后的计算中可以依次递推计算出。
575. int fib(int n)
{ int i, f , f0=0 , f1=1 ;
if (n==0) return(0) ;
if (n==1) return(1) ;
for (i=2 ; i<=n ; i++ )
{ f=f0+f1 ; f0=f1 ; f1=f ; }
return(f) ;
}
int Fib_search(RecType ST[] , KeyType key , int n)
/* 在有序表ST中用Fibonacci方法查找关键字为key的记录 */
{ int Low=1, High, Mid, f1, f2 ;
High=n ; f1=fib(n-1) ; f2=fib(n-2) ;
while (Low<=High)
{ Mid=Low+f1-1;
603. 2 LR型平衡化旋转⑴ 失衡原因
在结点a的左孩子的右子树上进行插入,插入使结点a失去平衡。a插入前的平衡因子是1,插入后a的平衡因子是2。设b是a的左孩子,c为b的右孩子, b在插入前的平衡因子只能是0,插入后的平衡因子是-1;c在插入前的平衡因子只能是0,否则,c就是失衡结点。
⑵ 插入后结点c的平衡因子的变化分析
① 插入后c的平衡因子是1:即在c的左子树上插入。设c的左子树的深度为HcL,则右子树的深度为HcL-1;b插入后的平衡因子是-1,则b的左子树的深度为HcL,以b为根的子树的深度是HcL+2。
604. 因插入后a的平衡因子是2 ,则a的右子树的深度是HcL。
② 插入后c的平衡因子是0:c本身是插入结点。设c的左子树的深度为HcL,则右子树的深度也是HcL;因b插入后的平衡因子是-1,则b的左子树的深度为HcL,以b为根的子树的深度是HcL+2;插入后a的平衡因子是2 ,则a的右子树的深度是HcL。
③ 插入后c的平衡因子是-1:即在c的右子树上插入。设c的左子树的深度为HcL,则右子树的深度为HcL+1 ,以c为根的子树的深度是HcL+2;因b插入后的平衡因子是-1,则b的左子树的深度为HcL+1,以b为根的子树的深度是HcL+3;则a的右子树的深度是HcL+1。
608. 3 RL型平衡化旋转⑴ 失衡原因
在结点a的右孩子的左子树上进行插入,插入使结点a失去平衡,与LR型正好对称。对于结点a,插入前的平衡因子是-1,插入后a的平衡因子是-2。设b是a的右孩子,c为b的左孩子, b在插入前的平衡因子只能是0,插入后的平衡因子是1;同样,c在插入前的平衡因子只能是0,否则,c就是失衡结点。
⑵ 插入后结点c的平衡因子的变化分析
① 插入后c的平衡因子是1:在c的左子树上插入。设c的左子树的深度为HcL,则右子树的深度为HcL-1。
609. 因b插入后的平衡因子是1,则其右子树的深度为HcL,以b为根的子树的深度是HcL+2;因插入后a的平衡因子是-2 ,则a的左子树的深度是HcL。
② 插入后c的平衡因子是0:c本身是插入结点。设c的左子树的深度为HcL,则右子树的深度也是HcL;因b插入后的平衡因子是1,则b的右子树的深度为HcL,以b为根的子树的深度是HcL+2;因插入后a的平衡因子是-2 ,则a的左子树的深度是HcL。
③ 插入后c的平衡因子是-1:在c的右子树上插入。设c的左子树的深度为HcL,则右子树的深度为HcL+1 ,以c为根的子树的深度是HcL+2;因b插入后的平衡因子是1,则b的右子树的深度为HcL+1,以b为根的子树的深度是HcL+3;则a的右子树的深度是HcL+1。
610. ⑶ 平衡化旋转方法
先以b进行一次顺时针旋转,再以a进行一次逆时针旋转,如图9-9所示。即将整棵子树(以a为根)旋转为以c为根,a是c的左子树,b是c的右子树;c的右子树移到b的左子树位置,c的左子树移到a的右子树位置。图9-9 RL型平衡化旋转示意图abbRaLcL
xcR
xcbcbRaLcL
xcR
xa
611. ⑷ 旋转后各结点(a,b,c)的平衡因子分析
① 旋转前 (插入后)c的平衡因子是1:
a的左子树没有变化,深度是HcL,右子树是c旋转前的左子树,深度为HcL,则a的平衡因子是0;b的右子树没有变化,深度为HcL,左子树是c旋转前的右子树,深度为HcL-1 ,则b的平衡因子是-1; c的左、右子树分别是以a 和b为根的子树,则c的平衡因子是0 。
② 旋转前 (插入后)c的平衡因子是0:
旋转后a,b,c的平衡因子都是0 。
③ 旋转前 (插入后)c的平衡因子是-1:
旋转后a,b,c的平衡因子分别是1,0,0 。
综上所述,即整棵树旋转后是平衡的。
658. 冲突:对于不同的关键字ki、kj,若kikj,但H(ki)=H(kj)的现象叫冲突(collision) 。
同义词:具有相同函数值的两个不同的关键字,称为该哈希函数的同义词。
哈希函数通常是一种压缩映象,所以冲突不可避免,只能尽量减少;当冲突发生时,应该有处理冲突的方法。设计一个散列表应包括:
① 散列表的空间范围,即确定散列函数的值域;
② 构造合适的散列函数,使得对于所有可能的元素(记录的关键字),函数值均在散列表的地址空间范围内,且出现冲突的可能尽量小;
③ 处理冲突的方法。即当冲突出现时如何解决。
683. 习 题 九⑴ 对于一个有n个元素的线性表,若采用顺序查找方法时的平均查找长度是什么?若结点是有序的,则采用折半查找法是的平均查找长度是什么?
⑵ 设查找表采用单链表存储,请分别写出对该表进行顺序查找的静态查找和动态查找的算法。
⑶ 设二叉排序树中的关键字互不相同:则
① 最小元素无左孩子,最大元素无右孩子,此命题是否正确?
② 最大和最小元素一定是叶子结点吗?
③ 一个新结点总是插入在叶子结点上吗?
685. ⑺ 设关键字序列是(19, 14, 23, 01, 68, 84, 27, 55, 11, 34, 79),散列表长度是11,散列函数是H(key)=key MOD 11,
① 采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。
② 采用开放地址法的二次探测方法解决冲突,请构造该关键字序列的哈希表。
⑻ 试比较线性索引和树形索引的优点和缺点。
686. ⑼ 设关键字序列是(19, 24, 23, 17, 38, 04, 27, 51, 31, 34, 69),散列表长度是11,散列函数是H(key)=key MOD 11,
① 采用开放地址法的线性探测方法解决冲突,请构造该关键字序列的哈希表。
② 求出在等概率情况下,该方法的查找成功和不成功的平均查找长度ASL。
⑽ 下图是一棵3阶B_树,请画出插入关键字B,L,P,Q后的树形。GD EI MCAHJ KN O
698. 3 算法说明
算法中的R[0]开始时并不存放任何待排序的记录,引入的作用主要有两个:
① 不需要增加辅助空间: 保存当前待插入的记录R[i],R[i]会因为记录的后移而被占用;
② 保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录,起“哨兵监视”作用,避免在内循环中每次都要判断j是否越界。
742. 2 堆的性质
① 堆是一棵采用顺序存储结构的完全二叉树, k1是根结点;
② 堆的根结点是关键字序列中的最小(或最大)值,分别称为小(或大)根堆;
③ 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的;
堆中的任一子树也是堆。
利用堆顶记录的关键字值最小(或最大)的性质,从当前待排序的记录中依次选取关键字最小(或最大)的记录,就可以实现对数据记录的排序,这种排序方法称为堆排序。
743. 3 堆排序思想
① 对一组待排序的记录,按堆的定义建立堆;
② 将堆顶记录和最后一个记录交换位置,则前n-1个记录是无序的,而最后一个记录是有序的;
③ 堆顶记录被交换后,前n-1个记录不再是堆,需将前n-1个待排序记录重新组织成为一个堆,然后将堆顶记录和倒数第二个记录交换位置,即将整个序列中次小关键字值的记录调整(排除)出无序区;
④ 重复上述步骤,直到全部记录排好序为止。
结论:排序过程中,若采用小根堆,排序后得到的是非递减序列;若采用大根堆,排序后得到的是非递增序列。
744. 堆排序的关键
① 如何由一个无序序列建成一个堆?
② 如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?
4 堆的调整——筛选
⑴ 堆的调整思想
输出堆顶元素之后,以堆中最后一个元素替代之;然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;重复上述操作,直到是叶子结点或其关键字值小于等于左、右子树的关键字的值,将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”,如图10-10所示。
754. 归并的算法
void Merge(RecType R[], RecType DR[], int k, int m, int h)
{ int p, q, n ; p=n=k, q=m+1 ;
while ((p<=m)&&(q<=h))
{ if (LQ(R[p].key, R[q].key) ) /* 比较两个子序列 */
DR[n++]=R[p++] ;
else DR[n++]=R[q++] ;
}
while (p<=m) /* 将剩余子序列复制到结果序列中 */
DR[n++]=R[p++] ;
while (q<=h) DR[n++]=R[q++] ;
}
755. 2 一趟归并排序
一趟归并排序都是从前到后,依次将相邻的两个有序子序列归并为一个,且除最后一个子序列外,其余每个子序列的长度都相同。设这些子序列的长度为d,则一趟归并排序的过程是:
从j=1开始,依次将相邻的两个有序子序列R[j…j+d-1]和R[j+d…j+2d-1]进行归并;每次归并两个子序列后,j后移动2d个位置,即j=j+2d;若剩下的元素不足两个子序列时,分以下两种情况处理:
① 剩下的元素个数>d:再调用一次上述过程,将一个长度为d的子序列和不足d的子序列进行归并;
② 剩下的元素个数≤d:将剩下的元素依次复制到归并后的序列中。
756. ⑴ 一趟归并排序算法
void Merge_pass(RecType R[], RecType DR[], int d, int n)
{ int j=1 ;
while ((j+2*d-1)<=n)
{ Merge(R, DR, j, j+d-1, j+2*d-1) ;
j=j+2*d ;
} /* 子序列两两归并 */
if (j+d-1
780. 文件存储在外存上,通常是以块(I/O读写的基本单位,称为物理记录)存取。
物理记录和逻辑记录之间的关系是:
① 一个物理记录存放一个逻辑记录;
② 一个物理记录包含多个逻辑记录;
③ 多个物理记录存放一个逻辑记录。
⑶ 文件(File):大量性质相同的数据记录的集合。文件的所有记录是按某种排列顺序呈现在用户面前,这种排列顺序可以是按记录的关键字,也可以是按记录进入文件的先后等。则记录之间形成一种线性结构(逻辑上的),称为文件的逻辑结构;文件在外存上的组织方式称为文件的物理结构。基本的物理结构有:顺序结构,链接结构,索引结构 。
781. ⑷ 文件的分类
⑴ 按记录类型,可分为操作系统文件和数据库文件:
① 操作系统文件(流式文件) : 连续的字符序列(串)的集合;
② 数据库文件: 有特定结构(所有记录的结构都相同)的数据记录的集合。
⑵ 按记录长度,可分为定长记录文件和不定长记录文件:
① 定长记录文件:文件中每个记录都有固定的数据项组成,每个数据项的长度都是固定的;
② 不定长记录文件:与定长记录文件相反。
782. 2 文件的有关操作
文件是由大量记录组成的线性表,因此,对文件的操作主要是针对记录的,通常有:记录的检索、插入、删除、修改和排序,其中检索是最基本的操作。
⑴ 检索记录
根据用户的要求从文件中查找相应的记录。
① 查找下一个记录:找当前记录的下一个逻辑记录;
② 查找第k个记录:给出记录的逻辑序号,根据该序号查找相应的记录;
③ 按关键字查找:给出指定的关键字值,查找关键字值相同或满足条件的记录。对数据库文件,有以下四种按关键字查找的方式:
810. 11.3.1 外部排序方法 外部排序最基本的方法是归并。这种方法是由两个相对独立的阶段组成:
① 按内存(缓冲区)的大小,将n个记录的数据文件分成若干个长度为l的段或子文件,依次读入内存并选择有效的内部排序方法进行排序;然后将排好序的有序子文件重新写入到外存。子文件称为归并段或顺串。
② 采用归并的办法对归并段进行逐趟归并,使归并段的长度逐渐增大,直到最后合并成只有一个归并段的文件—排好序的文件。