链表插入排序 」基本思想是:在每个对象的结点中增加一个 链接指针数据成员link。 对于数组中的一组对象v[1…Vm,若 V[1],…V1已经通过指针link,按其排序 码从小到大链接起来。现要插入V团,=2, 3,…n,则必须在前面斗1个链接起来的对象 当中,循链检测比较,找到V团应插入的位置 把V[链入,并修改相应链接指针。从而得到 V[1],,,V的一个通过指针排好的链表。 如此重复执行,直到把m]也插入到链表中 排好序为止
CO 2125 4925 16 0 2 5 6 物始 i=2 current pre =3 current pre pre current
0 1 2 3 4 5 6 current pre i current pre i pre current i
CO 2125 4925 16 0 2 5 6 i=5 pre current i=6 ne current i 鳍r
0 1 2 3 4 5 6 pre current i pre current i
用于链表排序的静态链表的类定义 template <class Type> class staticlinklist template <class Type> class Element t p rivate Type key;结点的排序码 int link: /结点的链接指针 public Element (: key(O), link (NULl Type getKey (i return key; void setKey( const Type x )(key=x;) int getLink(freturn link;) void setLink( const int Ii link=1; 5
template <class Type> class staticlinklist; template <class Type> class Element { private: Type key; //结点的排序码 int link; //结点的链接指针 public: Element ( ) : key(0), link (NULL) { } Type getKey ( ) { return key; } void setKey ( const Type x ) { key = x; } int getLink ( ) { return link; } void setLink ( const int l ) { link = l; }
template <class Type> class staticlinklist i p rivate Element<ype>* Vector;∥存储向量 int maxSize Currentsize /向量中最大元素个数和当前元素个数 publica dstaticlinklist( int MaxSz= DefaultSize ): Max Size( Maxsz ) CurrentSize(0 f Vector=new Element <Type>[MaxSzl; 3
} template <class Type> class staticlinklist { private: Element <Type> * Vector; //存储向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; } }