数组和稀疏矩阵

1、第第5 5章章 数组和稀疏矩阵数组和稀疏矩阵 5.1 5.1 数组数组5.2 5.2 稀疏矩阵稀疏矩阵本章小结本章小结5.1.1 5.1.1 数组的基本概念数组的基本概念 数组数组是是n(n1)个个相同类型相同类型数据元素数据元素a1,a2,an构构成的有限序列成的有限序列,且该有限序列存储在一块且该有限序列存储在一块地址连续地址连续的的内存单元中。内存单元中。 由此可见由此可见,数组的定义类似于数组的定义类似于采用顺序存储结构采用顺序存储结构的线性表的线性表。数组具有以下数组具有以下性质性质： (1)数组中的数据元素数组中的数据元素数目固定数目固定。一旦定义了一。一旦定义了一个数组个数组,其

2、数据元素数目不再有增减变化。其数据元素数目不再有增减变化。 (2)数组中的数据元素具有数组中的数据元素具有相同的数据类型相同的数据类型。 (3)数组中的每个数据元素都和一组数组中的每个数据元素都和一组惟一的下标惟一的下标值对应。值对应。 (4)数组是一种随机存储结构。数组是一种随机存储结构。可随机存取可随机存取数组数组中的任意数据元素。中的任意数据元素。5.1.2 5.1.2 数组的存储结构数组的存储结构 在在一维数组一维数组中中,一旦一旦a1的存储地址的存储地址LOC(a1)确定确定,并并假设每个数据元素占用假设每个数据元素占用k个存储单元个存储单元,则任一数据元素则任一数据元素ai的存储地

3、址的存储地址LOC(ai)就可由以下公式求出：就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in) 上式说明上式说明,一维数组中任一数据元素的存储地址可一维数组中任一数据元素的存储地址可直接计算得到直接计算得到,即一维数组中任一数据元素可直接存即一维数组中任一数据元素可直接存取取,因此因此,一维数组是一种一维数组是一种随机存储结构随机存储结构。 nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1对于一个对于一个m m行行n n列的列的二维数组二维数组A Am mn n, ,有：有： 将将Am*n简记为简记为A, A是这样的一维数

4、组：是这样的一维数组： A=(a1,a2,ai,am) 其中其中, ai=(ai,1,ai,2,ai,n) (1jm)。 显然显然,二维数组二维数组同样满足数组的定义。一个同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类二维数组可以看作是每个数据元素都是相同类型的型的一维数组的一维数组一维数组的一维数组。 以此类推以此类推,任何任何多维数组多维数组都可以看作一个都可以看作一个线线性表性表,这时线性表中的每个数据元素也是一个线这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。性表。多维数组是线性表的推广。多维数组是多维数组是特殊的一维数组。特殊的一维数组。二位数组

5、的存储结构：二位数组的存储结构： 对于二维数组来说对于二维数组来说,由于计算机的存储结构是线由于计算机的存储结构是线性的性的,如何如何用线性的存储结构存放二维数组用线性的存储结构存放二维数组元素就元素就有一个有一个行列次序排放行列次序排放问题。问题。 以以行序为主序行序为主序的存储方式：即先存储第的存储方式：即先存储第1行行,然然后紧接着存储第后紧接着存储第2行行,最后存储第最后存储第m行。此时行。此时,二维数二维数组的线性排列次序为：组的线性排列次序为： a1,1,a1,2,a1,n,a2,1,a2,2,a2,n,am,1,am,2,am,n 对一个已知对一个已知以行序为主序以行序为主序的计

6、算机系统中的计算机系统中,当二当二维数组第一个数据元素维数组第一个数据元素a1,1的存储地址的存储地址LOC(a1,1)和每和每个数据元素所占用的存储单元个数据元素所占用的存储单元k确定后确定后, 则该二维数则该二维数组中任一数据元素组中任一数据元素ai,j的存储地址的存储地址可由下式确定：可由下式确定： LOC(ai,j)=LOC(a1,1)+(i-1)*n+(j-1)*k 其中其中n为列数。为列数。 同理可推出在同理可推出在以列序为主序以列序为主序的计算机系统中的计算机系统中有：有： LOC(ai,j)=LOC(a1,1)+(j-1)*m+(i-1)*k其中其中m为行数。为行数。思考：对多

7、维数组思考：对多维数组ArrayK1K2Kn，如何求，如何求出任意成员出任意成员Arrayi1i2in的偏移量的偏移量? i1*K2*K3*Kn+ i2*K3*Kn+ in-1*Kn+ in结论：多维数组同样能够实现结论：多维数组同样能够实现随机访问随机访问 例例5.1 对二维数组对二维数组float a54计算：计算： (1)数组数组a中的数组元素数目；中的数组元素数目； (2)若数组若数组a的起始地址为的起始地址为2000,且每个数组元素长且每个数组元素长度为度为32位位(即即4个字节个字节),数组元素数组元素a32的内存地址。的内存地址。 解：由于解：由于C语言中数组的行、列下界均为语言

8、中数组的行、列下界均为0,该数组行上界为该数组行上界为5-1=4,列上界为列上界为4-l=3,该数组的该数组的元素数目共有元素数目共有5*4=20个。个。 又由于又由于C语言采用语言采用行序为主序行序为主序的存储方式的存储方式,则有：则有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056 例例5.2 按行优先顺序和按列优先顺序列按行优先顺序和按列优先顺序列出四维数组出四维数组A2222所有元素在内存中所有元素在内存中的存储次序。的存储次序。 解：解： 按行优先的存储次序按行优先的存储次序: A0000, A0001, A0010, A001

9、1, A0100, A0101, A0110, A0111, A1000, A1001, A1010, A1011, A1100, A1101, A1110, A1111 按列优先的存储次序按列优先的存储次序: : A0000, A1000, A0100, A1100, A0010, A1010, A0110, A1110, A0001, A1001, A0101, A1101, A0011, A1011, A0111, A1111 例例5.3 对于二维数组对于二维数组Amn,其中其中m80,n80,先先读入读入m和和n,然后读该数组的全部元素然后读该数组的全部元素,对如三种情对如三种情况分别

10、编写相应函数况分别编写相应函数: (1)求数组求数组A靠边元素之和靠边元素之和; (2)当当m=n时时,分别求两条对角线上的元素之和分别求两条对角线上的元素之和,否则打印出否则打印出mn的信息。的信息。 解：解： (1)对应算法如下：对应算法如下： void proc1(ElemType An) int s=0,i,j;for (j=0;jn;j+) /*第一行和最后一行第一行和最后一行*/ s=s+A0j; s=s+Am-1j; for (i=1;im-1;i+) /*第一列和最后一列第一列和最后一列*/ s=s+Ai0; s=s+Ain-1;printf(s=%dn,s); (2)对应算法

11、如下：对应算法如下： void proc2(maxix A) int i, s=0; if (m!=n) printf(mn); else for (i=0;in;i+) s=s+Aii; /*求第一条对角线之和求第一条对角线之和*/s=s+An-i-1i; /*第二条对角线之和第二条对角线之和*/ if (n%2) s-=An/2n/2; /*去掉交叉点去掉交叉点*/ printf(s=%dn,s); 5.1.3 5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵是指特殊矩阵是指非零元素或零元素的分布有一定规非零元素或零元素的分布有一定规律律的矩阵的矩阵,为了为了节省存储空间节省存储

12、空间,特别是在高阶矩阵的情特别是在高阶矩阵的情况下况下,可以利用特殊矩阵的规律可以利用特殊矩阵的规律,对它们进行压缩存储对它们进行压缩存储,也就是说也就是说,使使多个相同的多个相同的非零元素非零元素共享同一个存储单共享同一个存储单元元,对对零元素零元素不分配存储空间。不分配存储空间。 特殊矩阵的主要形式有特殊矩阵的主要形式有对称矩阵对称矩阵、对角矩阵对角矩阵等等 它们都是它们都是方阵方阵,即行数和列数相同。即行数和列数相同。 1. 对称矩阵的压缩存储对称矩阵的压缩存储 若 一 个若 一 个 n 阶 方 阵阶 方 阵 A n n 中 的 元 素 满 足中 的 元 素 满 足ai,j=aj,i(0

13、i,jn-1), 则称其为则称其为n阶阶对称矩阵对称矩阵。 由于对称矩阵中的元素由于对称矩阵中的元素关于主对角线对称关于主对角线对称,因此因此在存储时可只存储对称矩阵中上三角或下三角中的在存储时可只存储对称矩阵中上三角或下三角中的元素元素,使得对称的元素共享一个存储空间使得对称的元素共享一个存储空间。 这样这样,就可以将就可以将n2个元素压缩存储到个元素压缩存储到(1+2+n)个元素的空间中。不失一般性个元素的空间中。不失一般性,我们以我们以行序为主序行序为主序存储其存储其下三角下三角(包括对角线包括对角线)的元素。的元素。 n2个元素个元素 n(n+1)/2个元素个元素A0.n-1,0.n-

14、1 B0,1,.,n(n+1)/2-1 aij bk21)i(i k=+ j ij+ i ij21)j(j 2. 对角矩阵的压缩存储对角矩阵的压缩存储 若一个若一个n阶方阵阶方阵A满足其满足其所有非零元素所有非零元素都集中在都集中在以主对角线为中心的带状区域以主对角线为中心的带状区域中中,则称其为则称其为n阶对角阶对角矩阵矩阵。 其主对角线上下方各有其主对角线上下方各有b条次对角线条次对角线,称称b为矩阵为矩阵半带宽半带宽,(2b+1)为矩阵的为矩阵的带宽带宽。 对于半带宽为对于半带宽为b(0b(n-1)/2)的对角矩阵的对角矩阵, 其其|i-j|b的元素的元素ai,j不为零不为零,其余元素为

15、零。其余元素为零。 . b条 b条 0 0 . 半带宽为半带宽为b b的对角矩阵的对角矩阵 当当b1时称为时称为三对角矩阵三对角矩阵。其压缩地址计算公式如下：其压缩地址计算公式如下： k=(3i-1)+(j-i+2)-1=2i+j A B aij bk5.2 5.2 稀疏矩阵稀疏矩阵 一个阶数较大的矩阵中的一个阶数较大的矩阵中的非零元素个数非零元素个数s相对相对于矩阵元素的总个数于矩阵元素的总个数t十分小时十分小时,即即st时时,称该矩称该矩阵为稀疏矩阵。例如一个阵为稀疏矩阵。例如一个100100的矩阵的矩阵,若其中若其中只有只有100个非零元素个非零元素,就可称其为就可称其为稀疏矩阵稀疏矩阵

16、。5.2.1 5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 稀疏矩阵的压缩存储方法是稀疏矩阵的压缩存储方法是只存储非零元素只存储非零元素。 由于稀疏矩阵中非零元素的由于稀疏矩阵中非零元素的分布没有任何规律分布没有任何规律,所所以在存储非零元素时还必须同时存储该非零元素所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素需由一个非零元素需由一个三元组三元组(i,j,ai,j)惟一确定惟一确定,稀疏矩阵稀疏矩阵中的所有非零元素构成三元组线性表。中的所有非零元素构成三元组线性表。 假设有一个假设有一个6

17、7阶稀疏矩阵阶稀疏矩阵A(为图示方便为图示方便,我我们所取的行列数都很小们所取的行列数都很小), A中元素如下图所示。则中元素如下图所示。则对应的三元组线性表为：对应的三元组线性表为： (0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4)47000000060000000500000000030000020000010076A一个稀疏矩阵一个稀疏矩阵A A 若把稀疏矩阵的三元组线性表按顺序存储结若把稀疏矩阵的三元组线性表按顺序存储结构存储构存储, ,则称为则称为稀疏矩阵的三元组顺序表稀疏矩阵的三元组顺序表。则三。则三元组顺序表的数据结

18、构可定义如下：元组顺序表的数据结构可定义如下： #define MaxSize 100 /*矩阵中非零元素最多个数矩阵中非零元素最多个数*/ typedef struct int r; /*行号行号*/ int c; /*列号列号*/ ElemType d; /*元素值元素值*/ TupNode; /*三元组定义三元组定义*/ typedef struct int rows; /*行数值行数值*/ int cols; /*列数值列数值*/ int nums; /*非零元素个数非零元素个数*/ TupNode dataMaxSize; TSMatrix; /*三元组顺序表定义三元组顺序表定义*/

19、 其中其中,data域中表示的非零元素，通常域中表示的非零元素，通常以行序以行序为主序为主序顺序排列，它是一种顺序排列，它是一种下标按行有序下标按行有序的存储的存储结构。这种有序存储结构可简化大多数矩阵运算结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设算法。下面的讨论假设data域按行有序存储。域按行有序存储。 (1)从一个二维矩阵创建其三元组表示从一个二维矩阵创建其三元组表示 以行序方式扫描二维矩阵以行序方式扫描二维矩阵A,将其非零的元素插入到将其非零的元素插入到三元组三元组t的后面。算法如下：的后面。算法如下： void CreatMat(TSMatrix &t,E

20、lemType AMN) int i,j; t.rows=M;t.cols=N;t.nums=0; for (i=0;iM;i+) for (j=0;j=t.rows | cs=t.cols) return 0; while (kt.datak.r) k+;/*查找行查找行*/ while (kt.datak.c) k+;/*查找列查找列*/ if (t.datak.r=rs & t.datak.c=cs) /*存在这样的元素存在这样的元素*/ t.datak.d=x; else /*不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素*/ for (i=t.nums-1;ik

21、;i-) /*元素后移元素后移*/ t.datai+1.r=t.datai.r; t.datai+1.c=t.datai.c; t.datai+1.d=t.datai.d; t.datak.r=rs;t.datak.c=cs;t.datak.d=x; t.nums+; return 1; (3)将指定位置的元素值赋给变量将指定位置的元素值赋给变量 先在三元组先在三元组t中找到指定的位置中找到指定的位置,将该处的元素值将该处的元素值赋给赋给x。算法如下：。算法如下： int Assign(TSMatrix t,ElemType &x,int rs,int cs) int k=0; if

22、(rs=t.rows | cs=t.cols) return 0; while (kt.datak.r) k+; while (kt.datak.c) k+; if (t.datak.r=rs & t.datak.c=cs) x=t.datak.d; return 1; else return 0; (4)输出三元组输出三元组 从头到尾扫描三元组从头到尾扫描三元组t,依次输出元素值。算法如下：依次输出元素值。算法如下： void DispMat(TSMatrix t) int i; if (t.nums=0) return;printf(“t%dt%dt%dn,t.rows,t.col

23、s,t.nums); printf( -n); for (i=0;it.nums;i+)printf(t%dt%dt%dn,t.datai.r,t.datai.c, t.datai.d); (5)矩阵转置矩阵转置 对于一个对于一个mn的矩阵的矩阵Amn,其转置矩阵是一个其转置矩阵是一个nm的矩阵。设为的矩阵。设为Bn m,满足满足ai , j=bj , i,其中其中1im,1jn。其完整的转置算法如下：。其完整的转置算法如下： 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+) 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+; 以上算法的时间复杂度为以上算