实验七：查找算法及其应用

陕西科技大学实验报告 第页班级物联网121学号201206100128姓名张奇实验组别实验日期2014年6月13日室温报告日期2014年6月13日成绩报告内容:(目的和要求、原理、步骤、数据、计算、小结等)实验名称:查找算法及其应用一、实验目的1、掌握查找折半查找、顺序查算法的概念。2、熟练运用C语言实现折半查找、顺序查算法的基本操作。3、在掌握查找算法基本操作的基础上，能够用查找算法解决简单问题。二、实验环境MicrosoftVisualC++6.0三、实验要求编写程序测试这折半查找、顺序查算法。四、实验原理1、折半查找又称二分查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。算法要求必须采用顺序存储结构以及必须按关键字大小有序排列。2、顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。五、实验方案具体参照下页流程图。附页六、实验代码#include"stdio.h"typedefintKeyType; //定义关键字类型typedefstruct{ //定义数据元素类型KeyTypekey;}DataType;#defineLISTSIZE100 //定义静态查找表类型typedefstruct{DataTypeitems[LISTSIZE];intlength;}SqList;/*顺序查找算法*/intSeqSearch(SqListL,DataTypeX) //L为静态查找表,X为待查找元素{ inti=L.length; L.items[i].key=X.key; //设置监视哨 while(L.items[i].key!=X.key)i--; returni;}/*折半查找算法*/intBinarySearch(SqListL,DataTypeX) //L为静态查找表,X为待查找元素{ intlow=0,upper=L.length-1,mid; while(low<=upper) { mid=(low+upper)/2; if(L.items[mid].key==X.key)returnmid; //查找成功 if(L.items[mid].key<X.key)low=mid+1; //在后半子区间查找 elseupper=mid-1; //在前半子区间查找 } return-1; //查找失败}intmain(){ inti,pos; SqListl; DataTypex; printf("\n请输入顺序表的长度:"); scanf("%d",&l.length); printf("\n请输入顺序表中的元素:\n"); for(i=0;i<l.length;i++) scanf("%d",&l.items[i].key); printf("\n请输入要查找的数:"); scanf("%d",&x.key); pos=SeqSearch(l,x); printf("\n该数据在顺序表中的位置为:%d\n\n",pos-1); return0;}七、实验结果八、实验小结本次实验掌握查了找折半查找、顺序查算法的概念，运用C语言实现