C++教程:什么是鏈表

2020-05-23 14:26:55

字體：大中小

來源：轉載

供稿：網友

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

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

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

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

和數組一樣，鏈表也可以用來存儲一系列的數據，它也是電腦中存儲數據的最基本的結構之一。然而，我們已經擁有了數組，也了解了數組的動態分配（堆內存），我們為什么還需要鏈表呢？

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

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

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

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

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

上一篇：C++教程:鏈表的創建和遍歷

下一篇：C++教程:C++結構數組與結構指針