七、线性表的链式存储结构
1、問(wèn)題引入
開(kāi)發(fā)數(shù)組類(lèi)模板的原因在于：在創(chuàng)建基于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表時(shí)，發(fā)現(xiàn)這樣的線(xiàn)性表可能被誤用，因?yàn)橹剌d了數(shù)組訪(fǎng)問(wèn)操作符，使用時(shí)跟數(shù)組類(lèi)似，但是線(xiàn)性表和數(shù)組有很大的區(qū)別，所以激發(fā)了新的需求：開(kāi)發(fā)數(shù)組類(lèi)替換C++原生數(shù)組類(lèi)，因?yàn)樵鷶?shù)組類(lèi)也存在著很大缺陷，使用不方便。
基于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表的另一個(gè)缺點(diǎn)：插入或刪除元素時(shí)，涉及到大量數(shù)據(jù)元素的移動(dòng)，對(duì)于效率的影響非常大
一個(gè)新的需求：在插入或刪除元素時(shí)不需要大量移動(dòng)數(shù)據(jù)元素的一種數(shù)據(jù)結(jié)構(gòu)，即基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表
2、鏈?zhǔn)浇Y(jié)構(gòu)的定義
為了表示每個(gè)數(shù)據(jù)元素于其直接后繼元素之間的邏輯關(guān)系；數(shù)據(jù)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)其直接后繼的信息。
\(a_i\)和\(a_{i+1}\)是線(xiàn)性表中的兩個(gè)相鄰數(shù)據(jù)元素，在物理內(nèi)存中無(wú)相鄰關(guān)系。
一個(gè)數(shù)據(jù)元素包含了兩部分：\(a_i\)是數(shù)據(jù)元素本身的數(shù)據(jù)信息，還有一個(gè)地址信息，地址是第\(i\)個(gè)元素的直接后繼，即第\(i+1\)個(gè)的元素在內(nèi)存中的地址信息。換句話(huà)說(shuō)就是如果找到了第\(i\)個(gè)元素，不僅可以得到第\(i\)個(gè)元素的本身的值之外，還可以得到第\(i+1\)個(gè)元素在內(nèi)存中的位置
3、鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)
基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表中，每個(gè)結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域
- 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素本身
- 指針域：存儲(chǔ)相鄰結(jié)點(diǎn)的地址
兩種線(xiàn)性表名稱(chēng)統(tǒng)一：
- 順序表：基于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表
- 鏈表：基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表
- 單鏈表：每個(gè)結(jié)點(diǎn)只包含直接后繼的地址信息
- 循環(huán)鏈表：單鏈表的最后一個(gè)結(jié)點(diǎn)的直接后繼為第一個(gè)結(jié)點(diǎn)
- 雙向鏈表：單鏈表中的結(jié)點(diǎn)包含直接前驅(qū)和后繼的地址信息
- 雙向循環(huán)鏈表......
4、鏈表中的基本概念
- 頭結(jié)點(diǎn)：鏈表中的輔助結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針；不包含任何數(shù)據(jù)信息，是為了簡(jiǎn)化代碼進(jìn)行輔助
- 數(shù)據(jù)結(jié)點(diǎn)：鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，表現(xiàn)形式為：(數(shù)據(jù)元素，地址)
- 尾結(jié)點(diǎn)：鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)。單獨(dú)放出的原因：尾結(jié)點(diǎn)包含的地址信息直接決定了鏈表的性質(zhì)，地址信息為空，就是單鏈表；地址為第0個(gè)元素的地址信息，就是循環(huán)鏈表；地址信息為隨機(jī)值，就是一個(gè)非法鏈表
5、單鏈表
5.1 單鏈表中的結(jié)點(diǎn)定義
// 用struct定義類(lèi)，默認(rèn)屬性是public // T是泛指類(lèi)型，鏈表可以存儲(chǔ)各種類(lèi)型的數(shù)據(jù) struct Node : public Object {T value;Node* next; // 指向后繼結(jié)點(diǎn)的指針 }5.2 單鏈表的內(nèi)部結(jié)構(gòu)
頭結(jié)點(diǎn)在單鏈表中的意義是：輔助數(shù)據(jù)元素的定位，方便插入和刪除操作，因此，頭結(jié)點(diǎn)不存儲(chǔ)實(shí)際的數(shù)據(jù)元素。
5.3 在目標(biāo)位置處插入數(shù)據(jù)元素
從頭結(jié)點(diǎn)開(kāi)始，通過(guò)current指針定位到目標(biāo)位置
從堆空間申請(qǐng)新的Node結(jié)點(diǎn)
執(zhí)行操作
node->value = e; node->next = current->next; current->next - node;5.4 在目標(biāo)位置刪除數(shù)據(jù)元素
從頭結(jié)點(diǎn)開(kāi)始，通過(guò)previous指針定位到目標(biāo)位置的前一個(gè)地址
使用toDel指針指向需要?jiǎng)h除的結(jié)點(diǎn)
執(zhí)行操作：
toDel = previous->next; previous->next = toDel->next; delete toDel;6、小結(jié)
鏈表中的數(shù)據(jù)元素在物理內(nèi)存中無(wú)相鄰關(guān)系
鏈表中的結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域
頭結(jié)點(diǎn)用于輔助數(shù)據(jù)元素定位，方便插入和刪除操作
插入和刪除操作需要保證鏈表的完整性
轉(zhuǎn)載于:https://www.cnblogs.com/chenke1731/p/9495573.html
總結(jié)
以上是生活随笔為你收集整理的七、线性表的链式存储结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
