C语言 数据结构 ， 用链式队列和链式栈 判断一个字符串是否为回文

Question

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxStackSize 50
typedef char ElemType;
typedef struct snode
{
ElemType data;
struct snode *next;
}SingleLinkedNode;

void StackInitiate(SingleLinkedNode **head) //初始化
{
if((*head=(SingleLinkedNode *)malloc(sizeof(SingleLinkedNode)))==NULL)
exit(1);
(*head)->next=NULL;
}
int StackNotEmpty(SingleLinkedNode *head) //是否为空
{
if(head->next==NULL)
return 0;
else
return 1;
}
int StackPush(SingleLinkedNode *head,ElemType x) //入栈
{
SingleLinkedNode *p;
if((p=(SingleLinkedNode *)malloc(sizeof(SingleLinkedNode)))==NULL)
{
printf("内存空间不足无法插入！\n");
return 0;
}
p->data=x;
p->next=head->next;
head->next=p;
}
int StackPop(SingleLinkedNode *head,ElemType *d) //删除元素（弹出）
{
SingleLinkedNode *p=head->next;
if(p=NULL)
{
printf("堆栈已空出错！");
return 0;
}
head->next=p->next;
*d=p->data;
free(p);
return 1;
}
typedef struct qnode //队列
{
ElemType data;
struct qnode *next;
}LinkedQueueNode;
typedef struct
{
LinkedQueueNode *front;
LinkedQueueNode *rear;
}LQueue;

void QueueInitiate(LQueue *Q) //初始化
{
Q->rear=NULL;
Q->front=NULL;
}
int QueueNotEmpty(LQueue Q) //是否为空
{
if(Q.front==NULL)
return 0;
else
return 1;
}

int QueueAppend(LQueue *Q,ElemType x) //入队列
{
LinkedQueueNode *p;
if((p=(LinkedQueueNode *)malloc(sizeof(LinkedQueueNode)))==NULL)
{
printf("内存空间不足！");
return 0;
}
p->data=x;
p->next=NULL;
if(Q->rear!=NULL)
Q->rear->next=p;
Q->rear=p;
if(Q->front==NULL)
Q->front=p;
return 1;
}

int QueueDelete(LQueue *Q,ElemType *d) //出队列（删除）
{
LinkedQueueNode *p;
if(Q->front==NULL)
{
printf("队列已空无数据出队列！\n");
return 0;
}
else
{
*d=Q->front->data;
p=Q->front;
Q->front=Q->front->next;
if(Q->front==NULL)
Q->rear=NULL;
free(p);
return 1;
}
}

typedef struct //顺序栈（进制 ）
{
ElemType stack[MaxStackSize];
int top;
}SequenceStack;
void StackInitiate(SequenceStack *S)
{
S->top=0;
}

int StackNotEmpty(SequenceStack *S)
{
if(S->top<=0)
return 0;
else
return 1;
}

int StackPush(SequenceStack *S,ElemType x)
{
if(S->top>=MaxStackSize)
{
printf("堆栈已满无法插入!\n");
return 0;
}
else
{
S->stack[S->top]=x;
S->top++;
return 1;
}
}
int StackPop(SequenceStack *S,ElemType *d)
{
if(S->top<=0)
{
printf("堆栈已空!\n");
return 0;
}
else
{
S->top--;
*d=S->stack[S->top];
return 1;
}
}
void main() //主函数在这里
{
SingleLinkedNode *head;
LQueue Q;
SequenceStack *myStack;
int i, decimal,k,g;
char str[20],x,d;
StackInitiate(&head);
StackInitiate(myStack);
QueueInitiate(&Q);
printf("输入字符串：");
gets(str);
i=0;
while(i<strlen(str))
{
StackPush(head,str[i]);
QueueAppend(&Q,str[i]);
i++;
}
g=0;
while(StackNotEmpty(head)&&QueueNotEmpty(&Q)) //提示说这里错了！！！！！！
{
StackPop(head,&x);
QueueDelete(&Q,&d);

if(x!=d)
break;
g++;
}

if(g<strlen(str))
printf("不是回文!\n");

if(g==strlen(str))
printf("是回文!\n");
}

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const MaxStackSize = 50;

typedef char ElemType;

typedef struct snode {
ElemType data;
struct snode *next;
}*LinkStack,*psNode;

LinkStack GetEmptyStack() { // 初始化
LinkStack head = (psNode)malloc(sizeof(struct snode));
if((head) == NULL) {
printf("内存空间不足无法插入！\n");
return NULL;
}
head->data = '0';
head->next = NULL;
return head;
}

int StackNotEmpty(LinkStack head) { // 是否为空
return (head->next != NULL);
}

int StackPush(LinkStack head,ElemType x) { // 入栈
psNode p = (psNode)malloc(sizeof(struct snode));
if(p == NULL) {
printf("内存空间不足无法插入！\n");
return 0;
}
p->data = x;
p->next = head->next;
head->next = p;
return 1;
}

int StackPop(LinkStack head,ElemType *x) { //删除元素（弹出）
psNode p = head->next;
if(StackNotEmpty(head)) {
*x = p->data;
head->next = p->next;
free(p);
return 1;
}
return 0;
}

typedef struct qnode  { // 队列
ElemType data;
struct qnode *next;
}*pqNode;

typedef struct queue{
pqNode front;
    pqNode rear;
}*LinkQueue;

LinkQueue GetEmptyQueue() { //初始化
LinkQueue Q = (struct queue *)malloc(sizeof(struct queue));
if(Q == NULL) {
printf("内存空间不足无法插入！\n");
return NULL;
}
Q->rear = NULL;
    Q->front = NULL;
return Q;
}

int QueueNotEmpty(LinkQueue Q) { //是否为空
return (Q->front != NULL);
}

int QueueAppend(LinkQueue Q,ElemType x) { //入队列
struct qnode *p = (struct qnode *)malloc(sizeof(struct qnode));
if(p == NULL) {
printf("内存空间不足!\n");
return 0;
}
p->data = x;
p->next = NULL;
if(Q->front == NULL) // 队列为空
Q->front = Q->rear = p;
else {
Q->rear->next = p;
Q->rear = p;
}
return 1;
}

int QueueDelete(LinkQueue Q,ElemType *d) { //出队列（删除）
pqNode p;
if(QueueNotEmpty(Q)) {
*d = Q->front->data;
p = Q->front;
Q->front = p->next;
if(p->next == NULL) Q->rear = NULL;
free(p);
return 1;
}
printf("队列已空无数据出队列！\n");
return 0;
}

typedef struct sqstack { //顺序栈（进制）
ElemType stack[MaxStackSize];
int size;
}SequenceStack;

void StackInitiate(SequenceStack *S) {
S->size = 0;
}

int StackNotEmpty(SequenceStack *S) {
return (S->size > 0);
}

int StackPush(SequenceStack *S,ElemType x) {
if(S->size >= MaxStackSize) {
printf("堆栈已满无法插入!\n");
return 0;
}
S->stack[S->size] = x;
++S->size;
return 1;
}

int StackPop(SequenceStack *S,ElemType *d) {
if(S->size == 0) {
printf("堆栈已空!\n");
return 0;
}
--S->size;
*d = S->stack[S->size];
return 1;
}

int main() { //主函数在这里
LinkStack head = GetEmptyStack();
LinkQueue Q = GetEmptyQueue();
// SequenceStack myStack;
char x,d;
int i = 0,flag;
char str[MaxStackSize];
    
    printf("输入字符串：");
scanf("%s",str);
while(str[i]) {
StackPush(head,str[i]);
QueueAppend(Q,str[i]);
++i;
}
while(StackPop(head,&x) && QueueDelete(Q,&d) && flag)
flag = (x == d);
if(flag) printf("是回文!\n");
else printf("不是回文!\n");
return 0;  
}

Answer 2

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define STACKSIZE 100

typedef struct
{
char item[STACKSIZE];
int top;
}SqStack;

typedef struct QNode
{
char data;
struct QNode *next;
}LQNode, *PQNode;
typedef struct
{
PQNode front, rear;
} LinkQueue;

int InitStack(SqStack *S);
int StackEmpty(SqStack S);
int Push(SqStack *s, char data);
int Pop(SqStack *s, char *data);
int InitQueue(LinkQueue *q);
int TraverseQueue(LinkQueue Q) ;
int QueueEmpty(LinkQueue q);
int EnQueue(LinkQueue *q, char item);
int DeQueue(LinkQueue *q, char *item);
int DestroyQueue (LinkQueue *Q);

int main()
{
char num[100], it, str[100], sum[100];
int i, flag, len;
SqStack zb;
LinkQueue lb;

InitStack(&zb);
InitQueue(&lb);
do
{

printf("(1) 请输入元素并存入队列\n");
printf("(2) 将元素存入栈\n");
printf("(3) 显示栈内元素\n");
printf("(4) 判断回文\n");
printf("(5) 退出\n");

scanf("%d", &flag);
switch (flag)
{
case 5:
{
printf("END\n");
DestroyQueue(&lb);
return 0;
}
case 1:
{
InitQueue(&lb);
printf("Please input a number:\n");
scanf("%s", str);
len = strlen(str);
for(i=0; i<len; i++)
{
if(!EnQueue(&lb, str[i]))
{
break;
}
}
printf("输入的队列为:");
TraverseQueue(lb);
break;
}
case 2:
{
if(QueueEmpty(lb))
{
printf("队列为空，请先输入\n");
}
for(i=0; i<len; i++)
{
DeQueue(&lb, &it);
Push(&zb, it);
sum[i] = it;
}
sum[i] = '\0';
break;
}
case 3:
{
if(StackEmpty(zb))
{
printf("空栈\n");
break;
}
for(i=0; i<len; i++)
{
Pop(&zb, &it);
num[i] = it;
}
num[i] = '\0';
printf("出栈顺序为:");
printf("%s\n", num);
break;
}
case 4:
{
i = strcmp(num, sum);
if(i == 0)
{
printf("是\n");
}
else
{
printf("不是\n");
}
break;
}
default :
{
printf("ERROR");
}
}
} while (1);

}

int InitStack(SqStack *S)
{
S->top = -1;
return 1;
}

int StackEmpty(SqStack S)
{
if (S.top == -1)
{
return 1;
}
else
{
return 0;
}
}

int Push(SqStack *s, char data)
{
if (s->top == STACKSIZE - 1)
{
printf("\n栈已满");
return 0;
}
s->top++;
s->item[s->top] = data;
return 1;
}

int Pop(SqStack *s, char *data)
{
if (s->top == -1)
{
printf("\n栈已空");
return 0;
}
*data = s->item[s->top];
s->top--;
return 1;
}

int InitQueue(LinkQueue *q)
{
q->front = q->rear = (PQNode)malloc(sizeof(LQNode));
if (!q->front)
{
printf("\n初始化队列失败！");
return 0;
}
q->front->next = NULL;
return 1;
}

int QueueEmpty(LinkQueue q)
{
if (q.front == q.rear)
{
return 1;
}
else
{
return 0;
}
}

int EnQueue(LinkQueue *q, char item)
{
PQNode p;
p = (PQNode)malloc(sizeof(LQNode));
if (!p)
{
printf("\n内存分配失败，无法存入数据！\n");
return 0;
}

p->data = item;
p->next = NULL; //初始化入队结点
q->rear->next = p;
q->rear = p;
return 1;
}

int DeQueue(LinkQueue *q, char *item)
{
PQNode p;
if (q->front == q->rear)
{
printf("\n队列已空，不能完成出队操作！");
return 0;
}
p = q->front->next;
*item = p->data;
q->front->next = p->next;
free(p);
if (q->rear == p)
{
q->front = q->rear;
}
return 1;
}

int DestroyQueue (LinkQueue *Q)
{
while(Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return 1;
}

int TraverseQueue(LinkQueue Q)
{
PQNode p;
if (QueueEmpty(Q))
{
return 0;
}
p = (PQNode)malloc(sizeof(LQNode));
p = Q.front->next;
while (p != NULL)
{
printf("%c", p->data);
p = p->next;
}
printf("\n");
return 1;
}