数据结构大作业

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

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

3、所有硬卧车厢在中间、所有硬座车厢在最后。编程模拟上述车厢调度过程。提示：两个辅助铁轨相当于两个栈，右端车厢进入用相应字符串给出，如 “BBACBCAABBCAa左端车厢的用新生成的字符串给出。在 给出模拟函数，并 在主函数中进行调用测试。CCCBBBBBAAAAABBACBCAABBCAA铁轨3、填写实验报告，实验报告文件取名为。4、上传实验报告文件、源程序文件及到Ftp服务器上()的文件夹下。三.抽象数据类型定义ADT STACK isData:元素具有ElemType类型的栈，用标示符StackType表示栈对象类型 Operation:void InitStack(Stack &

4、S)操作结果：初始化栈S,即构造一个空栈 Svoid Push(Stack &S, ElemType item,int i)操作结果：元素item进栈，作为新的栈顶元素ElemType Pop(Stack &S,int i)操作结果：栈顶元素出栈，并返回其值ElemType Peek(Stack S,int i)操作结果：取S当前栈顶元素，并返回，但元素不出栈End STACK四.存储结构定义及算法思路一、定义共建栈的相关属性struct Stack ElemType *stack ;实验结果与分析B一回W任意输入 T串字符其中n表示褒座.日表示屈卧.c表示软卧”Bi 旧CRc

5、anRBC白口CCC DBS A ft A A A Pi*eany ky to cont: inue六.心得体会【附录-源程序】#include<>#include<>typedef char ElemType;struct Stack ElemType *stack ;int topi;int MaxSize;int top2;；#include ""void main()Stack s;char a20;int i,j,m=0,n=0;InitStack(s);coutvv”任意输入一用字符(其中A表示硬座，B表示硬卧，C表示软 卧):"

6、;<<endl;i=0;cin>>a;while(ai='A'|ai='B'|ai='C') if(ai='C')cout<<ai;else if(ai='B')Push(s,ai);m+;elsePush(s,ai);n+;i+;for(i=0;i<m;i+)cout<<Pop(s);for(j=0;j<n;j+)cout<<Pop(s); void InitStack(Stack &S)=20;=new ElemType口；if(!cerr<<”动态申请失败!"<<endl;exit；=-1;=;bool EmptyStack(Stack &S)return =-1&&=;void Push(Stack &S, ElemType item)!"<<endl;if=cout<<"栈已经全满，没有多余的空间存放元素elseif(item='B')+;=item;if(item='A');=item;ElemType Pop(Stack &S