文档介绍：武汉理工大学《数据结构》课程设计说明书
题目：车厢调度问题 初始条件：
理论：学****了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践: 计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务:(包括课程设计工作量及其技术要求，以及说明书撰写等具体要求)
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
车厢调度问题
摘要：通过输入车厢系列的编号n,求出所有可能由此输出的长度为 n的车厢系列，用入
栈出栈的方法，实现车厢调度，并演示每一种出栈序列的过程。任务：假设停在铁路调度 站入 口处的车厢系列的编号依次为 1, 2, 3,-no设计一个程序，求出所有可能由此输出
的长度为n的车厢系列。
关键字：车厢，调度，栈，递归
随着人民生活水平的提高，越来越多的人坐火车出去旅游，这也让火车车厢的量大量 增 大，也随之出现了一个问题，即合理的调度车厢，本课程设计即利用数据结构里的栈的知识， 设计一个合理的算法，来解决此问题。
.需求分析
假设停在铁路调度站入口处的车厢序列的编号依次为 1, 2, 3,……，n,设计一个程
序，求出所有可能的长度为n的车厢序列。
实现栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的基 本操作必须借助于基本操作进行。
测试数据取n=3 , 4,程序输出的结果应该在屏幕上显示出来。
.数据结构设计
全局变量定义
typedef int SEIemType;
typedef int Status;
int end;/*最后一个车厢的号码*/
武汉理工大学《数据结构》课程设计说明书
long total=0;/* 总的组合方案数目*/
武汉理工大学《数据结构》课程设计说明书
栈的定义
typedef struct stacklist
void StackJ nit(SqStack *s)
void Stack_Push(SqStack *s5SEIemType e)
SEIemType Stack_Pop(SqStack *s)
Status Stack_Empty(SqStack *s)
Status Stack_Full(SqStack *s)
void Stack_pri ntreverse(SqStack s)
.算法设计
用到的进出栈算法基础知识
(1)根据要求，了解可能要用到的算法：
进栈(PUSH算法
①若TOPAn时，贝呼合出溢出信息，作出错处理(进栈前首先检查栈是否已满，满则溢出； 不满则作②)；
② 置TOP=TOP+1栈指针加1,指向进栈地址);
③S(TOP)=X结束(X为新进栈的元素)；
退栈(POP算法
① 若TOPCO,则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢;
不空则作②)；
②X=S(SOP)(退栈后的元素赋给X)；
③TOP=TOP-,1结束(栈指针减1,指向栈顶)。
武汉理工大学《数据结构》课程设计说明书
程序分析
栈的数据结构
typedef struct stacklist
武汉理工大学《数据结构》课程设计说明书
SEIemType *base;
SEIemType *top; int stacksize;
}SqStack;
武汉理工大学《数据结构》课程设计说明书
void Stack J nit(SqStack *s)
(
s->base=(SEIemType *)malloc(end*sizeof(int));
if(!s->base) exit(O);
s->top=s->base;
s->stacksize=e nd;
}
void Stack_Push(SqStack *s,SEIemType e)
(