|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
稀疏矩阵指矩阵中非零元素很少，且分布没有规律。设二维数组Am×n有N个非零元素，N<<m*n，但它不是特殊矩阵（如对角矩阵）。对稀疏矩阵而言，只存储非零元素。用线性表存储稀疏矩阵的非零元素，除非零元素的值外，还应有一些辅助信息。顺序存储节省存储空间，但插入和删除不方便。稀疏矩阵的表示可用三元组[i,j,aij]来表示，其中，i、j、aij分别表示行列位置和值。由此可见，稀疏矩阵可由表示非零元的三元组和其行列数唯一确定。节点中除元素值外，还有元素所在行、列信息。节点结构如下：
|
|
|
|
|
|
对如下图所示的稀疏矩阵，其三元组表示为（1, 2, 12），（1, 3, 9），（3, 1, -3），（3, 6, 14），（4, 3, 24），（5, 2, 18），（6, 1, 15），（6, 3, -7）。
|
|
|
|
|
|
|
|
|
|
|
|
可利用三元组表实现矩阵的运算（以行序为主序），如矩阵的转置和矩阵的相乘等。
|
|
|
|
对于矩阵am×n转置为bn×m，使a[i, j]=b[j, i]，其中，1≤i≤n, 1≤j≤m，其实现步骤如下。
|
|
|
|
|
|
|
|
|
|
按a.data中三元组的次序进行转置，将转置后的三元组置入b中恰当的位置，如能预先确定M中每一列的第一个非零元在b.data中的相应位置，则转置时可直接放入b.data恰当的位置。先求每一列非零元的个数，设num、cpot两个向量，num[col]表示M中第col列非零元个数，cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。
|
|
|
|
在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。
|
|
|
|
|
|
常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
|
|
|
|
若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。
|
|
|
|
若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n2个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素aij（aji）之间存在着一一对应的关系。
|
|
|
|
|
|
对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
|
|
|
|
|
|
|
|
若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：
|
|
|
|
k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）
|
|
|
|
其他特殊矩阵可作类似的推导和计算，这里不再一一说明。
|
|
|
|
|
|
在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。
|
|
|
|
对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，aij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
|
|
|
|
一个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［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
|
|
|
|
以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
|
|
|
|
|
|
|
|
Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
|
|
|
|
|
|
Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
|
|
|
|
|
|
（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
|
|
|
|
|
|
（3）数据元素的下标关系具有上下界的约束且下标有序。
|
|
|
|
|
|
（1）取值操作。给定一组下标，读其对应的数据元素。
|
|
|
|
（2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
|
|
|
|
几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
|
|
|
|
|
|
由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
|
|
|
|
对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
|
|
|
|
二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
|
|
|
|
|
|
|
|
设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
|
|
|
|
Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
|
|
|
|
|
|
Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
