enhancedlinkedlist.h

模拟数据结构的链表

#include <stdexcept>
#include "LinkedList.h"
using namespace std;

class ListItemNotFoundException : public logic_error {

public:
    ListItemNotFoundException() throw() :
    logic_error ("No ListItem was found ! " ) {}}
;

template <class T>

class EnhancedLinkedList : public LinkedList<T> {


public:
	EnhancedLinkedList() : LinkedList<T>(){}

	T& find_first(const T& key);
	
	EnhancedLinkedList find_all (const T& key);

	void remove_first (const T& key); 

	void remove_all(const T& key);
};


template<class T>

T& EnhancedLinkedList<T>:: find_first(const T& key)
{
	 Node<T>* current = head;
	 if(empty())
	 {
		 throw EmptyListException("find_first()");
	 }
        while (current != NULL) {
            if(current->getData() == key)
				return current->getData();
			current = current->getNext();
        }
		throw ListItemNotFoundException();
		
}

template<class T>

EnhancedLinkedList<T> EnhancedLinkedList<T>:: find_all (const T& key)
{
	EnhancedLinkedList<T> temList;
	Node<T>* current = head;
	if(empty())
	 {
		 throw EmptyListException("find_all()");
	 }
        while (current != NULL) {
            if(current->getData() == key)
			{
				temList.push_back(key);
			}
			current = current->getNext();
        }
		return temList;
}

template<class T>

void EnhancedLinkedList<T> :: remove_first (const T& key)
{	
	Node<T>* temp = NULL;
	Node<T>* current = head;
	
        while (current != NULL) {
            if(current->getData() == key)
			{
				if(current == head)
				{
					head = current->getNext();
				}
				else if(current == tail)
				{
					tail=temp;
					tail->getNext()=NULL;
				}
				else
				{
					temp->getNext() = current->getNext();
				}
				count--;
				delete current;
				return;
			}
			temp = current;
			current = current->getNext();
			
        }
}

template <class T>
void EnhancedLinkedList<T>::remove_all(const T &key)
{
	Node<T> *temp = NULL;
	Node<T> *temp1 = head;
	while(temp1!=NULL)
	{
		if(temp1->getData()==key)
		{
			if(temp1==tail)
			{
				tail = temp;
			}
			if(temp==NULL)
			{
				head = temp1->getNext();
				delete temp1;
				count--;
				temp1 = head;
			}
			else
			{
				temp->getNext() = temp1->getNext();
				delete temp1;
				count--;
				temp1 = temp->getNext();
			}
		}
		else
		{
			temp = temp1;
			temp1 = temp->getNext();
		}
	}
}