pingheng.c

一个vc++环境下的数据结构的课程设计报告源代码

#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=EH;
     rc->bf=RH;
     break;
   }
   ld->bf=EH;
   T->rchild=r_rotate(T->rchild);
   T=l_rotate(T);
 }
 return T;
}
/*********************************旋转函数**************************/
struct BST *r_rotate(struct BST *T)                         /*右旋转函数*/
{
 struct BST *lc;
 lc=T->lchild;
 T->lchild=lc->rchild;