文档介绍：车厢调度排序综合二〇一四年六月车厢调度 1 .问题陈述假设停在铁路调度站入口处的车厢序列的编号一次为 1,2,3,4 。设计一个程序,求出所有可能由此输出的长度为 4的车厢序列。 2. 需求分析(1)根据栈的顺序存储结构 SqStack 之上实现栈的基本操作,即实现栈类型。(2) 程序对任何栈的任何存取(即更改、读取和状态判别等操作)必须借助于软件综合课程设计基本操作执行。(3)用户可以自己输入调度的大小,然后由程序自动生成结果。 3 .概要设计车厢调度是栈的典型运用,要知道车厢调度是怎样的思想,首先就必须掌握栈的相关知识,才能更好的实现其主要功能。栈的定义栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。栈中没有数据元素时,称为空栈。栈的插入操作通常称为压栈或进栈,栈的删除操作通常称为退栈或出栈。栈的主要特点是“后进先出”,即后进栈的元素先弹出。每次进栈的数据元素都放在当前栈顶元素之前成为新的栈顶元素,每次出栈的数据元素都是当前栈顶元素。栈也称为后进先出表。抽象数据类型栈的定义如下: ADT Stack {数据对象:D={a1|i<=i<=n,n>=0,ai 为ElemType 类型} 数据关系: R={<ai,ai+1>|ai,ai+1 ∈D,i=1, …,n-1} 基本运算: InitStack(&s): 初始化栈,构造一个空栈 s; Push(&s,e): 进栈,将元素 e插入到栈 s中作为栈顶元素; Pop(&s,e): 出栈,从栈 s中退出栈顶元素,并将其值赋给 e。}4 .详细设计算法设计本程序设计从总体上划分四个功能模块:栈基本操作的定义 3个,操作函数模块 1个。 1) 栈基本操作定义模块包括栈的初始化,出栈、进栈。包含的函数为, InitStack(),Push(),Pop(). Void InitStack() {定义初始化操作,是指针指向-1; }Void Push() {定义定义进栈操作,先把要进栈的数赋给指针所指的位置,再让指针+1 }Void Pop() {先把指针-1,再把所指的位置上的元素返回}2)操作函数模块 void Operation () {实现初始化序列, 判断序列是否满足结束条件, 产生新的序列再判断等等功能。} 注意要点: 要求车厢高度的方法, 1代表进栈, 0代表出栈(1) 第一位一定要是 1,因为不能一开始就出栈; (2) 最后一位不能为期不远(也就是为 0),因为最后不能进栈; (3)0 和1的数目要匹配,这里 0和1都是输入车厢节数; (4)0 不能比 1多。 5 .程序代码#include<iostream> #include<> #include<fstream> #define STACK_SIZE 30 #define STACKADD 10 #define NULL 0 #define MAX 1000 using namespace std; typedef struct { int *base; int *top; int stacksize; int length; }SqStack; void Initlist(SqStack *s); void Operation(SqStack *s); int a[MAX]={0}; int b=0,i; int main() { SqStack s; int h=0; Initlist(&s); Operation(&s); char *path="E:\\ "; ofstream fout(path); if(fout) { while(a[h]!=0) { cout<<a[h]<<" "; fout<<a[h]<<" "; h++; if(h%i==0) { cout<<endl; fout<<endl; }}} return 0; } void Initlist(SqStack *s) { s->base=s->top=(int *)malloc(STACK_SIZE*sizeof(int)); if(!s->base) { cout<<" 开辟失败"; exit(1); } s->length=0; s->stacksize=STACK_SIZE; } void Push(SqStack *s,int i) { if(s->length==s->stacksize) { s->base=(int *)realloc(s->base,(STACK_SIZE+STACKADD)*sizeof(int)); s->length=