车厢调度问题课程设计报告(共13页).doc

《车厢调度问题课程设计报告(共13页).doc》由会员分享，可在线阅读，更多相关《车厢调度问题课程设计报告(共13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 课 程 设 计 报 告课程名称 数据结构课程设计 选题名称 车厢调度 班级 A1401 姓名 王蓉 学号 02 实验组别 同组实验者 完成时间2016 年 1 月 4 日至2016 年 1 月15 日指导教师 卫丽华 目 录专心-专注-专业1、数据结构课程设计任务书1.1、题目车厢调度 1.2、要求假设在铁路调度站（如教科书图3.1（b）所示）入口处的车厢序列的编号依次为1,2,3,.,n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。 首先在教科书上提供的栈的顺序存储结构Seqstack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取(即更改,读取

2、和状态判别等操作)必须借助于基本操作进行。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

3、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.初始化三个栈in

4、put,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

5、)初始条件：栈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)/ 一个数进栈后,有两种处理方式：要么立刻出栈,要么进行下一个数的进栈

6、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

7、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、测试结果的分析与讨论（测试要写出测试用例及每个

8、用例结果的的截图）运行该程序当车厢长度为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;/ 栈大小

9、 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 *(-(

10、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 *i

11、nput,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(out

12、put)/ 栈满时输出序列产生，输出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程序设计总结该程序设计的初期我只知道顺序栈的实现，通过图书馆以及网络资源的共享，我知道了递归的使用，更加利于有车厢调度的实现。虽然能够有效运行车厢的所有序列，但只针对车厢长度较小的车厢长度，一旦车厢长度过大，程序的运行任然需要一定的时间，此方面还要深入研究。7、致谢能够完成这次课程设计必须感谢数据结构课程老师卫丽华，在她的帮助下我抓住了该课程设计的核心，能够理解并实现了代码的成功运行。8、参考文献1 严蔚敏。数据结构习题，清华大学出版社2 管致锦。数据结构，清华大学出版社