循环链表的任意元素都有一个前驱和一个后继，所有数据元素在关系上构成逻辑上的环。
循环链表是一种特殊的单链表，尾结点的指针指向首结点的地址。
循环链表的逻辑关系图如下：

循环链表的设计实现要点：
A、通过模板定义CircleList，继承自LinkedList
B、定义连接链表首尾的内部函数
C、实现首元素的插入和删除操作
D、重写清空操作和遍历操作

A、插入位置为0时，头结点和尾结点均指向新结点，新结点作为首结点插入链表。
B、删除位置为0时，头结点和尾结点指向位置为1的结点，删除销毁首结点

Node* last(){ return this->position(this->m_length - 1)->next;}2、首尾结点连接

void lastToFirst(){ last()->next = this->m_header.next;}三、循环链表的实现

template <typename T> class CircleList:public LinkedList<T> { protected: typedef typename LinkedList<T>::Node Node; //尾结点 Node* last() { return this->position(this->m_length - 1)->next; } //链接最后一个结点和首结点 void lastToFirst() { last()->next = this->m_header.next; } int mod(int index)const { return (this->m_length == 0)?0:(index % this->m_length); } public: bool insert(int index, const T& value) { bool ret = true; //计算插入结点的位置 index = index % (this->m_length + 1); ret = LinkedList<T>::insert(index, value); //如果插入位置为0 if(ret && (index == 0)) { lastToFirst();//连接首尾结点 } return ret; } bool insert(const T& value) { return insert(this->m_length, value); } bool remove(int index) { bool ret = true; index = mod(index); //删除结点为首结点 if(index == 0) { //首结点 Node* toDel = this->m_header.next; if(toDel) { //将头结点的下一个结点指向首结点的下一个结点 this->m_header.next = toDel->next; this->m_length--;//链表长度减1 //链表不为空 if(this->m_length > 0) { lastToFirst();//连接新的首结点与尾结点 if(this->m_current == toDel) { this->m_current = toDel->next; } } else { //链表为空，置空 this->m_header.next = NULL; this->m_current = NULL; } //销毁要删除的结点 this->destroy(toDel); } else { ret = false; } } else { //删除的结点不是首结点，按单链表处理 ret = LinkedList<T>::remove(index); } return ret; } bool set(int index, const T& value) { index = mod(index); return LinkedList<T>::set(index, value); } T get(int index)const { index = mod(index); return LinkedList<T>::get(index); } bool get(int index, T& value) { index = mod(index); return LinkedList<T>::get(index, value); } int find(const T& value) { int ret = -1; //首结点 Node* current = this->m_header.next; //遍历链表查找数据元素 for(int i = 0; i < this->length(); i++) { if(current->value == value) { ret = i; break; } //移动游标 current = current->next; } return ret; } void clear() { //删除链表中结点至头结点 while(this->m_length > 1) { remove(1); } //删除首结点 if(this->m_length == 1) { Node* toDel = this->m_header.next; this->m_header.next = NULL; this->m_current = NULL; this->m_length = 0; this->destroy(toDel); } } bool move(int pos, int step) { pos = mod(pos); return LinkedList<T>::move(pos, step); } bool end() { return (this->m_length == 0) || (this->m_current == NULL); } ~CircleList() { clear(); } };四、约瑟夫环（Josephus）1、约瑟夫环简介

Josephu约瑟夫环问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

//约瑟夫环void jusephus(int n, int k, int m){ //构建循环链表 CircleList<int> cl; for(int i = 1; i <= n; i++) { cl.insert(i); } //移动当前结点到位置k-1，设置步长为m-1 cl.move(k-1, m-1); while(cl.length() > 0) { cl.next();//移动到目标位置 cout << cl.current() << endl; //删除目标位置结点 cl.remove(cl.find(cl.current())); }}3、递归方法解决约瑟夫环问题

当编号为1开始时可以使用递归
假设n=10,m=3
1 2 3 4 5 6 7 8 9 10 m=3
第一次有人出列后：1 2 4 5 6 7 8 9 10
出环的序列：4 5 6 7 8 9 10 1 2
转换为：1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 4 5 6 7 8 9 10 1 2
设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号，则f(10,3,10)是我们要的结果
当i=1时，  f(n,m,i) = (n-1+m)%n
当i>1时，  f(n,m,i)= ( f(n-1,m,i-1)+m )%n
当编号为0开始时可以使用递归
假设n=10,m=3
0 1 2 3 4 5 6 7 8 9 m=3
第一次有人出列后：0 1 3 4 5 6 7 8 9
3 4 5 6 7 8 9 0 1
1 2 3 4 5 6 7 8 9
+3: 4 5 6 7 8 9 10 11 12
%10: 3 4 5 6 7 8 9 1 2
设f(n,m,i)为n个人的环，报数为m，第i个人出环的编号，则f(10,3,10)是我们要的结果
当i=1时，  f(n,m,i) = (n-1+m)%n
当i>1时，  f(n,m,i)= ( f(n-1,m,i-1)+m )%n

#include <stdio.h>#include <stdlib.h>int Josephu_recursion(int n, int m, int i){ if(1 == i) return (n-1 + m) % n; else return (Josephu_recursion(n-1, m, i-1) + m) % n;}int main(void){ int i; for(i = 1; i <= 10; i ++) printf("第%2d次出环：%2d\n", i, Josephu_recursion(10, 3, i));}4、数组方法解决约瑟夫环问题

/*********************************************** * 约瑟夫环问题的数组解决 * n:约瑟夫环的长度 * k:起点 * m:步长 * *********************************************/int JosephuArray(int n, int k, int m){ //分配n+1个int空间 int *a = (int *)malloc((n+1) * sizeof(int)); int i, j; //下标从1开始赋值 for(i = 1; i <= n; i++) a[i] = i;//从a[1]开始 //依次出环 for(i = n; i >= 1; i--) { //计算每次出环的k值 k = (k + m -1) % i; if(k == 0) k = i; printf("%2d\n", a[k]);//打印出出环的序号 //将出环的位置后的元素前移 for(j = k; j < i; j++) a[j] = a[j+1]; } free(a);}