存档:
#include <stdio.h>
#include <stdlib.h>
#define max 20
typedef int keytype;
#include "search.h"
int main()
{
sstable st;
keytype key;
int result,num;
init(st);
printf("***************************************\n");
printf("1.顺序查找\n");
printf("2.折半查找\n");
printf("3.输出表信息\n");
printf("4.退出\n");
printf("***************************************\n");
printf("请输入你的选择:\n");
scanf("%d",&num);
while()
{
switch(num)
{
case :
printf("请创建顺序查找表");
create(st);
printf("请输入顺序查找的关键字:");
scanf("%d",&key);
result=search_seq(st,key);
if(result!=)
printf("在顺序表里第%d个位置查找到了!\n",result);
else
printf("在顺序表里没有找到!\n");
break;
case :
printf("请创建递增的折半查找表\n");
create(st);
printf("请输入折半查找的关键字:");
scanf("%d",&key);
result=search_bin(st,key);
if(result!=)
printf("在顺序表里第%d个位置查找到了!\n",result);
else
printf("在顺序表里没有找到!\n");
break;
case :
print(st);
break;
case :
exit();
break;
default:printf("输入错误!\n");
}
printf("\n请重新输入您的选择:\n");
scanf("%d",&num);
}
return ;
}
typedef char infotype;
typedef struct
{
keytype key;//keytype为关键字的数据类型
infotype other;//其他数据
}elemtype;//数据元素类型
typedef struct
{
elemtype *r;//基地址
int length;//元素个数
}sstable;//静态查找表
int init(sstable &l)//初始化静态查找表,分配资源
{
l.r=new elemtype[max];
if(!l.r)
{
printf("初始化错误!\n");
return ;
}
l.length=;
return ;
}
void print(sstable l)//打印静态查找表的内容
{
for(int i=;i<=l.length;i++)
printf("%d号关键字:%d\n",i,l.r[i].key);
printf("元素个数:%d\n",l.length);
}
int create(sstable &l)//创建表,对表中输入数据
{
l.length=;
int k,i;
printf("请输入int型关键字,以-1结束:\n");
scanf("%d",&k);
while(k!=-)
{
l.r[l.length+].key=k;//0号位置留空
l.length++;
if(l.length>=max)
return ;
scanf("%d",&k);
}
printf("下标:");
for(i=;i<=l.length;i++)
printf("%4d",i);
printf("\n");
printf("key :");
for(i=;i<=l.length;i++)
printf("%4d",l.r[i].key);
printf("\n");
return ;
}
int search_seq(sstable st,keytype key)//在顺序表ST中顺序查找其关键字等于key的数据元素
{
//若找到,则函数值为该元素在表中的位置,否则为0
st.r[].key=key;
for(int i=st.length;i>=;i--)//从后往前找
{
if(st.r[i].key==key)
{
return i;
}
}
return ;
}
int search_bin(sstable st,int key)//在有序表ST中折半查找其关键字等于key的数据元素
{
//若找到,则函数值为该元素在表中的位置,否则为0
int low=;
int high=st.length;
int mid;
while(low<=high)
{
mid=(low+high)/;
printf("折半查找的low值%d、high值%d、mid值%d\n",low,high,mid);
if(key==st.r[mid].key)
return mid;
else if(key<st.r[mid].key)
high=mid-;
else
low=mid+;
}
return ;//表中不存在待查元素
}
运行结果如下:
