《搜索实验报告》由会员分享，可在线阅读，更多相关《搜索实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、重庆交通大学设计性实验报告班 级: 计软2班 学 号： 姓 名： 旧城余约 实验项目名称： 搜索 实验项目性质： 设计性实验 实验所属课程： 算法与数据结构 实验室(中心)： B01-407 指 导 教 师 ： 鲁云平 实验完成时间： 2015 年 5月 20 日教师评阅意见： 签名： 年 月 日实验成绩：一、 实验目的应用线性结构、树形结构实现查找。二、 实验内容及要求 内容： 1）有序表的二分查找；2）二叉排序树的查找。 要求：1） 建立有序表，然后进行二分查找；2） 建立二叉排序树，然后查找。三、 实验设备及软件 设备：计算机； 软件：visual C+ 6.0四、 实验过程及步骤 运行
2、环境：visual C+ 6.0； 实现思路：首先，是有序表的书写，是在顺序表的基础上用有序插入控制数据的有序输入，从而建立有序表，为后面的二分法查找数据做准备。顺序表的数据成员中，用*element来存储数据，MaxSize表示最大存储空间，length表示当前存储长度；在成员函数中，void Insert( T& x)用来有序插入数据建立有序表，每次插入数据前都要与已有数据进行比较大小，从而确定插入位置，同时void Search(T &x)用来二分法查找数据，先定义两个起始位置和末位置的变量以及一个中间位置的变量，每次用要查找的数与中间位置的数据进行比较，如果小则末位置为中间位置加一，反
3、之起始位置为中间位置减一； 然后，是二分排序树的书写，有二叉树结点BinaryTreeNode，包括数据域data，左子树指针leftChild以及右子树指针rightChild；在BinarySearchTree中用void Insert( T &x,BinaryTreeNode *&ptr)函数进行建立二叉树，比根数据小的存在左子树，比根大的存在右子树，用BinaryTreeNode* Find( T x,BinaryTreeNode *ptr)进行搜索查找，用递归算法进行实现，要查找的数比根数小，往左子树递归，反之，往右子树递归。 最后，用菜单进行实现。 编译步骤：在写类的时候，逐个函数
4、进行测试。五、 主要代码及运行结果（一）、主要代码：SeqList类：#includetemplateclass SeqListprivate:T *element;int MaxSize;int length;public:SeqList(int MaxListSize=10);SeqList()if(element)delete element;bool IsEmpty() return length=0;int Length()return length;bool Find(int i,T& x);/将第i个元素的值用x返回SeqList Delete(int i,T& x);/删除第i
5、个元素，并返回x的值void Search(T &x) ;/二分法搜索函数 void Insert( T& x);/有序插入建立有序表void Output() ;T GetNumber(int i)return elementi;templateSeqList:SeqList(int MaxListSize)MaxSize=MaxListSize;element=new TMaxSize;length=0;template bool SeqList:Find(int i,T& x) if(ilength)return false;elsex=elementi-1; return true;t
6、emplate void SeqList:Search (T &x)int high=length;int low=0;int mid;while(lowelementmid)low=mid+1;else if(xelementmid)high=mid-1;else if(x=elementmid) cout查找成功！endl;coutmid+1;break; if(x!=elementmid&(mid=low|mid=high) cout查找失败endl;templatevoid SeqList:Output () for (int i=0;ilength;i+)coutelementi ;
7、templatevoid SeqList:Insert ( T &x)/有序插入函数int i=0;while(ilength&elementii;j-)/有序插入elementj=elementj-1;elementi=x;length+;BinarySearchTree类：#includeusing namespace std;templateclass BinarySearchTree;templateclass BinaryTreeNodeprotected:T data;BinaryTreeNode *leftChild,*rightChild;public:/BinaryTreeN
8、ode():leftChild(NULL),rightChild(NULL)/构造函数/BinaryTreeNode( T d):data(d),leftChild(NULL),rightChild(NULL)/构造函数BinaryTreeNode( T d=0,BinaryTreeNode *L=NULL,BinaryTreeNode *R=NULL):data(d),leftChild(L),rightChild(R)/构造函数BinaryTreeNode()if(leftChild)delete leftChild;if(rightChild)delete rightChild;T Ge
9、tData()return data;friend class BinarySearchTree;template class BinarySearchTreeprivate:BinaryTreeNode *root;/二叉搜索树的根指针T stopvalue;/数据输入停止标志，用于输入void Insert( T &x,BinaryTreeNode *&ptr);/插入BinaryTreeNode* Find( T x,BinaryTreeNode *ptr);/查找void Traverse(ostream& out,BinaryTreeNode *subTree);/前序遍历输出pub
10、lic:BinarySearchTree():root(NULL)/构造函数BinarySearchTree(T value):stopvalue(value),root(NULL)/构造函数BinarySearchTree()if(root)delete root;/析构函数int Find(T x)return Find(x,root)!=NULL;/查找void Insert( T& x)Insert(x,root);/插入新元素void Traverse(ostream& out)Traverse(out,root);templateBinaryTreeNode* BinarySear
11、chTree:Find (T x,BinaryTreeNode *ptr)/二叉排序树的递归查找算法if(ptr=NULL)cout搜索失败！endl;return NULL;/搜索失败else if(xdata)return Find(x,ptr-leftChild);/在左子数查找else if(xptr-data)return Find(x,ptr-rightChild);/在右子数查找elsecout搜索成功！endl;return ptr;/相等，搜索成功templatevoid BinarySearchTree:Insert(T &x,BinaryTreeNode *&ptr)if(ptr=NULL)/新节点作为叶子结点插入ptr=new BinaryTreeNode (x);/创建新节点if(ptr=NULL)cout内存不足！endl;exit(1);else if(xdata)Insert(x,ptr-leftChild);/小于等于根的关键字，向左子树插入/我不清楚和根相等的关键字往哪里存else if(xptr-data)Insert(x,ptr-rightChild);/大于根的关键字，向右子数插入/*templatevoid BinarySearchTree:Remove(const T &x,BinaryTreeNode *&ptr)Bi
