静态表的查找操作实验

《静态表的查找操作实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Windows环境下的TurboC2.0以上或VC++五、知识准备前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。六、验证性实验1．实验要求编程实现如下功能：（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。（3）主程序

3、中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。2.实验相关原理：查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。静态查找表采用顺序存储结构的数据描述为：#defineMAXSIZE100/*顺序查找表的最大长度*/typedefintkeytype;typedefstruct{keytypekey;word教育资料..}redtype;typedefstruct{redtypeelem[MAXSIZE];intlength;}Sstable;【核心算法提示】查找

4、操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。（1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序

5、设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。（2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。【核心算法描述】intsxsearch(SstableST,keytypekey)/*在顺序查找表ST中

6、，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0*/{ST.elem[0].key=key;/*在表头设置监视哨*/for(i=ST.length;ST.elem[i].key!=key;--i);/*从后往前顺序查找*/returni;}intbinsearch(SstableST,keytypekey)/*在按关键字从小到大的有序顺序表ST中，用二分查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0*/{low=1;

7、high=ST.length;/*置查找区间的初值*/while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;/*找到匹配记录*/elseif(key

8、tkeytype;typedefstruct{keytypekey;}redtype;typedefstruct{redtypeelem[MAXSIZE];intlength;}Sstable;intsxsearch(SstableST,keytypeKey)/*顺序查找函数*/{inti;ST.elem[0].key=Key;for(i=ST.length;ST.ele