Re: [問題] double link list做swap

看板C_and_CPP (C/C++)作者LPH66 (ha(ruhi|yate)ism)時間17年前 (2007/04/12 12:53)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

※ 引述《skyblue2021 (空虛的人生)》之銘言： : 我想用double link list做2個node的swap : 可是一直跑不出來@@ : trace了好幾遍還是不知道問題到底出在哪 : 以下是我的程式碼 : 感覺好像是node A那裡的link出了問題 : 可是想了很久還是不知道為什麼有問題@@" : 麻煩請大大指點一下,感謝~~ 那就來追追看吧 : void swap(void) : { <del> : if(a != 0 && b != 0) : { 已經找到兩個要換的node: ┐←┬─┐←┬ ┐←┬─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┴→└─┴→└ ┴→└─┴→└ : ptr=B; ptr ↓ ┐←┬─┐←┬ ┐←┬─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┴→└─┴→└ ┴→└─┴→└ : ptr->llink=B->llink; ptr ↓ ┐←┬─┐←┬ ┐←┬─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┴→└─┴→└ ┴→└─┴→└ : ptr->rlink=B->rlink; ptr ↓ ┐←┬─┐←┬ ┐←┬─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┴→└─┴→└ ┴→└─┴→└ (以上兩步都沒有作用，這間接造成你的問題，詳後述) : (A->llink)->rlink=B; ptr ↓ ┐←┬─┐←┬ ┐←┬─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┤ └─┴→└ ┴→└─┴→└ │ ↑ └──────────────┘ : B->llink=A->llink; ┌─────────────┐ptr ↓ │↓ ┐←┬─┐←┬ ┐ ├─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┤ └─┴→└ ┴→└─┴→└ │ ↑ └──────────────┘ : B->rlink=A->rlink; ┌─────────────┐ptr ↓ │↓ ┐←┬─┐←┬ ┐ ├─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┤ └─┴→└ ┴→└─┤ └ │ ↑ ↑│ └──────────────┘│ └─────────┘ : (A->rlink)->llink=B; ┌────────┐ ┌─────────────┐│ptr ↓ │ │↓↓ ┐←┬─┐ ├ ┐ ├─┐←┬ │ │Ａ│ │ │ │Ｂ│ │ ┤ └─┴→└ ┴→└─┤ └ │ ↑ ↑│ └──────────────┘│ └─────────┘ : (ptr->llink)->rlink=A; : (ptr->rlink)->llink=A; 這兩行亂掉了看上圖就知道原來在B的左邊那個點已經沒人指它了但你卻仍然想用ptr->llink來指到它所以就出問題而原因則是你前面的 B->llink=A->llink; B->rlink=A->rlink; 這兩行就先指走了以致於沒人指到B原先的鄰居而你原先試著保留這兩個指標的嘗試 (即上面我說沒作用的那兩行) 會沒有作用的原因則是因為你直接ptr=B; 這造成當你想把指標留到 ptr->llink 和 ptr->rlink 時寫入的卻是原本的 B->llink 和 B->rlink 因此它根本就沒有保留到然後在你改了 B->llink 和 B->rlink 後 ptr->llink 和 ptr->rlink 就不見了 : } : else printf("There is no such node number!!\n"); : system("PAUSE"); : } 另外附註一件事即使你把這個問題修正了當A和B相鄰時還是會錯這要當成special case來處理 -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」実琴：「難道你沒有男人的尊嚴了嗎?!」亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」－－プリンセス・プリンセス第二話 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 192.192.197.115 ※ 編輯: LPH66 來自: 192.192.197.115 (04/12 12:53)