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

《数据结构实验报告(实验三)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：实验三：桟的应用学院：计算机与软件学院专业:指导教师：蔡平报告人：文成学号：2011150259班级:5实验时间：2012-10-08实验报告提交时间:2012-10-20教务部制一、实验目的与要求：0的：1.掌握线性表的基本原理2.掌握线性表地基本结构3.掌握线性表地创建、插入、删除、查找的实现方法要求：1.熟悉C++语言编程2.熟练使用C++语言实现线性表地创建、插入、删除、奔找的实现方法二、实验内容：ProblemA:数据结构——实验3——STL堆栈对象的例程TimeLimit:1SecMemoryL

2、imit:128MBSubmit:103Solved:85[Submit][Status][WebBoard]Description掌握C++中STL自带的堆栈对象应用。演示堆栈对象的各种操作，以字符串的逆序输出为例子输入一个字符华，按输入顺序将字符压入堆栈，然后根据堆栈后进先出的特点，做逆序输出Input第一行输入t，表示有t个测试实例第二起，每一行输入一个字符串，注意字符串不要包含空格Output每行逆序输出每一个字符串SampleInput2abcdefaabbccSampleOutputfedcbaccbbaaHINTProblemB:数据结构一一实验3—一堆

3、栈应用之括号匹配TimeLimit:1SecMemoryLimit:128MBSubmit:365Solved:120[Submit][Status][WebBoard]Description处理表达式过程中需耍对括号匹配进行检验，括号匹配包括三种.•“(”和“)”,“[”和“]”，“{”和“}，，。例如表达式中包含括号如下：()[()([])]{}123456789101112从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检

4、验，可以遵循以下规则：1、当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。2、当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除3、若到最后，括号不能完全匹配，则说明输入的表达式奋错Input第一行输入一个t,表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入Output对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出errorSampleInput2(a+b)[4*5+(-6)][5*8]/{(a+b)-6SampleOu

5、tputokerrorHINT算法流程1、初始化，i=0,建立堆栈，栈为空2、输入表达式，建立指针指向表达式的头部3、读入表达式的第i个字符4、如果第i个字符是左括号，入栈5、如果第i个字符是右括号，检查桟顶元素是否匹配A.如果匹配，弹出栈顶元素B.如果不闪配，报错退出6、i++,指向K一个字符，是否已经表达式末尾A.未到末尾，重复步骤3B.已到达末尾a.堆栈为空，输出okb.堆拽不为空，输出error三、实验步骤与过程:源代码：A：#include#include#include#include

6、ip>usingnamespacestd;constintMaxStackSize=100;typedefcharDateType;classSeqStack{private:DateTypedate[MaxStackSize];//堆桟inttop;//栈顶指示器public:SeqStack();//构造函数〜SeqStack();//析构函数intPush(constDateTypeitem);//入栈DateTypePop();//出拽DateTypeGetTop()const;//取栈顶数据元素intNotEmpty()const;//堆栈非空否SeqSta

7、ck::SeqStack()//构造函数{top=0;}SeqStack::〜SeqStack()//析构函数{}intSeqStack::Push(constDateTypeitem)//入栈//把元素item入栈{if(top==MaxStackSize)//堆桟满时出错退出{cout«"堆栈己满”<