车厢调度问题课程设计

1、目 录目 录- 1 -正 文1一、题目分析1二、概要设计1三、详细设计3四、运行结果8五、课程设计体会9六、参考文献9正 文一、题目分析课程设计题目车厢调度：假设停在铁路调度站的车厢序列的编号依次为1，2.，3，.n。 设计一个程序，求出所有可能输出的长度为n的车厢序列。基本要求首先在教科书3.1.2节中提供的栈的顺序结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作进行。二、概要设计1设定栈的抽象数据类型定义：ADT Stack 数据对象：D=CharSet,i=1,2,.,n,n0数据关系：R1=D,i=2,.,n基本

2、操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TURE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若S不空，则e返回栈顶元素。Push（&S，&e）初始条件：栈S已存在。操作结果：在s的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。

3、操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（）初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。ADT Stack2.本程序包含两个模块1）主程序模块：Void main()初始化;For循环2）栈模块实现栈的抽象数据类型各模块之间的调用关系如下：主程序模块栈模块三、详细设计1）栈类型；typedef struct stacklistSElemType *base;SElemType *top;int stacksize;SqStack;栈的基本操作设置如下：void Stack_init(SqStack *s)

4、/初始化，设s为空栈void Stack_Push(SqStack *s,SElemType e)/若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE/若栈不变，并返回FALSESElemType Stack_Pop(SqStack *s)Status Stack_Empty(SqStack *s)Status Stack_Full(SqStack *s)void Stack_printreverse(SqStack s)void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)2)代码#includ

5、e using namespace std;typedef int SElemType;typedef int Status;int end;/*最后一个车厢的号码*/long total=0;/*总的组合方案数目*/typedef struct stacklistSElemType *base;SElemType *top;int stacksize;SqStack;void Stack_init(SqStack *s)s-base=(SElemType *)malloc(end*sizeof(int);if(!s-base) exit(0);s-top=s-base;s-stacksize

6、=end;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=end)return 1;return 0;void Stack_printreverse(SqStack s)int *

7、po;po=s.base;printf(t%ld: ,total);for(;po!=s.top;) printf(%d ,*po+);printf(n);void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)if(!Stack_Empty(inputPoint)Stack_Push(tempPoint,Stack_Pop(inputPoint);search(inputPoint,tempPoint,outputPoint);Stack_Push(inputPoint,Stack_Pop(tempPoi

8、nt);if(!Stack_Empty(tempPoint)Stack_Push(outputPoint,Stack_Pop(tempPoint);search(inputPoint,tempPoint,outputPoint);Stack_Push(tempPoint,Stack_Pop(outputPoint);if(Stack_Full(outputPoint)total+;Stack_printreverse(*outputPoint);主函数：void main()SqStack input,temp,output;int i;printf(nntttt车厢调度n);printf(n

9、t请输入车厢长度: );scanf(%d,&end);/*初始化三个栈*/Stack_init(&input);Stack_init(&temp);Stack_init(&output);/*将车厢号码进栈*/for(i=end;i=1;i-)Stack_Push(&input,i);search(&input,&temp,&output);3）主函数流程图开始提示输入输出初始化表达式2表达式3函数调用结束表达式1 1.栈的数据定义，输出操作信息民，并输入数据 2. 初始化三个栈input,temp,output3.for循环控制输出语句，车厢号依次进栈判断循环结束条件 4. 调用函数Stac

10、k_Push(&input,i); search(&input,&temp,&output);输出所有情况四、运行结果输入3，结果如下：输入4，结果如下：五、课程设计体会 通过对本学期的数据结构和课程的学习，我完成了本次的课程设计报告，其中得到了很多的体会，也了解到很多的知识点。我明白了课程设计是大学教育中一个重要的实践教学环节。在课程设计过程中,我根据具体设计题目，运用自己所学的知识，独立地进行设计和实验。除了巩固、加深和融合自己所学的数据结构专业课程知识外，更重要的是培养了我多方面的能力，如独立思考能力、综合设计能力、实践动手能力、开拓创新能力、自学能力、文献检索能力等等。通过这次的课程设计，我也了解到自己所学的一些不足之处，以及一些