1、理解題目：

　　已知條件為兩個(gè)鏈表La和Lb，最后得到的結(jié)果也是兩個(gè)鏈表，只不過(guò)是La中的部分結(jié)點(diǎn)移動(dòng)到Lb中，因此，本問(wèn)題主要是解決是怎么移動(dòng)的。

    2、算法：

　　在題目中沒(méi)有給出結(jié)點(diǎn)移動(dòng)的算法，我們先可以結(jié)合實(shí)例自己設(shè)計(jì)一個(gè)算法，然后看是不是與程序中的算法一致。如果不是，則再找算法。

    實(shí)例：

　　如圖所示，如果我們找到實(shí)線的指針，它們分別指向La中的Key1結(jié)點(diǎn)（p指針）、Key1的前一個(gè)結(jié)點(diǎn)（q指針）、Aj（從Key1結(jié)點(diǎn)開(kāi)始的第len個(gè)結(jié)點(diǎn)，r指針）和Lb中的Key2的前一個(gè)結(jié)點(diǎn)（s指針），則根據(jù)鏈表操作，用圖中的虛線指針連接，我們就可以把La中從Key1結(jié)點(diǎn)開(kāi)始的共len個(gè)結(jié)點(diǎn)全部移動(dòng)到Lb鏈表中。因此算法大致如下：

　�。�1）找到p和q指針；

　�。�2）找到r指針；

　�。�3）找到s指針；

　　（4）r->next=s->next（即把Aj結(jié)點(diǎn)連接到K2結(jié)點(diǎn)之前）；

　�。�5）s->next=q（即把K1結(jié)點(diǎn)連接到原來(lái)Lb中K2結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的后面）； 

　　注意：經(jīng)過(guò)（4）、（5）兩步操作，即實(shí)現(xiàn)了移動(dòng)操作。

　�。�6）要注意的是現(xiàn)在La鏈表已經(jīng)斷開(kāi)，也必須重新連接上，故要：

　　但是注意一下程序，就會(huì)發(fā)現(xiàn)里面有很多判斷，主要是看判斷是否可以移動(dòng)。我們考慮后（也可以看程序）發(fā)現(xiàn)，在以下幾種情況下，操作不能進(jìn)行：

　�。�1）La或Lb是空鏈表；

　�。�2）len表示個(gè)數(shù)的值，因此不能不大于0；

　�。�3）La中不存在Key1的結(jié)點(diǎn)；

　�。�4）La中從Key1結(jié)點(diǎn)開(kāi)始的結(jié)點(diǎn)個(gè)數(shù)小于len個(gè)；

　　（4）Lb中不存在Key2的結(jié)點(diǎn)；

    3、現(xiàn)在主要是看程序結(jié)構(gòu)是不是和我們自己考慮的算法符合。

　　程序段（5）～（8）：其中有p指針在向后移動(dòng)，一直到Key1為止，因此，它們的功能就是找到指向Key1結(jié)點(diǎn)的指針；同時(shí)，另有一個(gè)指針prep一直在p的后面，因此它就是指向Key1的前一個(gè)結(jié)點(diǎn)的指針。

　　程序段（10）～（13）：其中有一個(gè)k變量，每次循環(huán)后增加1，因此它是一個(gè)計(jì)數(shù)器。通過(guò)計(jì)數(shù)len次，就可以找到從Key1結(jié)點(diǎn)開(kāi)始的第len個(gè)結(jié)點(diǎn)。這時(shí)，應(yīng)該有一個(gè)指針（q）同時(shí)移動(dòng)，使得這個(gè)指針就是指向第len個(gè)結(jié)點(diǎn)的指針。

　　程序段（15）～（18）：其中有s指針在向后移動(dòng)，一直到Key2為止，因此，它們的功能就是找到指向Key2的前一個(gè)結(jié)點(diǎn)的指針。

　　程序段（20）～（22）：就是移動(dòng)La中的結(jié)點(diǎn)到Lb，并把La中斷開(kāi)的鏈表連接。從上述的分析發(fā)現(xiàn)，程序結(jié)構(gòu)是和我們自己考慮的算法一致的。

    4、考慮細(xì)節(jié)，并填空。

　　（1）我們的目的是找指向第len個(gè)結(jié)點(diǎn)的指針，找到后循環(huán)應(yīng)該結(jié)束，因此，要填k　�。�2）q指針應(yīng)該同時(shí)移動(dòng)，故應(yīng)填：q=q->next

　�。�3）這一段程序的功能是找到指向Key2的前一個(gè)結(jié)點(diǎn)的指針。其中s指針是指向Key2結(jié)點(diǎn)的，而pres指針跟在s后面。但是pres指針缺少初值，因此，這兒應(yīng)該給pres賦值。故，應(yīng)填：pres=Lb。

　�。�4）程序塊（20）、（21）、（22）的功能是移動(dòng)La中的結(jié)點(diǎn)到Lb，并把La中斷開(kāi)的鏈表連接。根據(jù)鏈表操作的方法，顯然（20）是把La中斷開(kāi)的鏈表連接，因此，（4）應(yīng)該填：prep->next；而（21）、（22）是移動(dòng)La中的結(jié)點(diǎn)到Lb，因此，（5）應(yīng)該填：pres->next。

上一頁(yè)  [1] [2] 

轉(zhuǎn)帖于：軟件水平考試_考試吧