//單循環(huán)鏈表的類定義cirlinklist.h
#define LEN 20
typedef int ElemType;
//單循環(huán)鏈表中結(jié)點的類型
typedef struct Lnode {
 ElemType data;   //值域
 Lnode* next;     //指針域
}LNode;
class cirlinklist
{private:
  LNode *head;//指向表頭的指針
  LNode *curr;//當(dāng)前結(jié)點指針
  int count;// 單循環(huán)鏈表的結(jié)點個數(shù)
 public:
//構(gòu)造函數(shù)
  cirlinklist();
//析構(gòu)函數(shù)
  ~cirlinklist(){delete head;}
//創(chuàng)建有序或無序的帶頭結(jié)點的單循環(huán)鏈表
  LNode *CreateCLinkL(int,int mark=0);
//清空單循環(huán)鏈表
  void ClearCList();
//求單循環(huán)鏈表長度
  int CListSize();
//檢查單循環(huán)鏈表是否為空
  bool CListEmpty();
//返回指向第pos個結(jié)點的指針
  LNode *Index(int pos);
//返回單循環(huán)鏈表中指定序號的結(jié)點值
  ElemType GetElem(int pos);
//遍歷單循環(huán)鏈表
  LNode *TraverseCList();
//當(dāng)前指針curr指向pos結(jié)點并返回curr
  LNode *Reset(int pos=0);
//當(dāng)前指針curr指向下一結(jié)點并返回
  LNode *Next();
// 判單循環(huán)鏈表當(dāng)前指針curr==head 否
  bool EndOCList();
//判單循環(huán)鏈表當(dāng)前指針curr->next是否到達表尾
  bool EndCList();
//刪除單循環(huán)鏈表當(dāng)前指針curr->next所指結(jié)點并返回其值
  ElemType DeleteNext();
//從單循環(huán)鏈表中查找元素
  bool FindCList(ElemType& item);
//更新單循環(huán)鏈表中的給定元素
  bool UpdateCList(const ElemType &item,ElemType &e);
//向鏈表中第pos個結(jié)點后插入域值為item的新結(jié)點
  void InsertCList(const ElemType& item,int pos);
//從鏈表中刪除第pos個結(jié)點并返回被刪結(jié)點的data
  ElemType DeleteCList(int pos);
};
//單循環(huán)鏈表的實現(xiàn)cirlinklist.cpp
#include<iostream.h>
#include<stdlib.h>
#include"cirlinklist.h"
//構(gòu)造函數(shù)
cirlinklist::cirlinklist()
{head=new LNode;
 curr=NULL;
 head->next=head;
 count=0;
}
//創(chuàng)建有序或無序的帶頭結(jié)點的單循環(huán)鏈表
LNode *cirlinklist::CreateCLinkL(int n,int mark)
{ElemType x,a[LEN];
 for(int i=0;i<n;i++) a[i]=random(150+i)%100;
 for(int i=0;i<n-1;i++)
  {int k=i;
   for(int j=i+1;j<n;j++)
    if(a[k]>a[j]) k=j;
   if(k!=i)
   {x=a[k];a[k]=a[i];a[i]=x;}}
 head=new LNode;
 head->next=curr=new LNode;
 for(int i=0;i<n;i++){
  if(mark==1) curr->data=a[i];//升序
  else
   if(mark==-1) curr->data=a[n-1-i];//降序
   else curr->data=rand()%100;//無序
  if(i<n-1){curr->next=new LNode;
   curr=curr->next;}
  count++;}
 curr->next=head;
 return head;
}
//清空單循環(huán)鏈表
void cirlinklist::ClearCList()
{LNode *cp,*np;
 cp=head->next;
 while(cp!=head)
 {np=cp->next;delete cp;cp=np;}
 head=NULL;
}
//求單循環(huán)鏈表長度
int cirlinklist::CListSize()
{LNode* p=head->next;
 int i=0;
 while(p!=head)
  {i++;p=p->next;}
 return i;
}
//檢查單循環(huán)鏈表是否為空
bool cirlinklist::CListEmpty()
{return head->next==head;}
//返回指向第pos個結(jié)點的指針
LNode *cirlinklist::Index(int pos)
{if(pos<1)
  {cerr<<"pos is out range!"<<endl;exit(1);}
 LNode* p=head->next;
 int i=0;
 while(p!=head)
  {i++;
   if(i==pos) break;
   p=p->next;}
 if(p!=head) return p;
 else {cerr<<"pos is out range!"<<endl;
  return NULL;}
}
//返回單循環(huán)鏈表中指定序號的結(jié)點值
ElemType cirlinklist::GetElem(int pos)
{if(pos<1)
 {cerr<<"pos is out range!"<<endl;exit(1);}
 LNode* p=head->next;
 int i=0;
 while(p!=head)
  {i++;
   if(i==pos) break;
   p=p->next;}
 if(p!=head) return p->data;
 else {cerr<<"pos is out range!"<<endl;
  return pos;}
}
//遍歷單循環(huán)鏈表
LNode *cirlinklist::TraverseCList()
{LNode *p=head->next;
 while(p!=head)
  {cout<<setw(4)<<p->data;
   p=p->next;}
 cout<<endl;
 return head;
}
//當(dāng)前指針curr指向pos結(jié)點并返回curr
LNode *cirlinklist::Reset(int pos)
{LNode* p=curr=head->next;
 int i=-1;
 while(p!=head)
  {i++;
   if(i==pos) break;
   p=p->next;curr=curr->next;}
 return curr;
}
//當(dāng)前指針curr指向下一結(jié)點并返回
LNode *cirlinklist::Next()
{curr=curr->next;
 return curr; 
}
// 判單循環(huán)鏈表當(dāng)前指針curr==head 否
bool cirlinklist::EndOCList()
{return curr==head;}
//判單循環(huán)鏈表當(dāng)前指針curr->next是否到達表尾
bool cirlinklist::EndCList()
{return curr->next==head;}
//刪除單循環(huán)鏈表當(dāng)前指針curr->next所指結(jié)點并返回其值
ElemType cirlinklist::DeleteNext()
{LNode *p=curr->next;
 curr->next=p->next;
 ElemType data=p->data;
 delete p;
 count--;
 return data;
}
//從單循環(huán)鏈表中查找元素
bool cirlinklist::FindCList(ElemType& item)
{LNode* p=head->next;
 while(p!=head)
  if(p->data==item)
   {item=p->data;return true;}
  else p=p->next;
 return false;
}
//更新單循環(huán)鏈表中的給定元素
bool cirlinklist::UpdateCList(const ElemType &item,ElemType &e)
{LNode* p=head->next;
 while(p!=head)  //查找元素
  if(p->data==item) break;
  else p=p->next;
 if(p==head) return false;
 else {  //更新元素
  p->data=e;return true;}
}
//向鏈表中第pos個結(jié)點后插入域值為item的新結(jié)點
void cirlinklist::InsertCList(const ElemType& item,int pos)
{LNode *newP=new LNode;
 newP->data=item;
 LNode* p=head->next;
 int i=0;
 while(p!=head)
  {i++;
   if(i==pos) break;
   p=p->next;}
 newP->next=p->next;
 p->next=newP;count++;
}
//從鏈表中刪除第pos個結(jié)點并返回被刪結(jié)點的data
ElemType cirlinklist::DeleteCList(int pos)
{if(pos<1)
  {cerr<<"pos is out range!"<<endl;exit(1);}
 LNode *p=head->next;
 curr=head;
 ElemType data;
 int i=0;
 while(p!=head)
  {i++;
   if(i==pos) break;
   p=p->next;curr=curr->next;}
 if(p!=head)
  {data=p->data;curr->next=p->next;
   delete []p;count--;return data;}
 else return pos;  
}
//單循環(huán)鏈表的測試與應(yīng)用cirlinklistm.cpp
#include<iomanip.h>
#include "cirlinklist.cpp"
void main()
{cout<<"cirlinklistm.cpp運行結(jié)果:\n";
 int m,i,n=10,x,it;
 bool f;
 cirlinklist p,t,q,mylink;
 p.CreateCLinkL(n,1);
 if(p.CListEmpty()) cout<<"單循環(huán)鏈表p空!\n";
 else cout<<"單循環(huán)鏈表p非空!\n";
 cout<<"單循環(huán)鏈表p(升序):\n";
 p.TraverseCList();
 if(p.CListEmpty()) cout<<"單循環(huán)鏈表p空!\n";
 else cout<<"單循環(huán)鏈表p非空!\n";
 if(p.EndCList()) cout<<"單循環(huán)鏈表p滿!\n";
 else cout<<"單循環(huán)鏈表p非滿!\n";
 cout<<"單循環(huán)鏈表t(無序):\n";
 t.CreateCLinkL(n-2);
 t.TraverseCList();
 cout<<"單循環(huán)鏈表t的長度:"<<t.CListSize()<<endl;
 cout<<"單循環(huán)鏈表q(降序):\n";
 q.CreateCLinkL(n,-1);
 q.TraverseCList();
 cout<<"單循環(huán)鏈表q的長度:"<<q.CListSize()<<endl;
 cout<<"鏈表q的第1個元素:"<<q.GetElem(1)<<endl;
 cout<<"鏈表q的第1個元素地址:"<<q.Index(1)<<endl;
 cout<<"鏈表q的第5個元素:"<<q.GetElem(5)<<endl;
 cout<<"鏈表q的第5個元素地址:"<<q.Index(5)<<endl;
 cout<<"鏈表q的第10個元素:"<<q.GetElem(10)<<endl;
 cout<<"鏈表q的第10個元素地址:"<<q.Index(10)<<endl;
 cout<<"鏈表q的curr->next所指元素地址:"<<q.Next()<<endl;
 x=65;it=66;
 if(q.FindCList(x)) cout<<x<<"查找成功!\n";
 else cout<<x<<"查找不成功!\n";
 if(q.UpdateCList(x,it)) cout<<x<<"更新成功!\n";
 else cout<<x<<"更新不成功!\n";
 cout<<"更新后單循環(huán)鏈表q:\n";
 q.TraverseCList();
 cout<<"插入后單循環(huán)鏈表q:\n";
 it=100;q.InsertCList(it,1);
 q.TraverseCList();
 cout<<"插入后單循環(huán)鏈表q:\n";
 it=101;q.InsertCList(it,5);
 q.TraverseCList();
 cout<<"插入后單循環(huán)鏈表q:\n";
 it=102;q.InsertCList(it,12);
 q.TraverseCList();
 cout<<"插入后q表長:"<<q.CListSize()<<endl;
 cout<<"第1個數(shù):"<<q.DeleteCList(1)<<"刪除成功!\n";
 cout<<"刪除后q表長:"<<q.CListSize()<<endl;
 q.TraverseCList();
 cout<<"第5個數(shù):"<<q.DeleteCList(5)<<"刪除成功!\n";
 cout<<"刪除后q表長:"<<q.CListSize()<<endl;
 q.TraverseCList();
 cout<<"第11個數(shù):"<<q.DeleteCList(11)<<"刪除成功!\n";
 cout<<"刪除后q表長:"<<q.CListSize()<<endl;
 q.TraverseCList();
 //求解約瑟夫(Josephus)問題
 cout<<"輸入人數(shù)n:";cin>>n;
 cout<<"輸入第次數(shù)m:";cin>>m;
 for(i=0;i<n;i++) mylink.InsertCList(i+1,i);
 cout<<"員工編號依次為:";
 LNode *w=mylink.Reset();
 while(!mylink.EndOCList())
  {cout<<setw(3)<<w->data;
   w=mylink.Next();}
 cout<<endl;
 cout<<"刪除次序依次為:\n";
 mylink.Reset(-1);
 for(i=0;i<n-1;i++)
 {for(int j=0;j<m-1;j++)
  {w=mylink.Next();
   if(mylink.EndOCList()) w=mylink.Next();}
  if(mylink.EndCList()) w=mylink.Next();
  cout<<"刪除第"<<mylink.DeleteNext()<<"人\n";}
 cout<<"最后剩下的是:第"<<mylink.GetElem(1)<<"個人\n";
 cin.get();cin.get();}
cirlinklistm.cpp運行結(jié)果:
單循環(huán)鏈表p非空!
單循環(huán)鏈表p(升序):
   2   8  10  10  28  28  47  49  63  66
單循環(huán)鏈表p非空!
單循環(huán)鏈表p滿!
單循環(huán)鏈表t(無序):
  45  89  87  64  19  68  55  46
單循環(huán)鏈表t的長度:8
單循環(huán)鏈表q(降序):
  93  51  47  46  43  41  35  32  31  13
單循環(huán)鏈表q的長度:10
鏈表q的第1個元素:93
鏈表q的第1個元素地址:12604252
鏈表q的第5個元素:43
鏈表q的第5個元素地址:12604316
鏈表q的第10個元素:13
鏈表q的第10個元素地址:12604396
鏈表q的curr->next所指元素地址:12604236
65查找不成功!
65更新不成功!
更新后單循環(huán)鏈表q:
  93  51  47  46  43  41  35  32  31  13
插入后單循環(huán)鏈表q:
  93 100  51  47  46  43  41  35  32  31  13
插入后單循環(huán)鏈表q:
  93 100  51  47  46 101  43  41  35  32  31  13
插入后單循環(huán)鏈表q:
  93 100  51  47  46 101  43  41  35  32  31  13 102
插入后q表長:13
第1個數(shù):93刪除成功!
刪除后q表長:12
 100  51  47  46 101  43  41  35  32  31  13 102
第5個數(shù):101刪除成功!
刪除后q表長:11
 100  51  47  46  43  41  35  32  31  13 102
第11個數(shù):102刪除成功!
刪除后q表長:10
 100  51  47  46  43  41  35  32  31  13
輸入人數(shù)n:8
輸入第次數(shù)m:3
員工編號依次為:  1  2  3  4  5  6  7  8
刪除次序依次為:
刪除第3人
刪除第6人
刪除第1人
刪除第5人
刪除第2人
刪除第8人
刪除第4人
最后剩下的是:第7個人