数组和稀疏矩阵精品文稿.ppt

《数组和稀疏矩阵精品文稿.ppt》由会员分享，可在线阅读，更多相关《数组和稀疏矩阵精品文稿.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、以下公式求出：就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*k(0in)上上式式说说明明,一一维维数数组组中中任任一一数数据据元元素素的的存存储储地地址址可可直直接接计计算算得得到到,即即一一维维数数组组中中任任一一数数据据元元素素可可直直接接存存取取,因因此此,一一维维数数组组是是一一种种随随机机存存储储结结构构。同同样样,二二维维及及多多维维数数组也满足随机存储特性。组也满足随机存储特性。第4页，本讲稿共48页对于一个对于一个m m行行n n列的二维数组列的二维数组A Amnmn,有：有：将将Am*n简记为简记为A,A是这样的一维数组：是这样的一维数组：A=(a1,a2,

4、ai,am)其中其中,ai=(ai,1,ai,2,ai,n)(1jm)。第5页，本讲稿共48页 显显然然,二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组的的一一维维数数组组。以以此此类类推推,任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表,这这时时线线性性表表中中的的每每个个数数据据元元素素也也是是一一个个线性表。多维数组是线性表的推广。线性表。多维数组是线性表的推广。第6页，本讲稿共48页 对对于于二二维维数数组组来来说说,由由于于计计算算机机的的存存储储

5、结结构构是是线线性性的的,如如何何用用线线性性的的存存储储结结构构存存放放二二维维数数组组元元素素就就有有一一个个行列次序排放问题。行列次序排放问题。以以行行序序为为主主序序的的存存储储方方式式：即即先先存存储储第第1行行,然然后后紧紧接接着着存存储储第第2行行,最最后后存存储储第第m行行。此此时时,二二维维数数组组的的线线性性排排列列次次序为：序为：a1,1,a1,2,a1,n,a2,1,a2,2,a2,n,am,1,am,2,am,n第7页，本讲稿共48页 对对一一个个已已知知以以行行序序为为主主序序的的计计算算机机系系统统中中,当当二二维维数数组组第第一一个个数数据据元元素素a1,1的的

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

7、：计算：(1)数组数组a中的数组元素数目；中的数组元素数目；(2)若若数数组组a的的起起始始地地址址为为2000,且且每每个个数数组组元元素素长长度度为为32位位(即即4个字节个字节),数组元素数组元素a32的内存地址。的内存地址。第10页，本讲稿共48页 解解：由由于于C语语言言中中数数组组的的行行、列列下下界界均均为为0,该该数数组组行行上上界界为为5-1=4,列列上上界界为为4-l=3,所所以以该该数数组组的的元元素数目共有素数目共有(4-0+1)*(3-0+1)=5*4=20个。个。又由于又由于C语言采用行序为主序的存储方式语言采用行序为主序的存储方式,则有：则有：LOC(a3,2)=

8、LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056第11页，本讲稿共48页5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特特殊殊矩矩阵阵是是指指非非零零元元素素或或零零元元素素的的分分布布有有一一定定规规律律的的矩矩阵阵,为为了了节节省省存存储储空空间间,特特别别是是在在高高阶阶矩矩阵阵的的情情况况下下,可可以以利利用用特特殊殊矩矩阵阵的的规规律律,对对它它们们进进行行压压缩缩存存储储,也也就就是是说说,使使多多个个相相同同的的非非零零元元素素共共享享同同一一个个存存储储单单元元,对零元素不分配存储空间。对零元素不分配存储空间。特特殊殊矩矩阵阵的的主主要要形形

9、式式有有对对称称矩矩阵阵、对对角角矩矩阵阵等等,它它们们都是方阵都是方阵,即行数和列数相同。即行数和列数相同。第12页，本讲稿共48页 1.对称矩阵的压缩存储对称矩阵的压缩存储 若若 一一 个个 n阶阶 方方 阵阵Ann中中 的的 元元 素素 满满 足足ai,j=aj,i(0i,jn-1),则称其为则称其为n阶阶对称矩阵对称矩阵。由由于于对对称称矩矩阵阵中中的的元元素素关关于于主主对对角角线线对对称称,因因此此在在存存储储时时可可只只存存储储对对称称矩矩阵阵中中上上三三角角或或下下三三角角中中的的元元素素,使使得得对对称称的的元元素素共共享享一一个个存存储储空空间间。这这样样,就就可可以以将将

10、n2个个元元素素压压缩缩存存储储到到个个元元素素的的空空间间中中。不不失失一一般般性性,我我们们以以行行序序为为主主序存储其下三角序存储其下三角(包括对角线包括对角线)的元素。的元素。第13页，本讲稿共48页 n2个元素个元素 n(n+1)/2个元素个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bkk=+j ij+i ij第14页，本讲稿共48页上三角矩阵：上三角矩阵：k=+j i ij时时ij时时第15页，本讲稿共48页下三角矩阵：下三角矩阵：k=ij时时ij时时第16页，本讲稿共48页 2.对角矩阵的压缩存储对角矩阵的压缩存储 若若一一个个n阶阶方方阵阵A满满足足其

11、其所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的的带带状状区区域域中中,则则称称其其为为n阶阶对对角角矩矩阵阵。其其主主对对角角线线上上下下方方各各有有b条条次次对对角角线线,称称b为为矩矩阵阵半半带带宽宽,(2b+1)为为矩矩阵阵的的带带宽宽。对对于于半半带带宽宽为为b(0b(n-1)/2)的的对对角角矩矩阵阵,其其|i-j|b的的元元素素ai,j不不为为零零,其其余余元元素素为为零零。下下图图所所示示是是半半带带宽为宽为b的对角矩阵示意图。的对角矩阵示意图。第17页，本讲稿共48页 半带宽为半带宽为b b的对角矩阵的对角矩阵第18页，本讲稿共48页当当b1时称为

12、三对角矩阵。时称为三对角矩阵。其压缩地址计算公式如下：其压缩地址计算公式如下：k=2i+j A B aij bk第19页，本讲稿共48页 例例5.2 按按行行优优先先顺顺序序和和按按列列优优先先顺顺序序列列出出四四维维数组数组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第20页，本讲稿共48页 解：解：按行优先的存储次序按行优先的存储次序:A0000,A0001,A0010,A0011,A0100,A0101,A0110,A0111,A1000,A1001,A1010,A1011,A1100,A1101,A1110,A1111第21页，本讲稿共48页 按列优先的存储次序按

13、列优先的存储次序:A0000,A1000,A0100,A1100,A0010,A1010,A0110,A1110,A0001,A1001,A0101,A1101,A0011,A1011,A0111,A1111第22页，本讲稿共48页 例例5.3 对对于于二二维维数数组组Amn,其其中中m80,n80,先先读读入入m和和n,然然后后读读该该数数组组的的全全部部元元素素,对对如如三三种种情情况况分分别别编编写相应函数写相应函数:(1)求数组求数组A靠边元素之和靠边元素之和;(2)求求从从A00开开始始的的行行、列列互互不不相相邻邻的的各各元元素素之之和和;(3)当当m=n时时,分分别别求求两两条条

14、对对角角线线上上的的元元素素之之和和,否否则则打印出打印出mn的信息。的信息。第23页，本讲稿共48页 解：解：(1)对应算法如下：对应算法如下：void proc1(ElemType An)int s=0,i,j;for(i=0;im;i+)/*第一列第一列*/s=s+Ai0;for(i=0;im;i+)/*最后一列最后一列*/s=s+Ain-1;for(j=0;jn;j+)/*第一行第一行*/s=s+A0j;for(j=0;jn;j+)/*最后一行最后一行*/s=s+Am-1j;s=s-A00-A0n-1-Am-10-Am-1n-1;/*减去减去4个角的重复元素值个角的重复元素值*/pri

15、ntf(s=%dn,s);第24页，本讲稿共48页 (2)对应算法如下：对应算法如下：void proc2(maxix A)int s=0,i=0,j=0;do do s=s+Aij;j=j+2;/*跳过一列跳过一列*/while(jn);i=i+1;/*下一行下一行*/if(j=0)j=1;else j=0;while(im);printf(s=%dn,s);第25页，本讲稿共48页(3)对应算法如下：对应算法如下：void proc3(maxix A)int i,s=0;if(m!=n)printf(mn);else for(i=0;im;i+)s=s+Aii;/*求第一条对角线之和求第一

16、条对角线之和*/for(i=0;in;i+)s=s+An-i-1i;/*累加第二条对角线之和累加第二条对角线之和*/s-=An/2n/2;printf(s=%dn,s);第26页，本讲稿共48页5.2 5.2 稀疏矩阵稀疏矩阵 一一个个阶阶数数较较大大的的矩矩阵阵中中的的非非零零元元素素个个数数s相相对对于于矩矩阵阵元元素素的的总总个个数数t十十分分小小时时,即即st时时,称称该该矩矩阵阵为为稀稀疏疏矩矩阵阵。例例如如一一个个100100的的矩矩阵阵,若若其其中中只只有有100个非零元素个非零元素,就可称其为就可称其为稀疏矩阵稀疏矩阵。第27页，本讲稿共48页5.2.1 5.2.1 稀疏矩阵的

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

18、矩矩阵阵A(为为图图示示方方便便,我我们们所所取取的的行行列列数数都都很很小小),A中中元元素素如如下下图图所所示示。则则对对应应的的三三元元组组线性表为：线性表为：(0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4)一个稀疏矩阵一个稀疏矩阵A A第29页，本讲稿共48页 若若把把稀稀疏疏矩矩阵阵的的三三元元组组线线性性表表按按顺顺序序存存储储结结构构存存储储,则则称称为为稀稀疏疏矩矩阵阵的的三三元元组组顺顺序序表表。则则三三元元组组顺顺序序表表的的数据结构可定义如下：数据结构可定义如下：第30页，本讲稿共48页#define MaxS

19、ize 100 /*矩阵中非零元素最多个数矩阵中非零元素最多个数*/typedef struct int r;/*行号行号*/int c;/*列号列号*/ElemType d;/*元素值元素值*/TupNode;/*三元组定义三元组定义*/typedef struct int rows;/*行数值行数值*/int cols;/*列数值列数值*/int nums;/*非零元素个数非零元素个数*/TupNode dataMaxSize;TSMatrix;/*三元组顺序表定义三元组顺序表定义*/第31页，本讲稿共48页 其其中中,data域域中中表表示示的的非非零零元元素素通通常常以以行行序序为为主

20、主序序顺顺序序排排列列,它它是是一一种种下下标标按按行行有有序序的的存存储储结结构构。这这种种有有序序存存储储结结构构可可简简化化大大多多数数矩矩阵阵运运算算算算法法。下下面面的的讨讨论论假假设设data域域按行有序存储。按行有序存储。第32页，本讲稿共48页 (1)从一个二维矩阵创建其三元组表示从一个二维矩阵创建其三元组表示 以以行行序序方方式式扫扫描描二二维维矩矩阵阵A,将将其其非非零零的的元元素素插插入入到到三三元元组组t的后面。算法如下：的后面。算法如下：void CreatMat(TSMatrix&t,ElemType AMN)int i,j;t.rows=M;t.cols=N;t.

21、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+;/*查找列查找列*/第34页，本讲稿共48页 if(t.datak.r=rs&t.datak.c=cs)t.datak.d=x;/*存在这样的元素存在这样的元素 else /*不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素*/for(i=t.nums-1;ik;i-)/*元素后移元素后移*/t.datai+1.r=t.datai.r;t.datai+1.c=t.data

22、i.c;t.datai+1.d=t.datai.d;t.datak.r=rs;t.datak.c=cs;t.datak.d=x;t.nums+;return 1;第35页，本讲稿共48页 (3)将指定位置的元素值赋给变量将指定位置的元素值赋给变量 先先在在三三元元组组t中中找找到到指指定定的的位位置置,将将该该处处的的元元素素值值赋赋给给x。算算法如下：法如下：int Assign(TSMatrix t,ElemType&x,int rs,int cs)int k=0;if(rs=t.rows|cs=t.cols)return 0;while(kt.datak.r)k+;while(kt.da

23、tak.c)k+;if(t.datak.r=rs&t.datak.c=cs)x=t.datak.d;return 1;else return 0;第36页，本讲稿共48页 (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(-n);for(i=0;it.nums;i+)printf(t%dt%dt%dn,t.datai.r,t.data

24、i.c,t.datai.d);第37页，本讲稿共48页 (5)矩阵转置矩阵转置 对对于于一一个个mn的的矩矩阵阵Amn,其其转转置置矩矩阵阵是是一一个个nm的的矩矩阵阵。设设为为Bnm,满满足足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.num

25、s;p+)/*p为为t.data的下标的下标*/第38页，本讲稿共48页 if(t.datap.c=v)tb.dataq.r=t.datap.c;tb.dataq.c=t.datap.r;tb.dataq.d=t.datap.d;q+;第39页，本讲稿共48页 以上算法的时间复杂度为以上算法的时间复杂度为O(t.cols*t.nums),而将二维数而将二维数组存储在一个组存储在一个m行行n列矩阵中时列矩阵中时,其转置算法的时间复杂度其转置算法的时间复杂度为为O(m*n)。最坏情况是当稀疏矩阵中的非零元素个数。最坏情况是当稀疏矩阵中的非零元素个数t.nums和和m*n同数量级时同数量级时,上述转

26、置算法的时间复杂度就为上述转置算法的时间复杂度就为O(m*n2)。对其他几种矩阵运算也是如此。可见对其他几种矩阵运算也是如此。可见,常规的非稀常规的非稀疏矩阵应采用二维数组存储疏矩阵应采用二维数组存储,只有当矩阵中非零元素个只有当矩阵中非零元素个数数s满足满足s(N)?(M):(N)/*矩阵行列较大者矩阵行列较大者*/typedef struct mtxn int row;/*行号行号*/int col;/*列号列号*/struct mtxn*right,*down;/*向右和向下的指针向右和向下的指针*/union int value;struct mtxn*link;tag;MatNode

27、;/*十字链表类型定义十字链表类型定义*/第46页，本讲稿共48页本章小结本章小结本章基本学习要点如下：本章基本学习要点如下：(1)理解数组和一般线性表之间的差异。理解数组和一般线性表之间的差异。(2)重点掌握数组的顺序存储结构和元素地址计算方法。重点掌握数组的顺序存储结构和元素地址计算方法。(3)掌掌握握各各种种特特殊殊矩矩阵阵如如对对称称矩矩阵阵、上上、下下三三角角矩矩阵阵和和对角矩阵的压缩存储方法。对角矩阵的压缩存储方法。(4)掌掌握握稀稀疏疏矩矩阵阵的的各各种种存存储储结结构构以以及及基基本本运运算算实实现现算法。算法。(5)灵活运用数组这种数据结构解决一些综合应用问题。灵活运用数组这种数据结构解决一些综合应用问题。第47页，本讲稿共48页练习题练习题 教材中教材中p113习题习题3、5和和6。第48页，本讲稿共48页