1.5 線性鏈表
考點(diǎn)12 線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算
1什么是線性鏈表
(l)線性表順序存儲(chǔ)的缺點(diǎn)
①在一般情況下，要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)，則在插入或刪除過(guò)程中需要移動(dòng)大量的數(shù)據(jù)元素。因此采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入或刪除的運(yùn)算效率很低；
②當(dāng)為一個(gè)線性表分配順序存儲(chǔ)空間后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿(mǎn)，但還需要插入新的元素時(shí)棧會(huì)發(fā)生“上溢”錯(cuò)誤；
③計(jì)算機(jī)空間得不到充分利用，并且不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。
(2)線性表鏈?zhǔn)降幕靖拍?BR> 在定義的鏈表中，若只含有一個(gè)指針域來(lái)存放下一個(gè)元素地址，稱(chēng)這樣的鏈表為單鏈表或線性鏈表。
在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱(chēng)為數(shù)據(jù)域；另一部分用于存放指針，稱(chēng)為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)。如圖1-13所示。
2線性單鏈表的存儲(chǔ)結(jié)構(gòu)
用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后件結(jié)點(diǎn)的地址(或位置)信息，這個(gè)信息稱(chēng)為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，
鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起。由于上述鏈表的每一個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，故將這種鏈表稱(chēng)為單鏈表(Single Linked)。
顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前驅(qū)結(jié)點(diǎn)Next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前驅(qū)，故應(yīng)設(shè)頭指針HEAD指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后件，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即NULL。
3帶鏈的棧與隊(duì)列
(1)棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕?lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱(chēng)為可利用棧
(2)隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，
考點(diǎn)12 線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算
1什么是線性鏈表
(l)線性表順序存儲(chǔ)的缺點(diǎn)
①在一般情況下，要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)，則在插入或刪除過(guò)程中需要移動(dòng)大量的數(shù)據(jù)元素。因此采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入或刪除的運(yùn)算效率很低；
②當(dāng)為一個(gè)線性表分配順序存儲(chǔ)空間后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿(mǎn)，但還需要插入新的元素時(shí)棧會(huì)發(fā)生“上溢”錯(cuò)誤；
③計(jì)算機(jī)空間得不到充分利用，并且不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。
(2)線性表鏈?zhǔn)降幕靖拍?BR> 在定義的鏈表中，若只含有一個(gè)指針域來(lái)存放下一個(gè)元素地址，稱(chēng)這樣的鏈表為單鏈表或線性鏈表。
在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱(chēng)為數(shù)據(jù)域；另一部分用于存放指針，稱(chēng)為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)。如圖1-13所示。
2線性單鏈表的存儲(chǔ)結(jié)構(gòu)
用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后件結(jié)點(diǎn)的地址(或位置)信息，這個(gè)信息稱(chēng)為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，
鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起。由于上述鏈表的每一個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，故將這種鏈表稱(chēng)為單鏈表(Single Linked)。
顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前驅(qū)結(jié)點(diǎn)Next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前驅(qū)，故應(yīng)設(shè)頭指針HEAD指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后件，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即NULL。
3帶鏈的棧與隊(duì)列
(1)棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕?lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱(chēng)為可利用棧
(2)隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，