实验八 查找实验.doc

实验八查找实验

1、程序验证
（1）建立含有若干个整数的顺序表，在此基础上实现顺序表的简单顺序查找算法。
（2）下列函数是以顺序表的最后一个单元作为监视哨的简单顺序查找，阅读该程序，写出运行结果，并通过运行来验证。
＃defineLIST_SIZE20
typedefstruct{
charr[LIST_SIZE]；
intlength； //length为表中元素的个数
}RecordList；
RecordList*SqLset(){
RecordList*L；
inti=0;charc;
L=malloc(sizeof(RecordList))；
scanf(“%c”,&c);//输入一个字符
L->length=0;
while(c!=’#’){//‘#’为输入结束标志
L->r[i]=c;
L->length++;i++;
if(L->length==LIST_SIZE-1)break;
scanf(“%c”,&c);
}
return(L)；
}
intSequenSearch(RecordList*L，chark,intn){
//在长度为n的顺序表L中顺序查找其关键字等于k的元素
inti=0,position=-1;//position为查找到的位置
L->r[n].key=k；//最后一个单元作为监视哨
while(n!=i){
if(L->r[i].key==k){
position=i+1;
break;
}
i++;
}
returnposition;
}
main(){
RecordList*A;
intm;
charc;
A=SqLset();
scanf(“%c”,&c);//输入待查元素
m=SequenSearch(A，c,A->length);
if(m==-1)
printf(“查找不成功！”)；
elseprintf(“m=%d,查找成功！”,m)；
}
2、算法填空
请在下面算法的空格处填入适当内容，以使算法能够递归实现二分查找过程。
＃defineLIST_SIZE20
typedefstruct{
intr[LIST_SIZE]；
intlength； //length为表中元素的个数
}RecordList；
RecordList*SqLset(){
RecordList*L；
inti=0,a;
L=malloc(sizeof(RecordList))；
printf(“输入一个整型有序序列，输入0时结束！”)
scanf(“%d”,&a);//输入一个整数
L->length=0;
while(a!=0){//整数0为输入结束标志，输入一个有序的整数序列
L->r[i]=a;
L->length++;i++;
if(L->length==LIST_SIZE-1)break;
scanf(“%d”,&a);
}
return(L)；
}
intBinSrch(RecordList*L，intk,intlow,inthigh){
//在有序表L中二分查找其关键字等于k的元素，
intmid;
if(low>high)return-1；
else{
mid=(low+high)/2；
if() //找到待查元素
returnmid；
elseif(k<L->r[mid])
return；
else
return;
}
}
main(){
RecordList*A;
intk,low,high;
A=SqLset();
low=0;high=A->length-1
scanf(“%d”,&k);//输入待查元素
m=BinSrch(A,k,low,high);
if(m==-1)
printf(“查找不成功！”)；
elseprintf(“m=%d,查找成功！”,m)；
}
3、算法设计
（1）为二分查找的非递归算法设计主函数，完善该算法，并通过运行来验证。
（2）设顺序表中的关键字是递增有序的，将监视哨设在高下标端，设计算法实现简单顺序查找。