yuesefu.cpp

用双链表实现的踢人问题

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

class OutOfBound{};

template<class T>
class Double;
template<class T>
class Iterator;

template<class T>
class DNode
{
	friend class Double< T >;
	friend class Iterator<T>;
private:
	T data;
	DNode<T> *left, *right;
};

template<class T>
class Iterator
{
public:
	T* Init(const Double<T>& c)
	{
		location=c.header->right;
		PIsHeader=c.header;		
		if(location!=c.header)
			return &location->data;
		return 0;
	}
	
	T* Next()
	{
		if(location==PIsHeader)
			location=location->right;
		location=location->right;		
		if(location==PIsHeader)
			location=location->right;
		return &location->data;
		
	}
private:
	DNode<T> *location;
	DNode<T> *PIsHeader;
};



template<class T>
class Double
{
	friend Iterator<T>;
public:
	Double();
	~Double();
	bool Empty() const{return n==0;}
	int Length() const {return n;}
	bool Retrieve(int k,T&x)const;
	int Locate(const T&x)const;
	
	void Clear()
	{
		DNode<T> *current;
		DNode<T> *next;
		current=header->right;
		while(!Empty())
		{
			next=current->right;
			delete current;
			n--;
			current=next;
		}
	}
	
	Double<T>& Insert(int k,const T&x);
	Double<T>& Delete(int k,  T&x);
	void PrintList () const;
	
private:
	int n;
	DNode<T> *header;
};

template<class T>
Double<T>::Double()
{
	DNode<T> *y=new DNode<T>;
	y->left=y;
	y->right=y;
	header=y;
	n=0;
}

template<class T>
Double<T>::~Double()
{
	DNode<T> *current;
	DNode<T> *next;
    current=header->right;
	while(!Empty())
	{
		next=current->right;
		delete current;
		n--;
		current=next;
	}
	delete header;
}

template<class T>
bool Double<T>::Retrieve(int k,T& x)const
{
	if(k<1 || k>n) return false;
	DNode<T> *current=header->right;
	int index =1;
	while(index<k)
	{
		current=current->right;
		index++;
	}
	x=current->data;
	return true;
}

template<class T>
int Double<T>::Locate(const T& x)const
{
	DNode<T> *current=header->right;
	int index =1;
	header->data=x;
	while(current->data!=x)
	{
		current=current->right;
		index++;
	}
	
	return ((current==header)?0:index);
}

template<class T>
Double<T>& Double<T>::Insert(int k,const T& x)
{
	if(k<0 || k>n) throw OutOfBound();
	DNode<T>* p=header->right;
	for(int index=1;index<k;index++)
		p=p->right;
	DNode<T> *y=new DNode<T>;
	y->data=x;
	y->left=p;
	y->right=p->right;
	p->right->left=y;
	p->right=y;
	n++;
	return * this;
	
}

template<class T>
Double<T>& Double<T>::Delete(int k, T& x)
{
	if(k<1 || k>n) throw OutOfBound();
	DNode<T>* q=header->right;
	for(int index=1;index<k;index++)
		q=q->right;
	q->left->right=q->right;
	q->right->left=q->left;
	x=q->data;
	delete q;
	n--;
	return * this;
	
}

template<class T>
void Double<T>::PrintList () const
{
	DNode<T> *current;
	for(current=header->right;current!=header;current=current->right)
		cout<<current->data<<" ";
}

int josephus(int n, int j)
{
	int N, MM;
	int A[10];
	string B[10];
	
	fstream in("in.txt");
	if (!in)
		return 1;   //结束程序执行
	
	while (!in.eof())
	{
		in >> N;
		in >> MM;
		for(int i=0;i<MM;i++)
		{
			in>>A[i];
		}
		for(int jj=0;jj<=N;jj++)
		{
			in>>B[jj];
		}
	}
	in.close();
		  int flag=1;
		  int fflag=1;
		  int m=1;
		  int M;
		  while(flag)
		  {
			  flag=0;
			  fflag=1;
			  Double<int> y;
			  for(int iii=0;iii<n;iii++)
				  y.Insert(iii,iii+1);
			  Iterator<int> p;
			  int *q=p.Init(y);
			  int *qVirtual=NULL;
			  for(int i=1;i<=n-j;i++)
			  {
				  if(m==1)
				  {
					  int*temp;
					  q=p.Init(y);
					  temp=p.Next();
					  for(int ii=0;ii<j;ii++)
					  {
						  if(*q==A[ii])
						  {
							  flag=1;
							  fflag=0;
							  y.Clear();
							  m=m+1;
							  break;
						  }
					  }
					  if(!fflag)
						  break;
					  
					  int x;
					  y.Delete(y.Locate(*q),x);
					  int *q;
					  q=temp;
					  qVirtual=temp;
					  M=1;
				  }
				  else
				  {
					  for (int h=1;h<=m-1;h++)
					  {
						  q=p.Next();
					  }
					  int*temp;
					  temp=p.Next();
					  for(int Ii=0;Ii<j;Ii++)
					  {
						  if(*q==A[Ii])
						  {
							  flag=1;
							  fflag=0;
							  y.Clear();
							  m=m+1;
							  break;
						  }
					  }
					  if(!fflag)
						  break;
					  
					  int x;
					  
					  y.Delete(y.Locate(*q),x);
					  
					  int *q;
					  q=temp;
					  qVirtual=temp;
					  M=m;
				  }
			  }
		  }
		  return M;
}

int Jjosephus(int n, int m)
{
	int N, MM;
	int A[10];
	string B[10];
	fstream in("in.txt");
	if (!in)
		return 1 ;   //结束程序执行
	
	while (!in.eof())
	{
		in >> N;
		in >> MM;
		for(int ii=0;ii<MM;ii++)
		{
			in>>A[ii];
		}
		for(int j=0;j<=N;j++)
		{
			in>>B[j];
		}
	}
	in.close();
	Double<int> y;
    for(int iiii=0;iiii<n;iiii++)
		y.Insert(iiii,iiii+1);
	Iterator<int> p;
	int *q=p.Init(y);
	int *qVirtual=NULL;
	for(int i=1;i<=n-MM;i++)
	{
		if(m==1)
		{
			int*temp;
			q=p.Init(y);
			temp=p.Next();
			//------------------------追加文件
			ofstream out("out.txt",ios::out|ios::app);
			
			out<<B[*q-1]<<endl;
			out.close();
            //追加问阿金--------------------------------
			int x;
			y.Delete(y.Locate(*q),x);
			int *q;
			q=temp;
			qVirtual=temp;
		}
		else
		{
			for (int j=1;j<=m-1;j++)
			{
				q=p.Next();
			}
			int*temp;
			temp=p.Next();
			//------------------------追加文件
			ofstream out("out.txt",ios::out|ios::app);
			
			out<<B[*q-1]<<endl;
			out.close();
            //追加问阿金--------------------------------
			
			int x;
			y.Delete(y.Locate(*q),x);
			int *q;
			q=temp;
			qVirtual=temp;
		}
	}
	return 0;
}
void main()
{
	Double<int> y;
	int N, J;
	int A[10];
	string B[20];
	
	fstream in("in.txt");
	if (!in)
		return ;   //结束程序执行
	
	while (!in.eof())
	{
		in >> N;
		in >> J;
		for(int i=0;i<J;i++)
		{
			in>>A[i];
		}
		for(int j=0;j<=N;j++)
		{
			in>>B[j];
		}
	}
	in.close();
	
	ofstream out("out.txt"); //写文件打开
	if(!out) {  //if(!out)等价于：if(!out.is_open())
		cout << "Cannot open file.\n"; 
		return ; 
	} 
	   out<<josephus(N,J)<<endl;
	   out.close();
	   Jjosephus(N,josephus(N,J));
}