北航数据结构Data03.ppt

数据结构
2
第三章数组
数组的概念
数组的定义
数组的形式化定义
数组的存储结构
矩阵的压缩存储
对称矩阵的压缩存储
对角矩阵的压缩存储
稀疏矩阵的三元组表示
3
稀疏矩阵的十字链表表示
数组应用举例
一元多项式的数组表示
n阶魔方
上机作业
4
数组的定义
1、数组
数组(Array)是一组按一定格式排列的、具有相同属性的项目或者数据元素,如线性表、矩阵等。
如果线性表的所有元素都是线性表(称为子表) ,且这些子线性表具有相同的上限标号和下限标号,那么这类线性表也称为数组。
数组可以看成是下标与值组成的数偶的有序集合,即对于每个下标,总有一个相应的元素与之对应。
这种基于位置上的对应关系是一种线性关系,因此,数组的逻辑结构就是一种线性结构。
5
2、数组的表示
在数组中用下标来唯一标识数据元素。如果数组元素只需要一个下标就能唯一确定,则称为一维数组;至少需要n个下标才能唯一确定一个元素,则称为n维数组。
一维数组表示成:A(n) 或者 A(m : n);其中A是数组名称,m称为数组的下界,n称为上界;而A(n)的下界默认为1。
二维数组表示成:A(m,n) 或者 A(i:m ,j:n);
n维数组表示成:A(i1,i2,i3,...,in);其中i1,i2,i3, ..., in表示数组各维的下标上界,下界均为1。
6
数组的形式化定义
1、一维数组的形式化定义
一维数组的逻辑结构可以形式化地定义为:ARRAY_1=(D,R),
其中,D={ai|c1<=i<=c2,aidata object},
R={ROW},ROW={<ai,ai+1>|c1<=i<=c2, ai,ai+1D }。
c1、c2,分别表示下标的一对界偶,即下界和上界。
数组中元素个数= c2 - c1 + 1
7
2、二维数组的形式化定义
二维数组,其逻辑结构的形式化定义可以表示成:ARRAY_2=(D,R),其中,D={aij|c1<=i<=c2, d1<=j<=d2,aijdata object},R={ROW,COL},
ROW={<aij,ai,j+1>|c1<=i<=c2, d1<=j<=d2-1, aij,ai,j+1D }
COL={<aij,ai+1,j>|c1<=i<=c2-1, d1<=j<=d2, aij,ai+1,jD }
(c1、c2)与(d1、d2)分别是下标i和j的上下界。
数组中元素个数= (c2 - c1 + 1)*(d2 - d1 + 1)
8
n维数组的逻辑结构的形式化定义ARRAY_n=(D,R),其中,
D={aj1,j2,…,jn|ci<=ji<=di,aj1,j2,…,jndata object},R={R1,R2,……,Rn}
Ri={<aj1,…,ji,…,jn,aj1,…,ji+1,…,jn >|
ck<=jk<=dk且k<>i,ci<=ji<=di-1,
aj1,…,ji,…,jn ,aj1,…,ji+1,…,jnD }
3、n维数组的形式化定义
9
4、数组的操作
n维数组的每个元素受到n个关系的约束,再每个关系中,每个元素都存在一个直接后继。每个关系都是线性关系。因此,n维数组是线性表的一种推广。
一般数组的规模是固定的,没有插入、删除运算。
给出一组下标,检索对应的数据元素;或者存取相应元素的值;
重新排列数组元素。
10
数组的存储结构
1、数组的降维存储
由于计算机内的存储空间是一维(线性)的,要将多维数组存储到计算机内,必须将多维数组映射到一维存储空间中,因此,需要降低数组的维数,即将n维数组看成是n个n-1维数组的有序集合。
在计算机中,数组也与线性表一样,是保存在一块连续的内存空间中的,即数组采用的是顺序分配方式。