railkk.cpp

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

#include<iostream>
#include<fstream>
#define M 8000
using namespace std;
class Node
{
	friend class Stack ;
	private:
		int data;
		Node *next;
}; 
class Stack
{  
public:
    Stack(){top = 0;}
	~Stack();
	bool Empty() const{ return top ==0;}	 
	int Top();
	Stack& Push(int x);
	Stack& Pop();
private:
	Node *top;
}; 
Stack::~Stack ()
{
	Node * next;
	while(top)
	{
		next=top-> next;
		delete top;
		top=next;
	}
} 
int Stack::Top()
{
	if(Empty()) return 0;
	return top->data ;
}
Stack&Stack::Push (int x)
{
	Node *p=new Node;
	p->data=x;
	p->next=top;
	top=p;
	return * this;
} 
Stack &Stack::Pop ()
{
	int x;
    Node *p=top;
	x=top->data;	 
	top=top->next;
	delete p;
	return * this;
}
int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"The input.txt is not existed!"<<endl;
		exit(1);
	}
	ofstream out("output.txt");
	Stack stack[M];
	int entrance[M],exit[M],n,k,Nowout=1,s=0,i=0,j,x,num=1;
	in>>n>>k;
	while(s++<n)
	{
		in>>x;		
        if(x==Nowout)
		{
			entrance[i]=0;
			exit[i++]=k+1;	 
			Nowout++;
			for(j=1;j<num&&Nowout<=n;j++)
			{
				if(stack[j].Top()==Nowout)
				{
					entrance[i]=j;
					exit[i++]=k+1;
					stack[j].Pop();
					if(!stack[j].Top ())
						stack[j].Push(n+1);
					Nowout++;					 
					j=0;
				} 
			} 
		}
		else
		{			
			for(j=1;j<num;j++)
			{					 
				if(x<stack[j].Top ())
				{
					stack[j].Push(x);                   
					entrance[i]=0;
					exit[i++]=j; 
					break;
				}
			}
			if(j==num)
			{
				stack[num++].Push(x);
                entrance[i]=0;
			    exit[i++]=j;			 
			}			
		}		 
	}
	while(Nowout<=n)
	{
		for(j=1;j<num;j++)
			{			 
				if(stack[j].Top()==Nowout)
				{
					entrance[i]=j;
					exit[i++]=k+1;
					stack[j].Pop();
					Nowout++;
					j=1;					
				} 
			}
	}
     if(num>k+1)
      	out<<"No solution!"<<endl;
     else
      	for(s=0;s<i;s++)
       	   	out<<entrance[s]<<"->"<<exit[s]<<endl;
  	return 0;
}