雙向循環鏈表-----C++

雙向循環鏈表-----C++

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
// define double-circular-linked-list-node
struct ListNode
{
	DataType _data;
	ListNode* _prev;
	ListNode* _next;
};
class DCListNode//double-circular-linked-list-node的簡稱
{
public:
	ListNode* NewNode(const DataType& x)
	{
		ListNode* cur = new ListNode;
		cur->_data = x;
		cur->_next = NULL;
		cur->_prev = NULL;
		return cur;
	}
	void Print()
	{
		if (_phead == NULL)
		{
			;//因為函數最後有cout<<"null"<<endl;
		}
		else if (_phead->_next == _phead)
		{
			cout << _phead->_data << "-";
		}
		else
		{
			ListNode* cur = _phead;
			while (cur->_next != _phead)
			{
				cout << cur->_data << "-";
				cur = cur->_next;
			}
			cout << cur->_data << "-";//因為此時cur指向最後一個節點
			
		}
		cout << "null" << endl;
	}
	void PushBack(DataType x)
	{
		ListNode* cur = NewNode(x);
		if (_phead == NULL)
		{
			_phead = cur;
			cur->_next = _phead;
			cur->_prev = _phead;
		}
		else if (_phead->_next == _phead)
		{
			_phead->_next = cur;
			cur->_prev = _phead;
			cur->_next = _phead;
			_phead->_prev = cur;
		}
		else
		{
			ListNode* tem = _phead->_prev;
			tem->_next = cur;
			cur->_prev = tem;
			cur->_next = _phead;
			_phead->_prev = cur;
		}
	}
	void PopBack()
	{
		if (_phead == NULL)
		{
			return;
		}
		else if (_phead->_next == _phead)
		{
			_phead = NULL;
		}
		else if (_phead->_next->_next == _phead)
		{
			_phead->_next = _phead;
			_phead->_prev = _phead;
		}
		else
		{
			ListNode* tem = _phead->_prev->_prev;
			tem->_next = _phead;
			_phead->_prev = tem;
		}
	}
	ListNode* Find(DataType x)
	{
		ListNode* cur = _phead;
		if (_phead == NULL)
		{
			return NULL;
		}
		else if (_phead->_next == _phead)
		{
			if (_phead->_data == x)
			{
				return _phead;
			}
			else
			{
				return NULL;
			}
		}
		else
		{
			if (cur->_prev->_data == x)
			{
				return cur->_prev;//因為後面的循環不能遍歷到最後一個節點
			}
			while (cur->_next != _phead)
			{
				if (cur->_data == x)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return NULL;
		}
	}
	void Insert(ListNode* pos,const DataType& x)
	{
		assert(pos);
		ListNode* cur = NewNode(x);
		if (pos->_next != _phead)
		{
			ListNode* tem = pos->_next;
			pos->_next = cur;
			cur->_prev = pos;
			cur->_next = tem;
			tem->_prev = cur;
		}
		else
		{
			pos->_next = cur;
			cur->_prev = pos;
			cur->_next = _phead;
			_phead->_prev = cur;
		}
	}
	/*void Erase(ListNode* pos)
	{
		assert(pos);
		if (_phead->_next == _phead)
		{
			delete pos;
			_phead = NULL;
		}
		else
		{
			ListNode* prev = pos->_prev;
			ListNode* next = pos->_next;
			prev->_next = next;
			next->_prev = prev;
			next->_next = prev;
			prev->_prev = next;
			_phead = next;
			delete pos;
		}
	}*/
	void Erase(ListNode* pos)
	{
		assert(pos);
		if (_phead->_next == _phead)//只有一個節點
		{
			delete pos;
			_phead = NULL;
		}
		ListNode* next = pos->_next;
		ListNode* pre = pos->_prev;
		if (pos == _phead)// 刪除的節點為頭節點
		{
			next->_prev = pre;
			pre->_next = next;
			_phead = next;
			delete pos;
		}
		else if (pos->_next == _phead)//刪除的節點為尾節點
		{
			pre->_next = next;
			next->_prev = pre;
			delete pos;
		}
		else//刪除的節點為中間節點
		{
			pre->_next = next;
			next->_prev = pre;
			delete pos;
		}
	}
public:
	DCListNode(ListNode* phead = NULL)
		:_phead(phead)
	{}
	~DCListNode()
	{
		clear();
	}
	void clear()
	{
		if (_phead == NULL)
		{
			;
		}
		else if (_phead->_next == _phead)
		{
			delete _phead;
			_phead = NULL;
		}
		else
		{
			ListNode* cur = _phead;
			while (cur->_next != _phead)
			{
				ListNode* del = cur;
				cur = cur->_next;
				delete del;
				del = NULL;
			}
			delete cur;//因為此時cur指向最後一個節點
			cur = NULL;
		}
	}
private:
	ListNode* _phead;
};
//test PushBack()  PopBack()
void test1()
{
	DCListNode s1;
	s1.PushBack(1);
	s1.PushBack(2);
	s1.PushBack(3);
	s1.PushBack(4);
	s1.PushBack(5);
	s1.Print();
	s1.PopBack();
	s1.Print();
	s1.PopBack();
	s1.Print();
	s1.PopBack();
	s1.Print();
	s1.PopBack();
	s1.Print();
	s1.PopBack();
	s1.Print();
	s1.PopBack();
	s1.Print();
}
//test Find()  Insert()  Erase()
void test2()
{
	DCListNode s1;
	s1.PushBack(1);
	s1.PushBack(2);
	s1.PushBack(3);
	s1.PushBack(4);
	s1.PushBack(5);
	cout << (s1.Find(2))->_data << endl;
	ListNode* p1 = s1.Find(2);
	s1.Insert(p1, 10);
	s1.Print();
	cout << (s1.Find(5))->_data << endl;
	ListNode* p2 = s1.Find(5);
	s1.Insert(p2, 20);
	s1.Print();
	ListNode* p3 = s1.Find(3);
	s1.Erase(p3);
	s1.Print();
}
int main()
{
	//test1();
	test2();
	system("pause");
	return 0;
}