车厢调度问题课程设计

1、课程设计(论文)任务书 软 件 学 院 学 院 软 件+会计 专 业 20122 班一、课程设计(论文)题目 车厢调度问题 二、课程设计(论文)工作自 2013 年 12 月 30 日起至 2014 年 1 月 5 日止 三、课程设计(论文) 地点: 创新大楼软件实训中心机房 四、课程设计(论文)内容要求：1本课程设计的目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2课程

2、设计的任务及要求1）基本要求：要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释；每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；设计部分应包

3、含系统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准： 学习态度：10分；系统设计：20分；编程调试：20分；回答问题：20分；论文撰写：30分。第 1 页4）参考文献：严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3 严蔚敏,吴伟民. 数据结构题集(C语言版)M. 清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社. 2007.85）课程设计进度安排准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；程序模块设计分析阶段（4学时）：程序概要设计、详细设计；代码编写调试阶段（8学时）：程序模块代码编写、调试、

4、测试；撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。 学生签名： 2013 年 12 月 29 日6） 课程设计题目具体要求：车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，n。设计一个程序,求出所有可能由此输出的长度为n 的车厢系列。基本要求：设计一个程序，求出由一个编号依次为1，2，、，n的车厢序列可能产生的所有出栈系列。利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。 对于每个输出序列演示出所有操作序列的变化过程 课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般

5、（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 王英华 职称： 讲师 2014 年 1 月 8 日 数据结构课程设计 题目： 车厢调度问题 学院： 软件学院 班级： 12软件+会计2班 学生： 韩嵩 目录正文一、设计任务.1二、需求分析.11、抽象数据类型.12、存储结构定义.23、基本操作.3三

6、、系统设计1、问题分解.32、模块结构.43、解题思路.4四、编码实现.4五、调试分析.71、实验数据.72、实验结果.7六、课设总结.91、数据结构使用小结.92、需完善之处.9课程设计体会、参考文献.10正 文1、 设计任务车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，n。设计一个程序,求出所有可能由此输出的长度为n 的车厢系列。基本要求：设计一个程序，求出由一个编号依次为1，2，、，n的车厢序列可能产生的所有出栈系列。利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。 对于每个输出序列演示出所有操作序列的变化过程

7、。二、需求分析1. 抽象数据类型本设计中用到的数据结构ADT定义如下：ADT Stack 数据对象：D=CharSet,i=1,2,.,n,n0数据关系：R1=<D,i=2,.,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TURE，否则返回FALS

8、E。GetTop(S,&e)初始条件：栈S已存在。操作结果：若S不空，则e返回栈顶元素。Push（&S，&e）初始条件：栈S已存在。操作结果：在s的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（）初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。ADT Stack2. 存储结构定义数据存储结构的C语言定义如下：typedef int SElemType;typedef int Status;int finish

9、; /最后一个车厢号码typedef struct SNodeSElemType *base;SElemType *top;int stacksize;SqStack;3. 基本操作数据结构的基本操作实现如下：void InitStack(SqStack *s)/初始化，设s为空栈void Push(SqStack *s,SElemType e)/若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE，若栈不变，并返回FALSESElemType Pop(SqStack *s)Status StackEmpty(SqStack *s)Status Full(SqStack *s)void

10、Printreverse(SqStack s)void Search(SqStack *InputPoint,SqStack *TempPoint,SqStack *OutputPoint)三、系统设计1. 问题分解该问题主要应实现以下功能：1. 栈的初始化2. 函数的递归调用3. 进栈出栈3.栈的打印2. 模块结构系统主要由两个模块组成，分别是：1.主程序模块2.栈模块 栈 主程序模块之间的结构如下： 主程序3. 解题思路各模块的实现步骤为：1. 栈的存储定义，输出操作信息，并输入数据2. 初始化三个栈Input,Temp,Output3.for循环控制输出语句，车厢号依次进栈4.输出所有情

11、况四、编码实现#include <stdio.h> #include<malloc.h>#include<iostream>using namespace std;typedef int SElemType;typedef int Status;int finish; /最后一个车厢号码typedef struct SNodeSElemType *base;SElemType *top;int stacksize;SqStack;void InitStack(SqStack *s)s->base=(SElemType *)malloc(finish*s

12、izeof(int);if(!s->base) exit(0);s->top=s->base;s->stacksize=finish;void Push(SqStack *s,SElemType e) /插入 *(s->top)+=e;SElemType Pop(SqStack *s) /删除 if(s->top=s->base)return 0;return *(-(s->top);Status StackEmpty(SqStack *s) /判断 if(s->top=s->base)return 1;return 0;Status

13、 Full(SqStack *s)if(s->top-s->base=finish)return 1;return 0;void Printreverse(SqStack s)int *p;p=s.base;for( ;p!=s.top; ) printf("%d ",*p+);printf("n");void Search(SqStack *InputPoint,SqStack *TempPoint,SqStack *OutputPoint)if(!StackEmpty(InputPoint)Push(TempPoint,Pop(Input

14、Point);Search(InputPoint,TempPoint,OutputPoint);Push(InputPoint,Pop(TempPoint);if(!StackEmpty(TempPoint)Push(OutputPoint,Pop(TempPoint);Search(InputPoint,TempPoint,OutputPoint);Push(TempPoint,Pop(OutputPoint);if(Full(OutputPoint)Printreverse(*OutputPoint);int main()SqStack Input,Temp,Output;int i;pr

15、intf("请输入车厢长度:n ");printf("*韩嵩制作*n");printf("备注：输入车厢长度即可得到所有进栈序列n"); scanf("%d",&finish); InitStack(&Input);/初始化 InitStack(&Temp);InitStack(&Output);for(i=finish;i>=1;i-) /进栈 Push(&Input,i);Search(&Input,&Temp,&Output); /输出所有

16、可能存在的情况 五、调试分析1. 实验数据 车厢的长度：3，52. 实验结果 六、课设总结1. 数据结构使用小结栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈！2. 需完善之处此程序不能让人清除的观察到操作的状态与变化过程，这点需要改进第 10 页课程设计体会通过此次课