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

双循环链表

• 在双链表的基础上，将链表中的最后一个结点的后继指针由指向nullptr修改为指向头结点，将链表头结点的前趋指针由指向nullptr修改为指向最后一个结点，从而构成双循环链表。

• 与双链表的主要的改动是

  • 在于构造函数的头结点的next指针和prior指针初始化时指向自己。
  • 判断是否为空应该是m_head->next == m_head而不是m_head->next== 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>
	struct Double_Node
	{
		T data;						//数据域
		Double_Node<T>* prior;		//前趋指针
		Double_Node <T>* next;		//后继指针

	};


	template<typename T>
	class Db_Cir_Link_List
	{
	public:
		Db_Cir_Link_List();
		~Db_Cir_Link_List();

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


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

		void DispList();                     //输出双循环链表中的所有元素
		int  ListLength();                   //获取双循环链表的长度
		bool Empty();                        //判断双循环链表是否为空


	private:
		Double_Node<T>* m_head;
		int m_length;
	};


	//构造函数进行初始化
	template<typename T>
	Db_Cir_Link_List<T>::Db_Cir_Link_List()
	{
		m_head = new Double_Node<T>;
		m_head->next = m_head;
		m_head->prior = m_head;
		m_length = 0;
	}

	template <typename T>
	bool Db_Cir_Link_List<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;
		}

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

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

		//因为是循环的，就不需要进行if(p_curr->next != m_head)
		p_curr->next->prior = node;
		p_curr->next = node;
		cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
		m_length++;	        //实际表长+1
		return true;
	}

	//删除第i个位置的元素
	template < typename T>
	bool Db_Cir_Link_List<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;
		}

		Double_Node<T>* p_curr = m_head;

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

		Double_Node<T>* p_willdel = p_curr->next;		 //p_willdel指向待删除的节点
		Double_Node<T>* p_willdelNext = p_willdel->next; //p_willdelNext指向待删除节点的下一个节点
		p_curr->next = p_willdel->next;					//第i-1个节点的next指针指向第i+1个节点
														// 链表是循环的不需要进行  if (p_willdelNext != m_head)
		p_willdelNext->prior = p_curr;					//第i+1个节点的prior指针指向第i-1个节点

		cout << "成功删除位置为" << i << "的元素，该元素的值为" << p_willdel->data << "!" << endl;
		m_length--;										//实际表长-1
		delete p_willdel;
		return true;
	}


	//获得第i个位置的元素值
	template<class T>
	bool Db_Cir_Link_List<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;
		}

		Double_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 Db_Cir_Link_List<T>::LocateElem(const T& e)
	{
		Double_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 Db_Cir_Link_List<T>::DispList()
	{
		Double_Node<T>* p = m_head->next;
		while (p != m_head) //这里采用while循环或者for循环书写都可以
		{
			cout << p->data << " ";  //每个数据之间以空格分隔
			p = p->next;
		}
		cout << endl; //换行
	}


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

	//判断双循环链表是否为空，时间复杂度为O(1)
	template<class T>
	bool Db_Cir_Link_List<T>::Empty()
	{
		if (m_head->next == m_head) //双循环链表为空
		{
			return true;
		}
		return false;
	}

	//通过析构函数对双循环链表进行资源释放
	template <typename T>
	Db_Cir_Link_List<T>::~Db_Cir_Link_List()
	{
		Double_Node<T>* pnode = m_head->next;
		Double_Node<T>* ptmp;
		while (pnode != m_head) //该循环负责释放数据节点
		{
			ptmp = pnode;
			pnode = pnode->next;

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


int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	_nmsp1::Db_Cir_Link_List<int>slinkobj;
	slinkobj.ListInsert(1, 1);
	slinkobj.ListInsert(2, 2);
	slinkobj.ListInsert(3, 3);
	slinkobj.DispList();
	slinkobj.ListDelete(3);
	slinkobj.DispList();

	slinkobj.ListInsert(3, 3);
	slinkobj.ListInsert(4, 4);
	int a=0;
	slinkobj.GetElem(3,a);
	cout << slinkobj.ListLength() << endl;
	slinkobj.Empty();
	slinkobj.LocateElem(3);
}