好嵌套箱501box.cpp

设计一个算法

#include<iostream>
#include<fstream>
#include<time.h>
using namespace std;
class OutOfBounds{};
class BadInput{};
//注意安排各个类的顺序，顺序不同，会有错误产生
class Node
{
	friend class List;
	friend class Iterator;
	friend class LinkedBase;
	int data;
	Node *next;
};

//表
class List
{
	friend class LinkedBase;	
	friend class Iterator;	
public:
	List(){first=0;}
	~List();
	bool Empty() const
	{
		return first==0;
	}
	int Length() const;
	bool Retrieve(int k,int& x) const;//返回表中第k个元素x
	int Locate(const int& x) const;//返回表中元素x的位置
	List&Insert(int k,const int& x);//在表的位置k出插入元素x
	List&Delete(int& x);//从表中删除位置k处的元素x
	void Output(ostream& out) const;
	Node *first;//指向第一个结点
};
List::~List()
{
	Node *next;
	while(first)
	{
		next=first->next;
		delete first;
		first=next;
	}
}
int List::Length() const
{
	Node*current=first;
	int len=0;
	while(current)
	{
		len++;
		current=current->next;
	}
	return len;
}
bool List::Retrieve(int k,int& x) const
{
	if(k<1)
		return false;
	Node *current=first;
	int index=1;
	while(index<k&&current)
	{
		current=current->next;
		index++;
	}
	if(current)
	{
		x=current->data;
		return true;
	}
	return false;
}
int List::Locate(const int& x)const
{
	Node *current=first;
	int index=1;
	while(current&&current->data!=x)
	{
		current=current->next;
		index++;
	}
	if(current)
		return index;
	return 0;
}
List&List::Insert(int k,const int& x)
{
	if(k<0) throw OutOfBounds();
	int index;
	Node *p=first;
   //找插入位置
	for(index=1;index<k&&p;index++)
		p=p->next;
	if(k>0&&!p) throw OutOfBounds();
	Node *y=new Node;       //给指针y分配空间
	y->data=x;
	if(k) //在位置p处插入
	{
		y->next=p->next;
		p->next=y;
	}
	else//在表首插入
	{
		y->next=first;
		first=y;
	}
	return *this;
}
List&List::Delete(int& x)//删去值为x的结点
{
	Node *current=first,
		*trail=0;//current的下一个结点
	//搜索值为x的元素
	while(current&&current->data!=x)///与书本有所不同
	{
		trail=current;
		current=current->next;
	}
	if(!current) 
		throw OutOfBounds();//找不到值为x的元素
	//在结点current处找到值为x的元素
	x=current->data;
	//将结点current从表中删除
	if(trail)
		trail->next=current->next;
	else
		first=current->next;//current是表首结点
	delete current;//释放结点空间
	return *this;
}
//搜索游标的定义
class Iterator
{
	friend class List;
	friend class LinkedBase;
	friend class LinkedDigraph;
	friend class Node;
public:
	int *Init(const List& c)
	{
		location=c.first;
		if(location) return &location->data;   //此处的&指的是取地址
		return 0;
	}
	int *Next()
	{
		if(!location) return 0;
		location=location->next;
		if(location) return &location->data;
		return 0;
	}
	Node *location;
};

//邻接表基类LinkedBase,抽取用邻接表实现各类图的共享特征
class LinkedBase
{
	friend class List;
	friend class Node;	
	friend class Iterator;
	//这里要补上需要用到本类私有成员的友元
public:	

	LinkedBase(int Vertices)
	{
		n=Vertices;
		e=0;
		h=new List[n+1];
	
	}
	~LinkedBase()
	{
		delete []h;	
	
	}
	void InitializePos()
	{
		pos=new Iterator[n+1];
	}
	void DeactivatePos()
	{
		delete []pos;
	}

	int Edges()const
	{
		return e;
	}
	int Vertices()const
	{
		return n;
	}
	int OutDegree(int i)const
	{
		if(i<1||i>n) throw OutOfBounds();
		return h[i].Length();///////////////？？？？？？？？？？？？？？？？
	}
	int n;//顶点数
	int e;//边数
	List *h;//邻接表数组
	Iterator *pos;//当前搜索位置数组
};
//用邻接表实现有向图
class LinkedDigraph:public LinkedBase
{
	friend class Iterator;
	friend class List;
	friend class Node;
public:
	LinkedDigraph(int Vertices)
		:LinkedBase(Vertices) {}
	bool Exist(int i,int j)const;
	LinkedDigraph&Add(int i,int j);
	LinkedDigraph&Delete(int i,int j);
	int InDegree(int i)const;
	int Begin(int i);
	int NextVertex(int i);
protected:
	LinkedDigraph&AddNoCheck(int i,int j);//每次插入，都插在在k=0这个位置
};
bool LinkedDigraph::Exist(int i,int j)const
{
	if(i<1||i>n)
		throw OutOfBounds();
	return (h[i].Locate(j))?true:false;
}
LinkedDigraph&LinkedDigraph::Add(int i,int j)
{
	if(i<1||j<1||i>n||j>n||i==j||Exist(i,j))
		throw BadInput();
	return AddNoCheck(i,j);
}
LinkedDigraph&LinkedDigraph::AddNoCheck(int i,int j)
{
	h[i].Insert(0,j);//在顶点i的邻接表表首插入顶点j
	e++;
	return *this;
}
LinkedDigraph&LinkedDigraph::Delete(int i,int j)
{
	if(i<1||i>n)
		throw OutOfBounds();
	h[i].Delete(j);
	e--;
	return *this;
}
int LinkedDigraph::InDegree(int i)const
{
	if(i<1||i>n) 
		throw OutOfBounds();
	//统计顶点处的入边数
	int sum=0;
	for(int j=1;j<=n;j++)
		if(h[j].Locate(i)) sum++;
	return sum;
}
int LinkedDigraph::Begin(int i)
{
	//返回第一个和i邻接的顶点
	if(i<1||i>n) throw OutOfBounds();
	int *x=pos[i].Init(h[i]);
	return (x)? *x:0;
}
int LinkedDigraph::NextVertex(int i)
{
	//返回顶点i的下一个邻接顶点
	if(i<1||i>n)
		throw OutOfBounds();
	int *x=pos[i].Next();
	return (x)? *x:0;
}

///////选择和排序
int Random(int a,int b) 
{
	srand(time(NULL));
	return (a+rand()%(b-a+1)); 
} 
int jdz(int a,int b)//返回两数差的绝对值
{
	int c;
	c=a-b;
	if(c<0)
		return c*(-1);
	else 
		return c;
}
inline void Swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}
int Partition(int a[],int p,int r)
{
	int i=p;
	int j=r+1;
	int x=a[p];
	//将>=x的元素交换到右边区域
	//将<=x的元素交换到左边区域
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j) break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

int RandomizedPartition(int a[],int p,int r)//产生随机化的划分算法
{
	int i;
	i=Random(p,r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
void RandomizedQuickSort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=RandomizedPartition(a,p,r);
		RandomizedQuickSort(a,p,q-1);//对左半段排序
        RandomizedQuickSort(a,q+1,r);//对右半段排序
	}
}

int Max(int *a,int n)//返回最大值的下标
{//确定a[0:n-1]中最大元素的下标
	int i,pos=0;
	for(i=1;i<n;i++)
	{
		if(a[pos]<a[i])
			pos=i;
	}
	return pos;
}
int compare(int aa[],int n,int bb[],int m)//m<n,比较数组aa是否有包含数组bb的全部元素
//如果有，返回1，没有，返回0
{
	int i,j;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(bb[i]==aa[j])
				break;
			else 
				continue;
		}
		if(j<=n-1)
			continue;
		else 
			return 0;
	}
	return 1;
}
	
int n,d,i,j,k,max,p,kk,r,y,q,c;
int temp[10000],b[8000][8000];
int tp[10000];
int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");
	while(in>>n>>d)
	{
		int **a=new int *[n];//定义二维数组，用于存放输入的值
		for(i=1;i<=n;i++)
		{
			a[i]=new int[d];
		}
		LinkedDigraph S(n);/////////////////图
		int *lengthb=new int[n];
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=d;j++)
				in>>a[i][j];
		}//输入

		for(i=1;i<=n;i++)
			RandomizedQuickSort(a[i],1,d);//排序
		for(i=1;i<=n;i++)
		{
			r=1;//r应该从1开始，因为数组b[i]的头一个元素已经固定了，就是i本身
			b[i-1][0]=i;///////////////注意，因为数组b的下标从0开始，所以要记得i-1
			for(j=1;j<=n;j++)
			{
				if(i==j) 
					continue;
				for(k=1;k<=d;k++)
				{
					if(a[i][k]<a[j][k])//比较
						continue;
					else  
						break;
				}
				if(k==d+1)
				{
					S.Add(j,i);//在图中加入一条有向边,这条有向边是由大箱指向小箱
					b[i-1][r++]=j;////注意，因为数组b的下标从0开始，所以要记得i-1
				}
			}
			lengthb[i-1]=r;//因为数组lengthb的下标从0开始，所以要记得i-1
		}
		for(i=1;i<=n;i++)
		{
			p=S.InDegree(i);//入度最多的就是最小的箱子
			temp[i-1]=p;//数组temp的下标从0开始
		}
		max=Max(temp,n);//寻找最小的箱子，但是最小箱子的入度是最大的(Max函数返回的是下标)
		kk=max;
		tp[0]=max+1;//把最小的箱子的下标记录下来
		temp[max]=-1;
		//////////////////////////////////
		j=1;
		for(i=1;i<n;)
		{
			max=Max(temp,n);//寻找次最小的箱子(Max函数返回的是下标)
			y=compare(b[kk],lengthb[kk],b[max],lengthb[max]);//前面的数组个数比后面多
			if(temp[max]==0)
			{
				for(c=0;c<lengthb[kk];c++)
				{
					if(max+1==b[kk][c])//如果找到的箱子的入度为0,则应该判断它是否是最大的箱子
					{
						tp[j++]=max+1;
						goto lop1;
					}
					else 
						continue;
				}		
			}
			if(y==0)
			{
				temp[max]=-1;
				goto lop2;//注意:kk值仍然不变
			}
			else if(y==1)
			{	
				kk=max;
				tp[j++]=max+1;
				temp[max]=-1;
			}
lop2:i++;
		}
lop1:q=j;//记录tp中的元素个数
		out<<q<<' '<<endl;
		for(i=0;i<q;i++)
			out<<tp[i]<<' ';
		out<<endl;		
	}

	return 1;
	
}