天津理工大学数据结构实验报告

1、实验（二）实验名称栈与队列应用软件环境Windows98/2000, VC+6.0或turbo C硬件环境P以上微型计算机实验目的理解栈和队列的逻辑特点，掌握栈或队列基本操作的实现，能运用栈或队列解决实际应用问题。实验内容（应包括实验题目、实验要求、实验任务等）所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，did pop I was able,elba saw I 等等。 编写程序，实现一个栈，并利用它判断一个字符串是否是回文。实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：1. 创建有关顺序栈的基本运算函数栈底的位置固定不变，栈顶的

2、位置随着进栈和退栈操作而动态变化，所以顺序栈需要一个变量top来指示当前栈顶的位置。1.1 初始化栈为顺序栈分配连续的栈空间，同时置空栈；1.2 判断栈是否为空栈空栈标志为：栈顶指针=栈底指针；1.3 销魂栈栈为空则返回1，否则返回0；1.4 进栈操作首先判断栈的状态，若未满，则top+1，然后将入栈元素置于栈顶指针top所指的存储单元中，使之指向新的栈顶，若栈满，发生“上溢”，程序退出。1.5 退栈操作首先判断栈的状态，若不空，则top-1，使其指向新的栈顶，若为空，发生“下溢”，程序退出。2. 运用顺序栈结构实现回文问题使用栈，将字符串的前一半入栈，再依次出栈，与后一半进行比较，若不相等，

3、则不是回文，否则是回文2.1 初始化栈s；2.2 利用i记录循环次数，i的初始值为1，循环直到i=字符串的一半时结束字符串下标为i的字符依次入栈。2.3 若字符串长度为偶数，i值不变，否则i+1；2.4 利用while循环，依次比较下标为i的字符串中的字符与出栈元素是否相等，以j=1，作为标志，若不等j=0并打断循环2.5 返回j的值，j=1，则字符串是回文，否则不是回文3. 主函数3.1 首先输入字符串的长度，然后依次输入字符；3.2 输出字符串；3.3 调用函数判断字符串是否是回文。结论：实验中，输入字符串长度3，输入字符串did，输出did是回文 输入字符串长度21，输入字符串I was

4、 able，elba saw I，输出I was able，elba saw I 是回文。实验中曾出现的问题，在主函数字符串的输入以下标0开始，可是下标为0的字符却不是输入的第一个字符，输入是从下标为1的字符开始，改正后，字符的输出和入栈都从下标为1的字符开始。附录（可包括源程序清单或其它说明）#include#include#define StackInitSize 100typedef struct /顺序栈的储存结构char dataStackInitSize;int top;SeqStack;SeqStack *InitStack() /栈的初始化SeqStack *s;s=(SeqS

5、tack *)malloc(sizeof(SeqStack);if(s!=NULL)s-top=-1;return s;else printf(没有足够的内存空间，申请失败，程序运行终止！n); exit(0);int IsEmpty(SeqStack *s) /判断栈是否为空return (s-top=-1)?1:0;void DestroyStack(SeqStack *s) /销毁栈free(s);printf(栈已销毁！n);void Push(SeqStack *s,char x) /进栈if(s-top=StackInitSize)printf(栈满！程序运行终止！n);exit(

6、0);elses-top+;s-datas-top=x;char Pop(SeqStack *s) /退栈char temp;if(IsEmpty(s)printf(栈空！程序运行终止！n);exit(0);elsetemp=s-datas-top;s-top-;return temp;int judge_huiwen(char a,int n) /判断一个字符串是否是回文SeqStack *s;s=InitStack();int i=1,j=1;while(i=n/2)Push(s,ai);i+;if(n%2!=0)i+;while(i=n&j=1)if(ai=Pop(s)i+;elsej=0;break;return j;void main()char a100;int i=0,n;printf(请先输入一个字符串的长度：);scanf(%d,&n);printf(请输入字符串：);for(i=0;i=n;i+)scanf(%c,&ai);for(i=1;i=n;i+) printf(%c,ai);if(judge_huiwen(a,n)printf(是回文。n);else printf(不是回文。n);运行结果： 天津理工大学计算机科学与工程系实验报告2011 至 20