车厢调度问题

武汉理工大学《数据结构》课程设计说明书

题目：车厢调度问题 初始条件：

理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。

要求完成的主要任务:(包括课程设计工作量及其技术要求， 以及说明书撰写等具体要求)

1、系统应具备的功能：

(1) 求出由一个编号依次为1, 2,……,n的车厢序列可能产生的所有出栈系列; (2) 求出有多少种出栈的可能性；

(3) 对于每个输出序列演示出所有操作序列的变化过程。 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现；

5、撰写课程设计报告，包括： (1) 设计题目； (2) 摘要和关键字；

(3) 正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、

不足之处、设计体会； (4) 结束语； (5) 参考文献。

时间安排：2007年7月2日一7日(第18周)

7月2日 查阅资料

7月3日 系统设计，数据结构设计，算法设计 7月4日-5日 编程并上机调试 7月6日 撰写报告

7月7日 验收程序，提交设计报告书。

指导教师签名:

2007 年7月2日

系主任(或责任教师)签名: 2007 年7月2日

武汉理工大学《数据结构》课程设计说明书

车厢调度问题

摘要：通过输入车厢系列的编号n,求出所有可能由此输出的长度为

n的车厢系列，用入

栈出栈的方法，实现车厢调度，并演示每一种出栈序列的过程。任务：假设停在铁路调度 站入口处的车厢系列的编号依次为 的长度为n的车厢系列。 关键字：车厢,调度,栈,递归

1, 2, 3,…n。设计一个程序,求出所有可能由此输出

0.引言

随着人民生活水平的提高，越来越多的人坐火车出去旅游，这也让火车车厢的量大量 增大，也随之出现了一个问题，即合理的调度车厢，本课程设计即利用数据结构里的栈的 知识，设计一个合理的算法，来解决此问题。

1. 需求分析

假设停在铁路调度站入口处的车厢序列的编号依次为 序，求出所有可能的长度为n的车厢序列。

实现栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的 基本操作必须借助于基本操作进行。

测试数据取n=3 , 4,程序输出的结果应该在屏幕上显示出来。

1，2, 3,……，n ,设计一个程

2. 数据结构设计

2.1全局变量定义

typedef int SEIemType; typedef int Status;

int end;/* 最后一个车厢的号码*/ long total=0;/*

总的组合方案数目*/

武汉理工大学《数据结构》课程设计说明书

2.2栈的定义

typedef struct stacklist void Stack_i nit(SqStack *s)

void Stack_Push(SqStack *s,SEIemType e) SEIemType Stack_Pop(SqStack *s) Status Stack_Empty(SqStack *s) Status Stack_Full(SqStack *s) void Stack_pri ntreverse(SqStack s)

3. 算法设计

3.1用到的进出栈算法基础知识

(1)根据要求，了解可能要用到的算法：

3.1.1进栈(PUSH算法

① 若TOP^n时，贝呼合出溢出信息，作出错处理(进栈前首先检查栈是否已满，满则溢出；不满则作②)；

② 置TOP=TOP+1栈指针加1,指向进栈地址); ③ S(TOP)=X结束(X为新进栈的元素)；

3.1.2退栈(POP算法

① 若TOPC0,则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，不空则作②)；

② X=S(SOP)(退栈后的元素赋给X)；

③ TOP=TOP-,1结束(栈指针减1，指向栈顶)。

3.2程序分析

3.2.1.栈的数据结构

typedef struct stacklist {

空则下溢;

武汉理工大学《数据结构》课程设计说明书

SElemType *base; SElemType *top; int stacksize; }SqStack;

武汉理工大学《数据结构》课程设计说明书

void Stack」nit(SqStack *s) {

s->base=(SEIemType *)malloc(end*sizeof(int)); if(!s->base) exit(0); s->top=s->base; s->stacksize=e nd; }

void Stack_Push(SqStack *s,SElemType e) {

*(s->top)++=e; }

SElemType Stack_Pop(SqStack *s) {

if(s->top==s->base) return 0; return *(--(s->top)); }

Status Stack_Empty(SqStack *s) {

if(s->top==s->base) return 1; return 0; }

Status Stack_Full(SqStack *s) {

if(s->top-s->base==e nd) return 1; return 0; }

武汉理工大学《数据结构》课程设计说明书

void Stack_pri ntreverse(SqStack s) {

int *po; po=s.base; printf(\"[%ld]: \for(;po!=s.top;) prin tf(\"%d \prin tf(\"\\n\"); }

322核心算法

void search(SqStack *in putPoi nt,SqStack *tempPoi nt,SqStack *outputPoi nt) {

if(!Stack_Empty(i nputPoi nt)) {

Stack_Push(tempPoi nt,Stack_Pop(i nputPoi nt)); search(i nputPo in t,tempPo in t,outputPo in t); Stack_Push(i nputPoi nt,Stack_Pop(tempPoi nt)); }

if(!Stack_Empty(tempPoi nt)) {

Stack_Push(outputPoi nt,Stack_Pop(tempPoi nt)); search(i nputPo in t,tempPo in t,outputPo in t); Stack_Push(tempPoi nt,Stack_Pop(outputPoi nt)); }

if(Stack_Full(outputPoi nt)) {

total++;

Stack_pri ntreverse(*outputPoi nt);

}

武汉理工大学《数据结构》课程设计说明书

}

323主程序描述

void main() {

SqStack in put,temp,output; int i;

prin tf(\"Wuha n Uni versity of Tech no logy 2005 Computer Scie nee & Tech no logy 华松 \\n\");

prin tf(\"Please in put the last Number of the Carriage:\"); scan f(\"%d\/*初始化三个栈*/ Stack_i nit(&in put); Stack_i nit(& temp); Stack_i nit(& output); /*将车厢号码进栈*/ for(i=e nd;i>=1;i--) Stack_Push(&in put,i);

search(&in put, &temp，&o utput); prin tf(\"the total:%ld\\\\n\getch(); }

4. 程序实现

4.1运行界面

(1) 运行主界面

梁

武汉理工大学《数据结构》课程设计说明书

当输入n的值为3时，屏幕显示 更 C AWINDOWS\\sy5tem321cmd.exe Wuhan Univcrsity of Technolos(y Computer Sclencc & Technolo^v zLnput the last NumJb&t1 o£ the Carriage: 3 3 Please [11： 1 ⑵

[21： E3 3： [41： It lie [SB

2 1 1 3 2 3 汚 5 Press anv key to continue ⑶当输入n的值为4时，屏幕显示

武汉理工大学《数据结构》课程设计说明书

4.2不足之处

我这个程序主要通过设置三个栈来实现，核心算法通过两次递归调用实现。可以实现 任务书里所要求的功能，但是也存在着不足之处，就是在运行界面，输出n值，按回车键, 得到输出结果后，要想继续输入另一数值 n,不能返回，只有退出，重新运行，才能输入得 到输出结果。

5. 设计体会

看到自己写的程序成功的运行真是种莫大的欣喜！

很多时候，总是感觉学到的东西不知何用，总想用学过的语言来写些程序，却一直不 知道写些什么。终于，机会来到了，数据结构课程设计，让我一下子回忆起了以前学到的 很多语言，于是，就有了运用自己所学的所有语言分别来实现车厢的调度。

通过这个星期的课程设计，我的收获还是不少。我的编程水平有了比较大的提高，虽 然我做的程序里还有写问题，做的不够深入，但独立完成一个比较大一点的程序的经历也 是很宝贵的。

武汉理工大学《数据结构》课程设计说明书

6. 结束语

本课程设计主要是为了实现解决以下问题的程序：假设停在铁路调度站入口处的车厢 序列的编号依次为1, 2, 3……N。求出所有由此输出的长度为 N的车厢序列。 我在解决 这个问题时，用的是Visual C++来做到这点的。

[1] 严蔚敏。《数据结构习题》，清华大学出版社[2] 许卓群，杨冬青。《数据结构与算法》，高等教育出版社[3] 张乃孝，裘宗燕。《数据结构一

参考文献

C++与面向对象的途经（修订版）》，高等教育出版社