sort_sl.h

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

#include "SLList.h"
#include "Key.h"
typedef Key Record;

template <class Record>
class Sortable_list: public List<Record> 
{ public: 
    void insertion_sort( );
    void merge_sort( );
  private: 
     //Auxiliary member functions
    void recursive_merge_sort(Node<Record> * &sub_list);
    Node<Record> *divide_from(Node<Record> *sub_list);
    Node<Record> *merge(Node<Record> *first, Node<Record> *second);
};

template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ Node<Record> *first_unsorted, // the first_unsorted node to be inserted
               *last_sorted, // tail of the sorted sublist
               *current, // used to traverse the sorted sublist
               *trailing; // one position behind current
  if(head == NULL) return; //the empty list is already sorted.
  last_sorted = head; // The first node alone makes a sorted sublist.
  while(last_sorted->next != NULL) 
    { first_unsorted = last_sorted->next;
      if(first_unsorted->entry < head->entry)// Insert *first_unsorted at the head of the sorted list:
        {last_sorted->next = first_unsorted->next;
         first_unsorted->next = head;
         head = first_unsorted; 
        }
       else  // Search the sorted sublist to insert*first_unsorted :
        { trailing = head; current = trailing->next;
          while(first_unsorted->entry > current->entry)
           { trailing = current; current = trailing->next; }
          // *first_unsorted now belongs between *trailing and *current.
          if(first_unsorted == current)
            last_sorted = first_unsorted; // already in right position
           else
            { last_sorted->next = first_unsorted->next;
              first_unsorted->next = current;
              trailing->next = first_unsorted;
            }
        }    
    }
}
template <class Record>
void Sortable_list<Record>::merge_sort( )
{ recursive_merge_sort(head); }

template <class Record> void Sortable_list<Record>::
recursive_merge_sort(Node<Record> * &sub_list)
{ if(sub_list != NULL && sub_list->next != NULL)
    { Node<Record> *second_half = divide_from(sub_list);
      recursive_merge_sort(sub_list);
      recursive_merge_sort(second_half);
      sub_list = merge(sub_list, second_half);
    }
}
template <class Record>
Node<Record> *Sortable_list<Record>::divide_from(Node<Record> *sub_list)
{ Node<Record> *position, // traverses the entire list
               *midpoint, // moves at half speed of position to midpoint
               *second_half;
  if((midpoint=sub_list) == NULL) return NULL; // List is empty.
  position=midpoint->next;
  while(position != NULL)
   { // Move position twice for midpoint's one move.
    position = position->next;
    if(position != NULL) 
      {  midpoint=midpoint->next; position = position->next; }
   }
  second_half = midpoint->next;
  midpoint->next = NULL;
  return second_half;
}
template <class Record> Node<Record> *Sortable_list<Record>::
merge(Node<Record> *first, Node<Record> *second)
{  Node<Record> *last_sorted; // points to the last node of sorted list
   Node<Record> combined;  // dummy first node, points to merged list dummy 
   last_sorted = &combined;
   while(first != NULL && second != NULL)  // Attach node with smaller key
     if(first->entry <= second->entry) 
       { last_sorted->next = first;
         last_sorted = first;
         first = first->next; // Advance to the next unmerged node.
       }
      else
       { last_sorted->next = second;
         last_sorted = second;
         second = second->next;
       }
   // After one list ends, attach the remainder of the other.
   if (first==NULL) last_sorted->next = second;
    else last_sorted->next=first;
   return combined.next;
}