[数据结构与算法]学习笔记——循环链表（C++表述）

在校学生，叙述中存在不足或错误之处还请各位批评斧正。

单向链表的弊端

我们先前已经学习了单向链表，因为存储时不一定需要保证连续性，每个结点均存储有直接后继，我们可以很方便的进行插删操作与空间扩大。但是我们也发现一个弊端，就是每次进行对表操作时，我们都需要从头遍历至尾或到达链表中某个结点，即方向的单一性。
这时我们提出一个方法：将单链表中尾结点Node_end的下一结点属性nextnode指向头结点表的head. 这样就可以使链表构成一个循环，无论从哪个地方开始，均可以完成遍历。

循环链表的结点模板定义

循环链表的结点定义与单向链表一样。我们可以发现循环链表中与单向链表的唯一不同就是尾结点的处理上。

template <class T>
class Node {
protected:
	T data;
	Node<T>* nextnode;
public:
	Node();//用于创建空的节点
	Node(const T& obj);//创建只知道数据的节点
	Node(const T& obj, Node<T>* address);//创建都知道的节点
	Node(const Node<T>& node);//复制节点


	virtual Node<T>* getNextNode();//返回下一节点地址
	virtual void setNextNode(Node<T>* const address);//设置下一节点
	virtual T& showData();//返回数据

	~Node();//销毁节点
};

循环链表模板的定义

循环链表中，我们直接引入单向链表一样的定义。因为循环链表算是单向链表的一种变形。

template<class T> class CircularList {
protected:
	Node<T>* head;//链表头
	int LENGTH;//链表大小

public:
	CircularList(); 	//构造函数，构造一个空表

public:
	virtual void add(const T& obj); 	//添加一个元素入表
	virtual void insert(const T& obj, int index); 	//插入一个元素进入表
	virtual T& check(int index)const; 	//查看一个元素
	virtual bool remove(int index); 	//删除一个元素
	virtual int length()const; 	//返回表长度

public:
	virtual ~LinkList();
};

循环链表的方法实现

构造函数的实现

构造函数中与单向链表大同小异，具体实现上，需要实例化一个头结点head，再设置头结点的下一结点指向head实现一个循环链表的空表定义。头结点是什么，为什么要使用一个头结点详细请看单向链表的笔记（超链接：单链表）。

template<class T>
CircularList<T>::CircularList() {
	head = new Node<T>(); 	//设置头结点
	head->setNextNode(head);  	//设置头结点指向头结点，形成循环链表空表
	LENGTH = 0;  	//设置表长度为0
}

向表添加元素

我们需要注意的是，因为表尾下一结点指向head，所以我们判断是否到达链表尾的判断方式会发生变化。

template<class T>
void CircularList<T>::add(const T& dt) {
	Node<T>* temp = new Node<T>(dt, head); 	//创建新的结点,新结点连在链表尾，所以下一结点指向head
	if(temp == nullptr) { return; } 	//创建结点失败，返回
	Node<T>* node = head->getNextNode(); 	//获取head的下一结点
	while(node->getNextNode() != head) {
		node = node->getNextNode(); 
	}
	node->setNextNode(temp); 	//将新结点连入循环链表
	LENGTH++; 
	return; 
}

在链表中查找元素

查找元素与我们也从头开始，从头遍历至链表尾。

template<class T>
T& CircularList<T>::check(int index) {
	index--; 	//传入是自然排序，将其转化为从0开始
	if(index < 0 || index >= LENGTH) { throw "ERROR OBJ"; }
	Node<T>* node = head->getNextNode(); 	//获取下一结点
	for(int i = 1; i <= index; i++) {
		node = node->getNextNode(); 
	}
	return node->showData(); 
}

向链表中插入一个元素

插入元素与单向链表一样，找到插入点，插入。我们知道，假若我们知道插入链表中p结点的后方且知道p的地址，我们仅需执行：

insert_element->setNextNode(p->getNextNode()); 
p->setNextNode(insert_element); 

这时insert()方法的时间复杂度为常数阶。
当我们只知道要插入的下标或者是知道插入位置的数据样例时，我们就需要对数组的元素进行遍历。这时insert()方法的时间复杂度为线性阶。

template<class T>
void CircularList<T>::insert(int index, const T& dt) {
	Node<T>* node = head->getNextNode(); 	//获取第一个数据地址
	for(int i = 1; i < index; i++) {
		node = node->getNextNode(); 
	}
	Node<T>* temp = new Node<T>(dt, node->getNextNode()); 	//创建新结点
	if(temp == nullptr) { return; }
	node->setNextNode(temp); 
	return; 
}

向链表中删除一个元素

与单向链表类似，从头开始遍历链表，对比样例或者到达所给下标，删除相应元素。

template<class T>
bool CircularList<T>::remove(int index) {
	index--; 
	if(index <0 || index >= LENGTH) {
		return false; 
	}
	Node<T>* node = head->getNextNode(); 
	for(int i = 1; i < index - 1; i++) { 	//找到删除位置的上一个结点
		node = node->getNextNOde(); 
	}
	node->setNextNode(node->getNextNode()->getNextNode()); 	//将删除点的后继给删除点的前驱
	delete node->getNextNode(); 	//删除相应结点
	return true; 
}