数据结构查找实验报告_数据结构报告实验报告
数据结构查找实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构报告实验报告”。
实验题9.1 设计一个程序exp9-1.cpp，输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法找关键字5的过程。程序如下：
//文件名:exp9-1.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {
KeyType key;
//KeyType为关键字的数据类型 //其他数据
//定义表中最多记录个数
InfoType data;
} NodeType;typedef NodeType SeqList[MAXL];
//顺序表类型
int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法
{
int i=0;
while(i
{
} printf(“%d ”,R[i].key);i++;
//从表头往后找
if(i>=n)return-1;
else
} void main(){ SeqList R;{
} printf(“%d”,R[i].key);return i;
} int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i
//建立顺序表
printf(“关键字序列:”);for(i=0;i
截图如下：
实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。
程序如下：
//文件名:exp9-2.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {
//定义表中最多记录个数 KeyType key;
//KeyType为关键字的数据类型
InfoType data;
//其他数据 } NodeType;typedef NodeType SeqList[MAXL];
//顺序表类型
int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low
{
mid=(low+high)/2;printf(“ 第%d
次
比
较
:在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key);
if(R[mid].key==k)
//查找成功返回
return mid;
if(R[mid].key>k)
//继续在R[low..mid-1]中查找
high=mid-1;
else
low=mid+1;
//继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i
//建立顺序表
R[i].key=a[i];printf(“关键字序列:”);for(i=0;i
比
较
元
素
中
} else printf(“元素%d的位置是%dn”,k,i);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 #define MAXL 100 #define MAXI 20 typedef int KeyType;typedef char InfoType[10];typedef struct {
KeyType key;
//KeyType为关键字的数据类型
//定义表中最多记录个数
//定义索引表的最大长度
InfoType data;
//其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct {
KeyType key;int link;
//KeyType为关键字的类型 //指向分块的起始下标
//顺序表类型
} IdxType;typedef IdxType IDX[MAXI];
//索引表类型
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m;
//b为每块的记录个数
printf(“二分查找n”);while(low
//在索引表中进行二分查找,找到的位置存放在low中
{
mid=(low+high)/2;printf(“ 第%d
次
比
较
:在[%d,%d]
中
比
较
元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key);
if(I[mid].key>=k)
high=mid-1;
else
low=mid+1;
count1++;
//累计在索引表中的比较次数
} if(low
//在索引表中查找成功后,再在线性表中进行顺序查找
{
printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k);
i=I[low].link;
printf(“顺序查找:n
”);
while(i
{
i++;count2++;
printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数
printf(“n”);
printf(“比较%d次,在顺序表中查找元素%dn”,count2,k);
if(i
return i;
else
return-1;}
素 } return-1;void main(){
} SeqList R;KeyType k=46;IDX I;int a[]={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
//建立顺序表
I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”);
截图如下：
