9-17设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个 元素,头指针为r。试设计一个算法,对其进行二路归并排序,要求不移动结点中的元素,只 改各链结点中的指针,排序后r仍指示结果链表的第一个结点。(提示:先对待排序的单链表 进行一次扫描,将它划分为若干有序的子链表其表头指针存放在一个指针队列中。当队列 不空时重复执行,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头 指针存放到队列中。如果队列中退出一个有序子链表后变成空队列,则算法结束。这个有序 子链表即为所求。) 【解答】 (1)两路归并算法 procedure merge( ha, hb: pointer; var hc: pointer ) var pa, pb, pc: pointer; if hat data<=hb↑data then begin hc =ha; pa: =hat next; pb: =hb; end else begin he: =hb; pb: =hbt. next; pa =ha; end; pc:=hc; while(pa nil )and( pb o nil)do then be pct next: =pa; pc: =pa; pa =pat. next; pct, next: =pb; pc =pb; pb: =pbt.next if pa o nil then pcf. next (2)归并排序主程序 pointer ) vars, t: pointer; var Q: Queue ifr=nil then return: SetEmpty (0); S =r; Enqueue( @,r); while s< nil do begin t:=s↑next while(to nil)and(st. data<=tf. data)do begin s t' =tf ifto nil then T; EnQueue( @, s ); end while not IsEmpty( o)d if IsEmpty( @) then break DEQueue( 0);9-17 设有 n 个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个 元素, 头指针为 r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只 改各链结点中的指针, 排序后 r 仍指示结果链表的第一个结点。（提示：先对待排序的单链表 进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。当队列 不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头 指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序 子链表即为所求。) 【解答】 (1) 两路归并算法 procedure merge ( ha, hb : pointer; var hc : pointer ); var pa, pb, pc : pointer; begin if ha↑ .data <= hb↑ .data then begin hc := ha; pa := ha↑ .next; pb := hb; end else begin hc := hb; pb := hb↑ .next; pa := ha; end; pc := hc; while ( pa <> nil ) and ( pb <> nil ) do if pa↑ .data <= pb↑ .data then begin pc↑ .next := pa; pc := pa; pa := pa↑ .next; end else begin pc↑ .next := pb; pc := pb; pb := pb↑ .next; end; if pa <> nil then pc↑ .next := pa else pc↑ .next := pb; end; (2) 归并排序主程序 procedure mergesort( var r : pointer ); var s, t : pointer; var Q : Queue; begin if r = nil then return; SetEmpty ( Q ); s:= r; Enqueue( Q, r); while s <> nil do begin t := s↑ .next; while ( t <> nil ) and ( s↑ .data <= t↑ .data ) do begin s:= t; t := t↑ .next; end; if t <> nil then begin s↑ .next := nil; s:= t; EnQueue( Q, s); end; end; while not IsEmpty( Q ) do begin r := DlQueue( Q ); if IsEmpty( Q ) then break; s := DlQueue( Q );