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

　　2.1線性表

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

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

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

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

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

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

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

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

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

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

　　u INITIATE(L)初始化操作

　　u LENGTH(L) 求長(zhǎng)度函數(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) 刪除操作

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

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

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

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

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

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

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

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

　　◆鏈?zhǔn)酱鎯?chǔ)

　　線性表鏈接存儲(chǔ)是用鏈表來存儲(chǔ)線性表。

　　單鏈表(線性鏈表)：

　　從鏈表的第一個(gè)表元開始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在鏈表的各表元中。鏈表的每個(gè)表元除要存儲(chǔ)線性表結(jié)點(diǎn)的信息以外，還要有一個(gè)成分來存儲(chǔ)其后繼結(jié)點(diǎn)的指針。

　　線性鏈表的特點(diǎn)是：每個(gè)鏈表都有一個(gè)頭指針，整個(gè)鏈表的存取必須從頭指針開始，頭指針指向第一個(gè)數(shù)據(jù)元素的位置，最后的節(jié)點(diǎn)指針為空。當(dāng)鏈表為空時(shí)，頭指針為空值;鏈表非空時(shí)，頭指針指向第一個(gè)節(jié)點(diǎn)。

　　鏈?zhǔn)酱鎯?chǔ)的缺點(diǎn)：

　　1) 由于要存儲(chǔ)地址指針，所以浪費(fèi)空間;

　　2) 直接訪問節(jié)點(diǎn)不方便;

　　循環(huán)鏈表：

　　循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是單鏈表的變形。它的特點(diǎn)就是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。因此，從表中任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到表中的其他結(jié)點(diǎn)。

　　循環(huán)鏈表和單向鏈表基本一致，差別僅在于算法中循環(huán)的條件不是結(jié)點(diǎn)的指針是否為空，而是他們的指針是否等于頭指針，

　　循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的 link 指針不為 0 (NULL)，而是指向了表的前端。

　　為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。

　　循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。

　　循環(huán)鏈表的示例：

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總