实验八 查找算法的应用.docx
《实验八 查找算法的应用.docx》由会员分享，可在线阅读，更多相关《实验八 查找算法的应用.docx（19页珍藏版）》请在冰点文库上搜索。
实验八查找算法的应用
实验八查找算法的应用
实验目的：
掌握查找算法的比较，熟练掌握各种查找方法的函数编写。
实验要求：
1、编写函数，实现顺序查找；
2、编写函数，实现折半查找；
3、编写程序，实现索引查找；
程序如下：
#include"string.h"
#include"stdio.h"
#include"string.h"
#include"malloc.h"
#defineERROR0;
#defineTRUE1;
#defineOK1;
typedefcharKeyType;
typedefstruct{
KeyTypekey;
}ElemType;
typedefstruct{//顺序存储结构
ElemTypeelem[100];
intlength;
}SSTable;
SSTableST,Idx,Bi;//定义查找表ST为全局变量
//定义分块有序表Idx的存储
typedefstruct{//索引表存储结构
KeyTypekey;
intlink;
}IdxType;
IdxTypeindex[50];//定义索引表为全局变量
inte,bi;//e,bi为全局变量，分别是索引表中每块表记录的个数和块数，全局变量方便踌函数调用
voidCreat_ST（）//构造一个含n个数据元素的表态查找表ST
{
intn,i,j=0;
chars[100];
printf（"你需要构造多少个数据？
请输入：
"）;
scanf（"%d",&n）;
printf（"\n"）;
while（n<0||n>100）
{
printf（"抱歉，系统暂时无法完成你需要的个数的操作，请重输：
\n"）;
getchar（）;
scanf（"%d",&n）;
}
printf（"接着，请输入%d个数据，以构造一个数据表\n",n）;
getchar（）;
gets（s）;
for（;s[j]!
='\0';j++）
ST.elem[j].key=s[j];
ST.length=j;
printf（"你输入了%d个数据!
它们是：
\n",j）;
for（i=0;iprintf（"%c",ST.elem[i].key）;
printf（"\n"）;
}
voidDestroy_ST（）//销毁表ST
{
inti;
if（!
ST.elem[0].key）
printf（"错误！
原表为空，销毁失败。
\n"）;
else
{for（i=ST.length-1;i<0;i--）
free（ST.elem[i].key）;//从表尾开始销毁
ST.length=0;
printf（"原表销毁成功！
\n"）;
}
}
intSearch_Seq（）//顺序查找
{
KeyTypeky;
inti;
if（ST.length==0）
{printf（"查找表为空，请先建表！
\n"）;
returnERROR;}
printf（"要查找的数据:
\n"）;
scanf（"%c",&ky）;
ST.elem[ST.length+1].key=ky;//哨兵
for（i=0;ST.elem[i].key!
=ky;i++）;//从前往后找
//i为要查找元素在表中位置，若失败，为0
if（i<=ST.length）printf（"恭喜，查找成功！
该数据在表的第%d个位置上。
\n",i+1）;
elseprintf（"抱歉，查找失败！
\n"）;
}
voidvisit_S（）//被Trave_ST函数调用
{
inti;
printf（"ST表中的元素如下：
\n"）;
for（i=0;iprintf（"%c",ST.elem[i].key）;
printf（"\n"）;
}
voidTrave_ST（）//遍历查找表，其中对ST的每个元素调用函数visit_S
{
if（ST.length==0）
printf（"错误，原表为空，遍历失败!
"）;
else
visit_S（）;
}
voidCreat_Bi（）//构造一个含n个数据元素的表态查找表Bi,数据实现有序排列
{
intn,i,j=0;
charc;
chars[100];
printf（"你需要构造多少个数据？
请输入：
"）;
scanf（"%d",&n）;
printf（"\n"）;
while（n<0||n>100）
{
printf（"抱歉，系统暂时无法完成你需要的个数的操作，请重输：
\n"）;
getchar（）;
scanf（"%d",&n）;
}
printf（"接着，请输入%d个数据，以构造一个数据表\n",n）;
getchar（）;
gets（s）;
for（;s[j]!
='\0';j++）
Bi.elem[j].key=s[j];
Bi.length=j;
printf（"你输入了%d个数据!
它们是：
\n",j）;
for（i=0;iprintf（"%c",Bi.elem[i].key）;
printf（"\n"）;
for（i=0;iprintf（"%c",ST.elem[i].key）;
printf（"\n"）;
for（j=0;jfor（i=0;iif（Bi.elem[i].key>Bi.elem[i+1].key）
{
c=Bi.elem[i].key;
Bi.elem[i].key=Bi.elem[i+1].key;
Bi.elem[i+1].key=c;
}
printf（"你输入的数据有序排列后为:
\n"）;
for（i=0;iprintf（"%c",Bi.elem[i].key）;
printf（"\n"）;
}
voidDestroy_Bi（）//销毁表Bi
{
inti;
if（!
Bi.elem[0].key）
printf（"错误！
原表为空，销毁失败。
\n"）;
else
{for（i=Bi.length-1;i<0;i--）
free（Bi.elem[i].key）;//从表尾开始销毁
Bi.length=0;
printf（"原表销毁成功！
\n"）;
}
}
intSearch_Bin（）//有序查找
{
KeyTypeky;
inti;
inthigh,mid;
intlow=0;
if（Bi.length==0）
{printf（"查找表为空，请先建表！
\n"）;
returnERROR;
}
high=Bi.length;
printf（"要查找的数据:
\n"）;
scanf（"%c",&ky）;
while（low<=high）
{
mid=（low+high）/2;
if（Bi.elem[mid].key==ky）
{printf（"恭喜，查找成功！
该数据在表的第%d个位置上。
\n",mid+1）;
return;
}
elseif（kyhigh=mid-1;
else
low=mid+1;
}
printf（"抱歉，查找失败！
\n"）;
}
voidvisit_B（）//被Trave_Bi函数调用
{
inti;
printf（"Bi表中的元素如下：
\n"）;
for（i=0;iprintf（"%c",Bi.elem[i].key）;
printf（"\n"）;
}
voidTrave_Bi（）//遍历查找表，其中对Bi的每个元素调用函数visit_B
{
if（Bi.length==0）
printf（"错误，原表为空，遍历失败!
"）;
else
visit_B（）;
}
voidCreat_Idx（）//构造一个含n个数据元素的索引查找表Idx,因为时间和水平有限，算法中要求读者有序输入数据
{
intn,i,j=0;//n为有序表中数据个数
chars[100];
charc;
printf（"你需要构造多少个数据？
请输入：
"）;
scanf（"%d",&n）;
printf（"\n"）;
while（n<0||n>100）
{
printf（"抱歉，系统暂时无法完成你需要的个数的操作，请重输：
\n"）;
getchar（）;
scanf（"%d",&n）;
}
printf（"接着，请输入%d个数据，以构造一个数据表\n",n）;
getchar（）;
gets（s）;//如果输入的数据串大于n，系统将自动进行截断处理
for（i=0;i{
if（i>1）//当已输入的数据多于一个时
while（s[i]//如果大于前者，要求重输，并自动覆盖当前检测到的数据
{printf（"你输入的第%d个数据比前一个数小了，请重输一个比%c大的数据：
",i+1,s[i-1]）;
scanf（"%c",&c）;
s[i]=c;
getchar（）;
}
}//完成数据输入
for（;s[j]!
='\0';j++）
Idx.elem[j].key=s[j];
Idx.length=j;
printf（"你输入的数据中%d个有效!
它们是：
\n",n）;
Idx.length=n;
for（i=0;iprintf（"%c",Idx.elem[i].key）;
printf（"\n"）;
printf（"你想把有序表分成多少块?
__"）;//索引表
scanf（"%d",&bi）;
while（bi<1||bi>100||n/bi<1）{
printf（"\n输入错误或表中数据个数少于%d个，请重输要分的块数!
",bi）;
scanf（"%d",&bi）;
e=n/bi;}
e=n/bi;//每块记录个数
i=0;
for（j=0;j{index[j].key=Idx.elem[i].key;//初始化
index[j].link=i;//link即为Idx中元素的标记号
for（i=（j?
e*j-1:
0）;i{
if（Idx.elem[i+1].key>Idx.elem[i].key）//后面的大，重新赋值给index
{index[j].key=Idx.elem[i+1].key;
index[j].link=i+1;}
else//保持不变
{index[j].key=Idx.elem[i].key;
index[j].link=i;
}
}//fori
}//forj
printf（"你建立的索引表为：
\n"）;
for（i=0;i{
printf（"块中最大数据:
%c,位置：
%d\n",index[i].key,index[i].link+1）;
}
}
voidDestroy_Idx（）//销毁表Idx
{
inti;
if（!
Idx.elem[0].key）
printf（"错误！
原表为空，销毁失败。
\n"）;
else
{for（i=Idx.length-1;i<0;i--）
free（Idx.elem[i].key）;//从表尾开始销毁
Idx.length=0;
printf（"原表销毁成功！
\n"）;
}
}
voidIdxSerch（）//索引表查找
{
intlow=0,high=bi-1,mid,i;
intfl=0;
charky;
if（Idx.length==0）
{printf（"查找表为空，请先建表！
\n"）;
return;}
printf（"请输入你要查找的数据:
_\n"）;
getchar（）;
scanf（"%c",&ky）;
while（low<=high）
{
mid=（low+high）/2;
if（index[mid].keylow=mid+1;
else
high=mid-1;
}
if（low{
for（i=index[low].link;i<=index[low].link+e-1&&iif（Idx.elem[i-1].key==ky）//此处，如果用Idx.elem[i]将查找表中首元素失败
{printf（"恭喜，查找成功！
该数据在表的第%d个位置上。
\n",i）;fl=1;}
}
if（fl==0）printf（"抱歉，查找失败！
\n"）;
}
voidvisit_Idx（）//被Trave_Idx函数调用
{
inti;
printf（"Idx表中的元素如下：
\n"）;
for（i=0;iprintf（"%c",Idx.elem[i].key）;
printf（"\n"）;
}
voidTrave_Idx（）//遍历查找表，其中对Bi的每个元素调用函数visit_B
{
if（Idx.length==0）
printf（"错误，原表为空，遍历失败!
"）;
else
visit_Idx（）;
}
intmenu（a）//可以公用的分菜单
{
inti;
printf（"\n\n\n"）;
for（i=0;i<80;i++）printf（"-"）;
printf（"\n"）;
printf（"1.构建查找表\t\t2.销毁查找表\t\t3.在表中查找元素\n"）;
printf（"4.遍历表中记录\t\t5.返回上层主菜单\t\t0.退出本系统\n"）;
for（i=0;i<80;i++）
printf（"-"）;
printf（"\n"）;
printf（"\t\t请输入0——5选择：
"）;
scanf（"%d",&a）;
getchar（）;
return（a）;
}
voidMENU_All（）//主菜单
{
inta;
inti,flag,go;
printf（"\n\n\n"）;
for（i=0;i<80;i++）printf（"^"）;
for（i=0;i<80;i++）printf（"^"）;
printf（"\t\t\t欢迎使用静态查找表系统\n"）;
for（i=0;i<80;i++）
printf（"*"）;
printf（"\n"）;
printf（"1.顺序表的查找\t\t2.有序表的查找（折半查找）\t\t3.索引表顺序查找\n"）;
printf（"0.退出本系统\n"）;
for（i=0;i<80;i++）
printf（"*"）;
printf（"\n"）;
printf（"\t\t现在，请输入0——3选择您的操作（继续或退出）：
"）;
scanf（"%d",&go）;
getchar（）;
switch（go）
{case1:
{
for（i=1;a!
=5;i++）
{
a=menu（a）;
switch（a）
{
case1:
Creat_ST（）;break;
case2:
Destroy_ST（）;break;
case3:
Search_Seq（）;break;
case4:
Trave_ST（）;break;
case5:
break;//跳出顺序表查找的循环，回到上一层菜单
case0:
exit（0）;
default:
printf（"选择错误，请重选！
\n\n"）;
}
}//for
break;
}//case1
case2:
{
for（i=1;a!
=5;i++）
{
a=menu（a）;
switch（a）
{case1:
Creat_Bi（）;break;
case2:
Destroy_Bi（）;break;
case3:
Search_Bin（）;break;
case4:
Trave_Bi（）;break;
case5:
break;//跳出有序表的查找（折半查找）的循环，回到上一层菜单
case0:
exit（0）;
default:
printf（"选择错误，请重选！
\n\n"）;}
}
break;
}//case2
case3:
{
for（i=1;a!
=5;i++）
{
a=menu（a）;
switch（a）
{case1:
Creat_Idx（）;break;
case2:
Destroy_Idx（）;break;
case3:
IdxSerch（）;break;
case4:
Trave_Idx（）;break;
case5:
break;//跳出索引表顺序查找的循环，回到上一层菜单
case0:
exit（0）;
default:
printf（"选择错误，请重选！
\n\n"）;}
}
break;
}//case3
case0:
exit（0）;
default:
printf（"选择错误，请重新输入你的操作选择！
\n\n"）;
}
}
voidmain（）
{
inta,b;
inti;
for（i=1;;i++）
{
if（i>1）
{printf（"\n请注意，系统即将刷新清屏并回到主菜单，请记住当前操作!
\n\n"）;
system（"PAUSE"）;//暂停函数
system（"cls"）;//清屏函数
}
MENU_All（）;
}
}
运行结果：
升级会员 