llist1.h

约瑟夫问题有原始的约瑟夫和发展了的约瑟夫两种。 原始的约瑟夫的描述： 古代某法官要判决N个犯人的死刑

#ifndef LLIST1_H
#define LLIST1_H
#include"list1.h"
template<class Elem>
class LList{
private:
   Link<Elem>* head;
   Link<Elem>* tail;
   Link<Elem>* fence;
   int leftcnt;
   int rightcnt;
   Elem deleteElement;
   void init(const Elem item,int num)
   {
     fence=head=tail=new Link<Elem>(item,num);
     leftcnt=rightcnt=0;
   }
   void removeall()
   {
     while(head!=NULL)
     {
       fence=head;
       head=head->next;
       delete fence;
     }
   }
public:
   LList(const Elem item,int num){init(item,num);}
   ~LList(){removeall();}
   bool append(const Elem&,int);
   bool remove(Elem&);
   void setStart()
   {fence=head;rightcnt+=leftcnt;leftcnt=0;}
   void setEnd()
   {fence=tail;leftcnt+=rightcnt;rightcnt=0;}
   void prev();
   void next()
   {
     if(fence!=tail)
       {fence=fence->next;rightcnt--;leftcnt++;}
   }
   int leftLength() const {return leftcnt;}
   int rightLength() const {return rightcnt;}
   bool setPos(int pos);
   bool getValue(Elem& it) const
   { if(rightLength()==0) return false;
     it=fence->next->element;
     return true;
   }
   void print() const;
   int yesefu(int);
   Elem& getElement();
};

template<class Elem>
bool LList<Elem>::append(const Elem& item,int num)
{
  tail=tail->next=new Link<Elem>(item,NULL,num);
  rightcnt++;
  return true;
}

template<class Elem>
bool LList<Elem>::remove(Elem& it)
{
   if(fence->next==NULL) return false;
     it=fence->next->element;
      Link<Elem>* ltemp=fence->next;
      fence->next=ltemp->next;
      if(tail==ltemp) tail=fence;
      delete ltemp;
      rightcnt--;
      return true;
}
template<class Elem>
void LList<Elem>::prev()
{
  Link<Elem>*temp=head;
  if(fence==head) return;
  while(temp->next!=fence) temp=temp->next;
  fence=temp;
  leftcnt--;rightcnt++;
}
template<class Elem>
bool LList<Elem>::setPos(int pos)
{
   if((pos<0)||(pos>rightcnt+leftcnt))return false;
   fence=head;
   for(int i=0;i<pos;i++)fence=fence->next;
   return true;
}
template<class Elem>
void LList<Elem>::print() const
{
  Link<Elem>* temp=head->next;
  cout<<"<";
  while(temp!=NULL)
  {
     cout<<temp->element<<"  ";
     temp=temp->next;
  }
  cout<<">\n";
}
template<class Elem>
int LList<Elem>::yesefu(int n)
{
   int numval=9999999 ;
   if(n-1==0)
   numval=fence->next->number;
   while(n-1!=0)
   {  if(head==tail) break;
      if(fence==tail)
      fence=head;
      fence=fence->next;
      if(head==tail) break;
      if(fence==tail)
      fence=head;
      n--;
      numval=fence->next->number;
   }

   remove(n);
   deleteElement=n;
   return numval;
}
template<class Elem>
Elem& LList<Elem>::getElement()
{
  return deleteElement;
}
# endif