数据结构实验报告二.doc

《数据结构实验报告二.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告《数据结构与算法》实验报告题目：实验二栈与队列日期 2012年9月24日班级学号姓名李中明成绩实验环境： WindowsXPVC++6.0实验内容与完成情况： 1．设单链表中存放n个字符,设计一个算法,使用栈判断该字符串是否中心对称,如abccba即为中心对称字符串.提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用bj()函数判断是否为中心对称字符串。在bj（）函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。#include#include#defineMaxLen1

2、00typedefstructnode{chardata;structnode*next;}cnode;cnode*create(chars[]){inti=0;cnode*h,*p,*r;while(s[i]!=''){p=(cnode*)malloc(sizeof(cnode));p->data=s[i];p->next=NULL;if(i==0){h=p;r=p;}else{r->next=p;r=p;}i++;}returnh;}intjudge(cnode*h){charst[MaxLen];inttop=0;cnode*p=h;while(

3、p!=NULL){st[top]=p->data;top++;p=p->next;}p=h;while(p!=NULL){top--;if(p->data==st[top])p=p->next;elsebreak;}if(p==NULL)return1;elsereturn0;}voidmain(){charstr[MaxLen];cnode*h;printf("输入一个字符串：");scanf("%s",str);h=create(str);if(judge(h)==1)printf("str是中心对称字符串");elseprintf("str不是中

4、心对称字符串");}输入一个字符串：abccba输出：str是对称字符串 2．假设以数组sequ[0..MaxSize-1]存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。试写出此环形队列队满的条件，并设计相应入队和出队的算法。#include#definemaxsize6typedefcharqueue[maxsize];intrear=0,len=0;intenqueue(queuequ,charx){if(len==maxsize)return0;else{rear=(rear+1

5、)%maxsize;qu[rear]=x;len++;return1;}}intdequeue(queuequ,char*x){intfront;if(len==0)return0;else{front=(rear-len+1+maxsize)%maxsize;*x=qu[front];len--;return1;}}voidmain(){charx;queuequ;printf("a入队");enqueue(qu,'a');printf("b入队");enqueue(qu,'b');printf("c入队");enqueue(qu,'c');

6、printf("出队一次：");dequeue(qu,&x);printf("%c",x);printf("d入队");enqueue(qu,'d');printf("e入队");enqueue(qu,'e');printf("出队一次：");dequeue(qu,&x);printf("%c",x);printf("f入队");enqueue(qu,'f');printf("g入队");enqueue(qu,'g');printf("出队一次：");dequeue(qu,&x);printf("%c",x);printf("余

7、下元素出列：");while(len>0){dequeue(qu,&x);printf("%c",x);}printf("");}余下元素出列：defg出现的问题及解决方法：1.为了使存储空间能得到充分的利用，我们所创建的队列都是循环队列。该环形队列对满的条件为：len==MaxSize，队空的条件为：len==0。并且、由rear,len求队列头指针front的过程为：front=rear-len+1；if(front<0)front=front+MaxSize；即front=(rear-len+1+MaxSize)%MaxSize当进行插入和删

8、除运算后，队尾指针算法：rear=（rear+1）%Maxsize