[说明]
函数DelXInsY(LinkedList Lx,LinkedList Ly,int key 1,int key2,int len)的功能是,将线性表X中关键码为key1的结点开始的len个结点,按原顺序移至线性表Y中关键码为key2的结点之前,若移动成功,则返回0;否则返回-1。线性表的存储结构为带头结点的单链表,Lx为表X的头指针,Ly为表Y的头指针。单链表结点的类型定义如下。
typedef struct node
int key;
struct node *next;
*LinkedList;
[C程序代码]
参考答案:k<len或其等价形式
(2) q=q_>next或其等价形式
(3) pres=Ly或其等价形式
(4) prep_>next
(5) prep_>next
解析:由题干说明及所给出的C程序代码可知,已知条件为两个链表Lx和Ly,最后得到的结果也是两个链表,只不过是将Lx中的部分结点移动到Ly中,因此,本问题主要解决的问题是怎么合理地移动相关结点。
在题干信息中没有给出结点移动的具体算法描述,这就要求解题时要先结合实例自行设计一个算法,然后观察是否与程序中的算法一致。若不一致,则再寻找其他算法。在自己设计相关算法之前,最好要先看一看题目给出的算法提示,在给出的C程序代码中,总是有一些蛛丝马迹可以让我们找到突破口的,这些地方通常都会给出题目所用算法的暗示。
如图8-11所示,如果找到实线的指针,它们分别指向Lx中的key1结点(p指针)、key1的前一个结点(q指针)、Xj(从key1结点开始的第len个结点,r指针)和Ly中的key2的前一个结点(s指针),则根据链表操作,用图8-11中的虚线指针连接,就可以将Lx中从key1结点开始的len个结点全部移动到Ly链表中。因此算法大致如下所示。
(1) 找到p和q指针。
(2) 找到r指针。
(3) 找到s指针。
(4) r_>next=-s_>next(把xj结点连接到K2结点之前)。
(5) s_>next=q(把K1结点连接到原来Ly中K2结点的前一个结点后面)。注意:经过(4)、(5)两步操作,即实现了移动操作。
(6) 要注意的是现在Lx链表已经断开,程序还必须将其重新连接上。
但是注意阅读一下试题所给出的C程序代码,就会发现里面有很多判断,主要是看判断是否可以移动。但在以下几种情况下,不允许进行移动操作。
(1) Lx或Ly是空链表。
(2) len表示个数的值,因此必须大于0。
(3) Lx中不存在key1的结点。
(4) Lx中从key1结点开始的结点个数小于len个。
(5) Ly中不存在key2的结点。
上述考虑的算法与C代码之问的对应关系如下。
第5~8行程序段:其中有p指针在向后移动,一直到key1为止,因此,它们的功能就是找到指向key1结点的指针;同时,还有一个指针prep一直在p的后面,因此它就是指向key1的前一个结点的指针。
第10~13行程序段:其中有一个k变量,每次循环后增加1,因此它是一个计数器。通过计数len次,就可以找到从key1结点开始的第len个结点。这时,应该有一个指针(q)同时移动,使得这个指针就是指向第len个结点的指针。
第15~18行程序段:其中有s指针在向后移动,一直到key2为止,因此,它们的功能就是找到指向key2的前一个结点的指针。
第20~22行程序段:就是移动Lx中的结点到Ly,并把Lx中断开的链表连接。
(1) 本程序设计的关键点之一是寻找指向第len个结点的指针,找到后循环就应该结束,因此,(1)空缺处应该填入k<len。若该空缺处错误地填入k<=len,则会使指针多移动一次。例如,当len=3时,指针其实只要移动两次就可以了。
(2) q指针应该同时移动,因此(2)空缺处应该填入q=q_>next。
(3) 空缺处(3)所处的程序段的功能是:查找到指向key2的前一个结点的指针。其中,指针s是指向key2结点的,而指针pres跟在指针s后面。但是指针pres缺少初值,因此,(3)空缺处应该给pres赋值,即应填入pres=Ly。
(4) 第20~22行程序段的功能是:移动Lx中的结点到Ly,并把Lx中断开的链表连接。根据链表操作的方法,显然第20行语句是将Lx中断开的链表再连接上,因此,(4)空缺处应该填入prep_>next。而第21行和第22行语句是移动Lx中的结点到Ly,因此,(5)空缺处应该填入pres_>next。