车厢调度问题-课程设计报告

山东交通学院数据结构课程设计车厢调度问题院(系)别信息工程系班级计算133学号130811341姓名闫琛指导教师王成时间2015-03-09—2015-03-20课程设计任务书题目车厢调度问题系(部)信息科学与电气工程学院专业计算机科学与技术班级计算133学生姓名闫琛学号1308113413月9日至3月20日共2周指导教师(签字)系主任(签字)年月日成绩评定表作品成绩报告成绩口试（答辩）成绩总评成绩目录1课程设计概述.........................................................................................错误!未定义书签。1.1车厢调度问题功能概述......................................................................................错误!未定义书签。2车厢调度问题总体设计........................................................................................................错误!未定义书签。2.1全局变量定义.............................................................................................................错误!未定义书签。2.2栈的定义.......................................................................................................................错误!未定义书签。3.算法设计............................................................................................................................23.1用到的进出栈算法基础知识...............................................................................错误!未定义书签。3.2程序分析.......................................................................................................................错误!未定义书签。3.2.2核心算法..........................................................................................................43.2.3主程序描述.....................................................................................................54.程序实现..........................................................................................................................54.1运行界面..................................................................................................................54.2不足之处...................................................................................................................75.设计体会...........................................................................................................................76.结束语.................................................................................................................................81车厢调度问题摘要：通过输入车厢系列的编号n，求出所有可能由此输出的长度为n的车厢系列，用入栈出栈的方法，实现车厢调度，并演示每一种出栈序列的过程。任务：假设停在铁路调度站入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n的车厢系列。关键字：车厢,调度,栈,递归0.引言随着人民生活水平的提高，越来越多的人坐火车出去旅游，这也让火车车厢的量大量增大，也随之出现了一个问题，即合理的调度车厢，本课程设计即利用数据结构里的栈的知识，设计一个合理的算法，来解决此问题。1.需求分析假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3,……，n,设计一个程序，求出所有可能的长度为n的车厢序列。实现栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的基本操作必须借助于基本操作进行。测试数据取n=3，4,程序输出的结果应该在屏幕上显示出来。2.数据结构设计2.1全局变量定义typedefintSElemType;typedefintStatus;2intend;/*最后一个车厢的号码*/longtotal=0;/*总的组合方案数目*/2.2栈的定义typedefstructstacklistvoidStack_init(SqStack*s)voidStack_Push(SqStack*s,SElemTypee)SElemTypeStack_Pop(SqStack*s)StatusStack_Empty(SqStack*s)StatusStack_Full(SqStack*s)voidStack_printreverse(SqStacks)3.算法设计3.1用到的进出栈算法基础知识（1）根据要求，了解可能要用到的算法：3.1.1进栈（PUSH）算法①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；②置TOP=TOP+1（栈指针加１，指向进栈地址）；③S(TOP)=X，结束（X为新进栈的元素）；3.1.2退栈（POP）算法①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；②X=S(SOP)，（退栈后的元素赋给X）；③TOP=TOP-1，结束（栈指针减１，指向栈顶）。3.2程序分析3.2.1.栈的数据结构typedefstructstacklist{3SElemType*base;SElemType*top;intstacksize;}SqStack;voidStack_init(SqStack*s){s-base=(SElemType*)malloc(end*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=end;}voidStack_Push(SqStack*s,SElemTypee){*(s-top)++=e;}SElemTypeStack_Pop(SqStack*s){if(s-top==s-base)return0;return*(--(s-top));}StatusStack_Empty(SqStack*s){if(s-top==s-base)return1;return0;}StatusStack_Full(SqStack*s){if(s-top-s-base==end)4return1;return0;}voidStack_printreverse(SqStacks){int*po;po=s.base;printf([%ld]:,total);for(;po!=s.top;)printf(%d,*po++);printf(\n);}3.2.2核心算法voidsearch(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(tempPoint));}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++;5Stack_printreverse(*outputPoint);}}3.2.3主程序描述voidmain(){SqStackinput,temp,output;inti;printf(请输入车厢数(2-30)\n);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);printf(thetotal:%ld\\n,total);getch();}4.程序实现4.1运行界面(1)运行主界面6(2)当输入n的值为3时，屏幕显示7(3)当输入n的值为4时，屏幕显示4.2不足之处我这个程序主要通过设置三个栈来实现，核心算法通过两次递归调用实现。可以实现任务书里所要求的功能，但是也存在着不足之处，就是在运行界面，输出n值，按回车键，得到输出结果后，要想继续输入另一数值n,不能返回，只有退出，重新运行，才能输入得到输出结果。5.设计体会看到自己写的程序成功的运行真是种莫大的欣喜！很多时候，总是感觉学到的东西不知何用，总想用学过的语言来写些程序，却一直不知道写些什么。终于，机会来到了，数据结构课程设计，让我一下子回忆起了以前学到的很多语言，于是，就有了运用自己所学的所有语言分别来实现车厢的调度。通过这个星期的课程设计，我的收获还是不少。我的编程水平有了比较大的提高，虽然我做的程序里还有写问题，做的不够深入，但独立完成一个比较大一点的程序的经历也8是很宝贵的。6.结束语本课程设计主要是为了实现解决以下问题的程序：假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3……N。求出所有由此输出的长度为N的车厢序列。我在解决这个问题时，用的是VisualC++来做到这点的。参考文献[1]严蔚敏。《数据结构习题》，清华大学出版社[2]许卓群，杨冬青。《数据结构与算法》，高等教育出版社[3]张乃孝，裘宗燕。《数据结构—C++与面向对象的途经(修订版)》，高等教育出版社