实验2用堆栈解决火车车厢重排问题的编程

《实验2用堆栈解决火车车厢重排问题的编程》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验2用堆栈解决火车车厢重排问题的编程一、目的通过对本次实验，我们应：1、加深对线性表、堆栈的认识；2、加深接口、类、索引器的认识；3、掌握堆栈数据结构，并应用堆栈编程解决实际问题。二、实验准备1、软件准备：C#.net。2、参考数据（示例）：文件夹“…实验2示例”中的数据。三、实验背景描述1、问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1-n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。当所有的车厢都按照这种次序

2、排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图3.1a给出了一个转轨站，其中有k=3个缓冲铁轨H1，H2和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。在图3.1a中，n=9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图3.1b给出了按所要求的次序重新排列后的结果。图2.1根据上面的描述，编写程序实现下面的功能：·编写一算法实现火车车箱的重排；·编写程序模拟图2.1所示的具有9节车厢

3、的火车入轨和出轨的过程。·程序主界面设计如图2.2所示。图2.22、问题分析为了重排车厢，需从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。当缓冲铁轨上的车厢编号不是按照从顶到底的递增次序排列时，重排任务将无法完成。新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v>u,且v是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。只有这样才能使后续的车厢重排所受到的限制最小。3、堆栈的基本

4、操作·初始化栈：也就是产生一个新的空栈；·入栈操作Push(Tx):将指定类型元素x进到栈中；·出栈操作Pop():将栈中的栈顶元素取出来，并在栈中删除栈顶元素；·取栈顶元素GetTop():将栈中的栈顶元素取出来，栈中元素不变；·判断栈空IsEmpty():若栈为空，返回true，否则返回false；·清空操作Clear()：从栈中清除所有的数据元素。四、实验内容1、应用顺序存储结构（顺序栈）编程实现火车车厢重排；2、应用链式存储结构（单链栈）编程实现火车车厢重排。