静态表的查找操作实验

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

2、上或VC+ 五、知识准备前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。2. 实验相关原理：查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。静态查找表采用顺序

3、存储结构的数据描述为：#define MAXSIZE 100 /*顺序查找表的最大长度*/typedef int keytype;typedef structkeytype key;redtype;typedef struct redtype elemMAXSIZE; int length;Sstable;【核心算法提示】查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素 或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针

4、”。（1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。（2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分

5、，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。【核心算法描述】int sxsearch(Sstable ST, keytype key)/*在顺序查找表ST中，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */ ST.elem0.key=key; /*在表头设置监视哨*/for(i=ST.length;ST.elemi.key!=key;-i); /*从后往前顺序查找*/return i;int binsearch(Sstable ST,keytype key)/*在按关键字从小到大的有序顺序表ST中，用二分查找的方法查找其

6、关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */ 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=mid-1;/*继续对左半部分进行二分查找*/ else low=mid+1；/*继续对右半部分进行二分查找*/return 0; /*找不到匹配记录*/3源程序代码参考#define MAXSIZE 100

7、typedef int keytype;typedef struct keytype key; redtype;typedef struct redtype elemMAXSIZE; int length; Sstable;int sxsearch(Sstable ST,keytype Key)/*顺序查找函数*/ 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;

8、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=mid-1; else low=mid+1; return 0; main()/*主函数*/Sstable ST; int i,pos,x,key; pos=0; while(1) printf("n 1-Sxserachn"); printf(" 2-Binserachn"); printf

9、(" 3-Exitn"); printf("please input choose(1-3):"); scanf("%d",&x); switch(x) case 1: printf("please input table length n:");/*请求输入顺序表表长*/ scanf("%d",&ST.length); printf("please input n data:n");/*请求输入n个关键字值*/ for(i=1;i<=ST.length

10、;i+) scanf("%d",&ST.elemi.key); printf("please input key:");/*请求输入待查找的记录关键字值*/ scanf("%d",&key); pos=sxsearch(ST,key); /*调用顺序查找函数*/ break; case 2: printf("please input table length n:");/*请求输入顺序表表长*/ scanf("%d",&ST.length); printf("p

11、lease input n data(sort):n");/*请求输入n个关键字值（必须升序排列）*/ for(i=1;i<=ST.length;i+) scanf("%d",&ST.elemi.key); printf("please input key:");/*请求输入待查找的记录关键字值*/ scanf("%d",&key); pos=binsearch(ST,key);/*调用二分法查找函数*/ break; case 3: return; default: printf("choo

12、se errorn"); if(pos=0) printf("nthe data is not found.n"); /*若找不到，提示信息*/ else printf("nthe data is at position %dn",pos); /*若找到，输出位置*/4运行结果参考如图6-1所示 图6-1 验证性实验运行结果七、设计性实验1实验要求编程实现如下功能：（1）建立索引查找表（2）利用索引查找确定给定记录在索引查找表中的块号和在块中的位置。2核心算法分析 索引查找表有索引表和块表两部分所构成，其中索引表存储的是各块记录中的最大关键字值

13、和各块的起始存储地址，用顺序存储结构，各块的起始存储地址的初始值置为空指针；而块表中存储的是查找表中的所有记录并且按块有序，用链式存储或顺序存储结构，在此用链式存储结构。则索引查找表的存储结构图如6-2所示： 块链头指针最大关键字大工业大工业 12 23 47 3ST361294152314211331453747ST. LengthST. rr0 r1 r2 r3图6-2 索引查找表的存储结构示意图 将如图6-2所示的存储结构描述为： #define MAXSIZE 100typedef int keytype;typedef struct bnode /*块链中的结点类型*/ keytyp

14、e key; /*存储块中记录的关键字值*/ struct bnode *next; /*指向块链中下一记录结点的指针*/ Bnode;typedef struct snode /*索引表中元素的类型*/ keytype Maxkey; /*存储各块记录中的最大关键字值*/ Bnode *head; /*块链的头指针*/Snode;typedef struct /*索引查找表的结构类型*/ Snode rMAXSIZE; /*索引顺序表*/ int length; /*索引顺序表中存储数据的个数*/ Stable;由于在索引查找表中，索引表是按关键字从小到大排列的有序顺序表，块链是一个无序链表

15、，所有索引表的查找过程可归纳为：（1）在索引表中用二分查找确定待查找的记录所在的块号；（2）沿着块链指针用顺序查找的方法确定待查找的记录在块链中的存储位置。如果查找成功，则输出待查找记录在索引表中的块号和在块链中的存储地址；如果查找失败，则输出“没有找到”的信息。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=mid-1; else low=mid+1; return high+1; Blink findrec(Stable ST,keytype key) /