xx 大学 xx 学院算法与数据结构试验报告设计名称： 算法与数据结构 设计题目： 队列的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）： xx 课题工作时间： 2012 年 4 月 26 日 说明：实验课程类别：课程内实验实验课程性质：必修适用专业、年级：2010 级计算机工程、计算机网络开课院、系：计算机科学与工程学院计算机工程教研室学时：18编写依据：《算法与数据结构》实验教学大纲修订时间：2012 年 2 月《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用上机的工作环境要求：Windows 2000 或以上操作系统、VC++ 6.0 或者其它高级程序设计语言。
学生应按指导教师的要求独立完成实验，并按要求撰写实验报告每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传报告内容至少包含如下内容：1、 学生基本情况：专业班级、学号、姓名2、 实验题目、实验内容3、 设计分析4、 源程序代码5、 测试用例（尽量覆盖所有分支）6、 实验总结一．实验内容与学时分配序次实验题目实验类型 基本技能训练学时一 线性结构综合应用 综合性（1）掌握线性结构的常用操作；（2）能够应用线性结构解决比较简单的问题 10二 非线性结构综合应 用 综合性（1）掌握树形、图形结构的插入、删除、查找等算法；（2）能够应用二叉树解决比较简单的问题4三 查找技术综合应用 综合性（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决简单的实际问题 2四 排序技术综合应用 综合性（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌2握各种排序方法的时间复杂度的分析方法一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。
二、试验内容(1)问题描述：一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站假定 n 个车站的编号分别为 1~n，即货运列车按照第 n 站至第 1 站的次序经过这些车站为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢所以，给定任意次序的车厢，必须重新排列它们车厢的重排工作可以通过国转轨站完成在转轨站中有一个入轨、一个出轨和 k 个缓冲轨，缓冲轨位于入轨和出轨之间假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题2)基本要求：设计存储结构表示 n 个车厢、k 个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：出 轨入 轨581742963 987654321H1H3H2出 轨入 轨581H1H3H2963742出 轨入 轨58H1H3H29674321出 轨入 轨5H1H3H2968754321出 轨入 轨H1H3H2987654321(a) 将 369、247 依次入缓冲轨 (b) 将 1 移至出轨，234 移至出轨(c) 将 8 入缓冲轨，5 移至出轨 (d) 将 6789 移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：1. 分别对k个队列初始化；2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号；3.1 如果入轨中的车厢编号等于nowOut，则3.1.1 输出该车厢；3.1.2 nowOut++；3.2 否则，考察每一个缓冲轨队列for (j=1; jusing namespace std;const MS=100;template struct QNode{T data;QNode *next;};template class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素 x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template LiQueue::LiQueue( ){QNode *s;s=new QNode;s->next=NULL;front=rear=s;}template LiQueue::~LiQueue( ){QNode *p;while(front){p=front;front=front->next;delete p;}}template void LiQueue::EnQueue(T x){QNode *s;s=new QNode; s->data=x; //申请一个数据域为 x的结点 ss->next=NULL;rear->next=s; //将结点 s插入到队尾 rear=s;}template T LiQueue::DeQueue(){ QNode *p; int x;if (rear==front) throw "下溢";p=front->next; x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为 1delete p;return x;}template T LiQueue::GetFront(){if (rear!=front) return front->next->data;}template T LiQueue::GetRear(){if(rear!=front)return rear->data;}template bool LiQueue::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout>n;cout>k;}void Train::ChongPai(){int a[MS];LiQueue*b;b=new LiQueue[k+2];cout>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<
六、试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前 C++语言，很好的解决了这一类问题其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过 vc6.0 来建立队列，以及初始化队列、进队列、出队列等等同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。