數組的儲存

【定義】

數組： 由 n（≥1） 個相同類型的數據元素構成的有限序列， 是線性表的推廣。
一旦被定義， 維數和長度就不可再改變， 一般對其只有元素的存取和修改操作。

一維數組

$$Arr[a_0,\dots ,a_{n?1}]$$
計算 ai 的位置： pos(ai) = pos(a0) + i *L (ai 前面有 i 個元素）

二維數組

——可看作元素是一維數組的一維數組。 假設為 n*m 大小。
行優先

列優先

特殊矩陣的壓縮

——多個值相同的元素只分配一個存儲空間， 對零元素不分配空間。

對稱矩陣

aij = aji

若從 a1,1 開始， 則 ai,j 在一維數組中存儲下標

一般存儲下三角矩陣
下三角區域（含主對角線）
第一行：1個元素
第二行：2個元素
第i-1行：i-1個元素
第i行:j-1個元素
故 aij 為第i(i-1)/2+j個元素

i(i-1)/2+j-1, i >= j 下三角區和主對角線
j(j-1)/2+i-1, i < j 上三角區

三角矩陣

——上三角區 or 下三角區全為同一常量 => 會浪費一半的存儲空間。

下三角矩陣元素 aij 和數組下標的關系
n(n+1)/2, i < j 上三角區
i(i-1)/2+j-1, i ≥ j 下三角區和主對角線

上三角矩陣元素 aij 和數組下標的關系

上三角區域 （包含主對角線）
第一行：n個元素
第二行:n-1個元素
第i-1行：n-i+2個元素
第i行:j-i個元素
ai;為第(n+n-i+2)(i-1)/2 + j-i+1=(i-1)(2n-i+2)/2+j-i+1個元素

n(n+1)/2, i > j 下三角區
(i-1)(2n-i+2)/2 + (j-i), i ≤ j 上三角區和主對角線

三對角矩陣

——也稱帶狀矩陣， 對于 ai,j,當|i-j|>1 時， 有 ai,j = 0

除第1行和第i行外，每行都有三個元素，
第i行有j-i+2個元素，
故aij為第(i-2)*3+2+j-i+2=2i+j-2個元素

三對角矩陣的順序存儲

三對角矩陣元素 aij 和數組下標的關系
k = 2i + j -3

稀疏矩陣儲存方式

順序儲存（三元組表示法&偽地址表示法）
鏈式存儲（鄰接表表示法&十字鏈表表示法）