文档介绍:回也示冬裸鼻*冷
数据结构课程设计
题目名称:车厢调度
计算机科学与技术学院
2,3,…,n。设
即实现栈类型。程
假设停在铁路调度站入口处的车厢序列的编号一次为1,计一个程序,求出所有可能由此输出的长度为n的车
回也示冬裸鼻*冷
数据结构课程设计
题目名称:车厢调度
计算机科学与技术学院
2,3,…,n。设
即实现栈类型。程
假设停在铁路调度站入口处的车厢序列的编号一次为1,计一个程序,求出所有可能由此输出的长度为n的车厢序列。
实现栈的顺序存储结构SqStack之上实现栈的基本操作,序对栈的基本操作必须借助于基本操作进行。
规定:
输入的形式为整形,输入值的范围为100内整数;
输出的形式为整形,以2位的固定位宽输出;
程序所能达到的功能;输入车厢长度n输出所有可能的车厢序列;
测试数据:测试数据取n=3,4,0,101,程序输出的结果应该在屏幕上显示出来。
:火车调度问题最适合用数据结构中的栈来解决。而解决相应问题算法核心,是栈的递归。所以程序除了要有栈的基本函数,还要有以递归算法为核心的函数。
设计思想:一个数的进栈以后,有两种处理方式:要么立刻出栈,或者下一个数的进栈(如果还有下一个元素)。其出栈以后,也有两种处理方式:要么继续出栈(栈不为空),或者下一个数的入栈。
核心算法:包含两重递归,下一个元素处理完后返回,再处理出栈的递归。进栈的递归跳出条件为最后一个元素进栈。出栈的递归跳出条件为栈空
各模块功能如下:
栈的定义:
struct
snode
//结构体
void
Initstack()
//初始化
void
push(intq)
//入栈
int
pop()
//出栈
int
Emptys()
//判断栈是否为空
核心算法:
voidprocess(intpos,intpath[],int curp)//当前处理位置pos的兀素
栈的数据结构:
structsnode
{
intdata[MaxLen];inttop;
}s;//定义一个栈指针void Initstack()〃初始化
{
=-1;
}
voidpush(intq)//入栈
{
++;
[]=q;
}
intpop()//出栈
{
inttemp;temp=[];--;
returntemp;
}
int Emptys()〃判断栈是否为空
if(==-1)
return1;
else
return0;
}
核心算法:
voidprocess(intpos,intpath[],int curp)//当前处理位置pos的兀素
{
intm,i;
if(pos<n)//编号voidprocess(intpos,intpath[],intcurp)//当前
处理位置pos的兀素进栈递归
{
push(pos+l);〃当前元素进栈后下一个元素继续进栈process(pos,path,curp);〃出栈后处理下一个元素继续进栈push(m);
}
if(pos=n&&Emptys()