利用链式堆栈和队列实现回文判断.docx

武汉大学实验报告资源与环境科学院 系 地理信息系统 专业 2013年12月22号实验名称利用链式堆栈和队列实现回文判断指导老师游涟姓名冯萱班级地信三班学号2012301130082成绩一、 实验原理利用链式队列先进先出的特点和链式堆栈的先进后出的特点可以很容易的判断一个字符串是不是回文的，本实验利用了这些特点完成了队列和堆栈的创建和初始化、定义、入队入栈、出队出栈、取栈顶元素队头元素，以及撤销队列和堆栈等函数并实现调用二、实验目的熟练运用堆栈和队列的各种操作，并会运用他们的特点做一些实际的应用。二、 实验步骤：1、 把堆栈的创建及操作函数放到LStack头文件下： 1：定义节点结构体：typedef struct snodeDataType data;struct snode *next;StNode;2：初始化堆栈：void StackInitiate(StNode * head)if(*head=(StNode*)malloc(sizeof(StNode)=NULL) exit(1);(*head)-next=NULL;3：判断堆栈非空：int StackNotEmpty(StNode *head)if(head-next=NULL) return 0;elsereturn 1;4：入栈函数：int StackPush(StNode *head,DataType x)StNode *p;if(p=(StNode *)malloc(sizeof(StNode)=NULL)printf(内存空间不足无法插入!n);return 0;p-data=x;p-next=head-next;head-next=p;return 1;5：出栈函数：int StackPop(StNode *head,DataType *d)StNode *p=head-next;if(p=NULL)printf(堆栈已空，出错!);return 0;head-next=p-next;*d=p-data;free(p);return 1;6：取栈顶元素：int StackTop(StNode *head,DataType *d)StNode *p=head-next;if(p=NULL)printf(堆栈已空出错!);return 0;*d=p-data;7：撤销堆栈：void Destory(StNode *head)StNode *p,*p1;p=head;while(p!=NULL)p1=p;p=p-next;free(p1);2、 把对队列的创建及操作函数放到LQueue头文件下：1：头结点结构体的创建：typedef struct qnodeDataType data;struct qnode *next;LQNode;2：队首队尾指针结构体的创建：typedef structLQNode *front;LQNode *rear;LQueue;3：初始化队列：void QueueInitiate(LQueue *Q) Q-rear = NULL;Q-front = NULL;4：判断队列非空：int QueueNotEmpty(LQueue Q)if(Q.front=NULL) return 0;else return 1;5：入队函数：int QueueAppend(LQueue *Q,DataType x)LQNode *p;if(p=(LQNode *)malloc(sizeof(LQNode)=NULL)printf(内存空间不足!n);return 0;p-data=x;p-next=NULL;if(Q-rear!=NULL) Q-rear-next=p;Q-rear=p;if(Q-front=NULL) Q-front=p;return 1;6:删除队列元素：int QueueDelete(LQueue *Q,DataType *d)LQNode *p;if(Q-front=NULL)printf(队列已空无数据可删!n);return 0;else*d=Q-front-data;p=Q-front;Q-front=Q-front-next;if(Q-front=NULL) Q-rear=NULL;free(p);return 1;7：得到队列元素：int QueueGet(LQueue Q,DataType *d)if(Q.front=NULL)printf(队列已空无数据可取！n);return 0;else*d=Q.front-data;return 1;8:撤销队列：void Destory(LQueue Q)LQNode *p,*p1;p=Q.front;while (p!=NULL)p1=p;p=p-next;free(p1);3、 源程序：实现了对以上头文件函数的调用和实现：#include#include#include#include#includetypedef char DataType;#includeLQueue.h#includeLStack.hvoid HuiWen(char str)LQueue myqueue;StNode *mystack;char x,y;int i,length;length=strlen(str);QueueInitiate(&myqueue);StackInitiate(&mystack);for(i=0;ilength;i+)QueueAppend(&myqueue,stri);StackPush(mystack,stri);while(QueueNotEmpty(myqueue)=1&StackNotEmpty(mystack)=1)if(QueueDelete(&myqueue,&x)=1&StackPop(mystack,&y)=1&x!=y)printf(%s不是回文!n,str);return;if(QueueNotEmpty(myqueue)|StackNotEmpty(mystack)printf(%s不是回文!n,str);elseprintf(%s是回文!n,str);void main()char str1=ABCDEDCBA;char str2=ABCDEDCAB;HuiWen(str1);HuiWen(str2);Sleep(10000);4、 实验结构如图：二：源程序实现函数的调用：#include#include#include#includetypedef int DataType;#includeSLNode.h#includeStack.hvoid main()SLNode *la,*lb;int x,i;int a10;ListInitiate(&la);ListInitiate(&lb);for(i=0;i10;i+) if(ListInsert(la,i,i+1)=0)printf(Errorn);return;printf(输出la：n);for(i=0;iListLength(la);i+)if(ListGet(la,i,&x)=0)printf(Errorn);return;else printf(%d ,x);printf(n);printf(输出就地逆置la:n);JiudiReserve(la);for(i=0;iListLength(la);i+)if(ListGet(la,i,&x)=0)printf(Errorn);return;else printf(%d ,x);printf(n);printf(再用返回lb逆置输出为:n);lb=SLNodeReserv