数组和稀疏矩阵

关于数组和稀疏矩阵第1页，共57页，2022年，5月20日，23点32分，星期四5.1.1数组的基本概念

数组是n(n＞1)个相同类型数据元素a0,a1,…,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。由此可见,数组的定义类似于采用顺序存储结构的线性表。第2页，共57页，2022年，5月20日，23点32分，星期四数组具有以下性质：

(1)数组中的数据元素数目固定，一旦定义了一个数组，其数据元素数目不再有增减变化。

(2)数组中的数据元素具有相同的数据类型。

(3)数组中的每个数据元素都和一组唯一的下标值对应。

(4)数组是一种随机存储结构，可随机存取数组中的任意数据元素。第3页，共57页，2022年，5月20日，23点32分，星期四5.1.2数组的存储结构

在一维数组中,假设a0的存储地址由LOC(a0)确定,且每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：

LOC(ai)=LOC(a0)+i*k(0≤i≤n-1)

上式说明,一维数组中任一数据元素的存储地址可直接计算得到,即一维数组中任一数据元素可直接存取。因此,一维数组是一种随机存储结构。同样,二维及多维数组也满足随机存储特性。第4页，共57页，2022年，5月20日，23点32分，星期四对于一个m行n列的二维数组Am×n,有：

将Am*n简记为A,A是这样的一维数组：

A=(a0,a1,…,ai…,am-1)其中,ai=(ai,0,ai,1,…,ai,n－1)(0≤i≤m-1)。第5页，共57页，2022年，5月20日，23点32分，星期四

显然,二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推,任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。第6页，共57页，2022年，5月20日，23点32分，星期四

对于二维数组来说，由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数组元素就有一个行／列次序排放问题。

以行序为主序的存储方式：即先存储第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第7页，共57页，2022年，5月20日，23点32分，星期四

对一个已知以行序为主序的计算机系统中,当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)和每个数据元素所占用的存储单元k确定后,则该二维数组中任一数据元素ai,j的存储地址可由下式确定：

LOC(ai,j)=LOC(a0,0)+[i*n+j]*k

其中n为列数。第8页，共57页，2022年，5月20日，23点32分，星期四

同理可推出在以列序为主序的计算机系统中有：

LOC(ai,j)=LOC(a0,0)+[j*m+i]*k

其中m为行数。第9页，共57页，2022年，5月20日，23点32分，星期四

例5.1对二维数组floata[5][4]计算：

(1)数组a中的数组元素数目；

(2)若数组a的起始地址为2000，且每个数组元素长度为32位(即4个字节)，数组元素a[3][2]的内存地址。

第10页，共57页，2022年，5月20日，23点32分，星期四

解：该数组的元素数目共有5*4=20个。由于C语言采用行序为主序的存储方式,则有：

LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056第11页，共57页，2022年，5月20日，23点32分，星期四5.1.3特殊矩阵的压缩存储

特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，为了节省存储空间,特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律,对它们进行压缩存储，也就是说，使多个相同的非零元素共享同一个存储单元，对零元素不分配存储空间。

特殊矩阵的主要形式有对称矩阵、对角矩阵等，它们都是方阵，即行数和列数相同。第12页，共57页，2022年，5月20日，23点32分，星期四

1.对称矩阵的压缩存储若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i(1≤i,j≤n),则称其为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。这样,就可以将n2个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性,我们以行序为主序存储其下三角(包括对角线)的元素，例如：第13页，共57页，2022年，5月20日，23点32分，星期四15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann

在这个下三角矩阵中，第i行恰有i个元素，元素总数为：n(n+1)/2

因此，我们可以按从上到下、从左到右将这些元素存放在一个向量b[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和b[k]之间找一个对应关系。第14页，共57页，2022年，5月20日，23点32分，星期四

若i≧j，则aij在下三角形中。aij之前的i-1行共有1+2+…+i-1=i(i-1)/2个元素，在第i行上，aij之前有j-1个元素（即ai1,ai2,ai3,…,aij-1），因此有：a11a21a22a31…an1…annk=0123-1i*(i-1)/2+j–1当i>=jj*(j-1)/2+i-1当i<jk=第15页，共57页，2022年，5月20日，23点32分，星期四2.三角矩阵的压缩存储

以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图a所示，它的下三角（不包括主对角线）中的元素均为常数c。下三角矩阵正好相反，它的主对角线上方均为常数c，如图b所示。在大多数情况下，三角矩阵常数为零。

a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩阵(b)下三角矩阵第16页，共57页，2022年，5月20日，23点32分，星期四

三角矩阵的重复元素c可共享一个存储空间，其余元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到b[0..n(n+1)/2]中，其中c存放在最后一个分量中。上三角矩阵中，主对角线之上的第i行(0≦i<n)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。因此，b[k]和aij的对应关系是：i(2n-i+1)/2+j-i当i≦jn(n+1)/2当i>jk=下三角矩阵的存储和对称矩阵类似，b[k]和aij对应关系是：

i(i+1)/2+ji≧jn(n+1)/2i<jk=第17页，共57页，2022年，5月20日，23点32分，星期四3.对角矩阵的压缩存储若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵，其主对角线上下方各有b条次对角线,称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0≤b≤(n-1)/2)的对角矩阵，其|i-j|≤b的元素ai,j不为零,其余元素为零。下图所示是半带宽为b的对角矩阵示意图。第18页，共57页，2022年，5月20日，23点32分，星期四

半带宽为b的对角矩阵

第19页，共57页，2022年，5月20日，23点32分，星期四

a00a01a10a11a12a21a22a23….…..….可用以行序为主序的

an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1

形式存储b[3n-2]中

当b＝1时称为三对角矩阵，如：主对角线下方的元素的下标关系为i=j+1,此时k=3(i-1)+2主对角线上的元素的下标关系为i=j,此时k=3(i-1)+3主对角线下的元素的下标关系为i=j－1,此时k=3(i-1)+4即：k=2i+j第20页，共57页，2022年，5月20日，23点32分，星期四

例5.2

按行优先顺序和按列优先顺序列出四维数组A[2][2][2][2]所有元素在内存中的存储次序。第21页，共57页，2022年，5月20日，23点32分，星期四

解：按行优先的存储次序:A[0][0][0][0],A[0][0][0][1],A[0][0][1][0],A[0][0][1][1],A[0][1][0][0],A[0][1][0][1],A[0][1][1][0],A[0][1][1][1],A[1][0][0][0],A[1][0][0][1],A[1][0][1][0],A[1][0][1][1],A[1][1][0][0],A[1][1][0][1],A[1][1][1][0],A[1][1][1][1]第22页，共57页，2022年，5月20日，23点32分，星期四

按列优先的存储次序:

A[0][0][0][0],A[1][0][0][0],A[0][1][0][0],A[1][1][0][0],A[0][0][1][0],A[1][0][1][0],A[0][1][1][0],A[1][1][1][0],A[0][0][0][1],A[1][0][0][1],A[0][1][0][1],A[1][1][0][1],A[0][0][1][1],A[1][0][1][1],A[0][1][1][1],A[1][1][1][1]第23页，共57页，2022年，5月20日，23点32分，星期四5.2稀疏矩阵

一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t时,称该矩阵为稀疏矩阵。例如一个100×100的矩阵,若其中只有100个非零元素,就可称其为稀疏矩阵。第24页，共57页，2022年，5月20日，23点32分，星期四5.2.1稀疏矩阵的三元组表示

稀疏矩阵的压缩存储方法是只存储非零元素。由于稀疏矩阵中非零元素的分布没有任何规律,所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组(i,j,ai,j)惟一确定,稀疏矩阵中的所有非零元素构成三元组线性表。第25页，共57页，2022年，5月20日，23点32分，星期四

假设有一个6×7阶稀疏矩阵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))第26页，共57页，2022年，5月20日，23点32分，星期四

若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。则三元组顺序表的数据结构可定义如下：第27页，共57页，2022年，5月20日，23点32分，星期四

#defineMaxSize100//矩阵中非零元素最多个数

typedefstruct{inti; //行号

intj; //列号

ElemTypee; //元素值

}Triple; //三元组定义

typedefstruct{intmu; //行数值

intnu; //列数值

inttu; //非零元素个数

Tripledata[MaxSize+1];}TSMatrix;//三元组顺序表定义

第28页，共57页，2022年，5月20日，23点32分，星期四ije121213931-361432452181154-7M.dataM.mu=6M.nu=7M.tu=8第29页，共57页，2022年，5月20日，23点32分，星期四用常规的二维数组表示时的算法

其时间复杂度为:O(M.mu×M.nu)for(col=1;col<=M.nu;++col)

for(row=1;row<=M.mu;++row)T[col][row]=M[row][col];（1）用三元组表示时矩阵转置运算的实现用三元组表示时如何实现？第30页，共57页，2022年，5月20日，23点32分，星期四方法1：ije121213931-3614324521811564-7M.dataM.mu=6M.nu=7M.tu=8转置后得Tijv13-31615211225183194246-76314T.dataT.mu=7T.nu=6T.tu=8第31页，共57页，2022年，5月20日，23点32分，星期四StatusTransposeSMattrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;

//q表示下一次找到的非零元在T.data中的下标for(col=1;col<=M.nu;col++)for(p=1;p<=M.tu;p++){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMattrix其时间复杂度为:O(M.nu×M.tu)，若M.tu与M.muM.nu同数量级时，有O(M.mu×M.nu2)第32页，共57页，2022年，5月20日，23点32分，星期四方法二：快速转置其基本思想是对M.data仅扫描一遍，在扫描到每一个元素时将其放在T.data的合适的位置上。cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colM.nu)1357889colnum[col]cpot[col]12223241506170第33页，共57页，2022年，5月20日，23点32分，星期四方法2（快速转置）：ije121213931-3614324521811564-7M.dataM.mu=6M.nu=7M.tu=8转置后得TT.mu=7T.nu=6T.tu=8T.dataijv211231913-3631434242518161546-7123456781357889colnum[col]cpot[col]1222324150617046297538第34页，共57页，2022年，5月20日，23点32分，星期四1）根据M的mu、nu和tu的值，对T的mu、nu和tu赋相应的值；2）初始化数组num;3）扫描M.data，计算num的值；4）根据num的值，计算cpot的值；5）扫描M.data一遍，将非零元放在T.data的合适的位置上。算法描述如下页所示：第35页，共57页，2022年，5月20日，23点32分，星期四StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;col++)num[col]=0;for(t=1;col<=M.tu;t++)++num[M.data[t].j];cpot[1]=1;//求第col列中第一个非零元在T.data中的序号

for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(t=1;t<=M.tu;t++){col=M.data[t].j;q=cpot[col];T.data[q].i=M.data[t].j;T.data[q].j=M.data[t].i;T.data[q].e=M.data[t].e;++cpot[col];}}returnOK;}//FastTransposeSMatrix时间复杂度为：第36页，共57页，2022年，5月20日，23点32分，星期四分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……第37页，共57页，2022年，5月20日，23点32分，星期四

三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。2.行逻辑链接的顺序表typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组表

intrpos[MAXRC+1];//各行第一个非零元的位置表

intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。第38页，共57页，2022年，5月20日，23点32分，星期四（1）取值运算，给定一组下标，求矩阵的元素值voidvalue(RLSMatrixM,intr,intc,ElemType&e){p=M.rpos[r];//第r行第一个非零元的位置

q=…;//第r行最后一个非零元的位置

while(p<=q&&M.data[p].j<c)p++;if(p>q){e=0;return;}if(M.data[p].j==c)e=M.data[p].e;elsee=0;}//value第39页，共57页，2022年，5月20日，23点32分，星期四for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){Q[i][j]=0;for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];}其时间复杂度为:O(m1×n2×n1)(2)矩阵乘法运算:2.1精典乘法运算算法：第40页，共57页，2022年，5月20日，23点32分，星期四M1002000N=3×44×2Q=M

×N06-1004Q=3×2100010001000A=B=110000003×44×2C=A

×B111111C=3×2第41页，共57页，2022年，5月20日，23点32分，星期四M、N和Q的三元组表示分别如下：ije131452-1312ije2221131-2324ije2621-1324M.dataN.dataQ.dataQ[i][j]=第42页，共57页，2022年，5月20日，23点32分，星期四

Q初始化;ifQ是非零矩阵{//逐行求积

for(arow=1;arow<=M.mu;++arow){//处理M的每一行

ctemp[]=0;//累加器清零计算Q中第arow行的积并存入ctemp[]中；将ctemp[]中非零元压缩存储到Q.data；

}//forarow}//if

基本思想：…………第43页，共57页，2022年，5月20日，23点32分，星期四StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){//求矩阵乘积Q=M×N,采用行逻辑链接存储表示

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//初始化Q，Q.tu表示现已存入Q中的非零元个数

if(M.tu*N.tu!=0){//Q是非零矩阵

for(arow=1;arow<=M.mu;++arow){

处理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrix第44页，共57页，2022年，5月20日，23点32分，星期四

ctemp[]=0;//当前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;//Q的第arow行在Q.data中的位置

if(arow<M.mu)tp=M.rpos[arow+1];else{tp=M.tu+1}for(p=M.rpos[arow];p<tp;++p){

//对当前行中每一个非零元给它该乘的元素乘一遍

brow=M.data[p].j;if(brow<N.mu)t=N.rpos[brow+1];else{t=N.tu+1}//t为本行最后一个非零元的下一位

for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘积元素在Q中列号

ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq

处理的每一行M第45页，共57页，2022年，5月20日，23点32分，星期四}//求得Q中第crow(=arow)行的非零元for(ccol=1;ccol<=Q.nu;++ccol)//压缩存储该行非零元if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]=（arow,ccol,ctemp[ccol]）;}//if第46页，共57页，2022年，5月20日，23点32分，星期四分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数M.tu=Mmn，N中非零元的个数

N.tu=Nnp，相乘算法的时间复杂度就是(mp(1+nMN))

，当M<0.05和N<0.05及n<1000时，相乘算法的时间复杂度就相当于(mp)。第47页，共57页，2022年，5月20日，23点32分，星期四

思考：如果两个稀疏矩阵M和N是可乘的，且M和N都以行逻辑链接的三元组顺序表进行存储，编写一个类-C算法，求这两个矩阵的相乘积Q，Q以二维数组的形式存储（即Q不进行压缩）。第48页，共57页，2022年，5月20日，23点32分，星期四//-------稀疏矩阵的十字链表存储表示---------typedefstructOLNode{inti,j;Elemtypee;structOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;//行和列链表头指针向量基址

intmu,nu,tu;}CrossList3.十字链表e结点结构示意图:ijerightdown第49页，共57页，2022年，5月20日，23点32分，星期四30050-100200011314522-1312^^^^^^^第50页，共57页，2022年，5月20日，23点32分，星期四3.1创建一个稀疏矩阵的十字链表存储结构基本思想:创建一个稀疏矩阵M的十字链表存储结构的过程就是给M的5个域赋确切值的过程。1）输入M的行m、列n和非零元的个数t；2）申请存储行、列链表头指针的存储空间；3）建立m+n个空链表；4）输入一个非零元的(行，列，值）；5）产生一个结点p；并给其i,j,e赋相应值；6）将p插在相应行的适当位置上；7）将p插在相应列的适当位置上；8）重复4）、5）、6）、7）步，直到非零元输入完为止。第51页，共57页，2022年，5月20日，23点32分，星期四StatusCreatMatrix_OL(CrossList&M){//创建稀疏矩阵M，采用十字链表存储表示

//if(M)free(M);错！删除这一行P104scanf(&m,&n,&t);//输入行、列和非零元的个数

M.mu=m;M.nu=n;M.tu=t;if(!(m.rhead=(OLink*)malloc((m+1)*sizeof(Olink)))exit(OVERFLOWER);//0号单元不用

if(!(m.chead=(OLink*)malloc((n+1)*sizeof(Olink)))exit(OVERFLOWER);//0号单元不用

M.rhead[]=NULL;M.chead[]=NULL;//初始化头指针，