#include <iostream>
#include <string>using namespace std;typedef int EType; // 自定义链表的数据元素为整数。struct QType {int number;
};
//定义队列顺序存储结构
struct Queue
{QType* element; // 存放结点的数据元素。int front; //对头节点int rear; //队尾节点int maxsize; //队列最大容量
};//构造空队列算法
void CreatQueue(Queue& Q, int MaxQueueSize) {Q.maxsize = MaxQueueSize;Q.element = new QType[Q.maxsize];Q.front = 0;Q.rear = 0;
}//判断队列是否为空
bool IsEmpty(Queue& Q) {if (Q.front == Q.rear) return true;return false;
}//判断队列是否满了front=rear+1;
bool IsFull(Queue& Q) {if (Q.front == (Q.rear + 1) % (Q.maxsize + 1)) return true;return false;
}//返回队头元素的值
bool GetFront(Queue& Q, QType& result) {//将font后面一个位置的队列元素的值取出if (IsEmpty(Q)) return false;result = Q.element[(Q.front + 1) % (Q.maxsize + 1)];return true;
}//返回队尾元素的值
bool GetRear(Queue& Q, QType& result) {//将font后面一个位置的队列元素的值取出if (IsEmpty(Q)) return false;result = Q.element[(Q.rear + 1) % (Q.maxsize + 1)];return true;
}//进队运算
//将一个新的的元素x存储到当前rear所指空间的下一个位置,首先要判断队列是否为满了
bool EnQueue(Queue& Q, QType& x) {if (IsFull(Q)) return false;Q.rear = (Q.rear ) % (Q.maxsize + 1); //rear指向空间Q.element[Q.rear] = x;//存入xreturn true;
}//出队运算
//将front所指空间的下一个位置的元素取出,首先要判断队列是否为空
bool OutQueue(Queue& Q, QType& result) {if (IsEmpty(Q)) return false;Q.front = (Q.front + 1) % (Q.maxsize + 1); //front指向空间的下一个位置result = Q.element[Q.front];return true;
}/*
开始时,n节车厢进入缓冲轨道,再从缓冲轨道按编号1至编号n的次序离开缓冲轨道,进入出轨为了重排车厢,需要按车厢到达入轨的先后,从前至后依次检查如果上的所有车厢。
如果正在检车的车厢就是下一个满足排列要求的车厢,就可以直接把它放到出轨上去。如果不是,则把他移动到缓冲轨道上,再按输出次序要求,轮到它时才将它放到出轨上
缓冲铁轨是按照FIFO队列的方式使用的。RearrangementTrack重新排列n个车厢,它最多可以使用k个缓冲轨道,如果缓冲轨道不足,不能成功地重排
则返回false,否则返回true开始创建一个指向k个队列的表头数组Q[k],其中Q[i](i=1,2,...k)表示第i个缓冲轨道。NowOut是下一个要输出至出轨
的车厢号。minH是已经进入到各缓冲轨道中最小的车厢号,minQ是minH所在是缓冲铁轨,即队列编号算法OutPut用于将当前再缓冲轨道中可以送到出轨的车厢,送至出轨,它同时再寻找缓冲轨道中最小的车厢编号的车厢
确认其能否送至出轨,如可以则送至出轨,并修改minQ和minH算法Hold根据车厢调度规则,把某个暂时不能送至出轨的车厢current送人一个缓冲轨道,
如果current可以成为缓冲轨道中新的最小车厢,就修改minQ和minH。将一节暂时不能送至出轨的车厢移动到缓冲铁轨是,采用如下的原则确定应该把这节车厢移动到哪一个缓冲铁轨,
这个原则可以减少缓冲铁轨的使用。
(1)该缓冲轨道上现有的各车厢的编号都小于current
(2)如果多个缓冲轨道都满足这一条件,则选择第一个缓冲轨道队尾(左端)车厢编号醉倒的缓冲铁轨
(3)如果已有车厢的缓冲铁轨中,队尾的车厢编号都大于current,则current选择一个空的缓冲铁轨(如果存在)则进入
(4)如果无空缓冲铁轨可选择,则无法调度
*/
bool RearrangementTrack(int r[],int n,int k) {//车厢初始排列为r[1:n],如果成功排列则返回true,否则false//创建k个缓冲铁轨队列H,并初始化为空队列Queue* Q = new Queue[k];int MaxQueueSize = 10;for (int i = 0; i < k; i++) {CreatQueue(Q[i], MaxQueueSize);}int NowOut = 1;//当前应该输出的车厢编号int minH = n + 1;//缓冲轨道中编号最小的车厢编号,目前假设为0_____车厢编号int minQ;//minQ车厢对应的缓冲铁轨编号______铁轨编号for (int i = 1; i <= n; i++) {if (r[i] == NowOut) {//当前到站的车厢编号是刚刚出站的车厢编号的后一个,则直接输出cout << "从入轨输出" << r[i] << "号车厢到出轨" << endl;if (NowOut != n)//如果车厢还没有发完NowOut++;//当前应该输出下一车厢while (minH == NowOut) {//缓冲轨道中编号最小的车厢编号就是当前应该发车的车厢编号//从缓冲轨道输出minHOutPut(minH, minQ, Q, k, n);if (NowOut != n)NowOut++;//当前应该输出下一车厢}}else { //将r[i]送入某个缓冲轨道if (!Hold(r[i], minH, minQ, Q, k, n)) {delete []Q;return false;}}delete []Q;return true;}
}void OutPut(int &minH,int &minQ,Queue Q[],int k,int n) {// 从minQ中输出最小车厢minH,寻找下一个最小的车厢编号minH及对应的铁轨编号int current;//当前的车厢编号QType x;x.number = minH;//当前最小车厢编号OutQueue(Q[minQ], x);//最小车厢轨道中弹出最小车厢cout << "从" << minQ << "号缓冲铁轨输出" << minH << "号车厢到出轨" << endl;minH = n + 1;//假设一个最小的车厢编号,它比实际的车厢号大,以后替换for (int i = 1; i < k;i++) {//通过检查所有队列的首部,寻找新的minQ和minHGetFront(Q[i], x);current = x.number;if (!IsEmpty(Q[i]) && current < minH) {//如果该轨道的车厢不为空,并且当前的车厢编号小于最小的车厢编号minH = current;//最小的车厢编号就是当前车厢编号minQ = i;//当前轨道就是最小车厢所在轨道}}
}bool Hold(int current,int &minH,int &minQ,Queue Q[],int k,int n) {//为车厢current寻找最优的缓冲铁轨,如果没有,则返回false,否则返回trueint BestCushion = 0;//目前最优的缓冲铁轨,为0时表示还未找到最优的缓冲铁轨int BestLast = 0; //BestCushion最优的缓冲铁轨的最后一节车厢编号QType x; //车厢的编号for (int i = 1; i < k; i++) {//扫描缓冲轨道if (!IsEmpty(Q[i])) {//缓冲轨道i不为空GetRear(Q[i], x);//缓冲轨道的最后一个车厢,返回给xif (current > x.number && x.number > BestLast) {//当前车厢大于x车厢,并且x车厢大于最优轨道的最后一节车厢BestLast = x.number;BestCushion = i;}}else {//current小于已使用缓冲轨道的最后一节车厢的编号,则进入未使用的缓冲轨道iif (!BestCushion) BestCushion = i;}}if (!BestCushion) {//无可用缓冲轨道,无法调度,失败cout << "wrong!!!缓冲轨道不足,无法调度,失败" << endl;return false;}x.number = current;EnQueue(Q[BestCushion], x);//吧current压入最有铁轨队列cout << "从入轨将" << current << "号车厢一道最优缓冲铁轨" << BestCushion << endl;if (current < minQ) {//检查current是否可以成为新的minQ和minH,如果可以,那么就修改minQ = current;minH = BestCushion;}return true;
}
详细解决方案
深入理解数据结构——列车重排算法
热度:87 发布时间:2024-01-17 05:09:38.0
相关解决方案
- 算法效率(数据结构),该如何解决
- 数据结构,很无力~该怎么处理
- 数据结构,该怎么处理
- java 数据结构,该如何解决
- 数据库 数据结构 关于索引解决办法
- 数据结构,离散数学什么的重要吗。该怎么解决
- 数据结构 - 线性表学习(php模拟)
- 【数据结构】【归并排序】
- 数据结构 05——树与二叉树
- 数据结构——01数据结构绪论
- 数据结构——02算法简介
- 《数据结构(C语言版)》课程学习(15)——实验项目名称:矩阵的转置
- 数据结构--连续内存分配的实现
- n叉树 数据结构
- 链表 数据结构
- Hash表 数据结构
- 数据结构——红黑数学习
- c(数据结构)下树的创建的非递归算法
- 数据结构-时间复杂度大O排名
- 数据结构---顺序表
- 数据结构----顺序栈
- 【数据结构】#数据结构复习提纲
- 数据结构 递归遍历二叉树 C/C++
- 数据结构 C/C++ 冒泡排序
- 数据结构 C/C++ 关键路径
- 数据结构 C/C++ 链栈
- 数据结构 C/C++ 链式队列
- 数据结构 C/C++ 对角矩阵
- 数据结构 C/C++ 对称矩阵
- C/C++ 数据结构 单链表