5.1 数组
一维数组的示例计算机学院信息教研室
DS
计算机学院信息教研室
DS
一维数组的特点连续存储的线性聚集（别名 向量 ）
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
只要知道一个数组元素在数组中是第几个,就可直接存取这个数组元素,
一维数组
时 0,)(
时 0α,
)(
iliL O C
i
iL O C
1
LOC ( ai ) = LOC ( ai -1 ) + l =α+ i*l
计算机学院信息教研室
DS 一维数组的数组元素可以是基本数据类型,可以是复杂数据类型,当基本类型也是数组时,一维数组扩充为二维数组 (矩阵 ).
A[j][k] 直接前驱 直接后驱行的方向 a[j][k-1] a[j][k+1]
列的方向 a[j-1][k] a[j+1][k]
沿矩阵边缘,无直接前驱和直接后驱的情况,
二维数组 (矩阵 ) 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
二维数组 (矩阵 ) 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
二维数组
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
11211101
12221202
11211101
10201000
mnananana
maaaa
maaaa
maaaa
a
行优先 LOC ( i,j ) =
= a + ( i * m + j) * l
安全类数组的提出考虑了数足下标越界问题，
且可以重新定义数组元素个数计算机学院信息教研室
DS
5.3 特殊矩阵的压缩存储科学和工程计算问题中经常用到矩阵运算，
矩阵数据元素一般用二维数组来存储当遇到特殊矩阵时，
为了降低空间复杂度，
可考虑对矩阵进行压缩存储 ----只存储其中数值不同的部分计算机学院信息教研室
DS
3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
§ 5.3 特殊矩阵的压缩存储
A[m][n] 保存 m*n个数据
1 5 11 18
0 10 17 20
0 0 1 9
0 0 0 3
3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
上三角矩阵对称矩阵
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3
常数矩阵一,常数矩阵的存储
（ m,n,c)（ 4,4,3)
二,n阶 对称矩阵存储 3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
a[i][j]=a[j][i]
0=< i,j<=n-1
只保存下三角矩阵：
a[i][j] = sa[k]
k=i*(i+1)/2+j; (i>=j)
k=j*(j+1)/2+i; (i<j)
3 6 6 6
5 8 6 6
9 4 3 6
1 7 0 1
只保存下三角矩阵：
a[i][j] = sa[k]
k=i*(i+1)/2+j; (i>=j)
a[i][j] = sa[n*(n+1)/2]
(i<j)
§ 5.4 稀疏矩阵的压缩存储
21 0 0 19 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 50 0
0 0 0 0 0 0
t=3;
s=6*6=36;
￡=t/s 稀疏因子
￡<=0.05
三元组存储
（ 1）三元组顺序表；
（ 2）三元组链表 ；
§ 5.5 串（ string)
定义,n个字符组成的有限序列
s=“s0 s1 …,sn-1”,n为串的长度。
s1=“I am a singer”
s2=“singer” 存储结构：
（ 1）链表；
（ 2）数组；
串 是非数值计算 算法处理的主要对象串和字符时两个不同的概念串,a”
字符 ‘ a’
计算机学院信息教研室
DS
C++串的基本操作
（ 1）串长度
（ 2）串拷贝
（ 3）串连接
（ 4）串比较
（ 5）串定位
…
计算机学院信息教研室
DS
本章小结学习要点：
a)、熟悉数组元素的定位及串的基本概念；
b),掌握特殊、稀疏矩阵的存储 ；
c)、熟悉串的基本操作。
一维数组的示例计算机学院信息教研室
DS
计算机学院信息教研室
DS
一维数组的特点连续存储的线性聚集（别名 向量 ）
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
只要知道一个数组元素在数组中是第几个,就可直接存取这个数组元素,
一维数组
时 0,)(
时 0α,
)(
iliL O C
i
iL O C
1
LOC ( ai ) = LOC ( ai -1 ) + l =α+ i*l
计算机学院信息教研室
DS 一维数组的数组元素可以是基本数据类型,可以是复杂数据类型,当基本类型也是数组时,一维数组扩充为二维数组 (矩阵 ).
A[j][k] 直接前驱 直接后驱行的方向 a[j][k-1] a[j][k+1]
列的方向 a[j-1][k] a[j+1][k]
沿矩阵边缘,无直接前驱和直接后驱的情况,
二维数组 (矩阵 ) 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
二维数组 (矩阵 ) 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
二维数组
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
11211101
12221202
11211101
10201000
mnananana
maaaa
maaaa
maaaa
a
行优先 LOC ( i,j ) =
= a + ( i * m + j) * l
安全类数组的提出考虑了数足下标越界问题，
且可以重新定义数组元素个数计算机学院信息教研室
DS
5.3 特殊矩阵的压缩存储科学和工程计算问题中经常用到矩阵运算，
矩阵数据元素一般用二维数组来存储当遇到特殊矩阵时，
为了降低空间复杂度，
可考虑对矩阵进行压缩存储 ----只存储其中数值不同的部分计算机学院信息教研室
DS
3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
§ 5.3 特殊矩阵的压缩存储
A[m][n] 保存 m*n个数据
1 5 11 18
0 10 17 20
0 0 1 9
0 0 0 3
3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
上三角矩阵对称矩阵
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3
常数矩阵一,常数矩阵的存储
（ m,n,c)（ 4,4,3)
二,n阶 对称矩阵存储 3 5 9 1
5 8 4 7
9 4 3 0
1 7 0 1
a[i][j]=a[j][i]
0=< i,j<=n-1
只保存下三角矩阵：
a[i][j] = sa[k]
k=i*(i+1)/2+j; (i>=j)
k=j*(j+1)/2+i; (i<j)
3 6 6 6
5 8 6 6
9 4 3 6
1 7 0 1
只保存下三角矩阵：
a[i][j] = sa[k]
k=i*(i+1)/2+j; (i>=j)
a[i][j] = sa[n*(n+1)/2]
(i<j)
§ 5.4 稀疏矩阵的压缩存储
21 0 0 19 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 50 0
0 0 0 0 0 0
t=3;
s=6*6=36;
￡=t/s 稀疏因子
￡<=0.05
三元组存储
（ 1）三元组顺序表；
（ 2）三元组链表 ；
§ 5.5 串（ string)
定义,n个字符组成的有限序列
s=“s0 s1 …,sn-1”,n为串的长度。
s1=“I am a singer”
s2=“singer” 存储结构：
（ 1）链表；
（ 2）数组；
串 是非数值计算 算法处理的主要对象串和字符时两个不同的概念串,a”
字符 ‘ a’
计算机学院信息教研室
DS
C++串的基本操作
（ 1）串长度
（ 2）串拷贝
（ 3）串连接
（ 4）串比较
（ 5）串定位
…
计算机学院信息教研室
DS
本章小结学习要点：
a)、熟悉数组元素的定位及串的基本概念；
b),掌握特殊、稀疏矩阵的存储 ；
c)、熟悉串的基本操作。
