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

《天津理工大学数据结构实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验（二）实验名称栈与队列应用软件环境Windows98/2000,VC++6.0或turboC硬件环境PⅡ以上微型计算机实验目的理解栈和队列的逻辑特点，掌握栈或队列基本操作的实现，能运用栈或队列解决实际应用问题。实验内容（应包括实验题目、实验要求、实验任务等）所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，didpopIwasable,elbasawI等等。编写程序，实现一个栈，并利用它判断一个字符串是否是回文。实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：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，输出

4、did是回文输入字符串长度21，输入字符串Iwasable，elbasawI，输出Iwasable，elbasawI是回文。实验中曾出现的问题，在主函数字符串的输入以下标0开始，可是下标为0的字符却不是输入的第一个字符，输入是从下标为1的字符开始，改正后，字符的输出和入栈都从下标为1的字符开始。附录（可包括源程序清单或其它说明）#include#include#defineStackInitSize100typedefstruct{//顺序栈的储存结构chardata[StackInitSize];inttop;}SeqS

5、tack;SeqStack*InitStack(){//栈的初始化SeqStack*s;s=(SeqStack*)malloc(sizeof(SeqStack));if(s!=NULL){s->top=-1;returns;}else{printf("没有足够的内存空间，申请失败，程序运行终止！");exit(0);}}intIsEmpty(SeqStack*s){//判断栈是否为空return(s->top==-1)?1:0;}voidDestroyStack(SeqStack*s){//销毁栈free(s);printf("栈已销毁！");}voi

6、dPush(SeqStack*s,charx){//进栈if(s->top==StackInitSize){printf("栈满！程序运行终止！");exit(0);}else{s->top++;s->data[s->top]=x;}}charPop(SeqStack*s){//退栈chartemp;if(IsEmpty(s)){printf("栈空！程序运行终止！");exit(0);}else{temp=s->data[s->top];s->top--;returntemp;}}intjudge_huiwen(chara[],intn){//判断一

7、个字符串是否是回文SeqStack*s;s=InitStack();inti=1,j=1;while(i<=n/2){Push(s,a[i]);i++;}if(n%2!=0)i++;while(i<=n&&j==1){if(a[i]==Pop(s))i++;else{j=0;break;}}returnj;}voidmain(){chara[100];inti=0,n;printf("请先输入一个字符串的长度：");scanf("%d",&n);printf("请输入字符串：");for(i=0;i<=n;i++)scanf("%c",&a[i]);for(i

8、=1;i<=n;i++)printf(