重學資料結構（四、數組和廣義表）

一、數組

1、數組的定義

數組是由類型相同的資料元素構成的有序集合,每個元素稱為數組元素，每個元素受 n(n>=1) 個線性關系的限制，每個元素在 n 個線性關系中的序号i1, i2, …，in 稱為該元素的下标，可以通過下标通路該資料元素。

數組分為一維數組和多元數組。

數組一旦被定義， 它的維數和維界就不再改變。 是以， 除了結構的初始化和銷毀之外， 數組隻有存取元素和修改元素值的操作。

1.1、一維數組

一維數組是指下标的個數隻有一個的數組， 有時稱為向量， 是最基本的資料類型， 在Java 中需要事先聲明，程式才能夠在編譯過程中預留記憶體空間。

聲明的格式一般為：

<資料類型><變量名稱>[]= new<資料類型>[<數組大小>];      

例如：

float numbera=new int[5];      

聲明一個長度為 5 的浮點資料類型的一維數組，數組名為numbera。

1.2、多元數組

多元數組是指下标的個數有兩個或兩個以上， 我們比較常用的是二維數組。

二維數組的聲明同一維數組。 格式為：

<資料類型> <數組名稱>[][]=new 〈資料類型>[sizel][size2];      

int data[][]=newim [5][4];      

表示聲明了名稱為data的整形二維數組。

2、數組存儲

2.1、一維數組的存儲

一維數組A[n] = {a0, a1…,an-1}的資料存儲按照順序存儲， 邏輯位址和實體位址都是連續的。

一維數組任意資料元素ai的存儲單元位址：Loc(ai) = Loc(a0) + i * k (0 ≤ i < n)，其中k為單個元素所占空間。

2.2、多元數組的存儲

由于記憶體是一維的，而數組是多元結構，可以認為二維數組是一個每個資料元素是一維數組的一維數組；三維數組是每個資料元素是二維數組的一維數組；四維數組是個每個資料元素是三維數組的一維數組，以此類推。

以二維數組的順序存儲為例說明， 對于一個m×n的二維數組，可以看成一個矩陣：

也可以看成一個行向量的一維數組：

二維數組在順序存儲時一般有兩種。

• 行優先順序： 存儲時先按行從小到大的順序存儲， 在每一行中按列号從小到大存儲。

• 列優先順序： 存儲時先按列從小到大的順序存儲， 在每一列中按行号從小到大存儲。

  

以上的兩種存儲順序中， 第一個被存放的元素總是第一行第一列的資料元素， 是以該元素的位址是我們的己知條件。

行優先順序存儲二維數組的任一資料元素 a[i,j] 的存儲單元位址：Loc(a[i，j]) = Loc(a[0, 0]) + (i * n + j) *k （0 ≤ i < m，0 ≤ j < n），其中k為單個元素所占空間。

列優先存儲的二維數組a[i,j]的存儲單元位址：Loc(a[i,j]) = Loc(a[0,0]) + (j * m + i)*k（0 ≤ i < m，0 ≤ j < n），其中k為單個元素所占空間。

二、矩陣的存儲

1、矩陣的壓縮存儲

所謂矩陣的壓縮存儲， 也就是在存儲數組時， 盡量減少存儲空間， 是以在矩陣存儲中， 如果有規律可尋， 隻要存儲其中一部分， 而另一部分的存儲位址可以通過相應的算法将它計算出來， 進而占有比較少的存儲空間達到存儲整個矩陣的目的。

矩陣的壓縮存儲僅是針對特殊矩陣的， 而對于沒有規律可循的二維數組則不能夠使用矩陣壓縮存儲。

二維數組(矩陣)的壓縮存儲一般有 3 種， 它們分别是對稱矩陣、 稀疏矩陣和三角矩陣。

1.1、對稱矩陣

若n階矩陣A中的元素滿足以下條件:

aij=aji（i>=1;j>=1）

則成為對稱矩陣。如下例：

結合資料結構壓縮存儲的思想，我們可以使用一維數組存儲對稱矩陣。由于矩陣中沿對角線兩側的資料相等，是以數組中隻需存儲對角線一側（包含對角線）的資料即可。

對稱矩陣的實作過程是，若存儲下三角中的元素，隻需将各元素所在的行标 i 和列标 j 代入下面的公式：

存儲上三角的元素要将各元素的行标 i 和列标 j 代入另一個公式：

最終求得的 k 值即為該元素存儲到數組中的位置（矩陣中元素的行标和列标都從 1 開始）。

例如，在數組 skr[6] 中存儲上文中的對稱矩陣，則矩陣的壓縮存儲狀态如圖 所示（存儲上三角和下三角的結果相同）：

注意，以上兩個公式既是用來存儲矩陣中元素的，也用來從數組中提取矩陣相應位置的元素。例如，如果想從上圖中的數組提取矩陣中位于 (3,1) 處的元素，由于該元素位于下三角，需用下三角公式擷取元素在數組中的位置，即：

1.2、稀疏矩陣

稀疏矩陣是矩陣中的一種特殊情況，其非零元素的個數遠小于零元素的個數。

稀疏矩陣壓縮存儲主要采用三元表示法來實作。其存儲規則是每一個非零元素占有一行， 每行中包含非零元素所在的行号、 列号、 非零元素的數值。

(row col value)

例如稀疏矩陣：

采用三元表示法：

1.3、三角矩陣

以對角線劃分，三角矩陣有上三角和下三角兩種。

主對角線下的資料元素全部相同的矩陣為上三角矩陣，主對角線上元素全部相同的矩陣為下三角矩陣。

對于這類特殊的矩陣，壓縮存儲的方式是：重複元素C可共用一個存儲空間，其餘的元素可以采用對稱矩陣的壓縮存儲方式存儲。

這麼一來，對稱矩陣可以看做一種特殊的三角矩陣。

三、廣義表

1、廣義表的定義

廣義表是線性表的推廣， 具體定義為n(n>=0)個元素的有限序列。

一般記作：LS=(a1,a2,a3, … ai, …, an)

廣義表的資料元素可以分為兩種，一種不可再分（原子），一種可再分（子表）。

以下是一些常見的廣義表定義：

• A = ()：A 表示一個廣義表，隻不過表是空的。
• B = (e)：廣義表 B 中隻有一個原子 e。
• C = (a,(b,c,d)) ：廣義表 C 中有兩個元素，原子 a 和子表 (b,c,d)。
• D = (A,B,C)：廣義表 D 中存有 3 個子表，分别是A、B和C。這種表示方式等同于 D = ((),(e),(b,c,d)) 。
• E = (a,E)：廣義表 E 中有兩個元素，原子 a 和它本身。這是一個遞歸廣義表，等同于：E = (a,(a,(a,…)))。

從上面的例子可以歸納出一些結論：

• 廣義表的元素可以是子表， 而子表的元素還可以是子子表……由此， 廣義表是一個多層次的結構。
• 廣義表可為其他廣義表共享。
• 廣義表可以是一個遞歸表，即廣義表也可以是其本身的一個子表。

當廣義表不是空表時，稱第一個資料（原子或子表）為"表頭"，剩下的資料構成的新廣義表為"表尾"。

2、廣義表的存儲

由于廣義表中的資料元素具有不同的結構，通常是一種遞歸的資料結構，很難為每個廣義表配置設定固定大小的存儲空間，一般用鍊式存儲結構表示，有頭尾表示法和孩子兄弟表示法兩種存儲方式。

2.1、頭尾表示法

任意非空的廣義表，可分解為表頭和表尾，反之，一對确定的表頭和表尾可唯一确定一個廣義表。

在頭尾表示法中需要有兩種結構的結點：一種是表結點，可以表示字表；一種是原子結點，用來表示原子。

在表結點中有三個域組成：标志域、指向表頭的指針域和指向表尾的指針域；

而原子結點需要兩個域：标志域和值域。标志域是用來區分這兩種結點的。

2.3、孩子兄弟表示法

在孩子兄弟表示法中，原子結點和表結點用相似的兩種結點來表示。

其中表結點有孩子結點，cp和bp分别指向第一個孩子換一個兄弟的指針域；

原子結點是無孩子結點，data和bp分别是指域和指向兄弟的指針域。

tag是标志域，用來區分這兩類結點，如tag為1，則表示該結點為表結點即有孩子的結點；tag為0，則表示該節點為原子結點即無孩子結點。

​