第 5-4 页
深圳信息学院
三、二维数组的存储 1. 行为主序的方式：先存储数组的第一行元素，再存储第二行元素 ； 行为主序的方式：先存储数组的第一行元素，再存储第二行元素…； 2. 列为主序的方式：先存储数组的第一列元素，再存储第二列元素 ； 列为主序的方式：先存储数组的第一列元素，再存储第二列元素…； 在众多的程序设计语言中，以行序为主序方式的有PASCAL、 在众多的程序设计语言中，以行序为主序方式的有 、 COBOL、C及扩展 及扩展BASIC等，以列序为主序方式的有 语言。 、 及扩展 等 以列序为主序方式的有FORTRAN语言。 语言
7
M=
0
0 0
0 0
15 0 0 0
0 -4
0 0 0 -1 0 0 -2 0 0 0 0 21 深圳信息学院
第 5-8 页
二、稀疏矩阵的三元组表示法： 稀疏矩阵的三元组表示法： （1）将稀疏矩阵的非零元素用三元组 ） < row, column, value > 表示（ 表示稀疏矩阵的第 row 行、第 表示（ column 列的值为 value） ） （2）用一顺序表（二维数组）来存放上述三元组（每一个三元组即为 ）用一顺序表（二维数组）来存放上述三元组（ 顺序表的一个数据元素）并按行为主序存放。 顺序表的一个数据元素）并按行为主序存放。 4 6 6 例： 0 0 7 顺序存储结构——三元组表示法 顺序存储结构 三元组表示法 0 4 15
例：一维数组
a
a0
0
a1
1
a2
2
a3
3
……
……
ai
i
...…
……
an-1
n-1
深圳信息学院
第 5-2 页
矩阵) 例：二维数组(m X n矩阵 二维数组 矩阵
a[0][0] a[0][1] a[1][1] a[1][0] A = a[2][0] a[2][1] a[m −1][0] a[m −1][1]
7
M=
0
0 0
0 0
15 0 0 0
1 2 3 3
1 3 0 5
-4 -1 -2 21
第 5-9 页
0 -4
0 0 0 -1 0 0 -2 0 0 0 0 21
深圳信息学院
loc(aij)=loc(a00)+(i*n+j)*s
深圳信息学院
第 5-6 页
a00 a10
按列为主序存放
……. a(m-1)0 a01
a00 a01 …….. a10 a11 ……..
a0(n-1) a1()
a11 …….. a(m-1)1 ……. a0(n-1) a1(n-1) …….. a(m-1)(n-1)
深圳信息学院
第 5-5 页
a00 a01 ……. a0(n-1) a10
按行为主序存放
a00 a01 …….. a10 a11 ……..
a0(n-1) a1(n-1)
a11 …….. a1(n-1)
…………………. a(m-1)0 …….. a(m-1)(n-1)
………. a(m-1)0 a(m-1)1 …….. a(m-1)(n-1)
…………………. a(m-1)0 …….. a(m-1)(n-1)
loc(aij)=loc(a00)+(j*m+i)*s
深圳信息学院
第 5-7 页
5.3
稀疏矩阵
一、概念 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。 一个m行 列的矩阵是一平面阵列 列的矩阵是一平面阵列， 个元素。 一个 行n列的矩阵是一平面阵列，有m×n个元素。可以对矩阵作加、 × 个元素 可以对矩阵作加、 乘等运算。这里我们感兴趣的不是矩阵本身， 减、乘等运算。这里我们感兴趣的不是矩阵本身，而是矩阵在计算机 内的有效存储方法和对应的各种矩阵运算的算法。 内的有效存储方法和对应的各种矩阵运算的算法。只有少数程序设计 语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。 语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。 有较多值相同元素或较多零元素， 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没 有一定规律的矩阵称为稀疏矩阵。 有一定规律的矩阵称为稀疏矩阵。 例：
《数据结构》 数据结构》
第五章
数组和广义表
深圳信息学院
第 5-1 页
数
组
5.1 数组定义 数组是由下标和值组成的偶对（下标， 的有限集合。 数组是由下标和值组成的偶对（下标，值）的有限集合。 数组中每组有定义的下标，都存在一个与之相对应的值， 数组中每组有定义的下标，都存在一个与之相对应的值，这个值称 为数组元素。 为数组元素。
a[0][ n −1] a[1][ n −1] a[2][ n −1] a[m −1][ n −1]
深圳信息学院
第 5-3 页
5.2 数组的顺序存储结构 一、数组的操作 1. 建立数组。 建立数组。 2. 对于给定下标，存取相应的数组元素。 对于给定下标，存取相应的数组元素。 3. 对于给定下标，修改相应的数组元素。 对于给定下标，修改相应的数组元素。 二、一维数组的存储 Loc(a[i])=Loc(a[0])+i*s 0 1 i n-1 a0 a1 … ai … an-1 Loc(a0) Loc(a0)+s Loc(a0)+i*s Loc(a0)+(n-1)*s a0 a1 … ai … an-1