【原】072.火车车厢重排

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
#include "malloc.h"
#include "string.h"
#define StackSize 100 //假定预分配的栈空间最多为100个元素 
#define MaxLength  100// 最大的字符串长度 	
typedef int DataType;//假定栈元素的数据类型为整数 	
typedef struct{
	DataType data[StackSize];
	int top;
}SeqStack;   

// 置栈空
void Initial(SeqStack *S)
{//将顺序栈置空
	S->top=-1;
} 
//判栈空
int IsEmpty(SeqStack *S)
{
	return S->top==-1;
}
//判栈满
int IsFull(SeqStack *S)
{
	return S->top==StackSize-1;
}
//进栈
void Push(SeqStack *S,DataType x)
{
	if (IsFull(S))
	{
		printf("栈上溢"); //上溢,退出运行
		exit(1);
	}
	S->data[++S->top]=x;//栈顶指针加1后将x入栈
}
//出栈
DataType Pop(SeqStack *S)
{
	if(IsEmpty(S))
	{
		printf("栈为空"); //下溢,退出运行
		return -1;
	}
	return S->data[S->top--];//栈顶元素返回后将栈顶指针减1
}
// 取栈顶元素
DataType Top(SeqStack *S)
{
	if(IsEmpty(S))
	{
		printf("栈为空"); //下溢,退出运行
		exit(1);
	}
	return S->data[S->top];
}
int  Hold(int c,int *minH, int *minS,SeqStack H[],int k, int n)
{// 在一个缓冲铁轨中放入车厢c
	// 如果没有可用的缓冲铁轨，则返回0
	// 如果空间不足，则引发异常N o M e m
	// 否则返回1
	// 为车厢c寻找最优的缓冲铁轨
	// 初始化
	int BestTrack = 0,i; // 目前最优的铁轨
	int BestTop = n + 1;// 最优铁轨上的头辆车厢
	int x;// 车厢索引
	//扫描缓冲铁轨
	for (i = 1; i <= k; i++)
		if (IsEmpty(&H[i])) 
		{// 铁轨i 不空
			x = Top (&H[i]) ;
			if (c<x && x < BestTop)
			{//铁轨i 顶部的车厢编号最小
				BestTop = x;
				BestTrack = i;
			}
		}
		else // 铁轨i 为空
			if (!BestTrack) 
				BestTrack = i;
			if (!BestTrack) 
				return 0; //没有可用的铁轨
			//把车厢c 送入缓冲铁轨
			Push(&H[BestTrack],c);
			printf("Move car %d  from input to holding track %d\n" ,c, BestTrack);
			//必要时修改minH 和minS
			if (c<*minH) {
				*minH = c; 
				*minS = BestTrack; 
			}
			return 1;
}
void Output(int* minH, int* minS, SeqStack H[ ], int k, int n)
{ //把车厢从缓冲铁轨送至出轨处，同时修改m i n S和m i n H
	int c,i; // 车厢索引
	// 从堆栈m i n S中删除编号最小的车厢minH
	c=Pop(&H[*minS]) ;
	printf("Move car %d from holding track %d to output\n",*minH,*minS);
	// 通过检查所有的栈顶，搜索新的m i n H和m i n S
	*minH=n+2;
	for (i = 1; i <= k; i++)
		if (!IsEmpty(&H[i]) && (c=Top(&H[i])) < *minH) {
			*minH = c;
			*minS = i;
		}
}
int Railroad(int p[], int n, int k)
{// k个缓冲铁轨，车厢初始排序为p [1:n]
	// 如果重排成功，返回1，否则返回0
	// 如果内存不足，则引发异常NoMem 。
	//创建与缓冲铁轨对应的堆栈
	SeqStack *H;
	int NowOut = 1; //下一次要输出的车厢
	int minH =n+1; //缓冲铁轨中编号最小的车厢
	int minS,i; //minH号车厢对应的缓冲铁轨
	H=(SeqStack*)calloc((k+1),sizeof(SeqStack)*(k+1));
	//车厢重排
	for (i = 1; i<= n; i++)
		if (p[i] == NowOut) {// 直接输出t
			printf("移动车厢%d从出口到入口",p[i]);
			NowOut++;
			//从缓冲铁轨中输出
			while (minH == NowOut) {
				Output(&minH, &minS, H, k, n);
				NowOut++;
			}
		}
		else {// 将p[i] 送入某个缓冲铁轨
			if (!Hold(p[i], &minH, &minS, H, k, n))
				return 0;
		}
		return 1;
}
void main(void)
{
	int p[8]={2,4,1,6,5,3,8,7};
	Railroad(p,8,4);
}