数据结构考研分类复习真题 第十章 答案[33]

PROCEDURE StraightInsertSort(VAR R:listtype;n:integer);

VAR ij:integer;

BEGIN

FOR i:= TO n DO {假定第一个记录有序}

BEGIN

R[]:=R[i]; j:=i; {将待排序记录放进监视哨}

WHILE R[]key<R[j]key DO {从后向前查找插入位置同时向后移动记录}

BEGIN R[j+]:=R[j]; j:=j; END;

R[j+]:=R[] {将待排序记录放到合适位置}

END {FOR}

END

TYPE pointer=↑node;

node=RECORD key:integer; link:pointer; END

PROCEDURE LINSORT(L:pointer);

VAR tpqs:pointer;

BEGIN

p:=L↑link↑link; {链表至少一个结点p初始指向链表中第二结点(若存在)}

L↑link↑link=NIL; {初始假定第一个记录有序}

WHILE p<>NIL DO

BEGIN q:=p↑link; {q指向p的后继结点}

s=L;

WHILE (s↑link<>NIL AND s↑link↑key<p↑key) DO

s:=s↑link; {向后找插入位置}

p↑link:=s↑link; s↑link=p;{插入结点}

p=q; {恢复p指向当前结点}

END {WHILE}

END; {LINSORT}

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []