数据结构 | 每日一练（48）

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-