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

一、數組

1、數組的定義

數組是由類型相同的數據元素構成的有序集合,每個元素稱為數組元素，每個元素受 n(n>=1) 個線性關系的約束，每個元素在 n 個線性關系中的序號i1, i2, …，in 稱為該元素的下標，可以通過下標訪問該數據元素。

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

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

1.1、一維數組

一維數組是指下標的個數只有一個的數組， 有時稱為向量， 是最基本的數據類型， 在Java 中需要事先聲明，程序才能夠在編譯過程中預留內存空間。

聲明的格式一般為：

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

1

例如：

float numbera=new int[5];

1

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

1.2、多維數組

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

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

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

1

例如：

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

1

表示聲明了名稱為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中的元素滿足以下條件:

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

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

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

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

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

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

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

1.2、稀疏矩陣

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

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

例如稀疏矩陣：

采用三元表示法：

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，則表示該節點為原子結點即無孩子結點。

上一篇：重學數據結構（三、隊列）

下一篇：重學數據結構（五、串）

參考：

【1】：鄧俊輝 編著. 《數據結構與算法》

【2】：王世民 等編著 . 《數據結構與算法分析》

【3】： Michael T. Goodrich 等編著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》

【4】：嚴蔚敏、吳偉民 編著 . 《數據結構》

【5】：程杰 編著 . 《大話數據結構》

【6】：Java數據結構–數組、矩陣、廣義表

【7】：矩陣（稀疏矩陣）壓縮存儲（3種方式）

【8】：什么是廣義表、廣義表及定義詳解

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。