datastructure.c

编写了一个关于图的操作的应用程序

#include  <stdio.h>        /*头文件包含说明*/
#include  <stdlib.h>
#include  <string.h>
#include  <bios.h>
#include  <dos.h>
#include  <conio.h>

#define  maxvertex  100         /*常量说明*/
#define  stack_max  100
#define  stackincrement  10
#define LEFT 75
#define RIGHT 77
#define ENTER 28

struct gra *g;
struct vexqueue *que;           /*全局变量说明*/
struct gra2 *g2;
struct sqstack *s;
int liantong=0;
int shunxu[ maxvertex ],shunxu1=0;


int getkey ( );
void selectmenu ( void );
int subfungo ( );
int bioskey ( int cmd );
void wind ( int, int, int, int, int, int, int );
void selectmainmenu ( );
void wmainmenu ( );
void quit ( );
void initscreen ( );
void textcolor ( int );
void textbackground ( int );
void  creategra () ;
void  check(char *string,int ,int,int,int) ;
void getsgrade() ;
void dfstraverse();
void  bfstraverse();
void deletev() ;
void  toplogicalsort();
void qinping();

/*=====================结构体说明===================*/


/*$$$$$$$$$$$$$$$$$$用十字链表存储时所用结构体$$$$$$$$*/

typedef  struct  arcbox{
          int  tailvex;               /* 弧尾的位置  */
          int  headvex;               /* 弧头的位置  */
          struct  arcbox  *hlink;     /* 下一条弧尾的位置*/
          struct  arcbox  *tlink;     /* 下一个弧头的位置*/
          char  arcinfo[5];           /*  权值的信息  */
          }ARCBOX;
typedef  struct  vexnode{
          char  vex[5];              /*  顶点的值 */
          int   seamark;             /*  访问标志（访问过（1），未访问过（0））*/
          ARCBOX  *firstin;          /*  由顶点出发的第一条弧 */
          ARCBOX  *firstout;         /*  到顶点的第一条弧 */
          }VEXNODE;
typedef  struct  gra{
          VEXNODE  vexlist[maxvertex];/* 顶点结构体数组 */
          int  vexnum;                /* 顶点数*/
          int  arcnum;                /* 弧数 */
          }LGRAPH;

typedef  struct vexqueue{
         struct  vexposition *rear;   /* 队列头指针 */
         struct  vexposition *tail;   /* 队列尾指针 */
         }QUEUE;

typedef  struct vexposition{
         int position;                /* 顶点在顶点数组中的位置  */
         struct vexposition  *next;   /* 指向下一个定点位置的指针 */
         }Vexposition;

/*$$$$$$$$$$$$$$$$$$用邻接表存储时所用结构体$$$$$$$$*/

typedef struct  sqstack{
          struct vernode2 *top;       /* 堆栈的顶部  */
          struct vernode2 *base;     /*  栈底指针 */
          int  stacksize;
          }SQstack;

typedef struct arcnode2{
   int   position;                    /* 顶点在顶点数组中的位置 */
   struct  arcnode2 *nextarc;         /* 指向下一个定点位置的指针*/
   char  info[5];                     /*  权值的信息 */
   }Arcnode2;

typedef struct vernode2{
   char  value[5];                    /*  顶点的值 */
   int   vermark;                     /*  访问标志（访问过（1），未访问过（0））*/
   int  gradein;                      /*  入度值   */
   int  gradeout;                     /*  出度值  */
   struct arcnode2 *firstarc;         /*  由顶点出发的第一条弧的指针 */
}Vernode2;

typedef struct gra2{
   struct vernode2  verlist[maxvertex];/*  顶点结构体数组*/
   int  vernum;                        /*  顶点数 */
   int  arcnum;                        /*  弧数 */
}Gra2;






/*＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝*/

/*############################具体的实际操作######################*/

void welcome ( )
{
  int i, j ;
  window ( 1, 1, 80, 25);    /*界面初始化*/
  textbackground ( BLACK );
  textcolor ( GREEN );
  clrscr ( );
  for( i = 1; i < 80; i++ )
  {
    gotoxy ( i, 1 ); putch ( 0xe );
   }
  gotoxy ( 2, 2 ); putch ( 0xc9 );
  for( i = 3; i < 79; i++ )
  {
    gotoxy ( i, 2 ); putch ( 0xcd );
  }
    gotoxy ( 79, 2 ); putch( 0xbb );
    gotoxy( 2, 24 );  putch( 0xc8 );

  for( i = 3; i < 80; i++ )
  {
    gotoxy ( i, 24 ); putch( 0xcd );
  }
  gotoxy ( 79, 24 ); putch( 0xbc );

  for( i = 1; i < 80; i++ )
  {
    gotoxy ( i, 25 ); putch ( 0xe );
  }
  for( i = 1; i < 25; i++ )
  {
    gotoxy( 1, i ); putch( 0xe );
    gotoxy( 80, i ); putch ( 0xe );
  }
  for( i = 3; i < 24; i++ )
  {
    gotoxy ( 2, i ); putch ( 0xba );
    gotoxy ( 79, i ); putch( 0xba );
  }
  for( i = 23; i < 42; i++ )
    {
      gotoxy ( i, 4 ); putch( 0x5 );
    }
  for( i = 23; i < 42; i++ )
  {
      gotoxy ( i, 7 ); putch ( 0x5 );
  }
  gotoxy ( 25 , 6 );  cprintf ( "DATASTRUCTURE!" );
  gotoxy ( 20 , 11 );  puts ( "SIMPLY USE OF THE  GRAPH" );
  for( i = 20; i < 45; i++ )
  {
    gotoxy ( i, 12 ); putch ( 0xf7 );
  }
  gotoxy ( 26 ,15 ); putch ( 0x10 );
  gotoxy ( 27, 15 ); putch ( 0x10 );
  gotoxy ( 29, 15 ); printf( "Cumputer Scinece and Tecnology Institute" );
  gotoxy ( 33, 17 ); putch ( 0x10 );
  gotoxy ( 34, 17 ); putch ( 0x10 );
  gotoxy ( 36, 17 ); printf( "class 0402" );
  gotoxy ( 39, 19 ); putch ( 0x10 );
  gotoxy ( 40, 19 ); putch ( 0x10 );
  gotoxy ( 42, 19 ); cprintf ( "Zhangjian" );
  gotoxy ( 45, 21 ); putch ( 0x10 );
  gotoxy ( 46, 21 ); putch ( 0x10 );
  gotoxy ( 48, 21 ); printf( "num:012004016222" );
  gotoxy ( 48, 23 ); putch ( 0x10 );
  gotoxy ( 49, 23 ); putch ( 0x10 );
  gotoxy ( 51, 23 ); puts ( "Date:2006.9.1" );
  gotoxy ( 65, 23 ); putch ( 0xf );
  getch ( );
}

/*==================================制作操作界面======================================*/

static int hj = 20, mam = 0;                                        /*依次为标志常数，菜单标号*/
static int sbx[] = {3,15,25,37,49,61,73};                        /*主菜单输出位置*/
static int key = 0;
static char buf[5000]; 
static char *mainmenu[] = { "creatgraph","gradenum", "dfstraverse", "bfstraverse", "deletvertex", "circlecheck", "Quit" };                  /*主菜单项目*/
char *selecthelp ="       CREAT A GRAPH IMPLYING THE RELATION OF THE MATTERS";    /*下标语*/
char *operatehelp ="                        OPERRATIONS ON A GRAPH";


void disp_menu_item ( int x, int y, int fcolor, int bcolor, char *string )   /*光条设置函数*/
{
    textbackground ( bcolor );
    textcolor ( fcolor );
    gotoxy ( x, y );
    cputs ( string );
}

void enteredit ( )              /*进入编辑状态函数*/
 {
    window ( 1, 1, 80, 25 );
    textattr ( 0x3e );
    gotoxy ( sbx[mam], 1 );    /*在指定位置输出主菜单*/
    cputs ( mainmenu[mam] );
 }

void selectmenu ( )
{
     while( 1 )
     {
         key = getkey ( );                  /*循环接受键盘输入*/
         if( key == LEFT || key == RIGHT )  /*主菜单左右选择*/
           selectmainmenu ( );
         if( key == ENTER )                /*回车确认选项*/
         {
            enteredit ( );                 /*进入编辑状态*/
            window ( 2, 3, 80, 25 );
            textbackground ( 1 );
            textcolor ( 7 );
            if( !subfungo ( ) )
               break;
            qinping();
            window(1,1,80,25);
            wmainmenu ( );
         }
     }
}


int subfungo ( )
{
     switch ( mam )
     {
        case 0:
            creategra () ;
            break;
        case 1:
            getsgrade();
            break;
        case 2:
            dfstraverse();
            break;
        case 3:
             bfstraverse();
             break;
        case 4:
             deletev();
             break;
        case 5:
             toplogicalsort();
             break;
        case 6:
             quit ( );
             break;
      }
    return 1;
 }

void selectmainmenu ( )                   /*选择主菜单*/
{
    window ( 1, 1, 80, 25 );
    disp_menu_item ( sbx[mam], 1, 14, 3, mainmenu[mam] );                     /*恢复主菜单光条*/
    if( key == LEFT )                                                         /*实现主菜单的循环*/
       mam = mam == 0 ? 6: mam - 1;
    if( key == RIGHT )
       mam = mam == 6 ? 0 : mam + 1;
    disp_menu_item ( sbx[mam], 1, 14, 4, mainmenu[mam] );                    /*设置光条*/
}

                                                                            /*写主菜单*/
void wmainmenu ( )
{
    int i;
    window ( 1, 1, 80, 25 );
    textattr ( 0x3e );
    for(i = 0; i < 7; i++ )
    {
       gotoxy( sbx[i], 1 );  cputs ( mainmenu[i] );
    }
    gotoxy ( sbx[mam], 1 );
    textattr ( 0x4e );
    cputs ( mainmenu[mam] );
}


void init ( )                  /*屏幕初始化*/
{
  textmode( 8 );
  window ( 2, 3, 79 ,22 );
  textbackground ( GREEN );
  textcolor ( BLACK );
  clrscr( );
}


void quit ( )                 /*退出函数*/
{
    window ( 1, 1, 80, 25);
    textbackground ( 0 );
    textcolor ( 7 );
    clrscr ( );
    exit ( 0 );
}


void initscreen ( )          /*编辑状态设置*/
{
    textmode ( 4 );
    window ( 1, 1, 80, 25);
    textattr ( 0x17 );
    clrscr ( );
    window ( 1, 1, 80, 1 );
    textattr ( 0x3e );
    clrscr ( );
    window ( 1, 25, 80, 25 );
    textattr ( 0x6a );
    clrscr ( );
    wind ( 1, 2, 80, 23, 2, 1, 15 );
    window ( 1, 24, 80, 24 );
    textattr ( 0x74 );
    clrscr ( );
    cputs ( selecthelp );
    window ( 1, 25, 80, 25 );
    textattr ( 0x6e );
    cputs ( operatehelp );
}


void wind ( int x1, int y1, int x2, int y2, int frmtp, int z, int t)    /*画框函数*/
{
    int i;
    int c[2][6]={
                   {0xda,0xc4,0xbf,0xb3,0xc0,0xd9},   /*线条选项*/
                   {0xc9,0xcd,0xbb,0xba,0xc8,0xbc}
                 };
    textbackground ( z );
    textcolor ( t );
    window ( x1, y1, x2, y2 );
    clrscr ( );
    if( frmtp )
      {
          window ( 1, 1, 80, 25 );
          gotoxy ( x1, y1 );  putch ( c[frmtp-1][0] );  /*画上边框线*/
          for( i = x1 + 1; i < x2; i++ )
              putch ( c[frmtp-1][1] );
          putch ( c[frmtp-1][2] );
          for( i = y1 + 1; i < y2; i++)                 /*画竖直边框线*/
             {
                 gotoxy ( x1, i ); putch ( c[frmtp-1][3] );
                 gotoxy ( x2, i ); putch ( c[frmtp-1][3] );
             }
          gotoxy ( x1, y2 ); putch ( c[frmtp-1][4] );
          for( i = x1 + 1; i < x2; i++ )
             putch ( c[frmtp-1][1] );                  /*画下边框线*/
          putch ( c[frmtp-1][5] );
      }
   window ( x1 + 1, y1 + 1, x2 - 1, y2 - 1 );
}



void qinping ( )        /*清屏函数*/
{
   window ( 2, 3, 79, 22 );
   textbackground ( GREEN );
   textcolor ( WHITE );
   clrscr ( );
}

 void shezhi(int x1,int y1,int x2,int y2,int bcolor,int fcolor,char *string)
 {
     window(x1,y1,x2,y2);
     textbackground(bcolor);
     textcolor(fcolor);
     clrscr();
     gets(string);
     window(2,3,79,22);
}


void shezhi1(int x1,int y1,int x2,int y2,int bcolor,int fcolor,char *string)
 {
     window(x1,y1,x2,y2);
     textbackground(bcolor);
     textcolor(fcolor);
     clrscr();
     puts(string);
     window(2,3,79,22);
}


int getkey ( )
{
    union  star
    {
       unsigned int x;
       unsigned char y[2];
    }key1;
    do
    {
        key1.x = bioskey( 0 );
        return ( key1.y[1] );
    }while ( 1 );
}

/*·········堆栈的操作········*/
 initstack()
{
   (*s).base=(struct vernode2 *)malloc(stack_max*sizeof(struct vernode2));
   if(!(*s).base)
     exit(-1);                         /*  堆栈初始化 */
   (*s).top=(*s).base;
   (*s).stacksize=stack_max;
 }

void push(struct vernode2 *e)           /* 入栈操作 */
{
   if((*s).top-(*s).base>=(*s).stacksize)
   {
     (*s).base=(struct vernode2 *)realloc((*s).base,((*s).stacksize+stackincrement)*sizeof(struct vernode2));
     if(!(*s).base)
        exit(-1);
     (*s).top=(*s).base+(*s).stacksize;
     (*s).stacksize+=stackincrement;
   }
   *(*s).top++=*e;
}


struct vernode2 * pop()               /*  出栈操作 */
{
   if((*s).top==(*s).base)
     return (0);
   else
     return(--s->top);
}

int  stackempty()                    /*  判断栈空（空（1），非空（0））*/
{
   if(s->top==s->base)
     return(1);
   else
     return(0);
}


/*＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ */




/*@@@@@@@@@@@@@@@@@@@@@@队列操作@@@@@@@@@@@@@@@@@@*/

int  dequeue (struct vexqueue *p)   /*   出队列 */
{
   struct vexposition *q;
   int  locate;
   if((*p).rear==(*p).tail)
     return(0);
   q=p->rear->next;
   locate=(*q).position;
   p->rear->next=(*q).next;
   if((*p).tail==q)
     (*p).tail=(*p).rear;
   free(q);
   return(locate);
}

void  enqueue(struct vexqueue *q,int x)   /* 入队列 */
{
   Vexposition *s;
   s=(struct vexposition *)malloc(sizeof(struct vexposition));
   if(!s)
     exit(-1);
   (*s).position=x;
   (*s).next=NULL;
   q->tail->next=s;
   (*q).tail=s;
 }

void initque(struct vexqueue *p)         /*  队列初始化 */
{
  (*p).rear=(*p).tail=(struct vexposition *)malloc(sizeof(struct vexposition));
  if(!(*p).rear)
    exit(-1);
  p->tail->next=NULL;
}


int empty(struct vexqueue *p)           /*   判断队列是否为空 */
{
   if(p->tail==p->rear)
     return(1);
   else
     return(0);
}


void  creategra ()                    /*   创建图并同时用邻接表和十字链表存储 */
{
  int i,key,j,k,t,cap;
  char ding1[5],qu[2];
  struct arcnode2 *p,*q;
  struct arcbox  *p1;
  g2=(struct gra2 *)malloc(sizeof(struct gra2));
  g=(struct gra *)malloc(sizeof(struct gra));
  qinping();
  gotoxy(3,3);
  printf("The total number of the vertexes:"); /* 输入顶点总数和边的总数  */
  scanf("%d",&((*g2).vernum));
  (*g).vexnum=(*g2).vernum;
  gotoxy(3,4);
  printf("The total number of the arcs:");
  scanf("%d",&((*g2).arcnum));
  (*g).arcnum=(*g2).arcnum;
  gotoxy(3,5);
  printf("Now input the information about the vertexes:");
  gets(qu);                                    /* 输入顶点 */
  for(i=0,cap=6;i<(*g2).vernum;i++,cap+=2)
  {
      if(cap==19||cap==18)
     {
         gettext(2,5,79,22,buf);
         puttext(2,3,79,20,buf);
         cap-=2;
     }
     gotoxy(3,cap);
     printf("vertex%d:",i);
     shezhi(14,cap+2,18,cap+2,1,7,(*g2).verlist[i].value);
     strcpy((*g).vexlist[i].vex,(*g2).verlist[i].value);
     (*g2).verlist[i].vermark=0;
     (*g2).verlist[i].gradein=0;
     (*g2).verlist[i].gradeout=0;
     (*g2).verlist[i].firstarc=NULL;
     (*g).vexlist[i].seamark=0;
     (*g).vexlist[i].firstin=NULL;
     (*g).vexlist[i].firstout=NULL;
  }
  gotoxy(3,cap);
  printf("Now input the information about the arcs:");