? 一维数组
? 多维数组
? 特殊矩阵的压缩存储
一维数组
? 定义
相同类型的数据元素的集合。
? 一维数组的示例
? 与顺序表的不同在于数组可以按元
素的下标直接存储和访问数组元素。
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
数组的定义和初始化
main ( ) {
int a1[3] = { 3,5,7 },*elem;
for ( int i = 0; i < 3; i++ )
printf (,%d”,a1[i],“\n” ); //静态数组
elem = a1;
for ( int i = 0; i < 3; i++ ) {
printf (,%d”,*elem,“\n” ); //动态数组
elem++;
}
}
数组溢出的处理
? 一维数组的问题在于：如果其空间大小已
经分配，一旦空间占满，再加入新元素将
产生溢出。
? 已知一维数组的大小为 MaxSize，其定义
和分配如下：
typedef int dataType;
DataType * data = (DataType *) malloc
( MaxSize * sizeof ( DataType ) );
? 现已产生溢出，那么处理溢出的方法为：
const int NewSize = 100;
DataType * newArray =
new DataType[NewSize];
if ( newArray == NULL )
{ stderr (“存储分配错 \n” ); exit(1); }
int n = ( NewSize <= MaxSize )?
NewSize, MaxSize;
DataType *srcptr = data;
DataType *destptr = newArray;
while ( n-- ) * destptr++ = * srcptr++;
delete [ ] data;
data = newArray;
多维数组
? 多维数组是一维数组的推广
? 多维数组是一种非线性结构。其特
点是 每一个数据元素可以有多个直
接前驱和多个直接后继 。
? 数组元素的下标一般具有固定的下
界和上界，因此它比其他复杂的非
线性结构简单。
二维数组 三维数组
行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
??
?
?
?
?
?
??
?
?
?
?
?
????
?
?
?
?
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
?
????
?
?
?
? 二维数组
行优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每
个元素占用 d 个存储单元
LOC ( j,k ) = a + ( j * m + k ) * d
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
?
?
?
?
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
?
????
?
?
?
列优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每
个元素占用 d 个存储单元
LOC ( j,k ) = a + ( k * n + j ) * d
? 三维数组
?各维元素个数为 m1,m2,m3
?下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * d
前 i1 页总
元素个数
第 i1 页的
前 i2 行 总
元素个数
第 i2 行前 i3
列 元素个数
? n 维数组
?各维元素个数为 m1,m2,m3,…,m n
?下标为 i1,i2,i3,…,i n 的数组元素的存
储地址：
limia
n
j
n
jk
nkj *
1
1 1
?
?
?
?
?
?
?
?
???? ? ?
?
? ??
LOC ( i1,i2,…,i n ) = a +
( i1*m2*m3*…*m n + i2*m3*m4*…*m n+
+ ……+ i n-1*mn + in ) * l
特殊矩阵的压缩存储
? 特殊矩阵是指非零元素或零元素的分
布有一定规律的矩阵。
? 特殊矩阵的压缩存储主要是针对 阶数
很高 的特殊矩阵。为节省存储空间，
对可以不存储的元素，如零元素或对
称元素，不再存储。
?对称矩阵
?三对角矩阵
对称矩阵的压缩存储
? 设有一个 n?n 的对称矩阵 A。
?
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
A
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
在矩阵中, aij = aji
? 为节约存储，只存对角线及对角线以
上的元素，或者只存对角线及对角线
以下的元素。前者称为上三角矩阵，
后者称为下三角矩阵。
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
下
三
角
矩
阵
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
上
三
角
矩
阵
? 把它们按行存放于一个一维数组 B 中，称
之为对称矩阵 A 的压缩存储方式。
? 数组 B 共有 n + ( n - 1 ) + ???+ 1 =
n*(n+1)/2 个元素。
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?下三
角
矩
阵
B a00 a10 a11 a20 a21 a22 a30 a31 a32 …… an-1n-1
0 1 2 3 4 5 6 7 8 n(n+1)/2-1
若 i ? j,数组元素 A[i][j]在数组 B中的存放位置
为 1 + 2 + ???+ i + j = (i + 1)* i / 2 + j
前 i行 元素总数 第 i行第 j个 元素前元素个数
若 i < j，数组元素 A[i][j] 在矩阵的上三角
部分,在数组 B 中没有存放，可以找它的对
称元素 A[j][i],= j *(j +1) / 2 + i
若已知某矩阵元素位于数组 B 的第 k个位
置，可寻找满足
i (i + 1) / 2 ? k < (i + 1)*(i + 2) / 2
的 i,此即为 该元素的行号。
j = k - i * (i + 1) / 2
此即为该元素的列号。
例，当 k = 8,3*4 / 2 = 6 ? k < 4*5 / 2 =10,
取 i = 3。 则 j = 8 - 3*4 / 2 = 2。
?
?
?
?
?
?
?
?
?
?
33323130
23222120
13121110
03020100
aaaa
aaaa
aaaa
aaaa
上
三
角
矩
阵
B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33
0 1 2 3 4 5 6 7 8 9
若 i? j，数组元素 A[i][j]在数组 B中的存放位
置为 n + (n-1) + (n-2) + ???+ (n-i+1) + j-i
前 i行 元素总数 第 i行第 j个 元素前元素个数
n = 4
若 i ? j，数组元素 A[i][j]在数组 B中的存
放位置为
n + (n-1) + (n-2) + ???+ (n-i+1) + j-i =
= (2*n-i+1) * i / 2 + j-i =
= (2*n-i-1) * i / 2 + j
若 i > j，数组元素 A[i][j]在矩阵的下三角
部分，在数组 B 中没有存放。因此，找它
的对称元素 A[j][i]。
A[j][i]在数组 B 的第 (2*n-j-1) * j / 2 + i
的位置中找到。
三对角矩阵的压缩存储
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??????
1121
122232
232221
121110
0100
0000
000
000
000
0000
A
nnnn
nnnnnn
aa
aaa
aaa
aaa
aa
??????
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1
0 1 2 3 4 5 6 7 8 9 10
? 三对角矩阵中除主对角线及在主对角线上
下最临近的两条对角线上的元素外，所有
其它元素均为 0。总共有 3n-2个非零元素。
? 将三对角矩阵 A中三条对角线上的元素按
行存放在一维数组 B 中，且 a00存放于 B[0]。
? 在三条对角线上的元素 aij满足
0 ? i ? n-1,i-1 ? j ? i+1
? 在一维数组 B 中 A[i][j] 在第 i 行，它前面
有 3*i-1 个非零元素,在本行中第 j 列前面
有 j-i+1 个，所以元素 A[i][j] 在 B 中位置
为 k = 2*i + j。
? 若已知三对角矩阵中某元素 A[i][j] 在数组
B[ ] 存放于第 k 个位置，则有
i = ?(k + 1) / 3?
j = k - 2 * i
? 例如，当 k = 8 时，
i = ?(8+1) / 3? = 3,j = 8 - 2*3 = 2
当 k = 10 时，
i = ?(10+1) / 3? = 3,j = 10 - 2*3 = 4
? 多维数组
? 特殊矩阵的压缩存储
一维数组
? 定义
相同类型的数据元素的集合。
? 一维数组的示例
? 与顺序表的不同在于数组可以按元
素的下标直接存储和访问数组元素。
35 27 49 18 60 54 77 83 41 02
0 1 2 3 4 5 6 7 8 9
数组的定义和初始化
main ( ) {
int a1[3] = { 3,5,7 },*elem;
for ( int i = 0; i < 3; i++ )
printf (,%d”,a1[i],“\n” ); //静态数组
elem = a1;
for ( int i = 0; i < 3; i++ ) {
printf (,%d”,*elem,“\n” ); //动态数组
elem++;
}
}
数组溢出的处理
? 一维数组的问题在于：如果其空间大小已
经分配，一旦空间占满，再加入新元素将
产生溢出。
? 已知一维数组的大小为 MaxSize，其定义
和分配如下：
typedef int dataType;
DataType * data = (DataType *) malloc
( MaxSize * sizeof ( DataType ) );
? 现已产生溢出，那么处理溢出的方法为：
const int NewSize = 100;
DataType * newArray =
new DataType[NewSize];
if ( newArray == NULL )
{ stderr (“存储分配错 \n” ); exit(1); }
int n = ( NewSize <= MaxSize )?
NewSize, MaxSize;
DataType *srcptr = data;
DataType *destptr = newArray;
while ( n-- ) * destptr++ = * srcptr++;
delete [ ] data;
data = newArray;
多维数组
? 多维数组是一维数组的推广
? 多维数组是一种非线性结构。其特
点是 每一个数据元素可以有多个直
接前驱和多个直接后继 。
? 数组元素的下标一般具有固定的下
界和上界，因此它比其他复杂的非
线性结构简单。
二维数组 三维数组
行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
??
?
?
?
?
?
??
?
?
?
?
?
????
?
?
?
?
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
?
????
?
?
?
? 二维数组
行优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每
个元素占用 d 个存储单元
LOC ( j,k ) = a + ( j * m + k ) * d
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
?
?
?
?
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
]][[]][[]][[
111101
121202
111101
101000
mnanana
maaa
maaa
maaa
a
?
????
?
?
?
列优先存放：
设数组开始存放位置 LOC( 0,0 ) = a,每
个元素占用 d 个存储单元
LOC ( j,k ) = a + ( k * n + j ) * d
? 三维数组
?各维元素个数为 m1,m2,m3
?下标为 i1,i2,i3的数组元素的存储地址：
（按页 /行 /列存放）
LOC ( i1,i2,i3 ) = a +
( i1* m2 * m3 + i2* m3 + i3 ) * d
前 i1 页总
元素个数
第 i1 页的
前 i2 行 总
元素个数
第 i2 行前 i3
列 元素个数
? n 维数组
?各维元素个数为 m1,m2,m3,…,m n
?下标为 i1,i2,i3,…,i n 的数组元素的存
储地址：
limia
n
j
n
jk
nkj *
1
1 1
?
?
?
?
?
?
?
?
???? ? ?
?
? ??
LOC ( i1,i2,…,i n ) = a +
( i1*m2*m3*…*m n + i2*m3*m4*…*m n+
+ ……+ i n-1*mn + in ) * l
特殊矩阵的压缩存储
? 特殊矩阵是指非零元素或零元素的分
布有一定规律的矩阵。
? 特殊矩阵的压缩存储主要是针对 阶数
很高 的特殊矩阵。为节省存储空间，
对可以不存储的元素，如零元素或对
称元素，不再存储。
?对称矩阵
?三对角矩阵
对称矩阵的压缩存储
? 设有一个 n?n 的对称矩阵 A。
?
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
A
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
在矩阵中, aij = aji
? 为节约存储，只存对角线及对角线以
上的元素，或者只存对角线及对角线
以下的元素。前者称为上三角矩阵，
后者称为下三角矩阵。
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
下
三
角
矩
阵
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?
上
三
角
矩
阵
? 把它们按行存放于一个一维数组 B 中，称
之为对称矩阵 A 的压缩存储方式。
? 数组 B 共有 n + ( n - 1 ) + ???+ 1 =
n*(n+1)/2 个元素。
?
?
?
?
?
?
?
?
?
?
?
?
?????
?
?
?
11121110
12222120
11121110
10020100
nnnnn
n
n
n
aaaa
aaaa
aaaa
aaaa
?
?????
?
?
?下三
角
矩
阵
B a00 a10 a11 a20 a21 a22 a30 a31 a32 …… an-1n-1
0 1 2 3 4 5 6 7 8 n(n+1)/2-1
若 i ? j,数组元素 A[i][j]在数组 B中的存放位置
为 1 + 2 + ???+ i + j = (i + 1)* i / 2 + j
前 i行 元素总数 第 i行第 j个 元素前元素个数
若 i < j，数组元素 A[i][j] 在矩阵的上三角
部分,在数组 B 中没有存放，可以找它的对
称元素 A[j][i],= j *(j +1) / 2 + i
若已知某矩阵元素位于数组 B 的第 k个位
置，可寻找满足
i (i + 1) / 2 ? k < (i + 1)*(i + 2) / 2
的 i,此即为 该元素的行号。
j = k - i * (i + 1) / 2
此即为该元素的列号。
例，当 k = 8,3*4 / 2 = 6 ? k < 4*5 / 2 =10,
取 i = 3。 则 j = 8 - 3*4 / 2 = 2。
?
?
?
?
?
?
?
?
?
?
33323130
23222120
13121110
03020100
aaaa
aaaa
aaaa
aaaa
上
三
角
矩
阵
B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33
0 1 2 3 4 5 6 7 8 9
若 i? j，数组元素 A[i][j]在数组 B中的存放位
置为 n + (n-1) + (n-2) + ???+ (n-i+1) + j-i
前 i行 元素总数 第 i行第 j个 元素前元素个数
n = 4
若 i ? j，数组元素 A[i][j]在数组 B中的存
放位置为
n + (n-1) + (n-2) + ???+ (n-i+1) + j-i =
= (2*n-i+1) * i / 2 + j-i =
= (2*n-i-1) * i / 2 + j
若 i > j，数组元素 A[i][j]在矩阵的下三角
部分，在数组 B 中没有存放。因此，找它
的对称元素 A[j][i]。
A[j][i]在数组 B 的第 (2*n-j-1) * j / 2 + i
的位置中找到。
三对角矩阵的压缩存储
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??????
1121
122232
232221
121110
0100
0000
000
000
000
0000
A
nnnn
nnnnnn
aa
aaa
aaa
aaa
aa
??????
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1
0 1 2 3 4 5 6 7 8 9 10
? 三对角矩阵中除主对角线及在主对角线上
下最临近的两条对角线上的元素外，所有
其它元素均为 0。总共有 3n-2个非零元素。
? 将三对角矩阵 A中三条对角线上的元素按
行存放在一维数组 B 中，且 a00存放于 B[0]。
? 在三条对角线上的元素 aij满足
0 ? i ? n-1,i-1 ? j ? i+1
? 在一维数组 B 中 A[i][j] 在第 i 行，它前面
有 3*i-1 个非零元素,在本行中第 j 列前面
有 j-i+1 个，所以元素 A[i][j] 在 B 中位置
为 k = 2*i + j。
? 若已知三对角矩阵中某元素 A[i][j] 在数组
B[ ] 存放于第 k 个位置，则有
i = ?(k + 1) / 3?
j = k - 2 * i
? 例如，当 k = 8 时，
i = ?(8+1) / 3? = 3,j = 8 - 2*3 = 2
当 k = 10 时，
i = ?(10+1) / 3? = 3,j = 10 - 2*3 = 4
