1、 1 车厢调度问题车厢调度问题 摘要: : 实现栈的基本操作,即实现类型。程序对栈的任何存取，即更改，读取和 状态判别等操作，必须借助于基本操作。在操作过程中的任何状态下都有两种可 能的操作：“入”“出” 。 每个状态下处理问题的方法都是相同的， 具有递归特性 。 关键字:栈 递归 打印 0.0.引言引言 数据结构是计算机科学与技术、软件工程及相关学科的专业基础课，也 是软件设计的技术基础。 数据结构课程的教学要求之一是训练学生进行复杂 的程序设计的技能和培养良好程序设计的风格， 其重要程度决不亚于理论知识的 传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基 本能力，是培
2、养创新意识和创新能力的极为重要的环节。基本要求如下： (1) 熟练掌握基本的数据结构； (2) 熟练掌握各种算法； (3) 运用高级语言编写质量高、风格好的应用程序。 1 1. .需求分析需求分析 (1)这个实验要求我用栈实现车厢调度. (2)车厢的个数是由用户输入的. (3)程序会自动给车厢进行从 1 到 n 的编号. (4)用户输入车厢个数后,程序打印出所有可能的车厢出站顺序. 2.2.数据结构设计数据结构设计 在这个程序中存储结构是栈,对于栈的声明和定义如下: typedef struct SqStack int *top; /*栈顶指针*/ int *base; /*在栈构造之前和销毁
3、之后.base 的值为 NULL*/ int stacksize; /*当前分配的存储空间*/ SqStack; /*顺序栈的结构体声明和定义*/ 2 3 3. .算法设计算法设计 3.1 3.1 对算法的简单描述对算法的简单描述 这个实验中, 要求用到栈. 实现栈的基本操作,即实现类型。程序对栈的任 何存取（即更改，读取和 状态判别等操作）必须借助于基本操作。在操作过程 中的任何状态下都有两种可能的操作： “入” “出” 。 每个状态下处理问题的方法 都是相同的，具有递归特性 。栈实现是方便的 无论如何调度，我们的操作都是入栈和出栈，设定入栈为 1，出栈为-1，对 n 列车 厢有 2n 次这
4、样的操作，例如 n=4，则有操作 1111-1-1-1-1、 1-11-11-11-1 等.所以还要构造一个操作命令队列 trainlist。 在算法中还要用到递归算法,其本质为: 一个数的进栈以后 有两种处理方式： 要么立刻出栈， 或者下一个数的进栈。 一个数的出栈以后 也有两种处理方式：要么继续出栈（栈不为空） ，或 者下一个数的入栈。 3.23.2 栈的基本操作栈的基本操作 3.23.2.1.1 构造一个栈构造一个栈 void InitStack2(SqStack *S,int base_size) S-base=(int *)malloc(base_size * sizeof(int); if(!S-base) puts(“ERROR!“); return ; S-top=S-base; S-stacksize=base_size; /*构造一个空栈*/ 3.2.2 3.2.2 插入新的栈顶元素插入新的栈顶元素 3 void
