实验十二 静态表的查找
一、实验目的
1. 掌握顺序查找的算法实现。
2. 掌握二分查找操作的算法实现及实现该查找的前提。
3. 理解并掌握哈希查找的算法实现过程。
二、实验内容
建立顺序查找表,并在此查找表上分别实现顺序查找和二分查找操作;建立哈希表,并在此表上实现哈希查找。
难度A:根据输入的查找表的长度n和n个关键字值,分别建立顺序查找表,分别进行顺序查找和二分查找;个人完成,评分最高至70分。( 具体数据值请参考课后P362页实验题9的1和2两题)
难度B:根据输入的查找表的长度n和n个关键字值,构建哈希表,并实现哈希查找;个人完成,评分最高至90分。(具体数据值参考课后P362页实验题5)
难度C:在主程序中要求设计一个菜单,允许用户通过菜单多次选择执行哪一种查找操作;个人完成,评分最高至100分。
- 实验步骤
查找操作是根据给定的某个值,在查找表中确定一个其关键字等于给定值得数据元素
或记录的过程。若查找表中存在这样一个记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在查找表中的位置;若在查找表中不再这样的记录,则称“查找不成功”。
- 顺序查找基本步骤:从表中最后一个记录开始,逆序扫描查找表,一次将扫描到的结点关键字值与给定值key比较,若当前扫描到的结点关键字值与key相等,则查找成功;若扫描到第一个记录,仍未找到关键字等于key的记录,则查找失败;监视哨可设置在表头,也可设置在表尾。
- 二分查找也叫折半查找,这种查找要求查找表必须是有序顺序表;在查找操作的基本步骤:首先取出表中的中间元素,若其关键字值等于给定key,则查找成功,操作结束;否则以中间元素为分界点,将查找表分为两个子表,并判断所查的key值所在的子表前部分,还是后部分,再重复上述步骤直到找到关键字值为key的元素或子表长度为0。
- 哈希表查找:哈希表存储的基本思路是:设要存储的对象个数为n,设置一个长度为m的连续内存空间,以线性表中每个对象的关键字k为自变量,通过一个称为哈希函数把k映射为内存单元的地址。其查找过程与建表过程相似,假设给定的值为k,根据建表时设定的哈嘻哈书计算出哈希地址,若表中改地址单元不为空且该地址的关键字不等于k,则按建表时设定的处理冲突的方法找下一个地址,如此反复下去,直到某个单元地址为空或关键字比较相等为止。
#define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; }redtype; typedef struct { redtype elem[MAXSIZE]; int length; }Sstable; int sxsearch(Sstable ST,keytype Key)/*顺序查找函数*/ { int i; ST.elem[0].key=Key; for(i=ST.length;ST.elem[i].key!=Key;--i); return i; } int binsearch(Sstable ST,keytype Key)/*二分法查找函数*/ { int low,mid,high; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if (Key==ST.elem[mid].key) return mid; else if (Key<ST.elem[mid].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---Sxserach\n"); printf(" 2---Binserach\n"); printf(" 3---Exit\n"); 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;i++) scanf("%d",&ST.elem[i].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("please input n data(sort):\n");/*请求输入n个关键字值(必须升序排列)*/ for(i=1;i<=ST.length;i++) scanf("%d",&ST.elem[i].key); printf("please input key:");/*请求输入待查找的记录关键字值*/ scanf("%d",&key); pos=binsearch(ST,key);/*调用二分法查找函数*/ break; case 3: return; default: printf("choose error\n"); } if(pos==0) printf("\nthe data is not found.\n"); /*若找不到,提示信息*/ else printf("\nthe data is at position %d\n",pos);} /*若找到,输出位置*/ }
C:\Users\Administrator\Documents\未命名1.cpp In function 'int main()':
34 30 C:\Users\Administrator\Documents\未命名1.cpp [Error] 'printf' was not declared in this scope
38 15 C:\Users\Administrator\Documents\未命名1.cpp [Error] 'scanf' was not declared in this scope
60 10 C:\Users\Administrator\Documents\未命名1.cpp [Error] return-statement with no value, in function returning 'int' [-fpermissive]