数据结构-第七周-稀疏矩阵课件

矩阵是一个具有m行n列的数据表，共包含有m*n个元素，每个元素处在确定行和列的交点位置上，与一对行号和列号唯一对应。

矩阵是很多科学与工程计算问题中研究的数学对象，在用高级语言编程时，一般采用二维数组来存储矩阵。

矩阵 矩阵是一个具有m行n列的数据表，共包含有m*n个元素，每个普通矩阵的完全存储如果矩阵中的每个元素的值都是不能确定的值，那么存储这样的矩阵时，每个元素都必须存储，即需要完全存储。

用高级语言描述时，就是使用二维数组的形式存储矩阵。普通矩阵的完全存储如果矩阵中的每个元素的值都是不能确定的值，有的矩阵中，非零元素非常少---稀疏矩阵还有一些矩阵的元素分布有一定的规律---特殊矩阵（比如对称矩阵、三角矩阵）特殊矩阵和稀疏矩阵有的矩阵中，非零元素非常少---稀疏矩阵特殊矩阵和稀疏矩阵3

6

4

7

86

2

8

4

24

8

1

6

97

4

6

0

58

2

9

5

7对称矩阵3c

c

c

c6

2

c

c

c48

1

c

c7

4

6

0

c8

2

9

5

7三角矩阵特殊矩阵36478对称矩阵3cccc三a00a010

0

0a10a11

a120

00a21

a22

a23000

a32

a33

a340

0

0

a43

a44对角矩阵特殊矩阵a00a01000对角矩阵特殊矩阵15000210

000000

010600

0000509

00000稀疏矩阵稀疏矩阵15000210稀疏矩阵稀对于特殊矩阵和稀疏矩阵若仍采用二维数组形式存放，将造成存储单元的很大浪费。可以利用这些矩阵的特点和规律，只存储部分元素，从而提高存储空间的利用率。矩阵的压缩存储对于特殊矩阵和稀疏矩阵矩阵的压缩存储特殊矩阵和稀疏矩阵的压缩存储 在对特殊矩阵和稀疏矩阵进行存储时，为了节省存储空间，可以对这类矩阵进行压缩存储。

压缩存储的基本思想是：⑴多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。

特殊矩阵和稀疏矩阵的压缩存储 在对特殊矩阵和稀疏矩阵进行对称矩阵的压缩存储3647862842481697460582957A＝n阶对称矩阵（方阵）特点：aij=aji如何压缩存储？只存储下三角部分的元素或是上三角部分的元素，使得每两个对称元素共享一个存储空间。对称矩阵的压缩存储36478A＝n阶对称矩阵（方阵）压缩存储后节省了多少空间？对于一个n阶对称矩阵，如果完全存储需要n2个存储空间；如果压缩存储，需要n(n+1)/2个存储空间。对称矩阵的压缩存储3647862842481697460582957A＝压缩存储后节省了多少空间？对于一个n阶对称矩阵，如果完全存储定义一个一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，那么对称矩阵A中任一元素aij和sa[k]之间的对应关系如何？对称矩阵的压缩存储定义一个一维数组sa[n(n+1)/2]作为n阶对称矩阵A的(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的下标=阴影部分的面积=

i×(i+1)/2+j

0…

i

n-10…j…n-1

aij每行元素个数12…iaij在本行中的序号aij第0行第1行…第i-1行对称矩阵的压缩存储

(a)下三角矩阵(b)存储说明对于下三角中的元素aij（i>=j），在一维数组sa中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i

对称矩阵的压缩存储

第1行第n-1行第0行

a00

a10

a11

a20

a21

a22

aij…

a

n-10

an-11…

an-1n-1…第2行012345kn(n+1)/2-1对于下三角中的元素aij（i>=j），在一维数组sa中的下标例：将压缩存储在一维数组a中的4x4阶对称矩阵按矩阵格式输出。inti,j;for(i=0;i<4;i++){for(j=0;j<4;j++)if(i>=j)cout<<a[i*(i+1)/2+j];/*输出主对角线以及主对角线以下元素*/else

cout<<a[j*(j+1)/2+i];/*输出主对角线以上元素*/cout<<endl;}例：将压缩存储在一维数组a中的4x4阶inti,j;三角矩阵的压缩存储3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩阵34810c2946c

c１57c

c

c08c

c

c

c7(b)上三角矩阵n阶上（下）三角矩阵是指下（上）三角（不包括主对角线）中的元素均为常数c三角矩阵的压缩存储3cccc(a)下三角矩阵的压缩存储3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩阵34810c2946c

c１57c

c

c08c

c

c

c7(b)上三角矩阵如何压缩存储三角矩阵？可以只存储上三角（或下三角）部分的元素，对于常量c多开辟一个空间来存储。三角矩阵的压缩存储3cccc(a)下下三角矩阵中任一元素aij在一维数组中的下标k与i、j的对应关系：i×(i＋1)/2＋j

当i≥jn×(n＋1)/2

当i＜jk=下三角矩阵的压缩存储012345

k

n(n+1)/2-1n(n+1)/2第1行第0行

a00

a10

a11

a20

a21

aij…

an-1n-1…第2行

c

a22存储下三角元素对角线上方的常数——只存一个数据元素sa[n(n+1)/2]用于存放常量c下三角矩阵中任一元素aij在一维数组中的下标k与i、j的对应矩阵中任一元素aij在数组中的下标k与i、j的对应关系：

i×(2n-i+1)/2+j-i

当i≤jn×(n＋1)/2

当i＞jk=上三角矩阵的压缩存储存储上三角元素对角线上方的常数——只存一个数据元素sa[n(n+1)/2]用于存放常量c矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i对角矩阵压缩存储对角矩阵：n阶对角矩阵是指所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

对角矩阵压缩存储对角矩阵：n阶三对角矩阵：n阶三对角矩阵的非零元素仅出现在主对角线(aii,0<=i<=n-1)上以及紧邻主对角线上面的那条对角线上（aii+1,0<=i<=n-2)和紧邻主对角线下面的那条对角线上（ai+1i,0<=i<=n-2)

a00

a01

000a10

a11

a12

000a21

a22

a23

000

a32

a33

a34000a43

a44A=5阶三对角矩阵非零元素个数是？当|i-j|>1时，元素aij=0n阶三对角矩阵：n阶三对角矩阵的非零元素仅出现在主对角线(a元素aij与一维数组下标k的关系：k=2+3(i－1)+(

j－i+1)=2i+j

(b)一维数组元素sa[k]和矩阵元素aij的对应关系(c)压缩到一维数组中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112三对角矩阵的压缩存储(a)三对角矩阵

0

00

000

000

000

A=a00

a01a10

a11

a12a21

a22

a23a32

a33

a34a43

a44元素aij与一维数组下标k的关系：(b)一维数组元素sa稀疏矩阵的压缩存储1500000

0

0

00110

000600

0000009

00000A=若矩阵Amxn中的非零元素个数非常少，且非零元素的分布没有任何规律，则称该矩阵为稀疏矩阵。稀疏矩阵的压缩存储150000稀疏矩阵的压缩存储1500000

0110000

000600

0000009

00000A=如何只存储非零元素？稀疏矩阵中的非零元素的分布没有规律。稀疏矩阵的压缩存储150000由于稀疏矩阵中非零元素的分布没有规律，因此在存储非零元素的值的同时，还必须记下该非零元素在矩阵中的行号和列号。稀疏矩阵的压缩存储定义三元组：稀疏矩阵中的每个非零元素对应一个三元组：(行号，列号，非零元素值)——三元组由于稀疏矩阵中非零元素的分布没有规律，因此在存储非零元素的值三元组表：将稀疏矩阵的所有非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个三元组线性表。三元组表：((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))如何存储三元组表？三元组表：将稀疏矩阵的所有非零元素对应的三元组所构成的集合，若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵示例A5×6=003513053100017000600200210000100800rowcolval数组b[m]0352011330255033101417415622620527211381049834行号：0到4列号：0到5该三元组线性表按“行序为主序”，用一维数组进行存放按“列序为主序”的三元组线性表示例A5×6=003513053100017000600227typedefstruct

//三元组的类型定义{

introw; //非零元素行号 intcol;//非零元素列号

ElemTypeval; //非零元素值}tupletype;#defineMAXSIZE100;

typedefstruct //三元组顺序表存储结构定义{ tupletypedata[MAXSIZE];//非零元素的三元组表

intrnum;

//矩阵行数 intcnum; //矩阵列数 intlen; //矩阵总非零元素个数

}table;三元组顺序表存储结构定义typedefstruct //三元组的类型定义#def三元组顺序表采用顺序存储结构存储三元组表

0015

0322

05-15

1111

123

236

4091

空空空闲闲闲rowcole0123456MAXSIZE-11500220-15

0113000

000600

00000091

00000A=5（矩阵的行数）6（矩阵的列数）7（非零元个数）三元组顺序表采用顺序存储结构存储三元组表0(1)从一个稀疏矩阵创建其对应三元组表以行序方式扫描二维稀疏矩阵A,将其非零的元素插入到三元组顺序表m的后面。算法如下：#defineM16#defineN17

voidCreatTable(table*m,ElemTypeA[M1][N1]){ inti,j; m->rnum=M1;m->cnum=N1;m->len=0; for(i=0;i<M1;i++) {for(j=0;j<N1;j++) if(A[i][j]!=0)/*只存储非零元素*/{ m->data[m->len].row=i;

m->data[m->len].col=j;

m->data[m->len].val=A[i][j];

m->len++; } }}(1)从一个稀疏矩阵创建其对应三元组表

(2)取值操作，从三元组表中取出稀疏矩阵指定位置的元素值算法思路：先在三元组m中找到指定的位置,然后将该处的元素值赋给x。

intgetvalue(table*m,ElemType*x,inti,intj){intk=0;

if(i>=m->rnum||j>=m->cnum)return0;while(k<m->len&&i>m->data[k].row)k++;//找第i行while(k<m->len&&j>m->data[k].col)k++;//找第j列

if(m->data[k].row==i&&m->data[k].col==j)//元素存在

{*x=m->data[k].val;return1;}elsereturn0;}(2)取值操作，从三元组表中取出稀疏矩阵指定位置的元(3)稀疏矩阵赋值，将给定值，赋值到三元组表的指定位置算法思路：先在三元组表m中找到指定的位置k,若指定位置已经有值，则用给定值替换原有值，否则，将指定位置k及其后面的元素后移一位,然后将给定的元素值x插入到指定位置处。

intputValue(table*m,ElemTypex,inti,intj){inti,k=0;

if(i>=m->rnum||j>=m->cnum)return0;while(k<m->len&&i>m->data[k].row)k++;//找第i行while(k<m->len&&j>m->data[k].col)k++;//找第j列if(m->data[k].row==i&&m->data[k].col==j)//元素存在m->data[k].val=x; //用给定值x替换原值(3)稀疏矩阵赋值，将给定值，赋值到三元组表的指定位置else/*元素不存在时，将其插入*/{for(i=m->len-1;i>=k;i--)

/*元素后移*/{m->data[i+1]=m->data[i];}

m->data[k].row=i;

m->data[k].col=j;

m->data[k].val=x;

m->len++;}return1;}else/*元素不存在时，将其插入*/

(4)按矩阵格式输出以三元组顺序表存储的稀疏矩阵算法思路：对稀疏矩阵中的每个元素，从头到尾扫描三元组m,若在三元组表中存在，则输出其元素值，否则输出0。

voidDispTable(table*m)

{

inti,j,k,e;for(i=0;i<m->rnum;i++)

{for(j=0;j<m->cnum;j++)

{e=0;

for(k=0;k<m->len;k++)

if(i==m->data[k].row&&j==m->data[k].col)

{e=m->data[k].val;break;}

cout<<e<<"";

}

cout<<endl;}

}(4)按矩阵格式输出以三元组顺序表存储的稀疏矩阵

(5)矩阵转置对于一个m×n的稀疏矩阵Am×n,其转置矩阵是一个n×m的稀疏矩阵Bn×m。矩阵正常存储时，转置的一般算法？(5)矩阵转置矩阵正常存储时，转置的一般算法？

(5)稀疏矩阵Am×n用三元组顺序表ta存储，实现对稀疏矩阵的转置算法思路（1）：显然，稀疏矩阵的转置依旧是稀疏矩阵。

稀疏矩阵Bn×m是稀疏矩阵Am×n的转置矩阵,假设使用三元组表ta存储稀疏矩阵A，如何得到存储稀疏矩阵B的三元组表tb简单方法是：将存储存储稀疏矩阵Am×n的三元组表ta的行列号互换就可以得到转置后的三元组表tb(5)稀疏矩阵Am×n用三元组顺序表ta存储，实现对稀A3×4=0091250000106rowcolval三元组顺序表ta092011230250131124236B4×3=0500019001206rowcolval三元组顺序表tb090211203251031214326三元组表ta的行列号互换A3×4=0091250000106rowcolv

(5)稀疏矩阵转置(互换行列号）voidtrans(table*ta,table*tb)

{ inti;

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len; for(i=0;i<ta->len;i++)

{

tb->data[i].row=ta->data[i].col; tb->data[i].col=ta->data[i].row; tb->data[i].val=ta->data[i].val;}}算法缺点：无法保证三元组表tb也是以“行序为主序”进行存放(5)稀疏矩阵转置(互换行列号）算法缺点：算法思路（2）：为了保证三元组表tb也是以“行序为主序”进行存放，按照三元组ta的列序（即转置后三元组表tb的行序）进行转置。即将稀疏矩阵A，按照列序将每列中的非零元素，转置后依次送入三元组表tb中存储，这样得到的三元组表tb恰好是以“行序为主序”。具体过程：第一次扫描三元组表ta时，逐个找出所有列号为0的三元组，转置后按顺序送入三元组表tb中；同理，第二遍扫描三元组表ta,逐个找出所有列号为1的三元组，转置后按顺序送入三元组表tb中；反复进行，将所有列号都进行一遍。最后一遍扫描三元组表tb,逐个找出所有列号为cunm-1的三元组，转置后按顺序送入三元组表tb中。

(5)稀疏矩阵Am×n用三元组顺序表ta存储，实现对稀疏矩阵的转置算法思路（2）：(5)稀疏矩阵Am×n用三元组顺序表tA3×4=0091250000106rowcolval三元组顺序表ta092011230250131124236B4×3=0500019001206rowcolval三元组顺序表tb01234对A逐列转置即：逐行得到B对ta按照列号从0到cnum-1依次扫描？A3×4=0091250000106rowcolv

(5)稀疏矩阵转置（逐行得到B）voidtrans(table*ta,table*tb){intk,b,q;

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len;(5)稀疏矩阵转置（逐行得到B）q=0； /*q为tb->data的下标*/if(tb->len!=0)

{for(k=0;k<ta->cnum;k++)

for(p=0;p<ta->len;p++)/*p为ta->data的下标*/ if(ta->data[p].col==k)

{

tb->data[q].row=ta->data[p].col;

tb->data[q].col=ta->data[p].row;

tb->data[q].val=ta->data[p].val; q++;

}

}}q=0； /*q为tb->data的下标*/

以上算法的时间复杂度为O(ta->cnum*ta->len)而将二维数组存储在一个m行n列矩阵中时,其转置算法的时间复杂度为O(m*n)当非零元素个数较小时，O(ta->cnum*ta->len)优于O(m*n)以上算法的时间复杂度为算法思路（3）：分段定位总体思路：转置时，对三元组表ta中的三元组依次进行转置，转置后的三元组直接放到对应稀疏矩阵B的三元组表tb中的分段位置上。为了能将待转置的三元组表ta中的元素一次定位到三元组表tb的正确位置，需要预先对三元组表tb进行分段定位。1）预先处理阶段(a)计算稀疏矩阵A每一列中非零元素的个数（即：A转置后的稀疏矩阵B每一行中非零元素的个数）设置一个数组num[]来存放这些数。例如：num[k]中存放的是矩阵A中第k列的非零元素的个数（即：矩阵B中第k行的非零元素的个数）

(5)稀疏矩阵Am×n用三元组顺序表ta存储，实现对稀疏矩阵的转置算法思路（3）：分段定位(5)稀疏矩阵Am×n用三元组算法思路（3）：分段定位1）预先处理阶段(b)计算稀疏矩阵A每一列中的第一个非零元素在三元组表tb中的正确位置（即：A转置后的矩阵B每一行中的第一个非零元素在三元组表tb中的正确位置）设置一个数组pot[]来存放这些位置。例如：pot[k]中存放的是矩阵A中第k列中的第一个非零元素在三元组表tb中的正确位置算法思路（3）：分段定位A5×6=003513053100017000600002102000100800rowcolval0352011330255033101417415622621137203381049834三元组顺序表ta1、计算数组num[]num[]数组初值为0；将三元组表ta扫描一遍，对于其中列号为k的元素，给相应的num[k]加1。2、计算数组pot[]pot[0]=0;pot[k]=pot[k-1]+num[k-1];//k>=1A5×6=003513053100017000600002k012345num[k]212311pot[k]0235891）预先处理阶段预先处理阶段得到一个分段定位的结果k012345num[k]212311pot[k]02358算法思路（3）：分段定位2）转置阶段对三元组表ta进行扫描。数组pot[]中的值记录了矩阵A中每一列的第一个非零元素在三元组表tb中的正确位置。每当矩阵A中第k列有一个非零元素存入到三元组表tb时，将pot[k]++，即：pot[k]始终存放矩阵A第k列中的下一个非零元素的正确位置。因此，通过pot[k]可以得到三元组表ta中每个元素转置加入到三元组表tb时的正确位置。算法思路（3）：分段定位

(5)稀疏矩阵转置（分段定位）voidtrans(table*ta,table*tb)

{intk,q,i;

intnum[N],pot[N];

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len;(5)稀疏矩阵转置（分段定位）for(k=0;k<ta->cnum;k++) /*初始化num[]为0*/{ num[k]=0; }for(i=0;i<ta->len;i++)

/*将三元组表ta扫描一遍，对于其中列号为k的元素，给相应的num[k]加1。*/{ num[ta->data[i].col]++; }pot[0]=0;for(k=1;k<ta->cnum;k++)

/*计算pot[]各数组元素的值*/{ pot[k]=pot[k-1]+num[k]; }for(p=0;i<ta->len;p++){ j=ta->data[p].col; q=pot[j];

tb->data[q].row=ta->data[p].col; tb->data[q].col=ta->data[p].row; tb->data[q].val=ta->data[p].val;

pot[j]++;

/*矩阵A本列上下一个非零元素的位置，即矩阵B本行上下一个非零元素的位置*/} }for(k=0;k<ta->cnum;k++) /*初始

以上算法的时间主要耗费在四个并列的单循环上，这四个并列的单循环分别循环了：ta->cnum、ta->len、ta->cnum、ta->len次，因此总的时间复杂度为：O(ta->cnum+ta->len)以上算法的时间主要耗费在四个并列的单循环上，除了顺序存储，也可以把稀疏矩阵按链式存储结构进行压缩存储。除了顺序存储，也可以把稀疏矩阵按链式存储结构进行压缩存储。稀疏矩阵的三元组线性表的链式存储1、简单链式存储稀疏矩阵A的每个非0元素对应一个结点，结点含有的域为:row(行号)、col(列号),val(元素值),next(链域)。将所有的结点串成一个链表。稀疏矩阵简单链式存储示例稀疏矩阵的三元组线性表的链式存储1、简单链式存储稀疏矩阵A的稀疏矩阵的三元组线性表的链式存储2、行链表组将稀疏矩阵Am×n每一行中非零元素对应的结点构成一个链表，m个行链表形成一个链表组-----行链表组即：创建一个指针数组，数组元素中存放的就是某一行链表的第一个结点的地址，即该行链表的头指针。例如：ah[i]是第i个行链表的头指针稀疏矩阵的三元组线性表的链式存储2、行链表组将稀疏矩阵Am×3、稀疏矩阵的正交链表（十字链表）存储与实现正交链表存储思路是：为稀疏矩阵的每一行非零元素设置一个单独链表,同时也为每一列非零元素设置一个单独链表。这样稀疏矩阵的每一个非零元素就同时包含在两个链表中,即：每一个非零元素同时包含在所在行的行链表中和所在列的列链表中。从而降低了链表的长度，也方便了行方向和列方向的搜索。稀疏矩阵的三元组线性表的链式存储3、稀疏矩阵的正交链表（十字链表）存储与实现稀疏矩阵的三元组采用正交链表存储结构来存储稀疏矩阵：稀疏矩阵每个非零元素存储为一个链表结点结点结构为：rowcolvaldownrightrow：存储非零元素的行号col：存储非零元素的列号val：存储非零元素的值right：指针域，指向同一行中的下一个非零元素结点down：指针域，指向同一列中的下一个非零元素结点采用正交链表存储结构来存储稀疏矩阵：rowcolvaldow

202∧M=300501002000

003

035∧∧

111∧∧∧稀疏矩阵的压缩存储——正交链表∧存储所有列链表的头指针的指针数组存储所有行链表的头指针的指针数组任一非零元素M[i][j]所对应的结点，既处在第i-1行的行链表上，又处在第j-1列的列链表上202∧M=3005正交链表结点结构定义如下：typedef

struct

OLNode

{

int

row,

col;

//行号与列号

ElemType

val;

//值

struct

OLNode

*right,

*down;

//指针域

}OLNode,

*OLink;

typedef

struct

{

OLink

*rowhead,

*colhead;

//

存放行、列链表的头指针的数组的首地址

int

rnum,

cnum,