数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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-
你学习了么?
文 | 闫小林