北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验2——题目五 学生姓名： 班 级： 班内序号： 学 号： 日 期：
1．实验要求
利用队列结构实现车厢重排问题。车厢重排问题如下： 一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。
2. 程序分析
2.1 存储结构
要实现车厢的重排列，需要用到一系列的缓冲轨道。车厢只能从后进，从前出，用队列是正合适的。因为要从头访问，且不知道有多少个元素，故产用链表比较合适，也方便操作。用链队列来表示一个缓冲轨道，可以将车厢排入其中。其元素为一个节点，表示有车厢的序号，和所指向的下一个节点。用一个数组来存放这样一些缓冲轨道。用另外一个数组来存放未排序的车厢。
以下是一个队列的结构图：
……… Data Data Data Next Next Next
Front Rear
车厢节点
struct Node {
第1页
北京邮电大学信息与通信工程学院
int Data; Node * Next; };
缓冲轨道
class LinkQueue {
public: LinkQueue(){} // 构造函数 ~LinkQueue(){} // 析构函数 void InQueue(int a){} // 车厢入队操作 void OutQueue(){} //车厢出队操作 bool Empty(){} // 判断缓冲轨道是否为空 Node * GetRear(){} // 获得尾指针 Node * GetFront(){} // 获得头指针 private: Node * Front; // 头指针 Node * Rear; // 尾指针 };
2.2 关键算法分析
关键函数和算法
1． 车厢入队操作 void InQueue(int a)
1.1 创建新节点temp
1.2 修改temp的数据data 1.3 temp的next制空
1.4 将temp赋值给尾指针rear的next 1.5 将temp赋值给尾指针rear
2． 车厢出队操作 void OutQueue()
2.1 判断队列是否为空。为空输出错误，不为空执行以下操作。 2.2 将front的next暂时存在新建的指针temp中。 2.3 将temp的next赋值给front的next。 2.4 删除temp节点。
2.5 判断如果front的next为空，将front赋值给next。
3. 产生1到n的随机排列
3.1 srand((unsigned int)time(NULL))
3.2 产生随机数，赋值给车厢序列的第一个元素。
3.3 产生随机数，并与之前车厢序列的每一个元素比较，若有相同的，则重复此部。如
没有相同的将其赋给车厢序列的下一个元素，再重复执行。
3.4 赋值完成后，结束程序段。
第2页
北京邮电大学信息与通信工程学院
4. 进入缓冲轨道
4.1 依次取出车厢序列中的元素，从第一个缓冲轨道开判定。
4.2 若该轨道没有元素，调用入列函数。若有元素，比较最后一个元素的data和车厢序
号的大小。
4.3 若车厢的序号大，调用入列函数。反之，进行下一缓冲轨道的比较。 4.4 若到最后一个缓冲轨还不能入列。则判断剩余的车厢顺序。
4.5 若剩余的车厢顺序从1依次排列，输出提示。结束程序段。反之，输出错误信息，结
束程序运行。
2.3 其他
交互界面的实现：
1. 使用While循环。持续的进行操作。 2. 输出提示信息，让用户进行选择，输入字符。
3. 用if去判断输入的字符是否也设定的字符相同。若相同就执行相应
的操作。
3. 程序运行结果
第3页
北京邮电大学信息与通信工程学院
第4页
北京邮电大学信息与通信工程学院
第5页
北京邮电大学信息与通信工程学院
4. 总结
本次实验使用的链队列。是首次遇到这样的问题。开始觉得无从下手，你知道怎么在实际中运用已经学过的知识。但是通过仔细的分析，结合实际的情况。结合书上的例题和运用，最终完成了实验的要求。
任何一个实验都不是一蹴而就的，都是需要一个过程的。准备做得越充分，后面代码的编写和函数的实现就是水到渠成，速度也会越来越快。同时，这也是一个知识不断丰富的过程。同时也是知识得到运用和加深的过程。所以不管学什么知识，都要将其用到实践中去，这样才有意义。特别是数据结构，理论需要实践的验证。
第6页