车厢调度实习报告

数据结构课程设计车厢调度胡海洪1数据结构课程设计车厢调度胡海洪310400642904计算机科学与技术（1）班2006年7月

2．3题车厢调度实习报告题目：编制一个将长度为n的车厢进行调度后的所有序列输出的程序班级：04计算机科学与技术1班姓名：胡海洪学号：3104006429完成日期：06年7月一、需求分析1、用编号依次为1，2，3，……，n表示停在铁路调度站入口处的车厢序列。2、用一个栈形象地表示为火车的调度站。3、利用栈先进后出的性质，结合递归和回溯算法，实现编号1…n的车厢的所有可能的序列和每种序列的出入栈变化过程。本程序用C语言实现，已经在TURBOC2.0环境下通过。二、概要设计1、设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈CharSet，i=1，2，……，n，n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作结果：构造一个空栈S。Push(&S,e);初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,e);初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。}ADTStack本程序包括三个模块：初始化数据——输入总数——初始化栈和序列显示所有的序列——递归调用——输出所有结果演示一种序列——输入要演示的序列——每一步演示三、详细设计1、为了使车厢能够调度，需要定义一个栈，利用栈先进后出的性质，改变车厢的顺序；因为输出的序列有很多种，而且序列的产生是用递归产生的，所以定义一个二维数组，用它保存所有的输出序列，供演示时调用。structpathss{intpaths[MAXSIZE][MAXSIZE];intnumber;}AllPath;2、栈类型structSNode{intdata[MAXSIZE];inttop;}S;栈的基本操作：voidInitStack()/*栈的初始化*/{S.top=-1;}voidPush(intq)/*进栈*/{S.data[++S.top]=q;}intPop()/*出栈*/{inttemp;temp=S.data[S.top--];returntemp;}intStackEmpty()/*判断栈是否为空*/{if(S.top==-1)return1;elsereturn0;}3、求所有序列的伪码算法：voidAttemper(intpos,intpath[],intcur){if(pos<n){一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈}if(栈不空){一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈}if(pos==n&&栈空){一种可能输出序列产生，输出；并将每种序列保存在二维数组里；}}4、演示一种序列的伪码算法：演示时，采用的是向逆推的方法，因为我们已经知道了一种输出序列的结果和它的最初状态，就可以利用栈将中间过程显示出来；voidChooseDisplay(){intk,Output,Input=1;for(Output=0;Output<n;Output++){if(输出序列中当前的数据大于等于入口处的数据时){while(输出序列中当前的数据大于等于入口处的数据时){入口处的数据要一直压栈}显示每一步结果}else（序列中当前的数据小于入口处的数据）{弹出栈顶,重新显示结果}}}5、主函数和其他函数voidmain()/*主函数*/{功能选择分别调用：1:InputNumber()2:DisplayAll()3:ChooseDisplay()}voidDisplayAll()/*显示所有输出序列*/{调用函数Attemper}voidPrint()/*一个栈打印操作*/{inti;for(i=S.top;i>=0;i--)printf("\t\t\t|%d|\n",S.data[i]);}voidDisplayOnly(intk,intOutput,intInput)/*显示操作序列的状态的变化过程*/{第一步：显示输出序列的状态变化第二步：显示栈的状态变化第三步：显示输入序列的状态变化}6、函数的调用关系图反映了演示程序的层次结构：InputNumber()DisplayAll()Attemper()ChooseDisplay()InputNumber()ExitInitStack()InputNumber()DisplayAll()Attemper()ChooseDisplay()InputNumber()ExitInitStack()DisplayOnly()InitStack()四、调试分析本程序的栈其实也是一个一维数组,然后用一个top作为指针,控制数组的长度。栈的基本操作较简单明了。本程序有两个核心算法，即求所有序列和演示每一序列的变化过程。整个程序运行期间实行静态存储管理。本程序在TURBOC2.0同VC++环境下均可通过。五、用户手册本程序的运行环境为DOS操作系统，执行文件为：Attemper.exe。2、运行程序后,显示如下界面:六、测试结果（1）测试数据n=3；（也可以测试其他数据）（2）选择功能“1”,回车，显示如下：*******************1:输入火车的长度N**2:输出所有可能序列**3:演示一个序列变化**4:退出本程序*******************1请输入火车车厢的长度N:（3）输入车厢总数“3”,选择功能“2”，按回车显示如下：2所有可能的输出序列如下:1:3212:2313:2134:1325:123*******************1:输入火车的长度N**2:输出所有可能序列**3:演示一个序列变化**4:退出本程序*******************（4）选择功能“3”,回车显示如下:3请输入你想要查看序列状态变化过程的序号:7．输入要演示的序列号,如输入“3”,再一直按回车，显示如下:3请输入你想要查看序列状态变化过程的序号:3输出序列栈输入序列<----1<----2<----3|1|<----2<----3|2||1|<----3<----2|1|<----3<----2<----1<----3<----2<----1|3|<----2<----1<----3（5）输入”4”,回车则退出程序七、附录源程序文件名清单：Attemper.c//主程序Attemper.exe//可执行文件Attemper.OBJ//目标源文件八、心得体会1、通过这次作业，我感到学到不少知识，首先对C语言有了一个比较完整的认识，以前学习C语言的知识很零碎、不系统，通过写源程序使我对C语言的数据类型（特别构造类型的数据）有了一个完整的认识，为今后进一步学习C++奠定了良好的基础。2、加深了对《数据结构》这门课程的学习和领会。以往只是知道这门课程对计算机专业很重要，但具体起来又不明白到底怎样重要？通过设计，我才体会到没有《数据结构》的知识是无法写程序的！由于本人掌握知识深度欠缺，只好采用一个二维数组和一个一维数组，这样明显增加了时间复杂性。3、实践是检验真理的唯一手段！《数据结构》中的许多