《哈希表的应用实现》由会员分享,可在线阅读,更多相关《哈希表的应用实现(4页珍藏版)》请在金锄头文库上搜索。
1、试验六实现挨次和二分查找算法一、试验目的把握挨次和二分查找算法的根本思想及其实现方法。二、试验内容对给定的任意数组设其长度为n,分别用挨次和二分查找方法 在此数组中查找与给定值k相等的元素 。三、算法思想与算法描述1、挨次查找,在挨次表R0.n-1中查找关键字为k的记录,成功时 返回找到的记录位置,失败时返回-1,具体的算法如下所示:int SeqSearch(SeqList R,int n,KeyType k)int i=0; while(i=n)return -1;elseprintf(“%d“,Ri.key);return i;2、二分查找,在有序表R0.n-1中进展二分查找,成功时返回
2、记 录的位置,失败时返回-1,具体的算法如下:int BinSearch(SeqList R,int n,KeyType k)int low=0,high=n-1,mid,count=0; while(lowk) high=mid-1;elselow=mid+1;return -1;四、试验步骤与算法实现#include #define MAXL 100 typedef int KeyType;typedef char InforType10; typedef structKeyTypekey; InforTypedata;NodeType;typedef NodeType SeqListMA
3、XL;int SeqSearch(SeqList R,int n,KeyType k)int i=0; while(i=n)return -1;elseprintf(“%d“,Ri.key);return i;int BinSearch(SeqList R,int n,KeyType k)int low=0,high=n-1,mid,count=0; while(lowk) high=mid-1;elselow=mid+1;return -1;int BinSearch1(SeqList R,KeyType k, int low,int high)int mid; if(lowhigh)ret
4、urn -1;mid=(low+high)/2; if(k=Rmid.key)return mid; else if(kRmid.key)return BinSearch1(R,k,low,mid-1);elsereturn BinSearch1(R,k,mid+1,high);void main()SeqList R; int n=10; KeyType k=7;int a=1,5,3,4,2,6,7,11,9,10,i;for(i=0;in;i+) Ri.key=ai;printf(“n“); if(i=SeqSearch(R,n,k)!=-1)printf(“n元素%d的位置是%dn“,k,i);elseprintf(“n元素%d的位置不在表中n“,k);printf(“n“); if(i=BinSearch(R,n,k)!=-1)printf(“n元素%d的位置是%dn“,k,i);elseprintf(“n元素%d的位置不在表中n“,k);printf(“n“); if(i=BinSearch1(R,k,0,7)!=-1)printf(“n元素%d的位置是%dn“,k,i);elseprintf(“n元素%d的位置不在表中n“,k);printf(“n“);五、试验测试及结果程序完全正确的执行结果,如下图:六、总结与体会