railqkk.cpp

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

#include "iostream.h"
#include "iomanip.h"
#include "fstream.h"
class node
{
public:
	int data;
	node *next;
};
class qnode 
{
private:
	node * head;
	int length;
public:
	qnode();
	~qnode();
	node * gethead(){return head;};
	node *gettail();
	int getlength(){return length;};
	void input(int k);
	void output();
	void printlist();
};
qnode::qnode()
{head=NULL;length=0;}
qnode::~qnode()
{
	node *temp=head;
	while(temp)
	{
		head=head->next;
		delete(temp);
		temp=head;
	}
	delete(head);
}
void qnode::input(int k)
{
	node *newp;
	newp=new node;
	newp->data=k;
	newp->next=head;
	head=newp;
	length++;
}
void qnode::output()
{
	node *p1,*p2;
	p1=head;
	p2=NULL;
	if(p1->next==NULL)
	{
		head=NULL;
		length--;
		return;
	}
	while(p1->next)
	{
		p2=p1;
		p1=p1->next;
	}
	p2->next=NULL;
	delete(p1);
	length--;
}
node *qnode::gettail()
{
	node *p1=head,*p2=NULL;
	while(p1)
	{
		p2=p1;
		p1=p1->next;
	}
	return p2;
}	
int main()
{
	int m,n,i,j,outp=1,yes=1,k=0,index=0,a[1000],limit[500],rec[10000][2];qnode line[1000];
	ifstream input("input.txt");
	ofstream output("output.txt"); 
	input>>m>>n;
	for(i=0;i<m;i++)
		input>>a[i];
	for(i=0;i<n-1;i++)
		input>>limit[i];
	while(outp<m+1)
	{
		if(a[k]==outp){rec[index][0]=0,rec[index][1]=n,index++;outp++;}
		else
		{
			for(j=0;j<n-1;j++)
			{
				if(((line[j].gethead()==NULL)||(a[k]>line[j].gethead()->data))&&(line[j].getlength()<limit[j]))
				{
					line[j].input(a[k]);
					rec[index][0]=0,rec[index][1]=j+1,index++;
					break;
				}
			}
			if(j==n-1)
			{
				output<<"No Solution!";
				return 0;
			}
		}
		while(1)
		{
			yes=0;
			for(j=0;j<n-1;j++)
				if((line[j].gethead()!=NULL)&&(line[j].gettail()->data==outp))
				{
					rec[index][0]=j+1,rec[index][1]=n,index++;
					outp++;
					line[j].output();
					yes=1;
				}
			if(yes==0)break;
		}
		if(k<m)k++;
	}
	for(i=0;i<index;i++)
		output<<rec[i][0]<<"->"<<rec[i][1]<<endl;
	return 0;
}