在程序设计语言中大都提供了数组作为构造数据类型，本章重点讨论数组以及特殊矩阵的
存储
与
寻址
。
目录
数组
数组的定义
数组是由一组
类型相同
的数据元素构成的
有序
集合
，
每个数据元素称为一个数组元素（简称为元素），每个元素受
n
(
n
≥1)
个
线性关系
的约束，
每个元素在
n
个线性关系中的序号
i
1
、
i
2
、…、
i
n
称为该元素的下标，并称该数组为
n
维数组。
如上图表示的二维数组中，
元素
a
22
受两个线性关系的约束，在行上有一个行前驱
a
21
和一个行后继
a
23
，在列上有一个列前驱
a
12
和和一个列后继
a
32
。
数组的特点
-
元素本身可以具有某种结构，属于同一数据类型；
-
数组是一个具有固定格式和数量的数据集合。
数组的基本操作
-
读操作：给定一组下标，读出对应的数组元素；
-
写操作：给定一组下标，存储或修改与其相对应的数组元素。
读操作和写操作本质上只对应一种操作——
寻址
在数组上一般不能做插入和删除元素的操作，
所以不用预留空间，适合采用顺序存储。
数组的存储结构与寻址
一维数组
设一维数组的下标的范围为闭区间［
l
，
h
］，
每个数组元素占用
c
个存储单元，则其任一元素
a
i
的存储地址可由下式确定：
Loc(
a
i
)＝Loc(
a
l
)＋(
i
－
l
)×
c
二维数组
常用的映射方法有两种：
-
按
行
优先：
先行后列
，先存储行号较小的元素，行号相同者先存储列号较小的元素。
-
按
列
优先：
先列后行
，先存储列号较小的元素，列号相同者先存储行号较小的元素。
按行优先存储的寻址
a
ij
前面的元素个数
=阴影部分的面积
=整行数×每行元素个数+本行中
a
ij
前面的元素个数
=(
i
–
l
1
)×(
h
2
–
l
2
＋1)＋(
j
–
l
2
)
矩阵的压缩存储
特殊矩阵和稀疏矩阵
特殊矩阵：
矩阵中很多值相同的元素并且它们的分布有一定的规律：对称矩阵、三角矩阵、对角矩阵
…
稀疏矩阵：
矩阵中有很多零元素。
压缩存储的基本思想
⑴ 为多个值
相同
的元素只分配
一个
存储空间；
⑵ 对
零
元素
不分配
存储空间。
对称矩阵
压缩存储：
存储下三角部分的元素。由于下三角中共有
n
×(
n
+1)/2
个元素，可将这些元素按行存储到一个数组
SA[
n
×(
n
+1)/2]
中。
a
ij
在一维数组中的序号
=阴影部分的面积
=[(i-1)(i-1)+(i-1)]/2 + j =
i
×(
i
-1)/2+
j
∵
一维数组下标从0开始
∴
a
ij
在一维数组中的下标
k
=
i
×(
i
-1)/2+
j
-1
对于下三角中的元素
a
ij
（
i
≥
j
）
，在数组
SA
中的下标
k
与
i
、
j
的关系为：
k
＝
i
×(
i
-1)/2＋
j
-1
。
上三角中的元素
a
ij
（
i
＜
j
），
因为
a
ij
＝
a
ji
，
则访问和它对应的元素
a
ji
即可，即：
k
＝
j
×
(
j
-1)/2＋
i
-1
三角矩阵
压缩存储：只存储上三角（或下三角）部分的元素。
下三角矩阵：
矩阵中任一元素
a
ij
在数组中的下标
k
与
i
、
j
的对应关系：
上三角矩阵：
矩阵中任一元素
a
ij
在数组中的下标
k
与
i
、
j
的对应关系：
对角矩阵
所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。
寻址计算方法：
元素
a
ij
在一维数组中的序号
=2 + 3(
i
－2)+(
j
－
i
+ 2)
=2
i
+
j
-2
∵
一维数组下标从0开始
∴元素
a
ij
在一维数组中的下标
k
=
2
i
+
j
-3
稀疏矩阵
由于稀疏矩阵中的非零元素的分布没有规律，因此
将稀疏矩阵中的每个非零元素表示为
：
(
行号，列号，非零元素值)
——
三元组
三元组表
：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。
转置操作：
算法1：
直接取，顺序存
（时间复杂度较高）
在
A
的三元组顺序表中
依次
找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后
顺序
存储到
B
的三元组顺序表中。
伪代码：
1. 设置转置后矩阵
B
的行数、列数和非零元个数；
2. 在
B
中设置初始存储位置
pb；
3. for (col=
最小列号;
col<=
最大列号;
col++)
3.1
在
A
中查找列号为
col
的三元组；
3.2 交换其行号和列号，存入
B
中
pb
位置；
3.3
pb++；
算法2：
顺序取，直接存。
即在
A
中依次取三元组，交换其行号和列号放到
B
中
适当
位置。
引入两个数组作为辅助数据结构：
num[nu]：
存储矩阵
A
中某列的非零元素的个数；
cpot
[nu]：
初值表示矩阵
A
中某列的第一个非零元素在
B
中的位置。
num
与
cpot存在如下递推关系：
cpot
[0]=0；
cpot
[col]=
cpot
[col-1]+num[col-1]； 1≤col＜nu
将矩阵
A
中
col
列元素存放在
B
中下标为
cpot
[col]
的位置
伪代码：
1. 设置转置后矩阵
B
的行数、列数和非零元素的个数；
2. 计算
A
中每一列的非零元素个数；
3. 计算
A
中每一列的第一个非零元素在
B
中的下标；
4. 依次取
A
中的每一个非零元素对应的三元组；
4.1 确定该元素在
B
中的下标
pb
；
4.2
将该元素的行号列号交换后存入
B
中
pb
的位置；
4.3 预置该元素所在列的下一个元素的存放位置；
十字链表
采用
链接
存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：
row：
存储非零元素的行号
col：
存储非零元素的列号
item：
存储非零元素的值
right：
指针域，指向同一行中的下一个三元组
down：
指针域，指向同一列中的下一个三元组
稀疏矩阵的压缩存储——十字链表的具体存储方法
（
1
） 每一行的非零元素按其列号由
right
域链成一个带头结点的循环链表。
（
2
）每一列的非零元素按其行号由
down
域链成一个带头结点的循环链表。
（
3
）由于各行列链表头结点
row
域、
col
域和
item
域均为空，行链表头结点只用
right
域，列链表头结点只用
down
域，故这两组链表头结点可以合用。
（
4
）为了实现对某一行（或某一列）头指针的快速查找，将指向这些头结点的头指针存在一个数组中。
本章总结
