railroad.cpp

实现火车箱卸载的程序

#include <iostream.h>
#include <stdio.h>


class Node{
	friend class LinkedStack;
	private:
		T data;
		Node *link;
};

class LinkedStack{
	public:
		LinkedStack(){top=0;}
		~LinkedStack();
		bool IsEmpty() const {return 0==top;}
		bool IsFull() const;
		T Top() const;
		LinkedStack<T>& Add(const T& x);
		LinkedStack<T>& Delete(T& x);
	private:
		Node<T> *top;
};

LinkedStack<T>::~LinkedStack()
{
	Node<T>*next;
	while (top){
		next=top->link;
		delete top;
		top=next;
	}
}

bool LinkedStack<T>::IsFull() const
{
	try{Node<T> *p=new Node<T>;
		delete p;
		return false;}
	catch (NoMem){return false;}
}

T LinkedStack<T>::Top() const
{
	if(IsEmpty()) throw outofBounds();
	return top->data;
}

LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{
	Node<T> *p=new Node<T>;
	p->data=x;
	p->link=top;
	top=p;
	return *this;
}

LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{
	if (IsEmpty()) throw OutOfBounds();
	x=top->data;
	Node<T> *p=top;
	top=top->link;
	delete p;
	return *this;
}
//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;main;;;;;;;;;;;;;
bool Hold(int c,int& minH,int& minS,LinkedStack<int> H[],int k,int n);
void Output(int& minH,int& minS,LinkedStack<int> H[],int k,int n);
bool Railroad(int p[],int n,int k);

void main()
{
	int lp[9]={3,6,9,2,4,7,1,8,5};
	int ln=9;
	int lk=3;
	Railroad(lp[],ln,lk);
}
bool Railroad(int p[],int n,int k)
{
	LinkedStack<int> *H;
	H=new LinkedStack<int>[k+1];
	int NowOut=1;
	int minH=n+1;
	int minS;
	for(int i=1;i<=n;i++)
		if(p[i]==NowOut){
		cout<<"Move car"<<p[i]<<"from input to output"<<endl;
		NowOut++;
	       while(minH==NowOut){
			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)
{
	int c;
	H[minS].Delete(c);
	cout<<"Move car"<<minH<<"from holding track"<<minS<<"to output"<<endl;
	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)
{
	int BestTrack=0;
	int BestTop=n+1;
	int x;
	for(int i=1;i<=k;i++)
		if(!H[i].IsEmpty()){
			x=H[i].Top();
			if(c<x&&x<BestTop){
				BestTop=x;
				BestTrack=i;}
		}
		else
			if(!BestTrack) BestTrack=i;
	if(!BestTrack) return false;
	H[BestTrack].Add(c);
	cout<<"move car"<<c<<"from input""to holding track"<<BestTrack<<endl;
	if(c<minH){minH=c;minS=BestTrack;}
	return true;
}