目录一、功能描述 (2)1、输入火车厢信息 (2)2、入轨 (2)3、出轨 (2)4、退出 (2)二、总体概要设计 (2)1、系统设计框图: (2)2、系统设计流程图 (3)三、详细设计 (3)1 功能一：输入火车厢信息 (3)1）概要设计： (3)2）算法描述： (3)3)算法分析 (4)2 功能二：入轨 (4)1）概要设计： (4)2）算法描述： (4)3)算法分析： (7)3 功能三：出轨 (8)1）概要设计 (8)2）算法描述： (8)3）算法分析: (11)4 功能四：退出 (11)四、效果及存在问题 (11)1、效果显示: (11)1）输入火车厢信息 (12)2）入轨 (12)3）出轨： (12)4）显示重排完成车厢排列 (13)2、存在问题 (13)五、心得及体会 (14)六、参考文献 (14)七、评分表（见尾页）.............................. 错误！未定义书签。
附录：源代码. (14)一、功能描述1、输入火车厢信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。
2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。
3、出轨给出每节火车厢出轨提示。
4、退出如果不需要操作就退出系统。
二、总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。
1、系统设计框图:2、系统设计流程图三、详细设计1 功能一：输入火车厢信息1）概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排列信息，并在屏幕上显示火车原始排列。
2）算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：int i,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;i<M;i++){scanf("%d",&A[i]);}printf("未转轨前的火车厢排列如下，请核对：\n");for(i=0;i<M;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[],int A,int m) /*入栈*/{STLink p;if(!(p=(STLink)malloc(LEN)))return 0;else{p->data=A;p->link=top[m];top[m]=p;return 1;}}int trainpush(int M,int A[],STLink top[]){int m,k=0,l;top[k]=NULL; /* 初始化第一个堆栈 */push(top,A[0],0); /*把第一节车厢压入缓冲铁轨*/printf("缓冲铁轨: 1 栈顶值:%d\n",top[0]->data);for(m=1;m<M;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",l+1,top[l]->data);l=k+1;}}}}return k+1;}3)算法分析：本函数实现的是提示每节车厢应进入的缓冲铁轨号及将每节车厢压入到缓冲铁轨中，首先将存放车厢号的数组及将要进行初始化的栈顶指针数组top[]作为实参传递给本自定义函数，首先初始化第一个堆栈，把第一节车厢压入栈中，输出缓冲铁轨号及第一节车厢号，后用for循环从第二个将要进栈的元素与前面的元素比较，前面所有栈顶值最大值一定为最后一个栈的栈顶值，如果此次需进栈的车厢号比前面所有栈顶值都大就重新初始化一个新的栈把车厢号压入新的栈的栈底并输出当前栈的栈号及本栈的栈顶值，否则就把需进栈的车厢号压入前面已经存在的缓冲铁轨中。
从第一个栈开始循环，找出第一个栈顶元素比需进栈元素要大的栈，将该车厢压入此栈中并修改栈顶值。
就这样利用循环控制所有的车厢都进入到缓冲铁轨中。
其中单个入栈函数push（）函数的实现过程如下：定义一个我们自定义的结构体类型的指针，利用此指针申请一个新节点，将车厢号送入该节点的数据域，并将原来的栈顶指针top移向该新申请的节点，始终使得top指针指向栈顶元素。
该算法最好的情况下（相对最好，因为此情况下需使用大量的堆栈）只需在当前最后一个堆栈进行操作，时间复杂度为O(1)，最差情况下（就是只有当前最后一个堆栈的栈顶值大于需进栈的车厢号）的时间复杂度为：O(M*k)。
3 功能三：出轨1）概要设计：利用for循环每次都找出最小的栈顶元素显示该最小元素所在的栈号并使得其出栈完成火车厢重排工作。
本自定义的函数实现过程中调用了判断堆栈为空函数及单个元素出栈函数，实现大量判断堆栈元素是否已经出栈为空并找到合适的栈顶元素后就将该车厢出栈的操作。
2）算法描述：流程图：代码：int empty( STLink top[],int n) /*判断是否为空*/ {return (top[n]==NULL);}int pop(STLink top[],int m) /*出栈*/{int A;STLink p;p=top[m];A=p->data;top[m]=top[m]->link;free(p);return A;}void trainpop(int M,int A[],STLink top[],int N){int m,n=0,min,l=0,amin=0; /*把所有车厢都压出缓冲铁轨*/ /* min=top[n]->data;for(m=0;m<M;m++){for(l=n+1;l<N;l++) /* 从第一个非空栈的第二栈起，将栈顶值与最小值比较 *//* {if((top[l]!=NULL)&&(top[l]->data<min)) /*取缓冲铁轨中栈顶元素最小的*//* {min=top[l]->data;amin=l; /*将栈顶值最小的栈的栈号保存起来*//* }}printf("本次出站车厢在%d缓冲铁轨,请按提示将火车厢压出缓冲铁轨",amin);A[m]=pop(top,amin); /*把最小的栈顶元素压出栈并赋值给A*//* printf("A[%d]=%d\n",m,A[m]);if(top[amin]==NULL) /* 取出最小值后，将遇到的第一个非空栈的栈顶值重新赋给min *//* {min=top[amin+1]->data;n=amin+1;}else{min=top[amin]->data;n=amin;}}}3）算法分析:本函数实现的是提示每节车厢应进入的缓冲铁轨后顺序把每节车厢压出转轨站实现火车厢重排，将接收车厢号的数组及栈顶指针数组top[]作为实参传递给本自定义函数，首先定义一个变量min，初始化min为第一节车厢的栈顶值，用for循环控制外循环，依次取出每一节车厢。
内循环也用for语句控制从第一个非空栈的第二栈起，将栈顶值与min比较，得到每一轮比较缓冲铁轨中最小的栈顶元素，并将栈顶值最小的栈的栈号保存起来，把最小的栈顶元素压出栈并赋值给存放出栈元素的数组，取出最小值后，将遇到的第一个非空栈的栈顶值重新赋给min，进入下一轮外循环，从而获得正确的火车厢排列，在此过程中用printf语句输出提示出栈元素在几号缓冲铁轨。
其中单个出栈函数pop（）函数的实现过程如下：定义一个我们自定义的结构体类型的指针p及变量A，将原来的栈顶指针top赋给p，用A保存本次出栈元素，将top指向下一个节点，再释放出栈元素所在的节点，始终使得top指针指向栈顶元素并可以返回出栈元素A。
该算法最好的情况下内循环每次都在第一个栈取元素即只有一个缓冲铁轨，时间复杂度为O(M)，最差情况下为O(M*k)。
4 功能四：退出四、效果及存在问题1、效果显示:1）输入火车厢信息：2）入轨：3）出轨：4）显示重排完成车厢排列2、存在问题直接把所有车厢都压入到缓冲铁轨中，存在浪费空间及时间的现象，理想状态下碰到1号车厢及后续的连续车厢应直接输出不用进入转轨站，在此没有实现此功能。
五、心得及体会与其临渊羡鱼，不如退而结网。
这次数据结构课程设计给我的最大的印象就是如果自己有了兴趣，就动手去做，平时你再认真学习对各种数据结构对它的认识往往仍然是比较模糊的，通过此次课程设计对自己负责的课题要处理的数据结构有了质的的飞跃，首先能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；其次也提高程序设计和调试能力，通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；并且培养算法分析能力。