数据结构实验四.doc

福建农林大学金山学院实验报告
系（教研室）： 专业： 年级： 实验课程：数据结构
姓名： 学号： 实验室号：_ _ 计算机号：
实验时间： 指导教师签字： 成绩：
实验四：检索及基本算法的设计（验证性、4学时）
一、实验目的和要求
(1) 熟练掌握各种静态检索表方法(顺序检索、二分检索等)；
(2) 熟练掌握二叉排序树检索算法；
(3) 了解和掌握其它检索方法。
二、实验内容和原理
(1) 顺序检索算法的实现、二分法检索算法的实现；
(2) 二叉排序树检索算法的实现；
(3) Hash表的检索算法实现(选做)。
三、实验环境
1. 硬件：PC机；
2. 软件：Windows操作系统、Visual C++ 6.0
四、算法描述及实验步骤
算法描述及步骤如下：
（1）在VC环境下输入题目给出的程序代码。
（2）检查程序有无错误(包括语法错误和逻辑错误)，有则改之。
（3）编译和连接，仔细分析编译信息，如有错误应找出原因并改正之
（4）运行程序，输入数据，分析结果。
（5）将调试好的程序保存在自己的用户目录中，文件名自定
五、调试过程
顺序检索和二分法检索

二叉树查找

六、实验结果
顺序检索和二分法检索

二叉树查找

七、总结
(1)通过练习，了解C++源程序的编译，连接的运行，并能熟练使用集成环境的界面和有关菜单。
(2)能够通过编译时出现的出错提示信息，进行初步的纠错。
(3)完成一个程序的一般步骤为设计，录入 ，编译 ，如果出错，则修改，然后再编译，编译成功后，看看结果是否正确，如果结果不正确，则再重复以上步骤
（4）通过练习能，了解顺序检索、二分法检索和二叉树查找的性质，并通过练习进一步掌握顺序检索、二分法检索和二叉树查找的应用。
附录：
顺序检索和二分法检索
#include<iostream>
using namespace std;
int n=100;
typedef struct
{
int key;
}sqlist;
sqlist R[101];
int seqsearch(sqlist R[],int k,int s)
{
int i=s;
R[0].key=k;
while(R[i].key!=k)
i--;
return i;
}
int binaryseach(sqlist R[],int k,int s)
{
int low=1,mid,high=s;
while (low<=high)
{
mid=(low+high)/2;
if(k==R[mid].key)
return mid;
else
if(k<R[mid].key)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int main()
{
int s,i,k,t,h;
cout<<"输入要数组长度："<<endl;
cin>>s;
cout<<"输入数组元素"<<endl;
for(i=1;i<=s;i++)
cin>>R[i].key;
cout<<"输入要检索的数："<<endl;
cin>>k;
cout<<"顺序检索"<<endl;
t=seqsearch(R,k,s);
if(t!=0)
cout<<"第"<<k<<"个就是要检索的数"<<endl;
else
cout<<"不存在此数"<<endl;
cout<<"二分法检索"<<endl;
h=binaryseach(R,k,s);
if(h!=0)
cout<<"第"<<h<<"个就是要检索的数"<<endl;
else
cout<<"不存在此数"<<endl;
return 0;
}
二叉树查找
#include<iostream.h>
class Btree
{
public:
int value;
Btree *left;
Btree *right;
};
void insert(Btree *root,int k)
{
Btree *p;
Btree *q;
Btree *temp;
p=root;
q=root;
if(k==0)
{
cout<<"0 为本程序特殊符号记录，不能用做输入 "<<endl;
return;
}
while(p!=NULL&&p->value!=k)
{
if(k<p->value)
{
q=p;
p=p->left;
}
else
{
q=p;
p=p->right;
}
}
if(p==NULL)
{
temp=new Btree;
temp->value=k;
temp->left=NULL;
temp->right=NULL;
if(k<q->value)
q->left=temp;
else
q->right=temp;
}
else
{
cout<<"记录已经存在"<<endl;
return;
}
}
void dfs(Btree *p)
{
if(p==NULL)
return;
dfs(p->left);
if(p->value!=0)
cout<<" "<<p->value<<" ";
dfs(p->right);
}
void cz(Btree *root,int n)
{
Btree *p;
Btree *q;
p=root;
q=root;
int t;
while(p!=NULL)
{
if(n==p->value)
{
t=1;
break;
}
else
if(n<p->value)
{
q=p;
p=p->left;
}
else
if(n>p->value)
{
q=p;
p=p->right;
}
}
if(t==1)
cout<<"找到记录！"<<endl;
else
cout<<"找不到！"<<endl;
}
int main()
{char k;
int value,tag=1,n;
Btree *root=new Btree;
root->value=0;
root->left=NULL;
root->right=NULL;
while(tag)
{cout<<"选项：";
cin>>k;
switch(k)
{
case '1':
cout<<"输入关键字（非零整数）：";
cin>>value;
insert(root,value);
break;
case '2':
dfs(root);
cout<<endl;
break;
case '3':
cout<<"请输入要查找的数";
cin>>n;
cz(root,n);
break;
default:
tag=0;
}
}
return 0;}