搜索實(shí)驗(yàn)報(bào)告

1、重慶交通大學(xué)設(shè)計(jì)性實(shí)驗(yàn)報(bào)告班 級(jí): 計(jì)軟2班 學(xué) 號(hào)： 姓 名： 舊城余約 實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 搜索 實(shí)驗(yàn)項(xiàng)目性質(zhì)： 設(shè)計(jì)性實(shí)驗(yàn) 實(shí)驗(yàn)所屬課程： 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)室(中心)： B01-407 指 導(dǎo) 教 師 ： 魯云平 實(shí)驗(yàn)完成時(shí)間： 2015 年 5月 20 日教師評(píng)閱意見(jiàn)： 簽名： 年 月 日實(shí)驗(yàn)成績(jī)：一、 實(shí)驗(yàn)?zāi)康膽?yīng)用線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)實(shí)現(xiàn)查找。二、 實(shí)驗(yàn)內(nèi)容及要求 內(nèi)容： 1）有序表的二分查找；2）二叉排序樹(shù)的查找。 要求：1） 建立有序表，然后進(jìn)行二分查找；2） 建立二叉排序樹(shù)，然后查找。三、 實(shí)驗(yàn)設(shè)備及軟件 設(shè)備：計(jì)算機(jī)； 軟件：visual C+ 6.0四、 實(shí)驗(yàn)過(guò)程及步驟 運(yùn)行

2、環(huán)境：visual C+ 6.0； 實(shí)現(xiàn)思路：首先，是有序表的書(shū)寫(xiě)，是在順序表的基礎(chǔ)上用有序插入控制數(shù)據(jù)的有序輸入，從而建立有序表，為后面的二分法查找數(shù)據(jù)做準(zhǔn)備。順序表的數(shù)據(jù)成員中，用*element來(lái)存儲(chǔ)數(shù)據(jù)，MaxSize表示最大存儲(chǔ)空間，length表示當(dāng)前存儲(chǔ)長(zhǎng)度；在成員函數(shù)中，void Insert( T& x)用來(lái)有序插入數(shù)據(jù)建立有序表，每次插入數(shù)據(jù)前都要與已有數(shù)據(jù)進(jìn)行比較大小，從而確定插入位置，同時(shí)void Search(T &x)用來(lái)二分法查找數(shù)據(jù)，先定義兩個(gè)起始位置和末位置的變量以及一個(gè)中間位置的變量，每次用要查找的數(shù)與中間位置的數(shù)據(jù)進(jìn)行比較，如果小則末位置為

3、中間位置加一，反之起始位置為中間位置減一； 然后，是二分排序樹(shù)的書(shū)寫(xiě)，有二叉樹(shù)結(jié)點(diǎn)BinaryTreeNode，包括數(shù)據(jù)域data，左子樹(shù)指針leftChild以及右子樹(shù)指針rightChild；在BinarySearchTree中用void Insert( T &x,BinaryTreeNode<T> *&ptr)函數(shù)進(jìn)行建立二叉樹(shù)，比根數(shù)據(jù)小的存在左子樹(shù)，比根大的存在右子樹(shù)，用BinaryTreeNode<T>* Find( T x,BinaryTreeNode<T> *ptr)進(jìn)行搜索查找，用遞歸算法進(jìn)行實(shí)現(xiàn)，要查找的數(shù)比根數(shù)小，往左子

4、樹(shù)遞歸，反之，往右子樹(shù)遞歸。 最后，用菜單進(jìn)行實(shí)現(xiàn)。 編譯步驟：在寫(xiě)類(lèi)的時(shí)候，逐個(gè)函數(shù)進(jìn)行測(cè)試。五、 主要代碼及運(yùn)行結(jié)果（一）、主要代碼：SeqList類(lèi)：#include<assert.h>template<class T>class 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

5、length;bool Find(int i,T& x);/將第i個(gè)元素的值用x返回SeqList<T> Delete(int i,T& x);/刪除第i個(gè)元素，并返回x的值void Search(T &x) ;/二分法搜索函數(shù) void Insert( T& x);/有序插入建立有序表void Output() ;T GetNumber(int i)return elementi;template<class T>SeqList<T>:SeqList(int MaxListSize)MaxSize=MaxListSize;e

6、lement=new TMaxSize;length=0;template <class T>bool SeqList<T>:Find(int i,T& x) if(i<1|i>length)return false;elsex=elementi-1; return true;template <class T>void SeqList<T>:Search (T &x)int high=length;int low=0;int mid;while(low<=high)mid=(low+high)/2;if(x&g

7、t;elementmid)low=mid+1;else if(x<elementmid)high=mid-1;else if(x=elementmid) cout<<"查找成功！"<<endl;cout<<mid+1;break; if(x!=elementmid&&(mid=low|mid=high) cout<<"查找失敗"<<endl;template<class T>void SeqList<T>:Output () for (int i=0

8、;i<length;i+)cout<<elementi<<" "template<class T>void SeqList<T>:Insert ( T &x)/有序插入函數(shù)int i=0;while(i<length&&elementi<=x)/比較i+;for(int j=length;j>i;j-)/有序插入elementj=elementj-1;elementi=x;length+;BinarySearchTree類(lèi)：#include<iostream>usin

9、g namespace std;template<class T>class BinarySearchTree;template<class T>class BinaryTreeNodeprotected:T data;BinaryTreeNode<T> *leftChild,*rightChild;public:/BinaryTreeNode():leftChild(NULL),rightChild(NULL)/構(gòu)造函數(shù)/BinaryTreeNode( T d):data(d),leftChild(NULL),rightChild(NULL)/構(gòu)造函數(shù)Bi

10、naryTreeNode( T d=0,BinaryTreeNode *L=NULL,BinaryTreeNode *R=NULL):data(d),leftChild(L),rightChild(R)/構(gòu)造函數(shù)BinaryTreeNode()if(leftChild)delete leftChild;if(rightChild)delete rightChild;T GetData()return data;friend class BinarySearchTree<T>template <class T>class BinarySearchTreeprivate:B

11、inaryTreeNode<T> *root;/二叉搜索樹(shù)的根指針T stopvalue;/數(shù)據(jù)輸入停止標(biāo)志，用于輸入void Insert( T &x,BinaryTreeNode<T> *&ptr);/插入BinaryTreeNode<T>* Find( T x,BinaryTreeNode<T> *ptr);/查找void Traverse(ostream& out,BinaryTreeNode<T> *subTree);/前序遍歷輸出public:BinarySearchTree():root(NULL

12、)/構(gòu)造函數(shù)BinarySearchTree(T value):stopvalue(value),root(NULL)/構(gòu)造函數(shù)BinarySearchTree()if(root)delete root;/析構(gòu)函數(shù)int Find(T x)return Find(x,root)!=NULL;/查找void Insert( T& x)Insert(x,root);/插入新元素void Traverse(ostream& out)Traverse(out,root);template<class T>BinaryTreeNode<T>* BinarySear

13、chTree<T>:Find (T x,BinaryTreeNode<T> *ptr)/二叉排序樹(shù)的遞歸查找算法if(ptr=NULL)cout<<"搜索失?。?quot;<<endl;return NULL;/搜索失敗else if(x<ptr->data)return Find(x,ptr->leftChild);/在左子數(shù)查找else if(x>ptr->data)return Find(x,ptr->rightChild);/在右子數(shù)查找elsecout<<"搜索成功！&

14、quot;<<endl;return ptr;/相等，搜索成功template<class T>void BinarySearchTree<T>:Insert(T &x,BinaryTreeNode<T> *&ptr)if(ptr=NULL)/新節(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入ptr=new BinaryTreeNode<T> (x);/創(chuàng)建新節(jié)點(diǎn)if(ptr=NULL)cout<<"內(nèi)存不足！"<<endl;exit(1);else if(x<ptr->data)Inser

15、t(x,ptr->leftChild);/小于等于根的關(guān)鍵字，向左子樹(shù)插入/我不清楚和根相等的關(guān)鍵字往哪里存else if(x>ptr->data)Insert(x,ptr->rightChild);/大于根的關(guān)鍵字，向右子數(shù)插入/*template<class T>void BinarySearchTree<T>:Remove(const T &x,BinaryTreeNode<T> *&ptr)BinaryTreeNode<T> *temp;if(ptr!=NULL)if(x<ptr->da

16、ta)Remove(x,ptr->leftChild);else if(x>ptr->data)Remove(x,ptr->rightChild);else if(ptr->leftChild!=NULL&&ptr->rightChild!=NULL)temp=Min(ptr->rightChild);ptr->data=temp->data;Remove(ptr->data,ptr->rightChild);elsetemp=ptr;if(ptr->leftChild=NULL)ptr=ptr->r

17、ightChild;else if(ptr->leftChild=NULL)ptr=ptr->leftChild;delete temp;*/template<class T>void BinarySearchTree<T>:Traverse(ostream& out,BinaryTreeNode<T> *subTree)/私有函數(shù)：搜索并輸出根為subTree的二叉樹(shù)if(subTree!=NULL)out<<subTree->data<<' '/輸出subTree的數(shù)值Traverse(o

18、ut,subTree->leftChild);/遞歸搜索并輸出subTree的左子樹(shù)Traverse(out,subTree->rightChild);/遞歸并輸出subTree的右子樹(shù)/*template<class T>ostream& operator<<(ostream& out,BinarySearchTree<T>& Tree)Tree.Traverse(Tree.root,out);out<<endl;return out;*/Menu類(lèi)：#include"BST.h"#inc

19、lude"SeqList.h"template<class T>class Menupublic:void BillsOfSearch(SeqList<T> &ob1,BinarySearchTree<T> &ob2);void InputNumber(SeqList<T> &ob1,BinarySearchTree<T> &ob2);void OutputNumber(SeqList<T> &ob1,BinarySearchTree<T> &

20、ob2);void SearchNumber(SeqList<T> &ob1,BinarySearchTree<T> &ob2);template<class T>void Menu<T>:BillsOfSearch(SeqList<T> &ob1,BinarySearchTree<T> &ob2)int choice;while(choice)cout<<endl;cout<<"n=n"cout<<"| 搜索選項(xiàng) |n&qu

21、ot;cout<<"=n"cout<<"1、輸入數(shù)據(jù)！n"cout<<"2、輸出數(shù)據(jù)！n"cout<<"3、搜索數(shù)據(jù)！n"cout<<"0、退 出！n"cout<<"請(qǐng)輸入你的選擇（輸入編號(hào)即可）："cin>>choice;switch(choice) case 1: InputNumber(ob1,ob2);break;case 2: OutputNumber(ob1,ob2);break;

22、case 3: SearchNumber(ob1,ob2);break;case 0: break;default:cout<<"輸入有誤！"break;template <class T>void Menu<T>:InputNumber(SeqList<T> &ob1,BinarySearchTree<T> &ob2) T number;int sign=1,i=0;while(sign)/循環(huán)建立有序表i+;cout<<"請(qǐng)輸入第"<<i<<

23、;"個(gè)數(shù)據(jù)：(輸入0停止)"cin>>number;if(number=0)int choose=1;while(choose)cout<<"0是否為要輸入的數(shù)？（1、是；0、不是。）"cin>>choose;switch(choose) case 1:ob1.Insert(number);ob2.Insert(number);choose=0;break; case 0:sign=0;break; default:cout<<"輸入選擇有誤，請(qǐng)重新選擇！"<<endl;br

24、eak;/*if(choose=1) ob1.Insert(number);/建立有序表ob2.Insert(number);/建立二叉搜索樹(shù)choose=0;else if(choose=0)sign=0;elsecout<<"輸入選擇有誤，請(qǐng)重新選擇！"<<endl;*/elseob1.Insert(number);/建立有序表ob2.Insert(number);/建立二叉搜索樹(shù)/*for(int j=0;j<ob1.Length();j+)number1=ob1.GetNumber(j);ob2.Insert(number1);/將建立

25、的順序表轉(zhuǎn)換為二叉搜索樹(shù)*/template<class T>void Menu<T>:OutputNumber(SeqList<T> &ob1,BinarySearchTree<T> &ob2)int choose;while(choose)cout<<endl;cout<<"n=n"cout<<"| 輸出選項(xiàng) |n"cout<<"=n"cout<<"|1、順序表輸出！|n"cout<

26、<"|2、二叉搜索樹(shù)輸出！|n"cout<<"|0、退 出！|n"cout<<"請(qǐng)輸入你的選擇："cin>>choose;switch(choose) case 1:ob1.Output();break;case 2:ob2.Traverse(cout);break;case 0:break;default:cout<<"輸入有誤！"break;/*if(choose=1)ob1.Output();else if(choose=2)ob2.Traverse(cout);elsecout<<"輸入有誤！"<<endl;*/template<class T>void Menu<T>:SearchNumber(SeqList<T> &ob1,BinarySearchTree<T> &ob2)int choose;T x;cout<<"請(qǐng)輸入你要查找的數(shù)："cin>>x;while(choose)cout<<