静态表的查找操作实验

1、实验 B06: 静态表得查找操作实验、实验名称与性质所属课程数据结构实验名称静态表得查找操作实验学时2实验性质验证 综合 设计必做 /选做必做 选做二、实验目得1. 掌握顺序查找操作得算法实现。2. 掌握二分查找操作得算法实现及实现该查找得前提。3. 掌握索引查找操作得算法实现。三、实验内容1. 建立顺序查找表 ,并在此查找表上实现顺序查找操作 （验证性内容 ）。2. 建立有序顺序查找表 ,并在此查找表上实现二分查找操作 （验证性内容 ）。3. 建立索引查找表 ,并在此查找表上实现索引查找操作 （设计性内容 ）。四、实验得软硬件环境要求硬件环境要求 :PC 机（单机 ）使用得软件名称、版本号以

2、及模块 :Windows 环境下得 TurboC2 、 0 以上或 VC+五、知识准备 前期要求掌握查找得含义与顺序查找、二分查找及索引查找操作得方法。1.实验要求编程实现如下功能 :（1） 根据输入得查找表得表长序查找方法查找给定关键值得记录（2） 根据输入得查找表得表长六、验证性实验n与n个关键字值 ,建立顺序查找表 ,并在此查找表中用顺 , 最后输出查找结果。n与 n个按升排列得关键字值 ,建立有序顺序查找表 ,并在 此查找表中用二分查找方法查找给定关键值得记录 , 最后输出查找结果。（3） 主程序中要求设计一个菜单 , 允许用户通过菜单来多次选择执行哪一种查找操作。2、 实验相关原理

3、: 查找表分别静态查找表与动态查找表两种,其中只能做引用操作得查找表称为静态查找表。静态查找表采用顺序存储结构得数据描述为 : #define MAXSIZE 100 /* 顺序查找表得最大长度 */ typedef int keytype;typedef structkeytype key;redtype;typedef structredtype elemMAXSIZE;int length;Sstable;【核心算法提示】 查找操作就是根据给定得某个值 , 在查找表中确定一个其关键字等于给定值得数据元素 或记录得过程。若查找表中存在这样一个记录 , 则称“查找成功”。查找结果给出整个记录

4、 得信息 ,或指示该记录在查找表中得位置 ; 若在查找表中不存在这样得记录 ,则称“查找不成 功”。查找结果给出“空记录”或“空指针”。(1) 顺序查找操作得基本步骤 :从表中最后一个记录开始 , 逆序扫描查找表 ,依次将扫描 到得结点关键字值与给定值 key进行比较 ,若当前扫描到得结点关键字值与 key相等 ,则查找 成功;若扫描到第一个记录 ,仍未找到关键字值等于 key 得记录,则查找失败。在程序设计中 为了减少执行得循环次数使用了监视哨。监视哨可设置在表头 , 也可设置在表尾。在此设置(2) 二分查找也叫折半查找 , 这种查找要求查找表必须就是有序顺序表。 其查找操作得基 本步骤:首

5、先取出表中得中间元素 ,若其关键字值等于给定值key,则查找成功 ,操作结束 ;否则以中间元素为分界点 , 将查找表分成两个子表 , 并判断所查得 key 值所在得子表就是前部 分 , 还就是后部分 , 再重复上述步骤直到找到关键字值为key 得元素或子表长度为 0。【核心算法描述】int sxsearch(Sstable ST, keytype key)/* 在顺序查找表 ST中,用顺序查找得方法查找其关键字等于 key 得数据元素。若找到 ,则函数返回该 元素在表中得位置 , 否则返回 0 */ ST 、elem0 、 key=key; /* 在表头设置监视哨 */for(i=ST 、 l

6、ength;ST 、elemi 、 key!=key;i); /*从后往前顺序查找 */return i;int binsearch(Sstable ST,keytype key)/* 在按关键字从小到大得有序顺序表 ST中,用二分查找得方法查找其关键字等于 key 得数据元素。若 找到,则函数返回该元素在表中得位置 , 否则返回 0 */ low=1;high=ST 、 length; /* 置查找区间得初值 */while(low<=high) mid=(low+high)/2;if (key=ST 、 elemmid 、key)return mid;/* 找到匹配记录 */else

7、 if (key<ST 、 elemmid 、 key)high=mid1;/* 继续对左半部分进行二分查找 */else low=mid+1;/* 继续对右半部分进行二分查找 */return 0; /* 找不到匹配记录 */3.源程序代码参考#define MAXSIZE 100typedef int keytype;typedef struct keytype key;redtype;typedef struct redtype elemMAXSIZE;int length;Sstable;int sxsearch(Sstable ST,keytype Key)/* 顺序查找函数

8、*/ int i;ST、elem0 、 key=Key;for(i=ST 、 length;ST 、 elemi 、key!=Key;i);return i;int binsearch(Sstable ST,keytype Key)/* 二分法查找函数 */ int low,mid,high;low=1;high=ST 、 length;while(low<=high) mid=(low+high)/2;if (Key=ST 、 elemmid 、 key)return mid;else if (Key<ST 、 elemmid 、key) high=mid1;else low=m

9、id+1;return 0;main/* 主函数 */Sstable ST;int i,pos,x,key;pos=0;while(1) printf("n 1Sxserachn");printf(" 2Binserachn");printf(" 3Exitn");printf("please input choose(13):");scanf("%d",&x);switch(x) case 1:printf("please input table length n:"

10、;);/* 请求输入顺序表表长 */ scanf("%d",&ST 、 length);printf("please input n data:n");/* 请求输入 n 个关键字值 */ for(i=1;i<=ST 、 length;i+) scanf("%d",&ST 、 elemi 、 key);printf("please input key:");/* 请求输入待查找得记录关键字值 */ scanf("%d",&key);pos=sxsearch(ST,k

11、ey); /* 调用顺序查找函数 */ break;case 2:printf("please input table length n:");/* 请求输入顺序表表长 */ scanf("%d",&ST 、 length);printf("please input n data(sort):n");/* 请求输入 n 个关键字值 (必须升序排列 )*/ for(i=1;i<=ST 、 length;i+)scanf("%d",&ST 、elemi 、 key);printf("pl

12、ease input key:");/* 请求输入待查找得记录关键字值 */ scanf("%d",&key);pos=binsearch(ST,key);/* 调用二分法查找函数 */ break;case 3: return;default: printf("choose errorn");if(pos=0)printf("nthe data is not found 、 n"); /* 若找不到 ,提示信息 */elseprintf("nthe data is at position %dn"

13、;,pos); /* 若找到 ,输出位置 */ 4. 运行结果参考如图 61 所示图 61 验证性实验运行结果七、设计性实验1. 实验要求编程实现如下功能 :(1) 建立索引查找表(2) 利用索引查找确定给定记录在索引查找表中得块号与在块中得位置。2. 核心算法分析索引查找表有索引表与块表两部分所构成,其中索引表存储得就是各块记录中得最大关键字值与各块得起始存储地址 , 用顺序存储结构 ,各块得起始存储地址得初始值置为空指针 而块表中存储得就是查找表中得所有记录并且按块有序,用链式存储或顺序存储结构 ,在此用链式存储结构。则索引查找表得存储结构图如62所示 :STr0r1r2 r3ST 、 r

14、ST、 Length122347最大关键字块链头指针36153112923451437214713图 62 索引查找表得存储结构示意图将如图 62 所示得存储结构描述为 :#define MAXSIZE 100typedef int keytype;typedef struct bnode /* 块链中得结点类型 */ keytype key; /* 存储块中记录得关键字值 */struct bnode *next; /* 指向块链中下一记录结点得指针 */ Bnode;typedef struct snode/* 索引表中元素得类型 */ keytype Maxkey; /* 存储各块记录中

15、得最大关键字值 */Bnode *head; /* 块链得头指针 */Snode;typedef struct/* 索引查找表得结构类型 */ Snode rMAXSIZE; /* 索引顺序表 */int length; /* 索引顺序表中存储数据得个数 */Stable;由于在索引查找表中 ,索引表就是按关键字从小到大排列得有序顺序表,块链就是一个无序链表 ,所有索引表得查找过程可归纳为 :(1)在索引表中用二分查找确定待查找得记录所在得块号;(2)沿着块链指针用顺序查找得方法确定待查找得记录在块链中得存储位置。如果查找成功 ,则输出待查找记录在索引表中得块号与在块链中得存储地址;如果查找失

16、败 ,则输出“没有找到”得信息。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<ST 、 rmid 、Maxkey) high=mid1;elselow=mid+1;return high+1;Blink findrec(Stable ST,keytype key