单循环链表的实现（c++）

单循环列表

• 在单链表的基础上，将链表的最后一个结点的后继指针由指向nullptr修改为指向头结点。
• 优势在于只要给定了任意一个结点，都可以访问链表的所有结点
• 需要注意的是判断条件是头结点而不是nullptr

单循环列表的编程实现

#include <iostream>


#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

using namespace std;

namespace _nmsp1
{
	template <typename T> //T代表数据元素的类型
	struct Node
	{
		T        data;  //数据域，存放数据元素
		Node<T>* next;  //指针域，指向下一个同类型（和本节点类型相同）节点

	};

	//单循环链表的定义
	template <typename T>
	class CirLinkList
	{
	public:
		CirLinkList();      //构造函数，参数可以有默认值
		~CirLinkList();     //析构函数

	public:
		bool ListInsert(int i, const T& e);  //在第i个位置插入指定元素e
		void ListInsertBack(const T& e);
		bool ListDelete(int i);              //删除第i个位置的元素

		bool GetElem(int i, T& e);           //获得第i个位置的元素值
		int  LocateElem(const T& e);         //按元素值查找其在单循环链表中第一次出现的位置

		void DispList();                     //输出单循环链表中的所有元素
		int  ListLength();                   //获取单循环链表的长度
		bool Empty();                        //判断单循环链表是否为空	
		void rear();						 //检验尾指针的指向是否正确
		void Merge_Link_list(CirLinkList<T> p1, CirLinkList<T> p2);

	private:
		Node<T>* m_head;	//头指针
		Node<T>* m_rear;		//尾指针
		int m_length;		//单循环链表长度
	};


	//通过构造函数对单循环链表进行初始化
	template <typename T>
	CirLinkList<T>::CirLinkList()
	{
		m_head = new Node<T>;		//先创建一个头结点
		m_head->next = m_head;		//指向头部（注意和单链表的差别）
		m_rear = m_head;			//尾指针初始化和头结点是一样的
		m_length = 0;				//头结点不计入单循环链表的长度		
	}

	//在第i个位置（位置编号从1开始）插入指定元素e
	template <typename T>
	bool CirLinkList<T>::ListInsert(int i, const T& e)
	{
		//判断插入位置i是否合法，i的合法值应该是1到length+1之间
		if (i < 1 || i >(m_length + 1))
		{
			cout << "元素" << e << "插入的位置" << i << "不合法，合法的位置是1到" << m_length + 1 << "之间!" << endl;
			return false;
		}

		//如果是要插入尾指针之后
		//如果i= 表长+1 ：代表就插入在尾处，相当于单链表的尾插法
		if (i - 1 == m_length)
		{
			ListInsertBack(e);
			return true;
		}

		Node<T>* p_curr = m_head;

		//整个for循环用于找到第i-1个节点
		for (int j = 0; j < (i - 1); ++j)
		{
			p_curr = p_curr->next;
		}

		Node<T>* node = new Node<T>;
		node->data = e;
		node->next = p_curr->next;
		p_curr->next = node;

		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;	        //实际表长+1
		return true;

	}


	// 快速在尾部插入元素
	template<typename T>
	void CirLinkList<T>::ListInsertBack(const T& e)
	{
		Node<T>* node = new Node<T>;
		node->data = e;
		node->next = m_rear->next;
		m_rear->next = node;
		m_rear = node;
		if (m_rear->next == m_head)
		{
			cout << "尾部插入元素成功，更新尾指针成功" << endl;
		}
		m_length++;

	}

	//删除第i个位置的元素
	template < typename T>
	bool CirLinkList<T>::ListDelete(int i)
	{
		if (m_length < 1)
		{
			cout << "当前单循环链表为空，不能删除任何数据!" << endl;
			return false;
		}
		if (i < 1 || i > m_length)
		{
			cout << "删除的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
			return false;
		}

		Node<T>* p_curr = m_head;

		//整个for循环用于找到第i-1个节点
		for (int j = 0; j < (i - 1); ++j)	//用于定位
		{
			p_curr = p_curr->next;
		}
		Node<T>* p_willdel = p_curr->next;	//p_willdel指向待删除的节点
		p_curr->next = p_willdel->next;		//第i-1个节点的next指针指向第i+1个节点
		cout << "成功删除位置为" << i << "的元素，该元素的值为" << p_willdel->data << "!" << endl;
		m_length--;							//实际表长-1
		delete p_willdel;
		return true;
	}


	//获得第i个位置的元素值
	template<class T>
	bool CirLinkList<T>::GetElem(int i, T& e)
	{
		if (m_length < 1)
		{
			cout << "当前单循环链表为空，不能获取任何数据!" << endl;
			return false;
		}

		if (i < 1 || i > m_length)
		{
			cout << "获取元素的位置" << i << "不合法，合法的位置是1到" << m_length << "之间!" << endl;
			return false;
		}

		Node<T>* p_curr = m_head;
		for (int j = 0; j < i; ++j)
		{
			p_curr = p_curr->next;
		}
		e = p_curr->data;
		cout << "成功获取位置为" << i << "的元素，该元素的值为" << e << "!" << endl;
		return true;
	}


	//按元素值查找其在单循环链表中第一次出现的位置
	template<class T>
	int CirLinkList<T>::LocateElem(const T& e)
	{
		Node<T>* p_curr = m_head;
		for (int i = 1; i <= m_length; ++i)
		{
			if (p_curr->next->data == e)
			{
				cout << "值为" << e << "的元素在单循环链表中第一次出现的位置为" << i << "!" << endl;
				return i;
			}
			p_curr = p_curr->next;
		}
		cout << "值为" << e << "的元素在单循环链表中没有找到!" << endl;
		return -1;  //返回-1表示查找失败
	}

	//输出单循环链表中的所有元素，时间复杂度为O(n)
	template<class T>
	void CirLinkList<T>::DispList()
	{
		Node<T>* p = m_head->next;
		while (p != m_head)
		{
			cout << p->data << " ";
			p = p->next;
		}
		cout << endl;
	}

	//获取单循环链表的长度，时间复杂度为O(1)
	template<class T>
	int  CirLinkList<T>::ListLength()
	{
		return m_length;
	}

	//通过析构函数对单循环链表进行资源释放
	template <typename T>
	CirLinkList<T>::~CirLinkList()
	{
		Node<T>* pnode = m_head->next;
		Node<T>* ptmp;
		while (pnode != m_head)   //该循环负责释放数据节点（注意循环的条件）
		{
			ptmp = pnode;
			
			pnode = pnode->next;

			delete ptmp;
			
		}
		
		delete m_head;    //释放头结点
		m_head = nullptr;//非必须
		m_length = 0;     //非必须
	}

	template <typename T>
	void CirLinkList<T>::rear()
	{
		cout << " 链表最后一个元素为" << m_rear->data << endl;
	}

	template<typename T>
	void CirLinkList<T>::Merge_Link_list(CirLinkList<T>p1, CirLinkList<T>p2)		//合并两个单循环链表
	{
		Node<T>* p1_rear = p1.m_rear;
		Node<T>* p1head = p1_rear->next;
		Node<T>* p2_rear = p2.m_rear;
		Node<T>* p2head = p2_rear->next;

		p1_rear->next = p2_rear->next->next;
		p2_rear->next = p1head;

		p1_rear = p2_rear;
		//delete p2head;
		p1.m_length += p2.m_length;
		cout << "合并链表" << endl;

	}
	
	

}


int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口

	_nmsp1::CirLinkList<int> slinkobj;
	_nmsp1::CirLinkList<int> slinkobj1;
	slinkobj.ListInsert(1, 12);
	slinkobj.ListInsert(1, 24);
	slinkobj.ListInsert(3, 48);
	slinkobj.ListInsert(2, 100);
	slinkobj.DispList();
	slinkobj.rear();

	slinkobj1.ListInsert(1, 1000);
	slinkobj1.ListInsert(2, 2000);
	slinkobj1.ListInsert(3, 3000);
	slinkobj1.ListInsert(4, 4000);
	slinkobj1.DispList();
	
	slinkobj.Merge_Link_list(slinkobj, slinkobj1);
	slinkobj1.DispList();
	slinkobj.DispList();

	//slinkobj.ListInsertBack(1000);
	//slinkobj.DispList();
	//slinkobj.rear();


	//slinkobj.ListDelete(4);
	//slinkobj.rear();

	//int eval = 0;
	//slinkobj.GetElem(3, eval); //如果GetElem()返回true，则eval中保存着获取到的元素值
	//int findvalue = 100; //在单循环链表中要找的元素值
	//slinkobj.LocateElem(findvalue);
	//slinkobj.DispList();
	//cout << "单循环链表的长度为：" << slinkobj.ListLength() << endl;



	return 0;
}

• 注意：以上代码不是完全正确，在合并两个单链表的功能报错，后续解决。