rail.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream>
#include<fstream>
using namespace std;


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


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


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


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


template<class T>
T LinkedStack<T>::Top() const
{// 返回栈顶元素
return top->data;
}


template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{// 添加元素x
Node<T> *p = new Node<T>;
p->data = x;
p->link = top;
top = p;
return *this;
}


template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{// 删除栈顶元素，并将其送入x
x = top->data;
Node<T> *p = top;
top = top->link;
delete p;
return *this;
}

void Output(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);
bool Railroad(int p[], int n, int k);


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
if(minS!=-1)
H[minS].Delete(c) ;
std::ofstream outfile("output.txt",ios_base::app);
outfile<< minS <<"->"<<k+1 <<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)
{// 在一个缓冲铁轨中放入车厢c
// 如果没有可用的缓冲铁轨，则返回false
// 如果空间不足，则引发异常N o M e m
// 否则返回true
// 为车厢c寻找最优的缓冲铁轨
// 初始化
int BestTrack=0,BestTop=n+1,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) ;
std::ofstream outfile("output.txt",ios_base::app);
outfile <<"0"<<"->"<< BestTrack << endl;
//必要时修改minH 和minS
if (c < minH) {minH = c; minS = BestTrack ; }
return true;
}


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=-1; //minH号车厢对应的缓冲铁轨
//车厢重排
for (int i = 0; i <n; i++)
if (p[i] == NowOut) {// 直接输出t
std::ofstream outfile("output.txt",ios_base::app);
outfile <<"0->"<<k+1<< endl;
NowOut++ ;
//从缓冲铁轨中输出
while (minH == NowOut) {
Output(minH, minS, H, k, n);
NowOut++ ;
}
}
else {// 将p[i] 送入某个缓冲铁轨
if (!Hold(p[i], minH, minS, H, k, n))
return false;}
return true;
}


void main ()

{	
	int carriage,rail;
	ifstream infile("input.txt");
	infile>>carriage>>rail;
	int *p=new int [carriage];
	for(int i=0;i<carriage;++i)
		infile>>p[i];
	infile.close();
	ofstream outfile("output.txt");
    if(!Railroad(p, carriage,rail)){
    ofstream outfile("output.txt");
	outfile<<"No Solution!"<<endl;}
    outfile.close();
}