火车厢重排问题

《火车厢重排问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1.题目：21・1.队列的应用一一火车厢重排问题212简单指导22•设计目的及内容32・1•目的322内容3设计内容33•概要设计43・1•函数调用的关系图432流程图43-2-1.总体程序设计流程图43-2-2Output函数的流程图53-2-3.Hold函数的流程图64.算法描述84-1.模块一：LinkQueue()构造函数8初始化一个空的链队列84-2.模块二：析构函数8释放链队列中的各结点的存储空间84-3・模块三:EnQueue函数9将队头元素x入队94-4.模块四：DeQueue函数9将队头元素出队94・5

2、.模块五：GetQueue函数9取链队列的队头元素94-6.模块六：Empty函数10判断链队列是否为空104-7.模块七：Outputput函数10该函数调用6个函数模板来实现火车厢重排问题，预设K个缓冲轨道，通过运用函数模板来比较各个缓冲轨道的队头元素，确定队列的出队、入队元素，最后通过输入和输出函数來实现火车厢由小到大的顺序出轨105.源程序116.运行结果及性能分析156-1.运行结果及性能分析156-1・1・开始后的界面156-1-2.输入火车总数i=5和缓冲轨数j=3后的界面166-1-3.随机输入123.4.5

3、的进入顺序后开始进入重排界面1662性能分析167•心得体会171・题目:1-1•队列的应用——火车厢重排问题假设一列货运列车共有n节编号分别为1〜n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1〜n的次序排列，以便各车厢能够停靠在与其编号一致的站点。12简单指导为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站屮有一个入轨，一个出轨和K个位于入轨与岀轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各

4、车厢从右到左按照编号1〜n的次序通过出轨处离开转轨站2•设计目的及内容2・1•目的1、利用C言和C++等编程语言对实际问题进行编程，同时使用数据结构中的算法，实现各个函数的功能。2、通过课程设计理解并掌握队列的基木概念及其操作，并在此基础上编写队列的基木算法（比如说初始化一个队列，测试队列是否为空，取当前对头元素，队列的插入及删除等）。3、学会分析排序中的时间复杂度问题，提高分析算法的能力。4、培养我们的算法分析能力，程序设计调试能力，纠错能力，以及遇到困难时沉着稳重、坚持不懈的能力。Z2内容设计假设一列货运列车共有n节编号

5、分别为1〜n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号l~n的次序排列，以便各车厢能够停靠在与其编号一致的站点。设计内容（1）设计一个出轨和K个位于入轨与出轨间的缓冲铁轨来完成各个车厢按其编号排序。（2）构造一个类来存储队列的各个函数，判定各个队列是否为空，并确定元素的入队、出队，完成车厢能够按其编号大小排序。3•概要设计3・1•函数调用的关系图3・2•流程图321•总体程序设计流程图3-2-2Output函数的流程图.3・2・3・Hold寿3,24R

6、aihoad()図磨3漓扁囹BesHnlckHLHwestTnlckLE4.算法描述该问题是利用C++语言来实现的，首先通过建立一个类模板，类模板下有6个函数模板(分别为LinkQueue::LinkQueue(),LinkQueue:>LinkQueue(),LinkQueue::EnQueue(Tx),TLinkQueue::DeQueue(),TLinkQueue::GetQueue(),boolEmptyO),使用函数模板是先声明一个函数模板，之后才转化成相应的模板函数来进行调用执行，具体流程为函数模板实例化为模板函

7、数，然后被main和output函数调用4-1.模块一：LinkQueue()构造函数初始化一个空的链队列templateLinkQueue::LinkQueue()Node*s;s=newNode;〃队列存在〃定义s为一个新的节点s・>nex匸NULL;front=rear=s;〃s为空〃队列为空}4-2.模块二：析构函数释放链队列中的各结点的存储空间templateLinkQueue:>LinkQueue(){while(front)Node*p;p=fron

8、t->next;deletefront;front=p;〃假设队列存在〃输入的值不存在〃销毁队列〃释放队列所占用的存储空间}4-3.模块三：EnQueue函数将队头元素X入队templatevoidLinkQueue::EnQueue(Tx)Node*s;s=n