车厢调度问题课程设计

-1-目录目录...................................................................................................................-1-正文........................................................................................................................2一、题目分析....................................................................................................2二、概要设计....................................................................................................2三、详细设计....................................................................................................4四、运行结果....................................................................................................9五、课程设计体会..........................................................................................10六、参考文献..................................................................................................10正文一、题目分析课程设计题目车厢调度：假设停在铁路调度站的车厢序列的编号依次为1，2.，3，…..n。设计一个程序，求出所有可能输出的长度为n的车厢序列。基本要求首先在教科书3.1.2节中提供的栈的顺序结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作进行。二、概要设计1．设定栈的抽象数据类型定义：ADTStack{数据对象：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清为空栈。StackLength(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（）。}ADTStack2.本程序包含两个模块1）主程序模块：Voidmain(){初始化;For循环}2）栈模块——实现栈的抽象数据类型各模块之间的调用关系如下：主程序模块栈模块三、详细设计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)2)代码#includeiostreamusingnamespacestd;typedefintSElemType;typedefintStatus;intend;/*最后一个车厢的号码*/longtotal=0;/*总的组合方案数目*/typedefstructstacklist{SElemType*base;SElemType*top;intstacksize;}SqStack;voidStack_init(SqStack*s){s-base=(SElemType*)malloc(end*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=end;}voidStack_Push(SqStack*s,SElemTypee){*(s-top)++=e;}SElemTypeStack_Pop(SqStack*s){if(s-top==s-base)return0;return*(--(s-top));}StatusStack_Empty(SqStack*s){if(s-top==s-base)return1;return0;}StatusStack_Full(SqStack*s){if(s-top-s-base==end)return1;return0;}voidStack_printreverse(SqStacks){int*po;po=s.base;printf(\t[%ld]:,total);for(;po!=s.top;)printf(%d,*po++);printf(\n);}voidsearch(SqStack*inputPoint,SqStack*tempPoint,SqStack*outputPoint){if(!Stack_Empty(inputPoint)){Stack_Push(tempPoint,Stack_Pop(inputPoint));search(inputPoint,tempPoint,outputPoint);Stack_Push(inputPoint,Stack_Pop(tempPoint));}if(!Stack_Empty(tempPoint)){Stack_Push(outputPoint,Stack_Pop(tempPoint));search(inputPoint,tempPoint,outputPoint);Stack_Push(tempPoint,Stack_Pop(outputPoint));}if(Stack_Full(outputPoint)){total++;Stack_printreverse(*outputPoint);}}主函数：voidmain(){SqStackinput,temp,output;inti;printf(\n\n\t\t\t\t车厢调度\n);printf(\n\t请输入车厢长度:);scanf(%d,&end);/*初始化三个栈*/Stack_init(&input);Stack_init(&temp);Stack_init(&output);/*将车厢号码进栈*/for(i=end;i=1;i--)Stack_Push(&input,i);search(&input,&temp,&output);}3）主函数流程图1.栈的数据定义，输出操作信息民，并输入数据2.初始化三个栈input,temp,output3.for循环控制输出语句，车厢号依次进栈判断循环结束条件4.调用函数Stack_Push(&input,i);search(&input,&temp,&output);输出所有情况提示输入输出初始化表达式2表达式3函数调用结束表达式1开始四、运行结果输入3，结果如下：输入4，结果如下：五、课程设计体会通过对本学期的数据结构和课程的学习，我完成了本次的课程设计报告，其中得到了很多的体会，也了解到很多的知识点。我明白了课程设计是大学教育中一个重要的实践教学环节。在课程设计过程中,我根据具体设计题目，运用自己所学的知识，独立地进行设计和实验。除了巩固、加深和融合自己所学的数据结构专业课程知识外，更重要的是培养了我多方面的能力，如独立思考能力、综合设计能力、实践动手能力、开拓创新能力、自学能力、文献检索能力等等。通过这次的课程设计，我也了解到自己所学的一些不足之处，以及一些还不了解的知识点，以后会加强学习。六、参考文献1、车厢调度：参见《数据结构题集》P98。2、栈和数据结构：参见《计算机软件技术基础教程》P114、P86。3、程序编程：参见《C程序设计》。4、严蔚敏、吴伟民主编《数据结构》（C语言版）5、殷人昆等著《数据结构》（C++版）6、金远平著《数据结构》（C++描述）7、许卓群等著《数据结构与算法》