数据结构之火车厢重排.docxVIP

目录一、功能描述31、输入火车厢信息32、入轨33、出轨34、退出3二、 总体概要设计31、系统设计框图:32、系统设计流程图4三、详细设计41 功能一：输入火车厢信息41）概要设计：42）算法描述：43)算法分析52 功能二：入轨51）概要设计：52）算法描述：53)算法分析：83 功能三：出轨81）概要设计82）算法描述：93）算法分析:114 功能四：退出11四、效果及存在问题111、效果显示:111）输入火车厢信息112）入轨123）出轨：124）显示重排完成车厢排列132、存在问题13五、心得及体会14六、参考文献14七、 评分表（见尾页）14附录：源代码15一、功能描述1、输入火车厢信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。3、出轨给出每节火车厢出轨提示。4、退出如果不需要操作就退出系统。总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁 轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。1、系统设计框图:2、系统设计流程图三、详细设计1 功能一：输入火车厢信息1）概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排列信息，并在屏幕上显示火车原始排列。2）算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：inti,M,A[100],N=0;printf(\n\n);printf(************************************************************\n\n);printf(===============您好,欢迎光临火车转轨系统！===============\n\n);printf(请输入您要进行转轨的火车车厢总长：);scanf(%d,M);printf(\n请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢号\n\n); for(i=0;iM;i++) { scanf(%d,A[i]); }printf(未转轨前的火车厢排列如下，请核对：\n);for(i=0;iM;i++) printf(A[%d]=%d\n,i,A[i]);3)算法分析：此功能模块简单明了没有深度算法，在此不做分析。2 功能二：入轨1）概要设计：通过比较栈顶元素的大小的方法使得每个缓冲铁轨中车厢的排序是依次递减排列。本自定义的函数实现过程中调用了将初始化一个堆栈函数及单个元素进栈函数，实现需要的时候重新初始化一个堆栈并找到合适的堆栈存放车厢号后就将车厢进栈的操作。2）算法描述：流程图: : 代码: void init(STLink top[],int m) /*初始化堆栈*/ {top[m]=NULL; }int push(STLink top[],intA,int m) /*入栈*/{STLink p;if(!(p=(STLink)malloc(LEN)))return 0;else{p-data=A;p-link=top[m];top[m]=p;return 1;}} inttrainpush(intM,int A[],STLink top[]) {intm,k=0,l; top[k]=NULL; /* 初始化第一个堆栈 */ push(top,A[0],0); /*把第一节车厢压入缓冲铁轨*/printf(缓冲铁轨: 1 栈顶值:%d\n,top[0]-data); for(m=1;mM;m++) /*把车厢都压入缓冲铁轨*/ {if(A[m]top[k]-data) /*前面所有栈顶值最大值一定为最后一个栈的栈顶值，如果此次需进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并把车厢号压入新的栈的栈底*/{ init(top,++k);push(top,A[m],k);printf(缓冲铁轨：%d 栈顶值：%d\n,k+1,top[k]-data);}else /* 将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈的车厢号要大的栈中，比如要插入10号车厢，缓冲铁轨的栈顶值排列如下：2、11、5、12，13，将10插在11所在的栈的栈顶*/ { l=0;while(l=k) {if(A[m]top[l]-data)l++;else{push(top,A[m],l);printf(缓冲铁轨: %d 栈顶值:%d\n,