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

数据结构

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

——老子

1

每日一练

1.

循环链表 a 和 b 的结点值为字母，其中 a 表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在 a，b 两链表中出现的字母，且 c 中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设 a，b 的结点数分别为 m，n）

TYPE

link=^node;

node=RECORD

key:char; next:link

END;

PROC jj(a,b:link; VAR c:link);

VAR p,q,r,s:link;

BEGIN

new(c);c^.next:=c; q:=a; p:=a^.next;

WHILE p<>a DO

[（1）___；

WHILE p^.key=p^.next^.key DO [q:=p; p=p^.next];｛跳过相同字母｝

r:=b^.next ; （2）_____;

WHILE r^.key <>p^.key DO r:=r^.next;

IF r<>b THEN

[ s:=p; q^.next:=p^.next; （3） ;

s^.next:=c^.next; c^.next:=s; c:=s ]

ELSE [ q:=p; p:=p^.next ]

]; c:=c^.next；

END;

算法时间复杂度为 O（4）___ 。

正确答案

1.

(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值

(2)b^.key:=p^.key∥b的头结点起监视哨作用

(3)p:=p^.next∥找到a,b表中共同字母，a表指针后移

(4)0(m*n)

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-