【例10.2】表插入排序示例 0123456 初始状态 Mxa4938659776132749key或 next域 Mx4938659776132749key域 next域 Mx4938659776132749k域 i=2 201 next域 Mx4938659776132749key域 i=3 2310 next域
【例10.2】表插入排序示例 0 1 2 3 4 5 6 7 8 MAXINT 49 38 65 97 76 13 27 49 0 - - - - - - - - 初 始 状 态 key域 next域 MAXINT 49 38 65 97 76 13 27 49 1 0 - - - - - - - i=1 MAXINT 49 38 65 97 76 13 27 49 2 0 1 - - - - - - i=2 MAXINT 49 38 65 97 76 13 27 49 2 3 1 0 - - - - - i=3 key域 next域 key域 next域 key域 next域
Mx4938659776132749key域 23140 next域 Mx4938659776132749key域 i=5 231504 next域 Mx4938659776132749key域 i=6 6315042 next域 x4938659776132749key域 63150572 next域 Mx4938659776132749key域 i=8 681504723next域
MAXINT 49 38 65 97 76 13 27 49 2 3 1 4 0 - - - - i=4 MAXINT 49 38 65 97 76 13 27 49 6 3 1 5 0 5 7 2 - i=7 MAXINT 49 38 65 97 76 13 27 49 6 8 1 5 0 4 7 2 3 i=8 key 域 next 域 key 域 next 域 key 域 next 域 MAXINT 49 38 65 97 76 13 27 49 2 3 1 5 0 4 - - - i=5 key 域 next 域 MAXINT 49 38 65 97 76 13 27 49 6 3 1 5 0 4 2 - - i=6 key 域 next 域
表插入排序得到一个有序的链表,查找则 只能进行顺序查找,而不能进行随机查找, 如折半查找。为此,还需要对记录进行重排。 重排记录方法:按链表顺序扫描各结点, 将第ⅰ个结点中的数据元素调整到数组的第i个 分量数据域。因为第i个结点可能是数组的第j 个分量,数据元素调整仅需将两个数组分量 中数据元素交换即可,但为了能对所有数据 元素进行正常调整,指针域也需处理
表插入排序得到一个有序的链表，查找则 只能进行顺序查找，而不能进行随机查找， 如折半查找。为此，还需要对记录进行重排。 重排记录方法：按链表顺序扫描各结点， 将第i个结点中的数据元素调整到数组的第i个 分量数据域。因为第i个结点可能是数组的第j 个分量，数据元素调整仅需将两个数组分量 中数据元素交换即可，但为了能对所有数据 元素进行正常调整，指针域也需处理
【算法10.3】 1.j=l->r0]next;i-1;/指向第一个记录位置,从 第一个记录开始调整 2若4> length时,调整结束;否则, a.若j,j=-> riil.next;i计+;转(2)/数据元素应在 这分量中,不用调整,处理下一个结点 b.若j>i,|-> r.elem<->> lil. elen;∥交换数据元 素 Fl->rlj.next ∥保存下一个结点地址 -> ri. next=→> i nex;-> i next=;∥保持 后续链表不被中断 点Jp;计+;转(2)指向下一个处理的结 C.若ji, while(<i)j> rIil. next;/分量中原记录 已移走,沿j的指针域找寻原记录的位置转到a)
【算法10.3】 1. j=l->r[0].next；i=1； //指向第一个记录位置，从 第一个记录开始调整 2. 若i=l->length时，调整结束；否则， a. 若i=j，j=l->r[j].next；i++；转(2) //数据元素应在 这分量中，不用调整，处理下一个结点 b. 若j>i，l->r[i].elem<-->l->r[j].elem； //交换数据元 素 p=l->r[j].next； // 保存下一个结点地址 l->r[j].next=l->[i].next；l->[i].next=j； // 保持 后续链表不被中断 j=p；i++；转(2) // 指向下一个处理的结 点 c. 若j<i，while(j<i) j=l->r[j].next；//j分量中原记录 已移走，沿j的指针域找寻原记录的位置 转到(a)
【例10.3】对表插入排序进行重排示例 初 0123456 Mxa4938659776132749key或 状 态68150 723next域 i=1wx1338659776492749kev域 66(6)1504823ned域 i=2w32765977649384ks域 j=76(6)(7)504813mex域 i=3wx327389776496549ks域 1(2)76(6)(7)(7)04853next域
【例10.3】对表插入排序进行重排示例 0 1 2 3 4 5 6 7 8 MAXINT 49 38 65 97 76 13 27 49 6 8 1 5 0 4 7 2 3 初 始 状 态 key域 next域 MAXINT 13 38 65 97 76 49 27 49 6 (6) 1 5 0 4 8 2 3 i=1 MAXINT 13 27 65 97 76 49 38 49 6 (6) (7) 5 0 4 8 1 3 i=2 MAXINT 13 27 38 97 76 49 65 49 6 (6) (7) (7) 0 4 8 5 3 i=3 key域 next域 key域 next域 key域 next域 j=6 j=7 i=(2),7