数据结构：回文判断_数据结构回文的判断代码

7-1 回文判断
回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。

输入格式:
输入待判断的字符序列，按回车键结束，字符序列长度<20。

输出格式:
若字符序列是回文，输出“YES”；否则，输出“NO”。

输入样例:
abdba

输出样例:
YES

#include<iostream>
#include<cstring>
using namespace std;
#define maxsize 20
/*顺序栈的定义*/
typedef struct {
	int stacksize;//栈的长度
	char *base;//栈底指针
	char *top;//栈顶指针
} sqStack;
/*顺序栈的初始化*/
int initStack(sqStack &s) {
	s.base=new char[maxsize];//为顺序栈动态分配一个最大容量为maxsize的数组空间
	if(!s.base)//分配储存失败，直接结束进程
		exit(-2);
	s.top=s.base;//初始化，栈顶指针为base，即初始化为空栈
	s.stacksize=maxsize;//栈的最大容量
	return 1;
}
/*入栈操作*/
int push(sqStack &s,char e) {
	if(s.top-s.base==s.stacksize)//栈满判断条件
		return 0;
	*(s.top++)=e;//先赋值，再自增
	return 1;
}
/*出栈*/
int pop(sqStack &s) {
	char e;
	if(s.top==s.base)//栈为空，直接结束
		return 0;
	e=*(--s.top); //先自减，并且将元素赋给e
	return e;
}
/*分奇数和偶数，奇数去除中间的字符然后判断，偶素直接判断*/
/*回文判断*/
int huiwen(char *p) { //将数组
	sqStack s;
	int flag=1;//标识，1代表是回文，0代表不是回文
	initStack(s);
	int i=1,j;
	int len=strlen(p);//数组的长度
	while(i<=len/2) {
		push(s,*p);
		i++;
		*p++;

	}
	if(len%2==1)//若是奇数位字符串，直接将中间字符略过
		*p++;
	for(j=i-1; j>=1; j--) { //跳出循环时，i的值大了一
		char a;
		a=pop(s);
		if(*p==a)
			*p++;
		else
			flag=0;
	}
	return flag;
}

int main() {
	char p[21];
	cin>>p;
	if(huiwen(p))
		cout<<"YES";
	else
		cout<<"NO";
	return 0;
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74