radix.h

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

#include "SLList.h"
#include "Queue.h"
#include "Str.h"

template <class Record>
class Sortable_list: public List<Record> 
{ public: 
    void radix_sort( );
  private: 
     //Auxiliary member functions
    void rethread(Queue queues[]);
};

class Record
{ public:
    char_key letter(int position) const;
    Record( ); //default constructor
//    operator Key( ) const; // cast to Key
  private:   
    String Key;
};

const int max_chars = 28;
template <class Record>
void Sortable_list<Record> :: radix_sort( )
/* Post: The entries of the Sortable_list have been sorted so all their keys are in
         alphabetical order.
   Uses: Methods from classesList ,Queue , andRecord ;
          functionsposition andrethread . */
{ Record data;
  Queue queues[max_chars];
  for(int position= key_size-1; position >= 0; position--)
     {  // Loop from the least to the most significant position.
       while(remove(0,data) == success) 
        { int queue_number = alphabetic_order(data.key letter(position));
          queues[queue_number].append(data); // Queue operation.
        }
       rethread(queues); //Reassemble the list.
     }
}

Auxiliary Functions, Linked Radix Sort
Selecting a queue:
int alphabetic_order(char c)
/* Post: The function returns the alphabetic position of characterc , or it returns 0
if the character is blank. */
{ if(c==' ') return 0;
  if('a'<=c && c<='z') return c-'a'+1;
  if('A'<=c && c<='Z') return c-'A'+1;
   return 27;
}
Connecting the queues:
template <class Record>
void Sortable_list<Record>::rethread(Queue queues[])
/* Post: All the queues are combined back to the Sortable_list , 
         leaving all the queues empty.
   Uses: Methods of classesList , andQueue . */
{ Record data;
  for(int i=0; i<max_chars; i++)
    while(!queues[i].empty( ))
      { queues[i].retrieve(data);
        insert(size( ), data);
        queues[i].serve( );
       }
}