数据结构实验报告(实验三).doc

深圳大学实验报告课程名称:数据结构实验与课程设计实验项目名称:实验三:栈的应用学院:计算机与软件学院专业:指导教师:蔡平报告人:文成学号:2011150259 班级:5实验时间:2012-10-08实验报告提交时间:2012-10-20教务部制一、实验目的与要求:目的:、插入、删除、查找的实现方法要求:++++语言实现线性表地创建、插入、删除、查找的实现方法二、实验内容:ProblemA:数据结构——实验3——STL堆栈对象的例程TimeLimit:1SecMemoryLimit:128MBSubmit:103Solved:85[Submit][Status][WebBoard]Description掌握C++中STL自带的堆栈对象应用。演示堆栈对象的各种操作,以字符串的逆序输出为例子输入一个字符串,按输入顺序将字符压入堆栈,然后根据堆栈后进先出的特点,做逆序输出Input第一行输入t,表示有t个测试实例第二起,每一行输入一个字符串,bbaaHINTProblemB:数据结构——实验3——堆栈应用之括号匹配TimeLimit:1SecMemoryLimit:128MBSubmit:365Solved:120[Submit][Status][WebBoard]Description处理表达式过程中需要对括号匹配进行检验,括号匹配包括三种:“(”和“)”,“[”和“]”,“{”和“}”。例如表达式中包含括号如下:( ) [ ( ) ( [ ] ) ] { }1 2 3 4 5 6 7 8 9 10 11 12从上例可以看出第1和第2个括号匹配,第3和第10个括号匹配,4和5匹配,6和9匹配,7和8匹配,11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的,使用堆栈可以很方便的处理这种括号匹配检验,可以遵循以下规则:1、当接收第1个左括号,表示新的一组匹配检查开始;随后如果连续接收到左括号,则不断进堆栈。2、当接受第1个右括号,则和最新进栈的左括号进行匹配,表示嵌套中1组括号已经匹配消除3、若到最后,括号不能完全匹配,则说明输入的表达式有错Input第一行输入一个t,表示下面将有t组测试数据。接下来的t行的每行输入一个表达式,表达式只考虑英文半角状态输入,无需考虑中文全角输入Output对于每一行的表达式,检查括号是否匹配,匹配则输入ok,不匹配则输出errorSampleInput2(a+b)[4*5+(-6)][5*8]/{(a+b)-6SampleOutputokerrorHINT算法流程1、初始化,i=0,建立堆栈,栈为空2、输入表达式,建立指针指向表达式的头部3、读入表达式的第i个字符4、如果第i个字符是左括号,入栈5、如果第i个字符是右括号,,,报错退出6、i++,指向下一个字符,,,,输出error实验步骤与过程:源代码:A:#include<iostream>#include<>#include<>#include<iomanip>usingnamespacestd;constintMaxStackSize=100;typedefcharDateType;classSeqStack{private: DateTypedate[MaxStackSize];//堆栈 inttop;//栈顶指示器public: SeqStack();//构造函数 ~SeqStack();//析构函数 intPush(constDateTypeitem);//入栈 DateTypePop();//出栈 DateTypeGetTop()const;//取栈顶数据元素 intNotEmpty()const;//堆栈非空否};SeqStack::SeqStack()//构造函数{ top=0;}SeqStack::~SeqStack()//析构函数{}intSeqStack::Push(constDateTypeitem)//入栈//把元素item入栈{ if(top==MaxStackSize)//堆栈满时出错退出 { cout<<"堆栈已满"<<endl; exit(0); } date[top]=item;//先存储item top++;//然后top加1 return1;}DateTypeSeqStack::Pop()//出栈//出栈并返回栈顶元素{ if(top==0)//堆栈空时出错退出 { cout<<"堆栈已空"<<endl; exit(0); } to