数组和稀疏矩阵精选课件.ppt





《数组和稀疏矩阵精选课件.ppt》由会员分享,可在线阅读,更多相关《数组和稀疏矩阵精选课件.ppt(57页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关于数组和稀疏矩阵第一页,本课件共有57页5.1.1 5.1.1 数组的基本概念数组的基本概念 数数组组是是n(n1)个个相相同同类类型型数数据据元元素素a0,a1,an-1构构成成的的有有限限序序列列,且且该该有有限限序序列列存存储储在在一一块块地地址址连连续续的的内内存存单元中。单元中。由由此此可可见见,数数组组的的定定义义类类似似于于采采用用顺顺序序存存储储结结构构的的线线性表。性表。第二页,本课件共有57页数组具有以下性质:数组具有以下性质:(1)数数组组中中的的数数据据元元素素数数目目固固定定,一一旦旦定定义义了了一一个个数数组,其数据元素数目不再有增减变化。组,其数据元素数目不再有
2、增减变化。(2)数组中的数据元素具有相同的数据类型。数组中的数据元素具有相同的数据类型。(3)数数组组中中的的每每个个数数据据元元素素都都和和一一组组唯唯一一的的下下标标值对应。值对应。(4)数数组组是是一一种种随随机机存存储储结结构构,可可随随机机存存取取数数组组中中的的任意数据元素。任意数据元素。第三页,本课件共有57页5.1.2 5.1.2 数组的存储结构数组的存储结构 在在一一维维数数组组中中,假假设设a0的的存存储储地地址址由由LOC(a0)确确定定,且且每每个个数数据据元元素素占占用用k个个存存储储单单元元,则则任任一一数数据据元元素素ai的的存存储地址储地址LOC(ai)就可由以
3、下公式求出:就可由以下公式求出:LOC(ai)=LOC(a0)+i*k(0in-1)上上式式说说明明,一一维维数数组组中中任任一一数数据据元元素素的的存存储储地地址址可可直直接接计计算算得得到到,即即一一维维数数组组中中任任一一数数据据元元素素可可直直接接存存取取。因因此此,一一维维数数组组是是一一种种随随机机存存储储结结构构。同同样样,二二维维及及多多维维数数组组也也满满足随机存储特性。足随机存储特性。第四页,本课件共有57页对于一个对于一个m m行行n n列的二维数组列的二维数组A Amnmn,有:有:将将Am*n简记为简记为A,A是这样的一维数组:是这样的一维数组:A=(a0,a1,ai
4、,am-1)其中其中,ai=(ai,0,ai,1,ai,n1)(0im-1)。第五页,本课件共有57页 显显然然,二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组的的一一维维数数组组。以以此此类类推推,任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表,这这时时线线性性表表中中的的每每个个数数据据元元素素也也是是一一个个线线性性表表。多维数组是线性表的推广。多维数组是线性表的推广。第六页,本课件共有57页 对对于于二二维维数数组组来来说说,由由于于计计算算机机的的
5、存存储储结结构构是是线线性性的的,如如何何用用线线性性的的存存储储结结构构存存放放二二维维数数组组元元素素就就有有一一个个行行列次序排放问题。列次序排放问题。以以行行序序为为主主序序的的存存储储方方式式:即即先先存存储储第第1行行,然然后后紧紧接接着着存存储储第第2行行,最最后后存存储储第第m行行。此此时时,二二维维数数组组的的线线性性排排列列次次序为:序为:a0,0,a0,1,a0,n-1,a1,0,a1,1,a2,n-1,am-1,0,am-1,1,am-1,n-1第七页,本课件共有57页 对对一一个个已已知知以以行行序序为为主主序序的的计计算算机机系系统统中中,当当二二维维数数组组第第一
6、一个个数数据据元元素素a0,0的的存存储储地地址址LOC(a0,0)和和每每个个数数据据元元素素所所占占用用的的存存储储单单元元k确确定定后后,则则该该二二维维数数组组中中任任一一数数据据元元素素ai,j的存储地址可由下式确定:的存储地址可由下式确定:LOC(ai,j)=LOC(a0,0)+i*n+j*k 其中其中n为列数。为列数。第八页,本课件共有57页 同理可推出在以列序为主序的计算机系统中有:同理可推出在以列序为主序的计算机系统中有:LOC(ai,j)=LOC(a0,0)+j*m+i*k 其中其中m为行数为行数。第九页,本课件共有57页 例例5.1 对二维数组对二维数组float a54
7、计算:计算:(1)数组数组a中的数组元素数目;中的数组元素数目;(2)若若数数组组a的的起起始始地地址址为为2000,且且每每个个数数组组元元素素长长度度为为32位位(即即4个字节个字节),数组元素,数组元素a32的内存地址。的内存地址。第十页,本课件共有57页 解:该数组的元素数目共有解:该数组的元素数目共有5*4=20个。个。由于由于C语言采用行序为主序的存储方式语言采用行序为主序的存储方式,则有:则有:LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056第十一页,本课件共有57页5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特特殊殊矩矩
8、阵阵是是指指非非零零元元素素或或零零元元素素的的分分布布有有一一定定规规律律的的矩矩阵阵,为为了了节节省省存存储储空空间间,特特别别是是在在高高阶阶矩矩阵阵的的情情况况下下,可可以以利利用用特特殊殊矩矩阵阵的的规规律律,对对它它们们进进行行压压缩缩存存储储,也也就就是是说说,使使多多个个相相同同的的非非零零元元素素共共享享同同一一个个存存储储单单元元,对对零零元元素素不不分分配存储空间。配存储空间。特特殊殊矩矩阵阵的的主主要要形形式式有有对对称称矩矩阵阵、对对角角矩矩阵阵等等,它它们们都都是方阵,即行数和列数相同。是方阵,即行数和列数相同。第十二页,本课件共有57页 1.对称矩阵的压缩存储对称
9、矩阵的压缩存储 若若一一个个n阶阶方方阵阵Ann中中的的元元素素满满足足ai,j=aj,i(1i,jn),则则称其为称其为n阶阶对称矩阵对称矩阵。由由于于对对称称矩矩阵阵中中的的元元素素关关于于主主对对角角线线对对称称,因因此此在在存存储储时时可可只只存存储储对对称称矩矩阵阵中中上上三三角角或或下下三三角角中中的的元元素素,使使得得对对称称的的元元素素共共享享一一个个存存储储空空间间。这这样样,就就可可以以将将n2个个元元素素压压缩缩存存储储到到n(n+1)/2个个元元素素的的空空间间中中。不不失失一一般般性性,我我们以行序为主序存储其们以行序为主序存储其下三角下三角(包括对角线包括对角线)的
10、元素,例如:的元素,例如:第十三页,本课件共有57页 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 .7 0 6 1 3 an1 a n2 an3 a nn 在这个下三角矩阵中,第在这个下三角矩阵中,第i i行恰有行恰有i i个元素,元素总数为:个元素,元素总数为:n(n+1)/2n(n+1)/2 因此,我们可以按从上到下、从左到右将这些元素因此,我们可以按从上到下、从左到右将这些元素存放在一个向量存放在一个向量b0.n(n+1)/2-1b0.n(n+1)/2-1中。为了便于访问对中。为了便于访问对称矩阵称矩阵
11、A A中的元素,我们必须在中的元素,我们必须在a aijij和和bkbk之间找一个对应关之间找一个对应关系。系。第十四页,本课件共有57页 若若ijij,则,则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i-1i-1行共有行共有1+2+i-1=i(i-1)/21+2+i-1=i(i-1)/2个元素,在第个元素,在第i i行上,行上,a aijij之前有之前有j-1j-1个元素(即个元素(即a ai1i1,a,ai2i2,a,ai3i3,a,aij-1ij-1),因此有:),因此有:a11 a21 a22 a31 an1 annk=0 1 2 3-1i*(i-1)/2+j
12、1 i*(i-1)/2+j1 当当i=ji=jj*(j-1)/2+i-1 j*(j-1)/2+i-1 当当ijijk=第十五页,本课件共有57页2.三角矩阵的压缩存储三角矩阵的压缩存储 以主对角线划分,三角矩阵有上三角和下三角两种。以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵如图上三角矩阵如图a a所示,它的下三角(不包括主对角线)所示,它的下三角(不包括主对角线)中的元素均为常数中的元素均为常数c c。下三角矩阵正好相反,它的主对。下三角矩阵正好相反,它的主对角线上方均为常数角线上方均为常数c c,如图,如图b b所示。在大多数情况下,所示。在大多数情况下,三角矩阵三角矩阵常数为
13、零常数为零。a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c .c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵第十六页,本课件共有57页 三角矩阵的重复元素三角矩阵的重复元素c c可共享一个存储空间,其余元素正好有可共享一个存储空间,其余元素正好有n(n+1)/2n(n+1)/2个,因此,三角矩阵可压缩存储到个,因此,三角矩阵可压缩存储到b0.n(n+1)/2b0.n(n+1)/2中,中,其中其中c c存放在最后一个分量中。存放在最后一个分量中。上三角矩阵
14、中,主对角线之上的第上三角矩阵中,主对角线之上的第i i行行(0in)(0ijijk=下三角矩阵的存储和对称矩阵类似,下三角矩阵的存储和对称矩阵类似,bk和和aij对应关系是:对应关系是:i(i+1)/2+j ij n(n+1)/2 ijk=第十七页,本课件共有57页 3.对角矩阵的压缩存储对角矩阵的压缩存储 若若一一个个n阶阶方方阵阵A满满足足其其所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的的带带状状区区域域中中,则则称称其其为为n阶阶对对角角矩矩阵阵,其其主主对对角角线线上上下下方方各各有有b条条次次对对角角线线,称称b为为矩矩阵阵半半带带宽宽,(2b+1)为
15、为矩矩阵阵的的带带宽宽。对对于于半半带带宽宽为为b(0b(n-1)/2)的的对对角角矩矩阵阵,其其|i-j|b的的元元素素ai,j不不为为零零,其其余余元元素素为为零零。下图所示是半带宽为下图所示是半带宽为b的对角矩阵示意图。的对角矩阵示意图。第十八页,本课件共有57页 半带宽为半带宽为b b的对角矩阵的对角矩阵 第十九页,本课件共有57页 a00 a01 a10 a11 a12 a21 a22 a23 .可用以行序为主序的可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储形式存储b3n-2中中 当当b1时称为三对角矩阵,如:
16、时称为三对角矩阵,如:主对角线下方的元素的下标关系为主对角线下方的元素的下标关系为 i=j+1,此时此时k=3(i-1)+2主对角线上的元素的下标关系为主对角线上的元素的下标关系为 i=j,此时此时k=3(i-1)+3主对角线下的元素的下标关系为主对角线下的元素的下标关系为 i=j1,此时此时k=3(i-1)+4即:即:k=2i+j第二十页,本课件共有57页 例例5.2 按按行行优优先先顺顺序序和和按按列列优优先先顺顺序序列列出出四四维维数组数组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第二十一页,本课件共有57页 解:解:按行优先的存储次序按行优先的存储次序:A000
17、0,A0001,A0010,A0011,A0100,A0101,A0110,A0111,A1000,A1001,A1010,A1011,A1100,A1101,A1110,A1111第二十二页,本课件共有57页 按列优先的存储次序按列优先的存储次序:A0000,A1000,A0100,A1100,A0010,A1010,A0110,A1110,A0001,A1001,A0101,A1101,A0011,A1011,A0111,A1111第二十三页,本课件共有57页5.2 5.2 稀疏矩阵稀疏矩阵 一一个个阶阶数数较较大大的的矩矩阵阵中中的的非非零零元元素素个个数数s相相对对于于矩矩阵阵元元素素
18、的的总总个个数数t十十分分小小时时,即即st时时,称称该该矩矩阵阵为为稀稀疏疏矩矩阵阵。例例如如一一个个100100的的矩矩阵阵,若若其其中中只只有有100个非零元素个非零元素,就可称其为就可称其为稀疏矩阵稀疏矩阵。第二十四页,本课件共有57页5.2.1 5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 稀疏矩阵的压缩存储方法是稀疏矩阵的压缩存储方法是只存储非零元素只存储非零元素。由由于于稀稀疏疏矩矩阵阵中中非非零零元元素素的的分分布布没没有有任任何何规规律律,所所以以在在存存储储非非零零元元素素时时还还必必须须同同时时存存储储该该非非零零元元素素所所对对应应的的行行下下标标和和列列下下标
19、标。这这样样稀稀疏疏矩矩阵阵中中的的每每一一个个非非零零元元素素需需由由一一个个三三元元组组(i,j,ai,j)惟惟一一确确定定,稀稀疏疏矩矩阵阵中的所有非零元素构成三元组线性表。中的所有非零元素构成三元组线性表。第二十五页,本课件共有57页 假假设设有有一一个个67阶阶稀稀疏疏矩矩阵阵M(为为图图示示方方便便,我我们们所所取取的的行行列列数数都都很很小小),M中中元元素素如如下下图图所所示示。则则对对应应的的三元组线性表为:三元组线性表为:(0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,16),(5,3,-7)第二十六页,本
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 稀疏 矩阵 精选 课件

限制150内