huiwen.c

数据结构中---回文的判断,使用栈和队列来实现

#include <stdio.h>

#define TRUE  1
#define FALSE 0

typedef struct Node
{
    char data;
    struct Node * next;
} Node;   /* 定义节点 */

typedef Node * LinkStack;  /* 定义栈 */

typedef struct
{
    Node * front;
    Node * rear;
} * LinkQueue;      /* 定义队列 */

int initStack(LinkStack S)  /* 初始化栈 */
{
    Node * head;
    head=(Node *)malloc(sizeof(Node));
    head->next=NULL;
    if(head==NULL)    return FALSE;
    {
        S=head;
        return TRUE;
    }
}

int push(LinkStack S,char x)  /* 压栈 */
{
    Node * temp;
    temp=(Node *)malloc(sizeof(Node));
    if(temp==NULL)    return FALSE;
    temp->data=x;
    temp->next=S->next;
    S->next=temp;
    return TRUE;
}

int pop(LinkStack S,char *x)  /* 弹栈 */
{
    Node * temp;
    temp=S->next;
    if(temp==NULL)    return FALSE;
    S->next=temp->next;
    *x=temp->data;
    free(temp);
    return TRUE; 
}

int initQueue(LinkQueue Q)    /* 初始化队列 */
{
    Q->front=(Node *)malloc(sizeof(Node));
    if(Q->front==NULL)    return FALSE;
    Q->rear=Q->front;
    Q->front->next=NULL;
    return TRUE;
}

int enterQueue(LinkQueue Q,char x)  /* 入队 */
{
    Node * temp;
    temp=(Node *)malloc(sizeof(Node));
    if(temp==NULL)    return FALSE;
    temp->data=x;
    temp->next=NULL;
    Q->rear->next=temp;
    Q->rear=temp;
    return TRUE;
}

int deleteQueue(LinkQueue Q,char *y)  /* 出队 */
{
    Node * temp;
    if(Q->front==Q->rear)    return FALSE;
    temp=Q->front->next;
    Q->front->next=temp->next;
    if(Q->rear==temp)
        Q->rear=Q->front;
    *y=temp->data;
    free(temp);
    return TRUE;
}

void input(LinkStack S,LinkQueue Q)   /* 输入字串，入栈，入队 */
{
    char ch;
    LinkStack tempS;
    LinkQueue tempQ;
    printf("please input a serial char and end of '#':\n");
    while((ch=getchar())!='#')
    {
        push(S,ch);
        enterQueue(Q,ch);
    }
    /* 测试：输出栈中元素 */
    printf("\nStack element is :\n");
    tempS=S->next;
    while(tempS!=NULL)
    {
        printf("%c ",tempS->data);
        tempS=tempS->next;
    }
    /* 测试：输出队中元素 */
    printf("\nQueue element is :\n");
    tempQ=Q->front->next;
    while(tempQ!=NULL)
    {
        printf("%c ",tempQ->data);
        tempQ=tempQ->next;
    }
}

int compare(LinkStack S,LinkQueue Q)  /* 对字串进行比较 */
{
    int flag=1;
    char qch,sch;
    while(S->next!=NULL && Q->front->next!=NULL)
    {
        pop(S,&sch);
        deleteQueue(Q,&qch);
        if(sch!=qch)
        {
            flag=0;
            break;
        }
    }
    if(flag==0)
        return FALSE;
    else
        return TRUE;
}
main()
{
    LinkStack Stack;
    LinkQueue Queue;
    int result=0;
    initStack(Stack);      /* 初始化栈 */
    initQueue(Queue);      /* 初始化队列 */
    input(Stack,Queue);    /* 输入要处理的字符，并且入栈，入队 */
    result=compare(Stack,Queue);  /* 比较，并返回是否是回文的结果 */
    printf("\n\nThe result is :");
    if(result==1)
        printf("\nYes");
    else
        printf("\nNo");
    getch();
}