數(shù)據(jù)結(jié)構(gòu)查找技術(shù)驗(yàn)證實(shí)驗(yàn)報(bào)告

1、班級：計(jì)算機(jī)11-2學(xué)號：40姓名：朱報(bào)龍成績：實(shí)驗(yàn)十查找技術(shù)驗(yàn)證實(shí)驗(yàn)一、折半查找驗(yàn)證1. 實(shí)驗(yàn)?zāi)康恼莆照郯氩檎宜惴ǖ幕舅枷?；掌握折半查找算法的?shí)現(xiàn)方法；掌握折半查找算法的時(shí)間性能。2. 實(shí)驗(yàn)內(nèi)容對給定的有序數(shù)組（假設(shè)長度為n）,查找數(shù)組中與給定值k相等的元素設(shè)計(jì)與編碼#include<iostream>usingnamespacestd;#defineN15/定義常量N為數(shù)組長度voidfind(intarr,intkey,inti)/折半查找函數(shù)intlow=0,high=N-1,mid,j=0;/j計(jì)數(shù)查找次數(shù)while(low<=high)mid=(low+high

2、)/2;/取中間位+j;printf("n第%2d次查找low=%2dhigh=%2dmid=%2d",j,low,high,mid);/顯示每次查找低中高位，查找次數(shù)if(arrmid=key)/查到數(shù)據(jù)，跳出循環(huán)break;if(arrmid<key)查找的KEY大于中位值，查后半部low=mid+1;elsehigh=mid-1;查找的KEY小于中位值，查前半部if（low<=high）/查到數(shù)據(jù)printf（"nn經(jīng)過總共%2d次查找，找到該數(shù)字，該數(shù)字位于數(shù)組第%d位,nn",j,mid+1）;/顯示查到的數(shù)據(jù)的值，下標(biāo)值，總查找次

3、數(shù)elseprintf("nn沒有找到!");/顯示沒有找到voidmain()intarrN,key,i;printf("n齊干查找驗(yàn)證程序，設(shè)定被查數(shù)據(jù)有位，設(shè)定為：n");for(i=0;i<N;i+)輸入15個(gè)排好序的數(shù)據(jù)arri=i+1;printf("%d",arri);printf("n請輸入要查詢的數(shù)字(-,輸入小于等于零的數(shù)字退出驗(yàn)證程序)：")；scanf("%d”,&key);/輸入KEYwhile(key>0)find(arr,key,N);/調(diào)用折半查找函數(shù)p

4、rintf("n請輸入要查詢的數(shù)字(-,輸入小于等于零的數(shù)字退出驗(yàn)證程序)：")；scanf("%d”,&key);/輸入KEYa)程序運(yùn)行的結(jié)果如何？F:hengxuOD?bug曲瞼10.exe折半查找監(jiān)證程序I設(shè)定被查數(shù)據(jù)有位,設(shè)定為：12345678J1011121315請輸入要查詢的數(shù)字(->輸入小于等于零的數(shù)字正出會證程序):5第優(yōu)言濡?1口皿=0high=14mid=7第2次杳二,low=0high=6mid=3第？次亙泣loJ=4high=6mid=5第4次查比lou"4high-4mid-4經(jīng)過總共屯次查找，找到該數(shù)字，該數(shù)

5、字位于數(shù)組第寫位.請輸入要查詢的數(shù)字(-.輸入小于等于零的數(shù)字退出驗(yàn)證程序);二、二叉排序樹的建立1.實(shí)驗(yàn)?zāi)康恼莆斩媾判驑涠x和特性;掌握二叉排序樹的建立方法;實(shí)現(xiàn)基于二叉排序樹的查找技術(shù);掌握二叉排序樹的查找性能。2.實(shí)驗(yàn)內(nèi)容對給定的一組無序序列，建立一棵二叉排序樹；對建立的二叉排序樹實(shí)現(xiàn)查找操作。二、設(shè)計(jì)與編碼#include<iostream>usingnamespacestd;classBTpublic:BT(void)/構(gòu)造函數(shù)voidInitBiTree(BiTree*t);cout<<"初始化結(jié)束！n"/存儲結(jié)構(gòu)二叉鏈表typedef

6、structLnodeintkey;structLnode*lchild,*rchild;BiTnode,*BiTree;/創(chuàng)建、初始化voidInitBiTree(BiTree*t)*t=NULL;/置空/輸出中序遍歷二叉樹voidInorderBiTree(BiTreep)if(p)/p為空，則空操作，否則繼續(xù)執(zhí)行InorderBiTree(p->lchild);cout<<p->key<<""InorderBiTree(p->rchild);/查找數(shù)據(jù)BiTreeSearchBST(BiTreet,intk)BiTreep;p

7、=t;while(p!=NULL)&&(p->key!=k)if(k<p->key)p=p->lchild;elsep=p->rchild;return(p);-可編輯修改-/插入數(shù)據(jù)voidInsertBST(BiTree*t,intk)BiTnode*f,*p=*t;while(p)if(p->key=k)return;f=p;p=(k<p->key)?p->lchild:p->rchild;p=(BiTree)malloc(sizeof(BiTnode);p->key=k;p->lchild=p-&g

8、t;rchild=NULL;if(*t=NULL)*t=p;elseif(k<f->key)f->lchild=p;else/ 在二叉排序樹*t 中刪除關(guān)鍵字為k 的結(jié)點(diǎn)BT()cout<<" 調(diào)用析構(gòu)函數(shù)釋放!"<<endl;/ 析構(gòu)private:;/class BT int main()f->rchild=p;BTbt;/classBT創(chuàng)建對象btBT:BiTreet=NULL,p;intkey,q=1;bt.InitBiTree(&t);cout<<"請輸入關(guān)鍵字的值,以0結(jié)束:"

9、;<<endl;cin>>key;while(key)bt.InsertBST(&t,key);cin>>key;cout<<"中序遍歷建立的二叉排序樹的序列為:"-可編輯修改-bt.InorderBiTree(t);cout<<endl;cout<<"請輸入要插入的結(jié)點(diǎn)的關(guān)鍵字的值cin>>key;bt.InsertBST(&t,key);cout<<"插入后的二叉排序樹的中序序列為bt.InorderBiTree(t);cout<<endl;cout<<"請輸入要查找的結(jié)點(diǎn)的關(guān)鍵字的值cin>>key;p=bt.SearchBST(t,key);if(p=NULL)cout<<"沒有查找到該結(jié)點(diǎn)"<<endl;elsecout<<"查找到該結(jié)點(diǎn):":"<<endl;:"<<endl;:"<<endl;cout<<p->key<<e