allist.h

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

  // 用数组存储的链表(静态链表)的类声明及实现
typedef int index;
const int max_list = 30;
enum Error_code{ success, overflow, underflow, range_error};

template <class List_entry>
class Node 
{ public:
    List_entry entry;
    index next;
};

template <class List_entry>
class List                     
{ public:
    // Methods of the list ADT
    List( )
      { count=0; available=head=last_used=-1;}
    List(const List<List_entry> &);   // copy constructor
    ~List() {  clear();  }            // destructor
    List& operator=(const List<List_entry>&);   // List:overloaded assignment"="
    int size( ) const
      { return count; }
    bool full( ) const
      { return count==max_list; }
    bool empty( ) const
      { return count==0; }
    void clear( );
    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:
    // Data members
    Node<List_entry> workspace[max_list];
    index available, last_used, head;
    int count;
    // Auxiliary member functions
    index new_node( );
    void delete_node(index n);
    int current_position(index n) const;
    index set_position(int position) const;
};
template <class List_entry>
int List<List_entry>::current_position(index n) const
{ int i = head, j = 0;
  while( i>-1 && i!=n ) { j++; i=workspace[i].next; }
  if( i>-1 ) return j; else return -1;
}

template <class List_entry>
List<List_entry>::List(const List<List_entry> &copy)
{  available=head=last_used=-1;
   count = copy.count;
   index s, q, p = copy.head;
   if(count>0)
     { q = new_node( );                  
       workspace[q].entry = copy.workspace[p].entry;   
       head = q;
       while(copy.workspace[p].next!=-1)        
         { p=copy.workspace[p].next;
           s=q; q=new_node( ); workspace[s].next=q ;
           workspace[q].entry = copy.workspace[p].entry;
         }
       workspace[q].next=-1;
    }
}

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
   { index q=head, p=copy.head, s; 
     if(count==0) // 当前表是"空",复制首元结点 q==-1
       { head = s = new_node( ); //new index(p->entry);  
         workspace[head].entry = copy.workspace[p].entry;
         p=copy.workspace[p].next;   
       }
     while(p!=-1 && q!=-1)  //将copy表结点数据赋给*this表结点
       { workspace[q].entry = copy.workspace[p].entry; 
         s=q, q=workspace[q].next;  p=copy.workspace[p].next;  
       }
     if(q!=-1)  // 释放当前表多余结点空间  
       do{ p=workspace[q].next; delete_node(q); q=p;  }while(q!=-1);
     else
       while(p!=-1) // copy表比当前表长,需申请结点空间,复制剩余结点 
	 { q=new_node(); workspace[s].next=q ;
	   workspace[q].entry = workspace[p].entry;
       s = q;  p=copy.workspace[p].next; 
	 }; 
    workspace[s].next=-1;  
   } 
  count = copy.count;   
  return *this;
}
template <class List_entry>
index List<List_entry>::set_position(int position) const
{ int i = head, j = 0;
  while( i>-1 && j!=position ) { j++; i=workspace[i].next; }
  return i; 
}
template <class List_entry>
void List<List_entry>::clear()
// Post: The List is cleared.
 { if(head==-1)return;
   for( int i=head; i>-1; )
      { index j=i; i=workspace[i].next;
        workspace[j].next = available;  available = j; 
      }
   count=0;    
 }

template <class List_entry>
index List<List_entry>::new_node( )//相当于动态结构的new operator
/* Post:The index of the first available Node in workspace is returned; 
        the data members available,last_used, and workspace are updated 
        as necessary. If the workspace is already full,-1 is returned. */
{ index new_index;
  if(available != -1)
    { new_index = available;
      available = workspace[available].next;
    } 
   else if(last_used<max_list-1) new_index=++last_used;
         else return -1;
  workspace[new_index].next = -1;
  return new_index;
}  

template <class List_entry>  
void List<List_entry>::delete_node(index old_index)//相当于动态结构的 delete operator
/* Pre: The List has a Node stored at index old_index.
  Post: The List index old_index is pushed onto the linked stack 
        of available space;available,last_used, and workspace 
        are updated as necessary.  */
{ index previous;
  if( old_index==head ) head=workspace[old_index].next;
   else{ previous=set_position(current_position(old_index)-1);
         workspace[previous].next=workspace[old_index].next;
       }
  workspace[old_index].next = available;
  available = old_index;
}

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
theList , beginning at position0 and doing each in turn. */
{
  for(index n=head; n!=-1; n=workspace[n].next)
     (*visit)(workspace[n].entry);
}

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;
   index current = set_position(position);
   x=workspace[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.  */
{  index current;
   if (position<0 || position>=count) return range_error;
   current = set_position(position);
   workspace[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.  */
{  index old_node;
   if(count==0) return underflow;
   if(position < 0 || position >= count) return range_error;
   old_node=set_position(position);
   x = workspace[old_node].entry;
   delete_node(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 theList, the function succeeds: Any entry formerly atposition
         and all later entries have their position numbers increased by1 andx is 
         inserted at position of theList.
         Else: the function fails with a diagnostic error code. */
{ index new_index, previous, following;
  if(position<0 || position>count) return range_error;
  if(position>0)
    {previous=set_position(position-1);
     following=workspace[previous].next;
    }
   else following=head;
  if((new_index=new_node())==-1) return overflow;
  workspace[new_index].entry = x;
  workspace[new_index].next = following;
  if(position == 0) head = new_index;
   else workspace[previous].next = new_index;
  count++;
  return success;
}

template <class List_entry> 
int List<List_entry>::find(const List_entry &x)
{ index q = head;
  for (int i=0; i<count && workspace[q].entry!=x; i++) q=workspace[q].next;
  if( i>=count ) return -1; else return i;
}