doublylinkedlist.h

这是学习《Data Structures Using C++》

#ifndef H_doublyLinkedList
#define H_doublyLinkedList

#include <iostream>
#include <cassert>

using namespace std;

//Definition of the node
template <class Type>
struct  nodeType
{  
      Type info;
      nodeType<Type> *next;
      nodeType<Type> *back;  
};

template <class Type>
class doublyLinkedList
{
    friend ostream& operator<<(ostream&, 
                           const doublyLinkedList<Type>&);
       //Overload the stream insertion operator
public:
    const doublyLinkedList<Type>& operator=
                           (const doublyLinkedList<Type> &);
      //Overload the assignment operator.
    void initializeList();
      //Function to initialize the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0
    bool isEmptyList();
      //Function to determine whether the list is empty.
      //Postcondition: Returns true if the list is empty;
      //               otherwise, returns false.

    void destroy();
      //Function to delete all the nodes from the list.
      //Postcondition: first = NULL; last = NULL;  count = 0
 
    void reversePrint();
      //Function to output the info contained in each node
      //in the reverse order

    int length();
      //Function to return the number of nodes in the list.
      //Postcondition: The value of count is returned.

    Type front();
      //Function to return the first element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program 
      //               terminates; otherwise, the first 
      //               element of the list is returned. 

    Type back();
      //Function to return the last element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program
      //               terminates; otherwise, the last
      //               element of the list is returned. 

    bool search(const Type& searchItem);
      //Function to determine whether searchItem is in the list.
      //Postcondition: Returns true if searchItem is found
      //               in the list; otherwise, it returns false.

    void insertNode(const Type& insertItem);
      //Function to insert newItem in the list.
      //Precondition: If the list is nonempty, it must be in
      //              order.
      //Postcondition: newItem is inserted at the proper place
      //               in the list; first points to the first
      //               node, last points to the last node of the
      //               new list and count is incremented by 1.

    void deleteNode(const Type& deleteItem);
      //Function to delete deleteItem from the list. the 
      //Postcondition: If found, the node containing 
      //               deleteItem is deleted from the list, first
      //               points to the first node of the new list,
      //               last points to the last node of the new
      //               list, and count is decremented by 1; 
      //               otherwise, an appropriate message is
      //               printed. 

    doublyLinkedList(); 
      //default constructor
      //Initializes the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0

    doublyLinkedList(const doublyLinkedList<Type>& otherList); 
      //copy constructor
    ~doublyLinkedList(); 
      //destructor
      //Postcondition: The list object is destroyed.

protected:
    int count;
    nodeType<Type> *first; //pointer to the first node
    nodeType<Type> *last;  //pointer to the last node

private:
    void copyList(const doublyLinkedList<Type>& otherList); 
      //Function to make a copy of otherList.
      //Postcondition: A copy of otherList is created and
      //               assigned to this list.

};


template<class Type>
doublyLinkedList<Type>::doublyLinkedList()
{
	first= NULL;
	last = NULL;
	count = 0;
}

template<class Type>
bool doublyLinkedList<Type>::isEmptyList()
{
    return(first == NULL);
}

template<class Type>
void doublyLinkedList<Type>::destroy()
{ 
	nodeType<Type>  *temp; //pointer to delete the node
	
	while(first != NULL)
	{
		temp = first;
		first = first->next;
		delete temp;
	}

	last = NULL;
	count = 0;
}

template<class Type>
void doublyLinkedList<Type>::initializeList()
{
	destroy();
}

template<class Type>
int doublyLinkedList<Type>::length()
{
	return count;
}

template<class Type>
ostream& operator<<(ostream& osObject, 
					const doublyLinkedList<Type>& list)
{
    nodeType<Type> *current; //pointer to traverse the list

	current = list.first;  //set current to point to 
	                       //the first node

	while(current != NULL)
	{
	   cout<<current->info<<"  ";  //output info
	   current = current->next;
	}//end while

	return osObject;
}

template<class Type>
void doublyLinkedList<Type>::reversePrint()
{
      nodeType<Type> *current; //pointer to traverse 
                               //the list

	  current = last;  //set current to point to the 
                       //last node

      while(current != NULL)
      {
	      cout<<current->info<<"  ";  
	      current = current->back;
      }//end while
}//end reversePrint

template<class Type>
bool doublyLinkedList<Type>::search(const Type& searchItem)
{
    bool found;
    nodeType<Type> *current; //pointer to traverse the list

    found = false;
    current = first;

    while(current != NULL && !found)
        if(current->info >= searchItem)
           found = true;
        else
           current = current->next;

    if(found)
       found = (current->info == searchItem); //test for equality

    return found;
}//end search

template<class Type>
Type doublyLinkedList<Type>::front()
{
      assert(first != NULL);

	      return first->info;
}

template<class Type>
Type doublyLinkedList<Type>::back()
{
      assert(last != NULL);

      return last->info;
}

template<class Type>
void doublyLinkedList<Type>::insertNode(const Type& insertItem)
{
    nodeType<Type> *current;      //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    nodeType<Type> *newNode;      //pointer to create a node
    bool found;

    newNode = new nodeType<Type>; //create the node
    assert(newNode != NULL);

    newNode->info = insertItem;  //store the new item in the node
    newNode->next = NULL;
    newNode->back = NULL;

    if(first == NULL) //if the list is empty, newNode is 
                      //the only node
    {
       first = newNode;
       last = newNode;
       count++;
    }
    else
    {
        found = false;
        current = first;

        while(current != NULL && !found) //search the list
            if(current->info >= insertItem)
               found = true;
            else
            {
               trailCurrent = current;
               current = current->next;
            }

       if(current == first) //insert new node before first
       {
          first->back = newNode;
          newNode->next = first;
          first = newNode;
          count++;
       }
       else
       {
               //insert newNode between trailCurrent and current
          if(current != NULL)
          {
             trailCurrent->next = newNode;
             newNode->back = trailCurrent;
             newNode->next = current;
             current->back = newNode;
          }
          else
          {
             trailCurrent->next = newNode;
             newNode->back = trailCurrent;
             last = newNode;
          }
          count++;
       }//end else
    }//end else
}//end insertNode


template<class Type>
void doublyLinkedList<Type>::deleteNode(const Type& deleteItem)
{
   nodeType<Type> *current; //pointer to traverse the list
   nodeType<Type> *trailCurrent; //pointer just before current

   bool found;

   if(first == NULL)
      cerr<<"Cannot delete from an empty list"<<endl;
   else
      if(first->info == deleteItem) //node to be deleted is the 
                                    //first node
      {
         current = first;
         first = first->next;

         if(first != NULL)
            first->back = NULL;
         else
            last = NULL;
			
         count--;
         delete current;
      }
      else 
      {
         found = false;
          current = first;

         while(current != NULL && !found)  //search the list
            if(current->info >= deleteItem)
               found = true;
            else
               current = current->next;

         if(current == NULL)
           cout<<"The item to be deleted is not in the list"
		       <<endl;
        else
           if(current->info == deleteItem) //check for equality
           {
              trailCurrent = current->back; 
              trailCurrent->next = current->next;

              if(current->next != NULL)
                 current->next->back = trailCurrent;

              if(current == last)
                 last = trailCurrent;

              count--;
              delete current;
          }
          else
             cout<<"The item to be deleted is not in list."
			     <<endl;
       }//end else
}//end deleteNode

template<class Type>
void doublyLinkedList<Type>::copyList(const doublyLinkedList<Type>& otherList)
{
	cout<<"The definition of this function is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
doublyLinkedList<Type>::doublyLinkedList(const doublyLinkedList<Type>& otherList)
{
	  cout<<"The definition of the copy constructor is left as an exercise."<<endl;
	  cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
const doublyLinkedList<Type>& doublyLinkedList<Type>::operator=
							(const doublyLinkedList<Type> &)
{
	cout<<"Overloading the assignment operator is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
doublyLinkedList<Type>::~doublyLinkedList()
{
	cout<<"Definition of the destructor is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

#endif