数据结构之火车厢重排

1、目录 一、功能描述 . 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、效果显示 :

2、. 11 1）输入火车厢信息 . 12 2）入轨 . 12 3）出轨： . 12 4）显示重排完成车厢排列 . 13 2、存在问题 . 13 五、心得及体会 . 14 六、参考文献 . 14 七、 评分表（见尾页） . 错误！未定义书签。 附录：源代码 . 14 、功能描述 1、输入火车厢信息 设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供 必要数据信息。 2、入轨 给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。 3、出轨 给出每节火车厢出轨提示。 4、退出 如果不需要操作就退出系统。 二、总体概要设计 建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（

3、缓冲铁 中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单 节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车 厢排列。 1 、系统设计框图轨） printf(” 您好，欢迎光临火车转轨系统！= nn); 2、系统设计流程图 三、详细设计 1 功能一：输入火车厢信息 1 ）概要设计： 通过 printf 语句设置欢迎界面及显示让用户输入火车厢总长及火车 原始排列信息，并在屏幕上显示火车原始排列。 2 ）算法描述: 流程图： 在总流程图已经画出中， 此处不再累述 功能代码: int i,M,A100,N=0; prin tf(nn); prin tf(* nn

4、)； printf( 请输入您要进行转轨的火车车厢总长： ); scanf(%d,&M); printf(n 请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢 号 nn); for(i=0;iM;i+) scanf(%d,&Ai); printf( 未转轨前的火车厢排列如下，请核对： n); for(i=0;idata;) T / Amtopk data ar 1=0； ltopl-data l+ Push(top,Am,l; Printf( “ %d%d” ,l+1,topl-data); L=k+1) Return k+1; 代码: topm=NULL;

5、int push(STLink top,int A,int m) /* 入栈 */ STLink p; if(!(p=(STLink)malloc(LEN) return 0; else p-data=A; p-link=topm; topm=p; return 1; int trainpush(int M,int A,STLink top) int m,k=0,l; topk=NULL; /* 初始化第一个堆栈 */ push(top,A0,0); /* 把第一节车厢压入缓冲铁轨 */ printf( 缓冲铁轨 : 1 栈顶值 :%dn,top0-data); for(m=1;mtopk-d

6、ata) /* 前面所有栈顶值最大值一定为最后一个 栈的栈顶值，如果此次需进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并 把车厢号压入新的栈的栈底 */ init(top,+k); push(top,Am,k); printf( 缓冲铁轨： %d 栈顶值： %dn,k+1,topk-data); else /* 将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈 的车厢号要大的栈中，比如 要插入 10 号车厢，缓冲铁轨的栈顶值排列如下： 2、11、5、12，13，将 10 插在 11 所 while(ltopl-data) l+; else push(top,Am,

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

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

9、）的时间复杂度为： O（M*k）。 在的栈的栈顶 */ l=0; 值:dn,l+1,topl-data); 3 功能三：出轨 1）概要设计 ： 利用 for 循环每次都找出最小的栈顶元素显示该最小元素所在的栈号并使 得其出栈完成火车厢重排工作。本自定义的函数实现过程中调用了判断堆栈为 空函数及单个元素出栈函数，实现大量判断堆栈元素是否已经出栈为空并找到 合适的栈顶元素后就将该车厢出栈的操作。 2 ）算法描述： 流程图： 代码： int empty( STL ink top,i nt n) /* 判断是否为空 */ return (top n=NULL); int pop(STLink top,

10、int m) /* 出栈 */ int A; STLink p; p=topm; A=p-data; topm=topm-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=topn-data; for(m=0;mM;m+) for(l=n+1;ldatadata; amin=l; /* 将栈顶值最小的栈的栈号保存起来 */ /* printf( 本次出站车厢在 %d 缓冲铁轨 ,请按提示将火车厢压出缓冲铁

11、轨 ,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; 3) 算法分析 : 本函数实现的是提示每节车厢应进入的缓冲铁轨后顺序把每节车厢压出转 轨站实现火车厢重排，将接收车厢号的数组及栈顶指针数组 top 作为实参传 递给本自定义函数，首先定义一个变量 min,初始化

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

13、赋给 p，用 A 保存本次出栈 元素，将 top 指向下一个节点，再释放出栈元素所在的节点，始终使得 top 指 针指向栈顶元素并可以返回出栈元素 A。 该算法最好的情况下内循环每次都在第一个栈取元素即只有一个缓冲铁轨， 时间复杂度为 0(M),最差情况下为 O(M*k)。 4 功能四：退出 四、效果及存在问题 1、效果显示 : 1）输入火车厢信息 您好，念便用的缓冲铁轨数为询 2）入轨: I、飞：D0cu*ents and SctTingsAdAinistratorXJ面 MebuH】yJ2y-四。 走转轨前的火车fl排列如下, L0 3-1 rsi=9 想需更的转轴方、法如下.请按鬼示将各

14、丰厢庄入对应塢冲铁軌中： 颈 轨 訓轨轨轨轨轨轨 - -_ _ FvFvL L i)i)iLE.JiLE.J- - iviv二8r 8r 尸尸尸卜尸尸沪戸R- 1ZS432 345 d d 7 7 8 8 * = =1 1igffligffl谊=5=2:35=2:3- -fifi值 值fflffl- -ilil- -谊顶 顶顶顶顶栈 桟 i8i8 3）出轨: I、:DaimiLeiiTs and ScTingsXAdAinistratarj面乳码 e 隠好，您使用的鍰冲钱轨教为汚 请按认下提示将每节土厢压岀缓冲诜轨: 4）显示重排元成车厢排列 tt=顶顶恿旦宜 5 2 3 6 5 2 3 6

15、宜 口 CtICIZIZI 口口口 JII JibJII Jib- -JI JJI JfcpJfcpJ 媛缓 RLMJ=1 AC1J=2 A E2 J =3 AL3J=4 ftt41=5 ft61=7 AE7J-H AIBl-? 勻纨轨勃豹轨轨轨轨 L L 二- 二1 1 二 I I 二、二* 二、二.* LtLt- - 斗斗#u.u. WSSWSS醫a a t-lroy 昙 u= u= 1111吾、 12 3 2 3 4 3 4 5 12 3 2 3 4 3 4 5 在社任在7F7F在在在花 -nTT -TFT 一二 rmrm - -rmrm - -T3rT3r - -rnTrnT - -n

16、*En*E - -rm rm L_ Ls L_ Ls 二JTLL.JTLL.,ILl LL,. Ll.ILl LL,. Ll. 车车车+#车 出岀岀洋岀出出出 AAftAAft次: 12 3 412 3 4 57895789 穿竟第莒當fe算第第 2、存在问题 直接把所有车厢都压入到缓冲铁轨中，存在浪费空间及时间的现象，理想状 态下碰到 1 号车厢及后续的连续车厢应直接输出不用进入转轨站，在此没有实 现此功能。 五、心得及体会 与其临渊羡鱼，不如退而结网。这次数据结构课程设计给我的最大的印象 就是如果自己有了兴趣，就动手去做，平时你再认真学习对各种数据结构对它 的认识往往仍然是比较模糊的，通过

17、此次课程设计对自己负责的课题要处理的 数据结构有了质的的飞跃，首先能根据实际问题的具体情况，结合数据结构课 程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的 存储结构，并能设计出解决问题的有效算法；其次也提高程序设计和调试能力， 通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试方法， 迅速找出程序代码中的错误并且修改；并且培养算法分析能力。分析所设计算 法的时间复杂度和空间复杂度，进一步提高了我程序设计水平。 六、参考文献 数据结构教程（第二版） 唐发根 主编 C 语言程序设计 夏涛 主编 附录：源代码 /* 假设一列货运列车共有 n 节编号分别为 1n 的车

18、厢，在进站前这 n 节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进 入车 站时，所有车厢从前到后按编号 1n 的次序排列，以便各车厢能够 停靠在与其编号一致的站点。 为了达到这样的效果，可以在一个转轨站里完成车厢的重排工 作。在转轨站中有一个入轨，一个出轨和 K 个位于入轨与出轨间的缓冲铁 轨。 如下图所示。开始时，具有 n 节车厢的货车从入轨处进入转轨站；转 轨结束时，各车厢从右到左按照编号 1n 的次序通过出轨处离开转轨站。 要求：给了算法分析与完整的算法程序。 */ #include #include #include #include #include #define

19、 LEN sizeof(STACK) typedef struct node int data; struct node *link; STACK50,*STLink; STLink top50; void init(STLink top,int m) /* 初始化堆栈 */ topm=NULL; int empty( STLink top,int n) /* 判断是否为空 */ return (topn=NULL);int push(STLink top,int A,int m) /* 入栈 */ STLink p; if(!(p=(STLink)malloc(LEN) return 0;

20、else p-data=A; p-link=topm; topm=p; return 1; int pop(STLink top,int m) /* 出栈 */ int A; STLink p; p=topm; A=p-data; topm=topm-link; free(p); return A; int trainpush(int M,int A,STLink top) int m,k=0,l; topk=NULL; /* 初始化第一个堆栈 */ push(top,A0,0); /* 把第一节车厢压入缓冲铁轨 */ printf( 缓冲铁轨 : 1 栈顶值 :%dn,top0-data);

21、 for(m=1;mtopk-data) /* 前面所有栈顶值最大值一定为最后一个栈 的栈顶值，如果此次需 进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并把车厢号压入新的栈的 栈底 */ init(top,+k); push(top,Am,k); printf( 缓冲铁轨： %d 栈顶值： %dn,k+1,topk-data); else /* 将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈的车厢号 要大的栈中，比如 要插入 10号车厢，缓冲铁轨的栈顶值排列如下： 2、11、 5、 12， 13，将 10插在 11所在的栈的 栈顶 */ l=0; while(l

22、topl-data) l+; else push(top,Am,l); printf( 缓冲铁轨 : %d 栈顶 值:dn,l+1,topl-data); l=k+1; return k+1;void trainpop(int M,int A,STLink top,int N) int m,n=0,min,l=0,amin=0,bmin=0; /* 把所有车厢都压出缓冲铁轨 min=topn-data; for(m=0;mM;m+) for(l=n+1;ldatadata; amin=l; /* 将栈顶值最小的栈的栈号保存起来 */ printf( 本次出站车厢在 %d 缓冲铁轨 ,amin); Am=pop(top,amin); /* 把最小的栈顶元素压出 栈并赋值给 A*/ printf(A%d=%dn,m,Am); if(topamin=NULL) /* 取出最小值后，将遇到的第一个非空栈 的栈顶值重