实验B06:静态表得查找操作实验一、实验名称与性质所属课程数据结构实验名称静态表得查找操作实验学时2实验性质□验证□综合√设计必做/选做√必做□选做二、实验目得1.掌握顺序查找操作得算法实现。2.掌握二分查找操作得算法实现及实现该查找得前提。3.掌握索引查找操作得算法实现。三、实验内容1.建立顺序查找表,并在此查找表上实现顺序查找操作(验证性内容)。2.建立有序顺序查找表,并在此查找表上实现二分查找操作(验证性内容)。3.建立索引查找表,并在此查找表上实现索引查找操作(设计性内容)。四、实验得软硬件环境要求硬件环境要求:PC机(单机)使用得软件名称、版本号以及模块:Windows环境下得TurboC2、0以上或VC++五、知识准备前期要求掌握查找得含义与顺序查找、二分查找及索引查找操作得方法。六、验证性实验1.实验要求编程实现如下功能:(1)根据输入得查找表得表长n与n个关键字值,建立顺序查找表,并在此查找表中用顺序查找方法查找给定关键值得记录,最后输出查找结果。(2)根据输入得查找表得表长n与n个按升排列得关键字值,建立有序顺序查找表,并在此查找表中用二分查找方法查找给定关键值得记录,最后输出查找结果。(3)主程序中要求设计一个菜单,允许用户通过菜单来多次选择执行哪一种查找操作。2、实验相关原理:查找表分别静态查找表与动态查找表两种,其中只能做引用操作得查找表称为静态查找表。静态查找表采用顺序存储结构得数据描述为:#defineMAXSIZE100/*顺序查找表得最大长度*/typedefintkeytype;typedefstruct{keytypekey;}redtype;typedefstruct{redtypeelem[MAXSIZE];intlength;}Sstable;【核心算法提示】查找操作就是根据给定得某个值,在查找表中确定一个其关键字等于给定值得数据元素或记录得过程。若查找表中存在这样一个记录,则称“查找成功”。查找结果给出整个记录得信息,或指示该记录在查找表中得位置;若在查找表中不存在这样得记录,则称“查找不成功”。查找结果给出“空记录”或“空指针”。(1)顺序查找操作得基本步骤:从表中最后一个记录开始,逆序扫描查找表,依次将扫描到得结点关键字值与给定值key进行比较,若当前扫描到得结点关键字值与key相等,则查找成功;若扫描到第一个记录,仍未找到关键字值等于key得记录,则查找失败。在程序设计中为了减少执行得循环次数使用了监视哨。监视哨可设置在表头,也可设置在表尾。在此设置在表头。(2)二分查找也叫折半查找,这种查找要求查找表必须就是有序顺序表。其查找操作得基本步骤:首先取出表中得中间元素,若其关键字值等于给定值key,则查找成功,操作结束;否则以中间元素为分界点,将查找表分成两个子表,并判断所查得key值所在得子表就是前部分,还就是后部分,再重复上述步骤直到找到关键字值为key得元素或子表长度为0。【核心算法描述】intsxsearch(SstableST,keytypekey)/*在顺序查找表ST中,用顺序查找得方法查找其关键字等于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;high=ST、length;/*置查找区间得初值*/while(low<=high){mid=(low+high)/2;if(key==ST、elem[mid]、key)returnmid;/*找到匹配记录*/elseif(key<ST、elem[mid]、key)high=mid1;/*继续对左半部分进行二分查找*/elselow=mid+1;/*继续对右半部分进行二分查找*/}return0;/*找不到匹配记录*/}3.源程序代码参考#defineMAXSIZE100typedefintkeytype;typedefstruct{keytypekey;}redtype;typedefstruct{redtypeelem[MAXSIZE];intlength;}Sstable;intsxsearch(SstableST,keytypeKey)/*顺序查找函