文档介绍：数组的顺序表示和实现
注意:数组可以是多维的,但存储数据元素的内存单元地址
是一维的,因此,在存储数组结构之前,需要解决将
多维关系映射到一维关系的问题。
两种顺序存储方式
以行序为主序(低下标优先)
以列序为主序(高下标优先)
以行序为主序存放:
am-1, n-1
……..
am-1, 1
am-1, 0
……….
a1, n-1
……..
a11
a10
a0, n-1
…….
a01
a00
0
1
n -1
m*n -1
n
二维数组中任一元素 ai,j 的存储位置
LOC(i, j) = LOC(0, 0) + (b2×i+j )×L
某个元素的地址就是它前面所有行
所占的单元加上它所在行前面所有列元
素所占的单元数之和。
基地址或基址
二维数组的映象函数
a00 a01 …….. a0, n-1
a10 a11 …….. a1, n-1
am-1, 0 am-1, 1 …….. am-1, n-1
………………….
按列序为主序存放
0
1
m -1
m*n -1
m
am-1, n-1
……..
a1, n-1
a0, n-1
……….
am-1, 1
……..
a11
a01
am-1, 0
…….
a10
a00
a00 a01 …….. a0, n-1
a10 a11 …….. a1, n-1
am-1, 0 am-1, 1 …….. am-1, n-1
………………….
二维数组中任一元素 ai,j 的存储位置
LOC(i, j) = LOC(0, 0) + (b1×j+i )×L
某个元素的地址就是它前面所有列
所占的单元加上它所在列前面所有行元
素所占的单元数之和。
例 1:一个二维数组 A,行下标的范围是 1 到 6,列下标
的范围是 0 到 7,每个数组元素用相邻的 6 个字节
存储,存储器按字节编址。那么,这个数组的体积
是个字节。
答: Volume = m×n×L
= (6 – 1 + 1) ×(7 – 0 + 1) ×6
= 48×6 = 288
288
例 2:〖某校计算机系考研题〗
设数组 A[0…59, 0…69] 的基地址为 2048,每个元素占 2 个
存储单元,若以列序为主序顺序存储,则元素 A[31, 57] 的存储
地址为。
解:LOC(i, j) = LOC(31, 57)
= LOC(0, 0) + (b1×j+i )×L
= 2048 + (60×57+31 )×2
= 8950
8950
a00 a01 … a0, 69
a10 a11 … a1, 69
a59, 0 a59, 1 … a59, 69
……… a31, 57 ……
……………
……………
则 aij 和 sa[k] 存在着一一对应关系:
aij 前的 i -1 行有 1 + 2 +…+ (i -1)
= i(i -1)/2 个元素,在第 i 行上有
j 个元素。
因为aij = aji,所以只要交换上述
对应关系式中的 i 和 j 即可。
以行序为主序存储下三角:
对称矩阵的存储结构
矩阵的压缩存储
特殊矩阵
2、三角矩阵
以主对角线划分,三角矩阵有上(下)三角两种。上(下)
三角矩阵的下(上)三角(不含主对角线)中的元素均为常数。
在大多数情况下,三角矩阵常数为零。
上三角矩阵
下三角矩阵
三角矩阵的存储:除了存储主对角线及上(下)三角中的元
素外,再加一个存储常数 c 的空间。
3、对角矩阵
在对角矩阵中,所有的非零元素集中在以主对角线为中心的
带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角
线上的元素之外,其余元素皆为零。
对角矩阵可按行优先顺序或对角线的顺序,将其压缩存储到
一维数组中,且也能找到每个非零元素和向量下标的对应关系。
稀疏矩阵
压缩存储原则:存各非零元的值、行列位置和矩阵的行列数。
M 由{(1,2,12), (1,3,9), (3,1,-3),
(3,6,14), (4,3,24), (5,2,18),
(6,1,15), (6,4,-7) }
和矩阵维数(6, 7) 唯一确定。
三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。
i j tu
0
1
2
3
4
5
6
7
8
稀疏矩阵的压缩存储方法——顺序存储结构
1、三元组顺序表
6
7
8
1
2
12
1
3
9
3
1
-3
3
6
14
4
3
24
5
2
18
6