内容:
回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。
步骤：
- 算法分析
本算法利用数组和栈实现，其主要思路为将从键盘输入的所有元素入栈，然后依次出栈与数组元素比较。主要步骤为键盘输入需要判断的字符串存放在数组中，然后将数组中的元素依次进栈，栈顶元素出栈与数组元素进行比较，若为回文序列，则输出“该字符串是回文序列”，否则输出“该字符串不是回文序列”。其中利用到数据结构中所学的栈这一线性表，包括顺序栈的定义、初始化、判空、判断栈是否已满溢出、如何进栈和出栈等内容。设计了函数IsHuiwen()来判断用户从键盘输入的字符串是否为回文序列，
2.概要设计
使用C语言，其中设置了以下函数
程序运行流程图如下：
3.测试（设计测试用例或测试代码的设计与实现，测试结果截屏））
设计测试用例如下图：
测试用例涵盖：输入回文序列类型的字符串和非回文序列类型的字符串等问题，提供较多测试用例，保证测试效果。
结果截图：
4.源码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100//假定预分配的栈空间最多为100
#define n 100//定义数组长度
typedef char elem;//假定栈元素的数据类型为字符
typedef struct SeqStack {
elem data[MAXSIZE];//创建数组栈
int top;//定义栈顶指针
} SeqStack;
//顺序栈初始化
int Init_SeqStack(SeqStack *&S) {
S = (SeqStack*)malloc(sizeof(SeqStack));//分配空间
if(S == NULL) {
printf("申请分配空间失败\n");
return 0;//失败返回0，否则返回1
}
S -> top = -1;//将-1赋值给栈顶指针
return 1;
}
//判断是否栈满溢出
int Full_SeqStack(SeqStack *S) {
if(S -> top == MAXSIZE -1) {
return 1;//栈满返回1，否则返回0
} else {
return 0;
}
}
//判断栈是否为空
int Empty_SeqStack(SeqStack *S) {
if(S -> top == -1) {
return 1;//栈空返回1，否则返回0
} else {
return 0;
}
}
//元素进栈
void Push_SeqStack(SeqStack *&S, elem e) {
if(Full_SeqStack(S) == 1) { //判断栈是否已满
printf("栈已满，进栈失败\n");
return;
}
S -> top++;//栈顶指针+1
S -> data[S -> top] = e;//元素进栈
}
//出栈
int Pop_SeqStack(SeqStack *S, elem &e) {
if(Empty_SeqStack(S) == 1) { //判断栈是否为空
printf("该栈为空栈\n");
return 0;//为空栈返回0，出栈失败
}
e = S -> data[S -> top];//栈顶元素出栈
S -> top--;//栈顶指针减一
return 1;//出栈成功返回1
}
//判断是否为回文
int IsHuiwen(elem a[]) {
elem e;
SeqStack *S;
Init_SeqStack(S);//初始化顺序栈
for(int i = 0; a[i]; i++)//数组中的元素依次进栈
Push_SeqStack(S, a[i]);
for(int i = 0; a[i]; i++) { //顺序栈中栈顶元素依次出栈
Pop_SeqStack(S, e);
if(a[i] != e)//判断a[i]是否与栈顶元素相同
return 0;//不相同直接返回0
}
return 1;
}
int main() {
printf("请输入需要判断的字符串\n");
elem a[n];//定义长度为n的
gets(a);//键盘输入需要判断的字符串
if(IsHuiwen(a)) { //如果IsHUiwen(a)的返回值为1,则输出"该字符串是回文序列"
printf("该字符串是回文序列\n");
} else { //否则输出"该字符串不是回文序列"
printf("该字符串不是回文序列\n");
}
return 0;
}
