链表排序

/*********插入排序**********/
#include<iostream>
using namespace std;
/***Writed by Yecon***/

const int MaxNum = 999999;
const int DefaultSize = 10;
class staticlinklist;   //静态链表类的前视说明
class Element     //链表结点元素
{
 int key;
 int link;
public:
 int getKey(){return key;}
 void setKey(int k){key = k;}
 int getLink(){return link;}
 void setLink(const int l){link = l;}
};
class staticlinklist
{
 int MaxSize,CurrentSize;
public:
 Element *Vector;       //存储待排序元素的向量
 staticlinklist(int Msz = DefaultSize):MaxSize(Msz),CurrentSize(0)
 {
  Vector = new Element[MaxSize];
 }
 bool IsFull()
 {
  return CurrentSize == MaxSize -1;
 }
 int getCurrentSize()
 {
  return CurrentSize;
 }
 void InsertElem(int k)
 {
  if(CurrentSize < MaxSize)
  {
   Vector[CurrentSize].setKey(k);
   Vector[CurrentSize].setLink(0);
   CurrentSize++;
  }
 }
 void InsertElem(int k,int index,int pos)
 {
  if(index <= CurrentSize && CurrentSize != MaxSize)
  {
   for(int i = CurrentSize - 1;i >= index;i--)
   {
    Vector[i+1].setKey(Vector[i].getKey());
    Vector[i+1].setLink(Vector[i].getLink());
   }
   Vector[index].setKey(k);
   Vector[index].setLink(pos);
   CurrentSize++;
  }
 }
 void DispAll()
 {
  for(int i = 0;i < CurrentSize;i++)
  {
   cout << Vector[i].getKey() << "(" << Vector[i].getLink() << ")" << " ";
  }
  cout << endl;
 }
};
/**********END数据表类*********/

/**********静态链表排序算法********/
void LinkInsertSort(staticlinklist &list)
{
 //对元素list.Vector[1],...,list.Vector[i]按其关键码key排序，这是一个静态链表，
 //每个对象中有一个链域link。list.Vector[currentSize]作为排序后各对象所构成的有序循环链表的表头结点使用。
 //初始化时结点的关键码给最大值MaxNum。n是表中当前结点个数。

//Init:
 list.InsertElem(MaxNum,0,1);      //创头结点
 list.Vector[1].setLink(0);       //指向头结点，形成只有头结点的循环链表
 for(int i = 2;i <= list.getCurrentSize();i++)
 {
  int current = list.Vector[0].getLink();   //current是链表的检测指针
  int pre = 0;         //pre是指向current的前驱
  while(list.Vector[current].getKey() <= list.Vector[i].getKey())
  {
   //寻找插入位置
   pre = current;
   current = list.Vector[current].getLink();
  }
  list.Vector[i].setLink(current);list.Vector[pre].setLink(i); //结点i链入current与pre之间
 }
//END init
}
/*********END静态链表排序算法*********/

/*************测试函数***********/
int testLISort()//main()
{
 staticlinklist L(7);
 L.InsertElem(21);
 L.InsertElem(25);
 L.InsertElem(49);
 L.InsertElem(25);
 L.InsertElem(16);
 L.InsertElem(8);
 L.DispAll();
 LinkInsertSort(L);
 L.DispAll();

 getchar();
 return 0;
}