第5章数组和稀疏矩阵

1、第第5章章 数组和稀疏矩阵数组和稀疏矩阵 5.1 数数 组组5.1.1 数组的定义数组的定义一维数组是一维数组是n（n1）个相同类型的数据元素）个相同类型的数据元素a1，a2，an构成的有限序列，它本身就是一个线性表。二维数组可以看构成的有限序列，它本身就是一个线性表。二维数组可以看成是这样的一个定长线性表，它的每个数据元素也是一个定长成是这样的一个定长线性表，它的每个数据元素也是一个定长线性表。线性表。例如，以下的二维数组例如，以下的二维数组A以以m行行n列的矩阵形式表示，它可列的矩阵形式表示，它可以看成是一个线性表的线性表：以看成是一个线性表的线性表：a.aa.a.aaa.aaAm,nm,

2、m,n,n,nm212221212111几乎所有的程序设计语言都把数组类型设定为固有类型，几乎所有的程序设计语言都把数组类型设定为固有类型，数组一旦被定义，它的维数和每维大小就不再改变，其主要数组一旦被定义，它的维数和每维大小就不再改变，其主要的基本运算是存取元素值和修改元素值。的基本运算是存取元素值和修改元素值。5.1.2 数组的存储结构数组的存储结构以二维数组为例，在以二维数组为例，在C/C+语言中，由于数组下标从语言中，由于数组下标从0开开始，所以除特别指出外，后面的数组表示均统一为下标从始，所以除特别指出外，后面的数组表示均统一为下标从0开始。开始。 二维数组的存储次序有按行优先和按列

3、优先两种方式，二维数组的存储次序有按行优先和按列优先两种方式，按行优先存储的形式如下所示：按行优先存储的形式如下所示：假设每个元素占假设每个元素占k个存储单元，个存储单元，LOC(a0,0)表示表示a0,0元素元素的存储地址，对于元素的存储地址，对于元素ai,j，其存储地址为：，其存储地址为： 按列优先存储的形式如下所示：按列优先存储的形式如下所示：对于元素对于元素ai,j，其存储地址为：，其存储地址为： 【例【例5.1】 对于二维数组对于二维数组A0.20.5，当按行优先存储时，当按行优先存储时，元素元素A23是第几个元素；当按列优先存储时，元素是第几个元素；当按列优先存储时，元素A24是第

4、几个元素。是第几个元素。解：解：这里这里m=3，n=6，当按行优先存储时，元素，当按行优先存储时，元素A23的的前面有前面有2行计行计12个元素，在第个元素，在第2行中前面有行中前面有3个元素，所以元素个元素，所以元素A23是是12+3+1=16个元素。个元素。当按列优先存储时，元素当按列优先存储时，元素A24的前面有的前面有4列计列计12个元素，个元素，在第在第4列中前面有列中前面有2个元素，所以元素个元素，所以元素A24是是12+2+1=15个个元素。元素。5.1.3 数组的应用示例数组的应用示例【例【例5.2】 设计一个算法，实现一个设计一个算法，实现一个mn的整型数组的整型数组A的转置

5、运算。的转置运算。解：解：对于一个对于一个mn的数组的数组Amn，其转置矩阵是一个，其转置矩阵是一个nm的矩阵的矩阵Bnm，且，且Bij=Aji，0im，0jn，对应的，对应的算法如下：算法如下：void TransMat(int AMAX, int BMAX,int m,int n) int i,j;for (i=0;im;i+)for (j=0;jn;j+)Bji=Aij;4.2 特殊矩阵的压缩存储特殊矩阵的压缩存储二维数组也称为矩阵，特殊矩阵是指非零元素或零元素二维数组也称为矩阵，特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵的分布有一定规律的矩阵.为了节省存储空间，特别是在高阶矩阵

6、的情况下，可以为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储。利用特殊矩阵的规律，对它们进行压缩存储。 一个一个n阶方阵的元素可以分为主对角线、上三角和下三阶方阵的元素可以分为主对角线、上三角和下三角部分角部分 1. 对称矩阵的压缩存储对称矩阵的压缩存储若一个若一个n阶方阵阶方阵Ann的元素满足的元素满足ai,j=aj,i（0i，jn-1），则），则称其为称其为n阶对称矩阵阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此在存储时可由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角或下三角中的元素，使得对称的元素共只存储对称矩

7、阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。这样，就可以将享一个存储空间。这样，就可以将n2个元素压缩存储到个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，以行序为主序存储其下三角（包个元素的空间中。不失一般性，以行序为主序存储其下三角（包括对角线）的元素，如以图所示。括对角线）的元素，如以图所示。则则A中任一元素中任一元素ai,j和和bk之间存在着如下对应关系：之间存在着如下对应关系： 2. 三角矩阵的压缩存储三角矩阵的压缩存储有些非对称的矩阵也可借用此方法存储，如有些非对称的矩阵也可借用此方法存储，如n阶下（上）三阶下（上）三角矩阵。所谓角矩阵。所谓n阶下（上）

8、三角矩阵，是指矩阵的上（下）三角阶下（上）三角矩阵，是指矩阵的上（下）三角（不包括对角线）中的元素均为常数（不包括对角线）中的元素均为常数c或或0的的n阶方阵。设以一维阶方阵。设以一维数组数组B0.n(n+1)/2作为作为n阶三角矩阵阶三角矩阵A的存储结构，则的存储结构，则A中任一元中任一元素素ai,j和和B中元素中元素bk之间存在着如下对应关系：之间存在着如下对应关系： 上三角矩阵：上三角矩阵：下三角矩阵：下三角矩阵：其中，其中，B的元素的元素bn(n+1)/2中存放常数中存放常数c。3. 对角矩阵的压缩存储对角矩阵的压缩存储若一个若一个n阶方阵阶方阵A满足其所有非零元素都集中在以主对满足其

9、所有非零元素都集中在以主对角线为中心的带状区域中，则称其为角线为中心的带状区域中，则称其为n阶对角矩阵。其主对阶对角矩阵。其主对角线上下方各有角线上下方各有b条次对角线，称条次对角线，称b为矩阵半带宽为矩阵半带宽 。对于对于b=1的三对角矩阵的三对角矩阵A，只存储其非零元素，并按行，只存储其非零元素，并按行优先存储到一维数组优先存储到一维数组B中，将中，将A的非零元素的非零元素ai,j存储到存储到B的元的元素素bk中：中： k=2i+j 5.3 稀稀 疏疏 矩矩 阵阵一个阶数较大的矩阵中的非零元素个数一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素相对于矩阵元素的总个数的总个数t十分小时，即

10、十分小时，即st时，称该矩阵为时，称该矩阵为稀疏矩阵稀疏矩阵。例如一个例如一个100100的矩阵，若其中只有的矩阵，若其中只有100个非零元素，个非零元素，就可称其为稀疏矩阵。就可称其为稀疏矩阵。稀疏矩阵的压缩存储方法是只存储非零元素，主要有三稀疏矩阵的压缩存储方法是只存储非零元素，主要有三元组和十字链表两种方法。元组和十字链表两种方法。5.3.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示由于稀疏矩阵中非零元素的分布没有任何规律，所以在由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时还必须同时存储该非零元素所对应的行下标存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标

11、。和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组这样稀疏矩阵中的每一个非零元素需由一个三元组（i,j,ai,j）唯一确定，稀疏矩阵中的所有非零元素构成三元组）唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表。线性表。 (0,2,1)，(1,1,2)，(2,0,3)，(3,3,5)，(4,4,6)，(5,5,7)，(5,6,4) 47000000060000000500000000030000020000010076A三元组顺序表的数据结构可定义如下：三元组顺序表的数据结构可定义如下： #define MaxSize 100/矩阵中非零元素的最多个数矩阵中非零元素的最多个数typede

12、f struct int r;/行号行号int c;/列号列号ElemType d;/元素值为元素值为ElemType类型类型 TupNode;/三元组定义三元组定义typedef struct int rows;/行数行数int cols;/列数列数int nums;/非零元素个数非零元素个数TupNode dataMaxSize; TSMatrix;/三元组顺序表定义三元组顺序表定义稀疏矩阵运算通常包括矩阵转置、矩阵加、矩阵减、矩稀疏矩阵运算通常包括矩阵转置、矩阵加、矩阵减、矩阵乘等。这里仅讨论基本运算和矩阵转置运算算法。阵乘等。这里仅讨论基本运算和矩阵转置运算算法。（1）从一个二维稀疏矩

13、阵创建其三元组表示）从一个二维稀疏矩阵创建其三元组表示以行序方式扫描二维稀疏矩阵以行序方式扫描二维稀疏矩阵A，将其非零的元素插入，将其非零的元素插入到三元组到三元组t中。中。 void CreatMat(TSMatrix &t,ElemType AMN) int i,j;t.rows=M;t.cols=N;t.nums=0;for (i=0;iM;i+)for (j=0;j=t.rows | j=t.cols) return 0;/参数错误时返回参数错误时返回0while (kt.datak.r) k+; /查找行查找行while (kt.datak.c) k+; /查找列查找列if

14、(t.datak.r=i & t.datak.c=j) /存在这样的元素存在这样的元素t.datak.d=x;else/不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素for (k1=t.nums-1;k1=k;k1-) t.datak1+1.r=t.datak1.r;t.datak1+1.c=t.datak1.c;t.datak1+1.d=t.datak1.d;t.datak.r=i; t.datak.c=j; t.datak.d=x; t.nums+;return 1;/成功时返回成功时返回1（3）将指定位置的元素值赋给变量）将指定位置的元素值赋给变量对于稀疏矩阵对于稀

15、疏矩阵A，执行执行x=Aij。先在三元组。先在三元组t中找到指定中找到指定的位置，将该处的元素值赋给的位置，将该处的元素值赋给x。 int Assign(TSMatrix t,ElemType &x,int i,int j) int k=0;if (i=t.rows | j=t.cols)return 0;/参数错误时返回参数错误时返回0while (kt.datak.r) k+; /查找行查找行while (kt.datak.c) k+;/查找列查找列if (t.datak.r=i & t.datak.c=j)x=t.datak.d;elsex=0;/在三元组中没有找到表示是

16、零元素在三元组中没有找到表示是零元素return 1;/成功时返回成功时返回1（4）输出三元组运算算法）输出三元组运算算法从头到尾扫描三元组从头到尾扫描三元组t，依次输出元素值。，依次输出元素值。 void DispMat(TSMatrix t) int i;if (t.nums=0)/没有非零元素时返回没有非零元素时返回return;printf(t%dt%dt%dn,t.rows,t.cols,t.nums);printf(t-n);for (i=0;it.nums;i+)printf(t%dt%dt%dn,t.datai.r,t.datai.c,t.datai.d);（5）矩阵转置运算算

17、法）矩阵转置运算算法对于一个对于一个mn的矩阵的矩阵Amn，其转置矩阵是一个，其转置矩阵是一个nm的矩的矩阵。设为阵。设为Bnm，满足，满足bi,j=aj,i，其中，其中0im-1，0jn-1。 void TranTat(TSMatrix t,TSMatrix &tb) int p,q=0,v;/q为为tb.data的下标的下标tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if (t.nums!=0)/当存在非零元素时执行转置当存在非零元素时执行转置for (v=0;vt.cols;v+)/tb.dataq中的记录以中的记录以c域的次序排列域

18、的次序排列for (p=0;pt.nums;p+)/p为为t.data的下标的下标if (t.datap.c=v) tb.dataq.r=t.datap.c;tb.dataq.c=t.datap.r;tb.dataq.d=t.datap.d;q+;【例【例5.4】 采用三元组存储稀疏矩阵，设计两个稀疏矩阵采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法。相加的运算算法。解：解：实现相加运算的两个稀疏矩阵实现相加运算的两个稀疏矩阵a和和b的行数、列数都的行数、列数都必须相同。用必须相同。用i和和j两个变量分别遍历三元组两个变量分别遍历三元组a和和b，按行序优先，按行序优先方式进行处理，并将

19、结果存放在三元组方式进行处理，并将结果存放在三元组c中。中。当当a的当前元素和的当前元素和b的当前元素的行号、列号均相等时，的当前元素的行号、列号均相等时，将它们的值相加，只有在相加值不为将它们的值相加，只有在相加值不为0时，才在时，才在c中添加一个中添加一个新的元素表示相加后的结果。新的元素表示相加后的结果。 int MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c) int i=0,j=0,k=0;ElemType v;if (a.rows!=b.rows | a.cols!=b.cols)return 0;/行数或列数不等时不能进行相加运算行数或列数不等时不能进行相加运算c.rows=a.rows;c.cols=a.cols;/c的行列数与的行列数与a的相同的相同while (ia.nums