实习报告：2.3题 车厢调度
实习报告班级文化建设主题
题目：假设停在铁路调度站入口处的车厢序列的编号次序为1，2，3，…，n。设计一个程序，求出所有可能输出的长度为n的车厢序列。
班级：计算机（2）班 姓名：李伟 学号：07095216 完成日期：2009.9.9
一、需求分析
1、用编号依次为1，2，3，……，n表示停在铁路调度站入口处的车厢序列。
2、用一个栈形象地表示为火车的调度站。
3、利用栈先进后出的性质，结合递归和回溯算法，实现编号1…n的车厢的所有可能的序列。
4、 本程序用C红豆杉怎么养语言实现，已经在WIN-TC环境下通过。
二、概要设计
1、设定栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai | ai∈CharSet，i=1，2，……，n，n≥0}
数据关系：R1={<ai-1,ai> | ai-1,ai∈D,i=2，……，n}
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
Push(&S,e);
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素e。
Pop(&S,e);
初始条件：栈S已存在。
操作结果：删除S扒皮鱼怎么做好吃的栈顶元素，并以e返回其值。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。
}ADT Stack
2、 本程序包括两个模块：
（1） 初始化数据——输入总数——初始化栈和序列
（2） 显示所有的序列——递归调用——输出所有结果
三、详细设计
1、为了使车厢能够调度，需要定义一个栈，利用栈先进后出的性质，改变车厢的顺序；因为输出的序列有很多种，而且序列的产生是用递归产生的，所以定义一个二维数组，用它保存所有的输出序列，供演示时调用。
struct pathss{
int paths[MAXSIZE][MAXSIZE];
int number;
}AllPath;
2、栈类型
struct SNode{
int data[MAXSIZE];
int top;
}S;
栈的基本操作：
void InitStack() /*栈的初始化*/
{
S.top=-1;
}
void Push(int q) /*进栈*/
{
S.data[++S.top]=q;
}
int Pop() /*出栈胡豆的做法*/
{
int temp;
temp=S.p--];
return temp;
}
int StackEmpty() /*判断栈是否为空*/
{
p==-1)
return 1;
el
return 0;
}
3、求所有序列的伪码算法：
void Attemper(int pos,int path[],int cur)
{
if(pos<n) {
一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈
}
if(栈不空){
一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈
}
if(pos==n && 栈空){
一种可能输出序列产生，输出；
并将每种序列保存在二维数组里；
}
}
4、演示一种序列的伪码算法：
演示时，采用的是向逆推的方法，因为我们已经知道了一种输出序列的结果和它的最初状态，就可以利用栈将中间过程显示出来；
void ChooDisplay()discusd
{
int k,Output,Input=1;
for(Output=0;Output<n;Output++)
{
if(输出序列中当前的数据大于等于入口处的数据时)
{
while(输出序列中当前的数据大于等于入口处的数据时)
{
入口处的数据要一直压栈
}
显示每一步结果
}
el （序列中当前的数据小于入口处的数据 ）
{
弹出栈顶,重新显示结果
}
}
}
5、主函数和其他函数
void main() /*主函数*/
{
功能选择
分别调用：
1: InputNumber()
2: DisplayAll()
}
void DisplayAll() /*显示所有输出序列*/
{
调用函数Attemper
}
美国美女图片void DisplayOnly(int k,int Output,int Input) /*显示操作序列的状态的变化过程*/
{
第一步：显示输出序列的状态变化
第二步：显示栈的状态变化
}
6、函数的调用关系图反映了演示程序的层次结构：
四、调试分析
1、 本程序的栈其实也是一个一维数组,然后用一个top作为指针,控制数组的长度。
2、 栈的基本操作较简单明了。
3、 本程序有两个核心算法，即求所有序列和演示每一序列的变化过程。
4、 整个程序运行期间实行静态存储管理。
5、 本程序在WIN-TC可通过。
五、测试结果
（1）测试数据n=3云南大理丽江旅游攻略必去景点；（也可以测试其他数据）
（2）选择功能“1”,回车，显示如下：
* * * * * * * * * * * * * * * * * *
* 1: 输入火车的长度N *
* 2: 输出所有可能序列 *
* 3: 退出本程序 *
* * * * * * * * * * * * * * * * * *
1
请输入火车车厢的长度N:
（3） 输入车厢总数 “3”,选择功能“2”，按回车显示如下：
2
所有可能的输出序列如下:
1 : 3 2 1
2 : 2 3 1
元日古诗
3 : 2 1 3
4 : 1 3 2
