C++ 单链表与迭代器generic 模板类

数据结构–单链表

本以为单链表会比双链表简单，结果花了好几个晚上才把它搞定…
不带头节点的单链表，基本功能其实不难实现，但是迭代器调试了半天

 #pragma once
 #include <iostream>
 using namespace std;
 
 template <typename Type>
 struct Node
 {
 	Type data;
 	Node<Type> *next;     
 	Node<Type>(Node<Type> *ptr = NULL) { next = ptr; };
 	Node<Type>(const Type &_data, Node<Type> *ptr = NULL) { data = _data; next = ptr; }
 	
 };
 template <typename Type> class SLLIter;
 template <typename Type>
 class SLList
 {
 private:
 
 	Node<Type> *head;
 
 public:
 	friend class SLLIter<Type>;
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : Constructor
 	// Notes : constructs an empty list
 	/////////////////////////////////////////////////////////////////////////////
 	SLList() 
 	{
 		head =NULL;
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : Destructor
 		// Notes : Destroys the list
 		/////////////////////////////////////////////////////////////////////////////
 	~SLList() 
 	{
 		clear();
 		delete head;
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : Assignment Operator
 		/////////////////////////////////////////////////////////////////////////////
 	SLList<Type>& operator=(const SLList<Type>& that)
 	{
 		if (this == &that) {
 			return *this;
 		}
 		else {
 		clear();  
 		if (that.head == NULL) {
 			head = NULL;
 		}
 		else {
 			head = new Node<Type>(that.head->data);
 			Node<Type> *p1 = head;
 			Node<Type> *p2 = that.head->next;
 			unsigned int num = 1;
 			while (num < that.size()) {
 				p1->next = new Node<Type>(p2->data); 
 				p2 = p2->next;
 				p1 = p1->next;
 				num++;
 			}
 			p1->next = NULL;
 		}
 		}
 		return *this;
 	};
 
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : Copy Constructor
 		/////////////////////////////////////////////////////////////////////////////
 	SLList(const SLList<Type>& that)
 	{
 		head = NULL;
 		operator= (that);
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : addHead
 		// Parameters :	v - the item to add to the list
 		/////////////////////////////////////////////////////////////////////////////
 	void addHead(const Type& v)
 	{	
 
 		Node<Type> *tmp = new Node<Type>(v);
 		tmp->next = head;
 		head= tmp;
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : clear
 		// Notes : clears the list, freeing any dynamic memory
 		/////////////////////////////////////////////////////////////////////////////
 	void clear()
 	{
 		Node<Type>* begin = head;
 		while (begin != NULL)
 		{
 			head = head->next;
 			delete begin;
 			begin = head;
 		}
 		head = NULL;
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : insert
 		// Parameters :	index - an iterator to the location to insert at
 		//				v - the item to insert
 		// Notes : do nothing on a bad iterator
 		/////////////////////////////////////////////////////////////////////////////
 	void insert(SLLIter<Type>& index, const Type& v)
 	{;
 		if (index.cur==NULL||head==NULL)
 		{}//do nothing
 		else 
 		{
 			if (index.cur==head)
 			{
 				addHead(v);
 				index.cur = head;
 			}
 			else
 			{
 			Node<Type> *pre = head;
 			while (pre->next != index.cur)
 			{
 				pre = pre->next;
 			}
 			Node<Type> *tmp = new Node<Type>(v);
 			tmp->next = pre->next;
 			pre->next = tmp;
 			index.cur = tmp;
 			}
 			//else 
 			//{
 			//	
 			//	/*Node<Type> *tmp = new Node<Type>(v);
 			//	Node<Type>*current = head;
 			//	while (current->next != index.cur)
 			//	{
 			//		current = current->next;
 			//	}
 			//	tmp->next = index.cur;
 			//	current->next = tmp;*/
 			//
 			//}
 
 		}
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : remove
 		// Parameters :	index - an iterator to the location to remove from
 		// Notes : do nothing on a bad iterator
 		/////////////////////////////////////////////////////////////////////////////
 	void remove(SLLIter<Type>& index)
 	{
 		if (index.cur == NULL || head == NULL)
 		{
 			return;
 		}//do nothing
 		else
 		{
 			if (index.cur == head)
 			{
 				Node<Type> *tmp = head;
 				head = head->next;
 				delete tmp;
 				index.cur = head;
 			}
 			else
 			{
 				Node<Type>* prev = head;
 				while (prev->next != index.cur)
 				{
 					prev = prev->next;
 				}
 				prev->next = index.cur->next;
 				Node<Type>* temp = index.cur;
 				if (index.cur->next)
 					index.cur = index.cur->next;
 				else
 					index.cur = NULL;
 				delete temp;
 			}
 
 		}
 	};
 
 		/////////////////////////////////////////////////////////////////////////////
 		// Function : size
 		// Return : the number of items stored in the linked list.
 		/////////////////////////////////////////////////////////////////////////////
 			unsigned int size() const
 		{
 				if (head == NULL)
 				{
 					return 0;
 				}
 				else
 				{
 					int count = 0;
 					Node<Type> *cur = head;
 					while (cur != NULL)
 					{
 						count++;
 						cur = cur->next;
 					}
 					return count;
 				}
 			
 		};
 };
 
 template <typename Type>
 	class  SLLIter
 {
 		friend class SLList<Type>;
 private:
 	const SLList<Type> *list;
 	Node<Type>* cur;
 public:
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : Constructor
 	// Parameters :	listToIterate - the list to iterate
 	/////////////////////////////////////////////////////////////////////////////
 	SLLIter(const SLList<Type>& listToIterate) 
 		{
 		list = &listToIterate;
 		cur = list->head;
 		};
 
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : begin
 	// Notes : moves the iterator to the head of the list
 	/////////////////////////////////////////////////////////////////////////////
 		void begin() 
 		{
 			if (list->head != NULL)
 			{
 				cur = list->head;
 			}
 			else
 			{
 				cur = NULL;
 			}
 		};
 
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : end
 	// Notes : returns true if we are at the end of the list, false otherwise
 	/////////////////////////////////////////////////////////////////////////////
 		bool end() const
 		{
 			if (cur)
 			{
 					return false;
 			}
 			else
 			{
 				return true;
 			}
 		};
 
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : operator++
 	// Notes : move the iterator forward one node
 	/////////////////////////////////////////////////////////////////////////////
 		SLLIter<Type>& operator++() 
 		{
 			if (cur != NULL && cur->next != NULL)
 			{
 				cur = cur->next;
 			}
 			else {
 				cur = NULL;
 			}
 			return *this;
 		};
 
 	/////////////////////////////////////////////////////////////////////////////
 	// Function : current
 	// Notes : returns the item at the current iterator location
 	/////////////////////////////////////////////////////////////////////////////
 		Type& current() const
 		{
 			if(cur==NULL)
 			{ }
 				return cur->data;
 		};
 	};