printf(\ scanf(\ switch(x) { case 1:
printf(\请求输入顺序表表长*/ scanf(\
printf(\请求输入n个关键字值*/ for(i=1;i<=ST.length;i++) scanf(\
printf(\请求输入待查找的记录关键字值*/ scanf(\
pos=sxsearch(ST,key); /*调用顺序查找函数*/ break; case 2:
printf(\请求输入顺序表表长*/ scanf(\
printf(\请求输入n个关键字值（必须升序排列）*/ for(i=1;i<=ST.length;i++) scanf(\
printf(\请求输入待查找的记录关键字值*/ scanf(\
pos=binsearch(ST,key);/*调用二分法查找函数*/ break; case 3: return;
default: printf(\ } if(pos==0)
printf(\若找不到，提示信息*/ else
printf(\ at position %d\\n\若找到，输出位置*/ }
41
4．运行结果参考如图6-1所示
图6-1 验证性实验运行结果 七、设计性实验 1．实验要求
编程实现如下功能： （1）建立索引查找表
（2）利用索引查找确定给定记录在索引查找表中的块号和在块中的位置。 2．核心算法分析
索引查找表有索引表和块表两部分所构成，其中索引表存储的是各块记录中的最大关键字值和各块的起始存储地址，用顺序存储结构，各块的起始存储地址的初始值置为空指针；而块表中存储的是查找表中的所有记录并且按块有序，用链式存储或顺序存储结构，在此用链式存储结构。则索引查找表的存储结构图如6-2所示：
42
ST ST. Length 3 ST. r
r[0] r[1] r[2] r[3]
12 23 47 …… 最大关键字块链头指针
3 15 31 6 23 45 12 14 37 9 21 47 ^ 4 ^ 13 ^ 图6-2 索引查找表的存储结构示意图
将如图6-2所示的存储结构描述为： #define MAXSIZE 100
typedef int keytype;
typedef struct bnode /*块链中的结点类型*/ { keytype key; /*存储块中记录的关键字值*/
struct bnode *next; /*指向块链中下一记录结点的指针*/ } Bnode;
typedef struct snode /*索引表中元素的类型*/
{ keytype Maxkey; /*存储各块记录中的最大关键字值*/ Bnode *head; /*块链的头指针*/ }Snode;
typedef struct /*索引查找表的结构类型*/ { Snode r[MAXSIZE]; /*索引顺序表*/
int length; /*索引顺序表中存储数据的个数*/ }Stable;
由于在索引查找表中，索引表是按关键字从小到大排列的有序顺序表，块链是一个无序链表，所有索引表的查找过程可归纳为：
（1）在索引表中用二分查找确定待查找的记录所在的块号；
（2）沿着块链指针用顺序查找的方法确定待查找的记录在块链中的存储位置。
43
如果查找成功，则输出待查找记录在索引表中的块号和在块链中的存储地址；如果查找失败，则输出“没有找到”的信息。 3．核心算法描述
int findblock(Stable ST, keytype key)
/*用二分查找法在索引查找表ST的索引表中确定关键字值为key的待查找记录所在的块号,函数并返回值其块号值*/ { int low,high,mid; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if (key low=mid+1; } return high+1; } Blink findrec(Stable ST,keytype key) /*用顺序查找法在索引查找表的块链中确定关键字值为key的待查找记录的存储位置，如查找成功则函数返回其地址值，否则返回空指针*/ { Blink p; int Bno; Bno=findblock(ST,key); /*调用函数，确定待查记录所在块号*/ p=ST.r[Bno].head; /*取到待查记录所在块链的头指针*/ while (p&&p->key!=key) /*顺着链指针依次查找*/ p=p->next; return p; /*返回查找结果*/ } 44 实验B07: 二叉排序树的操作实验 一、实验名称和性质 所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 二叉排序树的操作 2 □验证 □综合 √设计 □必做 √选做 二、实验目的 1．掌握二叉排序树的含义及其在计算机中的存储实现。 2．掌握在二叉排序树上查找操作的算法实现。 3．掌握二叉排序树的插入、删除操作的算法实现。 三、实验内容 1．建立二叉排序树。 2．在二叉排序树上实现对给定值进行查找操作（验证性内容）。 3．在二叉排序树上实现插入、删除一个指定结点（设计性内容）。 4．判断一棵二叉树是否为二叉排序树（设计性内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） Windows环境下的TurboC2.0以上或VC++等。 使用的软件名称、版本号以及模块： 五、知识准备 前期要求掌握二叉排序树的含义、二叉排序树上的查找算法和二叉排序上的插入、删除操作的算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构。 （2）先输入待查找记录的关键字值key,然后在二叉排序树上查找该记录，如果在二叉排序树中存在该记录，则显示“找到”的信息，否则显示“找不到”的信息。 2. 实验相关原理： 二叉排序树的性质如下： （1） 若左子树不空，则左子树上所有结点的值均小于根结点的值。 （2） 若右子结不空，则右子树上所有结点的值均大于根结点的值。 （3） 左右子树又分别是二叉排序树。 二叉排序树的二叉链表存储结构描述为： 45