-
数组：数组是由n(n>=1)个相同类型的数据元素构成的有限序列
- 数组元素：数据元素
- 下标：每个元素在n个线性关系中的序号
- 数组维界：下标取值范围
-
数组与线性表的关系：数组是线性表的推广，一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推
-
数组一旦被定义，其维数和维界就不再改变，除结构的初始化和销毁外，数组只有存取元素和修改元素的操作
- 逻辑意义上的数组可采用计算机语言的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间，每个元素大小相等
- 一维数组存储结构关系式：
L
o
c
(
a
i
)
=
L
o
c
(
a
0
)
+
L
∗
i
(
0
<
=
i
<
n
)
Loc(a_i)=Loc(a_0)+L*i(0<=i
- 二维数组存储结构关系式
- 按行优先：
L
o
c
(
a
i
)
=
L
o
c
(
a
0
)
+
(
i
∗
c
o
l
s
+
j
)
∗
L
(
0
<
=
i
<
n
)
Loc(a_i)=Loc(a_0)+(i*cols+j)*L(0<=i
- 按列优先： L o c ( a i ) = L o c ( a 0 ) + ( j ∗ r o w s + i ) ∗ L ( 0 < = i < n ) Loc(a_i)=Loc(a_0)+(j*rows+i)*L(0<=i
- 按列优先： L o c ( a i ) = L o c ( a 0 ) + ( j ∗ r o w s + i ) ∗ L ( 0 < = i < n ) Loc(a_i)=Loc(a_0)+(j*rows+i)*L(0<=i
- 二维数组存储结构关系式
-
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间
-
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定规律性；如：对称矩阵，上（下）三角矩阵，对角矩阵
-
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把呈现规律性分配的，值相同的矩阵元素压缩到存储到一个存储空间中
-
对称矩阵：对于一个n阶方阵A[1…n][1…n]中的任意一个元素 a i j a_{ij} aij，都有 a i j = a j i ( 1 < = i , j < = n ) a_{ij}=a_{ji}(1<=i, j<=n) aij=aji(1<=i,j<=n)，则称其为对称矩阵；对称矩阵可分为三个区域：主对角线区域(i==j)，上三角区域(i
- 只存储下三角区域的元素，元素与下标之间的对应关系为
- i>=j: i(i-1)/2+(j-1)
- i
- 只存储下三角区域的元素，元素与下标之间的对应关系为
-
三角矩阵：上（下）三角区域存储非零矩阵元素，下（上）三角区域所有元素均为同一常量
- 可将下三角矩阵存储在B[n(n+1)/2+1]矩阵中
- i>=j: i(i-1)/2+j-1
- i
- 可将上三角区域存储在B[n(n+1)/2+1]矩阵中
- i<=j: (i-1)(2n-i+2)/2+(j-i)
- i>j: n(n+1)/2
- 可将下三角矩阵存储在B[n(n+1)/2+1]矩阵中
-
三对角矩阵：对n阶方阵中的任意元素，当|i-j|>1时值为0，即非零元素集中在以主对角线为中心的3条2对角线区域。
-
元素 a i j a_{ij} aij在一维数组中的下标为k=3(i-1)-1+j-(i-2)-1=2i+j-3
-
若已知元素存放在第k个位置，则可得 i = ⌊ ( k + 1 ) / 3 ⌋ + 1 i=left lfloor (k+1)/3 right rfloor +1 i=⌊(k+1)/3⌋+1
3 ( i − 1 ) − 1 < = k < 3 i − 1 i < = ( k + 1 ) / 3 + 1 , j = k − 2 i + 3 3(i-1)-1<=k<3i-1 \ i<=(k+1)/3+1, j=k-2i+3 3(i−1)−1<=k<3i−1i<=(k+1)/3+1,j=k−2i+3
-
-
稀疏矩阵：矩阵中非零元素的个数t相对于矩阵元素的个数s非常少，s>>t，如对于100*100矩阵，非零元素个数小于100
- 稀疏矩阵中的非零元素的分布没有规律，因此一般用一个三元组来记录非零元素的行，列和值：(行，列，值)
- 三元组可以采用数组存储(顺序存储三元组)，也可以采用十字链表法存储
