数据结构第5章数组和稀疏矩阵

数组特殊矩阵的压缩存储稀疏矩阵数组数组是n(n1)个相同类型数据元素a1,a2,…,an构成的有限序列。数组的性质：（1）数组中的数据元素数目固定。（定长）（2）数组中的数据元素具有相同的数据类型。（3）数组中的每个数据元素都和一组唯一的下标值对应。（4）数组是一种随机存储结构。可以随机存取数组中的任意数据元素。a33a322数组一维数组：a5m多维数组：m=8ADTList{数据对象:D={aj1,j2,j3,…,jd|ji=1,2,…,bi,i=1,2,…,d}数据关系:R={r1,r2,…,rn}ri,=aj1,j2,,,ji,…,jn,aj1,j2j,,,ji+1,…,jn|1jkbk,1kb且ki,1jibi-1,I=2,3,…d基本运算:Value(A,index1,index2,…,indexd);Assign(A,e,index1,index2,…,indexd);Adisp(A,b1,b2,…bd)}抽象数据类型数组的定义逻辑结构一维数组：aiai-1ai+1线性结构二维数组：aijaij-1aij+1ai-1jai+1j三维数组：aijkaij-1kaij+1kaijk+1aijk-1ai-1jkai+1jk线性结构推广数组的存储结构由于数组主要随机访问，没有插入和删除，所以采用顺序方式存储。一维数组的存储：按次序依次存储在一组连续的存储空间中。LOC(ai)=LOC(a1)+(i-1)*k多维数组的存储：问题：计算机内存是一维，如何存储多维数组。要求：将多维数组中每个元素按某种次序列排列成为一维结构。两种方法：以行为主序顺序和以列为主序顺序。二维数组行优先顺序存储结构a11a1nai1aijainam1amnAmn=Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*d每个元素占存储空间大小为dLoc(aij)=首地址+前面所有元素所占存储空间的总数a11a1n第1行ai1ain第i行am1amn第m行前i-1行：有(i-1)*n个元素第i行：有j-1元素aij前共有(i-1)*n+j-1个元素？问题：若第一个元素为a00（即下标为00）则Loc(aij)=?行aij前共有i行元素本行前有是j个元素Loc(aij)=Loc(a00)+(i*n+j)*dLoc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*da11am1第1列a1jamj第j列a1namn第n列前j-1列：有(j-1)*m个元素第j列：有i-1元素aij前共有(j-1)*m+i-1个元素每个元素占存储空间大小为dLoc(aij)=首地址+前面所有元素所占存储空间的总数？问题：若第一个元素为a00（即下标为00）则Loc(aij)=?列aij前共有j列元素本列前有是i个元素Loc(aij)=Loc(a00)+(j*m+i)*da11a1nai1aijainam1amnAmn=二维数组列优先顺序存储结构三维数组AmnpLoc(aijk)=Loc(a111)+[(i-1)*n*p+(j-1)*p+k-1)]*d行优先顺序：Loc(aijk)=Loc(a111)+[(i-1)+(j-1)*m+(k-1)*m*n]*d列优先顺序：a111…a11pa121…a12p…a1n1…a1npa211…a21p…amn1…amnpa111…am11a121…am21…a1n1…amn1a112…am12…a1np…amnp特殊矩阵的压缩存储a11a1nai1aijainam1amnAmn=通常可以采用二维数组存储矩阵空间复杂度：S(m,n)=O(m*n)问题：（1）矩阵中有大量相同的非零元素这样仍造成空间极大浪费多个相同的非零元素只分配一个存储空间矩阵压缩存储原则特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。对称矩阵、三角矩阵、对角矩阵3330201213041023520107931223911815384A对称矩阵特点：aij=aji只需存储上三角或下三角中的元素nnnnnnnnaaaaaaaaaaaaaaaa321333323122322211131211ASAa11a21a22a31a32a33a41a42a43……ann0123456789n(n+1)/2-1a32和a23存储在SA[5]矩阵中n*n个元素只需要n(n+1)/2个存储单元SA[k]=aijK=i(i-1)2+j-1ijijj(j-1)2+i-1nnnnnacccaaccaaacaaaa333223221131211Annnnnaaaacaaaccaaccca321333231222111A下三角矩阵上三角矩阵datatypeSA[]n(n+1)2+1(i-1)(2n-i+2)2+j-i+1ijijK=n(n+1)2datatypeSA[]n(n+1)2+1i(i-1)2+j-1ijijK=n(n+1)2三对角矩阵nnnnnnnnnnaaaaaaaaaaaaa111121343332232221121100000000000000000A01234567893n-2第1行第2行第3行第n行SAa11a12a21a22a23a32a33a34…ann-1ann|i-j|1K=2i+j-2-1|i-j|1aij=0稀疏矩阵设矩阵Am*n中有s个非零元素，若s远远小于矩阵元素的总数（即sm*n),则称A为稀疏矩阵。0094000006000200030180050Am=5,n=5,s=8sm*n由于非零元素在矩阵中的位置没有规律，所以不但要存储非零元素的值，而且还要存储其在矩阵中的位置。三元组（i,j,aij)(1,2,5)(1,5,8)(2,1,1)(2,3,3)(3,2,-2)(4,1,6)(5,2,4)(5,3,-9)存储方式：三元组表和十字链表0094000006000200030180050A12515821123332-241652453-9三元组表－－稀疏矩阵的顺序存储方式typedefstruct{intr,c;/*行号、列号*/ElemTyped;/*非零元素值*/}TupNode;typedefstruct{introws,cols,nums;/*行数、列数、非零元素个数*/TupNodedata[maxsize];/*三元组表*/}TSMatrix;ijv12345678smax稀疏矩阵的数据类型便于随机存取，但不适合矩阵的变化（即非零元素的位置及个数的变化）。21551812132323-214625435-912114621523-225432335-951812515821123332-241652453-9ijv12345678maxsize0094000006000200030180050A0000800000900304020506010Bijv12345678maxsizeA(i,j,aij)B(j,i,bij)？行优先变成列优先（1）全部传送（2）分列传送？T=O(n*t)效率低求转置矩阵12114621523-225432335-951812515821123332-241652453-9ijv12345678maxsizeijv12345678maxsizepot[1]pot[2]pot[3]pot[4]pot[5]最好先确好A中各列传送的起始位置设pot[n]用于存储各列的起始位置pot[1]=1pot[col]=pot[col-1]+num[col-1](num[n]各列非零个数）col12345num23201pot13688分析：求num[]T=O(t)求pot[]T=O(n)三元传送T=O(t)T=O(n+t)0094000006000200030180050A十字链表－－稀疏矩阵的链式存储方式非零结点结构：rowcolvaluedownright指向本行下一个非零结点分析：将同一行的非零结点链成一个循环单链表将同一列的非零结点链成一个循环单链表要求：每个结点设两个指针分别用于行和列链接为运算方便每个链表设一个头结点00linkdownright指向本列下一个非零结点0094000006000200030180050A12521123332-241652453-91580000000000H1H2H3H4H5H1H2H3H4H50000000000注：i行头结点中只用rptr,i列头结点中只用cptr,则可合用共享。00downright指向本行第一个非零结点指向本列下一个非零结点行列头结点利用这个数据域设指针将各行列头结点链接。55Hmlink行列表头结点存储矩阵的行数和列数，Hm确定十字链表结点结构rowcolvalue/linkdownright非零结点：（row,col,value)为非零元素的三元组。行列头结点：row=col=0link指向下一个行列头结点。行列表头结点：row为矩阵的行数col为阵的列数结点数据类型typedefstructmtxn{introw,col;structmtxn*right,*down;union{intvalue;structmtxn*link;}tag;}MatNode;小结数组：逻辑结构是线性结构的推广。数组的特点是定长。（没有插入和删除）数组采用顺序方式存储，二种排列方式：以行为主序排列和以列为主序排列。特殊矩阵的压缩存储：多个相同元素分配一个存储单元对称矩阵、三角矩阵、对角矩阵稀疏矩阵的压缩存储：零元素不分配存储空间，只存储非零元素的三元组。顺序方式：三元组表链式方式：十字链表