火车厢重排问题.doc

目录 1．题目： 3 1-1.队列的应用——火车厢重排问题 3 1-2.简单指导 4 2.设计目的及内容 5 2-1.目的 5 2-2.内容 5 设计内容 5 3.概要设计 6 3-1.函数调用的关系图 6 3-2.流程图 6 3-2-1. 总体程序设计流程图 6 3-2-2 Output函数的流程图. 7 3-2-3. Hold函数的流程图 8 4. 算法描述 10 4-1. 模块一：LinkQueue() 构造函数 10 初始化一个空的链队列 10 4-2. 模块二：析构函数 10 释放链队列中的各结点的存储空间 10 4-3. 模块三：EnQueue函数 11 将队头元素x入队 11 4-4. 模块四：DeQueue函数 11 将队头元素出队 11 4-5.模块五：GetQueue函数 11 取链队列的队头元素 11 4-6. 模块六：Empty函数 12 判断链队列是否为空 12 4-7. 模块七：Outputput 函数 12 该函数调用6个函数模板来实现火车厢重排问题，预设K个缓冲轨道，通过运用函数模板来比较各个缓冲轨道的队头元素，确定队列的出队、入队元素，最后通过输入和输出函数来实现火车厢由小到大的顺序出轨 12 5.源程序 13 6. 运行结果及性能分析 17 6-1. 运行结果及性能分析 17 6-1-1.开始后的界面 17 6-1-2. 输入火车总数i=5和缓冲轨数j=3后的界面 18 6-1-3.随机输入1.2.3.4.5的进入顺序后开始进入重排界面 18 6-2. 性能分析 18 7.心得体会 19 1．题目： 1-1.队列的应用——火车厢重排问题 假设一列货运列车共有n节编号分别为1~n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1~n的次序排列，以便各车厢能够停靠在与其编号一致的站点。 1-2.简单指导 为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各车厢从右到左按照编号1~n的次序通过出轨处离开转轨站 2.设计目的及内容 2-1.目的 1、利用C言和C++等编程语言对实际问题进行编程，同时使用数据结构中的算法，实现各个函数的功能。 2、通过课程设计理解并掌握队列的基本概念及其操作，并在此基础上编写队列的基本算法（比如说初始化一个队列，测试队列是否为空，取当前对头元素，队列的插入及删除等）。 3、学会分析排序中的时间复杂度问题，提高分析算法的能力。 4、培养我们的算法分析能力，程序设计调试能力，纠错能力，以及遇到困难时沉着稳重、坚持不懈的能力。 2-2.内容 设计假设一列货运列车共有n节编号分别为1~n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1~n的次序排列，以便各车厢能够停靠在与其编号一致的站点。 设计内容 （1）设计一个出轨和K个位于入轨与出轨间的缓冲铁轨来完成各个车厢按其编号排序。 （2）构造一个类来存储队列的各个函数，判定各个队列是否为空，并确定元素的入队、出队，完成车厢能够按其编号大小排序。 3.概要设计 3-1.函数调用的关系图 3-2.流程图 3-2-1. 总体程序设计流程图 3-2-2 Output函数的流程图. 3-2-3. Hold函数的流程图 3-2-4.Railroad()函数的流程图 4. 算法描述 该问题是利用C++语言来实现的，首先通过建立一个类模板，类模板下有6个函数模板（分别为LinkQueue::LinkQueue(),LinkQueue::~LinkQueue(),LinkQueue::EnQueue(T x),T LinkQueue::DeQueue(),T LinkQueue::GetQueue(),bool Empty()），使用函数模板是先声明一个函数模板，之后才转化成相应的模板函数来进行调用执行，具体流程为函数模板实例化为模板函数，然后被main和output函数调用 4-1. 模块一：LinkQueue() 构造函数 初始化一个空的链队列 template class T LinkQueueT::LinkQueue( ) { Node T *s; //队列存在 s=new NodeT; //定义S为一个新的节点 s-next=NULL; //s为空 front=rear=s