数据结构实验报告
查找
指导老师：柯凡
杨嘉玥 罗木兰 刘琳琳 姚望 李绮
2014 年 5 月 26 日
一． 实验内容
1.建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入
待查数据元素的关键字进行查找。
2.实现二叉排序树的创建、查找、插入、输出等算法
二． ADT 描述
1. 分别用数组和链式存储结构实现查找，在第一次实验内容的基础上新
增加了查找函数，具体代码见“详细设计”，截图见“运行界面”。
2. 二叉搜索树是一种特殊的二叉树，每个结点比左孩子中所有的结点都
要大，比右孩子中所有孩子都要小，因此，对二叉搜索树进行中序遍
历可以得到有序的一组序列。二叉搜索树的结点与树的类定义类似于
二叉树中的定义。我想起了用二叉树实现的另一种数据结构—堆。
二叉搜索树中用到的四个主要的函数：分别为查找，删除，插入以及
输出。其中插入的时候用到了查找函数中保存下来的结点信息，必须
要先判断树中是否已有该元素，若有，则不需要插入；若没有，要把
新节点加入到查找操作停止的地方。
删除操作中，若要删除叶结点，只需将父结点的指针清零再释放。若
被删结点的左子树为空，拿右子女顶替。同理右子树为空。若左右均
不为空，在右子树中寻找中序的第一个结点（最小），用它的值填补被
删结点，再来递归处理问题。
//查找函数
BSTNode *BSTreeSearch( BSTNode *bt, KeyType k );
//插入函数
void BSTreeInsert( BSTNode *&bt, KeyType k );
//删除函数
int BSTreeDelete( BSTNode *&bt, KeyType k );
//中序输出
void output(BSTNode *bt);
三． 详细设计
1. 线性表的查找
（1）用数组实现的查找
//查找函数部分
int search(T e)const
for (int i=1;i<=count;i++)
{
if (elems[i]==e)
return i;
}
return 0;
}
//main函数部分的查询语句
case 8:
{
int num;
cout<<"请输入要查找的数据"<<endl;
cin>>num;
int i=L.getlocation(num);
if(i==0)
cout<<"没有该数据!"<<endl;
else
cout<<"第 "<<i<<" 个数据"<<endl;
break;
}
（2）用链表实现的查找
//查找函数
int search(T& e)
{
int location=1;
Node<T> *p=head->next;
while(p!=NULL)
{
if(p->data==e)
{
return location;
}
else
{
p=p->next;
location++;
}
}
return location;
}
//main函数部分的查询语句
case 8:
{
double num;
cout<<"请输入要查找的元素"<<endl;
cin>>num;
int i=L.search(num);
if(i>L.length()){
cout<<"没有该元素！"<<endl;
}else
cout<<"第 "<<i<<"个元素"<<endl;
break;
}
