查找实验.docx
《查找实验.docx》由会员分享，可在线阅读，更多相关《查找实验.docx（18页珍藏版）》请在冰点文库上搜索。
查找实验
查找实验
一、实验目的
（1）了解各种查找的特性，以及它们在实际问题中的应用。
（2）掌握各种查找的实现方法及其基本操作，学会运用不同的查找方法来解决不同的问题。
二、实验内容
一、顺序查找
基本知识：
线性表的数据类型定义及对线性表的顺序扫描操作。
算法思想：
从线性表一端开始，顺序扫描线性表，依次将扫描到的结点关健字与给定值key比较，若相等，则查找成功；若扫描结束后，仍末找到关健字等于key的结点，则查找失败。
二、二分查找
基本知识：
线性表的数据类型定义、线性表中结点按其关健字有序排列。
算法思想：
①用待查值key与表的中间结点关健字比较（中间结点将线性表分为两个子表），若比较结果相等，则查找成功；
若待查值key大于中间结点关健字，选右子表继续比较；
若待查值key小于中间结点关健字，选左子表继续比较；
②重复①，直到查找成功或结束；
三、分块查找
基本知识：
分块查找是把线性表分成若干块，各块中的结点顺序可任意亦可有序，但块与块之间必须按关健字大小有序，即前一块中的最大关健字要小于后一块中的最小关健字。
因此，与线性表的顺序查找和二分查找不同，除定义线性表的数据类型外，还须定义一个递增有序的索引表，以描述线性表“分块有序”的状态
算法思想：
分块查找实际上是对索引表和线性表的两次查找。
顺序查找或二分查找索引表：
以确定待查结点在哪一块。
由于索引表递增有序（即块与块之间按关健字大小有序），因此，索引表的查找常采用二分查找算法以提高算法效率。
在所确定的块内顺序查找线性表：
确定待查结点在线性表的确切位置。
由于块内结点即可无序亦可有序，因此，块内查找一般采用顺序查找算法。
查找实验（两次课完成）
实验题目:
请编写一个完整的程序，用菜单驱动方法实现：
利用分块查找算法在线性表（学生情况表）list中查找给定值key（学号）的结点，并将该结点的部分数据进行修改。
注：
在此实验中你还可以添加一个或几个你最熟悉的查找算法来实现此功能。
解题思路：
例：
输入学号：
30207；选择课程名：
语文；输入修改成绩：
100；
在学生情况表中查找学号为“30207”的学生记录；将该学生记录的语文成绩修改为100；
建立文件算法：
建立待查找的数据文件SCORE.TXT的函数creat（）
输入算法：
在待查找的数据文件SCORE.TXT中找
输出算法：
将修改后的线性表（学生情况表）数据输出到文件SCORE.TXT中，
算法要点：
分块查找的查找过程分两步进行:
先在线性表中确定待查找的结点属于哪一块。
由于块与块之间按关健字大小有序，因此，块间查找可采用二分查找算法。
在所确定的块内查找待查结点，由于块内结点即可无序亦可有序，因此，块内查找一般可采用顺序查找算法。
找到指定结点后，按要求修改结点中的有关数据。
三、数据类型及算法
1．数据类型定义
（1）学生的结点结构
typedefstruct
{
charnum[8],name[10];//学生的学号，姓名
intage,chin,phy,chem,eng;//学生的年龄，中文、物理、化学和英语成绩
}STUDENT;
（2）线性表的结点结构
typedefstruct
{
keytypekey[8];//关键字
STUDENTstu;
}TABLE;
（3）索引表的结点结构
typedefstruct
{
keytypekey[8];
intlow,high;
}INDEX;
2．操作算法
（1）输入算法
从SCORE.TXT文件中读出数据、建立线性表及索引表可通过调用函数readtxt（void）完成，此函数算法如下：
voidreadtxt（void）//构造线性表list及索引表inlist
{
FILE*fp;inti,d;charmax[8];
fp=fopen（“score.txt”,”r”）;//以只读方式打开SCORE.TXT文件
for（i=0;i{
fscanf（fp,”%s”,list[i].stu.num）;//从文件SCORE.TXT中输入第i个学生的学号
fscanf（fp,”%s”,list[i].stu.name）;//从SCORE.TXT中输入第i个学生的姓名
fscanf（fp,”%d”,&list[i].stu.chin）;//从SCORE.TXT中输入第i生的中文成绩
fscanf（fp,”%d”,&list[i].stu.phy）;//从SCORE.TXT中输入第i生的物理成绩
fscanf（fp,”%d”,&list[i].stu.chem）;//从SCORE.TXT中输入第i生的化学成绩
fscanf（fp,”%d”,&list[i].stu.eng）;//从SCORE.TXT中输入第i生的英语成绩
strcpy（list[i].key,list[i].stu.num）;//将第i个学生的学号设为关键字
}
for（i=0;i{
inlist[i].low=i+（i*（S-1））;//每块内结点数为S
inlist[i].high=i+（i+1）*（S-1）;
}
strcpy（max,list[0].stu.num）;//将第0个学生的学号复制到数组max中
d=0;
for（i=1;i{
if（strcmp（max,list[i].stu.num）<0）//串max小于串list[i].stu.num
strcpy（max,list[i].stu.num）;//将大的串放到max中,这是在线性表的一块中找
if（（i+1）%6==0）
{
strcpy（inlist[d].key,max）;d++;//将索引表中第d个元素的inlist[d].key
if（istrcpy（max,list[i+1].stu.num）;//将线性表中的下一块的第一个学生的学号
i++;//复制到max中,去求该块中的最大学号
}
}
fclose（fp）;//关闭SCORE.TXT文件
}
（2）动态分块查找算法
voidmodify（char*key,intkc,intcj）//kc是课程号cj是成绩key是要找的学号
{
intlow1=0,high1=B-1,mid1,i,j;
intflag=0;
while（low1<=high1&&!
flag）
{
mid1=（low1+high1）/2;//在索引表中求中间块位置
if（strcmp（inlist[mid1].key,key）==0）//中间块的关键字值与要找的键值相比较
flag=1;//找到了
elseif（strcmp（inlist[mid1].key,key）>0）//到前边的块内查找
high1=mid1-1;
elselow1=mid1+1;//到后边的块内查找
}
if（low1{
i=inlist[low1].low;
j=inlist[low1].high;
}
while（ii++;//在块内找学号相符的学生,可能找到,也可能找不到
if（strcmp（list[i].key,key）==0）//找到了,根据所给的学号去修改相应的成绩
if（kc==1）
list[i].stu.chin=cj;
elseif（kc==2）
list[i].stu.phy=cj;
elseif（kc==3）
list[i].stu.chem=cj;
elseif（kc==4）
list[i].stu.eng=cj;
}
（3）输出算法
voidwritetxt（void）
{
FILE*fp;inti;
fp=fopen（“score.txt”,”w”）;//以写方式打开SCORE.TXT文件
for（i=0;i{
fprintf（fp,”%s“,list[i].stu.num）;
fprintf（fp,”%s“,list[i].stu.name）;
fprintf（fp,”%d“,list[i].stu.chin）;
fprintf（fp,”%d“,list[i].stu.phy）;
fprintf（fp,”%d“,list[i].stu.chem）;
fprintf（fp,”%d“,list[i].stu.eng）;
fprintf（fp,”\n”）;
}
fclose（fp）;//关闭SCORE.TXT文件
}
四、程序
#include
#defineM18//线性表长
#defineB3//将线性表分成B块
#defineS6//每块内结点数为S
typedefchardatatype;//
typedefcharkeytype;//定义关键字类型是字符型
typedefstruct//定义学生的结点结构
{
charnum[8],name[10];//学生的学号，姓名
intage,chin,phy,chem,eng;//学生的年龄，中文、物理、化学和英语成绩
}STUDENT;
typedefstruct//定义线性表的结点结构
{
keytypekey[8];STUDENTstu;
}TABLE;
typedefstruct//定义索引表的结点结构
{
keytypekey[8];intlow,high;
}INDEX;
TABLElist[M];//说明线性表变量
INDEXinlist[B];//索引表变量
//下面是主函数,各算法清单同前
voidmain（）
{
intkc,cj;charkey[8];
creat（）;//创建数据文件SCORE.TXT
printf（“请输入欲修改成绩的学生号!
\n”）;
gets（key）;
printf（“选择欲修改成绩的课程:
语文
（1）物理
（2）化学（3）英语（4）：
”）;
scanf（“%d”,&kc）;
printf（“输入该课程的修改成绩：
”）;
scanf（“%d”,&cj）;
readtxt（）;//调用输入数据函数
modify（key,kc,cj）;//调用分块查找及数据修改函数
writetxt（）;//调用输出数据函数
}
三、实验源程序及其运行结果
#include
#include
#defineM18
#defineB3
#defineS6
typedefchardatatype;
typedefcharkeytype;
typedefstruct
{
charnum[8],name[10];//学生的学号，姓名
intage,chin,phy,chem,eng;//学生的年龄，中文、物理、化学和英语成绩
}STUDENT;
STUDENTstud[M];
typedefstruct
{
keytypekey[8];//存放一位学生的关键字
STUDENTstu;//学生信息
}TABLE;
typedefstruct
{
keytypekey[8];//索引表的关键字记录学生的一项数据
intlow,high;//索引表是以块来存放的，这就要求记录每块的内容在线性表里的范围，以节约查找时间
}INDEX;
TABLElist[M];//说明线性表变量
INDEXinlist[B];//索引表变量
intsave（）
{FILE*fp;
inti;
if（（fp=fopen（"score.txt","wb"））==NULL）
{
printf（"不能打开文件\n"）;
return0;
}
printf（"\n文件的内容是\n\n"）;
for（i=0;i//并输出到屏幕上方便查看
{
fprintf（fp,"%s",stud[i].num）;//学号
printf（"%s",stud[i].num）;
fprintf（fp,"%s",stud[i].name）;
printf（"%s",stud[i].name）;
fprintf（fp,"%d",stud[i].chin）;
printf（"%d",stud[i].chin）;
fprintf（fp,"%d",stud[i].phy）;
printf（"%d",stud[i].phy）;
fprintf（fp,"%d",stud[i].chem）;
printf（"%d",stud[i].chem）;
fprintf（fp,"%d",stud[i].eng）;
printf（"%d",stud[i].eng）;
fprintf（fp,"\n"）;
printf（"\n"）;
}
fclose（fp）;
}
voidcreat（）
{
inti;
for（i=0;i{scanf（"%s%s%d%d%d%d",stud[i].num,stud[i].name,
&stud[i].chin,&stud[i].phy,&stud[i].chem,&stud[i].eng）;
}
save（）;
}
voidreadtxt（void）//构造线性表list及索引表inlist
{
FILE*fp;
inti,d;
charmax[8];
fp=fopen（"score.txt","r"）;//以只读方式打开SCORE.TXT文件
for（i=0;i{
fscanf（fp,"%s",list[i].stu.num）;//从文件SCORE.TXT中输入第i个学生的学号
fscanf（fp,"%s",list[i].stu.name）;//从SCORE.TXT中输入第i个学生的姓名
fscanf（fp,"%d",&list[i].stu.chin）;//从SCORE.TXT中输入第i生的中文成绩
fscanf（fp,"%d",&list[i].stu.phy）;//从SCORE.TXT中输入第i生的物理成绩
fscanf（fp,"%d",&list[i].stu.chem）;//从SCORE.TXT中输入第i生的化学成绩
fscanf（fp,"%d",&list[i].stu.eng）;//从SCORE.TXT中输入第i生的英语成绩
strcpy（list[i].key,list[i].stu.num）;//将第i个学生的学号设为关键字
}
for（i=0;i{
inlist[i].low=i+（i*（S-1））;//每块内结点数为S
inlist[i].high=i+（i+1）*（S-1）;
}
strcpy（max,list[0].stu.num）;//将第0个学生的学号复制到数组max中
d=0;
for（i=1;i{
if（strcmp（max,list[i].stu.num）<0）//串max小于串list[i].stu.num
strcpy（max,list[i].stu.num）;//将大的串放到max中,这是在线性表的一块中找
if（（i+1）%6==0）
{
strcpy（inlist[d].key,max）;d++;//将索引表中第d个元素的inlist[d].key
if（istrcpy（max,list[i+1].stu.num）;//将线性表中的下一块的第一个学生的学号
i++;//复制到max中,去求该块中的最大学号
}
}
fclose（fp）;//关闭SCORE.TXT文件
}
voidmodify（char*key,intkc,intcj）//kc是课程号cj是成绩key是要找的学号
{
intlow1=0,high1=B-1,mid1,i,j;
intflag=0;
while（low1<=high1&&!
flag）
{
mid1=（low1+high1）/2;//在索引表中求中间块位置
if（strcmp（inlist[mid1].key,key）==0）//中间块的关键字值与要找的键值相比较
flag=1;//找到了
elseif（strcmp（inlist[mid1].key,key）>0）//到前边的块内查找
high1=mid1-1;
elselow1=mid1+1;//到后边的块内查找
}
if（low1{
i=inlist[low1].low;
j=inlist[low1].high;
}
while（ii++;//在块内找学号相符的学生,可能找到,也可能找不到
if（strcmp（list[i].key,key）==0）//找到了,根据所给的学号去修改相应的成绩
if（kc==1）
list[i].stu.chin=cj;
elseif（kc==2）
list[i].stu.phy=cj;
elseif（kc==3）
list[i].stu.chem=cj;
elseif（kc==4）
list[i].stu.eng=cj;
}
voidwritetxt（void）
{
FILE*fp;inti;
fp=fopen（"score.txt","w"）;//以写方式打开SCORE.TXT文件
for（i=0;i{
fprintf（fp,"%s",list[i].stu.num）;
fprintf（fp,"%s",list[i].stu.name）;
fprintf（fp,"%d",list[i].stu.chin）;
fprintf（fp,"%d",list[i].stu.phy）;
fprintf（fp,"%d",list[i].stu.chem）;
fprintf（fp,"%d",list[i].stu.eng）;
fprintf（fp,"\n"）;
printf（"%s",list[i].stu.num）;
printf（"%s",list[i].stu.name）;
printf（"%d",list[i].stu.chin）;
printf（"%d",list[i].stu.phy）;
printf（"%d",list[i].stu.chem）;
printf（"%d",list[i].stu.eng）;
printf（"\n"）;
}
fclose（fp）;//关闭SCORE.TXT文件
}
intmain（）
{
intkc,cj;
charkey[8];
intx;
printf（"********************\n"）;
printf（"本程序是从文件中查找到一个数据并进行修改！
\n\n"）;
printf（"********************\n\n"）;
do
{
printf（"********************\n"）;
printf（"x=1建立文件!
\n"）;
printf（"x=2修改文件！
\n"）;
printf（"x=0退出"）;
printf（"注意：
如果还没有建立文件是不能操作的！
\n\n"）;
printf（"********************\n\n"）;
do
{
fflush（stdin）;
printf（"请输入x的值：
"）;
scanf（"%d",&x）;
if（（x!
=1）&&（x!
=2）&&（x!
=0））
{printf（"请输入正确的x的值！
\n\n"）;}
}while（（x!
=1）&&（x!
=2）&&（x!
=0））;
switch（x）
{case1:
printf（"\t文件的建立与输出\n"）;
printf（"建立的数据文件的内容是：
\n\n"）;
creat（）;//创建数据文件SCORE.TXT
printf（"\n\n"）;
break;
case2:
printf（"\t对文件进行修改：
\n"）;
printf（"请输入欲修改成绩的学生学号！
\n"）;//输入要修改的学生学号
scanf（"%s",key）;
printf（"选择欲修改的成绩课程：
语文
（1）物理
（2）化学（3）英语（4）：
"）;
//输入要修改的课程
scanf（"%d",&kc）;
printf（"输入该课程的修改成绩"）;//输入该课程的修改成绩
scanf（"%d",&cj）;
readtxt（）;
modify（key,kc,cj）;
printf（"\n修改后的数据为：
\n\n"）;
writetxt（）;
printf（"\n\n"）;
break;
}
}while（x!
=0）;
printf（"\t再见！
\n"）;
}
运行结果：
四、实验小结
1、建立文件：
即通过一个for循环，将各个学生的信息输入，再通过save函数将信息输入到文件中，然后再将数据输出到屏幕上。
2、数据的修改：
分两步走，首先要知道关键字在哪一块中，（二分法）在找到块之后要找到指定结点（顺序查找），从而进行数据修改。
升级会员 