數據結構考研分類復習真題 第十章 答案[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}

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23174.html