railq.cpp

设计一个算法

#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() const;
		T first() const;
		T last()const;
		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()const
{
	Node<T> *p;
    return true;
}
template<class T>
T Queue<T>::first() const
{
	return front->data;
}
template<class T>
T Queue<T>::last()const
{
	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)
{
	x=front->data;
	Node<T> *p=front;
	front=front->next;
	delete p;
	return * this;
}
main()
{   
	int n,k,i,*a,j,z,x=1,m=1,b,temp;
	ifstream infile("input.txt");
    if(!infile)
	{  
	cout<<"Error opening file for reading\n";
    return 0;
	}
	infile>>n>>k;
	a=new int[n];
	for(i=0;i<n;i++)
	infile>>a[i];
	infile.close();    
	Queue<int> *s=new Queue<int> [k]; 
	ofstream outfile("output.txt");
    if(!outfile)
	{
	cout<<"Error opening file for writing\n";
	return 0;
	}
	for(j=0;j<n;j++)
	{
	if(a[j]==j+1)
	{
		s[k-1].EnQueue(a[j]);
		outfile<<"0->"<<k<<endl;
	    m++;
	}
	else {
		s[0].EnQueue(a[j]);
		outfile<<"0->1"<<endl;
		break;
	}
	}
	for(i=j+1;i<n;i++)
	{      	  
		if(a[i]==m)
		{
        s[k-1].EnQueue(a[i]);
		outfile<<"0->"<<k<<endl;
		m++;
		b=0;
		while(b<x)
		{
			if(!s[b].Empty()&&s[b].first()==m)
			{
				s[b].DeQueue(z);
			    s[k-1].EnQueue(z);
				outfile<<b+1<<"->"<<k<<endl;
				m++;
				b=-1;
			}
			b++;
			if(m==n+1) return 0;
		}
		}
		else{
			for(temp=0,b=0;b<x;b++)
			{
				if(a[i]>s[b].last())  
				{
				s[b].EnQueue(a[i]);
				outfile<<"0->"<<b+1<<endl;
				temp=1;
				break;
				}
			}
		    if(temp==0){
			        if(x<k-1)
					{
			        s[x].EnQueue(a[i]);
					outfile<<"0->"<<x+1<<endl;
					}
			        else  
					{ 
					 outfile.close();
					 ofstream outfile("output.txt");
                     if(!outfile)
					 {
                       cout<<"Error opening file for writing\n";
	                   return 0;
					 }
			         outfile<<"No Solution!"<<endl; 
					 outfile.close();
			         return 0;
					}
			        x++;
			}
			}

		}
	outfile.close();  
    return 0;
}