1
每日一
1．设 Listhead 为一单链表的头指针，单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成，整数在单链表中是无序的。编一 PASCAL 过程，将 Listhead 链中结点分成一个奇数链和一个偶数链，分别由 P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW 过程申请空间。
类似本题的另外叙述有：
（1）设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于零的结点（链表 A 的元素类型为整型，要求 B、C 表利用 A 表的结点）。
(2) 设 L 为一单链表的头指针，单链表的每个结点由一个整数域 data 和指针域 NEXT 组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，分别由 P，Q 指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间。
(3) 将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
1) 写出其类型定义：
2) 写出算法。
正确答案
ps：||代表注释
1．[题目分析]本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。
PROC discreat(VAR listhead,P,Q: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 2=0 ∥处理偶数。
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；∥结束整个算法。
[算法讨论]由于算法要求“不得使用NEW过程申请空间，也没明确指出链表具有头结点，所以上述算法复杂些，它可能需要在第一个结点前插入新结点，即链表的头指针会发生变化。如有头结点，算法不必单独处理在第一个结点前插入结点情况，算法会规范统一，下面的（1）是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0（DATA DIV 2=0）判断的。
类似本题的其它题解答如下：
（1）[题目分析]本题基本类似于上面第7题，不同之处有二。一是带头结点，二是分解后的两个链表，一个是数据值小于0，另一个是数据值大于0。由于没明确要求用类PASCAL书写算法，故用C书写如下。
void DisCreat1(LinkedList A)
∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。
{B=A;
C=(LinkedList )malloc( sizeof(LNode));∥为C申请结点空间。
C->next=null ∥C初始化为空表。
p=A->next; ∥p为工作指针。
B->next=null; ∥B表初始化。
while(p!=null)
{r=p->next; ∥暂存p的后继。
if (p->data<0)∥小于0的放入B表。
{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。
else {p->next=C->next; C->next=p; }
p=r;∥p指向新的待处理结点。
}
}∥算法结束。
[算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。
（2） 本题同上面第7题，除个别叙述不同外，本质上完全相同，故不再另作解答。
（3）[题目分析]本题中的链表有头结点，分解成表A和表B，均带头结点。分解后的A表含有原表中序号为奇数的元素，B表含有原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表尾的指针即可方便实现。
void DisCreat3(LinkedList A)
∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号为奇数
∥的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。
{i=0;∥i记链表中结点的序号。
B=(LinkedList)malloc( sizeof(LNode);∥创建B表表头。
B->next=null; ∥B表的初始化。
LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。
ra=A;rb=B;
p=A->next; ∥p为链表工作指针，指向待分解的结点。
A->next=null; ∥置空新的A表
while(p!=null)
{r=p->next; ∥暂存p的后继。
i++;
if(i%2==0) ∥处理原序号为偶数的链表结点。
{p->next=rb->next;∥在B表尾插入新结点；
rb->next=p; rb=p;∥rb指向新的尾结点；
}
else∥处理原序号为奇数的结点。
{p->next=ra->next; ra->next=p; ra=p; }
p=r; ∥将p恢复为指向新的待处理结点。
}∥算法结束
如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！
-end-