北邮数据结构报告实验二车厢重排问题.doc

数据结构实验报告 实验名称： 实验二——栈和队列 学生姓名： 1．实验要求 实验目的： 进一步掌握指针、模版类、异常处理的使用； 掌握栈的操作的实现方法； 掌握队列的操作的实现方法； 培养使用栈解决实际问题的能力； 培养使用队列解决问题的能力； 题目5： 利用队列结构实现车厢重排问题。车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出的方式。编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。 提示：一列过车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后进入出轨，重新编排成一辆货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。 2. 程序分析 2.1 存储结构 存储结构： 原始列车排序的编号用普通的整型数组来实现，在缓冲轨中存放车厢编号时，使用队列进行实现，由于队列是先进先出，符合题目要求。由于建立了多条不同的缓冲轨，各个缓冲轨也组成了一个类的数组，方便存放和使用。 缓冲轨储存结构示意图如下： 缓冲轨1： 缓冲轨2：…… 缓冲轨3：…… …… 2.2 关键算法分析 一、关键算法： 1、构造队列 声明队列结点结构体 建立头结点 使front指针指向头结点 Rear指针指向头结点 2、入队操作 建立新的结点 将要入队的操作赋给新结点的data 使新结点的next为空 令rear的next指针指向新结点 rear指针后移 3、打印队列中的元素 设置工作指针指向front的下一个结点 输出当前工作结点的data值 工作指针后移 判断是否为空，若为空停止，不为空继续输出 4、列车编号入缓冲轨 将编号数组的第一个元素存入第一个缓冲轨 将编号数组下标增加1 判断若元素大于当前缓冲轨的最后一个元素或当前缓冲轨为空，则入队 若不成立，移至下一个缓冲轨继续判断 二、代码详细分析： 1、构造原始队列 关键代码： 建立新结点：NodeT * p=new NodeT ；p-next=NULL; 初始化头指针尾指针：rear=front=p; ; 2、将元素存入队列 关键代码： 建立新结点：NodeT * p=new NodeT; 赋值：p-data=x; 改变新结点指针域：p-next=NULL; 改变尾指针结点指针域：rear-next=p; 移动尾指针：rear=p; 示意图： 3、打印队列元素 关键代码： 建立工作结点：NodeT * q=front-next; 输出元素：coutq-data 指针后移：q=q-next; 4、车厢进入缓冲轨 关键代码： 建立类的指针：Queueint * track 建立缓冲轨数组：track= new Queueint[n]; 判断编号与缓冲轨：if(!track[j].Last()||track[j].Last()a[i]) 成立则入队：track[j].EnQueue(a[i]); 三、计算关键算法的时间、空间复杂度 构造队列O（1） 实现进入缓冲轨O（n2） 2.3 其他 在实现入轨操作时，时间复杂度较高，但在建立缓冲轨的时候，可以保证缓冲轨数量足够用。 3. 程序运行结果 测试主函数流程：流程图如图所示 流程图示意图 程序运行结果图如下： 测试条件：总车厢数为小于100的正整数 测试结论：程序可以实现100以内的编号的乱序车厢重排问题，并输出各个缓冲轨的车厢编号。 4. 总结 调试时出现的问题及解决的方法 心得体会改进 北京邮电大学信息与通信工程学院 第4页 北京邮电大学电信工程学院 第1页 Front Rear rear front ⑤ rear front ② ④ p ③ ③ ① front q q