搜索實驗報告

重慶交通大學設計性實驗報告班級:計軟2班學號：姓名：舊城余約實驗項目名稱：找尋實驗項目性質：設計性實驗實驗所屬課程：算法與數據構造實驗室(中心)：B01-407指導教師：魯云平實驗完成時間：2015年5月20日教師評閱建議：簽字：年代日實驗成績：一、實驗目的應用線性構造、樹形構造實現查找。二、實驗內容及要求內容：）有序表的二分查找；2）二叉排序樹的查找。要求：1）建立有序表，爾后進行二分查找；2）建立二叉排序樹，爾后查找。三、

實驗設備及軟件設備：計算機；軟件：visualC++四、

實驗過程及步驟運行環(huán)境：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)//新節(jié)點作為葉子結點插入{ptr=newBinaryTreeNode<T>(x);//創(chuàng)辦新節(jié)點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)//循環(huán)建立有序表{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