Question

C语言如何使用堆栈判断回文？

具体如图作法要求为须使用数组堆栈来进行处理，堆栈所需的数据型态及相关函式如下：typedef struct tagStack { char Item[MAX_ITEM]; int Top; }Stack;int Push(Stack *,char );int IsFull(Stack *);int Pop(Stack *,char *);int IsEmpty(Stack *);void PrintStack(Stack *);作法提示：1. 将读入的字符串依序push到堆栈2. 设定front为03. 堆栈顶端与front所指位置的项目进行比较4. 若不相等则该字符串非回文，输出”No”的结果。5. 若相等则pop顶端项目，并将front+1。6. 重复步骤3直到比较完字符串长度一半为止都相等，则输出”Yes”的结果。 输入说明 第一列输入测试案例的个数T。紧接着是每个测试案例的资料。 每个测试案例的输入为一个字符串，字符串的长度<100。 输出说明 针对每个测试案例输出一列结果，结果为”Yes”或”No”。Yes表示该案例是回文，No表示该案例不是回文。 Sample ResultSample Input 2abbaabcd Sample OutputYesNo

Answer 1

#include <iosteam>
#include <string>
using namespace std;

#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--;
delete p;
}

return d;
}

int main(void)
{
data input[MAX];
stack temp;
int i = 0;
int flag = 0;

initialize(&temp); //初始化临时栈
cin>>&input; //输入字符串

while (input[i] != '@')
{//字符串入栈
push(input[i], &temp);
i++;
}

while (!empty(&temp))
{//字符依次出栈和字符数组比较，判断是否回文数
if (temp.top->d == input[flag])
{
pop(&temp);
flag++;
}
else
{
cout<<"此字符序列不是回文数!\n";
break;
}
}

if (empty(&temp))
cout<<"此字符序列是回文数!\n";

return 1;
}