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

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

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

3、堆栈应用之括号匹配Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 365 Solved: 120SubmitStatusWeb BoardDescription处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“”和“”，“”和“”。例如表达式中包含括号如下：()()()123456789101112从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：1、 当接收第1

4、个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。2、 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除3、 若到最后，括号不能完全匹配，则说明输入的表达式有错Input第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入Output对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出errorSample Input2(a+b)4*5+(-6)5*8/(a+b)-6Sample OutputokerrorHINT算法流程1、初始化，i=0，建立堆

5、栈，栈为空2、输入表达式，建立指针指向表达式的头部3、读入表达式的第i个字符4、如果第i个字符是左括号，入栈5、如果第i个字符是右括号，检查栈顶元素是否匹配 A.如果匹配，弹出栈顶元素 B.如果不匹配，报错退出6、i+，指向下一个字符，是否已经表达式末尾 A. 未到末尾，重复步骤3 B. 已到达末尾 a. 堆栈为空，输出ok b. 堆栈不为空，输出error3、 实验步骤与过程：源代码：A：#include<iostream>#include<string.h>#include<stdlib.h>#include<iomanip>using na

6、mespace std;const int MaxStackSize=100;typedef char DateType;class SeqStackprivate:DateType dateMaxStackSize;/堆栈int top;/栈顶指示器public:SeqStack();/构造函数SeqStack();/析构函数int Push(const DateType item);/入栈DateType Pop();/出栈DateType GetTop()const;/取栈顶数据元素int NotEmpty()const;/堆栈非空否;SeqStack:SeqStack()/构造函数to

7、p=0;SeqStack:SeqStack()/析构函数int SeqStack:Push(const DateType item)/入栈/把元素item入栈if (top=MaxStackSize)/堆栈满时出错退出cout<<"堆栈已满"<<endl;exit(0);datetop=item;/先存储itemtop+;/然后top加1return 1;DateType SeqStack:Pop()/出栈/出栈并返回栈顶元素if (top=0)/堆栈空时出错退出cout<<"堆栈已空"<<endl;exi

8、t(0);top-;return datetop;DateType SeqStack:GetTop()const/取栈顶数据元素/取当前栈顶数据元素并返回if (top=0)/堆栈空时出错退出cout<<"堆栈已空"<<endl;exit(0);return datetop-1;/返回当前栈顶元素int SeqStack:NotEmpty()constreturn (top!=0);int Func(char exp,int n)SeqStack myStack;/定义链式堆栈int i;for(i=0;i<n;i+)myStack.Push(

9、expi);/入栈for(i=0;i<n;i+)cout<<myStack.GetTop();myStack.Pop();if (!myStack.NotEmpty()break;cout<<endl;return 0;int main()int testNo,i;char sample80;cin>>testNo;/输入测试次数cin.get();/消除上次输入的回车符号for(i=0;i<testNo;i+)cin.getline(sample,80);/输入样本数据Func(sample,strlen(sample);return 0;B：

10、#include<iostream>using namespace std;class Listprivate:int *elem;/数组元素int listsize;/顺序表最大长度int length;/顺序表当前长度public:List(int size);/构造函数List();/析构函数int ListLength();/获取顺序表的实际长度int ListInsert(int i,int e);/插入一个元素int ListDelete(int i);/删除一个元素，返回删除的元素int GetElem(int i);/获取一个元素，返回元素值int swap(int

11、 a,int b);/交换二个元素;List:List(int size)/构造函数listsize=size;length=0;elem=new intlistsize;List:List()/析构函数deleteelem;int List:ListLength()/获取顺序表的实际长度return length;int List:ListInsert(int i,int e)/插入一个元素if (length=listsize)return 0;/顺序表已满if (i<1 | i>length+1)return 0;/i值不合法if (i=length+1)elemlength

12、=e;elsefor (int j=length;j>i-1;j-)/位置i后面的元素全部后移一位elemj=elemj-1;elemi-1=e;length+;return 1;int List:ListDelete(int i)/删除一个元素，返回删除的元素if (length=0)return 0;if (i<1 | i>length)return 0;int temp=elemi-1;for (int j=i-1;j<length;j+)/位置i后面的元素全部前移一位elemj=elemj+1;length-;return temp;int List:GetEl

13、em(int i)/获取一个元素，返回元素值if(i<1 | i>length)return 0;return elemi-1;int List:swap(int a,int b)/交换二个元素if (a<1 | a>length | b<1 | b>length | a=b)cout<<"error"/输入不合法，则报错return 0;elseint temp=elema-1;/交换元素elema-1=elemb-1;elemb-1=temp;return 1;int main()int i,len,temp;List m

14、yList(100);/创建一个顺序表，最大长度为100cin>>len;for(i=1;i<len+1;i+)cin>>temp;myList.ListInsert(i,temp);for(i=1;i<myList.ListLength()+1;i+)/打印顺序表cout<<myList.GetElem(i)<<" "cout<<endl;int x,y;/输入交换元素的位置cin>>x>>y;if (myList.swap(x,y)/交换这二个元素for(i=1;i<m

15、yList.ListLength()+1;i+)/打印交换元素后的顺序表cout<<myList.GetElem(i)<<" "cout<<endl;cin>>x>>y;if (myList.swap(x,y)/交换这二个元素for(i=1;i<myList.ListLength()+1;i+)/打印交换元素后的顺序表cout<<myList.GetElem(i)<<" "cout<<endl;return 0;四、实验结果及数据处理分析：A：实验基本达到