数据结构大作业

1、浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验九 栈的应用 学生姓名 丁汀 专业班级 信管1006 学号 31001444 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。2、掌握利用栈各种操作来进行具体的实际应用。3、加强综合程序的分析、设计能力。二. 实验内容1、共享栈的设置，问题描述如下：在一个数组空间stackMaxSize中可以同时存放两个顺序栈，栈底分别处在数组的两端，当第1个栈的栈顶指针top1等于1时则栈1为空，当第2个栈的栈顶指针top2等于MaxSize时则栈2为空。两个栈

2、均向中间增长，当有元素向栈1进栈时，使top1增1得到新的栈顶位置，当有元素向栈2进栈时，使top2减1得到新的栈顶位置。当top1=top2-1或top1+1=top2时，存储空间用完，无法再向任一栈做进栈操作，此时可考虑给出错误信息并停止运行。要求： 给出共享栈的顺序存储类型定义。 给出共享栈的抽象数据类型定义。 建立头文件test9_stack.h，包含共享栈的基本操作实现函数；建立主程序文件test9.cpp，在主函数中对共享栈的各个操作进行测试。2、利用上述共享栈，实现火车车厢的调度模拟 设火车车厢分为三类：硬座、硬卧、软卧，分别用A、B、C表示。下图描述车厢调度的示意图，图中右端为

3、排列无序的车厢，左端为调度后的车厢排列，使得所有软卧车厢在最前面、所有硬卧车厢在中间、所有硬座车厢在最后。 编程模拟上述车厢调度过程。提示：两个辅助铁轨相当于两个栈，右端车厢进入用相应字符串给出，如“BBACBCAABBCAA”，左端车厢的用新生成的字符串给出。在test9_stack.h给出模拟函数，并在主函数中进行调用测试。BBACBCAABBCAACCCBBBBBAAAAA铁轨辅助铁轨3、填写实验报告，实验报告文件取名为report9.doc。4、上传实验报告文件report9.doc 、源程序文件test9.cpp及test9_stack.h到Ftp服务器上（ ftp:/10.66.2

4、8.222:2007 ）的文件夹下。三. 抽象数据类型定义ADT STACK is Data: 元素具有ElemType类型的栈，用标示符StackType表示栈对象类型 Operation: void InitStack(Stack &S) 操作结果：初始化栈S，即构造一个空栈 S void Push(Stack &S, ElemType item,int i) 操作结果：元素item 进栈，作为新的栈顶元素 ElemType Pop(Stack &S,int i) 操作结果：栈顶元素出栈，并返回其值 ElemType Peek(Stack S,int i) 操作结果

5、：取S当前栈顶元素，并返回，但元素不出栈End STACK4. 存储结构定义及算法思路1、 定义共建栈的相关属性struct Stack ElemType *stack ;/ 存栈元素 int top1; / 栈顶指示器1，直接指向栈的一端 int MaxSize; / 栈的最大长度 int top2; /栈顶指示器2，直接指向栈的另外一端;二、创建动态的共建栈void InitStack(Stack &S) S.MaxSize=20;S.stack=new ElemTypeS.MaxSize;if(!S.stack)cerr<<"动态申请失败!"<

6、;<endl;exit(1);S.top1=-1;S.top2=S.MaxSize;三、进栈操作，将相应的元素放到对应的位置中void Push(Stack &S, ElemType item)if(S.top1=S.top2-1)cout<<"栈已经全满，没有多余的空间存放元素!"<<endl;elseif(item='B')S.top1+;S.stackS.top1=item;if(item='A')S.top2-;S.stackS.top2=item;四、依次取出栈中符合条件的元素ElemType

7、Pop(Stack &S)if(S.top1=-1&&S.top2=S.MaxSize)cerr<<"Stack is empty!"<<endl;exit(1);if(S.top1!=-1)S.top1-;return S.stackS.top1+1;if(S.top2!=S.MaxSize)S.top2+;return S.stackS.top2-1; 五. 实验结果与分析六. 心得体会【附录-源程序】Test9.cpp#include<iostream.h>#include<stdlib.h>ty

8、pedef char ElemType;struct Stack ElemType *stack ; int top1; int MaxSize; int top2; ;#include "test9_stack.h"void main()Stack s;char a20;int i,j,m=0,n=0;InitStack(s);cout<<"任意输入一串字符(其中A表示硬座，B表示硬卧，C表示软卧):"<<endl;i=0;cin>>a;while(ai='A'|ai='B'|ai=&

9、#39;C')if(ai='C')cout<<ai;else if(ai='B') Push(s,ai);m+;else Push(s,ai);n+;i+;for(i=0;i<m;i+)cout<<Pop(s);for(j=0;j<n;j+)cout<<Pop(s); Test9_stack.hvoid InitStack(Stack &S) S.MaxSize=20;S.stack=new ElemTypeS.MaxSize;if(!S.stack)cerr<<"动态申请失败

10、!"<<endl;exit(1);S.top1=-1;S.top2=S.MaxSize; bool EmptyStack(Stack &S) return S.top1=-1&&S.top2=S.MaxSize;void Push(Stack &S, ElemType item)if(S.top1=S.top2-1)cout<<"栈已经全满，没有多余的空间存放元素!"<<endl;elseif(item='B')S.top1+;S.stackS.top1=item;if(item='A')S.top2-;S.stackS.top2=item;ElemType Pop(Stack &S)if(S.top1=-1&&S.top2=S.Ma