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

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1.已给如下关于单链表的类型说明：

TYPE

list=^node ;

node=RECORD

data: integer; next: list;

END;

以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为 p 和 q.

PROCEDURE mergelink(VAR p,q:list):

VAR h,r: list;

BEGIN

（1）______

h^.next:= NIL; r:=h;

WHILE((p<>NIL) AND (q<>NIL)) DO

IF (p^.data<=q^.data)

THEN BEGIN （2）___； r:=p; p:=p^.next； END

ELSE BEGIN （3）____； r:=q; q:=q^.next; END;

IF (p=NIL) THEN r^.next:=q;

（4）__；

p:=h^.next; dispose(h);

2.假设链表 p 和链表 q 中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为 max,且链表中其他结点的值都小于 max，在程序中取 max 为 9999。在各个链表中，每个结点的值各不相同，但链表 p 和链表 q 可能有值相同的结点（表头结点除外）。下面的程序将链表 q合并到链表 p 中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下

TYPE nodeptr=^nodetype；

nodetype=RECORD

data：integer； link：nodeptr;

END；

CONST max=9999;

PROCEDURE merge(VAR p:nodeptr;q:nodeptr);

VAR r,s: nodeptr;

BEGIN

r:=p;

WHILE (A)___ DO

BEGIN

WHILE r^.link^.data<q^.link^.data DO (B)___;

IF r^.link^.data>q^.link^.data

THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END

ELSE BEGIN (H)__; s:=q^.link; (I)__; dispose(s) END

END;

dispose(q)

END;

正确答案

1．

（1）new(h);∥生成头结点，以便于操作。

（2）r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p;

2.

A: r^.link^.data<>max AND q^.link^.data<>max

B: r:=r^.link

C: q^.link

D: q^.link

E: r^.link

F: r^.link

G: r:=s（或r:= r^.link）

H: r:=r^.link

I: q^.link:=s^.link

-end-

你学习了么?

文 | 闫小林