2023年搜索實(shí)驗(yàn)報告

重慶交通大學(xué)

設(shè)計(jì)性實(shí)驗(yàn)報告

班級：計(jì)軟2班

學(xué)號:—姓名：舊城余約

實(shí)驗(yàn)項(xià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)完畢時間：2023年5月20日

教師評閱意見：

署名：年月日

重驗(yàn)成績：

一、實(shí)驗(yàn)?zāi)康?/p>

應(yīng)用線性結(jié)構(gòu)、樹形結(jié)構(gòu)實(shí)現(xiàn)查找。

二、實(shí)驗(yàn)內(nèi)容及規(guī)定

內(nèi)容：

1）有序表的二分查找；

2）二叉排序樹的查找。

規(guī)定：

1）建立有序表，然后進(jìn)行二分查找；

2）建立二叉排序樹，然后查找。

三、實(shí)驗(yàn)設(shè)備及軟件

設(shè)備:計(jì)算機(jī)；

軟件：visualC++6.0

四、實(shí)驗(yàn)過程及環(huán)節(jié)

運(yùn)營環(huán)境:visualC++6.0;

實(shí)現(xiàn)思緒：一方面，是有序表的書寫,是在順序表的基礎(chǔ)上用有序插入控制數(shù)據(jù)

的有序輸入，從而建立有序表,為后面的二分法查找數(shù)據(jù)做準(zhǔn)備。順序

表的數(shù)據(jù)成員中，用*element來存儲數(shù)據(jù),MaxSize表達(dá)最大存儲空

間，length表達(dá)當(dāng)前存儲長度；在成員函數(shù)中，voidInsert(T&x)

用來有序插入數(shù)據(jù)建立有序表，每次插入數(shù)據(jù)前都要與已有數(shù)據(jù)進(jìn)行比

較大小，從而擬定插入位置，同時voidSearch(T&x)用來二分

法查找數(shù)據(jù)，先定義兩個起始位置和末位置的變量以及一個中間位置的

變量,每次用要查找的數(shù)與中間位置的數(shù)據(jù)進(jìn)行比較，假如小則末位置

為中間位置加一，反之起始位置為中間位置減一；

然后，是二分排序樹的書寫，有二叉樹結(jié)點(diǎn)BinaryTreeNode,涉

及數(shù)據(jù)域data,左子樹指針leftChild以及右子樹指針rightChild；在

BinarySearchTree中用voidInsert(T&x,BinaryT

reeNode<T>*&ptr)函數(shù)進(jìn)行建立二叉樹，比根數(shù)據(jù)小的存在左子樹,

比根大的存在右子樹，用BinaryTreeNode<T>*Find(Tx,Binar

yTreeNode<T>*ptr)進(jìn)行搜索查找，用遞歸算法進(jìn)行實(shí)現(xiàn)，要查找的

數(shù)比根數(shù)小，往左子樹遞歸，反之，往右子樹遞歸。

最后，用菜單進(jìn)行實(shí)現(xiàn).

編譯環(huán)節(jié):在寫類的時候，逐個函數(shù)進(jìn)行測試。

五、重要代碼及運(yùn)營結(jié)果

(一)、重要代碼：

SeqList類：

#include<assert.h>

template<classT>

classSeqList

(

oprivate:

6T*element;

0intMaxSize;

^intlength;

叩ub1ic:

oSeqList(intMaxListSize=10);

o~SeqList()

(

f(element)

。elete[]element;

boo1IsEmpty()

o{return1ength==0;}

intLength()

o{returnlength;}

aboo1Find(inti,T&x);//將第i個元素的值用x返回

。SeqList<T>Delete(inti,T&x);//刪除第i個元素，并返回x的值

。。voidSearch(T&x);〃二分法搜索函數(shù)

ovoidInsert(T&x);//有序插入建立有序表

woidOutput();

。TGetNumber(inti)

{returnelement[i]；}

)；

temp1ate<c1assT>

SeqList<T>：:SeqList(intMaxListSize)

(

MaxSize=MaxListSize;

element=newTfMaxSize];

1ength=O;

temp1ate<classT>

boo1SeqList<T>：：Find(inti,T&x)

(

oif(i<l||i>length)

8returnfalse；

?else

(

ex二e1ement[i-1];

returntrue;

°)

)

temp1ate<classT>

voidSeqList<T>：:Search(T&x)

(

?inthigh=length;

int1ow=0;

“ntmid;

while(low<=high)

(

omid=(1ow+high)/2；

ooif(x>e1ement[mid])

ow=mid+1;

eelseif(x<element[mid])

high=mid—1;

oelseif(x==e1ement[mid])

woutVv”查找成功!”<vend1;

。cout?mid+1；

。。break;。

}

°)

if(x!=element[midd==1ow||mid==high))

。cout<<"查找失敗"V<end1;

)

template<c1assT>

voidSeqList<T>::0utput()

(

for(inti=0;i<length;i++)

cout?e1ementli]?nM；

}

tempiate<c1assT>

voidSeqList<T>：:Insert(T&x)〃有序插入函數(shù)

(

inti=0;

owhile(i<length&&element[iJ<=x)//比較

i++；

。for(intj=length;j>i;j--)〃有序插入

elementfj]=elemen

^element[i]=x；

。1ength++;

)

BinarySearchTree類：

#include<iostream>

usingnamespacestd;

template<classT>

classBinarySearchTree;

template<classT>

classBinaryTreeNode

(

protected:

Tdata；

BinaryTreeNode<T>*1eftChild,*rightChi1d;

public:

o//BinaryTreeNode()：1eftChi1d(NULL),rightChild(NULL){}//構(gòu)造函數(shù)

//BinaryTreeNode(Td):data(d),leftChild(NULL),rightChiId(NULL){)

〃構(gòu)造函數(shù)

BinaryTreeNode(Td=0,BinaryTreeNode*L=NULL,BinaryTreeNode

*R=NULL):data(d),leftChi1d(L),rightChi1d(R){}//構(gòu)造函數(shù)

?BinaryTreeNode()

°(

。if(1eftChild)

^deleteleftChild;

。if(rightChild)

deleterightChiId;

°)

TGetData()

{returndata;}

ofriendclassBinarySearchTree<T>;

)；

template<classT>

classBinarySearchTree

(

private:

BinaryTreeNode<T>*root;//二叉搜索樹的根指針

oTstopvalue;〃數(shù)據(jù)輸入停止標(biāo)志，用于輸入

woidInsert(T&x,BinaryTreeNode<T>*&ptr)；〃插入

。BinaryTreeNode<T>*Find(Tx,BinaryTreeNode<T>*ptr);//查找

voidTraverse(ostream&out,BinaryTreeNode<T>*subTree)，前序遍歷輸

出

pub1ic:

BinarySearchTree()：root(NULL){}〃構(gòu)造函數(shù)

inarySearchTree(Tva1ue):stopvalue(value),root(NULL){}//構(gòu)造函數(shù)

o~BinarySearchTree()

°(

if(root)

^deleteroot;

。}//析構(gòu)函數(shù)

ointFind(Tx)

{returnFind(x,root)!=NULL;)//查找

oidInsert(T&x)

{Insert(x,root);)〃插入新元素

voidTraverse(ostream&out)

{Traverse(out,root);}

temp1ate<classT>

BinaryTreeNode<T>*BinarySearchTree<T>：:Find(Tx,BinaryTreeNode<

T>*ptr)//二叉排序樹的遞歸查找算法

(

oif(ptr==NULL)

。{

。cout<<”搜索失敗!”《end1;

returnNULL;〃搜索失敗

}

eIseif(x<ptr->data)

“returnFind(x,ptr->leftChild);//在左子數(shù)查找

elseif(x>ptr->data)

阿eturnFind(x,ptr->rightChi1d)；//在右子數(shù)查找

?else

°{

ecoutvV”搜索成功！"vvendl；

returnptr;//相等，搜索成功

)

)

template<classT>

voidBinarySearchTree<T>:：Insert(T&x,BinaryTreeNode<T>*&ptr)

(

°if(ptr==NULL)//新節(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入

°{

。ptr=newBinaryTreeNode<T>(x)；〃創(chuàng)建新節(jié)點(diǎn)

“if(ptr==NULL)

。{cout<v”內(nèi)存局限性！”<Vend1;exit(1)；)

)

elseif(x<ptr—>data)

^Insert(x,ptr->leftChild)；//小于等于根的關(guān)鍵字，向左子樹插入

。//我不清楚和根相等的關(guān)鍵字往哪里存

elseif(x>ptr->data)

^Insert(x,ptr—>rightChild);〃大于根的關(guān)鍵字,向右子數(shù)插入

)

/*template<classT>

voidBinarySearchTree<T>：:Remove(constT&x,BinaryTreeNode<T>*

&ptr)

(

BinaryTreeNode<T>%emp;

if(ptr!=NULL)

"if(x<ptr->data)

。Remove(x,ptr->leftChild);

?elseif(x>ptr->data)

3Remove(x,ptr—>rightChi1d)；

eIseif(ptr->leftChild!=NULL&&ptr->rightChild!=NULL)

(

etemp=Min(ptr->rightChi1d);

。。ptr—>data=temp—>data;

?Remove(ptr->data,ptr->rightChild);

}

?>e1se

。｛

。。01emp=ptr；

“if(ptr->leftChild==NULL)

。ptr=ptr—>rightChild；

oe1seif(ptr—>leftChild==NULL)

。optr=ptr->leftChild;

。deleteternp;

。｝

)*/

temp1ate<classT>

voidBinarySearchTree<T>::Traverse(ostream&out,BinaryTreeNode<T>

*subTree)//私有函數(shù):搜索并輸出根為subTree的二叉樹

(

if(subTree!=NULL)

6｛

^out<<subTree->data<<z〃輸出subTree的數(shù)值

ooTraverse(out,subTree->1eftChi1d)；//遞歸搜索并輸出subTree的左子樹

。Traverse(out,subTree->rightChi1d)；〃遞歸并輸出subTree的右子樹

)

)

/"tempiate<classT>

ostream&operator?(ostream&out,BinarySearchTree<T>&Tree)

(

Tree.Traverse(Tree.root,out)；

oout?end1;

^returnout;

}*/

Menu類：

#includeHBST.h"

#inc1ude"SeqList.h

template<c1assT>

classMenu

pub1ic:

voidBillsOfSearch(SeqList<T>&obl,BinarySearchTree<T>&ob2);

voidInputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2);

?voidOutputNumber(SeqList<T>&obl,BinarySearchTree<T>&ob2);

woidSearchNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2)；

)；

tempiate<classT>

voidMenu<T>:：BillsOfSearch(SeqList<T>&obl,BinarySearchTree<T>&

ob2)

(

“ntchoice；

whi1e(choice)

0(

cout<<endl;

℃out<^<n================—=============\n"；

^cout?uI搜索選項(xiàng)|\nM；

0co—二=二=============二—=—=—===—=\n"；

°c?*~1、輸入數(shù)據(jù)!~~~~1??~~\n";

ecout?”~?--------2、輸出數(shù)據(jù)!~~---------\n";

。cout<<*,~~~一??3、搜索數(shù)據(jù)!?^??~~\n"；

ocoutw"???/"^O、出!???????^^?\n*

cout<<”請輸入你的選擇(輸入編號即可):";cin?choice;

switch(choice)

00|

case1：InputNumber(obl,ob2);break;

。ecase2：OutputNumber(obl,ob2);break;

“case3：SearchNumber(ob1,ob2);break;

?case0:break;

3default：coutvv”輸入有誤!”；break;。

00|

}

)

temp1ate<classT>

voidMenu<T>：:InputNumber(SeqList<T>&ob1,BinarySearchTree<T>

&ob2)

(

Tnumber；

intsign=1,i=0;

owhi1e(sign)//循環(huán)建立有序表

。{

oi++;

3C0ut?”請輸入第1?i?”個數(shù)據(jù)：(輸入0停止)”;cin?number;

if(number==0)

00

ogintchoose=l;

DAWhi1e(choose)

0{

。ecout<<”0是否為要輸入的數(shù)？(1、是；0、不是。)*';cin?choose;

。aswitch(choose)

001

。。case1:obl.Insert(number);ob2.1nsert(number)；choose=O;break;

。case0:sign=0;break；

。edefault:cout<<”輸入選擇有誤，請重新選擇！"<<endl；break;

0010

。。/*if(choose==l)

(

sb1.Insert(number);//建立有序表

。ob2.Insert(number);〃建立二叉搜索樹

。choose=0；

0d|o

8e1seif(choose==0)6

o?sign=0；

。aoe1se

g。。coutVv"輸入選擇有誤，請重新選擇!”《end1;

8e*/

匕)

)

eIse

00bLinsert(number);〃建立有序表。

ob2.Insert(number);//建立二叉搜索樹

。/*for(intj=0;j<obl.Length();j++)

(

wnumberl=obl.GetNumber(j);

ob2.Insert(numberl);//將建立的順序表轉(zhuǎn)換為二叉搜索樹

。}文/

)

template<c1assT>

voidMenu<T>::OutputNumber(SeqList<T>&ob1,BinarySearchTree<T>&ob2)

(

ointchoose;

owhile(choose)

{°

?cout?end1；

ocoutV<"\p=============================\n"；

ocout?'1I輸出選項(xiàng)|\n?

oocout?"==============================\nn；

oocout<<"I?--------1、順序表輸出!"---------|\n”;

ooco卜??一?2、二叉搜索樹輸出!~~~I\n?

oocout?n|----???0、退出！------

。cout<V”請輸入你的選擇:";cin>>choose??

switch(choose)

00casel:obl.Output();break;

case2:ob2.Traverse(cout);break；

■case0:break；

。efau1t:cout〈v"輸入有誤!”;break;o

if(choose==l)

obl.Output();

oeIseif(choose==2)

oob2.Traverse(cout);

eIse

ocout<<"輸入有誤!n?end1;*/

)

template<classT>

voidMenu<T>：:SearchNumber(SeqList<T>&ob1,BinarySearchTree<T>

&ob2)

(

?intchoose;

Tx;

coutVV”請輸入你要查找的數(shù):";cin>>x;

while(choose)

°(

?cout?endl;

C[[t____”?

。cout?"|搜索選項(xiàng)|\n";

3cout<<"=========—===============—==========\nu;

。cout?MI-------------1、順序表的二分法搜索!???I\n"；

cout?"一?~~~2、二叉搜索樹搜索！?|\n

cout出!|\n'\

cout<<"請輸入你的選擇：”;cin?choose;

?switch(choose)

3(

casekobl.Search(x);break;

。ecase2:ob2.Find(x);break;

wcase0:break；

edefault:couivv”輸入有誤！"；break?

0)

}

)

主函數(shù)：

#include<iostream>

#include"MENU.h"

usingnamespacestd;

intmain()

(

SeqList<double>ob1;

BinarySearchTree<double>ob2;

Menu<doub1e>ob;

oob.BiHsOfSearch(obi,ob2)；

areturn0；

)

（二）、運(yùn)營結(jié)果:

主菜單:

萩賽獲全

1、111

卜青輸入你的猴擇（輸入編號即

輸入數(shù)據(jù):

搜素選項(xiàng)

入

據(jù)

~數(shù)

據(jù)

教

、^-

、--

出^-

、^-

入

輸/

〈

擎

編

/號T)

、

一4□

刖

的1

八-

請

入r1

入>1

j第2

刖<

素4

r層-

請f

d入>3

入

第<2

刖r-

屏

八2-

請-

.入>1

一<

^入

第-

屏

跳

3r入-

請

入>1

一

數(shù)<4-4

入

刖

第

公4:-

請

入1:<>89

刖r-

入

第5H-

請

入

d1:劇<>74

刖i-

入

數(shù)r

第/-

誨5

d入S<>

入2

刖:H-

入

？--2

請>

人

屏<

Q第4

可r-

入1

展->

請

(入<

一

第8-