Question

用数据结构的栈和队列 写 回文判断

假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。编程实现该程序。

Answer 1

用栈实现了判断回文数的操作，即把字符串依次入栈，然后出栈并依次和字符数组比较是否相等，从而判断字符序列是否回文数，代码如下：

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#define EMPTY 0

#define FULL 10000

#define MAX 10000

typedef char data;

typedef struct elem {

 data d;

 struct elem *next;

}elem;

typedef struct stack {

 int cnt;

 elem *top;

}stack;

void initialize(stack *stk);

void push(data d, stack *stk);

data pop(stack *stk);

bool empty(const stack *stk);

bool full(const stack *stk); //栈操作函数

void initialize(stack *stk)

{

 stk->cnt = 0;

 stk->top = NULL;

}

bool empty(const stack *stk)

{

 return stk->cnt == EMPTY;

}

bool full(const stack *stk)

{

 return stk->cnt == FULL;

}

void push(data d, stack *stk)

{

 elem *p;

 

 if (!full(stk))

 {

  p = (elem *)malloc(sizeof(elem));

  p->d = d;

  p->next = stk->top;

  stk->top = p;

  stk->cnt++;

 }

 

}

data pop(stack *stk)

{

 data d;

 elem *p;

 if(!empty(stk))

 {

  d = stk->top->d;

  p = stk->top;

  stk->top = stk->top->next;

  stk->cnt--;

  free(p);

 }

 

 return d;

}

int main(void)

{

 data input[MAX];

 stack temp;

 int i = 0;

 int flag = 0;

 initialize(&temp); //初始化临时栈

 scanf("%s", &input); //输入字符串

 while (input[i] != '@')

 {//字符串入栈

  push(input[i], &temp);

  i++;

 }

 while (!empty(&temp))

 {//字符依次出栈和字符数组比较，判断是否回文数

  if (temp.top->d == input[flag])

  {

   pop(&temp);

   flag++;

  }

  else

  {

   printf("此字符序列不是回文数!\n");

   break;

  }

 }

 

 if (empty(&temp))

  printf("此字符序列是回文数!\n");

 return 1;

}

运行结果：

Answer 2

//---------------------------------------------------------------------------

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

typedef struct node{
char data;
struct node *next;
}node;

typedef struct {
node *top;
unsigned int size;
} stack;

typedef struct{
node *front;
node *back;
unsigned int size;
} queue;

char pops(stack *a)
{
node *tf=NULL;
char rt=0;
if (a->size) {
tf=a->top;
a->top=a->top->next;
--a->size;
rt=tf->data;
free(tf);
}

return rt;
}

char popq(queue *a)
{
node *tf=NULL;
char rt=0;
if (a->size) {
tf=a->front;
a->front=a->front->next;
--a->size;
rt=tf->data;
free(tf);
}
return rt;
}

void push(stack *a,const char c)
{
node *t=(node*)malloc(sizeof(node));
if (t) {
t->data=c;
t->next=a->top;
a->top=t;
++a->size;
}
}
void push_back(queue *a,const char c)
{
node *t=(node*)malloc(sizeof(node));
if (t) {
t->data=c;
t->next=NULL;
if (!a->size) {
a->front=a->back=t;
}
else
{
a->back->next=t;
a->back=t;
}

++a->size;
}
}

int isempty(void *a,int tp)
{
if (tp==1) return !(((stack *)a)->size);
else return !(((queue *)a)->size);
}
void initqs(void *a,int tp)
{
if (tp==1) {
((stack*)a)->top=NULL;
((stack*)a)->size=0;
}
else{
((queue*)a)->front=((queue*)a)->back=NULL;
((queue*)a)->size=0;
}
}

void del(void *a,int tp)
{
node *t;
if (tp==1) {
while (((stack*)a)->top){
t= ((stack*)a)->top;
((stack*)a)->top=((stack*)a)->top->next;
free(t);
}
free(a);
}
else {
while (((queue*)a)->front){
t= ((queue*)a)->front;
((queue*)a)->front=((queue*)a)->front->next;
free(t);
}
free(a);
}
}
int chk(void)
{
char ch;
int fg=1,rt=0;

stack *a=(stack*)malloc(sizeof(stack));
queue *b=(queue*)malloc(sizeof(queue));
if (!a||!b) {
fprintf(stderr,"MEMORY ERROR");
exit(-1);
}
initqs(a,1);
initqs(b,0);

puts("Enter a string ,end with @");
while ((ch=getchar())!='@')
{
push(a,ch);
push_back(b,ch);
}

while (!isempty(a,1)&&!isempty(b,0))
{
if (pops(a)!=popq(b)) {
fg=0;
break;
}
}
if (fg&&isempty(a,1)&&isempty(b,0)) rt= 1;
del(a,1);
del(b,0);
return rt;

}
int main(void)
{
if (chk()) puts("YES");
else puts("NO");

return 0;
}
//---------------------------------------------------------------------------