第一章 鏈表

何謂鏈表

我們知道，一般用數(shù)組存放一組數(shù)據(jù)時(shí)，必須事先定義固定的長(zhǎng)度（即元素個(gè)數(shù)）。這在某些問(wèn)題的解決中，并不是特別的適用。例如，記錄不同班級(jí)的學(xué)生數(shù)據(jù)時(shí)，由于各班人數(shù)不同，會(huì)出現(xiàn)開(kāi)辟過(guò)大的數(shù)組導(dǎo)致內(nèi)存浪費(fèi)、開(kāi)辟過(guò)小的數(shù)組導(dǎo)致數(shù)組元素不夠用的情況。而鏈表可以根據(jù)需要?jiǎng)討B(tài)開(kāi)辟內(nèi)存單元，是一種常見(jiàn)的重要數(shù)據(jù)結(jié)構(gòu)。圖1.1所示為最簡(jiǎn)單的一種鏈表結(jié)構(gòu)。

圖1.1

鏈表如同鐵鏈一樣，一環(huán)扣一環(huán)，中間是不能斷開(kāi)的。打個(gè)通俗的比方：幼兒園老師帶領(lǐng)小朋友出來(lái)散步，老師牽著第一個(gè)小朋友的手，第一個(gè)小朋友的手牽著第二個(gè)小朋友的手……這就是一個(gè)“鏈”，最后一個(gè)小朋友的手是空的。

老師即“頭指針”變量，圖1.1中以Head表示，它存放一個(gè)地址。鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)該包括兩部分：一為實(shí)際元素值，一為下一結(jié)點(diǎn)的地址。

最后一個(gè)元素不指向其他元素，它被稱為“表尾”，以“NULL”表示，“NULL”在C++語(yǔ)言里指向“空地址”。

很顯然，這種鏈表的數(shù)據(jù)結(jié)構(gòu)，必須要用指針變量才能實(shí)現(xiàn)。