车厢调度实习报告

数据结构课程设计

车厢调度

胡海洪

3104006429

计算机科学与技术（1）班

2006年7月

1

04数据结构课程设计 车厢调度 胡海洪

2．3题 车厢调度

实习报告

题目：编制一个将长度为n的车厢进行调度后的所有序列输出的程序

班级：04计算机科学与技术1班 姓名：胡海洪 学号：3104006429 完成日期：06年7月

一、需求分析

1、用编号依次为1，2，3，„„，n表示停在铁路调度站入口处的车厢序列。 2、用一个栈形象地表示为火车的调度站。

3、利用栈先进后出的性质，结合递归和回溯算法，实现编号1„n的车厢的所有可能的

序列和每种序列的出入栈变化过程。

4、本程序用C语言实现，已经在TURBOC 2.0环境下通过。

二、概要设计

1、设定栈的抽象数据类型定义：

ADT Stack{

数据对象：D={ai | ai∈CharSet，i=1，2，„„，n，n≥0} 数据关系：R1={ | 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） 显示所有的序列——递归调用——输出所有结果

（3） 演示一种序列——输入要演示的序列——每一步演示

三、详细设计

1、为了使车厢能够调度，需要定义一个栈，利用栈先进后出的性质，改变车厢的顺序；因为输出的序列有很多种，而且序列的产生是用递归产生的，所以定义一个二维数组，用它保存所有的输出序列，供演示时调用。

struct pathss{

int paths[MAXSIZE][MAXSIZE];

1

数据结构课程设计 车厢调度 胡海洪

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)

1

数据结构课程设计 车厢调度 胡海洪

{

if(pos一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈 }

if(栈不空){

一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈 }

if(pos==n && 栈空){

一种可能输出序列产生，输出； 并将每种序列保存在二维数组里； } }

4、演示一种序列的伪码算法：

演示时，采用的是向逆推的方法，因为我们已经知道了一种输出序列的结果和它的最初状态，就可以利用栈将中间过程显示出来； void ChooseDisplay() {

int k,Output,Input=1;

for(Output=0;Outputif(输出序列中当前的数据大于等于入口处的数据时) {

while(输出序列中当前的数据大于等于入口处的数据时) {

入口处的数据要一直压栈

}

显示每一步结果

}

else （序列中当前的数据小于入口处的数据 ） {

弹出栈顶,重新显示结果

} } }

5、主函数和其他函数 void main() /*主函数*/ {

功能选择 分别调用：

1: InputNumber()

1

数据结构课程设计 车厢调度 胡海洪

2: DisplayAll() 3: ChooseDisplay() }

void DisplayAll() /*显示所有输出序列*/ {

调用函数Attemper }

void Print() /*一个栈打印操作*/ {

int i;

for(i=S.top;i>=0;i--)

printf(\"\\\ |%d|\\n\}

void DisplayOnly(int k,int Output,int Input) /*显示操作序列的状态的变化过程*/ {

第一步：显示输出序列的状态变化 第二步：显示栈的状态变化

第三步：显示输入序列的状态变化 }

6、函数的调用关系图反映了演示程序的层次结构：

InputNumber() InputNumber() DisplayAll() ChooseDisplay() Exit InitStack() Attemper() InitStack() DisplayOnly()

四、调试分析

1、本程序的栈其实也是一个一维数组,然后用一个top作为指针,控制数组的长度。 2、栈的基本操作较简单明了。

3、本程序有两个核心算法，即求所有序列和演示每一序列的变化过程。 4、整个程序运行期间实行静态存储管理。

5、本程序在TURBO C 2.0 同VC ++环境下均可通过。

五、用户手册

1、本程序的运行环境为DOS操作系统，执行文件为：Attemper.exe。

1

数据结构课程设计 车厢调度 胡海洪

2、运行程序后,显示如下界面:

六、测试结果

（1）测试数据n=3；（也可以测试其他数据） （2）选择功能“1”,回车，显示如下：

* * * * * * * * * * * * * * * * * * * 1: 输入火车的长度N * * 2: 输出所有可能序列 * * 3: 演示一个序列变化 * * 4: 退出本程序 * * * * * * * * * * * * * * * * * * * 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: 退出本程序 * * * * * * * * * * * * * * * * * * * （4）选择功能“3”,回车显示如下: 3

请输入你想要查看序列状态变化过程的序号:

7．输入要演示的序列号,如输入“3”,再一直按回车，显示如下: 3

请输入你想要查看序列状态变化过程的序号:3

1

数据结构课程设计 车厢调度 胡海洪

输出序列 栈 输入序列

<----1<----2<----3 |1|

<----2<----3

|2| |1|

<----3 <----2

|1|

<----3 <----2<----1

<----3 <----2<----1

|3| <----2<----1<----3

（5）输入”4”,回车则退出程序。

七、附录

源程序文件名清单： Attemper.c //主程序 Attemper.exe //可执行文件 Attemper.OBJ //目标源文件

八、心得体会

1、通过这次作业，我感到学到不少知识，首先对C语言有了一个比较完整的认识，以前学

习C语言的知识很零碎、不系统，通过写源程序使我对C语言的数据类型（特别构造类型的数据）有了一个完整的认识，为今后进一步学习C++奠定了良好的基础。

2、加深了对《数据结构》这门课程的学习和领会。以往只是知道这门课程对计算机专业很

重要，但具体起来又不明白到底怎样重要？通过设计，我才体会到没有《数据结构》的知识是无法写程序的！由于本人掌握知识深度欠缺，只好采用一个二维数组和一个一维数组，这样明显增加了时间复杂性。 3、实践是检验真理的唯一手段！《数据结构》中的许多理论必须通过实践才能体会到它的

真正含义。当开始写出源程序时，一编译就发现了大量的错误，经过不断的修改和完善，才能正常运行，又进行了录入数据和各项功能的测试。才有了一个比较完整的程序。 4、写程序是辛苦的，也是快乐的，当出现满篇编译错误时，恨不得丢掉，恨不得再也不写

程序。当自己设计的程序通过运行，达到理想的工作状态时，那种喜悦是难以言语的！ 5、最后，衷心地感谢老师的教诲，《数据结构》是一门难学的课程，老师认真的教学态度

值得我学习！

1