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