实验十二 静态表的查找
一、实验目的
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]
