24车厢调度问题课程设计

第1页课程设计(论文)任务书软件学院学院软件+会计专业2012—2班一、课程设计(论文)题目车厢调度问题二、课程设计(论文)工作自2013年12月30日起至2014年1月5日止三、课程设计(论文)地点:创新大楼软件实训中心机房四、课程设计(论文)内容要求：1．本课程设计的目的⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；⑵初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2．课程设计的任务及要求1）基本要求：⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释；⑷每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；⑵课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准：⑴学习态度：10分；⑵系统设计：20分；⑶编程调试：20分；第2页⑷回答问题：20分；⑸论文撰写：30分。第2页4）参考文献：⑴严蔚敏,吴伟民.数据结构(C语言版)[M].清华大学出版社.2010.3⑵严蔚敏,吴伟民.数据结构题集(C语言版)[M].清华大学出版社.1999.2⑶何钦铭,冯燕等.数据结构课程设计[M].浙江大学出版社.2007.85）课程设计进度安排⑴准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；⑵程序模块设计分析阶段（4学时）：程序概要设计、详细设计；⑶代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；⑷撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名：2013年12月29日6）课程设计题目具体要求：车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n的车厢系列。基本要求：⑴设计一个程序，求出由一个编号依次为1，2，、、、，n的车厢序列可能产生的所有出栈系列。⑵利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。⑶对于每个输出序列演示出所有操作序列的变化过程课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：王英华职称：讲师2014年1月8日《数据结构》课程设计题目：车厢调度问题学院：软件学院班级：12软件+会计2班学生：韩嵩目录正文一、设计任务................................................................1二、需求分析................................................................11、抽象数据类型........................................................................................12、存储结构定义........................................................................................23、基本操作................................................................................................3三、系统设计1、问题分解................................................................................................32、模块结构................................................................................................43、解题思路................................................................................................4四、编码实现................................................................4五、调试分析................................................................71、实验数据................................................................................................72、实验结果................................................................................................7六、课设总结................................................................91、数据结构使用小结................................................................................92、需完善之处............................................................................................9课程设计体会、参考文献...........................................10第1页正文一、设计任务车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n的车厢系列。基本要求：⑴设计一个程序，求出由一个编号依次为1，2，、、、，n的车厢序列可能产生的所有出栈系列。⑵利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。⑶对于每个输出序列演示出所有操作序列的变化过程。二、需求分析1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTStack{数据对象：D={iiaa|∈CharSet,i=1,2,...,n,,n≥0}数据关系：R1={iiiiaaaa,|,11∈D,i=2,...,n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。第2页操作结果：将栈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已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。}ADTStack2.存储结构定义数据存储结构的C语言定义如下：typedefintSElemType;typedefintStatus;intfinish;//最后一个车厢号码typedefstructSNode{SElemType*base;SElemType*top;intstacksize;第3页}SqStack;3.基本操作数据结构的基本操作实现如下：voidInitStack(SqStack*s)//初始化，设s为空栈voidPush(SqStack*s,SElemTypee)//若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE，若栈不变，并返回FALSESElemTypePop(SqStack*s)StatusStackEmpty(SqStack*s)StatusFull(SqStack*s)voidPrintreverse(SqStacks)voidSearch(SqStack*InputPoint,SqStack*TempPoint,SqStack*OutputPoint)三、系统设计1.问题分解该问题主要应实现以下功能：1.栈的初始化2.函数的递归调用3.进栈出栈3.栈的打印2.模块结构系统主要由两个模块组成，分别是：第4页1.主程序模块2.栈模块模块之间的结构如下：主程序3.解题思路各模块的实现步骤为：1.栈的存储定义，输出操作信息，并输入数据2.初始化三个栈Input,Temp,Output3.for循环控制输出语句，车厢号依次进栈4.输出所有情况四、编码实现#includestdio.h#includemalloc.h#includeiostreamusingnamespacestd;typedefintSElemType;typedefintStatus;intfinish;//最后一个车厢号码typedefstructSNode{SElemType*base;SElemType*top;主程序栈第5页intstacksize;}SqStack;voidInitStack(SqStack*s){s-base=(SElemType*)malloc(finish*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=finish;}voidPush(SqStack*s,SElemTypee)//插入{*(s-top)++=e;}SElemTypePop(SqStack*s)//删除{if(s-top==s-base)return0;return*(--(s-top));}StatusStackEmpty(SqStack*s)//判断{if(s-top==s-base)return1;return0;}第6页StatusFull(SqStack*s){if(s-top-s-base==finish)return1;return0;}voidPrintreverse(SqStacks){int*p;p=s.base;for(;p!=s.top;)printf(%d,*p++);printf(\n);}voidSearch(SqStack*InputPoint,SqStack*TempPoint,SqStack*OutputPoint){if(!StackEmpty(InputPoint)){Push(