回文判断

题目描述

假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。请编写一个程序判别读入的一个以’@’为结束符的字符序列是否是“回文”。提示：由于依次输入的字符序列中不含特殊的分隔符，则在判别是否是“回文”时，一种比较合适的做法是，同时利用“栈”和“队列”两种结构。

题目解析

本题也很简单，创建队列和栈两个数据结构，分别取Top比较再Pop，放到while循环里即可

//3. 假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。
//请编写一个程序判别读入的一个以’@’为结束符的字符序列是否是“回文”。
//提示：由于依次输入的字符序列中不含特殊的分隔符，则在判别是否是“回文”时，一种比较合适的做法是，同时利用“栈”和“队列”两种结构。\

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef char QueueDataType;
typedef struct QNode
{
   
    QueueDataType data;
    struct QNode* next;
}QNode;

typedef struct Queue
{
   
    QNode* phead;
    QNode* ptail;
}Queue;

void QueueInit(Queue* pq)
{
   
    pq->phead = NULL;
    pq->ptail = NULL;
}

QNode* BuynewQNode(QueueDataType x)
{
   
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
   
        perror("malloc fail");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void QueuePush(Queue* pq, QueueDataType x)
{
   
    assert(pq);
    QNode* newnode = BuynewQNode(x);
    if (pq->phead == NULL)
    {
   
        pq->phead = pq->ptail = newnode;
    }
    else
    {
   
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
}

void QueuePop(Queue* pq)
{
   
    assert(pq);
    assert(pq->phead);
    pq->phead = pq->phead->next;
}

QueueDataType QueueTop(Queue* pq)
{
   
    assert(pq);
    assert(pq->phead);
    return pq->phead->data;
}

bool QueueEmpty(Queue* pq)
{
   
    assert(pq);
    if (pq->phead == NULL)
    {
   
        return true;
    }
    else
    {
   
        return false;
    }
}

typedef char STDataType;
typedef struct Stack
{
   
    STDataType* a;
    int capacity;
    int top;
}Stack;

void StackInit(Stack* pst)
{
   
    pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (pst->a == NULL)
    {
   
        perror("malloc fail");
        return;
    }
    pst->capacity = 4;
    pst->top = 0;
}

STDataType StackTop(Stack* pst)
{
   
    assert(pst);
    assert(pst->top);
    return pst->a[pst->top - 1];
}

void StackPop(Stack* pst)
{
   
    assert(pst);
    assert(pst->top);
    pst->top--;
}

void StackPush(Stack* pst, STDataType x)
{
   
    assert(pst);
    if (pst->capacity = pst->top)
    {
   
        STDataType* tmp = NULL;
        int newcapacity = pst->capacity * 2;
        tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    pst->a[pst->top] = x;
    pst->top++;
}

bool StackEmpty(Stack* pst)
{
   
    if (pst->top == 0)
        return true;
    else
        return false;
}

void Input(Queue* pq, Stack* ps)
{
   
    char ret;
    printf("输入回文字符，以@结尾->");
    while (1)
    {
   
        scanf("%c", &ret);
        if (ret == '@')
            break;
        QueuePush(pq, ret);
        StackPush(ps, ret);
    }
}

void Judge(Queue* pq, Stack* ps)
{
   
    while (!QueueEmpty(pq))
    {
   
        char que = QueueTop(pq);
        QueuePop(pq);
        char st = StackTop(ps);
        StackPop(ps);
        if (que!=st)
        {
   
            printf("不是回文\n");
            return;
        }
    }
    printf("是回文\n");
    return;
}

int main()
{
   
    Queue q;
    Stack s;
    QueueInit(&q);
    StackInit(&s);
    Input(&q, &s);
    Judge(&q, &s);
    return 0;
}