数据结构实验——查找算法的实现.doc

《数据结构实验——查找算法的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、ng.h>#defineEQ(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;}

3、voidR_Rotate(BSTree&p){BSTnode*lc;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->

4、bf=lc->bf=0;R_Rotate(T);break;case-1:rd=lc->rchild;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;switc

5、h(lc->bf){case1:ld=lc->lchild;switch(ld->bf){case1:T->bf=0;lc->bf=-1;break;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&

6、taller){if(!T){T=(BSTree)malloc(sizeof(BSTnode));T->data=e;T->lchild=T->rchild=NULL;T->bf=0;taller=true;}else{if(EQ(e.key,T->data.key)){taller=false;cout<<"结点"<data.key)){if(!InsertAVL(T->lchild,e,taller)){re

7、turn0;}if(taller)switch(T->bf){case1:Leftbalance(T);taller=false;break;case0:T->bf=+1;taller=true;break;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

8、->bf=-1;taller=true;break;case-1:Rbalance(T);taller=false;break;}}}return1;}boolSearchBST(BSTreeT,ElemTypekey,BSTreef,BSTree&p){if(!T){p=f;cout<<"结点不存在。"<data.key)){p=T;cout<<"查找成功，存在结点";co