车厢调度问题课程设计报告

课程设计报告课程名称数据结构课程设计选题名称车厢调度班级A1401姓名王蓉学号02实验组别同组实验者完成时间2016年1月4日至2016年1月15日指导教师卫丽华目录1、数据结构课程设计任务书............................................31.1、题目..........................................................31.2、要求..........................................................32、总体设计..........................................................32.1、功能模块设计..................................................32.2、所有功能模块的流程图..........................................33、详细设计..........................................................43.1、程序中所采用的数据结构及存储结构的说明........错误!未定义书签。3.2、算法的设计思想................................错误!未定义书签。4、调试与测试........................................................75、源程序清单........................................................96、C程序设计总结...................................................137、致谢.............................................................138、参考文献.........................................................131、数据结构课程设计任务书1.1、题目车厢调度1.2、要求假设在铁路调度站（如教科书图3.1（b）所示）入口处的车厢序列的编号依次为1,2,3,...,n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。首先在教科书上提供的栈的顺序存储结构Seqstack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取(即更改,读取和状态判别等操作)必须借助于基本操作进行。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：2.2、所有功能模块的流程图开始主程序模块栈模块递归模块调度模块循环3、详细设计3.1、程序中所采用的数据结构及存储结构的说明1）栈类型；typedefstructstacklist{SElemType*base;SElemType*top;intstacksize;}SqStack;栈的基本操作设置如下：voidStack_init(SqStack*s)//初始化，设s为空栈voidStack_Push(SqStack*s,SElemTypee)//若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE//若栈不变，并返回FALSESElemTypeStack_Pop(SqStack*s)StatusStack_Empty(SqStack*s)定义一个空栈判断栈空或栈满输出车厢总个数调用函数输出所有车厢序列结束StatusStack_Full(SqStack*s)voidStack_printreverse(SqStacks)voidsearch(SqStack*inputPoint,SqStack*tempPoint,SqStack*outputPoint)3.2、算法的设计思想1.定义栈2.初始化三个栈input,temp,output3.for循环控制输出语句，车厢号依次进栈4.调用函数Stack_Push(&input,i);search(&input,&temp,&output);输出所有情况基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回1，否则返回0。GetTop(S,&e)初始条件：栈S已存在。操作结果：若S不空，则e返回栈顶元素。Push（&S，&e）初始条件：栈S已存在。操作结果：在s的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。核心算法voidsearch(SqStack*input,SqStack*temp,SqStack*output){if(!Emptystack(input))//一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈{Push(temp,Pop(input));search(input,temp,output);Push(input,Pop(temp));}if(!Emptystack(temp))//一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈{Push(output,Pop(temp));search(input,temp,output);Push(temp,Pop(output));}if(Fullstack(output))//栈满时输出序列产生，输出{total++;PrintStack(*output);}}主函数描述voidmain(){SqStackinput,temp,output;inti;printf(\n\n\t\t\t\t车厢调度\n);printf(\n\t请输入车厢长度:);scanf(%d,&final);printf(\n\t车厢序列为：\n);//将栈初始化Initstack(&input);Initstack(&temp);Initstack(&output);//将车厢号码进栈for(i=final;i=1;i--)Push(&input,i);search(&input,&temp,&output);//输出所有可能出现的情况}4、调试与测试4.1、调试方法与步骤运行该程序输入车厢长度3，显示结果输入车厢长度5，显示结果程序运行成功4.2、测试结果的分析与讨论（测试要写出测试用例及每个用例结果的的截图）运行该程序当车厢长度为3时当车厢长度为5时4.3、测试过程中遇到的主要问题及采取的解决措施车厢长度过长的话程序运行需要等待较长的时间，但程序本身是没有错的，因此就通过取小一点的车厢长度来测试，例如n=10。5、源程序清单#includestdio.h#includestdlib.htypedefintSElemType;typedefintStatus;intfinal;//最后一个车厢的号码(车厢长度)inttotal=0;//车厢序列的总个数typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈大小}SqStack;//顺序栈StatusInitstack(SqStack*s){//构造一个空栈s-base=(SElemType*)malloc(final*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=final;//若栈为空，存储分配失败}StatusPush(SqStack*s,SElemTypee)//插入元素e为新的栈顶元素{*(s-top)++=e;}SElemTypePop(SqStack*s)//若栈不为空，则删除s的栈顶元素{if(s-top==s-base)return0;elsereturn*(--(s-top));}StatusEmptystack(SqStack*s)//判断是否栈空{if(s-top==s-base)return1;elsereturn0;}StatusFullstack(SqStack*s)//判断是否栈满{if(s-top-s-base==final)return1;elsereturn0;}StatusPrintStack(SqStacks)//输出车厢序列的总个数{int*p;p=s.base;printf(\t[%ld]:,total);for(;p!=s.top;)printf(%d,*p++);printf(\n);}voidsearch(SqStack*input,SqStack*temp,SqStack*output){if(!Emptystack(input))//一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈{Push(temp,Pop(input));search(input,temp,output);Push(input,Pop(temp));}if(!Emptystack(temp))//一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进栈{Push(output,Pop(temp));search(input,temp,output);Push(temp,Pop(output));}if(Fullstack(output))//栈满时输出序列产生，输出{total++;PrintStack(*output);}}//主函数voidmain(){SqStackinput,temp,output;inti;printf(\n\n\t\t\t\t车厢调度\n);printf(\n\t请输入车厢长度:);scanf(%d,&final);printf(\n\t车厢序列为：\n);//将栈初始化Initstack(&input);Initstack(&temp);Initstack(&output);//将车厢号码进栈for(i=final;i=1;i--)Push(&input,i);search(&input,&temp,&output);//输出所有可能出现的情况}6、C程序设计总结该程序设计的初期我只知道顺序栈的实现，通过图书馆以及网络资源的共享，我知道了递归的使用，更加利于有车厢调度的实现。虽然能够有效运行车厢的所有序列，但只针对车厢长度较小的车厢长度，一旦车厢长度过大，程序的运行任然需要一定的时间，此方面还要深入研究。7、致谢能够完成这次课程设计必须感谢数据结构课程老师卫丽华，在她的帮助下我抓住了该课程设计的核心，能够理解并实现了代码的成功运行。8、参考文献[1]严蔚敏。《数据结构习题》，清华大学出版社[2]管致锦。《数据结构》，清华大学出版社