小明探索用链表思想实现插入排序。链表由节点连接而成,每个节点包含一个数据域和一个指针域。为了模拟这个过程,小明用a数组保存链表数据域,b数组保存链表指针域,排序的过程就是将每个数据的指针域不断链接到已有的有序链表合适位置,形成更长 的链表,直到所有的数据均链接到链表中。
例如将某节点插入到已有链表中,根据大小比较有三种情况:插入到最前面、插入到 最后、插入到中间,如图a所示,在链表中的节点 x 和节点 y之间插入节点n的过程示意:过程一(初始状态)如图1所示,链表中节点 x 的指针域指向节点y数据域,即图示①指向;过程二如图2所示,将节点n的指针域指向节点 y 数据域,即图示②指向;过程三如图 3 所示,将①指向断开,同时将节点 x 的指针域指向节点n数据域,即图示③指向;至此完成节点n的插入操作。
图a
具体程序设计方法如下:
1)将待排序的n个数保存在a(1)~a(n),b(1)~b(n)保存对应a数组各元素的位置,形成 n个没有链接的节点;
2)将a(1)结点看成只含有一个结点的链表head,且 head=1;
3)将a(2)节点插入到链表head的适当位置,使head仍有序,此时head成为含有两个结点的有序链表;以此方法依次将a数组中的其他节点插入到链表head中,最后链表 head上包含所有结点,且结点有序。依次输出head链表的数据域即完成排序。
程序运行界面如图b所示,采用此思想进行升序排序的 VB 代码如下,请回答下列问题。
图b