若二维数组arr[1..8，1..6]的首地址为base，数组元素按列存储，且每个元素占用4个存储..

免费智能真题库 > 历年试卷 > 程序员 > 2011年上半年程序员上午试卷综合知识

第36题

知识点：数组和矩阵列存储数组

关键词：存储单元二维数组数组章/节：常用数据结构

若二维数组arr[1..8，1..6]的首地址为base，数组元素按列存储，且每个元素占用4个存储单元，则元素arr[5, 5]在该数组空间的地址为（36)。

A. base+(4*8+4)*4

B. base+(5*8+5)*4

C. base+(4*6+4)*4

D. base+(5*6+5)*4

相关试题：数组

更多>

第38题 2017年上半年

34%

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

第35题 2013年下半年

63%

设数组a[1..n，1..m](n>1,m>1)中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素a[i，j](1≤i≤n, 相对于..

第40题 2009年上半年

33%

已知对称矩阵A_n*_n (A_i,j=A_j,i)的主对角线元素全部为0,若用一维数组B仅存储矩阵A的..


知识点讲解
· 数组和矩阵 · 列存储 · 数组

数组和矩阵

数组的特征

数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但是用不同的下标来访问（引用）。如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指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。

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

列存储

传统的关系型数据库都是以行为单位来进行数据的存储的，擅长进行以行为单位的数据处理，比如特定条件数据的获取。因此，关系型数据库也被称为面向行的数据库。相反，面向列的数据库是以列作为单位来进行数据的存储的，擅长进行以列为单位的数据处理。下表所示为面向行和面向列的数据库的比较。

面向行和面向列的数据库比较

面向列的数据库具有高扩展性，即使数据增加也不会降低相应的处理速度，所有它主要应用于需要处理大量数据的情况。另外，利用面向列的数据库的优势，把它作为批处理程序的存储器来对大量数据进行更新也是非常有用的。

列存储数据库，主要产品有Google的Bigtable、由Bigtable衍生的Hypertable和HBase、Cassandra这几个数据库。

数组

数组的定义及基本运算

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。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

题号导航 2011年上半年程序员上午试卷综合知识

本试卷我的完整做题情况



	第36题在手机中做本题