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

線性表（★★★★★）

【考法分析】

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

【要點(diǎn)分析】

1、順序表和鏈表的對(duì)比：

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

3、鏈表：線性表鏈?zhǔn)酱鎯?chǔ)，即用通過(guò)指針鏈接起來(lái)的結(jié)點(diǎn)來(lái)存儲(chǔ)數(shù)據(jù)元素，存儲(chǔ)各數(shù)據(jù)元素的結(jié)點(diǎn)物理上不要求連續(xù)，因此后期擴(kuò)展方便。因?yàn)槲锢砩喜贿B續(xù)，需要同時(shí)存儲(chǔ)各元素之間的邏輯關(guān)系，存儲(chǔ)密度小于1。

4、鏈表的分類：?jiǎn)捂湵?、雙鏈表、循環(huán)鏈表。

5、特殊的線性表：隊(duì)列（先進(jìn)先出）、棧（先進(jìn)后出）。

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

隊(duì)空條件：head=tail

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

【備考點(diǎn)撥】

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

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

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

4、掌握隊(duì)列的入隊(duì)和出隊(duì)序列的特點(diǎn)；掌握棧的入棧和出棧序列的特點(diǎn)。