数据结构（六）——循环链表
数据结构（六）——循环链表
一、循序链表简介
1、循环链表的定义
循环链表的任意元素都有一个前驱和一个后继，所有数据元素在关系上构成逻辑上的环。
循环链表是一种特殊的单链表，尾结点的指针指向首结点的地址。
循环链表的逻辑关系图如下：
创新互联是一家专业提供芙蓉企业网站建设,专注与成都做网站、网站建设、H5响应式网站、小程序制作等业务。10年已为芙蓉众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。
2、循环链表的设计实现
循环链表的设计实现要点：
A、通过模板定义CircleList，继承自LinkedList
B、定义连接链表首尾的内部函数
C、实现首元素的插入和删除操作
D、重写清空操作和遍历操作
3、循环链表的实现关键
A、插入位置为0时，头结点和尾结点均指向新结点，新结点作为首结点插入链表。
B、删除位置为0时，头结点和尾结点指向位置为1的结点，删除销毁首结点
二、循环链表的操作
1、尾结点获取
Node* last()
{
return this->position(this->m_length - 1)->next;
}2、首尾结点连接
void lastToFirst()
{
last()->next = this->m_header.next;
}三、循环链表的实现
template
class CircleList:public LinkedList
{
protected:
typedef typename LinkedList::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::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::remove(index);
}
return ret;
}
bool set(int index, const T& value)
{
index = mod(index);
return LinkedList::set(index, value);
}
T get(int index)const
{
index = mod(index);
return LinkedList::get(index);
}
bool get(int index, T& value)
{
index = mod(index);
return LinkedList::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::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的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
2、循环链表解决约瑟夫环问题
//约瑟夫环
void jusephus(int n, int k, int m)
{
//构建循环链表
CircleList 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
#include
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);
}网站标题：数据结构（六）——循环链表
本文URL：http://myzitong.com/article/gscecd.html