查找表
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;//查找表中关键字的类型
typedef struct{
KeyType key;
}ElemType;
//静态表查找
typedef struct{
ElemType *elem;
int length;
}SSTable;
//创建静态链表
int Creat(SSTable *ST)
{
int i,n;
printf("\n 请输入表长：");
scanf("%d",&n);
ST->elem=(ElemType*)malloc(sizeof(ElemType)*(n+1) );
if(!ST->elem )return 0;
printf("请输入%d个数据",n);
for(i=1;i<=n;i++)
scanf("%d",&(ST->elem[i].key ));
ST->length=n;
return 1;
}
//实现顺序查找，折半查找
int Search(SSTable ST,KeyType key,int *time){
int i;
ST.elem[0].key =key;//哨兵
*time=1;
for(i=ST.length;ST.elem[i].key != key ;i--)//利用循环完成查找
++(*time);
return i ;
}
int Search_Bin(SSTable ST,KeyType key,int *time)//折半查找
{
int low,high,mid;
low=1; high=ST.length ;
*time=0;
while(low<=high)
{
mid=(low+high)/2 ;
++(*time);
if(key==ST.elem [mid].key )return mid;
else if(key>ST.elem[mid].key) low=mid+1 ;//到右子表中进行查找
else high=mid-1 ;//到左子表中进行查找
}
return 0;
}
void main()
{
int i, n,time, loc;
KeyType key;
SSTable ST;
for(i=1;i<=4;i++)
{
printf("\n\n\t******输入下列序号，选用查询算法*******");
printf("\n\n\t 1.顺序查找 2.折半查找");
printf("\n\n 本次查寻为第%d次查询，请按上面的提示输入对应序号",i);
scanf("%d",&n);
switch(n)
{
case 1:
Creat(&ST);
printf("\n 请输入一个要查找元素的关键字");
scanf("%d",&key);
if(loc=Search(ST,key,&time))
printf("\n 顺序查找成功，共比较了%d次，要找的数据%d在第%d个数的位置上",time,key,loc);
else printf("\n 顺序查找失败");
break;
case 2:
Creat(&ST);
printf("\n 请输入一个要查找元素的关键字");
scanf("%d",&key);
if(loc=Search_Bin(ST,key,&time))
printf("\n 折半查找成功，共比较了%d次，要找的数据%d在第%d个数的位置上",time,key,loc);
else printf("\n 折半查找失败");
}}
printf("\n\n 查找结束 \n\n");
system("pause");
}
