(车厢调度)论文

1、摘 要车厢调度问题要求用户输入车厢的长度，然后有程序自动输出这些车厢经过调度站后输出的序列，要求输出所有的序列。本问题要求用栈模拟调度站，设计递归函数输出所有的序列，用数组存储输出的序列。重点就是产生序列的递归函数。编号为1,2，n的车厢 经过铁路调度站后输出不同的序列，本问题就是要把所有的长度为n的序列输出。一般来说，本问题在操作过程的任何状态下都有两种可能的操作，“入”“出”。每个状态下处理问题的方法都是相同的，这说明问题本身具有天然的递归特性，所以用递归算法实现。用一个顺序栈模拟铁路调度站，设计一个函数用于输出所有的序列，输出序列用数组存储。关键字：车厢调度; 递归特性; 顺序栈12目

2、录1、题目分析11.1设计目的11.2目的分析12、设计思路22.1需求分析22.2概要设计22.3详细设计33、实验结果和测试过程44、课设的设计体会及问题分析65、参考文献66、源程序代码61、题目分析1.1设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作

3、。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计

4、算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2目的分析(1)这个实验要求我用栈实现车厢调度.(2)车厢的个数是由用户输入的.(3)程序会自动给车厢进行从1到 n的编号.(4)用户输入车厢个数

5、后,程序打印出所有可能的车厢出站顺序.2、设计思路2.1需求分析本程序的任务是：假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3n。设计一个程序，求出所有可能由此输入的长度为N的车厢序列。若实现车厢调度的基本要求，所以需要建立一个栈来实现。栈的特性是先进后出，而根据栈的特性，进栈与出栈都有两种可能：一个数进栈后，要么立即出栈，要么进行下一个数的进栈；同样一个数出栈后，在栈不为空的情况下要么继续出栈，要么进行下一个数的进栈；输入一个车厢长度，从而得到由此输出长度为n的车厢序列，并定义一个二维数组来保存所有的输出序列。2.2概要设计1.定义栈的抽象数据类型定义： 基本操作：I struct

6、 SNodeint data45;int top;S; 操作结果：构造一个栈S。void InitStack() S.top=-1;操作结果：置栈S为空栈if(!StackEmpty()操作结果：判断栈空 void Push(int q) S.data+S.top=q;操作结果：在栈S的栈顶插入栈顶元素int Pop() int temp;temp=S.dataS.top-;return temp;操作结果：删除栈顶元素，出栈2.定义一个二维数组来保存所有的输出序列Struct pathsint paths4545;int number；allpath；定义全局变量Int n；Int path

7、4545;2.3详细设计（1）栈类型：struct SNodeint data45;int top;S;（2）栈的基本操作设置如下：void InitStack()S.top=-1;/初始化，设S为空栈(4)主函数流程图1. 栈的数据定义，输出操作信息，并输入数据2. 初始化栈3. for循环控制输出语句，车厢好依次进栈4. 判断循环结束条件5.调用函数operation（），输出所有情况。开始提示信息初始化表达式1表达式2表达式3结束函数调用图13、实验结果和测试过程1.此车厢调度的基本要求比较简单，只要掌握好栈的基本特性和基本操作，一般都能顺利完成。 2.此系统需要运用递归算法，所以还必须

8、对整个系统有个清晰的认识和思路，这样才能更好的掌握运行的详细过程与结果。每个步骤都有两种可能，那怎样解决操作问题呢？我决定先以入栈为主，能入先入，操作完毕后恢复至分步时的状态，再进行出栈的操作，这样两种可能就都完成了。 3.此系统中还有一个要求就是显示出操出作序列的状态的变化过程，因此，必须弄清楚栈的基本性质，谁先入栈，谁先出栈，每一步的过程必须清晰明了。 4.数据存储是用了一个数组，便于存储。运行结果图2运行结果如下图3不足之处在于对车厢个数进行了限制,车厢数越小越稳定.还有就是一次只能对一组车厢进行调度4、课设的设计体会及问题分析 经过七天的课程设计，感触颇深。这段时间，自己对于软件技术基

9、础理解的更加透彻。以前对于抽象的栈的运用不是很明了，现在已经会编写一些简单的源代码。比如栈的长度，初始化，删除，入栈和出栈等基本操作与基本特性，通过此次的课程设计，从原先的理论运用到现实的实践中，加深了对栈的理解。总体来说栈结构是比较容易的结构，所以现在能对栈的基本操作能比较熟练的运用了。但是由于此次设计用到了递归算法，基于对递归算法平时训练不是很多，故存在一些设计的问题。我完成了本次的课程设计报告，其中的到了很多的体会，也了解了很多的知识点。深刻的体会到做题目与看题目不是一个层次的，有些问题看书能看懂，感觉很简单，到真的去做的时候才发现没那么简单。所一通过这次课程设计，让我明白了不要一味的看

10、书，要自己动手去实践，才能够真正的把知识学好学透。5、参考文献1严蔚敏，吴伟民数据结构：C语言版M清华大学出版社19922陈维兴，林小茶.C+面向对象程序设计教程（第三版）M清华大学出版社19913徐德民.最新C语言程序设计M电子工业出版社1992年4唐策善，黄刘生.数据结构M中国科学技术出版社.1992年5仲萃豪，冯玉琳.程序设计方法学M北京科学技术出版社1985年6、源程序代码#include#includeint n;int path45; /定义全局变量struct pathssint paths4545;int number;AllPath; /定义一个二维数组来保存所有的输出序列s

11、truct SNodeint data45;int top;S; /栈的顺序存储结构的定义void InitStack() /栈的初始化S.top=-1;void Push(int q) /进栈S.data+S.top=q;int Pop() /出栈int temp;temp=S.dataS.top-;return temp;int StackEmpty() /判断栈是否为空if(S.top=-1) return 1;else return 0;void Attemper(int pos,int path,int cur) /调度过程int m,i;if(posn) Push(pos+1);

12、/一个数进栈后,要么立刻出栈,要么进行下一个数的进栈 Attemper(pos+1,path,cur); Pop();if(!StackEmpty() m=Pop(); /一个数出栈后,要么继续出栈(栈不空),要么继续下一个数的进栈 pathcur+=m; Attemper(pos,path,cur); Push(m);if(pos=n & StackEmpty() /一种可能输出序列产生 coutttt; coutAllPath.number+1:; for(i=0;icur;i+) coutpathi ; AllPath.pathsAllPath.numberi=pathi; /将每种序列

13、保存在二维数组里 cout=0;i-) coutttt |S.datai|n;void DisplayOnly(int k,int Output,int Input) /显示操作序列的状态的变化过程 int j;getchar(); /每按一次回车,就有一次变化for(j=0;j=Output;j+) cout-AllPath.pathskj; /负责显示输出序列的状态变化coutendl;Print(); /栈的状态变化coutttttt;for(j=Input;j=n;j+) /负责显示输入序列的状态变化 cout-j; coutendl;void ChooseDisplay() /状态变

14、化过程int k,Output,Input=1;coutk;k=k-1;InitStack();coutn 输出序列t 栈tt 输入序列;DisplayOnly(k,-1,1);for(Output=0;Output=Input) /当输出序列中当前的数据大于等于入口处 /的数据时, 入口处的数据要一直压栈,while(AllPath.pathskOutput=Input) /直到当前的数据小于入口处的数据 Push(Input); Input+; DisplayOnly(k,Output-1,Input); Pop();DisplayOnly(k,Output,Input); else /当序列中当前的数据小于入口处 /的数据时,弹出栈顶,重新显示结果 Pop(); DisplayOnly(k,Output,Input); void message() /菜单显示coutendl;cout1:输入火车的长度endl;cout2:输出所有可能序列endl;cout3:演示一个序列变化endl; cout4:退出本程序endl;coutendl;void Input