關(guān)鍵詞： 鏈表的定義、鏈表的插入和刪除操作

1. 鏈?zhǔn)酱鎯?chǔ)的定義

為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，數(shù)據(jù)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)其直接后繼的信息。

基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，每個(gè)結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域。

• 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素本身

• 指針域：存儲(chǔ)相鄰結(jié)點(diǎn)的地址

  
  

2. 專(zhuān)業(yè)術(shù)語(yǔ)的統(tǒng)一

順序表：基于順序存儲(chǔ)結(jié)構(gòu)的線性表
鏈表：基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表
1） 單鏈表： 每個(gè)結(jié)點(diǎn)只包含直接后繼的地址信息
2） 循環(huán)鏈表： 單鏈表中的最后一個(gè)結(jié)點(diǎn)的直接后繼為第一個(gè)結(jié)點(diǎn)
3） 雙向鏈表：?jiǎn)捂湵碇械慕Y(jié)點(diǎn)包含直接前驅(qū)和后繼的地址信息

3. 鏈表中的基本概念

• 頭結(jié)點(diǎn)：鏈表中的輔助結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針
• 數(shù)據(jù)結(jié)點(diǎn)：鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，表現(xiàn)形式為：（數(shù)據(jù)元素， 地址）
• 尾結(jié)點(diǎn)： 鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，包含的地址信息為空

4. 單鏈表中的節(jié)點(diǎn)定義

5. 單鏈表中內(nèi)部結(jié)構(gòu)

6. 單鏈表的插入操作

1） 從頭結(jié)點(diǎn)開(kāi)始，通過(guò)current指針定位到目標(biāo)位置
2） 從堆空間申請(qǐng)新的Node結(jié)點(diǎn)
3）執(zhí)行操作：

node->value = e;
node->next = current->next;
current->next = node;

7. 單鏈表的刪除操作

1） 從頭結(jié)點(diǎn)開(kāi)始，通過(guò)current指針定位到目標(biāo)位置
2） 使用toDel指針指向需要?jiǎng)h除的結(jié)點(diǎn)
3）執(zhí)行操作

toDel = current->next;
current->next = toDel->next;
delete toDel;

8. 小結(jié)

• 鏈表中的數(shù)據(jù)元素在物理內(nèi)存中無(wú)相鄰關(guān)系
• 鏈表中的結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域
• 頭結(jié)點(diǎn)用于輔助數(shù)據(jù)元素的定位，方便插入和刪除操作
• 插入和刪除操作需要保證鏈表的完整性

聲明：此文章僅是本人在學(xué)習(xí)狄泰學(xué)院《數(shù)據(jù)結(jié)構(gòu)實(shí)戰(zhàn)開(kāi)發(fā)教程》所做的筆記，文章中包含狄泰軟件資料內(nèi)容，一切版權(quán)歸狄泰軟件所有！
實(shí)驗(yàn)環(huán)境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4