sortable_list.h

链表和应用包括单链表和双链表等等。自己写的

#include SORTABLE_LIST_H
#define  SORTABLE_LIST_H

#include "list.h"
#include "key.h"

template <class Record>
class Sortable_list: public:List<Record> {
	public:                        //Add prototypes for sorting methods here.
		void   insertion_sort();
		void   selection_sort();
		void   shell_sort();
		
	private:                       //Add prototypes for auxiliary functions here.
            int  max_key(int low, int high);
			void  swap(int low, int high);
            void sort_interval(int start, int increment);
};


template <class Record>
void Sortable_list<Record>::insertion_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys in all
        the entries are sorted into nondecreasing order.
  Uses: Methods for the class Record; the contiguous List implementation of 
        Chapter 6*/
{
	int first_unsorted;              //position of first unsorted entry
    int position;                    //searches sorted part of list
	Record current;                  //holds the entry temporarily removed from list
	for(first_unsorted = 1; first_unsorted<count;first_unsorted++) 
		if(entry[first_unsorted]<entry[first_unsorted-1]) {
			position = first_unsorted;
			current = entry[first_unsorted]; //Pull unsorted entry out of the list.
			do                       //Shift all entries until the proper position is found
			{
				entry[position] = entry[position-1];
				position --;                   //position is empty.
			} while (position>0 &&entry[position-1]>current);
			entry[position]= current;
		}
} 

template <class Record>
int Sortable_list<Record>::max_key(int low, int high)
/*Pre: low and high are valid position in the Sortable_list and low <= high.
 Post: The position of the the entry between low and high with the largest key is 
       returned.
 Uses: The class Record. The contiguous List implementation of Chapter 6.*/
{

	int largest,current;
	largest = low;
	for(current = low+1;current <=high; current++)
		if(entry[largest]<entry[current])
			largest = current;
		return largest;
}

template <class Record>
void Sortable_list<Record>::selection_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys in
        all the entries are sorted into nondecreasing order.
  Uses: max_key, swap.*/
{
	for (int position = count-1; position>0;position--) {
		int max = max_key(0,position);
		swap(max,position);
	}
}


template <class Record>
void Sortable_list<Record>::swap(int low, int high)
/*Pre: low and high are valid position in the Sortable_list.
 Post: The entry at position low is swapped with the entry at position high.
 Uses: The contiguous List implementation of Chapter 6.*/
{

	Record temp;
	temp =entry[low];
	entry[low] = entry[high];
	entry[high] = temp;
}


template <class Record>
void Sortable_list<Record>::shell_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys in
        all the entries are sorted into nondecreasing order.
  Uses: sort_interval*/
{
	int  increment;           //spacing of entries in sublist
	int  start;               //starting pointer of sublist
	do 
	{
		increment =increment/3+1;
		for(start = 0; start<increment; start++)
			sort_interval(start,increment);         //modified insertion sort.
	} while (increment>1);
	increment = count;
}

template <class Record>
void Sortable_list<Record>::sort_interval(int start, int increment)
{{
	int first_unsorted;              //position of first unsorted entry
    int position;                    //searches sorted part of list
	Record current;                  //holds the entry temporarily removed from list
	for(first_unsorted = start; first_unsorted<count;first_unsorted=+increment) 
		if(entry[first_unsorted+increment]<entry[first_unsorted]) {
			position = first_unsorted;
			current = entry[first_unsorted]; //Pull unsorted entry out of the list.
			do                       //Shift all entries until the proper position is found
			{
				entry[position] = entry[position-increment];
				position =position-increment;                   //position is empty.
			} while (position>0 &&entry[position-increment]>current);
			entry[position]= current;
		}
} 

}

#endif