#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);} /*若找到，输出位置*/
}
一、实验目的
1. 掌握顺序查找的算法实现。
2. 掌握二分查找操作的算法实现及实现该查找的前提。
3. 理解并掌握哈希查找的算法实现过程。
二、实验内容
建立顺序查找表，并在此查找表上分别实现顺序查找和二分查找操作；建立哈希表，并在此表上实现哈希查找。
难度A：根据输入的查找表的长度n和n个关键字值，分别建立顺序查找表，分别进行顺序查找和二分查找；
难度B：根据输入的查找表的长度n和n个关键字值，构建哈希表，并实现哈希查找；
难度C：在主程序中要求设计一个菜单，允许用户通过菜单多次选择执行哪一种查找操作；
