如图所示，如果我们找到实线的指针，它们分别指向La中的Key1结点（p指针）、Key1的前一个结点（q指针）、Aj（从Key1结点开始的第len个结点，r指针）和Lb中的Key2的前一个结点（s指针），则根据链表操作，用图中的虚线指针连接，我们就可以把La中从Key1结点开始的共len个结点全部移动到Lb链表中。因此算法大致如下：

　　（1）找到p和q指针；

　　（2）找到r指针；

　　（3）找到s指针；

　　（4）r->next=s->next（即把Aj结点连接到K2结点之前）；

　　（5）s->next=q（即把K1结点连接到原来Lb中K2结点的前一个结点的后面）； 

　　注意：经过（4）、（5）两步操作，即实现了移动操作。

　　（6）要注意的是现在La链表已经断开，也必须重新连接上，故要：

　　但是注意一下程序，就会发现里面有很多判断，主要是看判断是否可以移动。我们考虑后（也可以看程序）发现，在以下几种情况下，操作不能进行：

　　（1）La或Lb是空链表；

　　（2）len表示个数的值，因此不能不大于0；

　　（3）La中不存在Key1的结点；

　　（4）La中从Key1结点开始的结点个数小于len个；

　　（4）Lb中不存在Key2的结点；

    3、现在主要是看程序结构是不是和我们自己考虑的算法符合。

　　程序段（5）～（8）：其中有p指针在向后移动，一直到Key1为止，因此，它们的功能就是找到指向Key1结点的指针；同时，另有一个指针prep一直在p的后面，因此它就是指向Key1的前一个结点的指针。

　　程序段（10）～（13）：其中有一个k变量，每次循环后增加1，因此它是一个计数器。通过计数len次，就可以找到从Key1结点开始的第len个结点。这时，应该有一个指针（q）同时移动，使得这个指针就是指向第len个结点的指针。

　　程序段（15）～（18）：其中有s指针在向后移动，一直到Key2为止，因此，它们的功能就是找到指向Key2的前一个结点的指针。

　　程序段（20）～（22）：就是移动La中的结点到Lb，并把La中断开的链表连接。从上述的分析发现，程序结构是和我们自己考虑的算法一致的。

    4、考虑细节，并填空。

　　（1）我们的目的是找指向第len个结点的指针，找到后循环应该结束，因此，要填k　　（2）q指针应该同时移动，故应填：q=q->next

　　（3）这一段程序的功能是找到指向Key2的前一个结点的指针。其中s指针是指向Key2结点的，而pres指针跟在s后面。但是pres指针缺少初值，因此，这儿应该给pres赋值。故，应填：pres=Lb。

　　（4）程序块（20）、（21）、（22）的功能是移动La中的结点到Lb，并把La中断开的链表连接。根据链表操作的方法，显然（20）是把La中断开的链表连接，因此，（4）应该填：prep->next；而（21）、（22）是移动La中的结点到Lb，因此，（5）应该填：pres->next。

上一页  [1] [2]