【C++】实现双向循环链表

秒速五厘米 2022-06-07 01:39 245阅读 0赞

双向链表有两个指针域，一个指向下一个节点(\_next)，一个则指向上一个节点(\_pre)。而双向循环链表则是在双向链表的基础上，其头结点的\_pre域为尾节点，尾节点的\_next域则为头结点。如下图所示：![SouthEast][]

/*双向循环链表的实现*/
    #include <iostream>
    #include <assert.h>
    using namespace std;
    typedef int DataType;
    typedef struct Node
    {
    	Node(const DataType& d)
    	: _pre(NULL)
    	, _next(NULL)
    	, _data(d)
    	{}
    	Node* _pre;
    	Node* _next;
    	DataType _data;
    }Node;
    class List
    {
    public:
    	friend ostream& operator<<(ostream& _cout, const List& list)//输出运算符的重载
    	{
    		Node* pcur = list._pHead;
    		if (pcur == NULL)//空链表
    			_cout << "over";
    		else
    		{
    			while (pcur->_next != list._pHead)//循环少最后一个节点，需在循环外加一句
    			{
    				_cout << pcur->_data << "-";
    				pcur = pcur->_next;
    			}
    			_cout << pcur->_data << "-";
    			_cout << "over";
    		}
    		return _cout;
    	}
    
    	List()//构造函数
    		:_pHead(NULL)
    	{}
    
    	List(DataType*arr, int size)//构造函数的重载
    		:_pHead(NULL)
    	{
    		for (int i = 0; i < size; i++)
    			PushBack(arr[i]);//尾插函数
    	}
    
    	List(const List& list)//拷贝构造函数
    	{
    		if (list._pHead == NULL)
    			return;
    		else
    		{
    			Node* pcur = list._pHead;
    			while (pcur->_next != list._pHead)
    			{
    				PushBack(pcur->_data);
    				pcur = pcur->_next;
    			}
    			PushBack(pcur->_data);
    		}
    	}
    
    	List& operator=(const List& list)//赋值运算符的重载
    	{
    		if (this != &list)
    		{
    			Node* pcur = list._pHead;
    			while (pcur->_next != list._pHead)
    			{
    				PushBack(pcur->_data);
    				pcur = pcur->_next;
    			}
    			PushBack(pcur->_data);
    		}
    		return *this;
    	}
    
    	~List()//析构函数
    	{
    		Clear();//清空函数
    	}
    
    	void Clear()//清空函数
    	{
    		Node* pcur = _pHead;
    		if (pcur == NULL)//空
    			return;
    		_pHead->_pre->_next = NULL;//将循环链表的最后一个节点的next置空
    		Node* pre = NULL;
    		while (pcur)
    		{
    			pre = pcur;
    			pcur = pcur->_next;
    			delete pre;
    		}
    		_pHead = NULL;
    	}
    
    	void PushBack(const DataType data)//尾插
    	{
    		if (NULL == _pHead)//空链表
    		{
    			_pHead = new Node(data);
    			_pHead->_pre = _pHead;
    			_pHead->_next = _pHead;
    		}
    		else//非空
    		{
    			Node* pcur = _pHead;
    			pcur = pcur->_pre;
    			//while (pcur->_next != _pHead)
    			//	pcur = pcur->_next;
    			Node* pNewNode = new Node(data);//创建节点
    			pcur->_next = pNewNode;
    			pNewNode->_pre = pcur;
    			pNewNode->_next = _pHead;
    			_pHead->_pre = pNewNode;
    		}
    	}
    
    	void PopBack()//尾删
    	{
    		if (_pHead == NULL)//空
    			return;
    		else if (_pHead->_next == _pHead)//只有一个节点
    		{
    			delete _pHead;
    			_pHead = NULL;
    		}
    		else//有多个节点
    		{
    			Node* pTailNode = _pHead->_pre;
    			pTailNode->_pre->_next = _pHead;
    			_pHead->_pre = pTailNode->_pre;
    			delete pTailNode;
    		}
    	}
    
    	void PushFront(const DataType data)//头插
    	{
    		if (NULL == _pHead)//空链表
    		{
    			_pHead = new Node(data);
    			_pHead->_next = _pHead;
    			_pHead->_pre = _pHead;
    		}
    		else//非空
    		{
    			Node* pNewNode = new Node(data);
    			Node* pTailNode = _pHead->_pre;
    			_pHead->_pre = pNewNode;
    			pNewNode->_next = _pHead;
    			_pHead = pNewNode;
    			_pHead->_pre = pTailNode;
    			pTailNode->_next = _pHead;
    		}
    	}
    
    	void PopFront()//头删
    	{
    		if (_pHead == NULL)//空链表
    			return;
    		else if (_pHead->_next == _pHead)//只有一个节点
    		{
    			delete _pHead;
    			_pHead = NULL;
    		}
    		else//有多个节点
    		{
    			/*Node* pcur = _pHead->_next;
    			pcur->_pre = _pHead->_pre;
    			_pHead->_pre->_next = pcur;
    			delete _pHead;
    			_pHead = pcur;*///将第二个节点保存
    			Node* pTailNode = _pHead->_pre;//将尾节点保存，两种都可以
    			_pHead = _pHead->_next;
    			delete _pHead->_pre;
    			_pHead->_pre = pTailNode;
    			pTailNode->_next = _pHead;
    		}
    	}
    
    	Node* Find(DataType data)//查找，没找到返回空
    	{
    		Node* pcur = _pHead;
    		if (pcur == NULL)
    			return NULL;
    		while (pcur->_next != _pHead)//最后一个节点数据不会进入循环
    		{
    			if (pcur->_data == data)
    				return pcur;
    			pcur = pcur->_next;
    		}
    		if (pcur->_data == data)//最后一个节点的查找
    			return pcur;
    		return NULL;
    	}

指定位置插入：

![SouthEast 1][]

Node* Insert(Node* pos, const DataType& data)//插入
    	{
    		assert(pos);//对插入点进行断言，避免插入点为空
    		Node* pNewNode = new Node(data);
    		/*pNewNode->_next = pos;//1
    		pNewNode->_pre = pos->_pre;//2
    		pos->_pre->_next = pNewNode;//3
    		pos->_pre = pNewNode;//4*/
    		/*两种都可以*/
    		Node* pcur = pos->_pre;//将pos的前一个节点保存，方便插入
    		pNewNode->_next = pos;
    		pos->_pre = pNewNode;
    		pcur->_next = pNewNode;
    		pNewNode->_pre = pcur;
    		if (pos == _pHead)//如果新插入的节点为头节点，将新节点设为_pHead
    			_pHead = pNewNode;
    		return pNewNode;
    	}
    
    	Node* Erase(Node* pos)//清除指定节点，返回该节点的下一个节点
    	{
    		assert(pos);//对删除点断言，要删除的节点不应该为空
    		if (pos->_next == pos)
    		{
    			delete pos;
    			pos = NULL;
    			return NULL;
    		}
    		Node* pcur = pos->_next;
    		pos->_pre->_next = pos->_next;
    		pos->_next->_pre = pos->_pre;
    		if (pos == _pHead)
    			_pHead = _pHead->_next;
    		delete pos;
    		return pcur;
    	}
    	
    	size_t Size()const//链表节点的个数
    	{
    		Node* pcur = _pHead;
    		size_t count = 1;
    		while (pcur->_next != _pHead)
    		{
    			count++;
    			pcur = pcur->_next;
    		}
    		return count;
    	}
    
    	bool Empty()const//判断链表是否为空，空链表返回1
    	{
    		return _pHead == NULL;
    	}
    
    private:
    	Node* _pHead;
    };
    
    void test2()
    {
    	int arr[5] = { 1,2,3,4,5 };
    	List list1(arr, sizeof(arr) / sizeof(arr[0]));
    	cout << list1 << endl;
    	list1.Insert(list1.Find(5), 8);
    	cout << list1 << endl;
    	//cout << list1.Size() << endl;
    	List list2;
    	cout << list2.Empty()<<endl;
    	list1.Erase(list1.Find(5));
    	cout << list1 << endl;
    	List list3 = list1;
    	cout << list3 << endl;
    }
    void test1()
    {
    	List list1;
    	list1.PushFront(1);
    	list1.PushFront(2);
    	//cout << list1 << endl;
    	int arr[5] = { 1, 2, 3, 4, 5 };
    	List list2(arr, sizeof(arr) / sizeof(arr[0]));
    	//cout << list2 << endl;
    	//list2.PopBack();
    	//cout << list2 << endl;
    	//list2.PopBack();
    	//cout << list2 << endl;
    	//list2.PopBack();
    	//cout << list2 << endl;
    	//list2.PopBack();
    	//cout << list2 << endl;
    	//list2.PopBack();
    	//cout << list2 << endl;
    	//list2.Clear();
    	//cout << list2 << endl;
    	//list2.PushFront(1);
    	//list2.PushFront(2);
    	//list2.PushFront(3);
    	//list2.PushFront(4);
    	//list2.PushFront(5);
    	//cout << list2 << endl;
    	List list3(list2);
    	cout << list3 << endl;
    	list3.PopFront();
    	cout << list3 << endl;
    	list3.PopFront();
    	cout << list3 << endl;
    	list3.PopFront();
    	cout << list3 << endl;
    	list3.PopFront();
    	cout << list3 << endl;
    	list3.PopFront();
    	cout << list3 << endl;
    }
    int main()
    {
    	//test1();
    	test2();
    	return 0;
    }

[SouthEast]: /images/20220607/f3f3b8654fe642a380e28d27fb25b08b.png
[SouthEast 1]: /images/20220607/fde6114d52834f1cb3d7376a1833a3c4.png