C++教程:什么是鏈表

2020-05-23 14:26:55

字體：大中小

供稿：網(wǎng)友

大家都知道自行車，可是你有沒有仔細觀察過自行車的鏈條呢？如下圖9.5.1就是一段自行車鏈條的樣子。

我們發(fā)現(xiàn)，自行車的鏈條雖然很長，卻是由一個個相同的小環(huán)節(jié)連接而成的。如左下圖9.5.2所示。每個環(huán)節(jié)又可以分成兩部分：一部分是一個鐵圈，讓別的環(huán)節(jié)能夠連接它；另一部分則是一個鐵拴，可以去連接別的環(huán)節(jié)。于是，將這些環(huán)節(jié)一一連接起來，就形成了長長的鏈條。
這時候，我們想到了這樣一種結(jié)構(gòu)：

struct node
{
int data;
node *next;
};
這個結(jié)構(gòu)有兩個成員數(shù)據(jù)，一個是整數(shù)data，另外一個是指向這種結(jié)構(gòu)的指針next。那么如果有若干個這樣的結(jié)構(gòu)變量，就能像自行車鏈條一樣，把這些變量連接成一條鏈子。如左下圖9.5.3所示。

我們把這些利用結(jié)構(gòu)指針連接起來的結(jié)構(gòu)變量稱為鏈表（Link List），每一個結(jié)構(gòu)變量（相當于鏈條中的每個環(huán)節(jié)）稱為鏈表的結(jié)點（Node）。如右上圖9.5.4所示。

和數(shù)組一樣，鏈表也可以用來存儲一系列的數(shù)據(jù)，它也是電腦中存儲數(shù)據(jù)的最基本的結(jié)構(gòu)之一。然而，我們已經(jīng)擁有了數(shù)組，也了解了數(shù)組的動態(tài)分配（堆內(nèi)存），我們?yōu)槭裁催€需要鏈表呢？

相信很多人都玩過即時戰(zhàn)略游戲（RTS），比如時下流行的魔獸爭霸、曾紅極一時的紅色警戒?？墒谴蠹矣袥]有考慮過，每個戰(zhàn)斗單位都有它們各自的屬性，電腦又是如何為我們造出來的部隊分配內(nèi)存的呢？

顯然，部隊的數(shù)量在程序執(zhí)行之前是未知的。如果用數(shù)組來存儲這些數(shù)據(jù)，那么就會造成游戲前期浪費內(nèi)存（沒有那么多的部隊），游戲后期存儲空間不夠（戰(zhàn)斗單位數(shù)大大增加）的情況。

那么使用數(shù)組的動態(tài)分配行不行呢？還是不行。因為部隊的數(shù)量在程序執(zhí)行的時候仍然是未知的。甚至連玩家自己也不知道要造多少戰(zhàn)斗單位，只是根據(jù)戰(zhàn)斗的實際情況來發(fā)展自己的勢力。所以，這時候最合理的內(nèi)存分配方式就是每造一個戰(zhàn)斗單位分配一個內(nèi)存空間。

然而，新問題又出現(xiàn)了：建造各單位的時間一般不可能是完全連續(xù)的，根據(jù)不同時刻程序運行的實際情況，每個單位分配到的內(nèi)存空間也不是連續(xù)的了?？臻g不連續(xù)就意味著沒有了方便的數(shù)組下標。我們就很難把這些零零散散的內(nèi)存空間集中起來管理。

鏈表的出現(xiàn)改變了這個情況。它可以在程序運行時根據(jù)實際需要一個個分配堆內(nèi)存空間，并且用它的指針可以把一系列的空間串聯(lián)起來，就像一條鏈子一樣。這樣一來，我們就能夠利用指針對整個鏈表進行管理了。

上一篇：C++教程:鏈表的創(chuàng)建和遍歷

下一篇：C++教程:C++結(jié)構(gòu)數(shù)組與結(jié)構(gòu)指針