南京信息工程大学本科课程设计报告

成绩：__________课程设计（数据结构）院、系计算机与软件学院专业软件工程姓名学号指导教师二零一五年十二月二十五日1南京信息工程大学课程设计车厢调度问题摘要：车厢调度问题要求通过对车厢序列的调整，输出所有可能的车厢顺序。本问题需要设计一个栈来模拟调度站，利用递归的方法输出所有可能，利用数组储存信息，入栈和出栈模拟了车厢进站和出站的过程。主要问题就是设计函数来模拟进站出站的过程。关键词：模拟，递归，栈，车厢1、题目分析1.1、问题描述：假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3，4。设计程序求所有可能由此输出的长度为4的车厢序列1.2、解决思路：车厢只能实现进站和出站，所以需要用到栈的方法来模拟车厢进站出站，通过递归求出所有可能。2、程序结构整个程序包括定义栈和，初始化栈，入栈，出栈，判断栈是否为空，以及递归模拟车站五个函数2.1栈的基础知识①定义栈；②voidInitstack()//初始化栈；｛s.top=-1;｝③voidpush(inte)//进栈；｛将e入栈；}④intpop()//出栈；{返回栈顶元素并删除；}2⑤intEmptys()//判断栈是否为空；{ifs.top==-1returnyes;elsereturnno;}2.2、核心算法内容voidsimulation（intbegin,intpath[],intend){begin初始值为0，利用begin判断是否所有元素都已经入栈①入栈递归：if(beginn){push(begin+1);simulation(begin+1,path,end);pop();}此处采用递归，所有数据都经历入栈；②判断栈是否为空，若不为空则准备出栈处理；if(!Emptys()){m=pop();path[end]=m;end++;simulation(begin,path,end);//出栈后处理下一个元素push(m);}③输出一种可能；}2.3、主函数中调用simulation函数；3、算法分析模仿车厢进出站的规则，当一个数进栈之后会有两种结果，要么立刻出栈，要么下一个数进栈，所以利用一个递归实现这个效果，当这个数出栈之后也有两种结果，要么栈中下一个数继续出栈，要么另外一个数入栈，所以出栈段也有递归，实现这个效果。直到栈空并且所有元素都经历入栈，输出一种可能性，两重递归可以把所有可能性都输出，程序运行结束。34、运行界面5、设计体会刚开始面对题目的时候我简单的以为只是对4进行全排列，所以我设计程序实现4的全排列。后来发现了其中的主要问题和难点。火车的车厢不可以随意调动，只能通过进出车站来调整顺序，这就和栈是同样的思路，所以我又重新设计程序，利用栈来模拟车站，因为要输出所有可能，所以我想到用递归来实现，经过设计，调试，修改，最终成功运行并且得到结果。6、编译环境MicrosoftVisualC++6.0；参考文献：[1]严蔚敏吴伟民.《数据结构（c语言版）》.清华大学出版社，2015；[2]李含光郑关胜.《c语言程序设计教程》.清华大学出版社，2011；