sllist.h

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

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

template <class Node_entry> struct Node    // Node declaration
{ Node_entry entry;                
  Node<Node_entry> *next;  
  Node( ){  next=NULL;  }     
  Node(Node_entry data, Node<Node_entry> *link=NULL)
  { entry=data;   next=link; } 
};

template <class List_entry>   
class List                         //  Single lined list declaration
{
 public:
    List(){ count=0; head = NULL;  }  // constructor
    List(const List<List_entry> &);   // copy constructor
    ~List();                          // destructor
    List& operator=(const List<List_entry>&); // List:overloaded assignment"="
    bool empty() const               // Judge whether isEmpty?
        { return count==0; }
    bool full()const;                // Judge whether isFull?
    int size()const                  // Compute the length    
        { return count; }                    
    void clear();                   // to clear the List: become empty    
    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
    void traverse(void (*visit)(List_entry &));            
 protected:
    Node<List_entry> *head;            //pointer: point to first node
    int count;                         //number of List_entry
    Node<List_entry> *set_position(int position) const;    
};
template <class List_entry>
void List<List_entry>::clear()
// Post: The List is cleared.
{  Node<List_entry> *p=head, *q;
   for(; p; p=q)
      { q=p->next;  delete p;  }
   head=NULL; count=0;
}

template <class List_entry>
List<List_entry>::~List()
{ clear(); }

template <class List_entry>
List<List_entry>::List(const List<List_entry> &copy)
{  count = copy.count;
   Node<List_entry> *q, *p = copy.head;
   if(p == NULL) head = NULL;
   else{ q = new Node<List_entry>(p->entry);  //申请,复制首元结点
         head = q;
         while(p->next)        //p->next != NULL
          { p = p->next;
            q->next = new Node<List_entry>(p->entry);
            q = q->next;
          }
         q->next=NULL;
       }
}

template <class List_entry>
List<List_entry>& List<List_entry>::operator=(const List<List_entry> &copy) //overloaded assignment operator
{ if(copy.count==0) clear(); 
  else
   { Node<List_entry> *q=head, *p=copy.head, *s; 
     if(count==0) // 当前表是"空",复制首元结点 q==NULL
       { head = s = new Node<List_entry>(p->entry);  
         p=p->next; 
       }
     while(p && q) //将copy表结点数据赋给*this表结点
       { q->entry=p->entry; 
         s=q, q=q->next;  p=p->next;  
       }
    if(q)  // 释放当前表多余结点空间  
       do{ p=q->next; delete q; q=p;  }while(q);
     else
	while(p) // copy表比当前表长,需申请结点空间,复制剩余结点 
	   { s->next = new Node<List_entry>(p->entry);
             s = s->next;  p = p->next; 
	   }; 
    s->next=NULL;  
   } 
  count = copy.count;   
  return *this;
}

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 = head;
   for( ; to_visit; to_visit=to_visit->next)
      (*visit)(to_visit->entry);      
}

template <class List_entry>
Node<List_entry>* List<List_entry>::set_position(int position) const
/* Pre: position is a valid position in the List; 0<= position <count.
  Post: Returns a pointer to the Node inposition . */
{ Node<List_entry> *q = head;
  for(int i=0; i<position; i++) q=q->next;
  return q;
}
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. */
{  Node<List_entry> *current;
   if (position<0 || position>=count) return range_error;
   current = 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.  */
{  Node<List_entry> *current;
   if (position<0 || position>=count) return range_error;
   current = 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, *previous;
   if(count==0) return fail;
   if(position < 0 || position >= count) return range_error;
   if(position > 0)
      { previous=set_position(position-1);
        old_node = previous->next;
        previous->next = old_node->next;
      }
   else { old_node = head ;      head = head->next;   }
   x = old_node->entry;
   delete old_node;
   count--;
   return success;
}

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.
         Otherwise The function fails with a diagnostic error_code. */
{  if (position<0 || position>count) return range_error;
   Node<List_entry> *new_node, *previous, *following;
   if (position > 0) 
      { previous = set_position(position-1);
        following = previous->next;
      }
  else following = head;
  new_node = new Node<List_entry>(x, following);
  if(new_node==NULL)return fail;
  if(position==0)head = new_node;
    else previous->next = new_node;
   count++;
   return success;
}
template <class List_entry> 
int List<List_entry>::find(const List_entry &x)
{ Node<List_entry> *q = head;
  for (int i=0; i<count && q->entry!=x; i++) q=q->next;
  if( i>=count ) return -1; else return i;
}