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

1武汉轻工大学数学与计算机学院《数据结构》课程设计说明书题目：车厢调度专业：数学与计算机学院班级：大类1304学号：姓名：指导老师：林菁2014年12月24日2一．题目分析课程设计题目：【问题描述】铁路调度站入口处的车厢序列编号依次为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时，可能的命令队列在00001111和01010101之间。找到了可能的命令队列，再找合法的命令队列。把所以可能的命令队列进行如下的条件判断，都满足的即是合法的命令队列。判断条件：1.第一个是0，末尾一个是1.2.0和1各一半3.每出现一个1，前面必须有一个0与之对应（类似括号匹配）3二．概要设计1．设定栈的抽象数据类型定义：ADTStack{数据对象：D={iiaa|∈CharSet,i=1,2,...,n,,n≥0}数据关系：∈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（）。}ADTStack三．详细设计源代码：4//stack.h#defineOVERFLOW-1#defineTRUE1#defineFLASE0#includeiostream#includeconio.husingnamespacestd;classstack{public:int*base;int*top;intnSize;intstackSize;public:stack(intn){base=newint[n+1];top=base;stackSize=n+1;nSize=0;}~stack(){delete[]base;}intpop(){//空栈出栈报错if(base==top){coutErrorPop!;getch();exit(OVERFLOW);}nSize--;intn=*(--top);*(top+1)=-1;returnn;}voidpush(inta){//栈满进栈报错if((top-base)==stackSize*sizeof(int)){coutErropush!;getch();exit(OVERFLOW);}5nSize++;*(top++)=a;}intgetTop(){if(base==top){coutErrorgettop!;getch();exit(OVERFLOW);}return*(top-1);}intstackEmpty(){if(top==base)returnTRUE;elsereturnFLASE;}voidclearStack(){top=base;}};//source.cpp#includestack.h//计数全局变量inttotal;//根据命令队列进行入栈与出栈voidoutput(intn,inta[]){stacks(n);total++;cout\t;cout[total];if(total10)cout:;elsecout:;inttemp=1;for(inti=0;i2*n;i++){if(a[i]==0){s.push(temp);temp++;}else{couts.pop();6cout'';}}coutendl;}//判断生成的命令队列是否符合要求booljugdeOk(intn,inta[]){intnumOfZero=0;for(inti=0;i2*n;i++){if(a[i]==0)numOfZero+=1;elsenumOfZero-=1;if(numOfZero0)returnFLASE;}if(numOfZero!=0)returnFLASE;elsereturnTRUE;}//判断命令队列是否到达上限booljugdeEnd(intn,inta[]){for(inti=0;in;i++){if(a[2*i]!=0)returnFLASE;}returnTRUE;}voidcreatOrder(intn,inta[]){intmark=0;//实现命令队列，将命令队列相对应的组合进行输出output(n,a);//通过加法来实现命令队列的生成do{inti=3;a[2*n-2]+=1;if(a[2*n-2]==2){a[2*n-2]=0;mark=1;}while(mark){a[2*n-i]+=1;7运行结果：图为n=4的情况if(a[2*n-i]==2)a[2*n-i]=0;elsemark=0;i++;}}while(!jugdeOk(n,a));if(jugdeEnd(n,a)){output(n,a);return;}creatOrder(n,a);}voidmain(){intn,i;cout车厢调度:endl;cout输入车厢数:;cinn;coutendl;int*a=newint[2*n];for(i=0;in;i++)a[i]=0;for(i=n;i2*n;i++)a[i]=1;creatOrder(n,a);delete[]a;}8四．总结与体会在学数据结构这门课的时候感觉并不是很难，或许是因为老师讲的很好，所以听的时候并不是很难。而且当时还做了几个小程序，约瑟夫环，哈夫曼树等等。当时是老师给了思路，然后让我们用C去实现。当时写的还蛮带劲的。可是这次课程设计我感觉十分无力了。看到车厢调度题目我就想了两个小时，竟然基本的解决方法都想不出来。虽然学过栈，但理解不深，只知道怎么去实现一个栈，而不理解为什么要这样去做，这样做会用什么好处。还有递归算法，只知道他很强大，也设计过几个递归程序，但也没有挖掘过。通过几天的努力，我的程序终于写完了。虽然算不上什么经典，但我个人还是蛮欣喜的，毕竟是自己设计的。当然有一个问题就是有些情况是不好实现的，例如当n=3时，序列312在不改变输入序列的前提下是无法输出的，这是栈的本质决定的。这次数据结构的程序设计让我明白了算法的重要性，同一个问题用不同的算法去实现效率是有巨大的差别的。