tc2.txt

数据结构实验指导书中关键算法的C语言实现

#include "stdio.h" 
#include "graphics.h" 
#include "stdlib.h" 

#define STACK_INIT_SIZE  100;
#define STACKINCREMENT    10;
#define OVERFLOW          1
#define OK          1
#define ERROR      0

typedef char      SElemType;
typedef char      QElemType;
typedef int     Status;


typedef struct {
    SElemType   *base;
    SElemType   *top;
    int     stacksize;
  }SqStack;

typedef struct QNode{
    QElemType  data;
    struct QNode  *next;
}QNode,*QueuePtr;

typedef struct{
        QueuePtr front;
        QueuePtr rear;
}LinkQueue;



Status InitStack(SqStack &S)
         {
        S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
        if(!S.base) exit(OVERFLOW);
        S.top=S.base;
        S.stacksize=STACK_INIT_SIZE;
        return OK;
        }

Status push(SpStack&S,SElemType e){
        if(S.top-S.base>=S.stacksize){
          S.base=(ElemType *)realloc(S.base,
           (S.stacksize+STACKINCREMENT)*sizeof(ElemType));
           if(!S.base) exit(OVERFLOW);
           S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT; }
        *S.top++=e;
        return OK;
        }

Status pop(SpStack&S,SElemType &e){
           if(S.top==S.base) return ERROR;
           e=*--S.top;
           return OK;
        }

Status InitQueue(LinkQueue&Q){
            Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
            if(!Q.front) exit(OVERFLOW);
              Q.front->next=NULL;
              return OK;
              }

Status EnQueue(LinkQueue&Q,QElemType e){
            QueuePtr p;
            p=(QueuePtr)malloc(sizeof(QNode));
            if(!p) exit(OVERFLOW);
            p->data=e; p->next=NULL;
            Q.rear->next=p;
            Q.rear=p;
            return OK;
            }

Status DeQueue(LinkQueue&Q,QElemType &e){
             QueuePtr p;
             if(Q.front==Q.rear) return ERROR;
             p=Q.front->next;
             e=p->data;
             Q.front->next=p->next;
             if(Q.rear==p) Q.rear=Q.front;
             free(p);
             return OK;
             }

main()
{   char a[];
    char ch1,ch2,ch3;
    int i=0,n;
    LinkQueue Q1,Q2;
     SqStack S;
    InitStack(S);
    InitQueue(Q1);
    InitQueue(Q2);
    while(ch1!='\n')
    { ch1=getchar();
      a[i]=ch1;
      i++; }
      n=strlen(a);
      for(i=n-1;i>=;i--)
       { ch1=a[i];
         push(S,ch1);}
      while(S.top!=S.base)
        {  pop(S,ch1);
           switch(ch1){
                case'B': ch1=A;push(S,ch1);ch1=d; push(S,ch1);ch1=A;
                         push(S,ch1);ch1=t;push(S,ch1); break;
                case'A': ch1=e; push(S,ch1);ch1=a;push(S,ch1);ch1=S;
                         push(s,ch1); break;
                case'(': while(ch1!=')') {pop(S,ch1);EnQueue(Q2,ch1);}
                         ch2=DeQueue(Q2);ch3=ch2;
                         push(S,ch3); ch2=DeQueue(Q2);
                         while(ch2!=')')
                           {push(S,ch2);
                            push(S,ch3);
                            DeQueue(Q2);}
                            break;
                default: EnQueue(Q1,ch1);
                         printf("%c",ch1);break;
          }

       while(Q1.front!=Q1.rear)
          { ch1=DeQueue(Q);
            switch(ch1){
               case't': printf("天");break;
               case'd': printf("地");break;
               case's': printf("上");break;
               case'a': printf("一只");break;
               case'e': printf("鹅");break;
               case'z': printf("追");break;
               case'g': printf("赶");break;
               case'x': printf("下");break;
               case'n': printf("蛋");break;
               case'h': printf("恨");break;
                       }

           }
           return OK;

}