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