數(shù)據(jù)結(jié)構(gòu)的的書說(shuō)鏈表需要1個(gè)特殊的頭節(jié)點(diǎn),但是std::list并沒有這么一個(gè)元素啊!

Ruckus優(yōu)科

list需要一個(gè)所謂的頭節(jié)點(diǎn)，這個(gè)頭節(jié)點(diǎn)是鏈表的開始，它指向鏈表的第一個(gè)元素，本身不存儲(chǔ)任何東西。這個(gè)我能理解。
但是我看std::list并沒有一個(gè)這么所謂的頭節(jié)點(diǎn)。

而且，我覺得，知道第一個(gè)節(jié)點(diǎn)就能訪問鏈表了，這個(gè)所謂的頭節(jié)點(diǎn)好像就是一種多余的存在啊。
求解釋

heguangwu

c++ stl庫(kù)文件可讀性不是很好，但理論是不會(huì)錯(cuò)的，雖然我也沒有看過(guò)代碼，所謂的頭結(jié)點(diǎn)其實(shí)就是一個(gè)指針而已

alwaysR9

頭節(jié)點(diǎn)存放或者不存放數(shù)據(jù)都可以，這看實(shí)現(xiàn)者自己的定義；
頭節(jié)點(diǎn)不存放數(shù)據(jù)可以令一些鏈表操作更方便，比如刪除連表中某個(gè)節(jié)點(diǎn)x：
假設(shè)頭節(jié)點(diǎn)不存放數(shù)據(jù)：

p = head;
q = head->next;
while (q) {
        if (q == x) {
                 p->next = q->next;
                 delete x;
                 break;
        }
        p = q;
        q = q->next;
}
return;

如果頭節(jié)點(diǎn)存放數(shù)據(jù)，那刪除節(jié)點(diǎn)的操作需要單獨(dú)處理頭節(jié)點(diǎn)：

if (x == head) {
        head = head->next;
        delete x;
        return;
}
p = head;
q = head->next;
while (q) {
        if (q == x) {
                 p->next = q->next;
                 delete x;
                 break;
        }
        p = q;
        q = q->next;
}
return;

不用糾結(jié)頭節(jié)點(diǎn)是否需要存數(shù)據(jù)，按照自己的想法定義就好

windoze

你看的那是什么數(shù)據(jù)結(jié)構(gòu)的書啊？鏈表這種東西都搞得這么復(fù)雜？

你有個(gè)指針指向第一個(gè)節(jié)點(diǎn)不就行了，還要什么“特殊的頭結(jié)點(diǎn)”？

dorodaloo

windoze 發(fā)表于 2015-12-03 22:14
你看的那是什么數(shù)據(jù)結(jié)構(gòu)的書��？鏈表這種東西都搞得這么復(fù)雜？

你有個(gè)指針指向第一個(gè)節(jié)點(diǎn)不就行了，還要 ...

windoze
是不會(huì)錯(cuò)的

action08

head本身是存在內(nèi)容的，要么為nil
也是個(gè)指針

action08

代碼語(yǔ)義翻譯一下，鏈表的指針不是用pq
這里數(shù)據(jù)結(jié)構(gòu)推薦用n next，p previous，代碼看起來(lái)規(guī)范些，當(dāng)然編譯器無(wú)所謂

windoze

回復(fù) 7# action08

pn……猛一看還以為說(shuō)三極管……

hanxin83

我也看過(guò)類似的說(shuō)法, 只不過(guò)說(shuō)是"可以有"而不是"需要".
有這個(gè)空的頭節(jié)點(diǎn), 只是為了避免:
1. 插入節(jié)點(diǎn), 每次都要額外判斷一下"鏈表是不是空".
2. 刪除節(jié)點(diǎn), 每次都要額外判斷一下"是不是刪了頭節(jié)點(diǎn)".

沒有當(dāng)然也是很好的, 我應(yīng)屆生畢業(yè)出來(lái)的時(shí)候弄個(gè)空的頭節(jié)點(diǎn)還被人說(shuō)是奇技淫巧呢~~~~