陣列的基本概念

陣列是一個二元組（idx，value）的集合，對每個idx，都有一個value值與之對應。idx稱為下標，可以由一個整數、兩個整數或多個整數構成，下標含有d（d≥1）個整數稱為維數是d。

陣列按維數分為一維、二維和多維陣列。

一維陣列A是n（n>1）個相同型別元素a0，a1，…，an-1構成的有限序列，其邏輯表示為A=（a0，a1，…，an-1），其中，A是陣列名，ai（0≤i≤n-1）是陣列A中序號為i的元素。

一個二維陣列可以看作是每個資料元素都是相同型別的一維陣列的一維陣列。

以此類推

陣列具有以下特點

（1）陣列中各元素都具有統一的資料型別。

（2）d（d≥1）維陣列中的非邊界元素具有d個前驅元素和d個後繼元素。

（3）陣列維數確定後，資料元素個數和元素之間的關係不再發生改變，特別適合於順序儲存。

（4）每個有意義的下標都存在一個與其相對應的陣列元素值。

d維陣列抽象資料型別

一維陣列

一維陣列的所有元素依邏輯次序存放在一片連續的記憶體儲存單元中。

其起始地址為第一個元素a0的地址即LOC(a0)。

假設每個資料元素佔用k個儲存單元。

則任一資料元素ai的儲存地址LOC(ai)就可由以下公式求出

d維陣列

以m行n列的二維陣列Am×n=(ai，j)為例討論（二維陣列也稱為矩陣）。

按行優先儲存

假設每個元素佔k個儲存單元，LOC(a0，0)表示a0，0元素的儲存地址。對於元素ai，j：

ai,j前面有0～i-1共i行，每行n個元素，共有i×n個元素。

在第i行中前面有a[i,0..j-1]，共j個元素。

合起來，ai,j前面有i×n+j個元素。

按列優先儲存

假設每個元素佔k個儲存單元，LOC(a0，0)表示a0，0元素的儲存地址。對於元素ai，j：

ai,j前面有0～j-1共j列，每列m個元素，共有j×m個元素。

在第j列中前面有a[0..i-1,j]，共i個元素。

合起來，ai,j前面有j×m+i個元素。則：

例子：設有二維陣列a[1..50，1..80]，其a[1][1]元素的地址為2000，每個元素佔2個儲存單元，若按行優先儲存，則元素a[45][68]的儲存地址為多少?若按列優先儲存，則元素a[45][68]的儲存地址為多少？

按行優先儲存

元素a[45][68]前面有1～44行，每行80個元素，計44×80個元素。

在第45行中，元素a[45][68]前面有a[45][1..67]計67個元素，這樣元素a[45][68]前面儲存的元素個數=44×80+67。

LOC(a[45][68])=2000+(44×80+67)×2=9174。

例子：設有二維陣列a[1..50，1..80]，其a[1][1]元素的地址為2000，每個元素佔2個儲存單元，若按行優先儲存，則元素a[45][68]的儲存地址為多少?若按列優先儲存，則元素a[45][68]的儲存地址為多少？

按列優先儲存

元素a[45][68]前面有1～67列，每列50個元素，計67×50個元素。

在第68列中，元素a[45][68]前面有a[1..44][68]計44個元素，這樣元素a[45][68]前面儲存的元素個數=67×50+44。

LOC(a[45][68])=2000+(67×50+44)×2=8788。

特殊矩陣的壓縮儲存

對稱矩陣的壓縮儲存

三角矩陣的壓縮儲存

對角矩陣的壓縮儲存

稀疏矩陣

一個階數較大的矩陣中的非零元素個數s相對於矩陣元素的總個數t十分小時，即s<<t時，稱該矩陣為稀疏矩陣。

例如一個100×100的矩陣，若其中只有100個非零元素，就可稱其為稀疏矩陣。

稀疏矩陣和特殊矩陣的不同點：

特殊矩陣的特殊元素（值相同元素、常量元素）分佈有規律。

稀疏矩陣的特殊元素（非0元素）分佈沒有規律。

稀疏矩陣的三元組表示

三元組表示中每個元素的類定義如下：

設計稀疏矩陣三元組儲存結構類TupClass如下：

TupClass類中包含如下基本運算方法：

其中，data列表用於存放稀疏矩陣中所有非零元素，通常按行優先順序排列。這種有序結構可簡化大多數稀疏矩陣運算演算法。

稀疏矩陣的十字連結串列表示

每個非零元素對應一個結點

每行的所有結點鏈起來構成一個帶行頭結點的迴圈單鏈表。以h[i]（0≤i≤m-1）作為第i行的頭結點。

每列的所有結點鏈起來構成一個帶列頭結點的迴圈單鏈表。 以h[i]（0≤i≤m-1）作為第i列的頭結點。

行、列頭結點可以共享

增加一個總頭結點，並把所有行、列頭結點鏈起來構成一個迴圈單鏈表

為了統一，設計結點型別如下：