滴水逆向联盟

标题: VC++2012编程演练数据结构《17》稀疏矩阵 [打印本页]
作者: 大灰狼    时间: 2014-8-26 08:16
标题: VC++2012编程演练数据结构《17》稀疏矩阵
如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩阵（sparse matrix）。
由于矩阵在程序中常使用二维阵列表示，二维阵列的大小  稀疏矩阵与使用的存储器空间成正比，如果多数的元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的存储器空间储存完整的矩阵数据。
　　二维数组Amn中有N个非零元素，若N<<m*n（N/m*n<=0.2),则称A为稀疏矩阵。
　　由于稀疏矩阵中含有很多的0元素,在计算机中存储会浪费很多的空间,因此我们通常采用压缩存储的方法。
　稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点.
　　假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只
　　需要2 0 0 0次浮点运算.
　　因为M AT L A B不能自动创建稀疏矩阵,所以要用特殊的命令来得到稀疏矩阵,在下一节
　　中将给出这些命令.前面章节中的算术和逻辑运算都适用于稀疏矩阵.
　　对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素.
　　  对于矩阵Amn的每个元素aij,知道其行号i和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义如下:
　　[i,j,aij]
　　该结点由3个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点.矩阵的每一个元素Qij,由一个三元组结点(i,j,aij)唯一确定.
　　例如稀疏矩阵A:
　　50 0 0 0
　　10 0 20 0
　　0 0 0 0
　　-30 0 -60 5
　　其对应的三元组表为：
　　1 1 50
　　2 1 10
　　2 3 20
　　4 1 -30
　　4 3 -60

　　4 4 5

打开IDE

我们创建一个工程


类的声名如下


[cpp] view plaincopy






类的实现如下


[cpp] view plaincopy






类的调用如下


[cpp] view plaincopy


  • #include "stdafx.h"  
  •   
  • //稀疏矩阵相关操作的测试  
  •   
  •   
  • //三元组顺序表的输出  
  • void print(TSMatrix a)  
  • {cout<<"   i   j   e\n";  
  • for(int k=0;k<a.tu;k++)  
  • {cout<<setw(4)<<a.data[k].ii;  
  • cout<<setw(4)<<a.data[k].jj;  
  • cout<<setw(4)<<a.data[k].e<<endl;}  
  • }  
  • void  main()  
  • {cout<<"运行结果:\n";  
  • int b[N][L],i,j,k=0;  
  • int a[L][N]={0,12,9,0,0,0,0,0,0,0,0,0,0,0,-3,0,0,0,0,14,0,  
  • 0,0,24,0,0,0,0,0,18,0,0,0,0,0,15,0,0,-7,0,0,0};  
  • TSMatrix a1,b1,c1;  
  • a1.mu=L;a1.nu=N;a1.tu=0;  
  • cout<<"稀疏矩阵a1:\n";  
  • for(i=0;i<L;i++)//输出数组a1  
  • {for(j=0;j<N;j++)  
  • cout<<setw(3)<<a[j];  
  • cout<<'\n';}  
  • //创建三元组顺序表  
  • for (i=0;i<L;i++)  
  • for (j=0;j<N;j++)  
  • if (a[j]!=0)  
  • { a1.data[k].ii=i;  
  • a1.data[k].jj=j;  
  • a1.data[k].e=a[j];  
  • a1.tu++;k++;}  
  • cout<<"原三元组顺序表a1:\n";  
  • print(a1);  
  • cout<<"按任意键继续...\n";getch();  
  • a1.TrMatrix(c1);  
  • for (i=0;i<N;i++)//初始化数组  
  • for (j=0;j<L;j++) b[j]=0;  
  • for (k=0;k<c1.tu;k++)  
  • b[c1.data[k].ii][c1.data[k].jj]=c1.data[k].e;  
  • cout<<"转置矩阵 c1:\n";  
  • for (i=0;i<N;i++)  
  • { for (j=0;j<L;j++)  
  • cout<<setw(3)<<b[j];  
  • cout<<'\n';}  
  • cout<<"转置矩阵三元组顺序表:\n";  
  • print(c1);  
  • cout<<"按任意键继续...\n";getch();  
  • a1.FastTrMatrix(b1);  
  • for (i=0;i<N;i++)//initial array_b  
  • for (j=0;j<L;j++) b[j]=0;  
  • for (k=0;k<b1.tu;k++)  
  • b[b1.data[k].ii][b1.data[k].jj]=b1.data[k].e;  
  • cout<<"转置矩阵 b1:\n";  
  • for (i=0;i<N;i++)  
  • { for (j=0;j<L;j++)  
  • cout<<setw(3)<<b[j];  
  • cout<<'\n';}  
  • int p[3][4]={{10,0,5,7},{2,1,0,0},{3,0,4,0}};  
  • int w[4][2]={{2,0},{4,8},{0,14},{3,5}};  
  • TSMatrix aa,bb,cc;  
  • aa.mu=3;aa.nu=4;aa.tu=0;  
  • bb.mu=4;bb.nu=2;bb.tu=0;  
  • //创建三元组顺序表  
  • for (k=0,i=0;i<3;i++)  
  • for (j=0;j<4;j++)  
  • if (p[j]!=0)  
  • { aa.data[k].ii=i;aa.data[k].jj=j;  
  • aa.data[k].e=p[j];  
  • aa.tu++;k++;}  
  • //创建三元组顺序表  
  • for (k=0,i=0;i<4;i++)  
  • for (j=0;j<2;j++)  
  • if (w[j]!=0)  
  • { bb.data[k].ii=i;bb.data[k].jj=j;  
  • bb.data[k].e=w[j];  
  • bb.tu++;k++;}  
  • aa.mulmatrix(bb,cc);  
  • cout<<"乘积矩阵三元组顺序表:\n";  
  • print(cc);  
  • cout<<"创建的稀疏矩阵:\n";  
  • TSMatrix ff(MROW,MCOL,4);  
  • cout<<"按任意键结束!\n";getch();}  




效果如下







欢迎光临 滴水逆向联盟 (http://www.dtdebug.com/) Powered by Discuz! X3.2