首頁(yè) 猿問(wèn) 關(guān)于數(shù)據(jù)結(jié)構(gòu)問(wèn)題？

關(guān)于數(shù)據(jù)結(jié)構(gòu)問(wèn)題？

數(shù)據(jù)結(jié)構(gòu)

幕布斯6054654 2018-08-05 10:06:29

關(guān)于單鏈表第i個(gè)數(shù)據(jù)刪除節(jié)點(diǎn)的算法怎么理解？我說(shuō)一下我目前對(duì)該算法的理解。示意圖如下，在該算法q=p->next；之前的內(nèi)容是使指針變量p遍歷鏈表，直到找到第i個(gè)結(jié)點(diǎn)元素。假設(shè)它找到了，*p指針也是指向的a(i)結(jié)點(diǎn)，為什么后面的刪除操作要把p當(dāng)作指向a(i-1)結(jié)點(diǎn)？

查看完整描述

1 回答

犯罪嫌疑人X

TA貢獻(xiàn)2080條經(jīng)驗(yàn) 獲得超4個(gè)贊

鏈表是有頭結(jié)點(diǎn)的，而頭結(jié)點(diǎn)在第一個(gè)節(jié)點(diǎn)之前，如你圖中所畫(huà)，假如a[i]為第一個(gè)元素，那么a[i-1]就是頭指針，頭指針里面不存放數(shù)據(jù)。假設(shè)你要找第1個(gè)節(jié)點(diǎn)，while(p->next && j < i)，這個(gè)循環(huán)退出的條件是p->next為NULL或j==i，剛開(kāi)始j=1，p指向的是頭節(jié)點(diǎn)，這個(gè)時(shí)候如果第一個(gè)節(jié)點(diǎn)不存在（即鏈表為空），則有p->next為空（頭結(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn)）；如果第一個(gè)節(jié)點(diǎn)存在則一定有j==i（i為1）成立，這個(gè)時(shí)候p指向的仍然是頭結(jié)點(diǎn)，所以就有下面的q=p->next，這個(gè)q就是第i個(gè)節(jié)點(diǎn)，只不過(guò)推遲執(zhí)行了一步。
另外，書(shū)上那份代碼有點(diǎn)小問(wèn)題，中間的判斷if(!(p->next) || j > i)當(dāng)中的j>i完全是多余的，因?yàn)閺牡谝粋€(gè)while循環(huán)結(jié)束時(shí)，j最多等于i，不會(huì)大于i。

反對(duì) 回復(fù) 2018-08-06