博客

数据结构（面向对象方法与C++语言描述）（第2版）循环链表内容整理

循环链表

循环链表（circular list）是另一种形式的表示线性表的链表，它的节点结构与单链表相同，与单链表不同的是链表中表位节点的link域中不是NULL，而是存放了一个指向链表开始结点的指针。这样，只要知道表中任何一个结点的地址，就能遍历表中其他任一结点。图是循环链表的示意图。

设 current 是在循环链表中逐个结点检测的指针，则在判断current是否达到链表的链尾时，不是判断是否 current->link == NULL，而是判断是否 current->link == first。

循环链表的运算与单链表类似，但在涉及链头与链尾处理时稍有不同。例如，在实现循环链表的插入运算时，如果在表的最前端插入，必须改变链尾最后一个节点的 link 域的值。这就需要循链搜索找到最后一个结点。如果在类定义中给出的链表指针不是放在链头的 first 指针，而是放在链尾的 rear指针，则实现插入或删除运算就会更方便，关键运算为：

newNode->link = rear->link; rear->link = newNode;

循环链表与单链表一样，可以有附加头结点，这样能够简化链表操作的实现，统一空表与非空表的运算。图给出空表与非空表情形下循环链表的形态。在带附加头结点的循环链表中，链尾结点的 link 域存放的是该链表附加头结点的地址。

代码实现

环境：vs2019

头文件：CircList.h

源文件：main.cpp

CircList.h代码：

#pragma once

#include <iostream>

template<typename T>
struct CircLinkNode {
	T data;
	CircLinkNode<T>* link;
	CircLinkNode(CircLinkNode<T>* next = nullptr) :data(0), link(next) {}
	CircLinkNode(T d, CircLinkNode<T>* next = nullptr) :data(d), link(next) {}
};

template<typename T>
class CircList
{
public:
	CircList();												//构造函数
	CircList(const T& x);									//构造函数
	CircList(CircList<T>& L);								//拷贝构造
	~CircList();											//析构函数
	void makeEmpty();										//将链表置空
	int Length()const;										//计算循环链表长度
	bool IsEmpty() { return first->link == first ? true : false; }
															//判表空否
	CircLinkNode<T>* getHead()const;						//返回附加头结点地址
	void setHead(CircLinkNode<T>* p);						//设置附加头结点地址
	CircLinkNode<T>* Search(T x);							//搜索含数据x的元素
	CircLinkNode<T>* Locate(int i)const;					//搜索第i个元素的地址
	bool getData(int i, T& x)const;							//取出第i个元素的地址
	void setData(int i, T& x);								//用x修改第i个元素的值
	bool Insert(int i, T& x);								//在第i个元素后插入x
	bool Remove(int i, T& x);								//删除第i个元素，x返回该元素的值
	void output();											//输出
	CircList<T>& operator=(CircList<T>& L);					//重载运算符=
	void inputFront(T endTag);								//前插法建立单链表
	void inputRear(T endTag);								//后插法建立单链表
private:
	CircLinkNode<T>* first, * last;						//头指针，尾指针
};

template<typename T>
inline CircList<T>::CircList()
{
	first = new CircLinkNode<T>;
	first->link = first;
	last = first;
}

template<typename T>
inline CircList<T>::CircList(const T& x)
{
	first = new CircLinkNode<T>(x);
	first->link = first;
	last = first;
}

template<typename T>
inline CircList<T>::CircList(CircList<T>& L)
{
	//拷贝构造函数
	T value;
	CircLinkNode<T>* srcptr = L.getHead();					//被赋值表的附加头结点地址
	CircLinkNode<T>* destptr = first = new CircLinkNode<T>;
	while (srcptr->link != L.first)							//逐个结点复制
	{
		value = srcptr->link->data;
		destptr->link = new CircLinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	last = srcptr;
	destptr->link = first;	
}

template<typename T>
inline CircList<T>::~CircList()
{
	makeEmpty();
	if (first != nullptr) delete first;
}

template<typename T>
inline void CircList<T>::makeEmpty()
{
	//将链表置位空表
	CircLinkNode<T>* q;
	while (first->link != first)
	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
	last = first;
}

template<typename T>
inline int CircList<T>::Length() const
{
	//计算带附加头结点的单链表的长度
	CircLinkNode<T>* p = first->link;
	int count = 0;
	while (p != first)										//循链扫描，寻找链尾
	{
		p = p->link;
		count++;
	}
	return count;
}

template<typename T>
inline CircLinkNode<T>* CircList<T>::getHead() const
{
	return first;
}

template<typename T>
inline void CircList<T>::setHead(CircLinkNode<T>* p)
{
	CircLinkNode<T>* current = first;
	while (current->link != first)
	{
		if (current->link == p) break;						//循链找p指针
		else current = current->link;
	}
	first = current->link;
	last = current;
}

template<typename T>
inline CircLinkNode<T>* CircList<T>::Search(T x)
{
	//在表中搜索含数据x的节点，搜索成功时函数返回该节点地址；否则返回first值。
	CircLinkNode<T>* current = first->link;
	while (current != first)
	{
		if (current->data == x) break;						//循链找含x结点
		else current = current->link;
	}
	return current;
}

template<typename T>
inline CircLinkNode<T>* CircList<T>::Locate(int i) const
{
	//定位函数。返回表中第i个元素的地址。若i<0或i超过表中结点个数，则返回first。
	if (i < 0) return first;								//i不合理
	CircLinkNode<T>* current = first->link;
	int k = 1;
	while (current != first && k < i)						//循链找第i个结点
	{
		current = current->link;
		k++;
	}
	return current;											//返回第i个结点地址，若返回first，表示i值太大
}

template<typename T>
inline bool CircList<T>::getData(int i, T& x) const
{
	//取出链表中第i个元素的值。
	if (i <= 0) return false;								//i值太小
	CircLinkNode<T>* current = Locate(i);
	if (current == first) return false;						//i值太大
	else
	{
		x = current->data;
		return true;
	}
}

template<typename T>
inline void CircList<T>::setData(int i, T& x)
{
	//给链表中的第i个元素赋值x。
	if (i <= 0) return;										//i值太小
	CircLinkNode<T>* current = Locate(i);
	if (current == first) return;							//i值太大
	else current->data = x;
}

template<typename T>
inline bool CircList<T>::Insert(int i, T& x)
{
	//将新元素x插入在链表中第i个结点之后。
	CircLinkNode<T>* current = Locate(i);
	if (current == first) return false;						//插入不成功
	CircLinkNode<T>* newNode = new CircLinkNode<T>(x);
	if (newNode == nullptr)
	{
		std::cerr << "存储分配错误！" << std::endl;
		exit(1);
	}
	newNode->link = current->link;
	current->link = newNode;
	if (newNode->link == first) last = newNode;
	return true;											//插入成功
}

template<typename T>
inline bool CircList<T>::Remove(int i, T& x)
{
	//将链表中的第i个元素删去，通过引用型参数x返回该元素的值。
	CircLinkNode<T>* current = Locate(i - 1);
	if (current == first || current->link == first)	return false;
	//删除不成功
	CircLinkNode<T>* del = current->link;					//重新拉链，将被删结点从链中摘下
	current->link = del->link;
	x = del->data;
	delete del;												//取出被删结点中的数据值
	if (current->link == first) last = current;
	return true;
}

template<typename T>
inline void CircList<T>::output()
{
	//循环链表的输出函数：将循环链表中所有数据按逻辑顺序输出到屏幕上。
	std::cout << "链表中的元素为： ";
	CircLinkNode<T>* current = first->link;
	while (current != first)
	{
		std::cout << current->data << " ";
		current = current->link;
	}
	std::cout << std::endl;
}

template<typename T>
inline CircList<T>& CircList<T>::operator=(CircList<T>& L)
{
	//重载函数：赋值操作，形式如 A = B，其中 A 是调用此操作的List对象，B 是参数表中的
	//引用型参数L结合的实参。
	makeEmpty();
	T value;
	CircLinkNode<T>* srcptr = L.getHead();					//被复制表的附加头结点地址
	CircLinkNode<T>* destptr = first = new CircLinkNode<T>;
	while (srcptr->link != L.first)							//逐个结点复制
	{
		value = srcptr->link->data;
		destptr->link = new CircLinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = first;
	last = destptr;
	return *this;											//返回操作对象地址
}

template<typename T>
inline void CircList<T>::inputFront(T endTag)
{
	//endTag是约定的输入序列结束的标志。如果输入序列是正整数，endTag可以是0或负数；
	//如果输入序列是字符，endTag可以是字符集中不会出现的字符，如"\0"。
	CircLinkNode<T>* newNode;
	T val;
	makeEmpty();
	std::cin >> val;
	while (val != endTag)
	{
		newNode = new CircLinkNode<T>(val);					//创建新结点
		if (newNode == nullptr)
		{
			std::cerr << "存储分配错误！" << std::endl;
			exit(1);
		}
		newNode->link = first->link;
		first->link = newNode;								//插入到表最前端
		if (last == first)
		{
			last = newNode;
		}
		std::cin >> val;
	}
}

template<typename T>
inline void CircList<T>::inputRear(T endTag)
{
	//endTag是约定的输入序列结束的标志
	CircLinkNode<T>* newNode;
	T val;
	makeEmpty();
	std::cin >> val;	
	while (val != endTag)									//last指向表尾
	{
		newNode = new CircLinkNode<T>(val);
		if (newNode == nullptr)
		{
			std::cerr << "存储分配错误！" << std::endl;
			exit(1);
		}		
		last->link = newNode;
		last = newNode;
		std::cin >> val;									//插入到表末端
	}
	last->link = first;
}

main.cpp代码：

#include "CircList.h"

int main()
{
	CircList<int> L1;
	CircList<int> L2;
	int val = 0;
	bool flag = false;

	std::cout << "Q:测试IsEmpty()  链表L1是否为空" << std::endl;
	flag = L1.IsEmpty();
	if (flag) std::cout << "链表L1为空" << std::endl;
	else std::cout << "链表L1不为空" << std::endl;

	std::cout << "Q:测试inputFront()  前插法建立单链表L1" << std::endl;
	L1.inputFront(-1);
	L1.output();

	std::cout << "Q:测试IsEmpty()  链表L1是否为空" << std::endl;
	flag = L1.IsEmpty();
	if (flag) std::cout << "链表L1为空" << std::endl;
	else std::cout << "链表不为空" << std::endl;

	std::cout << "Q:测试Length()  链表L1的长度为：" << std::endl;
	std::cout << L1.Length() << std::endl;

	std::cout << "Q:测试getData()  链表L1取第3个元素的值：" << std::endl;
	L1.getData(3, val);
	std::cout << val << std::endl;

	std::cout << "Q:测试setData()  链表L1修改第6个元素的值为99" << std::endl;
	val = 99;
	L1.setData(6, val);
	L1.output();

	std::cout << "Q:测试Insert()  链表L1在第8个元素后插入77" << std::endl;
	val = 77;
	L1.Insert(8, val);
	L1.output();

	std::cout << "Q:测试Remove()  链表L1删除第3个元素" << std::endl;
	L1.Remove(3, val);
	std::cout << "删除的元素为：" << val << std::endl;
	L1.output();

	std::cout << "Q:测试setHead()  链表L1设置第4个元素为头结点" << std::endl;
	CircLinkNode<int>* pnode = L1.Locate(4);
	L1.setHead(pnode);
	L1.output();

	std::cout << "Q:测试inputRear()  后插法建立单链表L2" << std::endl;
	L2.inputRear(-1);
	L2.output();

	std::cout << "Q:测试operator=()  赋值单链表L2" << std::endl;
	L2 = L1;
	L2.output();

	return 0;
}

控制台界面：