list.h

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

//顺序表的抽象数据类型定义

#define max_list 30       // 顺序表的最大长度（容量）
enum Error_code{ success, overflow, underflow, range_error};

template <class List_entry>    // 模板声明, List_entry是类参数(即,可变类型)
class List
{
  public:
    List(){ count=0; }   // 构造函数
    int size()     // 求顺序表的长度    
        { return count; }                    
    bool full()     // 判断顺序表是否已"满"
        { return count==max_list; }
    bool empty()     // 判断顺序表是否为空表
       { return count==0; }
    void clear()               // 清空顺序表
        { count=0; }
    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);     // 查找元素x,找不到返回-1，否则为x在表中的位置
  protected:
    List_entry entry[max_list] ;    // entry是指向存放数据元素的数组指针
    int count;    // 顺序表的当前长度(元素数目)
};
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. */
{  if (full( )) return overflow;
   if (position<0 || position>count) return range_error;
   for (int i=count-1; i>=position; i--) entry[i+1]=entry[i];
   entry[position]=x;
   count++;
   return success;
}
template <class List_entry> 
Error_code List<List_entry>::replace(int position, const List_entry &x)
{  if (empty()) return underflow;
   if (position<0 || position>=count) return range_error;
   entry[position] = x;  
   return success;
} 
template <class List_entry> 
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
{  if(empty()) return underflow;
   if(position<0 || position>=count) return range_error;
   x=entry[position];  
   return success;
}       
template <class List_entry> 
Error_code List<List_entry>::remove(int position, List_entry &x)
/* Post: If the List is not empty and 0≤position<n, where n is the number of entries in the List,
            the function succeeds:The entry at position is removed from the List, and all later 
            entries have their position numbers decreased by 1. The parameter x records a copy 
            of the entry formerly at position.
         Else: The function fails with a diagnostic error_code. */
{  if (empty( )) return underflow;
   if (position<0 || position>=count) return range_error;
   x=entry[position];   count--;
   for (int i=position; i>count; i++) entry[i]=entry[i+1];
   return success;
}   

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. */
{  
  for (int i=0; i<count; i++)(*visit)(entry[i]);
}

template <class List_entry> int List<List_entry>::Find(const List_entry &x)
{ int i=0;
  while( i<count && entry[i]!= x )i++;
  if(i<count) return i;  else return -1;
}