已知对称矩阵An*n (Aij=Aji)的主对角线..

2009年上半年上午试卷综合知识

第 40 题


知识点	数组和矩阵矩阵数组
关键词	一维数组数组
章/节	常用数据结构

已知对称矩阵A_n*_n (A_i,j=A_j,i)的主对角线元素全部为0,若用一维数组B仅存储矩阵A的下三角区域的所有元素（不包括主对角线元素），则数组B的大小为（40) 。

A. n(n-l)

B. n²/2

C. n(n-l)/2

D. n(n+l)/2

相关试题数组

第35题

2018年上半年

设数组a[1..m,1..n]（m＞1，n＞1）中的元素按行存放，每个元素占用1个存储单元，则数组元素a[i,j]（1≤i≤m，1≤j≤n）相对于数组首元素的偏移量为（）。

第38题

2017年上半年

在C程序中有一个二维数组A[7][8]，每个数组元素用相邻的 8个字节存储，那么存储该数组需要的字节数为（）。

第35题

2012年下半年

设数组a[1..n，1..m] (n>1, m>1)中的元素以行为主序存放，每个元素占用1个存储单元，则数组元素a[i，j] （1≤i≤n,1≤j≤m）相对于数组空间首地址的偏移量为（35）。

知识点讲解

· 数组和矩阵

· 矩阵

· 数组

数组和矩阵

数组的特征

数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但是用不同的下标来访问（引用）。如int a[6]；说明了一个一维整型数组a，其中各个整型元素组成了一个向量：a[0], a[1], a[2], a[3], a[4], a[5]。

数组还可以是多维数组，但二维以上的多维数组不是线性结构。

n维数组是一维数组（向量）的推广。二维数组（也叫矩阵）可看作其元素是一维数组的一维数组（线性表、向量），n维数组可看作其元素是n-1维数组的一维数组（线性表、向量）。n维数组的每个元素处于n个向量中，有n个前驱，也有n个后继。

对二维数组来说，给定维数和下标，如何得到数组元素存储位置？设每个数组占用L个内存单元，则二维数组A_mn按行优先顺序（下标从0开始），a_ij的地址为：

LOC（i, j）=LOC（0, 0）+（i*n+j）*L

二维数组A_mn按列优先顺序（下标从0开始），a_ij的地址为：

LOC（i,j）=LOC（0, 0）+（j*m+i）*L

对n维数组而言，一旦规定了数组的维数和各维的上下界限，便可为它分配存储空间；反之，只要给出一组下标便可求得相应数组元素的存储位置。以行序为例，设每个数据元素占L个存储单元，则n维数组任意元素的存储位置为：

其中，

C_n=L,C_i_-1=b_i×c_i, 1<i≤n

在C语言中，二维数组是按行优先存储的，数组float a[4][5]；的存储顺序为a[0][0], a[0][1], …, a[0][4], …, a[3][0], …, a[3][4], a[2][3]的地址为S+（2×5+3）×4=42，其中S为起始地址。

求解特殊矩阵的压缩存储地址

特殊矩阵是值相同或零元素在矩阵中的分布有一定的规律的矩阵，为了节约空间，常对下列特殊矩阵进行压缩存储。

对n阶对称矩阵或下三角矩阵A而言，如下图所示，如按行将a₁₁,a₂₁,a₂₂,a₃₁,a₃₂, …，a_n₁,a_n₂, …, a_nn存放在某一维数组B[1…（n+1）n/2]中，则某个a_ij（i≥j）在B中的存储位置可通过数列求和得到。由于第i行前共有i-1行，且元素个数分别为1, 2, …,i-1，则前i-1行的元素个数为：

n阶对称矩阵或下三角矩阵A

1+2+3+…+（i-1）=i（i-1）/2

因而，矩阵元素a_ij在B中的存储位置为k=i（i-1）/2+j（i≥j）。

对于三角矩阵，其某个矩阵元素在一维数组中的存储位置可使用此方法类似确定。

由压缩存储地址还原矩阵元素的行和列

若已知某个特殊矩阵的非零元素在一维数组中的存储位置，如何得到该矩阵元素的行和列坐标？下面就以下三角矩阵在一维数组中的存储位置求相应矩阵元素的行和列来加以说明。

对4.2.1.2节中的A和B，若k为某个下三角矩阵元素a_ij在B中的存储位置，则：

i（i-1）/2+j=k

初始化i=1，若i（i-1）/2≤k，则i++，直到i（i-1）/2>k，因而可得到行为i-1，列为k-i（i-1）/2。由k求i和j的算法如下：

稀疏矩阵的三元组存储结构

稀疏矩阵指矩阵中非零元素很少，且分布没有规律。设二维数组A_m_×_n有N个非零元素，N<<m*n，但它不是特殊矩阵（如对角矩阵）。对稀疏矩阵而言，只存储非零元素。用线性表存储稀疏矩阵的非零元素，除非零元素的值外，还应有一些辅助信息。顺序存储节省存储空间，但插入和删除不方便。稀疏矩阵的表示可用三元组[i,j,a_ij]来表示，其中，i、j、a_ij分别表示行列位置和值。由此可见，稀疏矩阵可由表示非零元的三元组和其行列数唯一确定。节点中除元素值外，还有元素所在行、列信息。节点结构如下：

对如下图所示的稀疏矩阵，其三元组表示为（1, 2, 12），（1, 3, 9），（3, 1, -3），（3, 6, 14），（4, 3, 24），（5, 2, 18），（6, 1, 15），（6, 3, -7）。

稀疏矩阵

三元组的C语言描述如下：

可利用三元组表实现矩阵的运算（以行序为主序），如矩阵的转置和矩阵的相乘等。

对于矩阵a_m_×_n转置为b_n_×_m，使a[i, j]=b[j, i]，其中，1≤i≤n, 1≤j≤m，其实现步骤如下。

（1）将矩阵的行、列数互换。

（2）将每个三元组中的i和j互换。

（3）重排三元组之间的次序。

按a.data中三元组的次序进行转置，将转置后的三元组置入b中恰当的位置，如能预先确定M中每一列的第一个非零元在b.data中的相应位置，则转置时可直接放入b.data恰当的位置。先求每一列非零元的个数，设num、cpot两个向量，num[col]表示M中第col列非零元个数，cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。

cpot函数的定义如下：

其实现算法如下：

稀疏矩阵的十字链表

链式存储可方便插入与删除。十字链表为每行和每列的非零元链成循环链表，每个非零元用一个节点表示，其形式如下图所示。

十字链表

i、j分别表示该数组某非零元素的行、列值，e表示该非零元素的值。down指向该行的下一行具有相同列的非零元素，right指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。

十字链表节点结构和头节点的数据结构可定义如下：

矩阵

矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。

在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。

特殊矩阵

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。

若矩阵A_n_×_n中的元素有a_ij=a_ji（1≤i，j≤n）的特点，则称之为对称矩阵。

若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n²个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素a_ij（a_ji）之间存在着一一对应的关系。

对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。

三对角矩阵示意图

若以行为主序将n阶三对角矩阵A_n_×_n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：

k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）

其他特殊矩阵可作类似的推导和计算，这里不再一一说明。

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。

对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，a_ij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。

一个6行7列的稀疏矩阵如下图所示，其三元组表为（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。

稀疏矩阵示意图

稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。

数组

数组的定义及基本运算

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

设有n维数组A［b₁，b₂，…，b_n］，其每一维的下界都为1，b_i是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j₁，j₂，…，j_n］（1≤j_i≤b_i）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。

以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。

可将A看作一个行向量形式的线性表：

A_m_*_n=［［a₁₁a₁₂…a₁_n］［a₂₁a₂₂…a_2n］…［a_m₁a_m₂…a_mn］］

也可将A看作列向量形式的线性表：

A_m_*_n=［［a₁₁a₂₁…a_m₁］［a₁₂a₂₂…a_m₂］…［a₁_na₂_n…a_mn］］

数组结构的特点如下：

（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。

（2）数据元素具有相同的类型。

（3）数据元素的下标关系具有上下界的约束且下标有序。

在数组中通常做下面两种操作：

（1）取值操作。给定一组下标，读其对应的数据元素。

（2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。

几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。

数组的顺序存储

由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。

二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。

二维数组的两种存储方式

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（i-1）×n+（j-1））×L

同理，以列为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（j-l）×m+（i-1））×L

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5