radix.cpp

数据结构与程序设计教材源码 数据结构与程序设计教材源码

 
const int max_chars = 28;
 
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 classes List, and Queue.
 
*/
{
   Record data;
   for (int i = 0; i < max_chars; i++)
      while (!queues[i].empty()) {
         queues[i].retrieve(data);
         insert(size(), data);
         queues[i].serve();
      }
}
 
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 classes List, Queue, and Record; 
functions position and rethread.
 
*/

{
   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.
   }
}