搜索实验报告

重庆交通大学设计性实验报告班级:计软2班学号：姓名：旧城余约实验项目名称：找寻实验项目性质：设计性实验实验所属课程：算法与数据构造实验室(中心)：B01-407指导教师：鲁云平实验完成时间：2015年5月20日教师评阅建议：签字：年代日实验成绩：一、实验目的应用线性构造、树形构造实现查找。二、实验内容及要求内容：）有序表的二分查找；2）二叉排序树的查找。要求：1）建立有序表，尔后进行二分查找；2）建立二叉排序树，尔后查找。三、

实验设备及软件设备：计算机；软件：visualC++四、

实验过程及步骤运行环境：visualC++；实现思路：第一，是有序表的书写，是在序次表的基础上用有序插入控制数据的有序输入，从而建立有序表，为后边的二分法查找数据做准备。序次表的数据成员中，用*element来储藏数据，MaxSize表示最大储藏空间，length表示当前储藏长度；在成员函数中，voidInsert(T&x)用来有序插入数据建立有序表，每次插入数据前都要与已有数据进行比较大小，从而确定插入地址，同时voidSearch(T&x)用来二分法查找数据，先定义两个初步地址和末地址的变量以及一此中间地址的变量，每次用要查找的数与中间地址的数据进行比较，若是小则末地址为中间地址加一，反之初步地址为中间地址减一；尔后，是二分排序树的书写，有二叉树结点BinaryTreeNode，包括数据域data，左子树指针leftChild以及右子树指针rightChild；在BinarySearchTree中用voidInsert(T&x,BinaryTreeNode<T>*&ptr)函数进行建立二叉树，比根数据小的存在左子树，比根大的存在右子树，用BinaryTreeNode<T>*Find(Tx,BinaryTreeNode<T>*ptr)进行搜索查找，用递归算法进行实现，要查找的数比根数小，往左子树递归，反之，往右子树递归。最后，用菜单进行实现。编译步骤：在写类的时候，逐个函数进行测试。五、主要代码及运行结果（一）、主要代码：SeqList类：#include<>template<classT>classSeqList{private:*element;intMaxSize;intlength;public:SeqList(intMaxListSize=10);~SeqList( ){if(element)delete[]element;}boolIsEmpty( ){returnlength==0;}intLength( ){returnlength;}boolFind(inti,T&x);//将第i个元素的值用x返回SeqList<T>Delete(inti,T&x);//删除第i个元素，并返回voidSearch(T&x);//二分法找寻函数voidInsert(T&x);//有序插入建立有序表voidOutput( );TGetNumber(inti){returnelement[i];}

x的值};template<classT>SeqList<T>::SeqList(intMaxListSize){MaxSize=MaxListSize;element=newT[MaxSize];length=0;}template<classT>boolSeqList<T>::Find(inti,T&x){if(i<1||i>length)returnfalse;else{x=element[i-1];returntrue;}}template<classT>voidSeqList<T>::Search(T&x){inthigh=length;intlow=0;intmid;while(low<=high){mid=(low+high)/2;if(x>element[mid])low=mid+1;elseif(x<element[mid])high=mid-1;elseif(x==element[mid]){cout<<"查找成功！"<<endl;cout<<mid+1;break;}}if(x!=element[mid]&&(mid==low||mid==high))cout<<"

查找失败

"<<endl;}template<classT>voidSeqList<T>::Output( ){for(inti=0;i<length;i++)cout<<element[i]<<"";}template<classT>voidSeqList<T>::Insert(T&x)//{

有序插入函数inti=0;while(i<length&&element[i]<=x)//

比较i++;for(intj=length;j>i;j--)//

有序插入element[j]=element[j-1];element[i]=x;length++;}BinarySearchTree类：#include<iostream>usingnamespacestd;template<classT>classBinarySearchTree;template<classT>classBinaryTreeNode{protected:Tdata;BinaryTreeNode<T>*leftChild,*rightChild;public://BinaryTreeNode( ):leftChild(NULL),rightChild(NULL){}////BinaryTreeNode(Td):data(d),leftChild(NULL),rightChild(NULL){}//BinaryTreeNode(Td=0,BinaryTreeNode*L=NULL,BinaryTreeNode*R=NULL):data(d),leftChild(L),rightChild(R){}//构造函数~BinaryTreeNode( ){

构造函数

构造函数if(leftChild)deleteleftChild;if(rightChild)deleterightChild;}TGetData( ){returndata;}friendclassBinarySearchTree<T>;};template<classT>classBinarySearchTree{private:BinaryTreeNode<T>*root;//

二叉找寻树的根指针Tstopvalue;//数据输入停止标志，用于输入voidInsert(T&x,BinaryTreeNode<T>*&ptr);//插入BinaryTreeNode<T>*Find(Tx,BinaryTreeNode<T>*ptr);//voidTraverse(ostream&out,BinaryTreeNode<T>*subTree);//public:BinarySearchTree( ):root(NULL){}//构造函数BinarySearchTree(Tvalue):stopvalue(value),root(NULL){}//~BinarySearchTree( )

查找前序遍历输出构造函数{if(root)deleteroot;}//析构函数intFind(Tx){returnFind(x,root)!=NULL;}//查找voidInsert(T&x){Insert(x,root);}//插入新元素voidTraverse(ostream&out){Traverse(out,root);}};template<classT>BinaryTreeNode<T>*BinarySearchTree<T>::Find(Tx,BinaryTreeNode<T>*ptr)//

二叉排序树的递归查找算法{if(ptr==NULL){cout<<"找寻失败！"<<endl;returnNULL;//找寻失败}elseif(x<ptr->data)returnFind(x,ptr->leftChild);//

在左子数查找elseif(x>ptr->data)returnFind(x,ptr->rightChild);//

在右子数查找else{cout<<"找寻成功！"<<endl;returnptr;//相等，找寻成功}}template<classT>voidBinarySearchTree<T>::Insert(T&x,BinaryTreeNode<T>*&ptr){if(ptr==NULL)//新节点作为叶子结点插入{ptr=newBinaryTreeNode<T>(x);//创办新节点if(ptr==NULL){cout<<"内存不足！"<<endl;exit(1);}}elseif(x<ptr->data)Insert(x,ptr->leftChild);//小于等于根的要点字，向左子树插入我不清楚和根相等的要点字往哪里存elseif(x>ptr->data)Insert(x,ptr->rightChild);//大于根的要点字，向右子数插入}/*template<classT>voidBinarySearchTree<T>::Remove(constT&x,BinaryTreeNode<T>*&ptr){BinaryTreeNode<T>*temp;if(ptr!=NULL)if(x<ptr->data)Remove(x,ptr->leftChild);elseif(x>ptr->data)Remove(x,ptr->rightChild);elseif(ptr->leftChild!=NULL&&ptr->rightChild!=NULL){temp=Min(ptr->rightChild);ptr->data=temp->data;Remove(ptr->data,ptr->rightChild);}else{temp=ptr;if(ptr->leftChild==NULL)ptr=ptr->rightChild;elseif(ptr->leftChild==NULL)ptr=ptr->leftChild;deletetemp;}}*/template<classT>voidBinarySearchTree<T>::Traverse(ostream&out,BinaryTreeNode<T>*subTree)//

私有函数：找寻并输出根为

subTree

的二叉树{if(subTree!=NULL){out<<subTree->data<<'';//输出Traverse(out,subTree->leftChild);//Traverse(out,subTree->rightChild);//

subTree的数值递归找寻并输出subTree的左子树递归并输出subTree的右子树}}/*template<classT>ostream&operator<<(ostream&out,BinarySearchTree<T>&Tree){,out);out<<endl;returnout;}*/出！~~~~~~~~~\n";Menu类：#include""#include""template<classT>classMenu{public:voidBillsOfSearch(SeqList<T>&ob1,BinarySearchTree<T>&ob2);voidInputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2);voidOutputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2);voidSearchNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2);};template<classT>voidMenu<T>::BillsOfSearch(SeqList<T>&ob1,BinarySearchTree<T>&ob2){intchoice;while(choice){cout<<endl;cout<<"\n=============================\n";cout<<"|找寻选项|\n";cout<<"=============================\n";cout<<"~~~~~~~1、输入数据！~~~~~~~~~\n";cout<<"~~~~~~~2、输出数据！~~~~~~~~~\n";cout<<"~~~~~~~3、找寻数据！~~~~~~~~~\n";cout<<"~~~~~~~0、退cout<<"请输入你的选择（输入编号即可）：";cin>>choice;switch(choice){case1:InputNumber(ob1,ob2);break;case2:OutputNumber(ob1,ob2);break;case3:SearchNumber(ob1,ob2);break;case0:break;default:cout<<"输入有误！";break;}}}template<classT>voidMenu<T>::InputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2){Tnumber;intsign=1,i=0;while(sign)//循环建立有序表{i++;cout<<"请输入第"<<i<<"个数据：(输入0停止)";cin>>number;if(number==0){intchoose=1;while(choose){cout<<"0可否为要输入的数？（1、是；0、不是。）";cin>>choose;switch(choose){case1:(number);(number);choose=0;break;case0:sign=0;break;default:cout<<"输入选择有误，请重新选择！"<<endl;break;}/*if(choose==1){(number);//建立有序表(number);//建立二叉找寻树choose=0;}elseif(choose==0)sign=0;elsecout<<"输入选择有误，请重新选择！"<<endl;*/}}else{(number);//建立有序表(number);//建立二叉找寻树}}/*for(intj=0;j<( );j++){number1=(j);(number1);//将建立的序次表变换为二叉找寻树}*/}template<classT>voidMenu<T>::OutputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2){intchoose;while(choose){cout<<endl;cout<<"\n=============================\n";cout<<"|输出选项|\n";cout<<"=============================\n";cout<<"|~~~~~~1、序次表输出！~~~~~~~|\n";cout<<"|~~~~~~2、二叉找寻树输出！~~~|\n";cout<<"|~~~~~~0、退出！~~~~~~~~~~|\n";cout<<"请输入你的选择：";cin>>choose;switch(choose){case1:( );break;case2:(cout);break;case0:break;default:cout<<"输入有误！";break;}}/*if(choose==1)( );elseif(choose==2)(cout);elsecout<<"输入有误！"<<endl;*/}template<classT>voidMenu<T>::SearchNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2){intchoose;Tx;cout<<"请输入你要查找的数：";cin>>x;while(choose){cout<<endl;cout<<"\n===================================\n