第六章数组

1、第第6章章 数组数组6.1 数组数组6.2 稀疏矩阵稀疏矩阵本章小结本章小结数组和广义表数组和广义表线性表、栈、队列、串都是线性结构，并且其线性表、栈、队列、串都是线性结构，并且其数据元素都是不能分解的原子类型数据元素都是不能分解的原子类型 数组和广义表数组和广义表逻辑上是线性结构的推广。逻辑上是线性结构的推广。 数组数组是以元素为线性表的线性结构，而且元是以元素为线性表的线性结构，而且元 素的结构相同；素的结构相同； 广义表广义表也是一种线性结构的推广，其元素的也是一种线性结构的推广，其元素的结构可以不同结构可以不同 高级语言中的数组w int a10;w char B45 二维数组二维数组

2、w int a23;ntypedef int A3; A a2;n两个变量组成的一个数组，两个变量组成的一个数组，其中每一个变量都是数组。其中每一个变量都是数组。其中其中a0，a1都是数组都是数组的名字，也就是地址。的名字，也就是地址。 a01a00a12a11a10a02数组的逻辑定义数组的逻辑定义 mnmmnnnmaaaaaaaaaA212222111211mnnnmmnmaaaaaaaaaA212221212111nA,21mjjjj,21 n n（n n1 1）维数组是一个向量，它的每个元素是维数组是一个向量，它的每个元素是n-1n-1维数维数组，且具有相同的上限和下限组，且具有相同的

3、上限和下限 mA,21iniii,21二维数组的矩二维数组的矩阵形式表示阵形式表示列向量形式列向量形式的线性表的线性表Am*n=(a11,a12,a1n),(a21,a22,a2n),(am1,am2,amn)行向量形式的线性表行向量形式的线性表一个二维数组可以看作是每个数据元素都是相同类型一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推，任何多维数组都可以的一维数组的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个看作一个线性表，这时线性表中的每个数据元素也是一个线性表。线性表。多维数组是线性表的推广。多维数组是线性表的推广

4、。推广到推广到d（d3）维数组，不妨把它看作一个由）维数组，不妨把它看作一个由d- -1维维数组作为数据元素的线性表；或者这样理解，它是一种较数组作为数据元素的线性表；或者这样理解，它是一种较复杂的线性表结构，由简单的数据结构即线性表复杂的线性表结构，由简单的数据结构即线性表辗转辗转合成而得。合成而得。6.1 数组的抽象数据类型ADTADT ArrayADT Array数据对象：数据对象： D Daaj1j2jnj1j2jn|n0|n0称为数组的维数，称为数组的维数，j ji i是数组元素的第是数组元素的第i i维下维下 标，标，0j0ji ibbi i-1-1，b bi i是数组第是数组第i

5、 i维的长度，维的长度， a aj1j2jn j1j2jn ElemSetElemSet 数据关系：数据关系： R=R R=R1 1,R,R2 2,R,Rn n R Ri i=a=| 0j| 0jk kbbk k-1,1kn-1,1kn 且且ki,0jki,0ji ibbi i-2,-2, a aj1jijnj1jijn,a,aj1ji+1jn j1ji+1jn D,i=2,nD,i=2,n基本操作：基本操作： Value(A,index Value(A,index1 1,index,indexn n) ) Assign(A,e,index Assign(A,e,index1 1,index,

6、indexn n) ) ADT ArrayADT Array 数组特点：数组一般不做插入数组特点：数组一般不做插入和删除操作。和删除操作。所以对数组的操作不像对线性所以对数组的操作不像对线性表的操作那样可以在表中任意表的操作那样可以在表中任意一个位置插入和删除元素一个位置插入和删除元素基本只有两个操作：取数组元素基本只有两个操作：取数组元素的值和修改数组元素的值的值和修改数组元素的值以二维数组为例w D=aij| aij D 0ib1-1, 0jb2-1 R=R1,R2 R1=ROW= , 0ib1-1, 0jb2-1 R2=COL= , 0ib1-1, 0 jb2-1 a00,a01,a0,

7、b2-1 . ab1-1,0,.ab1-1,b2-1对于数组来说，可以用下列结构表示：对于数组来说，可以用下列结构表示：（下标，元素）（下标，元素）一维数组：一维数组： （i, ai)二维数组：二维数组： （(i,j), aij)多维数组：多维数组：(j1,j2,jn),a j1,j2,jn)基本操作：基本操作： Value(A,index1,indexn) 初始条件：初始条件： A是是n维数组，维数组，index1,indexn 为为n个个下标值。下标值。 操作结果：操作结果：若各下标不超界，返回数组若各下标不超界，返回数组A的对应下的对应下标的元素值。标的元素值。 Assign(A,e,i

8、ndex1,indexn) 初始条件：初始条件：A是是n维数组，维数组，e为元素，为元素，index1,indexn为为n个下标值。个下标值。 操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的A的元素值。的元素值。 数组没有加工型的操作，最多是改变数组元素的值，不会数组没有加工型的操作，最多是改变数组元素的值，不会改变其结构。改变其结构。从存储结构上看，数组的所有元素存储在一块地址连从存储结构上看，数组的所有元素存储在一块地址连续的内存单元中。几乎所有的计算机语言都支持数组类型，续的内存单元中。几乎所有的计算机语言都支持数组类型，以以C/C+语言为例，其中

9、数组数据类型具有以下性质：语言为例，其中数组数据类型具有以下性质： （1）数组中的数据元素数目固定。一旦定义了一个数组）数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。其数据元素数目不再有增减变化。 （2）数组中的数据元素具有相同的数据类型。）数组中的数据元素具有相同的数据类型。 （3）数组中的每个数据元素都和一组唯一的下标值对应。）数组中的每个数据元素都和一组唯一的下标值对应。 （4）数组是一种随机存储结构。可随机存取数组中的任）数组是一种随机存储结构。可随机存取数组中的任意数据元素。意数据元素。6.1.2 数组的存储结构数组的存储结构 在一维数组中在一维数组中,

10、一旦一旦a1的存储地址的存储地址LOC(a1)确定确定,并假设每并假设每个数据元素占用个数据元素占用k个存储单元个存储单元,则任一数据元素则任一数据元素ai的存储地址的存储地址LOC(ai)就可由以下公式求出：就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in) 上式说明上式说明,一维数组中任一数据元素的存储地址可直接计算一维数组中任一数据元素的存储地址可直接计算得到得到,即一维数组中任一数据元素可直接存取即一维数组中任一数据元素可直接存取,因此因此,一维数组是一维数组是一种一种随机存储结构随机存储结构。 同样，二维及多维数组也满足随机存储特性。同样，二维及多维数组

11、也满足随机存储特性。 nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1对于一个对于一个m行行n列的二维数组列的二维数组Amn,有：有： 将将Amn简记为，简记为，A是这样的一维数组：是这样的一维数组： A=(a1,a2,ai,am)其中，其中，ai=(ai,1,ai,2,ai,n) (1im)。 对于二维数组来说对于二维数组来说,由于计算机的存储结构是线性的由于计算机的存储结构是线性的,如如何用线性的存储结构存放二维数组元素就有一个何用线性的存储结构存放二维数组元素就有一个行列次行列次序排放问题。序排放问题。 以以行序为主序的存储方式行序为主序的存储方式

12、：即先存储第：即先存储第1行行,然后紧接然后紧接着存储第着存储第2行行,最后存储第最后存储第m行。此时行。此时,二维数组的线性排列二维数组的线性排列次序为：次序为： a1,1,a1,2,a1,n,a2,1,a2,2,a2,n,am,1,am,2,am,n 对一个已知以行序为主序的计算机系统中对一个已知以行序为主序的计算机系统中,当二维数组第当二维数组第一个数据元素一个数据元素a1,1的存储地址的存储地址LOC(a1,1)和每个数据元素所占用和每个数据元素所占用的存储单元的存储单元k确定后确定后,则该二维数组中任一数据元素则该二维数组中任一数据元素ai,j的存储地的存储地址可由下式确定：址可由下

13、式确定： 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为行数。为行数。w 设有一个三维数组，其下标为（设有一个三维数组，其下标为（2，3，2）第一个下标：第一个下标：0，1第二个下标：第二个下标：0，1，2第三个下标：第三个下标：0，1则行序为主（低下标优先）则行序为主（低下标优先）(即第三个下标先变化）即第三个下标先变化）(0,0,0),(0,0,1),(0,1,0),(

14、0,1,1),(0,2,0),(0,2,1)(1,0,0),(1,0,1),(1,1,0),(1,1,1),(1,2,0),(1,2,1)列序为主（高下标优先）列序为主（高下标优先） (即第一个下标先变化）即第一个下标先变化）(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0,2,0),(1,2,0)(0,0,1),(1,0,1),(0,1,1),(1,1,1),(0,2,1),(1,2,1) 例如，按行优先顺序和按列优先例如，按行优先顺序和按列优先顺序列出四维数组顺序列出四维数组A2222所有元所有元素在内存中的存储次序。素在内存中的存储次序。 解：解： 按行优先的存储次序

15、按行优先的存储次序: A0000, A0001, A0010, A0011, 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 例如，例如，C/C+中二维数组中二维数组float a54的起始地址为的起始地址为2000

16、，且，且每个数组元素长度为每个数组元素长度为32位（即位（即4个字节），求数组元素个字节），求数组元素a32的的内存地址。内存地址。解：解：由于由于C/C+中数组的行、列下界均为中数组的行、列下界均为0，所以，所以，d1=4，c1=0，d2=3，c2=0，又由于，又由于C/C+数组采用行序为主序的存储数组采用行序为主序的存储方式，有：方式，有：LOC(a3,2)=LOC(a0,0)+(i-c1)(d2- -c2+1)+(j- -c2)k=2000+(34+2)4=2056。从中看到，对于从中看到，对于C/C+的数组的数组amn，求，求aij元素的地址为：元素的地址为：LOC(ai,j)=LOC

17、(a0,0)+(in+j)k练习题练习题练习题练习题w 设有数组设有数组Ai,j，数组的每个元素长度为，数组的每个元素长度为3字节，字节，i的值为的值为1 到到8 ，j的值为的值为1 到到10，数组从内存首地址，数组从内存首地址BA开始顺序开始顺序存放，当用以存放，当用以列为主存放列为主存放时，元素时，元素A5，8的存储首地的存储首地址为址为( )。w A. BA+141 w B. BA+180 w C. BA+222 w D. BA+225w 【南京理工大学南京理工大学 1997 一、一、8 （2分）分）】答案为：答案为：BnLOC(i,j)=LOC(c1,c2)+(j-c2)*(d1-c1

18、+1)+(i-c1)*L 以列序为主存放时以列序为主存放时练习题练习题w 二维数组二维数组A的元素都是的元素都是6个字符组成的串，行下标个字符组成的串，行下标i的范围从的范围从0到到8，列下标，列下标j的范围从的范围从1到到10。从供选择的答案中选出应。从供选择的答案中选出应填入下列关于数组存储叙述中（填入下列关于数组存储叙述中（ ）内的正确答案。）内的正确答案。w （1）存放）存放A至少需要（至少需要（ ）个字节；）个字节；w （2）A的第的第8列和第列和第5行共占（行共占（ ）个字节；）个字节；w 供选择的答案：供选择的答案：w （1）A. 90 B. 180 C. 240 D. 270

19、E. 540 w （2）A. 108 B. 114 C. 54 D. 60 E. 150 w 【山东工业大学山东工业大学 2000 三、三、1 （4分）分）】 【山东大学山东大学 1998 三、三、1 (4分分)】答案为：答案为：（1）：）： E（2）：）： A注意行列交点处的元素被计算了注意行列交点处的元素被计算了两次，所以应该减去一两次，所以应该减去一6.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储w当矩阵的阶数较高，而且矩阵中的一当矩阵的阶数较高，而且矩阵中的一些元素有特殊的性质时，可以采用节些元素有特殊的性质时，可以采用节省空间的存储方法。省空间的存储方法。w矩阵需要有特殊性：矩阵需要

20、有特殊性：n特殊矩阵：值相同，或零元素分布有一特殊矩阵：值相同，或零元素分布有一定的规律；定的规律；6.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵的主要形式有：特殊矩阵的主要形式有：（1）对称矩阵）对称矩阵（2）上三角矩阵下三角矩阵）上三角矩阵下三角矩阵（3）对角矩阵）对角矩阵它们都是方阵，即行数和列数相同。它们都是方阵，即行数和列数相同。1. 特殊矩阵w 特殊矩阵之特殊矩阵之 对称矩阵对称矩阵n若若n阶矩阵阶矩阵A中的元素满足下述性质中的元素满足下述性质 aij=aji 1i , jnn 则称则称A A为为n n阶对称矩阵阶对称矩阵 nn2个元素可以压缩到个元素可以压缩到n(n+

21、1)/2个空间中；个空间中；n以行序为主序将其以行序为主序将其下三角下三角（包括对角线）（包括对角线）中的元素中的元素存储到一个向量存储到一个向量Bn(n+1)/2中中a11a21a22a31an1annk= 0 1 2 3 2) 1( nn12) 1(nnjiijjjijiik当当12)1(12)1(BkBk和矩阵中的元素和矩阵中的元素a aijij之间存在着一一对应关系：之间存在着一一对应关系： 特殊矩阵之 对称矩阵若令：Imax（i,j), J=min(i,j),则可表示为：kI*(I-1)/2+J-1,则aij的地址可以如下计算：LOC（aij)=LOC(Bk)= LOC(B0)+K*

22、L=LOC(B0)+I*(I-1)/2+J-1*L练习题w 设有一个设有一个10阶的对称矩阵阶的对称矩阵A，采用压缩存储方式，采用压缩存储方式，以行序为主存储，以行序为主存储，a11为第一元素，其存储地址为第一元素，其存储地址为为1，每个元素占一个地址空间，则，每个元素占一个地址空间，则a85的地址为的地址为（ ）。）。w 【燕山大学燕山大学 2001 一、一、2 （2分）分）】w A. 13 w B. 33 w C. 18 w D. 40答案为：答案为： B练习题w 若对若对n阶对称矩阵阶对称矩阵A以行序为主序方式将其下三以行序为主序方式将其下三角形的元素角形的元素(包括主对角线上所有元素包

23、括主对角线上所有元素)依次存放依次存放于一维数组于一维数组B1.(n(n+1)/2中，则在中，则在B中确定中确定aij（ij）的位置）的位置k的关系为的关系为( )。w A. i*(i-1)/2+j w B. j*(j-1)/2+i w C. i*(i+1)/2+j w D. j*(j+1)/2+iw 【北京航空航天大学北京航空航天大学 2000 一、一、2 （2分）分）】答案为：答案为：B练习题w 设设A是是n*n的对称矩阵，将的对称矩阵，将A的对角线及对角线上方的的对角线及对角线上方的元素以列为主的次序存放在一维数组元素以列为主的次序存放在一维数组B1.n(n+1)/2中，中，对上述任一元

24、素对上述任一元素aij(1i，jn，且，且ij)在在B中的位置为中的位置为( )。w 【南京理工大学南京理工大学 1999 一、一、9（2分）分）】 w A. i(i-1)/2+j w B. j(j-1)/2+i w C. j(j-1)/2+i-1 w D. i(i-1)/2+j-1答案为：答案为：Bw 三角矩阵三角矩阵 :下（上）三角矩阵是指矩阵的上（下）下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元素均为常数三角（不包括对角线）中的元素均为常数c或零的或零的n阶阶矩阵。矩阵。w 存储同对称矩阵，再增加一个存储常数存储同对称矩阵，再增加一个存储常数c c的存储空间的存储空间 所

25、以共需所以共需n n* *(n+1)/2+1(n+1)/2+1个存储单元个存储单元 以上三角矩阵为例，按行优先顺序存储时，主以上三角矩阵为例，按行优先顺序存储时，主对角线上的第对角线上的第p p行（行（1=1=p=n)p=n)恰有恰有 n-p+1 n-p+1 个元素，个元素，则则aij 之前的之前的 i-1 行共有：行共有：特殊矩阵之 三角矩阵112)22(*)1()1(ipinipn个元素，在第个元素，在第 i 行上行上aij之前有之前有j-i个元素，个元素，特殊矩阵之 三角矩阵w因此因此aij和和Bk之间的对应关系为：之间的对应关系为：jinnjiijinki 2) 1()22(2) 1(

26、当当对应最后一个位置，对应最后一个位置，即放常数即放常数c的单元的单元w 对角矩阵对角矩阵 : :所有的非零元素都集中在以主对角线为中心所有的非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下的带状区域中。即除了主对角线上和直接在对角线上、下方若方若干条对角线上的元素之外，所有其它的元素均为零干条对角线上的元素之外，所有其它的元素均为零 特殊矩阵之 对角矩阵b条对角线条对角线n行行n列列(a)a11a12a21a22a23an-1,nan,nan,n-1OO(b)对角矩阵的一般情形对角矩阵的一般情形三对角矩阵三对角矩阵a11 a12 0 0 0a21 a22 a

27、23 0 00 a32 a33 a34 00 0 a43 a44 a450 0 0 a54 a55按行按行存储存储非零非零元素元素a11a12a21a22a23a32a33a34a43a44a45a54a5501234567891011 12三对角矩阵三对角矩阵(b=1)中中:第一行和第第一行和第n行为两个元行为两个元素素,其它行为其它行为3个元素个元素在2b+1对角矩阵中第第1行存储行存储 b+1 个个第第2行存储行存储 b+2 个个第第 b 行存储行存储 2b 个个从第从第b+1行到行到 n-b行行: 每行存储每行存储 2b+1个个第第n-b+1行存储行存储 2b 个个第第n-b+2行存储

28、行存储 2b-1 个个第第n行存储行存储 b+1 个个所以所以,在在2b+1对角矩阵中对角矩阵中,非零元素的个数为非零元素的个数为:(2b+1)(n-2b)+2(b+1)+2b*b/2=(2b+1)*n-b(b+1)共共 (n-b)-(b+1)+1=n-2b行行是一个等差级数是一个等差级数:(b+1)+(b+2)+2b也是一个等差级数也是一个等差级数:(b+1)+(b+2)+2b特殊矩阵w 在在 2b1 对角矩阵中，非零元素的个数为：对角矩阵中，非零元素的个数为：) 1(*) 12(2/*2) 1(2)2)(12(bbnbbbbbnb即在即在2b1对角矩阵中至少需要对角矩阵中至少需要) 1(*

29、) 12(bbnb 实际上由于对应关系比较复杂，实际上由于对应关系比较复杂， 较好的方法还是认为所有行都较好的方法还是认为所有行都有有 2b1个元素，所以压缩存个元素，所以压缩存储在（储在（2b1）*n的向量中的向量中练习题一w 将三对角矩阵将三对角矩阵A中三条对角线上的元素按中三条对角线上的元素按行存放在一维数组行存放在一维数组B中，且中，且a11存放于存放于B1中。试给出计算中。试给出计算A在三条对角线上的元素在三条对角线上的元素aij(1in, i-1ji+1)在一维数组在一维数组B中的存中的存放位置的计算公式。放位置的计算公式。a11 a12 0 0 0a21 a22 a23 0 00

30、 a32 a33 a34 00 0 a43 a44 a450 0 0 a54 a55按行按行存储存储非零非零元素元素a11a12a21a22a23a32a33a34a43a44a45a54a55123456789101112 13 K=3(i-1)+1 （主对角线上，即（主对角线上，即i=j)K=3(i-1)+2 （主对角线右上，即（主对角线右上，即i=j-1)K=3(i-1) （主对角线左下，即（主对角线左下，即i=j+1)由以上三式可得：由以上三式可得：K=2(i-1)+j （1i,jn, 1k3n-2)练习题二 设设A和和B均为下三角矩阵，每一个均为均为下三角矩阵，每一个均为n行行n列。

31、另设有一个二维数组列。另设有一个二维数组C，它有，它有n行行n+1列。试设计一个方案，将两个矩阵列。试设计一个方案，将两个矩阵A和和B中的下三角区域元素存放于同一个中的下三角区域元素存放于同一个C中。要求将中。要求将A的下三角区域中的元素存放的下三角区域中的元素存放于于C的下三角区域中，的下三角区域中，B的下三角区域中的下三角区域中的元素转置后存放于的元素转置后存放于C的上三角区域中。的上三角区域中。并给出计算并给出计算A的矩阵元素的矩阵元素aij和和B的矩阵元的矩阵元素素bij在在C中的存放位置下标的公式。中的存放位置下标的公式。10987654321A2019181716151413121

32、1BA的元素和的元素和B的元素在的元素在C中的中的存放位置下标的公式为：存放位置下标的公式为：Aij=Cij(0in, 0ji)Bij=Cji+1(0in, ijn) 20 10 9 8 719 16 6 5 418 15 13 3 217 14 12 11 1C算法的主要部分 for (i=0;in;i+) for( j=0;j=i;j+) /把把A赋予赋予C cij=Aij; for( j=i+1; j=n;j+) /把把B赋予赋予C cij=Bj-1i; 2. 稀疏矩阵w假设假设m行行n列的矩阵含列的矩阵含t个非零元素，且分布个非零元素，且分布无规律，则称：无规律，则称： = t/(m*

33、n) 为为稀疏因子稀疏因子通常认为通常认为0.05的矩阵为稀疏矩阵的矩阵为稀疏矩阵 以常规方法，即以二维数组表示高阶的稀以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题：疏矩阵时产生的问题：1) 零值元素占的空间很大；零值元素占的空间很大；2) 计算中进行了很多和零值的运算；计算中进行了很多和零值的运算；0009012700030008000000000200060A02200180000000159009000003004520000MA和和M均为稀疏矩阵均为稀疏矩阵解决稀疏矩阵存储及其运算问题的原则解决稀疏矩阵存储及其运算问题的原则w 1) 尽可能少存或不存零值元素；尽可能少存或不存

34、零值元素；w 2) 尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；w 3) 运算方便，即：运算方便，即： 能够尽可能快地找到与下标值能够尽可能快地找到与下标值(i,j)对应对应的元素；的元素； 能够尽可能快地找到同一行或同一列能够尽可能快地找到同一行或同一列的非零值元素；的非零值元素；稀疏矩阵的存储w 非零元素较少（非零元素较少（tm*n)，且分布无规律，且分布无规律n稀疏因子：稀疏因子： = t/(m*n) = 0.05w 存储结构存储结构n顺序存储结构顺序存储结构三元组顺序表三元组顺序表 n链式存储结构链式存储结构十字链表十字链表 0009012700030008000000

35、000200060A02200180000000159009000003004520000Mrowcole12616-234-842346751-12539rowcole155221-42433594315961186422稀疏矩阵的顺序存储：三元组顺序表稀疏矩阵的顺序存储：三元组顺序表define MAXSIZE 1000 用户自定义用户自定义typedef struct 三元组三元组int row,col; 非零元的行号、列号非零元的行号、列号 ElemType e; 非零元的值非零元的值Triple; /三元组类型三元组类型typedef struct Triple dataMAXSIZ

36、E +1;三元组表，三元组表，data0未用未用 int m,n,len; 矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数TSMatrix; /稀疏矩阵类型稀疏矩阵类型三元组顺序表同时存储行、三元组顺序表同时存储行、列值和非列值和非0元素的个数元素的个数三元组（三元组（i，j，aij)唯一确定了矩阵的唯一确定了矩阵的一个非一个非0元元练习题w 有一个有一个100*90的稀疏矩阵，非的稀疏矩阵，非0元素有元素有10个，设个，设每个整型数占每个整型数占2字节，则用三元组表示该矩阵时，字节，则用三元组表示该矩阵时，所需的字节数是（所需的字节数是（ ）。）。w 【南京理工大学南京理工大学 1

37、999 二、二、8 （2分）分）】w A. 60 w B. 66 w C. 18000 w D. 33答案为：答案为：B除了除了10个元素外，还有行数、列数、非个元素外，还有行数、列数、非0元素的个数元素的个数求转置矩阵的操作w 用常规的二维数组表示时的算法用常规的二维数组表示时的算法 for(col=1;col=n;col+) for (row=1;row=m;row+) Tcolrow=Mrowcol;其时间复杂度为：其时间复杂度为：O(m*n)三元组表的矩阵转置运算 0009012700030008000000000200060A07002000000080090000030061200

38、00Browcole12616-234-842346751-12539rowcole15-1221624335943-861-2647转置：转置：BAT，即即BijAji矩阵转置w 求一个矩阵的转置矩阵可以经过下列求一个矩阵的转置矩阵可以经过下列3 3个个步骤来完成：步骤来完成： n将矩阵的行列值互换；将矩阵的行列值互换； n对每个三元组所表示的非零元，将该元对每个三元组所表示的非零元，将该元素的行、列值互换；素的行、列值互换；n按行序重排三元组。按行序重排三元组。 矩阵转置w 如何实现按行序重排三元组？如何实现按行序重排三元组？ 在在A中依次从前至后找出中依次从前至后找出A的第一列的所有元素

39、，的第一列的所有元素，它们就是它们就是B的第一行的元素，放在的第一行的元素，放在B中。中。在在A中：中：在在B中：中：之前放在：（则它们属于同一列，且且和若有（),(),),(),2211212211ejiejiiiejieji之前放在且：和形成了两个三元组：),(),(),(),(22112211eijeijeijeij以上是第一列的处理，以上是第一列的处理，依次处理第二列依次处理第二列.第第 n 列列矩阵转置TSMatrix TransMatrix(TSMatrix A,TSMatrix B)采用三元组表方式存储稀疏矩阵，实现矩阵的转置采用三元组表方式存储稀疏矩阵，实现矩阵的转置 B.m=

40、A.n; B.n=A.m; B.len=A.len; if(B.len) ql;/q为工作指针，指示为工作指针，指示B中下一个三元组存放的位置中下一个三元组存放的位置 for(j1;jA.n;j+)/从从A的第一列开始扫描的第一列开始扫描 for(p1;pA.len; +p)/遍历三元组表遍历三元组表 if(A.datapcol=j) B.dataqrow=A.datapcol;/B的行为的行为A的列的列 B.dataqcol=A.dataprow;/B的列为的列为A的行的行 B.dataqe=A.datape; q+; /if /if return B;TransMatrix 时间复杂度为：

41、时间复杂度为： O(A.n *A.len)算法分析w 对于对于mu * nu矩阵，一般算法的时间复杂度矩阵，一般算法的时间复杂度为：为：O(mu * nu)。w 当非零元个数当非零元个数tu 和和 mu * nu同数量级时，该同数量级时，该算法的时间复杂度为：算法的时间复杂度为：O(mu * nu2);w 关键是：关键是：每次找第每次找第n列的元素时，必须从开列的元素时，必须从开始遍历整个三元组表，所以效率很低。始遍历整个三元组表，所以效率很低。w 实际上实际上:若知道若知道B的每一行的开始位置，就可的每一行的开始位置，就可以遍历整个三元组，根据数据元素的列坐标以遍历整个三元组，根据数据元素的

42、列坐标（即（即B的行）直接把数据元素放入的行）直接把数据元素放入B中，从而中，从而把算法的时间复杂度降低。把算法的时间复杂度降低。三元组表的矩阵快速转置 思想：思想：在扫描三元组表在扫描三元组表A.data的过程中，每遇到一个三元组，就将它的行列的过程中，每遇到一个三元组，就将它的行列值交换并放在三元组表值交换并放在三元组表B.data的正确位置上的正确位置上 。因此，需要求出矩阵因此，需要求出矩阵A中每列第中每列第一个非零元的位置一个非零元的位置 。position1=1 positionj=positionj-1+numberj-1 2jA.n j123456numberj121102po

43、sitionj124566矩阵矩阵A A的的numbernumber和和positionposition向量的值向量的值 : :用用number数组记录矩阵数组记录矩阵A中每列的非中每列的非0元素个数元素个数Position数组表示矩阵数组表示矩阵A中每列第一个非中每列第一个非0元素的位置元素的位置rowcole12616-234-842346751-125390009012700030008000000000200060ATSMatrix FastTransMatrix(TSMatrix A, TSMatrix B)三元组表上实现矩阵的快速转置算法三元组表上实现矩阵的快速转置算法 B.m=A

44、.n; B.n=A.m; B.len=A.len; if(A.len) for(j=1;j=A.n;j+)矩阵矩阵A A每一列非零元初始化为零每一列非零元初始化为零 numberj=0; for(t=1;t=A.len;t+) 求矩阵求矩阵A A每一列的非零元个数每一列的非零元个数 numberA.datat.col+; position1=1; for(j=2;j=A.n;j+) 求求A.dataA.data第第j j列第一个非零元在列第一个非零元在B.dataB.data中的序号中的序号 positionj=positionj-1+numberj-1;三元组表的矩阵快速转置 for(p=1

45、;p=A.len;p+) 求转置矩阵求转置矩阵B B的三元组表的三元组表 j=A.datap.col; q=positionj; B.dataq.row=A.datap.col; B.dataq.col=A.datap.row; B.dataq.e=A.datap.e; positionj+; /for /if return B; 三元组表的矩阵快速转置（续） 该算法的时间复杂度为：该算法的时间复杂度为：O(A.n+ A.len);O(A.n+ A.len);当待转置矩阵中的非当待转置矩阵中的非0元素个元素个数和数和A.m*A.n等数量级时，其等数量级时，其时间复杂度为时间复杂度为O(A.m*

46、A.n)，和和经典算法的时间复杂度相同经典算法的时间复杂度相同0009012700030008000000000200060Aj123456numberj121102positionj1245660700200000008009000003006120000Browcole12616-234-842346751-12539rowcole15-1221624335943-861-2647练习题w 对稀疏矩阵进行压缩存储目的是（对稀疏矩阵进行压缩存储目的是（ ）。）。【北京工商大学北京工商大学 2001 一、一、1 (3分分)】w A便于进行矩阵运算便于进行矩阵运算 w B便于输入和输出便于输入和

47、输出 w C节省存储空间节省存储空间 w D降低运算的时间复杂度降低运算的时间复杂度答案为：答案为：C练习题 判断w 稀疏矩阵压缩存储后，必会失去随机存取稀疏矩阵压缩存储后，必会失去随机存取功能。（功能。（ ）w 【中科院软件所【中科院软件所 1997 1997 一、一、1 1 （1 1分）】分）】答案为：答案为：对对三元组表上的矩阵乘法运算 602401500100352060008027050CBArowcolerow colerowcole11223254712383 61 1 22 -52 1 33 2 11 1 152 1 42 2 -23 2 6(a)(b)(c)矩阵相乘的经典算法

48、21 ,11,2111221121njmijkBkiAjiCmnBACnknmnmnm必须满足条件：for( i = 0; i m1; i+) for( j= 0; j n2; j+) Cij = 0; for( k = 0; k n1; k+) Cij += Aik * Bkj; 算法的时间复杂度为：算法的时间复杂度为： O(m1 * n1 * n2 )三元组表上的矩阵乘法运算w 稀疏矩阵不能采用经典的矩阵相乘。稀疏矩阵不能采用经典的矩阵相乘。w 原因原因1：无论是否为无论是否为0都要做一次相乘没有意都要做一次相乘没有意义；义；w 原因原因2： 定位定位A的每一行元素与的每一行元素与B的每一

49、列元的每一列元素较困难；素较困难；w 实际上：实际上：为了得到为了得到C的某一个值，只要对的某一个值，只要对A.data中的中的(i,k,eik)找到找到B.data中的（中的（k,j,ekj)相相乘即可。乘即可。这样只需扫描三元组表一次。这样只需扫描三元组表一次。三元组表上的矩阵乘法运算w 扫描扫描A时：为了便于找到时：为了便于找到B.data中第中第k行的第一行的第一个非个非0元素，用向量元素，用向量position，首先求出首先求出B中各行中各行的非的非0元素的个数，存入元素的个数，存入sum 中，然后求得中，然后求得B中中各行的第一个非各行的第一个非0元素在元素在B.data中的位置。

50、中的位置。w 思想：对思想：对A.data中每个元素中每个元素A.datap.e lenAp.1扫描扫描A.data，找出满足找出满足A.datap.col=B.dataq.row的所有的所有q，然后进行然后进行下列计算并累加下列计算并累加A.datap.e*B.dataq.e A的第的第 i 行的第行的第 k 列元素列元素Aik,始终在和始终在和 B 中的第中的第 k 行元素在计算行元素在计算. C的第的第 i 行元素行元素,是是A的第的第 i 行依次和行依次和B中的第中的第 1 列列,第第 2列列,第第 n2 列元素在做运算列元素在做运算.可以考虑按行计算可以考虑按行计算:设置一个数组设置

51、一个数组,用来记录用来记录Aik和和B的第的第k行的乘积行的乘积,当当k从从0到到n1变化时变化时,计算并依次累加即可计算并依次累加即可.for( i = 0; i m1; i+) for( j= 0; j n2; j+) Cij = 0; for( k = 0; k n1; k+) Cij += Aik * Bkj;具体过程0 6 0 00 8 0 27 0 5 0A0 01 00 35- 2B6 02- 40 15Crowcol e 1 2 5 1 4 7 2 1 2 2 3 8 3 3 6rowcol e 1 1 2 1 2 -5 2 1 3 3 2 1rowcol e1 2 52 1

52、3 i=1,sum1=152 1 21 1 2i=2,sum1=41 2 -5i=2,sum2=-102 3 83 2 1+83 3 63 2 1i=3,sum2=61 1 152 1 42 2 -23 2 6pqB的第的第4行没有非零行没有非零元素，不必要计算元素，不必要计算矩阵相乘算法大致过程 C初始化；初始化； If (C是非零矩阵）是非零矩阵） /逐行求积逐行求积 p=0; while(p data的三元组表的三元组表 中（实际上就是压缩存储）中（实际上就是压缩存储）; /while / if三元组表上的矩阵乘法运算改进的三元组表的类型说明如下：改进的三元组表的类型说明如下：defin

53、e MAXSIZE 1000 用户自定义用户自定义define MAXROW 100 用户自定义用户自定义typedef struct 三元组三元组 int row,col; 非零元的行号、列号非零元的行号、列号 ElemType e; 非零元的值非零元的值 Triple;typedef struct Triple dataMAXSIZE; 三元组表三元组表 int positionMAXROW+1;各行第一个非零元素的位置表各行第一个非零元素的位置表 int m,n,len; 矩阵的行数、列数和非零元素个数矩阵的行数、列数和非零元素个数TSMatrix; Positioni表示表示B中第中第

54、i行第一个非行第一个非0 元素在元素在B.data中的序号中的序号Positioni+1-1表示表示B中中第第i行最后一个非行最后一个非0 元素元素在在B.data中的序号中的序号为了表示为了表示B中的最后一行最后一个非中的最后一行最后一个非0元素在元素在B.data中中的序号，在的序号，在position中增加了一个分量，即中增加了一个分量，即B的第的第m2+1行第一个元素的位置，虽然行第一个元素的位置，虽然B中无中无m2+1行行三元组表上的矩阵乘法运算：算法实现int MultMatrix(TSMatrix A, TSMatrix B, TSMatrix *C)采用改进的三元组表表示法，求

55、矩阵乘积采用改进的三元组表表示法，求矩阵乘积C=AB if(A.n!=B.m) return 0;/矩阵相乘的条件矩阵相乘的条件 C-m=A.m; C-n=B.n; C-len=0;/初始化初始化 if(A.len*B.len!=0)/如果有一个为全如果有一个为全0则结果为则结果为0 p=0; while(pA.len) 处理处理A的当前元素的当前元素 crow=A.datap.row; for(ccol=0;ccoln;ccol+) sumccol=0;当前列各元素清零当前列各元素清零 while(pA.len & A.datap.row=crow) brow=A.datap.col; B的

56、当前行等于的当前行等于A的当前元素的列号的当前元素的列号 for(q=B.positionbrow;qB.positionbrow+1;q+) 处理处理B当前行当前行 ccol=B.dataq.col; 乘积元素在乘积元素在C中的列号中的列号 sumccol+=A.datap.e*B.dataq.e; p+; /while(pA.len & A.datap.row=crow) 三元组表上的矩阵乘法运算：算法实现（续） 已经求得已经求得C C中第中第crowcrow即即arowarow行的非零元素行的非零元素 for(ccol=0;ccoln;ccol+) 压缩存储该行非零元到三元组表压缩存储该

57、行非零元到三元组表C.dataC.data中中 if(sumccol) if(+C-lenMAXSIZE) return 0; C-dataC-len.row=crow; C-datac-len.col=ccol; C-dataC-len.e=sumccol; if if while(pA.len)while(pA.len) /if /ifreturn 1;MultiMatrix 即：扫描累加器当即：扫描累加器当前行的各个分量即前行的各个分量即当前行的每列当前行的每列三元组表表示的稀疏矩阵的相加三元组表表示的稀疏矩阵的相加0 0 0 3-0 0 5 0 0 0 0 2 6 0 0 0 A0 0

58、 0 3 0 0 4 0 0 0 0 0 0 0 8 0 B0 0 0 0 0 0 9 0 0 0 0 2 6 0 8 0 CBA大致算法如下Void matradd(TSMatrix A, TSMatrix B, TSMatrix C) /采用三元组顺序方式存储，实现矩阵相加采用三元组顺序方式存储，实现矩阵相加 if (A.m!=B.m | A.n!=B.n) exit(0); 矩阵矩阵C初始化；初始化；/设置设置C的行和列的行和列 if (A.len & B.len) i=1;j=1; while (i=A.len & jnext C. j=j-next w D. j=rj- nextD.

59、 j=rj- next答案为：答案为：A判断题w 数组可看成线性结构的一种推广，因此与数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等线性表一样，可以对它进行插入，删除等操作。（操作。（ ） w 【上海交通大学【上海交通大学 1998 1998 一、一、5 5】答案为：答案为：错错判断题w 一个稀疏矩阵一个稀疏矩阵A Am m* *n n采用三元组形式表示，采用三元组形式表示， 若把三元组中有关行下标与列下标的值互若把三元组中有关行下标与列下标的值互换，并把换，并把m m和和n n的值互换，则就完成了的值互换，则就完成了A Am m* *n n的转置运算。（的转置运算。

60、（ ）w 【西安交通大学【西安交通大学 1996 1996 二、二、8 (38 (3分分) )】答案为：答案为：错错还需要重还需要重新排序新排序数组小结w 了解数组的两种（以行为主、以列为主）了解数组的两种（以行为主、以列为主）存储表示方法，并掌握数组在以行序为主存储表示方法，并掌握数组在以行序为主的存储结构中的地址计算方法；的存储结构中的地址计算方法；w 掌握对特殊矩阵进行压缩存储时的下标变掌握对特殊矩阵进行压缩存储时的下标变换公式；换公式；w 了解稀疏矩阵的压缩存储方法的特点和适了解稀疏矩阵的压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进用范围，领会以三元组表示稀疏矩阵时进行矩