数据结构课程设计 火火车车厢重排调度

/* 本程序 "找出8位数中所有的雷劈数" by 陈映宏、陈淼鑫、林海鹏 Copyright (C) 2015 by 陈映宏、陈淼鑫、林海鹏，SYSU. All rights reserved. */ #include<iostream> #include<stack> using namespace std; void Reset(int in[], int n);//把车厢重新排布 void Output(int& minC, int& minB, stack<int> buffer[], int n); // 此函数把车厢从缓冲铁轨送至出轨处，同时修改minB和minC void Put(int c, int& minC, int &minB, stack<int> buffer[], int n);//将预备轨中的车厢送入缓冲轨 int main() { int n; s: cout << "请输入车厢个数:"; cin >> n; int *in = new int[n];//in为车厢原始顺序 cout << "请输入车厢初始排列顺序："; for (int i = 0; i < n; i++) cin >> in[i]; Reset(in, n); system("pause"); delete[]in; goto s; return 0; } void Reset(int in[], int n) { stack<int> *buffer = new stack<int>[n-1];//新建n-1个缓冲轨，保证一定能把车厢重新重新排布 int NextOut = 1; //下一次要输出的车厢 int minC = n + 1; //缓冲铁轨中编号最小的车厢min of carriage int minB; //minC号车厢对应的缓冲铁轨min of buffer // 车厢重排 //cout << "重新排布先后输出车厢为："; for (int i = 0; i < n; i++) { if (in[i] == NextOut)// 直接输出in[i] { cout << "直接送出" << in[i] << "号车厢" << endl; NextOut++; while ((minC == NextOut) && (NextOut<n+1)) // 从缓冲铁轨中输出 { Output(minC, minB, buffer, n); NextOut++; } } else// 将 in[i] 送入某个缓冲铁轨 Put(in[i], minC, minB, buffer, n); } return; } void Output(int& minC, int& minB, stack<int> buffer[], int n)//调用此函数时minC为下一个要输出的数 { // 从堆栈minB中输出编号最小的车厢minC //cout << minC << ' '; cout << "从" << minB << "号缓冲轨" << "送出" << minC << "号车厢" << endl; buffer[minB].pop(); // 通过检查所有的栈顶，搜索新的 minC和minB int temp; minC = n + 2; for (int i = 0; i < n - 1; i++) { if (!buffer[i].empty() && ((temp = buffer[i].top()) < minC)) { minC = temp; minB = i; } } } void Put(int c, int& minC, int &minB, stack<int> buffer[], int n) { // 在一个缓冲铁轨中为车厢c寻找最优的缓冲铁轨 int BestTrack = 0, // 目前最优的铁轨 BestTop = n + 1, // 最优铁轨上的头辆车厢 x;// 车厢索引 // 扫描缓冲铁轨 for (int i = 0; i < n-1; i++) if (!buffer[i].empty()) // 铁轨 i 不空 { x = buffer[i].top(); if (c < x && x < BestTop) // 铁轨 i 顶部的车厢编号最小 { BestTop = x; BestTrack = i; } } else // 铁轨 i 为空 if (!BestTrack) BestTrack = i; // 把车厢c 送入缓冲铁轨 buffer[BestTrack].push(c); cout << "把" << c << "号车厢" << "送进" << BestTrack << "号缓冲轨" << endl; // 必要时修改 minC 和 minB if (c < minC) { minC = c; minB = BestTrack; } return ; }