栈定义及其应用

《栈定义及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集美大学数据结构课程实验报告课程名称：数据结构班级：实验成绩：2012.3.20指导教师：姓名：实验项目名称：数据结构---栈学号：2011872070上机实践日期：12.3.24一、目的理解栈数据结构及其应用；理解递归及其应用二、实验内容1．栈的类定义（已实现，可参考附录：seqstack.h）2．顺序栈的类定义、实现与测试（已实现，可参考：seqstack—seqstack.cpp,main—main主要是完成顺序栈各个方法的测试工作，测试结束可取消，因为一个工程只能有一个main）3．链栈的类定义、实现与测试4．栈的应用1（可使用顺序栈

2、或链栈完成）：实现括号匹配测试如下表达式:”{[()](())}”及”{[()]]}”5．栈的应用2（可使用顺序栈或链栈完成）：实现中缀表达式计算器，提示将表达式后缀表示并存储于一个数组中，再完成该后缀表达式运算测试：5*3+(2-4/6)的后缀，其余测试自已设置6．递归及应用1：使用递归顺序输出链表中的各元素数据。（链表的创建可使用实验1）7．递归及应用2:使用递归逆序输出链表中的各元素数据8．栈的应用3（可使用顺序栈或链栈完成）：使用递归的回溯法实现小型迷宫程序（提示：程序分为两大模块，根据数据生成地图，漫游地图）三、实验使用环境VC++

3、6.0控制台程序四、实验关键代码与结果展示（部分截图）1.顺序栈：SeqStack.h#include#includeusingnamespacestd;constintstackIncreament=20;templateclassSeqStack{public:SeqStack(intsz=50);~SeqStack(){delete[]elements;页脚}voidPush(constT&x);boolPop(T&x);boolgetTop(T&x)const;boolIsE

4、mpty()const{returntop==-1;}boolIsFull()const{returntop==maxSize-1;}intgetSize()const{returntop+1;}voidMakeEmpty(){top=-1;}friendostream&operator<<(ostream&out,SeqStack&s){out<<"栈顶指针位于:"<

5、ate:T*elements;inttop;intmaxSize;voidoverflowProcess();};templateSeqStack::SeqStack(intsz){top=-1;maxSize=sz;elements=newT[maxSize];assert(elements);}templatevoidSeqStack::overflowProcess(){T*newArray=newT[maxSize+stackIncreament];assert(newArray

6、);for(inti=0;i<=top;i++)newArray[i]=elements[i];maxSize=maxSize+stackIncreament;delete[]elements;页脚elements=newArray;}templatevoidSeqStack::Push(constT&x){if(IsFull())overflowProcess();elements[++top]=x;}templateboolSeqStack::Pop(T&x){if(IsEmpty(

7、)){returnfalse;}x=elements[top--];returntrue;}templateboolSeqStack::getTop(T&x)const{if(IsEmpty()){returnfalse;}x=elements[top];returntrue;}Main.cpp#include"SeqStack.h"#include#include#include#includeusingnamespacestd;intma

8、in(){SeqStacksta;ifstreamfin("data.txt");assert(fin);intdata;while(!fin.eof()