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

1、车厢调度问题课程设计报告南逋理工爭院I课程设计报告课程名称数据结构课程设计选题名称车厢调度班级A1401 姓名 王蓉学号02实验组别同组实验者完成时间2016年1月4日至2016年1月15日1、数据结构课程设计任务书错误! 未定义书签。、题目.错误! 未定义书签。、要求.错误! 未定义书签。2、总体设计错误! 未定义书签。、功能模块设计 .错误! 未定义书签。、所有功能模块的流程图错误! 未定义书签。3、详细设计错误! 未定义书签。、程序中所采用的数据结构及存储结构的说明错误! 未定义书签。、算法的设计思想错误! 未定义书签。4、调试与测试错误! 未定义书签。5、源程序清单错误! 未定义书签。

2、6、C 程序设计总结错误! 未定义书签。7、致谢错误! 未定义书签。8、参考文献错误! 未定义书签。1、数据结构课程设计任务书、题目 车厢调度、要求 假设在铁路调度站（如教科书图（b）所示）入口处的车厢序列的编号依次为1,2,3,n 。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。首先在教科书上提供的栈的顺序存储结构 Seqstack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取 （即更改,读取和状态判别等操作）必须借助于基本操作进行。2、总体设计、功能模块设计 根据课程设计题目的功能要求，各个功能模块的组成框图如下:、所有功能模块的流程图n3、详细设计、程序中所采用的数据结

3、构及存储结构的说明1）栈类型;typ edef struct stacklistSEIemT ype *base;SEIemT ype *top;int stacksize;SqStack;栈的基本操作设置如下:void Stack_init(SqStack *s) 义栈2. 初始化三个栈 input,temp,output循环控制输出语句，车厢号依次进栈4.调用函数 Stack_Push(&input,i);search(&input,&temp,&output); 输出所有情况基本操作：InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S

4、已存在。操作结果：销毁栈 S。ClearStack(&S)初始条件：栈S已存在。操作结果：将栈S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈 S 的长度。StackEmpty(S)GetTop(S,&e)Push( &S， &e)Pop(&S,&e)操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse ( S，visit () 初始条件：栈 S 已存在。操作结果：从栈底到栈顶依次对 S 中的每个元素调用函数 visit ()。核心算法void search(SqStack *input,SqStack *temp,SqStack *output

5、) 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) / 栈满时输出序列产生，输出tot

6、al+;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); / 输出所有可能出现的情况

7、4、调试与测试、调试方法与步骤 运行该程序 输入车厢长度 3，显示结果输入车厢长度 5，显示结果程序运行成功、测试结果的分析与讨论测试要写出测试用例及每个用例结果的的截图） 运行该程序当车厢长度为3时当车厢长度为5时RU|F :利舒就t TiLrabT ir 皿跆 匚册巧1尋 惟.：. iT罕s萍却丸.M 1= i- -4 J T riHfP： 4 ) F I m； ar i ? * 1(1= 1431 i ? r I Mai：ill laN?i= lifIM = |J=I料和117 = 3 Mf J =詔*iiI-IVIEI2Z hlIVeft-t、测试过程中遇到的主要问题及采取的解决措施

8、车厢长度过长的话程序运行需要等待较长的时间，但程序本身是没有错的，因此就通过取小一点的车厢长度来测试，例如 n=ia5、源程序清单#in elude #in elude typ edef int SEIemT ype;typ edef int Status;int total=0; / 车厢序列的总个数typedef structSElemType *base; / 栈底指针SElemType *top; / 栈顶指针int stacksize; / 栈大小/ 构造一个空栈SqStack; / 顺序栈Status Initstack(SqStack *s) s-base=(SElemType

9、*)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;else return *(-(s-top);Status Emptystack(SqStack *s) / 判断是否栈空if(s-top=s-b

10、ase) return 1;else/ 判断是否栈满return 0;Status Fullstack(SqStack *s) if(s-top-s-base=final) return 1;elsereturn 0;int *p;p=;printf(t%ld: ,total);for(;p!=;) printf(%d ,*p+);printf(n);void search(SqStack *input,SqStack *temp,SqStack *output) if(!Emptystack(input) / 一个数进栈后 , 有两种处理方式：要么立 刻出栈, 要么进行下一个数的进栈Push

11、(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;i

12、nt i;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 管致锦。数据结构，清华大学出版社