．[題目分析]本題要求將一個鏈表分解成兩個鏈表兩個鏈表都要有序兩鏈表建立過程中不得使用NEW過程申請空間這就是要利用原鏈表空間隨著原鏈表的分解新建鏈表隨之排序
PROC discreat(VAR listheadPQ:linkedlist)∥listhead是單鏈表的頭指針鏈表中每個結點由一個整數域DATA和指針域NEXT組成本算法將鏈表listhead分解成奇數鏈表和偶數鏈表分解由P和Q指向且P和Q鏈表是有序的
P:=NIL;Q:=NIL;∥P和Q鏈表初始化為空表
s:=listhead;
WHILE(s<>NIL)DO
[r:=s^NEXT;∥暫存s的後繼
IF s^DATA DIV =∥處理偶數
THEN IF P=NIL THEN[P:=s;P^NEXT:=NIL;]∥第一個偶數鏈結點
ELSE[pre:=P;
IF pre^DATA>s^DATA THEN[s^NEXT:=pre;P:=s;∥插入當前最小值結點修改頭指針]
ELSE[WHILE pre^NEXT<>NIL DO
IF pre^NEXT^DATA<s^DATA THEN pre:=pre^NEXT;∥查找插入位置
s^NEXT:=pre^NEXT;∥鏈入此結點
pre^NEXT:=s;
]
]
ELSE∥處理奇數鏈
IF Q=NIL THEN[Q:=s;Q^NEXT:=NIL;]∥第一奇數鏈結點
ELSE[pre:=Q;
IF pre^DATA>s^DATA THEN[s^NEXT:=pre; Q:=s; ]∥修改頭指針
ELSE[WHILE pre^NEXT<>NIL DO∥查找插入位置
IF pre^NEXT^DATA<s^DATA THEN pre:=pre^NEXT;
s^NEXT:=pre^NEXT;∥鏈入此結點
pre^NEXT:=s;
]
]∥結束奇數鏈結點
s:=r;∥s指向新的待排序結點
]∥結束WHILE(s<>NIL)DO
ENDP;∥結束整個算法
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23350.html
