回文判断

设计题目二：3.4.4回文判断P591.设计要求1.1问题描述试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含字符“&”，且序列2是序列1的逆序列。例如：“a+b&b+a”是属该模式的字符序列，而“1+3&3-1”则不是。1.2需求分析这是一个利用栈结构完成的程序。为了实现算术优先算法，我们使用两个工作栈，一个称为操作符栈（OPTR）,用以寄存运算符；一个称为操作数栈（OPND），用以寄存操作数或运算结果。算法的基本思想是：（1）输入测试数据组数，接着分组输入字符串，以@结尾。（2）输入序列总长不超过(MAX_N=10005)/2个。将序列1先入栈，接着处理序列2，同时出栈判断。（3）将序列1全部入栈，接着输入序列2，同时出栈判断。（4）如果序列满足题目要求，则输出“回文序列”；否则，输出“非回文序列”。（5）测试数据：qwer&rewq@qwerrewq@qwer&rewq12364&23131@2.概要设计2.1主界面设计回文判断的程序界面设计并不复杂，有提示字符串输入及结束符号的信息即可。运行界面如下图所示：图2.12.2数据结构本系统采用顺序栈结构类型(stack)存储用户输入的字符串以便判断是否为回文。typedefstruct{charelem[Stack_Size];//用来存放栈中元素的一维数组inttop;//用来存放栈顶元素的下标}SeqStack;使用结构体，内部定义数组模拟栈。top为栈顶指针，指向当前元素的下一个位置。3模块设计3.1模块设计：本程序包含3个模块：主程序模块，判断模块，和顺序栈操作模块，调用关系如下：主程序回文判断模块顺序栈操作模块图2.23.2功能模块的调用关系图图2.3调用关系图3.3系统子程序及功能设计本系统共设置6个函数，其中主要包括主函数。其中主要的函数及功能说明如下。voidInitStack(SeqStack*S)//栈的初始化intIsEmpty(SeqStack*S)//判断栈是否为空intPush(SeqStack*S,charx)//入栈intPop(SeqStack*S,char*x)//出栈intplalindrome(char*b)//回文判断intmain()//主函数4详细设计是主函数main()InitStack()Pop()Push()回文判断plalindrome()IsEmpty()提示输入输出结果，并提示是否继续调用返回结果退出程序4.1数据类型定义（1）栈的结构体定义typedefstruct{charelem[Stack_Size];//用来存放栈中元素的一维数组inttop;//用来存放栈顶元素的下标}SeqStack;（2）全局变量定义#defineN20//定义接收字符串的最大长度#definetrue1//定义bool类型的true为1#definefalse0//定义bool类型的false为0#defineStack_Size50//定义栈的大小为504.2系统主要子程序详细设计（1）主函数模块设计（1）主函数模块voidmain(){输入字符串调用函数输出结果是否继续？}（2）函数模块设计A．创建头结点；B．进栈；主程序输入字符串输出判断字符串长度进栈出栈C．出栈，判断是否为回文(3)函数具体实现①构造一个空栈SvoidInitStack(SeqStack*S){S-top=-1;}②判断栈是否为空intIsEmpty(SeqStack*S){return(S-top==-1?1:0);}③入栈操作intPush(SeqStack*S,charx){if(S-top==Stack_Size-1)return(false);//栈已满S-top++;S-elem[S-top]=x;return(true);}④出栈操作intPop(SeqStack*S,char*x){//将栈S的栈顶元素弹出，放到x所指的存储空间中if(S-top==-1)//栈为空return(false);else{*x=S-elem[S-top];S-top--;/*修改栈顶指针return(true);}}⑤回文判断intplalindrome(char*b){charch;intk;SeqStackS;k=0;InitStack(&S);//初始化while(b[k]!='&')//字符串是否有‘&’字符{Push(&S,b[k]);k++;}k++;while((!IsEmpty(&S))&&(b[k]!='@'))//是否以‘@’结尾{Pop(&S,&ch);if(b[k]!=ch)return(0);elsek++;}if(b[k]=='@'&&IsEmpty(&S))return(1);}5测试分析（1）测试环境：vc++6.0（2）输入过程：因为使用getchar()输入，所以有些地方需要谨慎处理。用于getchar()可以读入任意字符，所以回车和空格之类的特殊字符也作为序列参与判断了。（3）测试结果：如图所示图2.4正确输入回文字符串示意图图2.5图2.6不按规则输入的示意图图2.7正确输入非回文字符串示意图6用户手册(1).本程序执行文件为“回文判断.exe”(2)进入本系统之后，随即显示系统主界面，用户可在该界面输入要测试回文的字符串（需要按照一定规则输入），并按回车键，会提示是否为回文字符串，并提示是否继续测试。7调试报告1．调试中遇到的问题及对问题的解决方法；对于语句中的一般回文单词能正常输出，句末跟标点符号连在一起的回文单词也能通过程序把字符串末尾的标点给去掉并正常输出，而字符串中的连接符可以作为回文单词的组成部分一起输出。其中如果输入中文，都是非回文字符串，这是程序的不足之处，时间匆忙，没有用太多的时间去考虑。2．算法的时间复杂度和空间复杂度。时间复杂度为O（n）；空间复杂度为O（n）3．整个程序我使用了while的循环方法可以是程序重复判断，这是出于我调试的过程中经常需要判断一些字符串是否为回文，以确定程序是否没有问题，不过我也是考虑到了这个程序能更人性化才有的这样的功能！8程序清单#defineN20//设置常量#definetrue1//设置booltrue的值为1#definefalse0//设置boolfalse的值为2#defineStack_Size50//定义栈的大小为50#includestdio.h#includeconio.htypedefstruct{charelem[Stack_Size];//用来存放栈中元素的一维数组inttop;//用来存放栈顶元素的下标}SeqStack;voidInitStack(SeqStack*S)//构造一个空栈S//{S-top=-1;}intIsEmpty(SeqStack*S){//判栈S为空栈时返回值为真，反之为假return(S-top==-1?1:0);//三目运算}intPush(SeqStack*S,charx){if(S-top==Stack_Size-1)return(false);//栈已满S-top++;//修改栈顶指针S-elem[S-top]=x;//push操作return(true);//返回push是否成功的bool类型}intPop(SeqStack*S,char*x){/*/将栈S的栈顶元素弹出，放到x所指的存储空间中if(S-top==-1)//栈为空return(false);else{*x=S-elem[S-top];//pop操作S-top--;//修改栈顶指针return(true);}}intplalindrome(char*b){charch;intk;SeqStackS;k=0;InitStack(&S);//初始化while(b[k]!='&')//字符串是否有‘&’字符{Push(&S,b[k]);k++;}k++;while((!IsEmpty(&S))&&(b[k]!='@'))//是否以‘@’结尾{Pop(&S,&ch);if(b[k]!=ch)return(0);elsek++;}if(b[k]=='@'&&IsEmpty(&S))return(1);}main(){intm,n,i,flag;chara[N];flag=1;do{m=n=i=0;printf(\n请输入一个字符串(以字符'@'结束输入)\n);scanf(%s,a);for(i=1;a[i];i++)if(a[i]=='@')m++;if((m==1)&&(a[i-1]=='@'))m=1;for(i=1;a[i];i++)if(a[i]=='&')n++;if(n==1)n=1;elsen=0;if(m&&n)i=plalindrome(a);if(i==1){i=0;printf(\n\t这是回文字符串!\n\n请问是否继续(y|n?));getchar();}else{printf(\n\t这不是回文字符串!\n\n\t请问是否继续(y|n)?);getchar();}if(getchar()=='y')//继续测试flag=1;else//退出程序{printf(“谢谢使用！再见！”);flag=0;}}while(flag);}