life.h

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

#include "SLList.h"
struct Cell
 { Cell( ) { row=col= 0; }   // constructors
   Cell(int x, int y) { row=x; col=y; }
   int row, col;           //grid coordinates
 };

class Hash_table 
{ public:
    Error_code insert(Cell *new_entry);
    bool retrieve(int row, int col) const;
  private:
    List<Cell *> table[hash_size];
}; 

class Life
{ public:
    Life( );
    void initialize( );
    void print( );
    void update( );
    ~Life( );
  private:
    List<Cell *> *living;
    Hash_table *is_living;
    bool retrieve(int row, int col) const;
    Error_code insert(int row, int col);
   int neighbor_count(int row, int col) const;
};

Error_code Hash_table::insert(const Record &new_entry)
/* Post:If the Hash_table is full, a code of overflow is returned. 
             If the table already contains an item with the key of 
             new_entry a code of duplicate error is returned.
             Otherwise: The Record new_entry is inserted into the           
              Hash_table and success is returned.
   Uses:Methods for classes Key,and Record. The function hash . */
{ Error_code result=success;
  int probe_count, increment, probe;  
  Key null;    

  null.make_blank( );
  probe=hash(new_entry);  probe_count = 0;   increment=1;    
  while( table[probe]!=null && table[probe]!=new_entry
       && probe_count<(hash_size+1)/2) 
    { probe_count++;
      probe=(probe+increment)%hash_size;
      increment += 2; 
   }
  if(table[probe]==null) table[probe]=new_entry;     
   else if(table[probe]==new_entry) result=duplicate_error;
           else result=overflow;                        
  return result;
}
  
void Life::update( )
/* Post: TheLife object contains the next generation of configuration.
   Uses: Theclass Hash_table and the class Life and its auxiliary functions. */
{ Life new_configuration;
  Cell *old_cell;
  for(int i=0; i<living->size( ); i++) 
   {living->retrieve(i, old_cell);     // Obtain a living cell.
    for(int row_add=-1; row_add<2; row_add++)
     for(int col_add=-1; col_add<2; col_add++)
      {int new_row=old_cell->row + row_add,
           new_col=old_cell->col+col_add;
           // new_row, new_col is now a living cell or a neighbor of a living cell,
       if(!new_configuration.retrieve(new_row, new_col))
       switch(neighbor_count(new_row, new_col)) 
         { case 3: //With neighbor_count3 , the cell becomes alive.
             new_configuration.insert(new_row, new_col); 
             break;
           case 2: //With count2 , cell keeps the same status.
             if(retrieve(new_row, new_col))
                new_configuration.insert(new_row, new_col); 
             break;
           default: break; // Otherwise, the cell is dead.
         }
      } // end_for(col_add ...
   } // end_for(i=...
   // Exchange data of current configuration with data ofnew_configuration .
  List<Cell *> *temp_list = living;
  living = new_configuration.living;
  new_configuration.living = temp_list;
  Hash_table *temp_hash = is_living;
  is_living = new_configuration.is_living;
  new_configuration.is_living = temp_hash;
}

void Life::print( )
/* Post: A central window onto theLife object is displayed.
Uses: The auxiliary functionLife::retrieve . */
{ int row, col;
  cout<< "\nThe current Life configuration is:\n" ;
  for(row=0; row<20; row++)
   { for(col=0; col<80; col++)
       if(retrieve(row, col)) cout<<'*';  else cout<<' ';
     cout<< endl;
   }
  cout<<endl;
}

Error_code Life::insert(int row, int col)
/* Pre: The cell with coordinates row and col is not in the Life configuration.
  Post: The cell has been added to the configuration. If insertion into either the
        List or theHash_table fails, an error code is returned.
  Uses: The class List, the class Hash_table, and the struct Cell */
{ Error_code outcome;
  Cell *new_cell=new_Cell(row, col);
  int index = living->size( );
  outcome=living->insert(index, new_cell);
  if(outcome==success) outcome = is_living->insert(new_cell);
  if(outcome != success)
    cout<<" Warning: new_Cell insertion failed" << endl;
  return outcome;
}

Life::Life( )
/* Post: The members of aLife object are dynamically allocated and initialized.
   Uses: Theclass Hash_table and theclass List . */
{ living = new List<Cell *>; is_living = new Hash_table; }

Life::~Life( )
/* Post: The dynamically allocated members of aLife object and allCell objects
         that they reference are deleted.
   Uses: Theclass Hash_table and theclass List . */
{ Cell *old_cell;
  for(int i=0; i<living->size( ); i++)
     { living->retrieve(i, old_cell);
       delete old_cell;
     }
  delete is_living; // Calls theHash_table destructor
  delete living; //Calls theList destructor
}
const int factor = 101;
int hash(int row, int col)
/* Post: The function returns the hashed valued between0 andhash_size . 1
         that corresponds to the givenCell parameter. */
{  int value;
   value = row + factor*col;
   value %= hash_size;
   if(value< ) return value+hash_size;
    else return value;
}