火车调度.doc

山东理工大学计算机学院课 程 设 计（数据结构）班 级姓 名学 号 指导教师2013年 1 月 7日课程设计任务书及成绩评定课题名称 火车调度问题、题目的目的和要求： 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 、设计进度及完成情况日 期内 容1月7日选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1月9日创建相关数据结构,录入源程序。1月11日调试程序并记录调试中的问题，初步完成课程设计报告。1月15日上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。1月16日考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二零一三 年 一 月 七 日目 录第一章 概述1第二章 系统分析2第三章 概要设计第四章 详细设计第五章 运行与测试第六章 总结与心得参考文献第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是车厢调度。车厢调度问题主要是一个针对火车站,出站进站的几种方案。首先统计出所有的可能的方案，其次就是把这些方案都能转换成“出站”“进站”这种显示形式，最后要提供一个查找功能，核对某种进出站的顺序是否是正确的。第二章 系统分析1.车厢调度就是模拟车厢调度站的工作，与数据结构中栈的存储结构类似，故而栈的基本操作为本程序的核心基础，本程序要求：（1）在程序中输入待进站的车厢序列时，不需要输入所有的车厢编号，只需要输入首列车厢的编号和尾列车厢的编号即可。需要分别输入两个整型数据。（2）程序的输出信息主要是：车厢出站的所有序列，或查找序列的可行性，对于可行性的输出。可附带输出车厢的进出序列。（一连串的:出入出入）（3） 程序的功能包括：对栈的数据结构的基本操作，如入栈，出栈等。以及对车厢进站，出站的操作。2.演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言是转化。系统中子程序及功能要求：（1）.in(SqStack *s1,SqStack *s2,int first,int final,int num):对车厢进行入站操作。并记录操作的次数。题目要求的一对整形数据的输入 (2)show(SqStack *s,int way)：所有进站，出站完成后对输出序列进行输出。(3)out(SqStack *s1,SqStack *s2,int first,int final,int num)：对车厢行出站操作。并记录操作次数。 (4)Control(SqStack *s1,SqStack *s2,int first,int final,int num)：对I n和out函数进行调用。在in和out函数里间接递归。 题目要求的递归在这里可以自然的实现 程序的调用过程如下： 主函数可调用子程序1，3，4； 子程序3可调用子程序4，2； 子程序1可调用子程序4； 子程序4可调用子程序1，3；3.程序执行时的命令：本程序为了使用时的方便，更加大众化，采用菜单式的方式来完成程序的演示，在程序执行过程中不需要什么指令，只需按提示输入相应的内容即可。（提醒：注意输入时格式，否者可能会引起一些错误）.4.测试数据。 1 2 3 4 5第三章 概要设计 1、数据机构的设计 在实验中，主要采用了栈的数据结构，因为栈的先进后出的特点是和题目中要求的车厢的进出类似的。栈的操作比较，适合递归算法的使用。 2、系统中用到的基本抽象数据定义如下： ADT Stack 数据元素：可以是任意类型的数据，但必须属于同一个数据对象。 数据关系：栈中数据元素之间是线形关系。 基本操作：（1） Initstack(&s)；（2） IsEmpty(&s)；（3） IsFull(&s)；（4） Push(&s,x)；（5） Pop(&s,&x)；（6） ClearStack(&s); (7) GetTop(&s,x);ADT Stack3、各部分的功能实现和伪代码如下： (1)、车厢入站的函数编写，伪代码实现如下： void in(SqStack *s1,SqStack *s2,int first,int final,int num) if(首列车厢号!=尾列车厢号+1)输出进出序列的字符串加入一个 “入”； 进站总操作次数减一：if(首列车厢号尾列车厢号+1)首列车厢号+； Control(s1,s2,first,final,num); （2）、车厢的出站的函数编写，伪代码实现如下： Status out(SqStack *s1,SqStack *s2,int first,int final,int num)if(剩下的操作次数=0)输出车厢序列；return 1;if(栈是空的)return 1;int exchange;进出序列字符串加上“ 出”；出栈一；进栈二；总操作次数-；Control(s1,s2,first,final,num);return 1;(3)控制函数的实现，主要是协调车厢出站和入站的函数，伪代码实现如下： int Control(SqStack *s1,SqStack *s2,int first,int final,int num)复制一份栈一的数据；复制一份栈二的数据；复制一份进出序列字符串数据；in(s1,s2,first,final,num);搬回两个栈的复制数据 搬回字符串的数据；out(s1,s2,first,final,num);return 1;（4）输出函数的实现,这一个模块的任务主要是把结果呈现在屏幕上，方面用户使用，伪代码实现如下： void show(SqStack *s,int way) if(way=0) 输出是第几个序列； for(int i=0;itop;i+) 输出栈中的数据；coutendl;elseif(way=1)int sign=1;for(int i=0;itop;i+)if(栈中的数据!=要查找的数据)sign=0;break;if(sign=1)cout已成功查找到序列:;number+; for(int i=0;itop;i+) 输出栈的数据；coutendl;cout车厢的进出序列为:top=-1;return 0;Status StackEmpty(SqStack *s)/判空if(s-top=-1)return 1;elsereturn 0;Status StackFull(SqStack *s)/判断栈满if(s-top=Stack_Size-1)return 1;elsereturn 0;Status Push(SqStack *s,SElemType e)/入栈if(s-top=Stack_Size-1)return 0;s-top+;s-elems-top=e;return 1;Status Pop(SqStack *s,SElemType *e)/出栈if(s-top=-1)return 0;else*e=s-elems-top;s-top-;return 1;(2) 车厢入站函数的详细代码 Status in(SqStack *s1,SqStack *s2,int first,int final,int num)/对车厢进行入队操作，并且纪录次数if(num0)system(pause);if(first!=final+1)myString=myString+入站 ; Push(s1,first);num-;if(firstfinal+1)first+; Control(s1,s2,first,final,num);return 0;(3) 车厢出站函数的详细代码 Status out(SqStack *s1,SqStack *s2,int first,int final,int num)/对所有车厢出站，并且记录次数if(num=0)show(s2,outWay);return 1;if(StackEmpty(s1)return 1;int exchange;myString=myString+出站 ;Pop(s1,&exchange);Push(s2,exchange);num-;Control(s1,s2,first,final,num);return 1;(4) 控制出站入站,递归调用的详细代码 Status Control(SqStack *s1,SqStack *s2,int first,int final,int num)/控制 in 和out函数调用。并且间接递归SqStack Copy1=*s1;/复制两个栈的数据SqStack Copy2=*s2;string CopyString=myString;/复制进出序列字符串数据in(s1,s2,first,final,num);*s1=Copy1;*s2=Copy2;myString=CopyString;out(s1,s2,first,final,num);return 1;(5) 屏幕显示函数的详细代码 Status show(SqStack *s,int way)/对所有出栈、入栈操作，进行显示if(way=0) cout第c+种情况：; for(int i=0;itop;i+) coutelemi ;coutendl;elseif(way=1)int sign=1;for(int i=0;itop;i+)if(s-elemi!=s3.elemi)sign=0;break;if(sign=1)cout已成功查找到序列:;c+; for(int i=0;itop;i+) coutelemi ;coutendl;cout车厢的进出序列为:endl;coutmyStringendl;return 0;主函数的详细代码:#include#include #include#include #define Stack_Size 100 /宏定义方面修改typedef int SElemType;typedef int Status;using namespace std;typedef structSElemType elemStack_Size;int top;int base;SqStack;int c;int outWay=0;string myString;SqStack s3;Status in(SqStack *s1,SqStack *s2,int first,int final,int num);Status show(SqStack *s,int way);Status out(SqStack *s1,SqStack *s2,int first,int final,int num);Status Control(SqStack *s1,SqStack *s2,int first,int final,int num);Status Initstack(SqStack *s)/建立空栈s-top=-1;return 0;Status StackEmpty(SqStack *s)/判空if(s-top=-1)return 1;elsereturn 0;Status StackFull(SqStack *s)/判断栈满if(s-top=Stack_Size-1)return 1;elsereturn 0;Status Push(SqStack *s,SElemType e)/入栈if(s-top=Stack_Size-1)return 0;s-top+;s-elems-top=e;return 1;Status Pop(SqStack *s,SElemType *e)/出栈if(s-top=-1)return 0;else*e=s-elems-top;s-top-;return 1;Status in(SqStack *s1,SqStack *s2,int first,int final,int num)/对车厢进行入队操作，并且纪录次数if(num0)system(pause);if(first!=final+1)myString=myString+入站 ; Push(s1,first);num-;if(firstfinal+1)first+; Control(s1,s2,first,final,num);return 0;Status out(SqStack *s1,SqStack *s2,int first,int final,int num)/对所有车厢出站，并且记录次数if(num=0)show(s2,outWay);return 1;if(StackEmpty(s1)return 1;int exchange;myString=myString+出站 ;Pop(s1,&exchange);Push(s2,exchange);num-;Control(s1,s2,first,final,num);return 1;Status Control(SqStack *s1,SqStack *s2,int first,int final,int num)/控制 in 和out函数调用。并且间接递归SqStack Copy1=*s1;/复制两个栈的数据SqStack Copy2=*s2;string CopyString=myString;/复制进出序列字符串数据in(s1,s2,first,final,num);*s1=Copy1;*s2=Copy2;myString=CopyString;out(s1,s2,first,final,num);return 1;Status show(SqStack *s,int way)/对所有出栈、入栈操作，进行显示if(way=0) cout第c+种情况：; for(int i=0;itop;i+) coutelemi ;coutendl;elseif(way=1)int sign=1;for(int i=0;itop;i+)if(s-elemi!=s3.elemi)sign=0;break;if(sign=1)cout已成功查找到序列:;c+; for(int i=0;itop;i+) coutelemi ;coutendl;cout车厢的进出序列为:endl;coutmyStringendl;return 0;Status diao() int FirstCar;int FinalCar;int num;string myString; SqStack s1,s2;c=1;system(cls);cout*endl;cout*-|车厢调度|-*endl;cout*endl;Initstack(&s1);Initstack(&s2);cout 请输入首列车厢号：endl;coutFirstCar;cout 请输入末尾车厢号：endl;coutFinalCar;if(FirstCarFinalCar)cout 要求输入的首列车厢号不大于尾列车厢号!endl;system(pause);/进入自动返空 diao();num=(FinalCar-FirstCar+1)*2;cout 输出全部车厢序列请按0,查找序列请按1:endl;coutmyString2;if(myString2=1)system(cls);outWay=1;cout请输入要查找的车厢序列:endl;for(int i=FirstCar;is3.elemi-1;elseif(myString2=0)system(cls);outWay=0;elsecout 没有此选项!endl;system(pause);diao ();Control(&s1,&s2,FirstCar,FinalCar,num-);if(c=1)cout您输入的序列不可行!endl;for(int i=0;i+)cout 继续操作请按1 ，结束操作请按0.endl;coutmyString;if(myString=1)diao ();break;elseif(myString