데이터 구조 재 미 있 는 문제 - 답장 문자열 의 판정

스 택 과 대기 열 을 동시에 사용 합 니 다.

   1: #include "stdio.h"

   2: #define STACK_INIT_SIZE 20

   3: #define STACKINCREMENT 10

   4:  

   5:  

   6: typedef char ElemType;   /* char     ElemType*/

   7:  

   8: typedef struct QNode {    /*       */

   9:     ElemType data;

  10:     struct QNode *next;

  11: } QNode , *QueuePtr;

  12:  

  13: typedef struct {     /*       */

  14:     QueuePtr front;   /*    */

  15:     QueuePtr rear;    /*    */

  16: } LinkQueue;

  17:  

  18: typedef struct {       /*       */

  19:     ElemType *base;

  20:     ElemType *top;

  21:     int stacksize;

  22: } sqStack;

  23:  

  24:  

  25: void initQueue(LinkQueue *q) {

  26:     /*        */

  27:     q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)); /*       ，                                                                           */

  28:  

  29:     if( !q->front) exit(0);     /*       */

  30:  

  31:     q->front->next = NULL;     /*       NULL*/

  32: }

  33:  

  34: void EnQueue(LinkQueue *q, ElemType e) {     /*     */

  35:     QueuePtr p;

  36:     p = (QueuePtr)malloc(sizeof(QNode));  /*          */

  37:  

  38:     if( !q->front) exit(0);     /*       */

  39:  

  40:     p->data = e;                /*   e   */

  41:     p->next = NULL;             /*      */

  42:     q->rear ->next = p;

  43:     q->rear = p;

  44: }

  45:  

  46: void DeQueue(LinkQueue *q, ElemType *e) {

  47:     /*    q   ，  q     ， e    */

  48:     QueuePtr p;

  49:  

  50:     if(q->front == q->rear) return;  /*    ，  */

  51:  

  52:     p = q->front->next;

  53:     *e = p->data;

  54:     q->front->next = p->next;

  55:  

  56:     if(q->rear == p) q->rear = q->front;  /*        ，       */

  57:  

  58:     free(p);

  59: }

  60:  

  61: void initStack(sqStack *s)

  62: {

  63:     /*                ，      s->base*/

  64:     s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));

  65:  

  66:     if(!s->base) exit(0);     /*      */

  67:  

  68:     s->top = s->base;       /*   ，      */

  69:     s->stacksize = STACK_INIT_SIZE;   /*     STACK_INIT_SIZE */

  70: }

  71:  

  72: void Push(sqStack *s, ElemType e) {       /*    */

  73:     if(s->top - s->base >= s->stacksize) {

  74:         /*  ，    */

  75:         s->base = (ElemType *)realloc(s->base, (s->stacksize +

  76:                                                 STACKINCREMENT) * sizeof(ElemType));

  77:  

  78:         if(!s->base) exit(0);   /*      */

  79:  

  80:         s->top = s->base + s->stacksize;

  81:         s->stacksize = s->stacksize + STACKINCREMENT; /*        */

  82:     }

  83:  

  84:     *(s->top) = e;  /*    */

  85:     s->top++;

  86: }

  87:  

  88: void Pop(sqStack *s , ElemType *e) {  /*    */

  89:     if(s->top == s->base) return;  /*       */

  90:  

  91:     *e = *--(s->top);              /*      */

  92: }

  93:  

  94: int StackLen(sqStack s) {    /*   s   */

  95:     return (s.top - s.base) ;

  96: }

  97:  

  98:  

  99: int main()

 100: {

 101:     sqStack s;

 102:     LinkQueue q;

 103:     ElemType e, r1, r2;

 104:     int flag = 1, i, len;

 105:  

 106:     initQueue(&q);  /*       */

 107:     initStack(&s);  /*      */

 108:     printf("Please input a string ,type '@' for end
");

 109:     scanf("%c", &e);

 110:  

 111:     while(e != '@') {      /*          */

 112:         Push(&s, e);

 113:         EnQueue(&q, e);

 114:         scanf("%c", &e);

 115:     }

 116:  

 117:     len =  StackLen(s) / 2; /*         */

 118:  

 119:     for(i = 0; i < len; i++)

 120:     {

 121:         Pop(&s, &r1);    /*    ， r1       */

 122:         DeQueue(&q, &r2); /*     ， r2       */

 123:  

 124:         if(r1 != r2) {

 125:             flag = 0;

 126:             break;

 127:         }

 128:     }

 129:  

 130:     if(flag == 1)printf("It is a circle string.
");

 131:     else printf("It is not a circle string.
") ;

 132:  

 133:     return 0;

 134:  

 135: }

 136: