车厢调度算法实习报告

题目：2.3车厢调度 难度系数: 4

选择的功能实现：利用堆栈存储结构模拟车厢调度过程

一、需求分析

1. 本演示程序中，使用顺序堆栈作为车厢调度车站，车子按1,2…n的顺序依次排列在

车站入口处，其中n<=50，堆栈中每个元素存储一个车厢号码代表该车。用户自己输入等候车厢的数目n，回车后会出现所有可能的车厢输出情况。如果输入小于0或n>50则会提示出错。

2. 演示程序以用户和计算机对话方式执行。即在计算机终端上显示提示信息之后，由

用户在键盘上输入车厢数目n后，相应的结果会显示在屏幕上。 3. 程序执行的命令包括：

1）构造顺序堆栈 2）初始化堆栈 3）调用递归函数 4. 测试数据

n=1, 输出结果为： 1 n=2, 输出结果为: 21 12

n=3, 输出结果为:

321 231 213 132 123 n=4，输出结果为：

4321 3421 3241 3214 2431 2341 2314 2143 2134 1432 1342 1324

1243 1234 二、概要设计

为实现以上功能，使用顺序堆栈结构构造了调度站模型。 1. 设定栈的抽象数据类型定义：

ADT Stack(

数据对象：D={ai|ai∈charset,i=1,2,…,n>0}

数据关系：R1={|ai-1,ai∈D,i=2,…n} 基本操作： Init(&s)

操作结果：构造一个空栈S; isEmpty()

初始条件：栈s已存在

操作结果：如果栈s空，则返回1，否则返回0； Pop()

初始条件：栈s已存在

操作结果：删除s的栈顶元素，并以temp返回其值 Push(q)

初始条件：栈s已存在

操作结果：在栈s的栈顶插入新的栈顶元素q }ADT Stack

2．本程序包含三个模块

1）主程序模块： Void main() {

初始化；

For(int a=0;a<100;a++) {

If(c==’Q’||c=’q’) Return 0; Else {

接收命令； 处理命令；

} } }

2）栈模块—实现栈抽象数据类型 3）递归模块—实现算法递归调用 各模块之间的调用关系如下：

主程序模块

递归模块

栈模块 三、详细设计

1. 构造堆栈

struct snode {

int data[max]; int top; }s;

栈的基本操作

void init() //初始化 {

s.top=-1; }

void push(int q) //入栈操作 {

s.top++;

s.data[s.top]=q; }

int pop() //出栈操作 {

int temp;

temp=s.data[s.top]; s.top--;

return temp; }

int isEmpty() //判读栈是否为空 {

if(s.top==-1) return 1; else

return 0; }

2. 递归算法：

void digui(int pos,int path[],int curp) {

int m,i;

if(pos{ push(pos+1);//选择把下一个压栈 digui(pos+1,path,curp); pop();//选择把下一个压栈进去的元素退出去，待会等待把自己退出去(恢复压栈前的初始状态)

}

if(!isEmpty())//当一个元素出去后，两种选择，一个是继续退下一个，一个是把自己再装进来

{

m=pop();

path[curp]=m; curp++;

digui(pos,path,curp);//退出去以后继续调用 push(m);//恢复退出前初始的状态 }

if(pos==n&&isEmpty()) {

for(i=0;i}

3. 主函数算法

int main() {

cout<<\"****************************************\"<char c; int path[max];

欢迎进入车厢调度程序

for(int a=0;a<100;a++) {

cout<<\"\\n退出实验请输入Q,继续实验请输入其他任何一个字母:\"; cin>>c;

if(c=='Q'||c=='q') return 0; else {

printf(\"输入车厢数目:\"); scanf(\"%d\ if(n<=0||n>50){ printf(\"input error!\\n\"); }

else{ init(); push(1);

printf(\"输出结果：\\n\"); digui(1,path,0); } } }

return 1; }

4. 函数调用关系图

Main Init digui Push pop isEmpty 四、调试分析

1. 本次作业的数据结构比较简单，但是递归算法是其核心，在每一个车厢入栈或出栈

后，都面临两种选择，一个是继续入栈，一个是继续出栈，正如提示所分析的，该情况具有先天的递归性，所以本代码编写时使用了递归算法，依次求得各种情况的值。

2. 栈元素中的base没有用处，所以删除了本代码中的堆栈更像一个带有头元素位置

情况的数组，这样在执行过程中更方便，也保留了堆栈的特点。 3. 本程序限定输入在1-50之间，所以由其他非法输入会报错。 4. 递归算法的时间复杂度？？ 五、用户手册

1. 本程序的运行环境为DOS操作系统，执行文件为：busdiaodu.exe 2. 进入演示程序后即显示如下用户界面：

3. 进入程序后，键入非q值和初始值即可进行计算，结束符为q或Q 六、测试结果

输入n=1, 输出结果为： 1

n=2, 输出结果为: 21 12

n=3, 输出结果为:

321 231 213 132 123 n=4，输出结果为：

4321 3421 3241 3214 2431 2341 2314 2143 2134 1432 1342 1324

1243 1234

六、附录

源程序文件清单： Busdiaodu.cpp //主程序