实验 二 栈和队列的基本操作实现及其应用

《实验 二 栈和队列的基本操作实现及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件114班李大宝201100834416数据结构实验报告（二）姓名:李大宝学院：计算机学院班级：软件114班第26页软件114班李大宝201100834416实验二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。2、会用栈和队列解决简单的实际问题。二、实验内容题目一试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。一、相关常量及结构定义：#defineSTACK_INIT_SIZ

2、E100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefcharSElemType;//把char类型定义为SElemType//栈类型定义typedefstructSqStack{SElemType*base;//栈底SElemType*top;//栈顶intstacksize;//最大容量}SqStack;//队列类型定义typedefstructQNode{SElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstr

3、uct{QueuePtrfront;//队首QueuePtrrear;//队尾}LinkQueue;二、设计相关函数声明：判断函数：intIsReverse()栈：intInitStack(SqStack&S)intPush(SqStack&S,SElemTypee)intPop(SqStack&S,SElemType&e)intStackEmpty(s)第26页软件114班李大宝201100834416队列；intinitqueue(LinkQueue&Q)intEnQueue(LinkQueue&Q,SElemTypee)intD

4、eQueue(LinkQueue&Q,SElemType&e)三、函数说明：1、栈初始化/*函数功能：对栈进行初始化参数：栈(SqStack&S)成功初始化返回1,否则返回0*/intInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//对栈申请空间。if(!S.base)exit(0);//未申请空间退出。S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}2、弹出栈顶元

5、素，并返回/*函数功能：对栈删除栈顶元素参数：栈SqStack&S,元素SElemType&e用e返回栈顶元素*/intPop(SqStack&S,SElemType&e){if(S.top==S.base)//栈为空时返回错误。returnERROR;e=*--S.top;//成功返回栈顶元素returnOK;}3、向栈中压入元素/*函数功能：向栈中压入元素参数：栈SqStack&S,元素SElemTypee成功压入返回1，否则返回0*/intPush(SqStack&S,SElemTypee){if(S.top-S.base>=S

6、.stacksize)//栈的大小过小时，从新申请内存{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}第26页软件114班李大宝201100834416*S.top++=e;//成功压入元素。returnOK;}4、栈是否为空/*函数功能：判断栈是否为空参数：栈SqStack

7、S为空返回1，否则返回0*/intStackEmpty(SqStackS){if(S.top==S.base)//为空条件S.top=S.basereturnOK;elsereturnERROR;//不空返回0}5、队列初始化/*函数功能：对队列进行初始化参数：队列(LinkQueue&Q)成功初始化返回1,否则返回0*/intinitqueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(ERROR);Q.front->ne

8、xt=NULL;returnOK;}6、入队/*函数功能：对队列进行入队参数：队列LinkQueue&Q，元素SElemTypee成功入栈返回1*/intEnQueue(LinkQueue&Q,SElemTypee){Q