计算机软件技术基础教程课件-9第九章-数组

第四章数组9.1数组的定义和运算一维数组[a0,a1,…,an-1]，由固定的n个元素构成，每个元素除具有值以外，还带有一个下标值，以确定该元素在表中的位置。二维数组

也由固定的六个元素构成，每个元素由值与一对下标构成。9.1数组的定义和运算此外，二维数组也可看做是由两个一维数组与一对下标元素定义的一维数组，这时每个数据元素受到两个下标关系约束，数据元素之间在每一个关系中仍具有线性特性，而在整个结构中呈非线性。例如，二维数组：9.1数组的定义和运算又可以写成

或

可以发现，当维数为1时，数组是一种元素数目固定的线性表；当维数大于1时，数组可以看做是线性表的推广。9.1数组的定义和运算数组结构具有的性质如下：

(1)数据元素数目固定。一旦说明了一个数组结构，其中的元素数目就不再有增减变化。

(2)数据元素具有相同的类型。

(3)数据元素的下标关系具有上下界的约束，并且下标有序。

对于数组，通常只有两种运算：

(1)给定一组下标，存取相应的数据元素。

(2)给定一组下标，修改相应数据元素中的某个数据项的值。9.2数组的顺序存储结构由于数组一般不做插入和删除运算，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此，采用顺序存储结构表示数组是自然的事了。9.2数组的顺序存储结构二维数组的两种存储方式9.2数组的顺序存储结构例如：二维数组Amn按行优先顺序存储在内存中，假设每个数据元素占用d个存储单元，则有

上式的推导思路是：结构中第aij个元素，其前面已存放了i-1行共(i-1)

n个元素，在第i行中其前面已存放了j-1个元素，因而总共占用的空间为((i-1)

n+j-1)

d，再以a11的存储地址作起始位置，即可推得。9.2数组的顺序存储结构同理，可推出二维数组Amn以列为主序的优先存储地址计算公式如下：

Loc(aij)=Loc(a11)+[(j-1)

m+(i-1)]

d

同样，三维数组Amnp按行优先顺序存储，其地址计算公式如下：

Loc(aijk)=Loc(a111)+[(i-1)

n

p+(j-1)

p+(k-1)]

d

9.2数组的顺序存储结构上述讨论均是假设数组的下界是1，而一般的二维数组是A[c1…d1，c2…d2]，这里c1，c2不一定是1。aij前一共有i-c1行，一共有d2-c2+1列，故i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算公式为

值得注意的是，在C语言中，数组下标的下界是0，因此二维数组的地址计算公式为：9.3矩阵的压缩存储9.3.1特殊矩阵1.对角矩阵

在对角矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和主对角线相邻近的上、下方以外，其余元素均为0。下图就是一个三对角矩阵。

9.3矩阵的压缩存储9.3.1特殊矩阵现在考虑最简单的一种，即只在主对角线上含有非零元素的对角矩阵，如下图所示。9.3矩阵的压缩存储9.3.1特殊矩阵2.三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指矩阵的下三角(不包含对角线)中的元素均为常数(或0)的n阶矩阵；下三角矩阵与之相反。下图给出了两种三角矩阵的表示形式。9.3矩阵的压缩存储9.3.1特殊矩阵下面找出数组元素A[k] 与aij的关系。

在下三角矩阵中，对于aij元素，前面已存放了i行，元素的总数为i

(i+1)/2，aij处在第i+1行的第j+1个元素，则其前面已存放的元素数目为i

(i+1)/2+j，也就是说，aij应是数组A的第k个元素，k=i

(i+1)/2+j。A[k]与aij的对应关系为9.3矩阵的压缩存储9.3.1特殊矩阵3.对称矩阵

在n阶方阵A中，若A中的元素满足aij=aji(0≤i，j≤n-1)，则称A是对称矩阵。下图给出了一个六阶对称矩阵。9.3矩阵的压缩存储9.3.1特殊矩阵由于对称矩阵中的元素关于对角线对称，因此在存储时只需存储矩阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。假如我们存储下三角中的元素，则元素的总数为n

(n+1)/2，按行优先关系存储，可得A[k] 与aij的对应关系为

k=i

(i+1)/2+j

0≤k≤n

(n+1)/2，i≥j

当i<j时，aij在上三角矩阵中，由于aij=aji，因此

k=j

(j+1)/2+i

i<j

最后一个统一的k，i，j的对应关系为

k=i

(i+1)/2+j

其中，i=max(i，j)；j=min(i，j)。9.3矩阵的压缩存储9.3.2稀疏矩阵由于特殊矩阵中非零元素的分布都是有规律的，因此总可以找到矩阵中的元素与一维数组下标之间的对应关系。还有一类矩阵，其中也含有非零元素及较多的零元素，但非零元素的分布没有任何规律，这就是稀疏矩阵。9.3矩阵的压缩存储9.3.2稀疏矩阵若矩阵Am

n中有s个非零元素，t个零元素，且s<<t，则称该矩阵为稀疏矩阵。

对于s与t的比较数量级，人们只能靠感觉来判定，这与实际问题及对存储的要求有关。由于非零元素的分布一般是没有规律的，因此，在存储非零元素的同时，还必须存储适当的辅助信息，才能迅速确定一个非零元素是矩阵中的哪一个元素。下面仅讨论用三元组表来表示两种稀疏矩阵的压缩存储方法。9.3矩阵的压缩存储9.3.2稀疏矩阵1.三元组表

若将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，则得到一个其结点均是三元组的线性表。我们将该线性表的顺序存储结构称为三元组表。因此，三元组表是稀疏矩阵的一种顺序存储结构。在下面的讨论中，均假定三元组是按行优先顺序排列的。9.3矩阵的压缩存储9.3.2稀疏矩阵稀疏矩阵A及三元组表9.3矩阵的压缩存储9.3.2稀疏矩阵一个m 

 n的矩阵A，它的转置矩阵B是一个n

m矩阵，且A[i][j] = B[j][i]，0≤i≤m-1，0≤j≤n-1，即A的行是B的列，A的列是B的行。

将A转置为B，就是将A的三元组表a->data置换为B的三元组表b->data，如果只是简单地交换a->data中i和j中的内容，那么得到的b->data将是一个按列优先顺序存储的稀疏矩阵B。要得到如图4-14(b)所示的按行优先顺序存储的b->data，就必须重新排列三元组的顺序。9.3矩阵的压缩存储9.3