实验题9.1 设计一个程序exp9-1.cpp,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法找关键字5的过程。
程序如下:
//文件名:exp9-1.cpp
#include <stdio.h>
#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<n && R[i].key!=k)
{
printf("%d ",R[i].key);
i++; //从表头往后找
}
if (i>=n)
return -1;
else
{
printf("%d",R[i].key);
return i;
}
}
void main()
{
SeqList R;
int n=10,i;
KeyType k=5;
int a[]={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>
#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<=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) //查找成功返回
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<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>
#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; //KeyType为关键字的类型
int link; //指向分块的起始下标
} 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<=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)
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<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=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)
printf("元素%d的位置是%d\n",k,i);
else
printf("元素%d不在表中\n",k);
printf("\n");
}
截图如下:
福州大学数计学院
《数据结构》上机实验报告
专业:应用数学
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
昆明理工大学信息工程与自动化学院学生实验报告201201学年第一学期课程名称数据结构开课实验室年月日一实验内容查找算法其中线性表的…
实验报告课程名称实验项目数据结构查找姓名xx专业班级学号网络工程网络132130402xxxx计算机科学与技术学院实验教学中心20…
100410528孙晨添数据结构实验报告实验第四章实验简单查找算法一需求和规格说明查找算法这里主要使用了顺序查找折半查找二叉排序树…
实验四查找一实验目的1掌握顺序表的查找方法尤其是折半查找方法2掌握二叉排序树的查找算法二实验内容1234建立一个顺序表用顺序查找的…
数据结构实验实验一静态查找表中的查找一、实验目的:1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查…
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
81实现顺序查找的算法一实验目的1熟悉掌握各种查找方法深刻理解各种查找算法及其执行的过程2学会分析各种查找算法的性能二实验内容81…
一实验目的和要求1掌握图的相关概念包括图有向图无向图完全图子图连通图度入度出度简单回路和环等定义2重点掌握图的各种存储结构包括邻接…
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
心得体会:做了一个星期的程序设计终于做完了,在这次程序设计课中,真是让我获益匪浅。对大一学习的C语言和这学期开的数据结构,并没有掌…