（1小时数据结构）数据结构c++描述（十一）--- 堆栈应用（火车车厢重排）

本章使用的是堆栈的链表来解决问题的，传送门：堆栈表示火车车厢重排如同图中一样通过，这三个缓冲铁轨，来让火车车厢来排出来顺序。每个缓冲都是一个堆栈。中间状态，这样就可以把数放入。满足：• 车厢可以从入轨的前部（即右端）移动到一个缓冲铁轨的顶部或出轨的左端。• 车厢可以从一个缓冲铁轨的顶部移动到出轨的左端。也会存在铁轨不足，跳出false；代码：先写上两个函数的声明：/*数组结构中的堆栈火车车厢重

比卡丘不皮

1004人浏览 · 2020-07-15 15:50:59

比卡丘不皮 · 2020-07-15 15:50:59 发布

本章使用的是堆栈的链表来解决问题的，传送门：堆栈表示

火车车厢重排

如同图中一样通过，这三个缓冲铁轨，来让火车车厢来排出来顺序。每个缓冲都是一个堆栈。

中间状态，这样就可以把数放入。

满足：

• 车厢可以从入轨的前部（即右端）移动到一个缓冲铁轨的顶部或出轨的左端。
• 车厢可以从一个缓冲铁轨的顶部移动到出轨的左端。

也会存在铁轨不足，跳出false；

代码：

先写上两个函数的声明：

/*
数组结构中的 堆栈 火车车厢重拍

对应书中代码：数据结构算法与应用c++描述

程序编写：比卡丘不皮

编写时间：2020年7月15日 14:30:09
*/

#pragma once
#include<iostream>
#include "LinkedStack.h"

using namespace std;
// 把车厢从缓冲铁轨送至出轨处，同时修改 minS和minH
void Output(int& minH, int& minS, LinkedStack<int> H[], int k, int n);
//在一个缓冲铁轨中放入车厢c
bool Hold(int c, int& minH, int &minS, LinkedStack<int> H[], int k, int n);

bool Railroad(int p[], int n, int k)：

//火车排序
//数组p 为入站前车厢顺序,n为车厢数，k为缓冲铁轨数
bool Railroad(int p[], int n, int k)
{
	//k 个缓冲铁轨，车厢初始排序为 p[1:n]
	// 如果重排成功，返回t r u e，否则返回false
	// 如果内存不足，则引发异常 NoMem 。
	//创建与缓冲铁轨对应的堆栈
	LinkedStack<int> *H;
	H = new LinkedStack<int>[k + 1];
	int NowOut = 1; //下一次要输出的车厢
	int minH = n + 1; //缓冲铁轨中编号最小的车厢
	int minS; //minH号车厢对应的缓冲铁轨
	// 车厢重排
	for (int i = 1; i<=n; i++)
	{
		if (p[i] == NowOut)
		{//直接输出
			cout << "Move car " << p[i] << " from input to output" << endl;
			NowOut++;
			// 从缓冲铁轨中输出
			while (NowOut == minH)
			{
				Output(minH, minS, H, k, n);
				NowOut++;
			}
		}
		else
		{
			if (!Hold(p[i], minH, minS, H, k, n))
			{
				return false;
			}
		}
	}
	return true;
}

void Output(int& minH, int& minS, LinkedStack<int> H[], int k, int n)

void Output(int& minH, int& minS, LinkedStack<int> H[], int k, int n)
{
	// 把车厢从缓冲铁轨送至出轨处，同时修改 m i n S和m i n H
		int c; // 车厢索引
			   // 从堆栈m i n S中删除编号最小的车厢 minH
	H[minS].Delete(c);
	cout << "Move car " << minH << " from holding track " << minS << " to output" << endl;
	// 通过检查所有的栈顶，搜索新的 m i n H和m i n S
	minH = n + 2;
	for (int i = 1; i <= k; i++)
		if (!H[i].IsEmpty() && (c = H[i].Top()) < minH) {
			minH = c;
			minS = i;
		}
}

bool Hold(int c, int& minH, int &minS, LinkedStack<int> H[], int k, int n)：

bool Hold(int c, int& minH, int &minS, LinkedStack<int> H[], int k, int n)
{
	// 在一个缓冲铁轨中放入车厢 c
	// 如果没有可用的缓冲铁轨，则返回 false
	// 如果空间不足，则引发异常 N o M e m
	// 否则返回true
	// 为车厢c寻找最优的缓冲铁轨
	int BestTrack = 0, BestTop = n + 1; //目前最优的铁轨 与 最优铁轨上的头辆车厢
	int x; //车厢索引
	for (int i = 1; i<=k; i++)
	{
		if (!H[i].IsEmpty()) //铁轨 i 不空
		{
			x = H[i].Top();
			if (c < x && x < BestTop)
			{
				// 铁轨 i 顶部的车厢编号最小
				BestTop = x;
				BestTrack = i;
			}
		}
		else   //铁轨 i 为空
		{
			if (!BestTrack)
			{
				BestTrack = i;
			}
		}
	}

	if (!BestTrack)
	{
		return false; //没有可用的铁轨
	}
	// 把车厢c 送入缓冲铁轨
	H[BestTrack].Add(c);
	cout << "Move car " << c << " from input " "to holding track " << BestTrack << endl;
	if (c < minH) { minH = c; minS = BestTrack; }
	return true;
}

测试函数：

void testRailroad()
{
	int a[] = { 0,5,8,1,7,4,2,9,6,3 };
	cout << "输入的车厢编号为 0 5 8 1 7 4 2 9 6 3" << endl;
	cout << Railroad(a, 9, 2) << endl << endl;
	
	int b[] = { 0,3,2,1,4,5,8,7,9,6 };
	cout << "输入的车厢编号为 0 3 2 1 4 5 8 7 9 6" << endl;
	cout << Railroad(b, 9, 2) << endl << endl;

	int c[10] = { 0, 3, 6, 9, 2, 4, 7, 1, 8, 5 };
	cout << "输入的车厢编号为 0 3 6 9 2 4 7 1 8 5" << endl;
	cout << Railroad(c, 9, 3) << endl;
}