1、数据结构实验查找算法的实现实验五查找算法实现1、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法,比较它们的平均查找长度。2、问题描述查找表是数据处理的重要操作, 试建立有100个结点的二叉排序树进行查找,然后用原数据建立AVL树, 并比较两者的平均查找长度。3、基本要求(1)以链表作为存储结构,实现二叉排序树的建立、查找和删除。(2)根据给定的数据建立平衡二叉树。4、测试数据随即生成5、源程序#include#include#include#define EQ(a,b) (a)=(b) #define LT(a,b) (a)(b)typedef int K
2、eytype;typedef struct Keytype key; /关键字域ElemType;typedef struct BSTnode ElemType data; int bf; struct BSTnode *lchild,*rchild; BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p)BSTnode *lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc; void L_Rotate(BSTree &p)BSTnode *rc
3、; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc; void Leftbalance(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-rchild; switch(rd-bf) case 1: T-bf=-1; lc-bf=0; break; case 0: T-bf=lc-bf=0; break; case -1: T-bf=0; lc-bf=1; break;
4、rd-bf=0; L_Rotate(T-lchild); R_Rotate(T); void Rbalance(BSTree &T)BSTnode *lc,*ld; lc=T-rchild; switch(lc-bf) case 1: ld=lc-lchild; switch(ld-bf) case 1: T-bf=0; lc-bf=-1; break; case 0: 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-
5、bf=0; L_Rotate(T); break; int InsertAVL(BSTree &T,ElemType e,bool &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结点 e.key 不存在。data.key) if(!InsertAVL(T-lchild,e,taller) return 0; if(taller) switc
6、h(T-bf) case 1: Leftbalance(T); taller=false; break; case 0: T-bf=+1; taller=true; break; case -1: T-bf=0; taller=false; break; else if(!InsertAVL(T-rchild,e,taller) return 0; if(taller) switch(T-bf) case 1: T-bf=0; taller=false; break; case 0: T-bf=-1; taller=true; break; case -1: Rbalance(T); tall
7、er=false; break; return 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T) p=f; cout结点不存在。data.key) ) p=T; cout查找成功,存在结点; coutdata.keydata.key) return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p);void Leftbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-b
8、f=+1) /p结点的左子树高,删除结点后p的bf减1,树变矮 p-bf=0; shorter=1; else if(p-bf=0)/p结点左、右子树等高,删除结点后p的bf减1,树高不变 p-bf=-1; shorter=0; else p1=p-rchild;/p1指向p的右子树 if(p1-bf=0)/p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理,树高不变 L_Rotate(p); p1-bf=1; p-bf=-1; shorter=0; else if(p1-bf=-1)/p1的右子树高,左旋处理后,树变矮 L_Rotate(p); p1-bf=p-bf=0; sho
9、rter=1; else p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=-1) p-bf=+1; p1-bf=0; else p-bf=0; p1-bf=-1; p2-bf=0; p=p2; shorter=1; void Rbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=-1) p-bf=0; shorter=1; else
10、 if(p-bf=0) p-bf=+1; shorter=0; else p1=p-lchild; if(p1-bf=0) R_Rotate(p); p1-bf=-1; p-bf=+1; shorter=0; else if(p1-bf=+1) R_Rotate(p); p1-bf=p-bf=0; shorter=1; else p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=1) p-bf=-
11、1; p1-bf=0; else p-bf=0; p1-bf=1; p2-bf=0; p=p2; shorter=1; void Delete(BSTree q,BSTree &r,int &shorter) if(r-rchild=NULL) q-data=r-data; q=r; r=r-lchild; free(q); shorter=1; else Delete(q,r-rchild,shorter); if(shorter=1) Rbalance_div(r,shorter); ElemType DeleteAVL(BSTree &p,ElemType key,int &shorte
12、r) ElemType k,a,b; a.key=1; b.key=0; BSTree q; if(p=NULL) cout结点不存在。data.key) )/在p的左子树中进行删除 k=DeleteAVL(p-lchild,key,shorter); if(shorter=1) Leftbalance_div(p,shorter); return k; else if(LQ(key.key,p-data.key) )/在p的右子树中进行删除 k=DeleteAVL(p-rchild,key,shorter); if(shorter=1) Rbalance_div(p,shorter); re
13、turn k; else q=p; if(p-rchild=NULL) /右子树空则只需重接它的左子树 p=p-lchild; free(q); shorter=1; else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild; free(q); shorter=1; else Delete(q,q-lchild,shorter); if(shorter=1) Leftbalance_div(p,shorter); p=q; return a; void Print_BSTTree(BSTree T,int i) if(T) if(T-rchild) Pr
14、int_BSTTree(T-rchild,i+1); for(int j=1;j=i;j+) cout ; coutdata.keylchild) Print_BSTTree(T-lchild,i+1); int main() BSTree T; ElemType e; InitBSTree(T); bool tall=false; bool choice=true; char y; while(choice) coute.key; InsertAVL(T,e,tall); Print_BSTTree(T,0); couty; if(y=Y|y=y) choice=true; else choice=false; BSTree f,p; choice=true; while(choice) coute.key; SearchBST( T,e,f,p); couty; if(y=Y|y=y) choice=true; else choice=false; int shorter; choice=true; while(choice) coute.key; DeleteAVL(T,e,shorter); Print_BSTTree(T,0); couty; if(y=Y|y=y) choice=true; else choice=false; return 0;
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2