迭代器的使用之双向循环链表

迷南。 2022-09-26 01:59 75阅读 0赞

# 模拟实现迭代器和用迭代器的方式实现双向循环链表 #

**什仫是迭代器？>**

迭代器是一个抽象的设计概念，它的定义为：提供一种方法，使之能够依序巡访某个容器所含的各个元素，而又无需暴露该聚合物的内部表述方式.

**迭代器的设计思维>**

将数据容器和算法分开，彼此独立设计，最后再以一帖胶着剂将他们撮合在一起.

**迭代器到底是什仫呢？>**

迭代器是类似智能指针的对象,在实现中我们可以想当然的把它看作一个指针对象而已.下面是智能指针的一点介绍：

[http://blog.csdn.net/qq\_34328833/article/details/52432418][http_blog.csdn.net_qq_34328833_article_details_52432418]

\--------------------------------------------

**双向循环链表>**

将双链表的终端结点的后继指针域由空指针改为指向头结点，而头结点的前驱指针域指向的则是终端结点，这种头尾相接的双链表称为双向循环链表.

**双向循环链表的插入和删除>**

![Center][]

\-------------------------------------

**下面就让我们开始造轮子**

模拟实现一个简单的迭代器：

template<class T,class Ref,class Ptr>
    struct Iterator
    {
    	typedef LinkNode<T> Node;
    	typedef Iterator<T,Ref,Ptr> Sef;
    
    	Iterator(Node *node)
    		:_node(node)
    	{}
    	Iterator()   //默认的构造函数
    	{}
    
    	bool operator == (const Sef& s)const
    	{
    		return _node == s._node;
    	}
    	bool operator != (const Sef& s)const
    	{
    		return _node != s._node;
    	}
    	Ref operator*()
    	{
    		return _node->_data;
    	}
    	Ptr operator->()
    	{
    		return _node;
    	}
    	Sef& operator++()   //前置++
    	{
    		_node=_node->_next;
    		return *this;
    	}
    	Sef operator++(int)   //后置++
    	{
    		Sef tmp(*this);
    		_node=_node->_next;
    		return tmp;
    	}
    	Sef& operator--()     //前置--
    	{
    		_node=_node->_prev;
    		return *this;
    	}
    	Sef operator--(int)   //后置--
    	{
    		Sef tmp(*this);
    		_node=_node->_prev;
    		return tmp;
    	}
    	Node *_node;
    };

模拟实现双向循环链表：

#pragma once
    #include<iostream>
    #include<cassert>
    using namespace std;
    
    template<class T>
    struct LinkNode
    {
    	LinkNode<T> *_next;
    	LinkNode<T> *_prev;
    	T _data;
    	LinkNode(const T& x)
    		:_data(x)
    		,_next(NULL)
    		,_prev(NULL)
    	{}
    };
    
    template<class T,class Ref,class Ptr>
    struct Iterator
    {
    	typedef LinkNode<T> Node;
    	typedef Iterator<T,Ref,Ptr> Sef;
    
    	Iterator(Node *node)
    		:_node(node)
    	{}
    	Iterator()   //默认的构造函数
    	{}
    
    	bool operator == (const Sef& s)const
    	{
    		return _node == s._node;
    	}
    	bool operator != (const Sef& s)const
    	{
    		return _node != s._node;
    	}
    	Ref operator*()
    	{
    		return _node->_data;
    	}
    	Ptr operator->()
    	{
    		return _node;
    	}
    	Sef& operator++()   //前置++
    	{
    		_node=_node->_next;
    		return *this;
    	}
    	Sef operator++(int)   //后置++
    	{
    		Sef tmp(*this);
    		_node=_node->_next;
    		return tmp;
    	}
    	Sef& operator--()     //前置--
    	{
    		_node=_node->_prev;
    		return *this;
    	}
    	Sef operator--(int)   //后置--
    	{
    		Sef tmp(*this);
    		_node=_node->_prev;
    		return tmp;
    	}
    	Node *_node;
    };
    
    template<class T>
    class LinkList
    {
    	typedef LinkNode<T> Node;
    public:
    	typedef Iterator<T,T&,T*> LinkIterator;
    
    	LinkList()
    	{
    		_head=CreatNode(T()); //传默认参数
    		_head->_next=_head;   //设置哨兵
    		_head->_prev=_head;
    	}
    	LinkList(const LinkList<T>& l)
    	{
    		_head=CreatNode(T());
    		_head->_next=_head;
    		_head->_prev=_head;
    
    		Node *cur=l._head->_next;
    		while(cur != l._head)
    		{
    			Insert(End(),cur->_data);
    			cur=cur->_next;
    		}
    	}
    	LinkList<T>& operator=(LinkList<T> l)
    	{
    		std::swap(_head,l._head);
    		return *this;
    	}
    	~LinkList()
    	{
    		Node *cur=_head->_next;
    		while(cur != _head)
    		{
    			Node *del=cur;
    			cur=cur->_next;
    			delete del;
    			del=NULL;
    		}
    		delete _head;
    	}
    public:
    	//void PushBack(const T& x)
    	//{
    	//	Node *tail=_head->_prev;
    	//	Node *NewNode=CreatNode(x);
    	//	tail->_next=NewNode;
    	//	NewNode->_prev=tail;
    
    	//	NewNode->_next=_head;
    	//	_head->_prev=NewNode;
    	//}
    	void PushBack(const T& x)
    	{
    		Insert(End(),x);
    	}
    	void PushFront(const T& x)
    	{
    		Insert(Begin(),x);
    	}
    	void PopBack()
    	{
    		Erase(--End());
    	}
    	void PopFront()
    	{
    		Erase(Begin());
    	}
    	void Insert(LinkIterator pos,const T& x)  //在指定位置前插
    	{
    		Node *cur=pos._node;
    		Node *prev=cur->_prev;
    		Node *NewNode=CreatNode(x);
    
    		NewNode->_next=cur;
    		cur->_prev=NewNode;
    		prev->_next=NewNode;
    		NewNode->_prev=prev;
    	}
    	void Erase(LinkIterator pos)
    	{
    		assert(pos != End());   //删除的不是哨兵
    		Node *del=pos._node;
    		del->_prev->_next=del->_next;
    		del->_next->_prev=del->_prev;
    		delete del;
    		del=NULL;
    	}
    	LinkIterator Begin()
    	{
    		return LinkIterator(_head->_next);
    	}
    	LinkIterator End()
    	{
    		return LinkIterator(_head);
    	}
    protected:
    	Node* CreatNode(const T& x)
    	{
    		Node *NewNode=new Node(x);
    		return NewNode;
    	}
    protected:
    	Node* _head;
    };

测试代码：

void testIterator()
    {
    	LinkList<int> l;
    
    	for(int i=0;i<10;i++)
    	{
    		l.PushBack(i+1);
    	}
    	LinkList<int>::LinkIterator it=l.Begin();
    	while(it != l.End())
    	{
    		cout<<*it<<" ";
    		++it;
    	}
    	cout<<endl;
    	
    	for(int i=0;i<10;i++)
    	{
    		l.PopBack();
    	}
    	LinkList<int>::LinkIterator it1=l.Begin();
    	while(it1 != l.End())
    	{
    		cout<<*it1<<" ";
    		++it1;
    	}
    	cout<<endl;
    }
    
    void test1()
    {
    	LinkList<int> l1;
    	for(int i=0;i<10;i++)
    	{
    		l1.PushFront(i+1);
    	}
    
    	LinkList<int>::LinkIterator it=l1.Begin();
    	while(it != l1.End())
    	{
    		cout<<*it<<" ";
    		++it;
    	}
    	cout<<endl;
    
    	for(int i=0;i<10;i++)
    	{
    		l1.PopFront();
    	}
    	LinkList<int>::LinkIterator it1=l1.Begin();
    	while(it1 != l1.End())
    	{
    		cout<<*it1<<" ";
    		++it1;
    	}
    	cout<<endl;
    }
    
    void test2()
    {
    	LinkList<int> l1;
    	l1.PushBack(1);
    	l1.PushBack(2);
    	l1.PushBack(3);
    	l1.PushBack(4);
    
    	LinkList<int>::LinkIterator it=l1.Begin();
    	while(it != l1.End())
    	{
    		cout<<*it<<" ";
    		++it;
    	}
    	cout<<endl;
    	//1 2 3 4
    	LinkList<int> l2(l1);
    	l2.PushBack(5);
    	LinkList<int>::LinkIterator it1=l2.Begin();
    	while(it1 != l2.End())
    	{
    		cout<<*it1<<" ";
    		++it1;
    	}
    	cout<<endl;
    	//1 2 3 4 5
    	l1=l2;
    	LinkList<int>::LinkIterator it2=l1.Begin();
    	while(it2 != l1.End())
    	{
    		cout<<*it2<<" ";
    		++it2;
    	}
    	cout<<endl;
    	//1 2 3 4 5
    }

\-------------------------------------

对于迭代器的理解和简单模拟就结束了....

[http_blog.csdn.net_qq_34328833_article_details_52432418]: http://blog.csdn.net/qq_34328833/article/details/52432418
[Center]: /images/20220717/c8c447e9feb046d6954035cbe43bac23.png