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

．[题目分析]本题要求将一个链表分解成两个链表两个链表都要有序两链表建立过程中不得使用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;∥结束整个算法

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