線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十）

        我們之前學(xué)習(xí)了順序存儲(chǔ)結(jié)構(gòu)線性表，雖然它很強(qiáng)大。但是存在一個(gè)不算是缺點(diǎn)的缺點(diǎn)：那便是在插入和刪除時(shí)。需要移動(dòng)大量的元素。那么該如何解決這個(gè)問題呢？我們直接會(huì)想到的是在數(shù)據(jù)元素之間空出位置，那么在后面的插入時(shí)便會(huì)很方便。那么此時(shí)便會(huì)出現(xiàn)一個(gè)問題：究竟留出多少空間合適呢？有一個(gè)極端是我們需要插入的是 n 個(gè)元素。換而言之，這個(gè)空間需要預(yù)留無(wú)窮大，那么這個(gè)肯定是不現(xiàn)實(shí)的。

        此時(shí)便出現(xiàn)了我們本節(jié)要講的內(nèi)容：鏈?zhǔn)酱鎯?chǔ)。我們來(lái)看看鏈?zhǔn)酱鎯?chǔ)的定義：為了表示每個(gè)數(shù)據(jù)元素與直接后繼元素之間的邏輯關(guān)系；數(shù)據(jù)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)直接后繼的信息。如下

        我們來(lái)看看鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)，它是基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，每個(gè)結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域。數(shù)據(jù)域是指粗出數(shù)據(jù)元素本身；而指針域是指存儲(chǔ)相鄰結(jié)點(diǎn)的地址。關(guān)系如下所示

        順序表指的是基于順序存儲(chǔ)結(jié)構(gòu)的線性表，鏈表指的是基于鏈?zhǔn)酱鎯?chǔ)機(jī)構(gòu)的線性表。鏈表分為三種：a> 單鏈表，即沒和結(jié)點(diǎn)只包含直接后繼的地址信息；b> 循環(huán)鏈表，即單鏈表中的最后一個(gè)結(jié)點(diǎn)的直接后繼為第一個(gè)結(jié)點(diǎn)；c> 雙向鏈表，即單鏈表中的結(jié)點(diǎn)包含治腳氣前驅(qū)和后繼的地址信息。

        下來(lái)我們來(lái)看看鏈表中的基本概念：A、頭結(jié)點(diǎn)。鏈表中的輔助結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針；B、數(shù)據(jù)結(jié)點(diǎn)。鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，表現(xiàn)形式為：（數(shù)據(jù)元素，地址）；C、尾結(jié)點(diǎn)。鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，包含的地址信息為空。那么單鏈表中的結(jié)點(diǎn)是怎樣進(jìn)行定義的呢？如下

        我們來(lái)看看單鏈表中的內(nèi)部結(jié)構(gòu)，如下

        頭結(jié)點(diǎn)在單鏈表中的意義是：輔助數(shù)據(jù)元素的定位，方便插入和刪除操作；因此，頭結(jié)點(diǎn)不存在存儲(chǔ)實(shí)際的實(shí)際數(shù)據(jù)元素。那么在目標(biāo)位置處是如何插入數(shù)據(jù)元素呢？1、從頭結(jié)點(diǎn)開始，通過 current 指針定位到目標(biāo)位置；2、從堆空間申請(qǐng)新的 Node 結(jié)點(diǎn)；3、執(zhí)行操作：node->value = e; node->next = current->next; current->next = node; 同理，在目標(biāo)位置處刪除數(shù)據(jù)元素：1、從頭結(jié)點(diǎn)開始，通過 current 指針定位到目標(biāo)位置；2、使用 toDel 指針指向需要?jiǎng)h除的結(jié)點(diǎn)；3、執(zhí)行操作：toDel = current->next; current->next = toDel->next; delete toDel;

        通過今天對(duì)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的學(xué)習(xí)，總結(jié)如下：1、鏈表中的數(shù)據(jù)元素在物理內(nèi)存中午相鄰關(guān)系；2、鏈表中的結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域；3、頭結(jié)點(diǎn)用于輔助數(shù)據(jù)元素的定位，方便插入和刪除操作；4、插入和刪除操作需要保證鏈表的完整性。

        今天七夕情人節(jié)，祝大家七夕快樂！