数据结构课程设计-回文判断

1设计题目：3.4.4回文判断专业：****姓名：***学号：***日期：2011.09.11一，问题描述二，需求分析三，概要设计四，详细设计五，测试分析六，源程序清单七，用户使用手册八，心得体会2一、问题描述判断依次读入的一个以@为结束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2都不含“&”字符，且序列2是序列1的逆序列。二、需求分析（1）输入测试数据组数，接着分组输入字符串，以@结尾。（2）输入序列总长不超过(MAX_N=10005)/2个。将序列1先入栈，接着处理序列2，同时出栈判断。（3）将序列1全部入栈，接着输入序列2，同时出栈判断。（4）如果序列满足题目要求，则输出“回文序列”；否则，输出“非回文序列”。（5）测试数据：pal.txt12a+b&b+a@a&b@a&a@3&@&@&@&@ab&ba@abc&bc@bc&cba@&ab@ab&@三、概要设计（1）数据结构：typedefstructStack{inttop,size;charstr[MAX_N1];};使用结构体，内部定义数组模拟栈。top为栈顶指针，指向当前元素的下一个位置，size表示栈内的元素个数。（2）函数介绍：4voidst_init(Stack*st);//栈的初始化boolst_push(Stack*st,constchar*temp);//入栈boolst_top(Stack*st,char*temp);//出栈（3）程序流程图：++iNYstr[i]==’@’?strlen(str)==奇数开始读入字符，str[i]5YN序列1入栈对序列2进行判断，同时出栈处理，标记判断状态。flag非回文序列回文序列结束6四、详细设计主要出栈和入栈函数，可以对边界进行处理，防止栈为空情况。boolst_push(Stack*st,constchar*temp){if(st-topst-size)returnfalse;st-str[st-top++]=*temp;returntrue;}boolst_pop(Stack*st){if(st-top==0)returnfalse;st-top--;returntrue;}另外还有取栈顶函数。boolst_top(Stack*st,char*temp){if(st-top==0)returnfalse;7*temp=st-str[st-top-1];returntrue;}五、测试分析（1）测试环境：CodeBlock10.04（2）输入过程：因为使用getchar()输入，所以有些地方需要谨慎处理。用于getchar()可以读入任意字符，所以回车和空格之类的特殊字符也作为序列参与判断了。（3）测试结果：8910六、源程序清单#includestdio.h#includestring.h#includestdlib.hconstintMAX_N=10005;typedefstructStack{inttop,size;charstr[MAX_N1];};voidst_init(Stack*st){st-size=MAX_N1;st-top=0;}boolst_push(Stack*st,constchar*temp){if(st-topst-size)returnfalse;st-str[st-top++]=*temp;returntrue;}11boolst_pop(Stack*st){if(st-top==0)returnfalse;st-top--;returntrue;}boolst_top(Stack*st,char*temp){if(st-top==0)returnfalse;*temp=st-str[st-top-1];returntrue;}intmain(){charstr[MAX_N],c;inti,j,cas,len;Stackst;boolflag;//freopen(pal.txt,r,stdin);printf(请输入测试组数：\n);scanf(%d,&cas);getchar();j=0;while(cas--)12{++j;printf(\n第%d组数据……\n,j);printf(\n请输入数据（字符串1&字符串2@）：\n);for(i=0;1;i++){str[i]=getchar();if(str[i]=='@'){str[i]='\0';break;}}getchar();flag=true;len=strlen(str);st_init(&st);if(!len&1)flag=false;else{for(i=0;ilen;i++){if(str[i]=='&')13break;st_push(&st,&str[i]);}for(++i;ilen;i++){st_top(&st,&c);flag=st_pop(&st);if(c!=str[i]||!flag){flag=false;break;}}if(st.top0)flag=false;}printf(\nCase:%d\n,j);if(flag)printf(回文序列。\n);elseprintf(非回文序列。\n);printf(\n);}printf(输入结束。Bychangning.huang);//while(true);14return0;}七、用户使用手册（1）开始需要输入要测试的组数，这样方便结束，减少一些繁琐的结束判断。（2）因为定义了文件流，可以用文件方便的进行读写。如使用文件读写，稍微将以下语句注释掉：printf(请输入测试组数：\n);printf(\n第%d组数据……\n,j);printf(\n请输入数据（字符串1&字符串2@）：\n);当然，不需要的话，注释掉freopen(pal.txt,r,stdin);即可。（3）输入格式依照题目要求即可。