大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)——查找算法地實(shí)現(xiàn)

《大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)——查找算法地實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、實(shí)用標(biāo)準(zhǔn)文案實(shí)驗(yàn)五查找算法實(shí)現(xiàn)精彩文檔實(shí)用標(biāo)準(zhǔn)文案1、實(shí)驗(yàn)?zāi)康氖炀氄莆枕樞虿檎?、折半查找及二叉排序?shù)、平衡二叉樹(shù)上的查找、插入和刪除的方法，比較它們的平均查找長(zhǎng)度。2、問(wèn)題描述查找表是數(shù)據(jù)處理的重要操作，試建立有100個(gè)結(jié)點(diǎn)的二叉排序樹(shù)進(jìn)行查找，然后用原數(shù)據(jù)建立AVL樹(shù)，并比較兩者的平均查找長(zhǎng)度。3、基本要求（1）以鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉排序樹(shù)的建立、查找和刪除。（2）根據(jù)給定的數(shù)據(jù)建立平衡二叉樹(shù)。4、測(cè)試數(shù)據(jù)隨即生成5、源程序#include#include#include#def

2、ineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)>(b))typedefintKeytype;typedefstruct{Keytypekey;//關(guān)鍵字域}ElemType;typedefstructBSTnode{ElemTypedata;intbf;structBSTnode*lchild,*rchild;}BSTnode,*BSTree;voidInitBSTree(BSTree&T){T=NULL;}voidR_Rotate(BSTree&p){BSTnode*lc;

3、lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}voidL_Rotate(BSTree&p){BSTnode*rc;rc=p->rchild;p->rchild=rc->lchild;精彩文檔實(shí)用標(biāo)準(zhǔn)文案rc->lchild=p;p=rc;}voidLeftbalance(BSTree&T){BSTnode*lc,*rd;lc=T->lchild;switch(lc->bf){case+1:T->bf=lc->bf=0;R_Rotate(T);break;case-1:rd=lc->rchil

4、d;switch(rd->bf){case1:T->bf=-1;lc->bf=0;break;case0:T->bf=lc->bf=0;break;case-1:T->bf=0;lc->bf=1;break;}rd->bf=0;L_Rotate(T->lchild);R_Rotate(T);}}voidRbalance(BSTree&T){BSTnode*lc,*ld;lc=T->rchild;switch(lc->bf){case1:ld=lc->lchild;switch(ld->bf){case1:T->bf=0;lc->bf=-1;break

5、;case0:精彩文檔實(shí)用標(biāo)準(zhǔn)文案T->bf=lc->bf=0;break;case-1:T->bf=1;lc->bf=0;break;}ld->bf=0;R_Rotate(T->rchild);L_Rotate(T);case-1:T->bf=lc->bf=0;L_Rotate(T);break;}}intInsertAVL(BSTree&T,ElemTypee,bool&taller){if(!T){T=(BSTree)malloc(sizeof(BSTnode));T->data=e;T->lchild=T->rchild=NULL;T->bf

6、=0;taller=true;}else{if(EQ(e.key,T->data.key)){taller=false;cout<<"結(jié)點(diǎn)"<data.key)){if(!InsertAVL(T->lchild,e,taller)){return0;}if(taller)switch(T->bf){case1:Leftbalance(T);taller=false;break;case0:T->bf=+1;taller=true;break;精彩文檔實(shí)用標(biāo)準(zhǔn)文案

7、case-1:T->bf=0;taller=false;break;}}else{if(!InsertAVL(T->rchild,e,taller)){return0;}if(taller)switch(T->bf){case1:T->bf=0;taller=false;break;case0:T->bf=-1;taller=true;break;case-1:Rbalance(T);taller=false;break;}}}return1;}boolSearchBST(BSTreeT,ElemTypekey,BSTreef,BSTree&p){i

8、f(!T){p=f;cout<<"結(jié)點(diǎn)不存在。"<