2025年探索性實驗研究綜合報告

試驗室(中心):B01-407 試驗完畢時間：年5月20日應(yīng)用線性構(gòu)造、樹形構(gòu)造實現(xiàn)查找。1)有序表的二分查找；2)二叉排序樹的查找。1)建立有序表，然后進(jìn)行二分查找；2)建立二叉排序樹，然后查找。設(shè)備：計算機(jī)；運行環(huán)境：visualC++6.0;實現(xiàn)思緒：首先，是有序表的書寫，是在次序表的基礎(chǔ)上用有序插入控制數(shù)據(jù)的有序輸入，從而建立有序表，為背面的二分法查找數(shù)據(jù)做準(zhǔn)備。次序表的數(shù)據(jù)組員中，用*element來存儲數(shù)據(jù)，MaxSize表達(dá)最大存儲空間，length表達(dá)目前存儲長度；在組員函數(shù)中，voidInsert(T&x)用來有序插入數(shù)據(jù)建立有序表，每次插入數(shù)據(jù)前都要與已經(jīng)有數(shù)據(jù)進(jìn)行比較大小，從而確定插入位置，同步voidSearch(T&x)用來二分法查找數(shù)據(jù)，先定義兩個起始位置和末位置的變量以及一種中間位置的變量，每次用要查找的數(shù)與中間位置的數(shù)據(jù)進(jìn)行比較，假如小則末位置為中間位置加一，反之起始位置為中間位置減一；然后，是二分排序樹的書寫，有二叉樹結(jié)點BinaryTreeNode,包括數(shù)據(jù)域data,左子樹指針leftChild以及右子樹指針rightChild;在BinarySearchTree中用voidInsert(T&x,BinaryTreeNode<T>*&ptr)函數(shù)進(jìn)行建立二叉樹，比根數(shù)據(jù)小的存在左子樹，比根大的存在右子樹，用BinaryTreeNode<T>*Find(Tx,BinaryTreeNode<T>*ptr)進(jìn)行搜索查找，用遞歸算法進(jìn)行實現(xiàn)，要查找的數(shù)比根數(shù)小，往左子樹遞歸，反之，往右子樹遞歸。最終，用菜單進(jìn)行實現(xiàn)。編譯環(huán)節(jié)：在寫類的時候，逐一函數(shù)進(jìn)行測試。SeqList(intMaxL}voidSearch(T&x);//二分法搜索函數(shù)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{}//構(gòu)造函數(shù)BinaryTreeNode(Td=0,BinaryTreeNode*{}Tstopvalue;//數(shù)據(jù)輸入停止標(biāo)志，用于輸入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);//在左子數(shù)查找returnFind(x,ptr->rightChild);//在右子數(shù)查找{cout<<"搜索成功!"<<endl;returnptr;/相等，搜索成功}voidBinarySearchTree<T>::Insert(T&x,BinaryTreeNode<{if(ptr==NULL)//新節(jié)點作為葉子結(jié)點插入{ptr=newBinaryTreeNod}//我不清晰和根相等的關(guān)鍵字往哪里存Insert(x,ptr->rightChild);//不小于根的關(guān)鍵字，向右子數(shù)插入}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)//私有函數(shù)：搜索并輸出根為subTree的二叉樹out<<subTree->data<<';//輸出subTree的數(shù)值}}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、輸入數(shù)據(jù)!~~~~~~~~~\n";cout<<"~~~~~~~2、輸出數(shù)據(jù)!~~~~~~~~~1n";cout<<"~~~~~~~3、搜索數(shù)據(jù)!~~~~~~~~~\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與否為要輸入的數(shù)?(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;}主函數(shù)：BinarySearchTree<doub}(二)、運行成果：主菜單：輸入數(shù)據(jù)：輸入數(shù)據(jù)：搜索選項是否為要輸入的數(shù)?1、是；a、不是。)日搜索選項 2、輸出數(shù)據(jù)!~~~~請輸入你的選擇(輸入編號即可),2 請輸入你的選擇(輸入編號即可),2-出! !輸出選項 搜索數(shù)據(jù)：~~~~~~~2、輸出數(shù)據(jù)!~~~~~~~~~~~~~~~~~~~~~~~~~~g退出~~~~~~~~~~請輸入你的選擇(輸入編號即可):3、順序表的二分法搜索!~~~、順序表的二分法搜索!~~~2、二又搜索樹搜索!~~~~~~~=-=- 請輸入你的選擇(輸入編號即可):aPreamanykeytoco在這次試驗中，我收獲了諸多，對次序表的認(rèn)識也加深了某些，基于數(shù)組的存儲構(gòu)造還是