大数据结构实验——查找算法地实现

《大数据结构实验——查找算法地实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案实验五查找算法实现精彩文档实用标准文案1、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。2、问题描述查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。3、基本要求（1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。（2）根据给定的数据建立平衡二叉树。4、测试数据随即生成5、源程序#include#include#include#def

2、ineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)>(b))typedefintKeytype;typedefstruct{Keytypekey;//关键字域}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;精彩文档实用标准文案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:精彩文档实用标准文案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<<"结点"<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;精彩文档实用标准文案

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<<"结点不存在。"<