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

一、设计题目：编写程序判定一个字符串是否为回文？如“123454321”为回文，“asdfgsa”不是回文。二、设计要求：根据设计题目写出设计思想，选用适合数据逻辑结构、物理结构。根据设计题目写出算法描述和算法。根据课程设计要求打印报告并进行答辩。三、概要设计（程序流程图）：首先建立一个字符数组，长度为254，然后向数组中写入索要判断的字符串。定义两个指针，一个指向队头，一个指向队尾，队头的指针不断递增，队尾的指针不断递减，在P1<P2的前提下，两个地址上的数据进行比较，如相等则两地址分别向中间靠拢，如对比的结果不同则跳出，但此时P1指针小于P2指针，所以判断字符串不是回文；如两者一直相等直到他们的地址P1二P2或P1〉P2（字符串为奇数个）时，跳出并判断为回文；在这其中P1指针的值与P2指针的值有不等的情况就直接判定不是回文。四、程序代码测试及结果分析：#include<stdio.h>#include<string.h>intmain(void){charstr[254];printf("请输入字符串：");gets(str); //输入字符char*p1=str,*p2=str+strlen(str)-1;//指针定义for(;pl<p2&&*p1==*p2;++pl,—p2);//FOR循环体为空puts(p1<p2?"所输字符串不是回文":"所输字符串是回文");return0;}*C:\Docu>entsandSettings\AdA±nistrator\Debug\Cpp1.exe填输入字符串：1貂454眈1嶄输字符串是回文Pressanvkeytocontinue结果分析：如上图例子，在输入123454321时，P1指向第一个1的地址，P2指向最后一个1的地址，FOR语句循环前无定义且为空语句，此时?1〈p2且*p1==*p2，继续循环执行循环体为空；以此类推，当程序执行至5次循环，也就是P1和P2的指针都在5的位置时，不满足循环条件pl<p2&&*p1二二*p2中的pl<p2,跳出循环，此时同样三目运算符（pl<p2?"所输字符串不是回文〃：〃所输字符串是回文"）中的pl<p2也不满足其值为假，所以输出为“所输字符串是回文”。在输入asdfgsa时，P1指向第一个a的地址，P2指向最后一个a的地址，FOR语句循环前无定义且为空语句，此B"p1<p2且*p1==*p2，继续循环执行循环体为空；以此类推，当执行两次++P1,—P2之后，P1指向d的地址，P2指向g的地址，这时不满足循环条件pl<p2&&*p1==*p2中的*p1==*p2,跳出循环，进行下一条语句：puts（pl<p2?所输字符串不是回文〃：〃所输字符串是回文’）；，此时pl<p2,执行结果为真的语句，所以输出"所输字符串不是回文"。五、设计总结：通过本次的课程设计，我明白了什么是回文，如何用C语言编写一个程序判断所输入的字符串是否为回文，以及怎么样最简单的简化程序的代码。这里的回文就是把回文是指正读和反读均相同的字符序列，所以可以用程序将字符串颠倒后与原字符串相比较，所用到的数据结构有单链表和栈，单链表用于存储字符串，栈用于对单链表中字符串的判定。先构造空栈，再将单链表存储的字符串中的前一半字符进栈，将栈中的字符逐个与单链表中的后半部分的字符进行比较。如果字符全部相等，则判定字符串是回文；如果有一个字符不相等，则判定字符串不是回文。也可以用首尾对比的方法较简单，将两个指针分别指向字符串的头地址和尾地址，两者中的数据相比较，如相等则两地址分别向中间靠拢，如对比的结果不同则跳出，但此时P1指针小于P2指针，所以判断字符串不是回文；如两者一直相等直到他们的地址P1二P2或P1〉P2（字符串为奇数个）时，跳出并判断为回文；在这其中n指针的值与P2指针的值有不等的情况就直接判定不是回文。通过本次课程设计，既让我复习了像堆栈和链表之类的数据结构，也锻炼和提高了我动手应用编毎语言程序的能力，让我受益匪浅。虽然程序很短，我也遇到了许多困难，在不断的试验和调试过程中更让我明白了有些事情看似简单，做起来并不容易的道理，道理容易明白，实际动手去做起来并不简单，要想学好数据结构和C,勤于的编写代码动手操作的重要性。六、参考资料：《数据结构（C语言版）》，严蔚敏等编著，清华大学出版社,2007.4《算法与数