关键词：循环链表的实现、约瑟夫环问题
1. 什么是循环链表？
- 概念上：
任意数据元素都有一个前驱和一个后继
所有的数据元素构成一个逻辑上的环 - 实现上
循环链表是一种特殊的单链表
尾结点的指针域保存了首结点的地址
循环链表的逻辑构成
循环链表的继承层次结构
2. 循环链表的实现思路
- 通过模板定义
CircleList类，继承自LinkList类 - 定义内部函数
last_to_first()，用于将单链表首尾相连 - 特殊处理：首元素的插入和删除操作
- 重新实现：清空操作和遍历操作
3. 循环链表的实现要点
- 插入位置为0时：头结点和尾结点均指向新结点，新结点成为首结点插入链表
bool insert(int i, const T& e)
{
bool ret = true;
i = i % (this->m_length + 1); // m_length + 1：表示插入之后的元素个数
ret = LinkList<T>::insert(i, e); // 用父类的insert函数直接插入
if( ret && ( i==0 )) // 判断插入是否成功，且i是否为0，
{
last_to_first(); // 当i为0时，表示在首元素插入元素，则将首尾相连
}
return ret;
}
- 删除位置为0时：头结点和尾结点指向位置为1的结点，安全销毁结点
bool remove(int i)
{
bool ret = true;
i = mod(i);
if( i == 0 ) // 删除的结点为首结点
{
Node* toDel = this->m_header.next;
if( toDel != NULL )
{
this->m_header.next = toDel->next;
--(this->m_length);
if( this->m_length > 0) // 当m_length > 0,表示此时链表不为空
{
last_to_first(); // 首尾相连
if( this->m_current == toDel )
{
this->m_current = toDel->next;
}
}
else // 当m_length == 0时，表示此时链表为空
{
this->m_header.next = NULL;
this->m_current = NULL;
}
this->destroy(toDel);
}
else
{
ret = false; // 当toDel == NULL， 表示此时链表为空链表，remove返回false
}
}
else // 删除的结点不为首结点
{
ret = LinkList<T>::remove(i);
}
return ret;
}
#ifndef CIRCLELIST_H
#define CIRCLELIST_H
#include "LinkList.h"
namespace DTLib
{
template < typename T>
class CircleList : public LinkList<T>
{
protected:
typedef typename LinkList<T>::Node Node;
int mod(int i) const;
Node* last() const; // 获取尾结点的next指针
void last_to_first() const; // 用于将单链表的首尾相连
public:
bool insert(const T& e);
bool insert(int i, const T& e);
bool remove(int i);
bool set(int i, const T& e);
T get(int i) const;
bool get(int i, T& e) const;
int find(const T& e) const; // 重新实现查找操作
void clear();
bool move(int i, int step = 1);
bool end();
~CircleList();
};
template < typename T >
int CircleList<T>::mod(int i) const
{
return ( (this->m_length == 0) ? 0 : (i % this->m_length) );
}
template < typename T >
typename LinkList<T>::Node* CircleList<T>::last() const
{
return this->position(this->m_length - 1)->next;
}
template < typename T >
void CircleList<T>::last_to_first() const
{
last()->next = this->m_header.next;
}
template < typename T >
bool CircleList<T>::insert(const T& e)
{
return insert(this->m_length, e);
}
template < typename T >
bool CircleList<T>::insert(int i, const T& e)
{
bool ret = true;
i = i % (this->m_length + 1);
// 先用LinkList中的insert()插入将元素插入，
// 然后判断插入元素是否成功且位置是否为首结点，
// 如果为首结点，则将尾结点指向首结点
ret = LinkList<T>::insert(i, e);
if( ret && (i == 0) )
{
last_to_first();
}
return ret;
}
template < typename T >
bool CircleList<T>::remove(int i)
{
bool ret = true;
i = mod(i);
if( i == 0 ) // 判断删除位置是否为首结点
{
Node* toDel = this->m_header.next;
if( toDel != NULL)
{
this->m_header.next = toDel->next;
--(this->m_length);
if( this->m_length > 0 )
{
last_to_first();
if( this->m_current == toDel )
{
this->m_current = toDel->next;
}
}
else // 当m_length为0时，链表为空
{
this->m_header.next = NULL;
this->m_current = NULL;
}
this->destroy(toDel);
}
else // 如果toDel为空，则链表为空，删除失败
{
ret = false;
}
}
else
{
ret = LinkList<T>::remove(i);
}
return ret;
}
template < typename T >
bool CircleList<T>::set(int i, const T& e)
{
return LinkList<T>::set(mod(i), e);
}
template < typename T >
T CircleList<T>::get(int i) const
{
return LinkList<T>::get(mod(i));
}
template < typename T >
bool CircleList<T>::get(int i, T& e) const
{
return LinkList<T>::get(mod(i), e);
}
template < typename T >
int CircleList<T>::find(const T& e) const
{
// 通过slider指针来遍历链表中的每个元素的value，
// 若找到，返回i，若没找到，返回-1.
int ret = -1;
Node* slider = this->m_header.next;
for(int i=0; i<this->m_length; ++i)
{
if( slider->value == e )
{
ret = i;
break;
}
slider = slider->next;
}
return ret;
}
template < typename T >
void CircleList<T>::clear()
{
// 将下标为1的结点循环删除，直到链表中只有一个结点为止，
// 然后再删除链表中的最后一个结点。
// 循环删除下标为1的结点而不是循环删除下标为0的结点的原因是：
// 循环删除下标为0的结点会导致头结点指针和尾结点指针的大量移动
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);
}
}
template < typename T >
bool CircleList<T>::move(int i, int step)
{
return LinkList<T>::move(mod(i), step);
}
template < typename T >
bool CircleList<T>::end()
{
return (this->m_length == 0) || (this->m_current == NULL);
}
template < typename T >
CircleList<T>::~CircleList()
{
clear();
}
}
#endif // CIRCLELIST_H
4. 约瑟夫环问题
已知n个人（以编号0， 1， 2，...，n-1分别表示）围坐在一张圆桌周围。从编号为s的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
#include "CircleList.h"
/* -----测试约瑟夫环问题----- */
/*
* people_num: 表示总人数
* s：表示编号为s的开始报数
* m：表示报到m时去掉此结点
*/
void test_josephus(int people_num, int s, int m)
{
CircleList<int> list;
for(int i=1; i<=people_num; ++i)
{
list.insert(i);
}
cout << "begin..." << endl;
list.move(s-1, m-1);
int flag = 0;
while(list.length() > 0)
{
list.next();
cout << "list.current(" << ++flag << ") = " << list.current() << endl;
list.remove(list.find(list.current()));
}
}
5. 小结
- 循环链表是一种特殊的单链表
- 尾结点的指针域保存了首结点的地址
- 特殊处理首元素的插入操作和删除操作
- 重新实现清空操作和遍历操作
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
网友评论