数据结构查找实验报告

实验题9.1设计一个程序exp9-1.cpp，输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法找关键字5的过程。程序如下：//文件名:exp9-1.cpp#include<stdio.h>#defineMAXL100 //定义表中最多记录个数typedefintKeyType;typedefcharInfoType[10];typedefstruct{ KeyTypekey; //KeyType为关键字的数据类型InfoTypedata; //其他数据}NodeType;typedefNodeTypeSeqList[MAXL]; //顺序表类型intSeqSearch(SeqListR,intn,KeyTypek)//顺序查找算法{inti=0;while(i<n&&R[i].key!=k) { printf("%d",R[i].key); i++; //从表头往后找 }if(i>=n) return-1;else { printf("%d",R[i].key); returni; }}voidmain(){ SeqListR; intn=10,i; KeyTypek=5; inta[]={3,6,2,10,1,8,5,7,4,9}; for(i=0;i<n;i++) //建立顺序表 R[i].key=a[i]; printf("关键字序列:"); for(i=0;i<n;i++) printf("%d",R[i].key); printf("\n"); printf("查找%d所比较的关键字:\n\t",k); if((i=SeqSearch(R,n,k))!=-1) printf("\n元素%d的位置是%d\n",k,i); else printf("\n元素%d不在表中\n",k); printf("\n");}截图如下：实验题9.2设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。程序如下：//文件名:exp9-2.cpp#include<stdio.h>#defineMAXL100 //定义表中最多记录个数typedefintKeyType;typedefcharInfoType[10];typedefstruct{ KeyTypekey; //KeyType为关键字的数据类型InfoTypedata; //其他数据}NodeType;typedefNodeTypeSeqList[MAXL]; //顺序表类型intBinSearch(SeqListR,intn,KeyTypek) //二分查找算法{ intlow=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次比较:在[%d,%d]中比较元素R[%d]:%d\n",++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 returnmid; if(R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return-1;}voidmain(){ SeqListR; KeyTypek=9; inta[]={1,2,3,4,5,6,7,8,9,10},i,n=10; for(i=0;i<n;i++) //建立顺序表 R[i].key=a[i]; printf("关键字序列:"); for(i=0;i<n;i++) printf("%d",R[i].key); printf("\n"); printf("查找%d的比较过程如下:\n",k); if((i=BinSearch(R,n,k))!=-1) printf("元素%d的位置是%d\n",k,i); else printf("元素%d不在表中\n",k);}截图如下：实验题9.3设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。程序如下：//文件名:exp9-3.cpp#include<stdio.h>#defineMAXL100 //定义表中最多记录个数#defineMAXI20 //定义索引表的最大长度typedefintKeyType;typedefcharInfoType[10];typedefstruct{ KeyTypekey; //KeyType为关键字的数据类型InfoTypedata; //其他数据}NodeType;typedefNodeTypeSeqList[MAXL]; //顺序表类型typedefstruct{ KeyTypekey; //KeyType为关键字的类型 intlink; //指向分块的起始下标}IdxType;typedefIdxTypeIDX[MAXI]; //索引表类型intIdxSearch(IDXI,intm,SeqListR,intn,KeyTypek) //分块查找算法{ intlow=0,high=m-1,mid,i,count1=0,count2=0; intb=n/m; //b为每块的记录个数 printf("二分查找\n"); while(low<=high) //在索引表中进行二分查找,找到的位置存放在low中 { mid=(low+high)/2; printf("第%d次比较:在[%d,%d]中比较元素R[%d]:%d\n",count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累计在索引表中的比较次数 } if(low<m) //在索引表中查找成功后,再在线性表中进行顺序查找 { printf("比较%d次,在第%d块中查找元素%d\n",count1,low,k); i=I[low].link; printf("顺序查找:\n"); while(i<=I[low].link+b-1&&R[i].key!=k) { i++;count2++; printf("%d",R[i].key); } //count2累计在顺序表对应块中的比较次数 printf("\n"); printf("比较%d次,在顺序表中查找元素%d\n",count2,k); if(i<=I[low].link+b-1) returni; else return-1; } return-1;}voidmain(){ SeqListR; KeyTypek=46; IDXI; inta[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i; for(i=0;i<25;i++) //建立顺序表 R[i].key=a[i]; I[0].key=14;I[0].link=0; I[1].key=34;I[1].link=4; I[2].key