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

课 程 设 计 报 告课程名称 数据结构课程设计 选题名称 车厢调度 班级 A1401 姓名 王蓉 学号 02 实验组别 同组实验者 完成时间2016 年 1 月 4 日至2016 年 1 月15 日指导教师 卫丽华 目 录1、数据结构课程设计任务书31.1、题目31.2、要求32、总体设计32.1、功能模块设计32.2、所有功能模块的流程图33、详细设计33.1、程序中所采用的数据结构及存储结构的说明43.2、算法的设计思想44、调试与测试45、源程序清单66、C程序设计总结77、致谢78、参考文献71、数据结构课程设计任务书1.1、题目车厢调度 1.2、要求假设在铁路调度站（如教科书图3.1（b）所示）入口处的车厢序列的编号依次为1,2,3,.,n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。 首先在教科书上提供的栈的顺序存储结构Seqstack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取(即更改,读取和状态判别等操作)必须借助于基本操作进行。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：主程序模块 递归模块栈模块调度模块开始2.2、所有功能模块的流程图定义一个空栈判断栈空或栈满调用函数 循环输出车厢总个数输出所有车厢序列结束3、详细设计3.1、程序中所采用的数据结构及存储结构的说明1）栈类型；typedef struct stacklistSElemType *base;SElemType *top;int stacksize;SqStack;栈的基本操作设置如下：void Stack_init(SqStack *s)/初始化，设s为空栈void Stack_Push(SqStack *s,SElemType e)/若分配空间成功，则在s的栈顶插入新的元素e，并返回TRUE/若栈不变，并返回FALSESElemType Stack_Pop(SqStack *s)Status Stack_Empty(SqStack *s)Status Stack_Full(SqStack *s)void Stack_printreverse(SqStack s)void search(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（）。核心算法void search(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);主函数描述void main()SqStack input,temp,output;int i;printf(nntttt车厢调度n);printf(nt请输入车厢长度: );scanf(%d,&final);printf(nt车厢序列为：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、源程序清单#include #include typedef int SElemType;typedef int Status;int final;/最后一个车厢的号码(车厢长度)int total=0;/车厢序列的总个数typedef struct SElemType *base;/栈底指针SElemType *top;/栈顶指针int stacksize;/ 栈大小 SqStack;/顺序栈Status Initstack(SqStack *s) /构造一个空栈s-base=(SElemType *)malloc(final*sizeof(int);if(!s-base) exit(0); s-top=s-base;s-stacksize=final; /若栈为空，存储分配失败Status Push(SqStack *s,SElemType e)/插入元素e为新的栈顶元素*(s-top)+=e;SElemType Pop(SqStack *s)/若栈不为空，则删除s的栈顶元素if(s-top=s-base)return 0;elsereturn *(-(s-top);Status Emptystack(SqStack *s)/判断是否栈空if(s-top=s-base)return 1;elsereturn 0;Status Fullstack(SqStack *s)/判断是否栈满if(s-top-s-base=final)return 1;elsereturn 0;Status PrintStack(SqStack s)/输出车厢序列的总个数int *p;p=s.base;printf(t%ld: ,total);for(;p!=s.top;) printf(%d ,*p+);printf(n);void search(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);/主函数void main()SqStack input,temp,output;int i;printf(nntttt车厢调度n);printf(nt请输入车厢长度: );scanf(%d,&final);printf(nt车厢序列为：n);/将栈初始化Initstack(&input);Initstack(&temp);Initstack(&output);/将车厢号码进栈for(i=final;i=1;i-)Push(&input,i);search(&input,&temp,&output);/输出所有可能出现的情况6、C程序设计总结该程序设计的初期我只知道顺序栈的实现，通过图书馆以及网络资源的共享，