為幫助考生備考軟考軟件設(shè)計師考試，希賽小編為大家整理了2022下半年軟件設(shè)計師知識點：線性表，相信對大家備考會有幫助。

線性表（★★★★★）

【考法分析】

本知識點的主要考查形式有：對順序表和鏈表的一些特點描述判斷正誤；或?qū)樞虮砗玩湵淼囊恍┎僮鬟M行對比；對于特殊的線性表隊列和棧的一些概念描述判斷正誤，或二者的出入序列合法性的判斷。

【要點分析】

1、順序表和鏈表的對比：

2、順序表：線性表順序存儲，即用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素，從而使得邏輯上相鄰的兩個元素，在物理上也相鄰。在存儲之前，先根據(jù)線性表的長度分配連續(xù)的物理空間，因此后續(xù)不方便擴展。只需要存儲數(shù)據(jù)元素，不需要存儲元素的邏輯關(guān)系因此存儲密度為1。

3、鏈表：線性表鏈式存儲，即用通過指針鏈接起來的結(jié)點來存儲數(shù)據(jù)元素，存儲各數(shù)據(jù)元素的結(jié)點物理上不要求連續(xù)，因此后期擴展方便。因為物理上不連續(xù)，需要同時存儲各元素之間的邏輯關(guān)系，存儲密度小于1。

4、鏈表的分類：單鏈表、雙鏈表、循環(huán)鏈表。

5、特殊的線性表：隊列（先進先出）、棧（先進后出）。

6、循環(huán)隊列：

隊空條件：head=tail

隊滿條件：(tail+1)%size=head

【備考點撥】

1、掌握順序表和鏈表各自的特點，能夠加以區(qū)分，并判斷相關(guān)描述的正確性；

2、了解順序表和鏈表一些操作的特殊性和對比；

3、 對于隊列和棧，掌握相關(guān)的特點和一些特殊的操作、循環(huán)隊列相關(guān)判斷公式；

4、掌握隊列的入隊和出隊序列的特點；掌握棧的入棧和出棧序列的特點。