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

文档介绍：深圳大学实验报告
课程名称: 数据结构实验与课程设计
实验项目名称: 实验三:栈的应用

学院: 计算机与软件学院

专业:

指导教师: 蔡平

报告人: 文成学号: 2011150259 班级: 5

实验时间: 2012-10-08
实验报告提交时间: 2012-10-20
教务部制
一、实验目的与要求:
目的:


、插入、删除、查找的实现方法
要求:
++语言编程
++语言实现线性表地创建、插入、删除、查找的实现方法
二、实验内容:
Problem A: 数据结构——实验3——STL堆栈对象的例程
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 103 Solved: 85
[Submit][Status][Web Board]
Description
掌握C++中STL自带的堆栈对象应用。
演示堆栈对象的各种操作,以字符串的逆序输出为例子
输入一个字符串,按输入顺序将字符压入堆栈,然后根据堆栈后进先出的特点,做逆序输出
Input
第一行输入t,表示有t个测试实例
第二起,每一行输入一个字符串,注意字符串不要包含空格
Output
每行逆序输出每一个字符串
Sample Input
2
abcdef
Sample Output
fedcba
ccbbaa
HINT
Problem B: 数据结构——实验3——堆栈应用之括号匹配
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 365 Solved: 120
[Submit][Status][Web Board]
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,不匹配则输出error
Sample Input
2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6
Sample Output
ok
error
HINT
算法流程
1、初始化,i=0,建立堆栈,栈为空
2、输入表达式,建立指针指向表达式的头部
3、读入表达式的第i个字符
4、如果第i个字符是左括号,入栈
5、如果第i个字符是右括号,检查栈顶元素是否匹配
,弹出栈顶元素
,报错退出
6、i++,指向下一个字符,是否已经表达式末尾
A. 未到末尾,重复步骤3
B. 已到达末尾
a. 堆栈为空,输出ok
b. 堆栈不为空,输出error
实验步骤与过程:
源代码:
A:
#include<iostream>
#include<>
#include<>
#include<iomanip>
using namespace std;
const int MaxStackSize=100;
typedef char DateType;
class SeqStack
{
private:
DateType date[MaxStackSize];//堆栈
int top;//栈顶指示器
public:
SeqStack();//构造函数
~SeqStack();//析构函数
int Push(const DateType item);//入栈
DateType Pop();//出栈
DateType GetTop()const;//取栈顶数据元素
int