软考中级-数据库-3.2 数据结构-数组和矩阵

 

数组

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

例如一维数组a[5]=[a1,a2,a3,a4,a5]

二维数组a[2][3]是一个2行2列的数组

第一行[a11,a12,a13]

第二行[a21,a22,a23]

• 由于数组一般不做插入和删除，且元素个数和元素之间的关系不再发生变动，那么数组适合采用顺序存储结构。
• 数组元素的存储方式及相关计算：

二维数组的存储结构可分为以行为主序(按行存储)和以列为主序（按列存储)两种方法。

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

以列为主序优先存储的地址计算公式为:

矩阵

• 这里主要讨论一些特殊矩阵的压缩存储的问题。
• 对多个值相同的元素可以只分配一个存储单元，零元素不分配存储单元。

下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。

(1)对称矩阵

(2)三对角矩阵

• 对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，其余的矩阵元素都为零。
• 下面主要考虑三对角矩阵，即只有主对角线及其左右两边为非零元素。
• 

 

(3)稀疏矩阵

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