hosteons中文网

前面章节中所介绍到的三种插入排序算法，其基本结构都采用数组的形式进行存储，因而无法避免排序过程中产生的数据移动的问题。如果想要从根本上解决只能改变数据的存储结构，改用链表存储。

表插入排序，即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中，不需要移动记录的存储位置，只需要更改结点间指针的指向。

链表的存储结构用代码表示为：

#define SIZE 100
typedef struct {
    int rc;//记录项
    int next;//指针项，由于在数组中，所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {
    SLNode r[SIZE];//存储记录的链表
    int length;//记录当前链表长度
}SLinkListType;

在使用数组结构表示的链表中，设定数组下标为 0 的结点作为链表的表头结点，并令其关键字取最大整数。则表插入排序的具体实现过程是：首先将链表中数组下标为 1 的结点和表头结点构成一个循环链表，然后将后序的所有结点按照其存储的关键字的大小，依次插入到循环链表中。

例如，将无序表{49，38，76，13，27}用表插入排序的方式进行排序，其过程为：

• 首先使存储 49 的结点与表头结点构成一个初始的循环链表，完成对链表的初始化，如下表所示：