railq.cpp

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

#include <iostream.h>
#include <fstream.h>
            
template <class T>   //队列结点类型
class Node 
{
	public:
		T data;
		Node<T> *next;
};

template <class T>   //用指针实现队列模板类
class Queue
{
	public:
		Queue()
		{
			front=rear=0;
		};
		~Queue();
		bool Empty() const
		{
			return ((front)? false:true);
		};
		bool Full();
		T First();
		T Last();
		Queue<T> & EnQueue(const T&x);
		Queue<T> & DeQueue(T & x);
	private:
		Node<T> * front;  //队首结点指针
		Node<T> * rear;   //队尾结点指针
};

template <class T>   //析构函数释放队列中的所有结点
Queue<T>::~Queue()
{
	Node<T> * next;
	while(front)
	{
		next=front->next;
		delete front;
		front=next;
	};
}

template <class T>   //检测队列空间是否已满
bool Queue<T>::Full() 
{
	Node<T> *p;
	try 
	{
		p=new Node<T>;
		delete p;
		return false;
	}
	catch (NoMem)
	{
		return true;
	}
}

template <class T>   //返回队首结点中的元素
T Queue<T>::First() 
{
	//if(Empty()) throw "error";
	return front->data;
}

template <class T>   //返回队尾中结点中的元素
T Queue<T>::Last() 
{
	//if(Empty()) throw "error";
	return rear->data;
}

template <class T>    //在队尾插新入结点
Queue<T> & Queue <T>::EnQueue(const T & x)
{
	//创建一个新的结点
	Node<T> * p=new Node<T>;
	p->data=x;
	p->next=0;
	//在队尾插入新结点
	if(front) rear ->next=p; //队首非空
	else front =p;   //空队列
	rear=p;
	return * this;
}

template<class T>    //删除队首结点
Queue<T> & Queue<T>::DeQueue(T & x)
{
	//if(Empty()) throw "error";
	//将队首元素存于x中
	x=front->data;
	//删除队首结点
	Node<T> *p=front;
	front=front->next;
	delete p;
	return * this;
}

void  main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n, k, i;
	in >> n>> k;
	int x;
	int TheTrack=1;
	int *a=new int[n];
	for(i=0; i<n; i++)
	{
		in>>a[i];
	};
    Queue<int> *hold=new Queue<int>[k-1];
	int flag=1;
    int *sign=new int[k-1];
	i=0;
	do
	{
		sign[i]=i+1;
		i++;
	}
	while(i<k-1);
	for(i=0;i<=n && (flag<=n);)
	{    
		if(a[i]==flag)
		{
			out<<"0->"<<k<<endl;
			i++;
			flag++;  
			continue;
		}
		else for(int j=0;j<k-1;j++)
		{
			if(!hold[j].Empty() && hold[j].First()==flag)
			{ 
				out<<sign[j]<<"->"<<k<<endl;
				hold[j].DeQueue(x);
				TheTrack=0;
			    flag++;  
				break;
			}
			else TheTrack=1;	
		}
	
	if(TheTrack==1)
	{             
		for(int t=0;i<n && t<k-1;t++)
		{ 
			if(hold[t].Empty()||a[i]>hold[t].Last())
			{
				hold[t].EnQueue(a[i]);
				out<<"0->"<<sign[t]<<endl;
				i++;
				break;
			}
		}
		if(t==k)
		{ 
			out<<"No Solution!"<<endl;
			break;
		}
	
	}
	}
}