《车厢调度问题课程设计报告》由会员分享,可在线阅读,更多相关《车厢调度问题课程设计报告(19页珍藏版)》请在金锄头文库上搜索。
1、南通理工李傀课程设计报告课程名称数据结构课程设计选题名称车厢调度班级 A1401 姓名 王蓉 学号 02实验组别 同组实验者完成时间2016年1月4日至2016年1月15 日指导教师卫丽华1、数据结构课程设计任务书 错误!未定义书签。、题目 错误!未定义书签。、要求 错误!未定义书签。2、总体设计 错误!未定义书签。、功能模块设计 错误!未定义书签。、所有功能模块的流程图 错误!未定义书签。3、详细设计 错误!未定义书签。、程序中所采用的数据结构及存储结构的说明 . 错误 ! 未定义书签。、算法的设计思想 错误!未定义书签。4、调试与测试 错误!未定义书签。5、源程序清单 错误!未定义书签。6
2、、C程序设计总结 错误!未定义书签7、致谢 错误!未定义书签。8、参考文献 错误!未定义书签。1、数据结构课程设计任务书、题目车厢调度、要求假设在铁路调度站(如教科书图(b)所示)入口处的车厢序列的编号 依次为1,2,3,,n 。设计一个程序,求出所有可能由此输出的长度为 n的车厢序列。首先在教科书上提供的栈的顺序存储结构 Seqstack之上实现栈的基本 操作,即实现栈类型。程序对栈的任何存取 (即更改,读取和状态判别 等操作)必须借助于基本操作进行。2、总体设计、功能模块设计 根据课程设计题目的功能要求,各个功能模块的组成框图如下:3、详细设计、程序中所采用的数据结构及存储结构的说明1)栈
3、类型;typedef struct stacklistSElemType *base;SElemType *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 已存在。操作结果:销毁栈S。Clea
4、rStack(&S)初始条件:栈S 已存在。StackLength(S)初始条件:栈S 已存在。操作结果:返回栈S 的长度。StackEmpty(S)初始条件:栈S 已存在。操作结果:若S为空栈,则返回1,否则返回0GetTop(S,&e)初始条件:栈S 已存在。操作结果:若S不空,则e返回栈顶元素。Push( &S, &e)初始条件:栈S已存在。操作结果:在s 的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件:栈S已存在。StackTraverse ( S, visit () )初始条件:栈S 已存在。操作结果:从栈底到栈顶依次对S 中的每个元素调用函数visit () 。核心算法vo
5、id 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(tem
6、p,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(&in
7、put,i);search(&input,&temp,&output); / 输出所有可能出现的情况4、调试与测试、调试方法与步骤运行该程序输入车厢长度3,显示结果输入车厢长度5,显示结果程序运行成功、测试结果的分析与讨论(测试要写出测试用例及每个用例结果的的截图) 运行该程序当车厢长度为3时当车厢长度为5时3 1 ib 42 1 1 4 *5LjJ、测试过程中遇到的主要问题及采取的解决措施车厢长度过长的话程序运行需要等待较长的时间,但程序本身是没有错的,因此就通过取小一点的车厢长度来测试,例如 n=105、源程序清单#include #include typedef int SElemTyp
8、e;typedef int Status;int final; 最后一个车厢的号码(车厢长度)int total=0; / 车厢序列的总个数typedef structSElemType *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; / 若
9、栈为空,存储分配失败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)re
10、turn 1;elsereturn 0;Status PrintStack(SqStack s) / 输出车厢序列的总个数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(temp,Pop(input);search(input,temp,output);Push(i
11、nput,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(
12、%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 管致锦。 数据结构 ,清华大学出版社