1 #include<iostream> 2 #include<cstdlib> 3 using namespace std; 4 5 //顺序栈定义 6 #define OK 1 7 #define ERROR 0 8 #define OVERFLOW -2 9 #define MAXSIZE 100 10 typedef int Status; 11 typedef char SElemType; 12 typedef struct 13 { 14 SElemType *base; 15 SElemType *top; 16 int stacksize; 17 } SqStack; 18 19 //算法：顺序栈的初始化 20 Status InitStack(SqStack &S) 21 { 22 // 构造一个空的顺序栈 S 23 S.base = new SElemType[MAXSIZE]; //将base指向新申请的栈数组中 24 if(!S.base) exit(OVERFLOW); //申请失败，则异常退出 25 S.top = S.base; //将栈底指针赋给栈顶指针，表示空栈 26 S.stacksize = MAXSIZE; //栈能容纳的最大容量 27 return OK; //申请成功 28 } 29 //算法：顺序栈的入栈 30 Status Push(SqStack &S, SElemType &e) 31 { 32 if(S.top-S.base==S.stacksize) //如果栈满 33 return ERROR; 34 // 插入元素e为新的栈顶元素 35 *S.top++ = e; //先将元素压栈，栈顶指针指向下一个地址 36 return OK; //入栈成功 37 } 38 //算法：顺序栈的出栈 39 Status Pop(SqStack &S, SElemType &e) 40 { 41 // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR 42 if (S.base==S.top) //表示空栈 43 return ERROR; //返回错误 44 e = *--S.top; //先将栈顶指针减1，再取栈顶元素 45 return OK; //出栈成功 46 } 47 //算法：判断是否为回文 48 int HuiWen(SElemType *ch, int length) //ch接收回文字符串数组的基地址，length接收回文字符串长度 49 { 50 SqStack S; 51 SElemType x; 52 int i,j, m = length/2; 53 InitStack(S); //初始化栈S 54 for(i=0;i<m;++i) //先将字符数组前一半的元素压入栈中 55 Push(S,ch[i]); 56 for(j=length-m;j<length;j++){ //从一半后开始，会跳过奇数个数最中间那个数的比较 57 if(Pop(S,x) && x!=ch[j])break; //如果出栈成功 且出栈元素不和当前字符对应，则跳出 58 } 59 if(j!=length)return ERROR; //如果j不等于length 说明不是回文，返回0 60 return OK; //否则返回1 61 } 62 63 int main() 64 { 65 cout << " ********************判断是否为回文************************ "; 66 int i, length, flag = 1; 67 while (flag) 68 { 69 cout << "请输入一个数，代表回文字符串的长度："; 70 cin >> length; //length存放回文字符串长度 71 cout << "请输入" << length << "个字符："; 72 SElemType *ch = new SElemType[2 * MAXSIZE]; //ch存放回文字符串数组的基地址 73 for (i = 0; i < length; i++) 74 cin >> ch[i]; //给数组ch 输入用以判断的字符串 75 cout << "您要判断的字符串是："; 76 for (i = 0; i < length; i++) 77 cout << ch[i]; //显示数组ch 中的字符串 78 if (HuiWen(ch, length)) 79 cout << "，此字符串是回文！ " ; //HuiWen()是判断回文的函数，是回文返回1 ，不是回文返回0 80 else 81 cout << "，此字符串不是回文！ " ; 82 cout << "继续判断，输入1，否则输入0："; 83 cin >> flag; 84 } 85 return 0; 86 }