2. 常用數據結構

　　2.1線性表

　　在數據結構中，線性結構常稱為線性表，是最簡單、最常用的一種數據結構，它是由n個相同數據類型的結點組成的有限序列。

　　其特點是：在數據元素的非空有限集合中，

　　u ◆存在唯一的一個被稱做“第一個”的數據元素

　　u ◆存在唯一的一個被稱做“最后一個”的元素數據元素

　　u ◆除第一個之外，集合中的每個數據元素均只有一個前驅

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

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

　　線性表最重要的性質是線性表中結點和相對位置是確定的。

　　線性表的結點也稱為表元，或稱為記錄，要求線性表的結點一定是同一類型的數據。線性表的結點可由若干個成分組成，其中唯一標識表元的成分成為關鍵字，簡稱鍵。

　　線性表是一個相當靈活的數據結構，它的長度可以根據需要增長或縮短。對線性表的基本運算如下：

　　u INITIATE(L)初始化操作

　　u LENGTH(L) 求長度函數

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

　　u PRIOR(L，elm)求前驅函數

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

　　u LOCATE(L，x) 定位函數

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

　　u DELETE(L，i) 刪除操作

　　有多種存儲方式能將線性表存儲在計算機內，其中最常用的是順序存儲和鏈接存儲。根據存儲方式的不同，其上述的運算實現也不一樣。

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

　　順序存儲方式優點：能直接訪問線性表中的任意結點。

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

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

　　順序存儲的缺點：

　　1) 線性表的大小固定，浪費大量的存儲空間，不利于節點的增加和減少;

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

　　◆鏈式存儲

　　線性表鏈接存儲是用鏈表來存儲線性表。

　　單鏈表(線性鏈表)：

　　從鏈表的第一個表元開始，將線性表的結點依次存儲在鏈表的各表元中。鏈表的每個表元除要存儲線性表結點的信息以外，還要有一個成分來存儲其后繼結點的指針。

　　線性鏈表的特點是：每個鏈表都有一個頭指針，整個鏈表的存取必須從頭指針開始，頭指針指向第一個數據元素的位置，最后的節點指針為空。當鏈表為空時，頭指針為空值;鏈表非空時，頭指針指向第一個節點。

　　鏈式存儲的缺點：

　　1) 由于要存儲地址指針，所以浪費空間;

　　2) 直接訪問節點不方便;

　　循環鏈表：

　　循環鏈表是另一種形式的鏈式存儲結構，是單鏈表的變形。它的特點就是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。因此，從表中任意一個結點出發都可以找到表中的其他結點。

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

　　循環鏈表最后一個結點的 link 指針不為 0 (NULL)，而是指向了表的前端。

　　為簡化操作，在循環鏈表中往往加入表頭結點。

　　循環鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。

　　循環鏈表的示例：

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總