pingheng.rar_数据结构 课程 设计报告

#include<stdio.h> #include<conio.h> #include<math.h> #define TRUE 1 #define FALSE 0 #define LH 1 #define EH 0 #define RH -1 struct BST { int data; int bf; struct BST *lchild; struct BST *rchild; }; struct DL { struct BST *data; struct DL *next; }; struct DLZZ { struct DL *front; struct DL *rear; }; int taller=0; int a[100],b[100],d=0,e=0; struct BST zero= { 0, 0, NULL, NULL, }; /******************************函数说明*****************************/ void CreateBST(struct BST **T); void insertBST(struct BST **T,int key); void CreateAVL(struct BST **T); void InsertOneToAVL(struct BST **T); void insertAVL(struct BST **T, int key); struct BST *l_balance(struct BST *T); struct BST *r_balance(struct BST *T); struct BST *r_rotate(struct BST *T); struct BST *l_rotate(struct BST *T); void InOrderTraverse(struct BST **T); void PreOrderTraverse(struct BST **T); void show(int *a,int *b); void show1(int *a,int *b); void height(struct BST **T); void save(struct BST **T,int *order); void InitQueue(struct DLZZ *Q); void EnQueue(struct DLZZ *Q,struct BST *e); void DeQueue(struct DLZZ *Q,struct BST **e); /**********************************主函数**************************/ void main(void) { struct BST *T; int k,flag=1; char *menu[]= { "1:CreateBST\n", "2:CreateAVL\n", "3:InsertOneToAVL\n", "4:InOrderTraverse\n", "5:PreOrderTraverse\n", "6:height\n", "0:Exit\n", "\nSelect[0-6]:" }; window(41,1,80,10); /*右边窗口为青色背景*/ textbackground(CYAN); textcolor(WHITE); clrscr(); window(41,11,80,25); textbackground(GREEN); textcolor(WHITE); clrscr(); gotoxy(5,6); printf("Hust Computer S&T C 0614 HeKai"); gotoxy(5,8); printf("Number:012006015113"); gotoxy(5,10); printf("2008.7.21"); window(1,1,40,25); /*左边窗口为兰色背景*/ textbackground(BLUE); textcolor(WHITE); clrscr(); T=NULL; while(flag) { clrscr(); for (k=0;k<=7;k++) printf ("%s",menu[k]); scanf("%d",&k); switch(k) { case 1: clrscr(); CreateBST(&T); getch(); break; case 2: clrscr(); CreateAVL(&T); getch(); break; case 3: clrscr(); InsertOneToAVL(&T); getch(); break; case 4: clrscr(); InOrderTraverse(&T); getch(); break; case 5: clrscr(); PreOrderTraverse(&T); getch(); break; case 6: clrscr(); d=0; e=0; height(&T); printf("Hight is %d",e); getch(); break; case 0: flag=0; break; } } } /***********************************创建二叉排序树***************/ void CreateBST(struct BST **T) /*新建二叉排序树*/ { int key,i; *T=NULL; for(i=0;i<100;i++) /*数组清零*/ { a[i]=0; b[i]=0; } printf("Input one data:"); /*提示输入数据结点*/ scanf("%d",&key); while(key!=0) /*输入的不是回车时*/ { d=0; e=0; height(T); save(T,b); insertBST(T,key); d=0; e=0; height(T); save(T,a); show(a,b); getch(); show1(a,b); window(1,1,40,25); textbackground(BLUE); clrscr(); printf("Input next one:"); scanf("%d",&key); } } /*********************************插入二叉排序树数据*********************/ void insertBST(struct BST **T,int key) { struct BST *p,*q; p=*T; while(p) { if(p->data==key) { printf("The data is exist!Input again!\n"); return; } q=p; if(key<p->data) p=p->lchild; else p=p->rchild; } p=(struct BST *)malloc(sizeof(struct BST)); p->data=key; p->lchild=p->rchild=NULL; if(*T==NULL) *T=p; /*被插结点*p为新的根结点*/ else if(key<q->data) q->lchild=p; /*被插结点为左孩子*/ else q->rchild=p; /*被插结点为右孩子*/ } /***********************************创建平衡二叉树********************/ void CreateAVL(struct BST **T) { int key,i; struct BST *p; *T=NULL; /*置零处理*/ for(i=0;i<100;i++) /*数组清零*/ { a[i]=0; b[i]=0; } printf("Input one data:"); scanf("%d",&key); while(key!=0) /*关键字不为回车时*/ { d=0; e=0; height(T); save(T,b); insertAVL(T,key); d=0; e=0; height(T); save(T,a); show(a,b); getch(); show1(a,b); window(1,1,40,25); textbackground(BLUE); clrscr(); printf("Input next one:"); scanf("%d",&key); } } /***********************************插入一个数据到平衡二叉树************/ void InsertOneToAVL(struct BST **T) { int key; struct BST *p; if(*T==NULL) { printf("No AVL!CreateAVL first!\n"); return; } printf("Input next one:"); scanf("%d",&key); while(key!=0) /*关键字不为回车时*/ { d=0; e=0; height(T); save(T,b); insertAVL(T,key); d=0; e=0; height(T); save(T,a); show(a,b); getch(); show1(a,b); window(1,1,40,25); textbackground(BLUE); clrscr(); printf("Input next one:"); scanf("%d",&key); } } /**********************************插入平衡二叉树数据*********************/ void insertAVL(struct BST **T, int key) /*插入元素结点*/ { struct BST *p; if(!*T) /*树为空时*/ { *T=(struct BST *)malloc(sizeof(struct BST)); (*T)->data=key; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=0; taller=TRUE; } else { if(key==(*T)->data) /*插入关键字已经存在时*/ { taller=FALSE; printf("The data is exist!Input again!\n"); return; } if(key<(*T)->data) /*插入值小于根结点关键字时*/ { insertAVL(&(*T)->lchild,key); /*在其左子树中搜索*/ if(taller) switch((*T)->bf) { case LH: /*调整，保持其平衡性*/ (*T)=l_balance(*T); taller=FALSE; break; case EH: (*T)->bf=LH; taller=TRUE; break; case RH: (*T)->bf=EH; taller=FALSE; break; } } else /*插入值大于根结点关键字时*/ { insertAVL(&(*T)->rchild,key); if(taller) { switch((*T)->bf) { /*调整保持其平衡性*/ case LH: (*T)->bf=EH; taller=FALSE; break; case EH: (*T)->bf=RH; taller=TRUE; break; case RH: (*T)=r_balance(*T); taller=FALSE; break; } } } } } /************************************左平衡函数************************/ struct BST *l_balance(struct BST *T) /*调整左平衡函数*/ { struct BST *lc,*rd; lc=T->lchild; switch(lc->bf) /*根据平衡因子调整*/ { case LH: T->bf=lc->bf=EH; T=r_rotate(T); break; case RH: rd=lc->rchild; switch(rd->bf) /*分情况解决平衡问题*/ { case LH: T->bf=RH; lc->bf=EH; break; case EH: T->bf=lc->bf=EH; break; case RH: T->bf=EH; lc->bf=LH; break; } rd->bf=EH; T->rchild=l_rotate(T->lchild); T=r_rotate(T); } return T; } /**************************************右平衡函数********************/ struct BST *r_balance(struct BST *T) /*调整右平衡函数*/ { struct BST *rc,*ld; rc=T->rchild; switch(rc->bf) { /*根据平衡因子调整*/ case RH: T->bf=rc->bf=EH; T=l_rotate(T); break; case LH: ld=rc->lchild; switch(ld->bf) /*分情况解决平衡问题*/ { case LH: T->bf=LH; rc->bf=EH; break; case EH: T->bf=rc->bf=EH; break; case RH: T->bf