C++实现双链表的基本功能

港控/mmm° 2022-07-17 00:14 168阅读 0赞

双链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域

线性表的双向链表存储结构：

typedef struct Node
    {
         DataType _data;
         struct Node *_next;
         struct Node *_front;
    }Node;

通过双链表的存储结构我们发现双链表可以反向查找结点优于单链表 ，实质上双链表就是以空间换取时间，虽然双链表具有可以反向查找数据的优点但是它也存在缺点：在插入和删除一个结点时需要维护两个指针变量，特别是在双链表的插入中指针的指向顺序是不可修改的。

双链表的插入过程：

![Center][]

双链表的删除过程：

![Center 1][]

C++实现双链表的基本功能：

typedef int DataType;
    class LinkList;
    class Node
    {
    	friend LinkList;
    	friend ostream &operator<<(ostream &os,Node &n);
    	friend ostream& operator<<(ostream &os,LinkList &list);
    public:
    	Node(DataType x)
    		:_data(x)
    		,_next(NULL)
    		,_front(NULL)
    	{}
    private:
    	DataType _data;
    	Node *_next;
    	Node *_front;
    };
    ostream &operator<<(ostream &os,Node &n)
    {
    	os<<n._data;
    	return os;
    }
    
    class LinkList
    {
    	friend ostream& operator<<(ostream &os,LinkList &list);
    public:
    	LinkList()
    		:_head(NULL)
    		,_tail(NULL)
    	{}
    	LinkList(const LinkList &list)
    		:_head(NULL)
    		,_tail(NULL)
    	{
    		Node *cur=list._head;
    		while(cur)
    		{
    			Node *tmp=new Node(cur->_data);
    			if(_tail)
    			{
    				_tail->_next=tmp;
    				tmp->_front=_tail;
    				_tail=tmp;
    			}
    			else       //空链表
    			{
    				_head=tmp;
    				_tail=tmp;
    			}
    			cur=cur->_next;
    		}
    	}
    	~LinkList()
    	{
    		Node *cur=_head;
    		while(cur)
    		{
    			Node *del=cur;
    			cur=cur->_next;
    			delete del;
    			del=NULL;
    		}
    	}
    public:
    	void PushBack(DataType x)
    	{
    		Node *NewNode=new Node(x);
    		if(_tail)
    		{
    			_tail->_next=NewNode;
    			NewNode->_front=_tail;
    			_tail=NewNode;
    		}
    		else
    		{
    			_head=NewNode;
    			_tail=NewNode;
    		}
    	}
    	void PopBack()
    	{
    		if(!_head && !_tail)    //空链表
    		{
    			cout<<"链表已空不可尾删"<<endl;
    			return ;
    		}
    		else if(_head == _tail)     //只有一个节点
    		{
    			delete _tail;
    			_head=NULL;
    			_tail=NULL;
    		}
    		else      //至少存在两个节点
    		{
    			Node *tmp=_tail;
    			_tail=tmp->_front;
    			_tail->_next=NULL;
    			delete tmp;
    			tmp=NULL;
    		}
    	}
    	void PushFront(DataType x)
    	{
    		Node *NewNode=new Node(x);
    		if(_head)
    		{
    			Node *tmp=_head;
    			NewNode->_next=tmp;
    			tmp->_front=NewNode;
    		}
    		else
    		{
    			_tail=NewNode;
    		}
    		_head=NewNode;    //更新头
    	}
    	void PopFront()
    	{
    		if(!_head && !_tail)     //空链表
    		{
    			cout<<"链表已空不可头删"<<endl;
    			return ;
    		}
    		else if(_head == _tail)    //只有一个节点
    		{
    			delete _head;
    			_head=NULL;
    			_tail=NULL;
    		}
    		else        //至少存在两个节点
    		{
    			Node *del=_head;
    			_head=del->_next;
    			_head->_front=NULL;
    			delete del;
    			del=NULL;
    		}
    	}
    	Node *FindNum(DataType x)
    	{
    		Node *cur=_head;
    		while(cur)
    		{
    			if(cur->_data == x)
    				return cur;
    			cur=cur->_next;
    		}
    		return NULL;
    	}
    	void Insert(Node *pos,DataType x)    //在指定位置后插
    	{
    		Node *NewNode=new Node(x);
    		if(pos->_next)
    		{
    			NewNode->_front=pos;
    			NewNode->_next=pos->_next;
    			pos->_next->_front=NewNode;
    			pos->_next=NewNode;
    		}
    		else    //在最后一个结点后插，类似PushBack
    		{
    			pos->_next=NewNode;
    			NewNode->_front=pos;
    			_tail=NewNode;    //更新尾
    		}
    	}
    	void Insert(int,Node *pos,DataType x)   //在指定位置前插
    	{
    		Node *NewNode=new Node(x);
    		if(pos->_front)
    		{
    			NewNode->_next=pos;
    			pos->_front->_next=NewNode;
    			NewNode->_front=pos->_front;
    			pos->_front=NewNode;
    		}
    		else   //在第一个结点的前插，类似PushFront
    		{
    			NewNode->_next=pos;
    			pos->_front=NewNode;
    			_head=NewNode;    //更新头
    		}
    	}
    	void Remove(DataType &x)
    	{
    		Node *pos=this->FindNum(x);
    		if(pos != NULL)
    		{
    			if((!(pos->_front)) && pos->_next)    //删除第一个结点
    			{
    					Node *tmp=pos->_next;
    				    tmp->_front=NULL;
    				    _head=tmp;
    			}
    			else if(pos->_front && (!(pos->_next)))   //删除最后一个结点
    			{
    				Node *tmp=pos->_front;
    				tmp->_next=NULL;
    				_tail=tmp;
    			}
    			else             //删除中间节点
    			{
    				Node *front=pos->_front;
    				Node *next=pos->_next;
    				next->_front=front;
    				front->_next=next;
    			}
    			delete pos;
    			pos=NULL;
    		}
    	}
    	void RemoveAll(DataType &x)
    	{
    		Node *cur=_head;
    		Node *ret=this->FindNum(x);
    		if(ret != _head)    //可删除第一个结点不是要删除的元素
    		{
    			while(cur)
    			{
    				Remove(x);
    				cur=cur->_next;
    			}
    		}
    	}
    	void Sort()
    	{
    		int flag=1;
    		Node *cur=_head;
    		Node *tail=NULL;
    		while(cur != tail)
    		{
    			while(cur->_next != tail)
    			{
    				if(cur->_data > cur->_next->_data)
    				{
    					DataType tmp=cur->_data;
    					cur->_data=cur->_next->_data;
    					cur->_next->_data=tmp;
    					flag=0;
    				}
    				cur=cur->_next;
    			}
    			if(flag == 1)
    				break;
    			tail=cur;
    			cur=_head;
    		}
    	}
    	void Erase(Node *pos)
    	{
    		if((!(pos->_front)) && pos->_next)    //删除第一个结点
    		{
    				Node *tmp=pos->_next;
    				tmp->_front=NULL;
    				_head=tmp;
    		}
    		else if(pos->_front && (!(pos->_next)))   //删除最后一个结点
    		{
    			Node *tmp=pos->_front;
    			tmp->_next=NULL;
    			_tail=tmp;
    		}
    		else             //删除中间节点
    		{
    			Node *front=pos->_front;
    			Node *next=pos->_next;
    			next->_front=front;
    			front->_next=next;
    		}
    		delete pos;
    		pos=NULL;
    	}
    private:
    	Node *_head;
    	Node *_tail;
    };
    
    ostream& operator<<(ostream &os,LinkList &list)
    {
    	Node *cur=list._head;
    	while(cur)
    	{
    		os<<(*cur)<<" ";
    		cur=cur->_next;
    	}
    	return os;
    }

在C++实现中如果遇到结点结构最好定义为struct，否则就会像上述情况一样需要声明多次友元，反而破坏了类的封装性  
测试代码：

void menu()
    {
    	cout<<"************1.尾插************2.尾删**************"<<endl;
    	cout<<"************3.头插************4.头删**************"<<endl;
    	cout<<"************5.指定位置后插****6.指定位置前插******"<<endl;
    	cout<<"************7.删除指定元素****8.删除所有指定元素**"<<endl;
    	cout<<"************9.排序************0.退出*************"<<endl;
    	cout<<"************11.Erase**********0.退出*************"<<endl;
    }
    
    void test()
    {
    	LinkList list;
    	Node *ret=NULL;
    	int input=1;
    	DataType x,num;
    	while(input)
    	{
    		menu();
    		cout<<"请输入您的选择>";
    		cin>>input;
    		switch(input)
    		{
    		case 1:
    			cout<<"请输入您要插入的数据>";
    			cin>>x;
    			list.PushBack(x);
    			break;
    		case 2:
    			list.PopBack();
    			break;
    		case 3:
    			cout<<"请输入您要插入的数据>";
    			cin>>x;
    			list.PushFront(x);
    			break;
    		case 4:
    			list.PopFront();
    			break;
    		case 5:
    			cout<<"请输入您要查找的数据>";
    			cin>>x;
    			ret=list.FindNum(x);
    			if(ret != NULL)
    			{
    				cout<<"请输入您要插入的数据>";
    			    cin>>num;
    			    list.Insert(ret,num);
    			}
    			else
    			{
    				cout<<"您所查找的数据不存在"<<endl;
    			}
    			break;
    		case 6:
    			cout<<"请输入您要查找的数据>";
    			cin>>x;
    			ret=list.FindNum(x);
    			if(ret != NULL)
    			{
    				cout<<"请输入您要插入的数据>";
    			    cin>>num;
    			     list.Insert(0,ret,num);  //0用于占位，构成重载
    			}
    			else
    			{
    				cout<<"您所查找的数据不存在"<<endl;
    			}
    			break;
    		case 7:
    			cout<<"请输入您要删除的数据>";
    			cin>>x;
    			list.Remove(x);
    			break;
    		case 8:
    			cout<<"请输入您要删除的数据>";
    			cin>>x;
    			list.RemoveAll(x);
    			break;
    		case 9:
    			list.Sort();
    			break;
    		case 10:
    			cout<<list<<endl;
    			break;
    		case 11:
    			cout<<"请输入您要擦除的数据>";
    			cin>>x;
    			ret=list.FindNum(x);
    			if(ret != NULL)
    			{
    				list.Erase(ret);
    			}
    			else
    			{
    				cout<<"您所查找的数据不存在"<<endl;
    			}
    			break;
    		case 0:
    			break;
    		default:
    			cout<<"您的输入错误"<<endl;
    			break;
    		}
    	}
    }

OVER

[Center]: /images/20220717/f4928e6a604c44d987b1f7c7a62b41bc.png
[Center 1]: /images/20220717/631ee5c316624b6384f174df89d7dc9a.png