c語言鏈表冒泡排序 C語言問題:怎樣實(shí)現(xiàn)對(duì)鏈表中兩個(gè)結(jié)點(diǎn)的交換?
C語言問題:怎樣實(shí)現(xiàn)對(duì)鏈表中兩個(gè)結(jié)點(diǎn)的交換?鏈表交換節(jié)點(diǎn)有兩種方式:交換節(jié)點(diǎn)內(nèi)容交換節(jié)點(diǎn)位置,如定義如下結(jié)構(gòu),分為數(shù)據(jù)部分和鏈表指針部分structdata{int num float score}s
C語言問題:怎樣實(shí)現(xiàn)對(duì)鏈表中兩個(gè)結(jié)點(diǎn)的交換?
鏈表交換節(jié)點(diǎn)有兩種方式:交換節(jié)點(diǎn)內(nèi)容交換節(jié)點(diǎn)位置,如定義如下結(jié)構(gòu),分為數(shù)據(jù)部分和鏈表指針部分structdata{int num float score}struct stu{structdata struct stu*next}*head,*P1,*P2,*P3,*p4head->p1->p2->p3->p4交換節(jié)點(diǎn)的內(nèi)容。節(jié)點(diǎn)的順序保持不變。交換兩個(gè)節(jié)點(diǎn)時(shí),只交換數(shù)據(jù)部分,下一個(gè)指針不移動(dòng)。例如,交換P1和P3(data)的內(nèi)容:structudata t=P1->datap1->data=P3->datap3->data=t//這是可以的。為了保持鏈表的正常連接,需要重置next的值。這個(gè)過程有點(diǎn)復(fù)雜,例如:交換P1和P3的位置:最后更改為:head->p3->p2->p1->p4。首先,找到P1的頭和P3的P2,然后開始重新分配鏈表的排列:1。(head)的新繼承節(jié)點(diǎn)P1的頭應(yīng)成為P3(P4)3的原繼承節(jié)點(diǎn),P3(P2)的新繼承節(jié)點(diǎn)應(yīng)成為p14、P3的新繼承節(jié)點(diǎn),P1(P2)結(jié)構(gòu)的原繼承節(jié)點(diǎn)stu*p1p,*P3P,*pfor(P=headp!=nullp=P->next){如果(P->next==P1)p1p=P//找到P1的前向頭如果(P->next==P3)P3P=P//找到P3的前體}p1p->next=P3//P3的前體節(jié)點(diǎn)的新后繼節(jié)點(diǎn)成為P3的前體節(jié)點(diǎn)head->p3 struct stu*tnext=P1->next//保存P1(P2)的前體節(jié)點(diǎn)p1->next=P3->next//p1的新后繼節(jié)點(diǎn)成為P3(P4)的前體節(jié)點(diǎn)p1->p4p3p->next=p1//P3當(dāng)新后繼節(jié)點(diǎn)成為p1 P2->p1p3->next=tnext//P3時(shí),新后繼節(jié)點(diǎn)成為原始后繼節(jié)點(diǎn)P3->p2
p1的交換列表節(jié)點(diǎn),通常是exchange節(jié)點(diǎn)結(jié)構(gòu)的內(nèi)容,下一個(gè)指針除外。傳統(tǒng)的、真實(shí)有效的方法是在不交換其他成員的情況下交換節(jié)點(diǎn)的關(guān)系指針。一個(gè)節(jié)點(diǎn)有自己的指針和指向下一個(gè)節(jié)點(diǎn)的指針?!八约旱闹羔槨笔巧弦粋€(gè)節(jié)點(diǎn)的下一個(gè)指針,所以我們需要交換上一個(gè)節(jié)點(diǎn)的下一個(gè)指針和當(dāng)前級(jí)別的下一個(gè)指針。而且,由于頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的關(guān)系與中間節(jié)點(diǎn)的關(guān)系不同,在與頭節(jié)點(diǎn)和尾節(jié)點(diǎn)交換時(shí),需要處理的上、中間節(jié)點(diǎn)有細(xì)微的區(qū)別。所以操作起來比較麻煩,如果關(guān)系處理不好,就會(huì)出錯(cuò)。另一種方法是交換除下一個(gè)指針以外的所有成員。思路非常清晰,就是代碼比較長(zhǎng),節(jié)點(diǎn)成員多的時(shí)候比較明顯,編寫比較麻煩。有一種確保思路清晰、書寫方便的方法是“將需要交換的兩個(gè)節(jié)點(diǎn)作為一個(gè)整體交換,然后將下一個(gè)指針交換回來”。我工作時(shí)經(jīng)常用這種方法。然而,盡管代碼讀起來流暢、短視,但你不能指望它能提高效率——因?yàn)樵谇袚Q結(jié)構(gòu)變量時(shí),雖然寫得很短,但實(shí)際上是一個(gè)成員一個(gè)成員地交換,更不用說“將下一個(gè)指針交換回來”的操作了。個(gè)人經(jīng)驗(yàn),供參考。