实习报告: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={
基本操作:
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.data[S.top--];
return temp;
}
int StackEmpty() /*判断栈是否为空*/ {
if(S.top==-1)
return 1;
else
return 0;
}
3、求所有序列的伪码算法:
void Attemper(int pos,int path[],int cur)
{
if(pos 一个数进栈后,有两种处理方式:要么立刻出栈,要么进行下一个数的进栈} if(栈不空){ 一个数出栈后,有两种处理方式:要么继续出栈,要么继续下一个数的进栈} if(pos==n && 栈空){ 一种可能输出序列产生,输出; 并将每种序列保存在二维数组里; } } 4、演示一种序列的伪码算法: 演示时,采用的是向逆推的方法,因为我们已经知道了一种输出序列的结果和它的最初状态,就可以利用栈将中间过程显示出来; void ChooseDisplay() { int k,Output,Input=1; for(Output=0;Output { if(输出序列中当前的数据大于等于入口处的数据时) { while(输出序列中当前的数据大于等于入口处的数据时) { 入口处的数据要一直压栈 } 显示每一步结果 } else (序列中当前的数据小于入口处的数据) { 弹出栈顶,重新显示结果 } } } 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 5 : 1 2 3 * * * * * * * * * * * * * * * * * * * 1:输入火车的长度N * * 2:输出所有可能序列 * * 3:退出本程序 * * * * * * * * * * * * * * * * * * * * * (4)选择功能“3”,回车显示如下: 3 请输入你想要查看序列状态变化过程的序号: (5)输入”3”,回车则退出程序。 六、附录 源程序文件名清单: Attemper.c //主程序 Attemper.exe //可执行文件 Attemper.OBJ //目标源文件