數據結構基礎-數組

數組

數組是定長線性表在維數上的擴展，即線性表中的元素又是一個線性表。

n維數組是一種”同構“的數據結構，也就是指其每個數據元素類型相同、結構相同。

數組其實就是同一類型的多個變量的集合。

數組元素的特點：

• 數據元素數目固定，一旦定義了一個數組結構，就不再有元素個數的增減變化。
• 數據元素具有相同的類型。
• 數據元素的下標關係具有上下界的約束且下標有序。

數組的基本運算：

• 給定一組下標，存取相應的數據元素。
• 給定一組下標，修改相應的數據元素中某個數據項的值。

如在JAVA中，數組的操作如下圖所示:

JAVA數組操作

數組的順序存儲：

數組一般不做插入和刪除運算，一旦定義了數組，則結構中的數據元素個數和元素之間的關係就不再發生變動，因此數據適合於採用順序存儲結構。

廣義表

廣義表是由0個或多個單元素或子表組成的有限序列，是線性表的推廣。

廣義表與線性表的區別：

線性表的元素都是結構上不可分的單元素，而廣義表可以是單元素，也可以是有結構的表。

廣義表一般記為：LS = (a1,a2,...,an),n>=1。其中a1...an等元素既可以是單個元素，也可以是廣義表。分別稱為原子和子表。

廣義表通常用圓括號括起來，用逗號分隔其中的元素,書寫時用大寫字母表示廣義表，用小寫字母表示原子。

廣義表的長度與深度：

長度：指廣義表中元素的個數。

深度：指廣義表展開後，所含的括號的最大層數。

如：

N=(),　N是一個空表，其長度為0。

L=(a，b)，L是長度為2的廣義表，它的兩個元素都是原子,深度為1

M=(x,L)=(x，(a，b)),M是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L，深度為2。

• 基本操作

廣義表的操作與線性表類似，但由於廣義表的結構比較複雜，運算的實現也不如線性表簡單，下面列出兩個比較特殊的運算：

取表頭：非空廣義表的第一個元素稱為表頭，它可以是一個單元素，也可以是一個子表。

取表尾：非空廣義表除表頭元素之外，由其餘元素構成的表稱為表尾。非空廣義表的表尾必定是一個表。

• 存儲結構：

廣義表中的元素本身又可以具有結構，它是一種帶有層次的非線性結構，因此難以用順序存儲結構表示，通常採用鏈式存儲結構。

非空廣義表可以分解為表頭和表尾兩部分，反之，一對確定的表頭和表尾可唯一確定一個廣義表。

廣義表的元素有兩種類型，因此鏈表結點結構也有兩種，如下圖所示，

廣義錶鏈表結點結構

tag 標記位：區分是原子還是子表，通常原子的 tag 值為 0，子表的 tag 值為 1。

hp 指針：用於連接本子表中存儲的原子或子表。

tp 指針：用於連接廣義表中下一個原子或子表。

對於廣義表C=(a,(b,c,d))，鏈式存儲結構如下圖所示：

廣義表(a,(b,c,d))存儲結構示意圖