用数据结构的栈和队列 写 回文判断
假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。编程实现该程序。
用栈实现了判断回文数的操作，即把字符串依次入栈，然后出栈并依次和字符数组比较是否相等，从而判断字符序列是否回文数，代码如下：
#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;
}
运行结果：
#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;
}
//---------------------------------------------------------------------------
