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

1、和通理工辜洗课程设计报告课程名称数据结构课程设计选题名称车厢调度班级 A1401姓名王蓉学号02实验组别同组实验者完成时间2016年1月4日至2016年1月15 日指导教师卫丽华目录1、数据结构课程设计任务书 31.1 、题目 31.2 、要求 32、总体设计 32.1 、功能模块设计 32.2 、所有功能模块的流程图 33、详细设计 43.1 、程序中所采用的数据结构及存储结构的说明 错误！未定义书签。3.2 、算法的设计思想 错误！未定义书签。4、调试与测试 75、源程序清单 96、C 程序设计总结 137、致谢 138、参考文献 131、数据结构课程设计任务书1.1、题目车厢调度1.2、

2、要求假设在铁路调度站（如教科书图 3.1 （b）所示）入口处的车厢序列的编号依次为 1,2,3,.,n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。首先在教科书上提供的栈的顺序存储结构Seqstack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取（即更改,读取和状态判别等操作）必须借助于基本 操作进行。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下:主程序模块栈模块递归模块调度模块2.2、所有功能模块的流程图结束3、详细设计3.1、程序中所采用的数据结构及存储结构的说明1)栈类型；typedef struct stacklistSEl

3、emType *base;SElemType *top;int stacksize;SqStack;栈的基本操作设置如下：void Stack_init(SqStack *s) 初始化，设 s 为空栈void Stack_Push(SqStack *s,SEIemType e)若分配空间成功，则在 s的栈顶插入新的元素e,并返回TRUE/若栈不变，并返回FALSESElemType Stack_Pop(SqStack *s)Status Stack_Empty(SqStack *s)Status Stack_Full(SqStack *s)void Stack_printreverse(SqS

4、tack 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

5、) 初始条件：栈 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已

6、存在。操作结果：从栈底到栈顶依次对 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,

7、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);Initsta

8、ck(&output);/ 将车厢号码进栈for(i=final;i=1;i-)Push(&input,i);search(&input,&temp,&output); / 输出所有可能出现的情况 4、调试与测试4.1 、调试方法与步骤运行该程序输入车厢长度 3，显示结果输入车厢长度 5，显示结果程序运行成功4.2、测试结果的分析与讨论（测试要写出测试用例及每个用例结果的的截图）运行该程序当车厢长度为3时当车厢长度为5时c Fraru Pi IbxVKk cra-xuft 7i xuhI St uiianxm车卿序列Sb 11L E 4 3 1 i Zl= -1 E 3 2 1 311 4 3

9、 S 2 1 41： -13 3(1 SI I 3215 Bl= 1 E 2* 1 71 r 1421 Bl： 3 4 3 & 1 ? Ir 14 2 15ial：326弓1ill;345L12 ：J24L石i;3215ill：01之il;z431U岸-15)117 =2A351S*la4if：E?51rsfiE2JL414.3、测试过程中遇到的主要问题及采取的解决措施车厢长度过长的话程序运行需要等待较长的时间，但程序本身是没有错的，因此就通过取小一点的车厢长度来测试，例如n=10。5、源程序清单#in elude #i nclude typedef int SEIemType;typedef

10、 int Status;int fin al;/最后一个车厢的号码（车厢长度）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; / 若栈为空，存储分配失

11、败 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-base) return 1;elsereturn 0;Status Fullstack(SqStack *s)/ 判断是否栈满if(s-top-s-base=final) r

12、eturn 1;else return 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,

13、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程序设计总结该程序设计的初期我只知道顺序栈的实现，通