dllist.h

这是本人精心搜集的关于常用图论算法的一套源码

#include <iostream.h>
enum Error_code{ success, fail, range_error };

template <class Node_entry>    // Node declaration
struct Node 
{//  data members
   Node_entry entry;
   Node<Node_entry> *next;
   Node<Node_entry> *back;
//  constructors
   Node();
   Node(Node_entry, Node<Node_entry> *link_back = NULL, Node<Node_entry> *link_next = NULL);
};

template <class List_entry>
Node<List_entry>::Node()
{   next = back = NULL;  }


template <class List_entry> Node<List_entry>::
  Node(List_entry data, Node<List_entry> *link_back,Node<List_entry> *link_next)
{  entry = data;
   back = link_back;
   next = link_next;
}

template <class List_entry>
class List                       //  doubly lined list declaration
{ public: 
   List();                            // constructor
   List(const List<List_entry> &);    // copy constructor
   ~List() {  clear();  }             // destructor
   List& operator=(const List<List_entry>&); // List:overloaded assignment"="
   int size() const  { return count; } // Compute the length 
   bool full() const;                  // Judge whether isFull?
   bool empty() const { return count==0; }  // Judge whether isEmpty?
   void clear();                            // to clear the List:become empty  
   void traverse(void (*visit)(List_entry &));
   Error_code retrieve(int position, List_entry &x) const;
   Error_code replace(int position, const List_entry &x);
   Error_code remove(int position, List_entry &x);
   Error_code insert(int position, const List_entry &x);
   int find(const List_entry &x);
      // search List entry x,return -1 if not find,otherwise return position of x

protected:
   int count;                    //number of List_entry
   mutable int current_position;    //int: Designation position of last operated node
   mutable Node<List_entry> *current;          //pointer:point to last operated node
   void set_position(int position) const; // The auxiliary function to locate list positions follows:
};

template <class List_entry>
List<List_entry>::List()
// Post: The List is initialized to be empty.
{  count = 0;
   current = NULL;
   current_position = -1;
}

template <class List_entry>
void List<List_entry>::clear()
// Post: The List is cleared.
{  Node<List_entry> *p, *q;
   if(count == 0) return;
   for(p = current->back; p; p=q)
      {  q=p->back;    delete p;  }
   for(p=current; p; p=q)
      {  q=p->next;   delete p;   }
   count = 0;
   current = NULL;
   current_position = -1;
}

template <class List_entry>
bool List<List_entry>::full() const
// Post: The function returns true or false according as the List is full or not.

{ Node<List_entry> *p;
  try { p=new Node<List_entry>; }
      catch(...) {  return true; }
  delete p;
  return false;
}

template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/* Post: The action specified by function *visit has been 
         performed on every entry of the List, beginning 
         at position 0 and doing each in turn.    */
{  Node<List_entry> *to_visit = current;
   if (to_visit != NULL)   //  Ignore empty lists.
      for( ; to_visit->back; to_visit=to_visit->back);   //  Find the beginning of List.
   for( ; to_visit; to_visit=to_visit->next)
      (*visit)(to_visit->entry);
}

template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/* Post:If the List is not full and 0<=position<=n,where n is the number of
        entries in the List, the function succeeds:Any entry formerly at
        position and all later entries have their position numbers 
        increased by 1 and x is inserted at position of the List. 
        Else:the function fails with a diagnostic error code. 
*/
{ Node<List_entry> *new_node, *following, *preceding;
  if( position<0 || position>count ) return range_error;
  if( position==0 )
    { if (count==0) following = NULL;
       else { set_position(0);   following = current; }
      preceding = NULL;
    }
   else 
    { set_position( position-1);
      preceding = current;
      following = preceding->next;
   }
   new_node = new Node<List_entry>(x, preceding, following);
   if(new_node == NULL) return fail;
   if(preceding != NULL) preceding->next = new_node;
   if(following != NULL) following->back = new_node;
   current = new_node;
   current_position = position;
   count++;
   return success;
}

template <class List_entry>
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
/* Post: If the List is not full and 0<=position<n, where n is 
         the number of entries in the List, the function succeeds:
         The entry in position is copied to x.
         Otherwise the function fails with an error code of range_error. */
{ if( position<0 || position>=count ) return range_error;
  set_position(position);
  x = current->entry;
  return success;
}

template <class List_entry>
Error_code List<List_entry>::replace(int position, const List_entry &x)
/* Post: If 0<= position <n, where n is the number of entries in the List,
         the function succeeds: The entry in position is replaced by x,
         all other entries remain unchanged.
         Otherwise the function fails with an error code of range_error.  */
{  if( position<0 || position>=count ) return range_error;
   set_position(position);
   current->entry = x;
   return success;
}

template <class List_entry>
Error_code List<List_entry>::remove(int position, List_entry &x)
/* Post: If 0<= position <n, where n is the number of entries in the List,
         the function succeeds: The entry in position is removed from the List, 
         and the entries in all later positions have their position numbers decreased by 1.
         The parameter x records a copy of the entry formerly in position.
        Otherwise the function fails with a diagnostic error code.  */
{  Node<List_entry> *old_node, *neighbor;
   if(count==0) return fail;
   if( position<0 || position>=count ) return range_error;
   set_position(position);
   old_node = current;
   if(neighbor=current->back) neighbor->next = current->next;
   if(neighbor=current->next)
     { neighbor->back = current->back;
       current = neighbor;
     }
   else
     { current = current->back;
       current_position--;
     }
   x = old_node->entry;
   delete old_node;
   count--;
   return success;
}

template <class List_entry>
void List<List_entry>::set_position(int position) const
/* Pre: position is a valid position in the List:0<=position<count.
  Post: The current Node pointer references the Node at position.
*/
{ if(current_position <= position)
    for( ; current_position!=position; current_position++)
         current = current->next;
   else
      for ( ; current_position!=position; current_position--)
         current = current->back;
}

template <class List_entry>
List<List_entry>::List(const List<List_entry> &copy)
// Post: The List is initialized to copy the parameter copy.
{ count = copy.count;
  current_position = copy.current_position;
  Node<List_entry> *new_node, *old_node = copy.current;
  if(old_node == NULL) current = NULL;
   else 
    { new_node = current = new Node<List_entry>(old_node->entry);
      while(old_node->next != NULL)
       { old_node = old_node->next;
         new_node->next = new Node<List_entry>(old_node->entry, new_node);
         new_node = new_node->next;
       }
      old_node = copy.current;
      new_node = current;
      while(old_node->back != NULL)
       { old_node = old_node->back;
         new_node->back = new Node<List_entry>(old_node->entry, NULL, new_node);
         new_node = new_node->back;
       }
   }
}
 
template <class List_entry>
List<List_entry>&  List<List_entry>::operator=(const List<List_entry> &copy)
// Post: The List is assigned to copy a parameter
{ List<List_entry> new_copy(copy);
  clear();
  count = new_copy.count;
  current_position = new_copy.current_position;
  current = new_copy.current;
  new_copy.count=0; 
  new_copy.current_position=-1;
  new_copy.current = NULL;
  return *this;
}
template <class List_entry> 
int List<List_entry>::find(const List_entry &x)
{ if(count==0)return -1;
  Node<List_entry> *q = current;  int i=current_position;
  for(; q && q->entry!=x; i++) q=q->next;
  if(q==NULL && current_position>0)       // not Find after current_position
    { q=current->back, i=current_position-1;
      for(; q && q->entry!=x; i--) q=q->back; // Finding before current_position
    }  
  if(q){ current=q; current_position=i; return i; } 
  else return -1;
}