linlist.h

海盗船问题 循环数数

template<class T>
 class Linlist;
template<class T> 
 class Listnode           //结点类
{	friend class Linlist<T>;
  	
private:
		Listnode<T> *next;
		T data;
	public:
	
		Listnode(Listnode<T> *ptr=NULL)
		{  next=ptr;}
		Listnode(const T& item,Listnode<T> *ptr=NULL)
		{  data=item;next=ptr;}
		~Listnode()
		{}
};
  
  template<class T>
class Linlist
 {
	   private:
		   Listnode<T> *head;
		   int size;
		   Listnode<T> *Index(int i);    //定位
	   public:
		   Linlist(void);
		   ~Linlist(void);

		   int Size(void);
		   void Insert(const T& item,int i);     //插入 
           T Delete (int i);                        //删除 
		   T Getdata(int i);            //取数据元素
		   
		   T Haidao(int m );            //海盗问题
  };

 template<class T>
	 Linlist<T>::Linlist(void)                    //构造函数 
 {
	 head=new Listnode<T>();
	 head->next=head;
	 size=0;
 }
  
 template<class T>
	 Linlist<T>::~Linlist(void)            //析构函数
 {
	  Listnode<T> *p,*q;
      p=head;
	  while(p->next!=head)
	  {
		   q=p;
           p=p->next;
		   delete q;
	  }
      delete p;
	  size=0;

 }
  template<class T>
	  Listnode<T> *Linlist<T>::Index(int i)          //定位 
  {
	   if(i<-1)
	   {  
		   cout<<"i越界"<<endl;
		   exit(0);
	   }
	   if(i==-1) return head;
     Listnode<T> *p=head->next;
	 for(int j=0;j<i;j++)
	 {
		 p=p->next;
		 if(p==head) p=p->next;
	 }
	 return p;
}
 
 template<class T>
	  void Linlist<T>::Insert(const T& item,int i)      //插入 
  {
		if(i<0)
		{
			cout<<"i越界出错"<<endl;
			exit(0);
		}
	  	Listnode<T> *p=Index(i-1);
	    Listnode<T> *q=new Listnode<T>(item,p->next);
		p->next=q;
		size++;
 }
template<class T>
T Linlist<T>::Delete (int i)      //删除
{
		if(i<0)
		{
			cout<<"i越界出错"<<endl;
			exit(0);
		}
	Listnode<T> *p=Index(i-1);
    Listnode<T> *q=p->next;
	p->next=p->next->next;
	T x=q->data;
	delete q;
	size--;
	return x;
}
 template<class T>
	 int Linlist<T>::Size(void)         
 {
	 return size;
 }

 template<class T>
	 T Linlist<T>::Getdata(int i)     //取数据元素 
 {
	 	if(i<0||i>size-1)
		{
			cout<<"i越界出错"<<endl;
			exit(0);
		}
      Listnode<T> *p=Index(i);
	  return p->data;
 }

 
 template<class T>
  T Linlist<T>::Haidao(int m)     //海盗问题 
  {  
	 Listnode<T> *p= head->next;
     Listnode<T> *q;
	  
	 while(size!=1)
	 {
		 for(int i=1;i<m-1;i++)
			 //循环m-1次，p指向应删除结点的前驱结点；
			  {
	   	         p=p->next;    
		         if(p==head) p=p->next;
			  }
        
       q=p->next;      // q指向应删除结点
	   if(q==head)
			{q=q->next;head->next=head->next->next;}
        else {p->next=q->next;}
	   T x=q->data;   
	   cout<<"   "<<x;    //输出删除结点的编号  
	   delete  q;
	    size--;
	    p=p->next;
	   if(p==head)p=p->next;
	 }
	return p->data; 
 }