軟考軟件設(shè)計(jì)師專題講義九：常用數(shù)據(jù)結(jié)構(gòu)

　　2. 常用數(shù)據(jù)結(jié)構(gòu)

　　2.1線性表

　　在數(shù)據(jù)結(jié)構(gòu)中，線性結(jié)構(gòu)常稱為線性表，是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是由n個相同數(shù)據(jù)類型的結(jié)點(diǎn)組成的有限序列。

　　其特點(diǎn)是：在數(shù)據(jù)元素的非空有限集合中，

　　u ◆存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素

　　u ◆存在唯一的一個被稱做“最后一個”的元素?cái)?shù)據(jù)元素

　　u ◆除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)

　　u ◆除最后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼

　　一個由n個結(jié)點(diǎn)e0，e1…，en-1組成的線性表記為：(e0，e1…，en-1)。線性表的結(jié)點(diǎn)個數(shù)稱為線性表的長度，長度為0的線性表稱為空的線性表，簡稱空表。對于非空線性表，e0是線性表的第一個結(jié)點(diǎn)，en-1是線性表的最后一個結(jié)點(diǎn)。線性表的結(jié)點(diǎn)構(gòu)成了一個序列，對序列中兩個相鄰結(jié)點(diǎn)ei和ei-1，稱前者是后者的前驅(qū)結(jié)點(diǎn)，后者是前者的后繼結(jié)點(diǎn)。

　　線性表最重要的性質(zhì)是線性表中結(jié)點(diǎn)和相對位置是確定的。

　　線性表的結(jié)點(diǎn)也稱為表元，或稱為記錄，要求線性表的結(jié)點(diǎn)一定是同一類型的數(shù)據(jù)。線性表的結(jié)點(diǎn)可由若干個成分組成，其中唯一標(biāo)識表元的成分成為關(guān)鍵字，簡稱鍵。

　　線性表是一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可以根據(jù)需要增長或縮短。對線性表的基本運(yùn)算如下：

　　u INITIATE(L)初始化操作

　　u LENGTH(L) 求長度函數(shù)

　　u GET(L，i) 取元素函數(shù)

　　u PRIOR(L，elm)求前驅(qū)函數(shù)

　　u NEXT(L，elm) 求后繼函數(shù)

　　u LOCATE(L，x) 定位函數(shù)

　　u INSERT(L，i，b)插入操作

　　u DELETE(L，i) 刪除操作

　　有多種存儲方式能將線性表存儲在計(jì)算機(jī)內(nèi)，其中最常用的是順序存儲和鏈接存儲。根據(jù)存儲方式的不同，其上述的運(yùn)算實(shí)現(xiàn)也不一樣。

　　u◆ 順序存儲：是最簡單的存儲方式，其特點(diǎn)是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。通常使用一個足夠大的數(shù)組，從數(shù)組的第一個元素開始，將線性表的結(jié)點(diǎn)依次存儲在數(shù)組中。

　　順序存儲方式優(yōu)點(diǎn)：能直接訪問線性表中的任意結(jié)點(diǎn)。

　　線性表的第i個元素a[i]的存儲位置可以使用以下公式求得： LOC(ai)=LOC(a1)+(i-1)*l

　　式中LOC(a1)是線性表的第一個數(shù)據(jù)元素a1的存儲位置，通常稱做線性表的起始位置或基地址。

　　順序存儲的缺點(diǎn)：

　　1) 線性表的大小固定，浪費(fèi)大量的存儲空間，不利于節(jié)點(diǎn)的增加和減少;

　　2) 執(zhí)行線性表的插入和刪除操作要移動其他元素，不夠方便;

　　◆鏈?zhǔn)酱鎯?/STRONG>