listt.h

Data Abstraction & Problem Solving with C++源码

// *********************************************************
// Header file ListT.h for the ADT list.
// Pointer-based implementation -- TEMPLATE VERSION
// *********************************************************
#include "ListNodeT.h"
#include "ListException.h"
#include "ListIndexOutOfRangeException.h"

template <class T> 
class List
{
public:
// constructors and destructor:
   List();
   List(const List<T> & aList);
   virtual ~List();
   // List operations:
   virtual bool isEmpty() const;
   virtual int  getLength() const;
   virtual void insert(int index, T newItem) 
         throw(ListIndexOutOfRangeException, ListException);
   virtual void remove(int index)
         throw(ListIndexOutOfRangeException);
   virtual void retrieve(int index, T & dataItem) const 
         throw(ListIndexOutOfRangeException);
protected:
   void setSize(int newSize);
   ListNode<T> *getHead() const;
   void setHead(ListNode<T> *newHead);
   T getNodeItem(ListNode<T> *ptr) const;
   ListNode<T> *getNextNode(ListNode<T> *ptr) const;
private:
   int          size;
   ListNode<T> *head;

   ListNode<T> *find(int position) const;
};  // end class

//#include "ListT.cpp"
// code from ListT.cpp included explicitly here
// only some functions implemented
#include <cstddef>  // for NULL

template <class T> 
List<T>::List(): size(0), head(NULL)
{
}  // end default constructor

template <class T> 
void List<T>::insert(int index, T newItem)
         throw(ListIndexOutOfRangeException)
{
   int newLength = getLength() + 1;

   if ((index < 1) || (index > newLength))
      throw ListIndexOutOfRangeException(
      "ListIndexOutOfRangeException: insert index out of range");
   else
   {  // create new node and place newItem in it
     ListNode<T> *newPtr = new ListNode<T>;
     size = newLength;
     newPtr->item = newItem;

     // attach new node to list
     if (index == 1)
     {  // insert new node at beginning of list
         newPtr->next = head;
         head = newPtr;
     }
     else
     {  ListNode<T> *prev = find(index-1);
         // insert new node after node 
         // to which prev points
         newPtr->next = prev->next;
         prev->next = newPtr;
      }  // end if
   }  // end if
} // end insert

template <class T> 
ListNode<T> *List<T>::find(int index) const
{
   if ( (index < 1) || (index > getLength()) )
      return NULL;
   else  // count from the beginning of the list
   {  ListNode<T> *cur = head;
      for (int skip = 1; skip < index; ++skip)
         cur = cur->next;
      return cur;
   }  // end if
}  // end find