enhancedlinkedlist.h

ssd5 答案 op1 希望能对大家有帮助

#include "LinkedList.h"



class ListItemNotFoundException : public logic_error {

public:
    ListItemNotFoundException(const string& what_arg ) throw() :
    logic_error ("ListItemNotFoundException: " + what_arg) {}}
;


//Enhanced linked list

template <class T>
class EnhancedLinkedList:public LinkedList<T>
{
public:
	EnhancedLinkedList();
	T& find_first (const T& key);
	EnhancedLinkedList<T> find_all (const T& key);
	void remove_first (const T& key);
	void remove_all (const T& key); 
};


//constructor
template <class T>
EnhancedLinkedList<T>::EnhancedLinkedList():LinkedList<T>()
{
	head=NULL;
	tail=NULL;
	count=0;
}



/*
Method find_first should search the EnhancedLinkedList for the
first occurrence of an item that matches the value in the 
parameter key. It should return a reference to the first 
matching item. If the invoking EnhancedLinkedList object 
is empty or no item is found that matches the parameter, 
a ListItemNotFoundException should be thrown. You will have to
define this exception (Hint: define this exception much the same 
way that the EmptyListException exception is defined in LinkedList.h). 
*/ 
template<class T>
T& EnhancedLinkedList<T>::find_first (const T& key){

	if( head == NULL)
		throw ListItemNotFoundException ("the head is null");
	else
	{
		Node<T>* current = head;
		while(current->getNext()!=tail)
		{
			if(current->getData() == key)
				return current->getData();
			current = current->getNext();
		}
		if(tail->getData() == key)
			return tail->getData();
		throw ListItemNotFoundException ("no item matches the parameter");
	}
}
//find_all
/*
Method find_all should search the invoking EnhancedLinkedList for 
all elements that match the value in the parameter key. It should 
return an EnhancedLinkedList object containing copies of all the 
items that match the parameter key. If the invoking EnhancedLinkedList
 object is empty or no item is found that matches the parameter, 
 this function should return an empty EnhancedLinkedList. 
*/
template<class T>
EnhancedLinkedList<T> EnhancedLinkedList<T>::find_all(const T& key)
{
	EnhancedLinkedList<T> fa;
	if(head == NULL)
		return fa;
	else
	{	
		Node<T>* current = head;

		while(current != tail)
		{
			if(current->getData() == key)
				fa.push_back(current->getData());

			current = current->getNext();
		}
		if(tail->getData() == key)
			fa.push_back(current->getData());
	}
	return fa;
}
/*
Method remove_first should remove the first element from the 
invoking EnhancedLinkedList whose data item matches the 
parameter key. If the invoking EnhancedLinkedList object
 is empty or no item is found that matches the parameter,
 this function should do nothing. Remember to leave no memory leaks.
*/
template<class T>
void EnhancedLinkedList<T>::remove_first (const T& key)
{
	if(head == NULL)
		return;
	if(head->getData() == key)
	{
		pop_front();
		return;
	}

	

	Node<T>* current = head->getNext();
	Node<T>* prior = head;
	while (current != tail)
	{
		if(current->getData() == key)
		{
			Node<T> * temp;
			temp = current;
			current = current->getNext();
			prior->getNext() = current;
			count --;
			delete temp;
			return;			
		}
		prior = current;
		current = current->getNext();
	}


	if(tail->getData() == key)
	{
		pop_back();
	}

}
/*
Method remove_all should remove all elements from the invoking
 EnhancedLinkedList whose data items match the parameter key.
 If the invoking EnhancedLinkedList object is empty or no item
 is found that matches the parameter, this function should do
 nothing. Remember to leave no memory leaks. 
*/
template<class T>
void EnhancedLinkedList<T>:: remove_all (const T& key)
{
	if(head == NULL)
		return;
	while(head->getData() == key)
		pop_front();



	Node<T>* current = head->getNext();
	Node<T>* prior = head;
	while (current != tail)
	{
		if(current->getData() == key)
		{
			Node<T> * temp;
			temp = current;
			current = current->getNext();
			prior->getNext() = current;
			count --;
			delete temp;
			continue;			
		}
		prior = current;
		current = current->getNext();
	}



	if(tail->getData() == key)
		pop_back();

}