2025年探索性实验研究综合报告

试验室(中心):B01-407 试验完毕时间：年5月20日应用线性构造、树形构造实现查找。1)有序表的二分查找；2)二叉排序树的查找。1)建立有序表，然后进行二分查找；2)建立二叉排序树，然后查找。设备：计算机；运行环境：visualC++6.0;实现思绪：首先，是有序表的书写，是在次序表的基础上用有序插入控制数据的有序输入，从而建立有序表，为背面的二分法查找数据做准备。次序表的数据组员中，用*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(intMaxL}voidSearch(T&x);//二分法搜索函数template<classT>{element=newT[Max}boolSeqList<T>::Find(inti,T{returntrue;}{{cout<<"查找成功!"<<endl;}if(x!=element[mid]&&(mid==lowllmcout<<"查找失败"<<endl;}}for(intj=length;j>i;j-)//有序插入}BinaryTreeNode<T>*leftChild,*rig//BinaryTreeNode(Td):data(d),leftChild(NULL),rightChild(NULL{}//构造函数BinaryTreeNode(Td=0,BinaryTreeNode*{}Tstopvalue;//数据输入停止标志，用于输入voidInsert(T&x,BinaryTreeNode<T>*&ptr);/BinaryTreeNode<T>*Find(Tx,BinaryTreeNode<T>*{{returnFind(x,root)!=NULL;}//查找voidTraverse(ostream&out)BinaryTreeNode<T>*BinarySearchTree<T>:Find(Tx,BinaryTreeNode<T>*ptr)//二叉排序树的递归查找算法{cout<<"搜索失败!"<<endl;returnNULL;//搜索失败}returnFind(x,ptr->leftChild);//在左子数查找returnFind(x,ptr->rightChild);//在右子数查找{cout<<"搜索成功!"<<endl;returnptr;/相等，搜索成功}voidBinarySearchTree<T>::Insert(T&x,BinaryTreeNode<{if(ptr==NULL)//新节点作为叶子结点插入{ptr=newBinaryTreeNod}//我不清晰和根相等的关键字往哪里存Insert(x,ptr->rightChild);//不小于根的关键字，向右子数插入}voidBinarySearchTree<T>::Remove(constT&x,BinaryTreeNode<T>*&ptr)Remove(x,ptr->rightCelseif(ptr->leftChild!=NULL&&ptr->rightChild!=NULL)temp=Min(ptr->rightChRemove(ptr->data,ptr->rightvoidBinarySearchTree<T>::Traverse(ostream&out,BinaryTreeNode<T>*subTree)//私有函数：搜索并输出根为subTree的二叉树out<<subTree->data<<';//输出subTree的数值}}ostream&operator<<(ostream&out,BinarySearch{Tree.Traverse(Tree.rvoidBillsOfSearch(SeqList<T>&ob1,BinarySearchTrvoidInputNumber(SeqList<T>&ob1,BinarySearchTreevoidOutputNumber(SeqList<T>&ob1,BinarySearcvoidSearchNumber(SeqList<T>&ob1,BinarySearvoidMenu<T>::BillsOfSearch(SeqList<T>&ob1,BinarySearchTree<T>&o{cout<<"\n=cout<<"=====cout<<"~~~~~~~1、输入数据!~~~~~~~~~\n";cout<<"~~~~~~~2、输出数据!~~~~~~~~~1n";cout<<"~~~~~~~3、搜索数据!~~~~~~~~~\n";cout<<"~~~~~~~0、退出!~~~~~~~~~\n";cout<<"请输入你的选择(输入编号即可):";cin>>choice;case1:InputNumber(obl,ocase2:OutputNumber(ob1,case3:SearchNumber(ob1,ob2);break;default:cout<<"输入有误!";break;}voidMenu<T>::InputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2){{cout<<"0与否为要输入的数?(1、是；0、不是。)";cin>>choose;{case1:obl.Insert(number);ob2.Insert(numdefault:cout<<"输入选择有误，请重新选择!"<<endl;break;}{ob1.Insert(number);//建立有序表ob2.Insert(number);//建立二叉搜索树}cout<<"输入选择有误，请重新选择!"<<endl;}ob1.Insert(number);//建立有序表ob2.Insert(number);//建立二叉搜索树}/*for(intj=0;j<ob1.LengthO;j++){numberl=ob1.GetNumber}voidMenu<T>:OutputNumber(SeqList<T>&obl,BinarySearchTree<T>&ob2){{cout<<"I~~~~~~1、次序表输出!~~cout<<"|~~~~~~2、二叉搜索树输出!~~~|\n";cout<<"I~~~~~~0、退出!~~~~~~~~~~|\n";default:cout<<"输入有误!";break;voidMenu<T>::SearchNumber(SeqList<T>&ob1,BinarySearch{{cout<<"\n============cout<<"l~~~~~~~1、次序表的二分法搜索!~cout<<"l~~~~~~~2、二叉搜索树搜索!~~~~~~~|\n";cout<<"I~~~~~~~0、退出!~~~~~~~~~~~~~|\n";default:cout<<"输入有误!";break;}主函数：BinarySearchTree<doub}(二)、运行成果：主菜单：输入数据：输入数据：搜索选项是否为要输入的数?1、是；a、不是。)日搜索选项 2、输出数据!~~~~请输入你的选择(输入编号即可),2 请输入你的选择(输入编号即可),2-出! !输出选项 搜索数据：~~~~~~~2、输出数据!~~~~~~~~~~~~~~~~~~~~~~~~~~g退出~~~~~~~~~~请输入你的选择(输入编号即可):3、顺序表的二分法搜索!~~~、顺序表的二分法搜索!~~~2、二又搜索树搜索!~~~~~~~=-=- 请输入你的选择(输入编号即可):aPreamanykeytoco在这次试验中，我收获了诸多，对次序表的认识也加深了某些，基于数组的存储构造还是