數組的基本概念

數組是一個二元組（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列的頭結點。

行、列頭結點可以共享

增加一個總頭結點，并把所有行、列頭結點鍊起來構成一個循環單鍊表

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