C++实现双向链表

浅浅的花香味﹌ 2022-01-13 18:43 304阅读 0赞

双向链表结构图：

[![wKiom1b2TPjA07T8AAAQhFFQvOI122.png][]][wKiom1b2TPjA07T8AAAQhFFQvOI122.png]

节点结构：

[![wKiom1b2TYSRnhYLAAANwuuYwz8829.png][]][wKiom1b2TYSRnhYLAAANwuuYwz8829.png]

代码实现：

/*DList.h*/
    
    #pragma once
    
    #include <iostream>
    #include <cassert>
    using namespace std;
    
    typedef int DataType;
    struct Node
    {
    	Node(const DataType& x)
    		:_data(x)
    		,_next(NULL)
    		,_prev(NULL)
    	{}
    	DataType _data;	//数据
    	Node* _next;    //后继
    	Node* _prev;	//前驱
    };
    
    class DList
    {
    public:
    	DList()
    		:_head(NULL),_tail(NULL)
    	{}
    	~DList()
    	{
    		Node* cur = _head;
    		while(cur)
    		{
    			Node* del = cur;
    			cur = cur->_next;
    			delete del;
    		}
    	}
    public:
    	void Display();	//打印链表
    	void PushBack(const DataType& x);	//尾插
    	void PushFront(const DataType& x);	//头插
    	void PopBack();						//尾删
    	void PopFront();					//头删
    	int DListLength();					//求链表长度
    	Node* Find(const DataType& x);		//找元素x位置
    	void Erase(Node* pos);				//删除pos位置元素
    	void Remove(const DataType& x);		//删除指定元素x
    	void RemoveAll(const DataType& x);	//删除所有元素x
    	void InsertBack(Node* pos, const DataType& x);	//在pos位置后面插入x
    	void InsertFront(Node* pos,const DataType& x);	//在pos位置前面插入x
    	void Sort();		//排序(元素递增方式)
    	void Reverse();		//反转链表
    private:
    	Node* _head;	//头管理
    	Node* _tail;	//尾管理
    };

/*DList.cpp*/
    
    #include "DList.h"
    
    void DList::Display()
    {
    	Node* cur = _head;
    	while(cur)
    	{
    		cout<<cur->_data<<"-->";
    		cur = cur->_next;
    	}
    	cout<<"Nvl."<<endl;
    }
    void DList::PushBack(const DataType& x)
    {
    	Node* NewNode = new Node(x);
    	if(_head == NULL)
    	{
    		_head = NewNode;
    		_tail = _head;
    	}
    	else
    	{
    		_tail->_next = NewNode;
    		NewNode->_prev = _tail;
    		_tail = NewNode;
    	}
    }
    void DList::PushFront(const DataType& x)
    {
    	Node* NewNode = new Node(x);
    	if(_head == NULL)
    	{
    		_head = _tail = NewNode;
    	}
    	else
    	{
    		_head->_prev = NewNode;
    		NewNode->_next = _head;
    		_head = NewNode;
    	}
    }
    void DList::PopBack()
    {
    	if(_head == NULL)
    	{
    		cout<<"List is empty!!"<<endl;
    		return;
    	}
    	Node* del = _tail;
    	_tail = _tail->_prev;
    	if(_tail != NULL)		//有节点时，将为指针后继置空
    		_tail->_next = NULL;
    	delete del;
    }
    void DList::PopFront()
    {
    	if(_head == NULL)
    	{
    		cout<<"List is empty!!"<<endl;
    		return;
    	}
    	Node* del = _head;
    	_head = _head->_next;
    	if(_head != NULL)		//有节点时，将头指针前驱置空
    		_head->_prev = NULL;
    	delete del;
    
    }
    int DList::DListLength()
    {
    	Node* cur = _head;
    	int count = 0;
    	while(cur)
    	{
    		count++;
    		cur = cur->_next;
    	}
    	return count;
    }
    Node* DList::Find(const DataType& x)
    {
    	Node* cur = _head;
    	while(cur)
    	{
    		if(cur->_data == x)
    		{
    			return cur;
    		}
    		cur = cur->_next;
    	}
    	return NULL;
    }
    void DList::Erase(Node* pos)
    {
    	assert(pos);
    	if(_head == NULL)  //无节点
    	{
    		cout<<"List is empty!!"<<endl;
    		return;
    	}
    	else if(pos == _head && pos == _tail)	//一个节点
    	{
    		delete _head;
    		_head = _tail = NULL;
    	}
    	else if(pos == _head && pos != _tail)//pos是头结点，并且不是尾节点，头删
    	{
    		PopFront();
    	}
    	else if(pos == _tail && pos != _head)//pos是尾节点，并且不是头结点，尾删
    	{
    		PopBack();
    	}
    	else
    	{
    		Node* del = pos;
    		pos->_next->_prev = pos->_prev;
    		pos->_prev->_next = pos->_next;
    		delete pos;
    	}
    }
    void DList::Remove(const DataType& x)
    {
    	Node* del = Find(x);
    	Erase(del);
    }
    void DList::RemoveAll(const DataType& x)
    {
    	while(Node* del = Find(x))
    	{
    		Erase(del);
    	}
    }
    void DList::InsertBack(Node* pos, const DataType& x)
    {
    	assert(pos);
    	Node* NewNode = new Node(x);
    	if(_head == NULL)
    	{
    		cout<<"please establish Dlist!!"<<endl;
    		return;
    	}
    	else if(pos == _tail)
    	{
    		PushBack(x);
    	}
    	else
    	{
    		NewNode->_next = pos->_next;
    		pos->_next->_prev = NewNode;
    		pos->_next = NewNode;
    		NewNode->_prev = pos;
    	}	
    }
    void DList::InsertFront(Node* pos, const DataType& x)
    {
    	assert(pos);
    	Node* NewNode = new Node(x);
    	if(_head == NULL)
    	{
    		cout<<"please establish Dlist!!"<<endl;
    		return;
    	}
    	else if(pos == _head)
    	{
    		PushBack(x);
    	}
    	else
    	{
    		pos->_prev->_next = NewNode;
    		NewNode->_prev = pos->_prev;
    		NewNode->_next = pos;
    		pos->_prev = NewNode;
    	}
    }
    void DList::Sort()
    {
    	Node* cur = _head;
    	Node* end = _tail->_next;
    	while(cur != end)
    	{
    		while(cur && (cur->_next != end))
    		{
    			if(cur->_data > cur->_next->_data)
    			{
    				swap(cur->_data, cur->_next->_data);
    			}
    			cur = cur->_next;
    		}
    		end = cur;
    		cur = _head;
    	}
    }
    void DList::Reverse()
    {
    	Node* cur = _head;
    	while(cur)
    	{
    		swap(cur->_next, cur->_prev);
    		cur = cur->_prev;
    	}
    	swap(_head, _tail);
    }

/*Test.cpp*/
    
    
    #include "DList.h"
    
    void Test()
    {
    	DList Dl;
    	int i = 0;
    	while(i<5)
    	{
    		Dl.PushBack(i);
    		i++;
    	}
    	Dl.Display();
    	while(i<10)
    	{
    		Dl.PushFront(i);
    		i++;
    	}
    	Dl.Display();
    	i = Dl.DListLength();
    	cout<<"DList Length = "<<i<<endl;
    	Node* ret = Dl.Find(4);
    	Dl.InsertFront(ret, 100);
    	Dl.Display();
    	Dl.Erase(ret);
    	Dl.Display();
    	Dl.PopFront();
    	Dl.Display();
    	Dl.Remove(0);
    	Dl.Display();
    	Dl.PushBack(1);
    	Dl.PushBack(1);
    	Dl.PushBack(11);
    	Dl.PushBack(1);
    	Dl.PushBack(1);
    	Dl.Display();
    	Dl.RemoveAll(1);
    	Dl.Display();
    	Dl.Reverse();
    	Dl.Display();
    	Dl.Sort();
    	Dl.Display();
    }
    
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }

结果：

[![wKioL1b2QufxabETAAAalBzVw\_U600.png][wKioL1b2QufxabETAAAalBzVw_U600.png]][wKioL1b2QufxabETAAAalBzVw_U600.png]

传说中，还有双向循环链表 ！！

转载于:https://blog.51cto.com/xujiafan/1755488

[wKiom1b2TPjA07T8AAAQhFFQvOI122.png]: /images/20220113/f50f28f1567946c984a838bea4d83b53.png
[wKiom1b2TYSRnhYLAAANwuuYwz8829.png]: https://s1.51cto.com/wyfs02/M02/7E/12/wKiom1b2TYSRnhYLAAANwuuYwz8829.png
[wKioL1b2QufxabETAAAalBzVw_U600.png]: https://s1.51cto.com/wyfs02/M01/7E/0E/wKioL1b2QufxabETAAAalBzVw_U600.png