数据结构之火车厢重排

1、目录、功能描述21、输入火车厢信息22、入轨23、出轨24、退出2二、总体概要设计21、系统设计框图：22、系统设计流程图3三、详细设计31功能一：输入火车厢信息31）概要设计：32）算法描述：33）算法分析42功能二：入轨41）概要设计：42）算法描述：43）算法分析：73功能三：出轨81）概要设计82）算法描述：83）算法分析：114功能四：退出11四、效果及存在问题111、效果显示：111）输入火车厢信息122）入轨123）出轨：124）显示重排完成车厢排列132、存在问题13五、心得及体会14六、参考文献14七、评分表（见尾页）错误！未定义书签。附录：源代码14、功能描述1、输入火车厢

2、信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。3、出轨给出每节火车厢出轨提示。4、退出如果不需要操作就退出系统。二、总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。1、系统设计框图2、系统设计流程图三、详细设计1功能一：输入火车厢信息1 )概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排

3、列信息，并在屏幕上显示火车原始排列。2 )算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：inti,M,A100,N=0;printf("nn");printf("*nn");printf("=您好，欢迎光临火车转轨系统！=nn");printf("请输入您要进行转轨的火车车厢总长：");scanf("%d",&M);printf("n请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢号nn");for(i=0;i<M;i+)(sc

4、anf("%d",&Ai);)printf("未转轨前的火车厢排列如下，请核对：n");for(i=0;i<M;i+)printf("A%d=%dn",i,Ai);3)算法分析：此功能模块简单明了没有深度算法，在此不做分析。2功能二：入轨1 )概要设计：通过比较栈顶元素的大小的方法使得每个缓冲铁轨中车厢的排序是依次递减排列。本自定义的函数实现过程中调用了将初始化一个堆栈函数及单个元素进栈函数，实现需要的时候重新初始化一个堆栈并找到合适的堆栈存放车厢号后就将车厢进栈的操作。2 )算法描述:流程图:k=o;topk=NULL

5、;Init(top,+k);Push(top,Am,k);Printf("d%d”:k+1,topk->data;)Am>topk->data?0ar1=0；1<=kJY葭Am>top1->data1+Push(top,Am,l;Printf("d%d”,l+1,topl->data);L=k+1)Returnk+1;代码:Push(top,A0,O);voidinit(STLinktop,intm)/*初始化堆栈*/topm=NULL;intpush(STLinktop,intA,intm)/*入栈*/(STLinkp;if(!(

6、p=(STLink)malloc(LEN)return0;else(p->data=A;p->link=topm;topm=p;return1;inttrainpush(intM,intA,STLinktop)(intm,k=0,l;topk=NULL;/*初始化第一个堆栈*/push(top,A0,0);/*把第一节车厢压入缓冲铁轨*/printf("缓冲铁轨：1栈顶值：dn",top0卜data);for(m=1;m<M;m+)/*把车厢都压入缓冲铁轨*/(if(Am>topk卜>data)/*前面所有栈顶值最大值一定为最后一个栈的栈顶值，

7、如果此次需进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并把车厢号压入新的栈的栈底*/(init(top,+k);push(top,Am,k);printf("缓冲铁轨：%d栈顶值：dn",k+1,topk卜>data);else/*将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈的车厢号要大的栈中，比如要插入10号车厢，缓冲铁轨的栈顶值排列如下：2、11、5、12,13,将10插在11所在的栈白栈顶*/1=0;whi1e(1<=k)if(Am>top1->data)1+；elsepush(top,Am,1);printf

8、("缓冲铁轨：%d栈顶值:dn",1+1,top1卜>data);1=k+1;returnk+1;3)算法分析:本函数实现的是提示每节车厢应进入的缓冲铁轨号及将每节车厢压入到缓冲铁轨中，首先将存放车厢号的数组及将要进行初始化的栈顶指针数组top口作为实参传递给本自定义函数，首先初始化第一个堆栈，把第一节车厢压入栈中，输出缓冲铁轨号及第一节车厢号，后用for循环从第二个将要进栈的元素与前面的元素比较，前面所有栈顶值最大值一定为最后一个栈的栈顶值，如果此次需进栈的车厢号比前面所有栈顶值都大就重新初始化一个新的栈把车厢号压入新的栈的栈底并输出当前栈的栈号及本栈的栈顶值，否则

9、就把需进栈的车厢号压入前面已经存在的缓冲铁轨中。从第一个栈开始循环，找出第一个栈顶元素比需进栈元素要大的栈，将该车厢压入此栈中并修改栈顶值。就这样利用循环控制所有的车厢都进入到缓冲铁轨中。其中单个入栈函数push()函数的实现过程如下：定义一个我们自定义的结构体类型的指针，利用此指针申请一个新节点，将车厢号送入该节点的数据域，并将原来的栈顶指针top移向该新申请的节点，始终使得top指针指向栈顶元素。该算法最好的情况下（相对最好，因为此情况下需使用大量的堆栈）只需在当前最后一个堆栈进行操作，时间复杂度为0（1）,最差情况下（就是只有当前最后一个堆栈的栈顶值大于需进栈的车厢号）的时间复杂度为：0

10、（M*k）o3功能三：出轨1）概要设计：利用for循环每次都找出最小的栈顶元素显示该最小元素所在的栈号并使得其出栈完成火车厢重排工作。本自定义的函数实现过程中调用了判断堆栈为空函数及单个元素出栈函数，实现大量判断堆栈元素是否已经出栈为空并找到合适的栈顶元素后就将该车厢出栈的操作。2）算法描述：流程图：代码:intempty(STLinktop,intn)/*判断是否为空*/(return(topn=NULL);intpop(STLinktop,intm)/*出栈*/(intA;STLinkp;p=topm;A=p->data;topm=topm->link;free(p);retu

11、rnA;voidtrainpop(intM,intA,STLinktop,intN)(intm,n=0,min,l=0,amin=0;/*把所有车厢都压出缓冲铁轨*/*min=topn->data;for(m=0;m<M;m+)(for(l=n+1;l<N;l+)/*从第一个非空栈的第二栈起，将栈顶值与最小值比较*/*if(topl!=NULL)&&(topl->data<min)/*取缓冲铁轨中栈顶元素最小的*/*min=topl->data;amin=l;/*将栈顶值最小的栈的栈号保存起来*/*printf("本次出站车厢在%d

12、缓冲铁轨，请按提示将火车厢压出缓冲铁轨",amin);Am=pop(top,amin);/*把最小的栈顶元素压出栈并赋值给A*/*printf("A%d=%dn",m,Am);if(topamin=NULL)/*取出最小值后，将遇到的第一个非空栈的栈顶值重新赋给min*/*min=topamin+1->data;n=amin+1;)elsemin=topamin->data;n=amin;)3)算法分析：本函数实现的是提示每节车厢应进入的缓冲铁轨后顺序把每节车厢压出转轨站实现火车厢重排，将接收车厢号的数组及栈顶指针数组top口作为实参传递给本自定义函数

13、，首先定义一个变量min,初始化min为第一节车厢的栈顶值，用for循环控制外循环，依次取出每一节车厢。内循环也用for语句控制从第一个非空栈的第二栈起，将栈顶值与min比较，得到每一轮比较缓冲铁轨中最小的栈顶元素，并将栈顶值最小的栈的栈号保存起来，把最小的栈顶元素压出栈并赋值给存放出栈元素的数组，取出最小值后，将遇到的第一个非空栈的栈顶值重新赋给min,进入下一轮外循环，从而获得正确的火车厢排列，在此过程中用printf语句输出提示出栈元素在几号缓冲铁轨。其中单个出栈函数pop()函数的实现过程如下：定义一个我们自定义的结构体类型的指针p及变量A,将原来的栈顶指针top赋给p,用A保存本次出

14、栈元素，将top指向下一个节点，再释放出栈元素所在的节点，始终使得top指针指向栈顶元素并可以返回出栈元素A该算法最好的情况下内循环每次都在第一个栈取元素即只有一个缓冲铁轨，时间复杂度为O(M),最差情况下为O(M*k)。4功能四：退出四、效果及存在问题1、效果显示:1）输入火车厢信息2）入轨:"C:DocxueimamdSettingsXAdiBiiiListratorJWXDeliugXlyI23Beze)f47g52369艮转轨前的火车麻排列如下，清核私AL03-1A12J=7AL3J=HAL4J=5卜=2H161=2AF?=FAFfl3=9质需要的转轨方法如下，请按淳示将各车

15、厢压入对应缓冲铁轨中：口XZ劲劲动劭也轨劲轨轨->F'v'谓-iv'-iv'liL-i1-LV二8T曾铁铁铁铁铁犷沪沪产产河沪ffff电好揄忠为常割胤事、1ZS432345=1值值tt=5=2:3-fi值值ffl-译慎求顶狈顶而Tni柱您好，您使用的线冲铁轨数为43）出轨:;Dttcu*eiiTsandScTing$XAdAinistratorDet>u?Xiy12)ex?:l15al:b=2S3M值值顶顶顶3且3仇顶顶顶监林S3*,1,!*!工到.功功轨即用轨动轨A次次政歌改政次次12345fi7e9匚=i-*翼rHiE.L-L1耕钞钞铁钞钞铁口E

16、mffl山山口口口W洋山承1,名2承N终在鸟<券£同2r专-b¥£L9金，演好，恋使用的缓冲铁轨数为通请按以下提示将每节二厢压出缓冲铁轨:RLMJ=1m11=2A2J=3AL3J=4AE41=5ft61=7AE7J-HAIBl-9iL二I二、二1二、二、二、二.*Lt-缺铁铁松钱聂轶轶然iiiiulroHaulnJITDIrDm?123234345在在正在布在正在在-nTT-TITn=rm-rm-An-HIT-rfTt-rmL_Ls二JTll.,iliLl.出出出根出出出出4）显示重排完成车厢排列2、存在问题直接把所有车厢都压入到缓冲铁轨中，存在浪费空间及时

17、间的现象，理想状态下碰到1号车厢及后续的连续车厢应直接输出不用进入转轨站，在此没有实现此功能。五、心得及体会与其临渊羡鱼，不如退而结网。这次数据结构课程设计给我的最大的印象就是如果自己有了兴趣，就动手去做，平时你再认真学习对各种数据结构对它的认识往往仍然是比较模糊的，通过此次课程设计对自己负责的课题要处理的数据结构有了质的的飞跃，首先能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；其次也提高程序设计和调试能力，通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中

18、的错误并且修改；并且培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高了我程序设计水平。六、参考文献数据结构教程（第二版）唐发根主编C语言程序设计夏涛主编附录：源代码/*假设一列货运列车共有n节编号分别为1门的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1n的次序排列，以便各车厢能够停靠在与其编号一致的站点。为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各车厢从右

19、到左按照编号1n的次序通过出轨处离开转轨站。要求：给了算法分析与完整的算法程序。*/#include<stdio.h>#include<malloc.h>#include<assert.h>#include<stdlib.h>#include<time.h>#defineLENsizeof(STACK)typedefstructnodeintdata;structnode*link;STACK50,*STLink;STLinktop50;voidinit(STLinktop,intm)/*初始化堆栈*/topm=NULL;intemp

20、ty(STLinktop,intn)/*判断是否为空*/return(topn=NULL);intpush(STLinktop,intA,intm)/*入栈*/(STLinkp;if(!(p=(STLink)malloc(LEN)return0;else(p->data=A;p->link=topm;topm=p;return1;intpop(STLinktop,intm)/*出栈*/(intA;STLinkp;p=topm;A=p->data;topm=topm卜>link;free(p);returnA;inttrainpush(intM,intA,STLinkto

21、p)(intm,k=0,l;topk=NULL;/*初始化第一个堆栈*/push(top,A0,0);/*把第一节车厢压入缓冲铁轨*/printf("缓冲铁轨：1栈顶值:%dn",top0->data);for(m=1;m<M;m+)/*把车厢都压入缓冲铁轨*/if(Am>topk->data)/*前面所有栈顶值最大值一定为最后一个栈的栈顶值，如果此次需进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并把车厢号压入新的栈的*/(init(top,+k);push(top,Am,k);printf("缓冲铁轨：%d栈顶彳K：%dn"

22、;,k+1,topk->data);else/*将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈的车厢号要大的栈中，比如栈顶*/(值:%dn",l+1,topl->data);要插入10号车厢，缓冲铁轨的栈顶值排列如下：2、11、5、12,13,将10插在11所在的栈的l=0;while(l<=k)(if(Am>topl->data)l+;else(push(top,Am,l);printf("缓冲铁轨：%d栈顶l=k+1;returnk+1;voidtrainpop(intM,intA,STLinktop,intN)(

23、intm,n=0,min,l=0,amin=0,bmin=0;/*把所有车厢都压出缓冲铁轨min=topn->data;for(m=0;m<M;m+)(for(l=n+1;l<N;l+)/*从第一个非空栈的第二栈起，将栈顶值与最小值比较*/(if(topl!=NULL)&&(top卜>data<min)/*取缓冲铁轨中栈顶元素最小的*/(min=topl->data;amin=l;/*将栈顶值最小的栈的栈号保存起来*/printf("本次出站车厢在%d缓冲铁轨",amin);Am=pop(top,amin);/*把最小的栈顶元素压出栈并赋值给A*/printf("A%d=%dn",m,Am);if(topamin=NULL)/*取出最小值后，将遇到的第一个非空栈的栈顶值重新赋给min*/(min=topamin+1->data;n=amin+1;else(min=topamin->data;n=amin;intexit()(return0;)voidmain()(inti,M,A100,N=0;printf("nn&quo