数据结构实验四.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
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>s;
cout<<"输入数组元素"<>R[i].key;
cout<<"输入要检索的数："<>k;
cout<<"顺序检索"<turn 0;
}
二叉树查找
#include
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 为本程序特殊符号记录，不能用做输入 "< }
while(p!=NULL&&p->value!=k)
{
if(kvalue)
{
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(kvalue)
q->left=temp;
else
q->right=temp;
}
else
{
cout<<"记录已经存在"<left);
if(p->value!=0)
cout<<" "<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(nvalue)
{
q=p;
p=p->left;
}
else
if(n>p->value)
{
q=p;
p=p->right;
}
}
if(t==1)
cout<<"找到记录！"< else
cout<<"找不到！"<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<>n;
cz(root,n);
break;
default:
tag=0;
}
}
return 0;}