代码实现了基本的功能,但是不全面。题和代码都在文件里面!
编码练习
一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n, 即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢,车厢的编号应与车站(目的地)的编号相同,使各车厢从前至后按编号1到n的次序排列,这样,在每个车站只需卸掉最后一节车厢即可。所以,给定任意次序的车厢,必须重新排列它们。可能通过转轨站完成车厢的重排工作,在转轨站中有一个入轨、一个出轨和k个缓冲轨,缓冲轨位于入轨和出轨之间。开始时,n节车厢从入轨进入转轨站,转轨结束时各车厢按照编号1至n的次序离开转轨站进入出轨。假定缓冲轨按先进先出的方式动作,因此可将它们视为队列,并且禁止将车厢从缓冲轨移至入轨,也禁止从出轨移至缓冲轨。图1给出了一个转轨站,其中有3个缓冲轨H1,H2和H3。
要求:
设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;
设计并实现车厢重排算法;
分析算法的时间性能。
581742963 --------- H1 ----------- 987654321
--------- H2 ----------
入 轨 --------- H3 ----------- 出 轨
图1 转轨站示意图
1