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

《利用链式堆栈和队列实现回文判断》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

武汉大学实验报告资源与环境科学院系地理信息系统专业2013年12月22号实验名称利用链式堆栈和队列实现回文判断指导老师游涟姓名冯萱班级地信三班学号2012301130082成绩一、实验原理利用链式队列先进先出的特点和链式堆栈的先进后出的特点可以很容易的判断一个字符串是不是回文的，本实验利用了这些特点完成了队列和堆栈的创建和初始化、定义、入队入栈、出队出栈、取栈顶元素队头元素，以及撤销队列和堆栈等函数并实现调用二、实验目的熟练运用堆栈和队列的各种操作，并会运用他们的特点做一些实际的应用。二、实验步骤：1、把堆栈的创建及操作函数放到LStack头文件下：1：定义节点结构体：typedefstructsnode{DataTypedata;structsnode*next;}StNode;2：初始化堆栈：voidStackInitiate(StNode**head){if((*head=(StNode*)malloc(sizeof(StNode)))==NULL)exit(1);(*head)->next=NULL;}3：判断堆栈非空：intStackNotEmpty(StNode*head){if(head->next==NULL)return0;elsereturn1;} 4：入栈函数：intStackPush(StNode*head,DataTypex){StNode*p;if((p=(StNode*)malloc(sizeof(StNode)))==NULL){printf("内存空间不足无法插入! ");return0;}p->data=x;p->next=head->next;head->next=p;return1;}5：出栈函数：intStackPop(StNode*head,DataType*d){StNode*p=head->next;if(p==NULL){printf("堆栈已空，出错!");return0;}head->next=p->next;*d=p->data;free(p);return1;}6：取栈顶元素：intStackTop(StNode*head,DataType*d){StNode*p=head->next;if(p==NULL) {printf("堆栈已空出错!");return0;}*d=p->data;}7：撤销堆栈：voidDestory(StNode*head){StNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;free(p1);}}1、把对队列的创建及操作函数放到LQueue头文件下：1：头结点结构体的创建：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;2：队首队尾指针结构体的创建：typedefstruct{LQNode*front;LQNode*rear;}LQueue;3：初始化队列：voidQueueInitiate(LQueue*Q) {Q->rear=NULL;Q->front=NULL;}4：判断队列非空：intQueueNotEmpty(LQueueQ){if(Q.front==NULL)return0;elsereturn1;}5：入队函数：intQueueAppend(LQueue*Q,DataTypex){LQNode*p;if((p=(LQNode*)malloc(sizeof(LQNode)))==NULL){printf("内存空间不足! ");return0;}p->data=x;p->next=NULL;if(Q->rear!=NULL)Q->rear->next=p;Q->rear=p;if(Q->front==NULL)Q->front=p;return1;}6:删除队列元素：intQueueDelete(LQueue*Q,DataType*d){LQNode*p;if(Q->front==NULL){printf("队列已空无数据可删! "); return0;}else{*d=Q->front->data;p=Q->front;Q->front=Q->front->next;if(Q->front==NULL)Q->rear=NULL;free(p);return1;}}7：得到队列元素：intQueueGet(LQueueQ,DataType*d){if(Q.front==NULL){printf("队列已空无数据可取！ ");return0;}else{*d=Q.front->data;return1;}}8:撤销队列：voidDestory(LQueueQ){LQNode*p,*p1;p=Q.front;while(p!=NULL){ p1=p;p=p->next;free(p1);}}1、源程序：实现了对以上头文件函数的调用和实现：#include#include#include#include#includetypedefcharDataType;#include"LQueue.h"#include"LStack.h"voidHuiWen(charstr[]){LQueuemyqueue;StNode*mystack;charx,y;inti,length;length=strlen(str);QueueInitiate(&myqueue);StackInitiate(&mystack);for(i=0;i#include#include#includetypedefintDataType;#include"SLNode.h"#include"Stack.h"voidmain(){SLNode*la,*lb;intx,i;inta[10];ListInitiate(&la);ListInitiate(&lb);for(i=0;i<10;i++){if(ListInsert(la,i,i+1)==0){printf("Error ");return;}}printf("输出la： ");for(i=0;i