数据结构课程设计 车厢调度.docx

武汉轻工大学数学与计算机学院《数据结构》课程设计说明书题 目： 车厢调度专 业： 数学与计算机学院班 级：大类1304 学 号：姓 名：指导老师： 林菁 2014年 12月 24日题目分析课程设计题目：【问题描述】铁路调度站入口处的车厢序列编号依次为1，2，3，……，n。设计一个程序求出所有可能由此输出的长度为n的车厢序列。【基本要求】首先在教科书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作进行。【测试数据】分别取n=1,2,3,4【实现提示】一般的说，在操作过程的任何状态下都有两种可能的操作：“入”和“出”。每个状态下处理问题的方法都是相同的，这说明问题本身具有天然的递归特性，可以考虑用递归算法实现。输入序列可以仅由一对整型变量表示，即给出序列头/尾编号。输出序列用栈实现是方便的。分析：任何情况下栈的操作方式都只有两种，入栈与出栈。如果知道入栈与出栈的组合，那么问题就可以很好的解决。所以我设计了命令队列。用0表示入栈，1表示出栈。在确定的输入队列的情况下，命令队列与输出队列是一一对应的。比如当n=3时，命令队列为000111的情况对应的输出队列是321。也就是说问题转换成了求所以可能的命令队列的问题了。如何求出所以的命令队列？我的解决方案是首先找到所以可能的命令队列所在的区间，然后在把这个区间内所有的队列遍历一遍，找出合法的队列，然后根据合法的命令队列进行操作栈，从而输出结果。根据分析，我发现，可能的命令队列所在的区间的最小端是0000……1111。最大端是010101……。比如n=4时，可能的命令队列01010101之间。找到了可能的命令队列，再找合法的命令队列。把所以可能的命令队列进行如下的条件判断，都满足的即是合法的命令队列。判断条件：第一个是0，末尾一个是1.0和1各一半每出现一个1，前面必须有一个0与之对应（类似括号匹配）概要设计1．设定栈的抽象数据类型定义：?ADT?Stack?{?数据对象：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已存在。操作结果：将栈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（）。?}ADT?Stack?详细设计源代码：运行结果：图为n=4的情况总结与体会在学数据结构这门课的时候感觉并不是很难，或许是因为老师讲的很好，所以听的时候并不是很难。而且当时还做了几个小程序，约瑟夫环，哈夫曼树等等。当时是老师给了思路，然后让我们用C去实现。当时写的还蛮带劲的。可是这次课程设计我感觉十分无力了。看到车厢调度题目我就想了两个小时，竟然基本的解决方法都想不出来。虽然学过栈，但理解不深，只知道怎么去实现一个栈，而不理解为什么要这样去做，这样做会用什么好处。还有递归算法，只知道他很强大，也设计过几个递归程序，但也没有挖掘过。通过几天的努力，我的程序终于写完了。虽然算不上什么经典，但我个人还是蛮欣喜的，毕竟是自己设计的。当然有一个问题就是有些情况是不好实现的，例如当n=3时，序列312在不改变输入序列的前提下是无法输出的，这是栈的本质决定的。这次数据结构的程序设计让我明白了算法的重要性，同一个问题用不同的算法去实现效率是有巨大的差别的。