一、实验目的
二、实验内容
1. 阅读、理解、调试程序3_1.c，掌握稀疏矩阵的压缩存储算法。
2. 阅读、理解、调试程序3_2.c，理解稀疏矩阵的压缩存储（三元组存储）后的乘法算法。
3．用三元组顺序表存储稀疏矩阵，实现上三角阵的压缩存储。
一．实验目的
1. 掌握特殊矩阵的压缩存储方法。
2．掌握稀疏矩阵的三元组压缩存储方法。
3．掌握稀疏矩阵三元组存储结构的矩阵转置、加法、乘法算法。
二．实验要求与内容
1. 参照课本P68-P74，完成稀疏矩阵三元组压缩存储结构后的转置运算、加法、乘法运算。
2. 完成三带状矩阵的压缩存储，并实现加法运算（乘法运算选做）。
3．（选做）完成下面矩阵压缩存储后的运算：C=A+B，其中，A为下三角矩阵，B为三带状矩阵。
注：以上三题测试矩阵应不少于6×6阶
三．实验步骤
1．数据结构
定义一个三元矩阵，例如a[10][2];a[0][0]储存该矩阵的行数，a[0][1]储存该矩阵的列数，a[0][2]储存该矩阵非0元素的个数。a[i][0]储存非0元素的行，a[i][1]储存非0元素的列。
2．算法设计
矩阵的加法考虑两个矩阵的行数列数是否相同，在同一位置都有值，两个矩阵其中之一在该位置有值。两个矩阵在该位置都没有值的情况不考虑。矩阵的乘法需要矩阵A的列数是否与矩阵B的行数相同，矩阵相乘后的矩阵C在第i行第j列的值是A矩阵的第i行乘以矩阵B的第j行。
三带状矩阵主要考虑压缩，b[s]=1+2*(i-1)+(j-1);
三带状矩阵主要考虑相乘是的合法性，即行数与列数的差值只能为1或者是0；
3．程序
矩阵的加法： for(int i=1;i<=a[0][0];i++)
{
for(int j=1;j<=a[0][1];j++)
{
if(i==a[s][0] && j==a[s][1] && i==c[t][0] && j==c[t][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=a[s][2]+c[t][2];
f++;
t++;
s++;
}
else if(i==a[s][0] && j==a[s][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=a[s][2];
f++;
s++;
}
else if(i==c[t][0] && j==c[t][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=c[t][2];
f++;
t++;
}
}
}
矩阵的乘法：
for(i=1;i<=a[0][0];i++)//第i行
for(j=1;j<=c[0][1];j++)//第j列
//矩阵相乘矩阵 a 的第i行*（矩阵c的第1列，第2列，，，，第c[0][1]列；
{
sum=0;
for(int k=1;k<=a[0][2];k++)//开始遍历a；
{
if(a[k][0]==i)//找到三元矩阵a中的第i行元素
{
for(int l=1;l<=c[0][2];l++)//开始遍历b
{
if(c[l][1]==j && a[k][1]==c[l][0])
{//找到三元矩阵c中的第j列元素,并且如果要乘积不为0；必须所找到的a的列值等于c的行值；
sum=sum+a[k][2]*c[l][2];//累加
break;
}
}
}
}
if(sum!=0)
{
s++;
d[s][0]=i;
d[s][1]=j;
d[s][2]=sum;
}
}
三带状矩阵的加法
//先将两个矩阵分别压缩存储在两个数组中，再相加
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cin>>d;
if(d!=0)
b[1+2*(i-1)+(j-1)]=d;
}
}
for(int i=1;i<=3*n-3;i++)
s[i]+=b[i];
三带状矩阵的乘法
for(i=1;i<=n;i++)//行
{
for(j=i-1;j<=i+1;j++)//列
{
sum=0;
if(s[1+2*(i-1)+(j-1)]!=0)
{
y=j;//y是要乘的带状矩阵的列
if(i==1)//k代表了从第i行的第几个元素开始做乘法，k之前的值都为0，没有必要做乘法
k=1;
else
k=i-1;
for(int w=k;w<=min(i+1,n);w++)//w代表了从第k开始做乘法，，到第i+1结束n-1，当在第n行的时候，k最多取到n
{
if(b[1+2*(w-1)+(y-1)]!=0 && (abs(y-w)==1|| abs(y-w)==0))//判断要乘的那个数是合法的，，即行数与列数相差1或者是0
sum=sum+s[1+2*(i-1)+(w-1)]*b[1+2*(w-1)+(y-1)];//需要累加起来
}
}
if(sum!=0)
{
h[1+2*(i-1)+(j-1)]=sum;
}
}
}
三带状矩阵和下三角矩阵相加：
for(int i=1;i<=s;i++)
{
for(int j=1;j<=s;j++)
{
if( i-j==1 || i==j)//当三带状矩阵和小三角矩阵都有值的时候
cout<<a[i*(i-1)/2+j]+b[1+2*(i-1)+(j-1)]<<" ";
else if(i
cout<<b[1+2*(i-1)+(j-1)]<<" ";
else if(i>j)//当只有三带状矩阵有值的时候
cout<<a[i*(i-1)/2+j]<<" ";
else
cout<<"0 ";
}
cout<<endl;
}
4．程序调试
四．结果与体会
稀疏矩阵的三元压缩矩阵乘法需要一定的逻辑性。三带状矩阵的乘法需要考虑到相乘的范围。三带状矩阵与下三角矩阵相加时需要注意各自行列的特点。
五．源程序
1.稀疏矩阵三元组压缩存储结构后的转置运算、加法、乘法运算。
#include<stdio.h>
#include<iostream>
using namespace std;
int a[20][3];
int b[20][3];
int c[20][3];
int d[20][3];
int main()
{
int n,m,k;
cout<<"请输入第一个稀疏矩阵的行列数以及非零个数"<<endl;
cin>>n>>m>>k;
a[0][0]=n;//行
a[0][1]=m;//列
a[0][2]=k;//个数
cout<<"请输入非零元数的行列坐标及值"<<endl;
for(int i=1;i<=k;i++)
{
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
//输出稀疏矩阵
cout<<"稀疏矩阵如下所示"<<endl;
int s=1;
for(int i=1;i<=a[0][0];i++)
{
for(int j=1;j<=a[0][1];j++)
{
int m=0;
if(a[s][0]==i && a[s][1]==j)
{
m=1;
cout<<a[s][2]<<" ";
s++;
}
if(m==0)
cout<<"0 ";
}
cout<<endl;
}
//矩阵的转置
b[0][0]=a[0][1];
b[0][1]=a[0][0];
b[0][2]=a[0][2];
s=1;
for(int i=1;i<=a[0][1];i++)
{
for(int j=1;j<=a[0][0];j++)
{
if(a[j][1]==i)
{
b[s][0]=a[j][1];
b[s][1]=a[j][0];
b[s][2]=a[j][2];
s++;
}
}
}
cout<<"转置后的稀疏矩阵"<<endl;
s=1;
for(int i=1;i<=b[0][0];i++)
{
for(int j=1;j<=b[0][1];j++)
{
int m=0;
if(b[s][0]==i && b[s][1]==j)
{
m=1;
cout<<b[s][2]<<" ";
s++;
}
if(m==0)
cout<<"0 ";
}
cout<<endl;
}
//稀疏矩阵的加法
cout<<"请输入第二个稀疏矩阵的行列数以及非零个数"<<endl;
cin>>n>>m>>k;
c[0][0]=n;//行
c[0][1]=m;//列
c[0][2]=k;//个数
//cout<<"请输入非零元数的行列坐标及值";
for(int i=1;i<=k;i++)
{
cin>>c[i][0]>>c[i][1]>>c[i][2];
}
//第二个矩阵
cout<<"第二个稀疏矩阵"<<endl;
s=1;
for(int i=1;i<=c[0][0];i++)
{
for(int j=1;j<=c[0][1];j++)
{
int m=0;
if(c[s][0]==i && c[s][1]==j)
{
m=1;
cout<<c[s][2]<<" ";
s++;
}
if(m==0)
cout<<"0 ";
}
cout<<endl;
}
cout<<endl;
s=1;int t=1;int f=1;
if(a[0][0]==c[0][0] && a[0][1]==c[0][1])//要进行矩阵的加法运算，两个矩阵的行数和列数必须相等
{
d[0][0]=a[0][0];
d[0][1]=a[0][1];
for(int i=1;i<=a[0][0];i++)
{
for(int j=1;j<=a[0][1];j++)
{
if(i==a[s][0] && j==a[s][1] && i==c[t][0] && j==c[t][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=a[s][2]+c[t][2];
f++;
t++;
s++;
}
else if(i==a[s][0] && j==a[s][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=a[s][2];
f++;
s++;
}
else if(i==c[t][0] && j==c[t][1])
{
d[f][0]=i;
d[f][1]=j;
d[f][2]=c[t][2];
f++;
t++;
}
}
}
d[0][2]=f-1;
}
else
cout<<"不能进行矩阵的加法运算"<<endl;
if(f!=1)
{
cout<<"相加后的矩阵"<<endl;
s=1;
for(int i=1;i<=d[0][0];i++)
{
for(int j=1;j<=d[0][1];j++)
{
int m=0;
if(d[s][0]==i && d[s][1]==j)
{
m=1;
cout<<d[s][2]<<" ";
s++;
}
if(m==0)
cout<<"0 ";
}
cout<<endl;
}
}
//矩阵乘法；
if(a[0][1]==c[0][0])
{
cout<<"第一个矩阵和第二个矩阵的相乘结果是"<<endl;
s=0;
int i,j,sum=0;
for(i=1;i<=a[0][0];i++)//第i行
for(j=1;j<=c[0][1];j++)//第j列
//矩阵相乘矩阵 a 的第i行*（矩阵c的第1列，第2列，，，，第c[0][1]列；
{
sum=0;
for(int k=1;k<=a[0][2];k++)//开始遍历a
if(a[k][0]==i)//找到三元矩阵a中的第i行元素
for(int l=1;l<=c[0][2];l++)//开始遍历b
{
if(c[l][1]==j && a[k][1]==c[l][0])
{//找到三元矩阵c中的第j列元素,并且如果要乘积不为0；必须所找到的a的列值等于c的行值；
sum=sum+a[k][2]*c[l][2];//累加
break;
}
}
if(sum!=0)
{
s++;
d[s][0]=i;
d[s][1]=j;
d[s][2]=sum;
}
}
d[0][0]=a[0][0];
d[0][1]=c[0][1];
d[0][2]=s;
s=1;
for(int i=1;i<=d[0][0];i++)
{
for(int j=1;j<=d[0][1];j++)
{
int m=0;
if(d[s][0]==i && d[s][1]==j)
{
m=1;
cout<<d[s][2]<<" ";
s++;
}
if(m==0)
cout<<"0 ";
}
cout<<endl;
}
}
else
cout<<"这两个矩阵不能相乘"<<endl;
return 0;
}
2.三带状矩阵的加法和乘法
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int s[50]={0};
int b[50]={0};
int h[50]={0};
int n,m;
int y,k,sum=0,i,j;
cout<<"请输入三带矩阵的阶数";
cin>>n;
int d;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>d;
if(d!=0)
s[1+2*(i-1)+(j-1)]=d;
}
}
cout<<"请输入要加的三带矩阵的阶数";
cin>>m;
if(m==n)
{
for(i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cin>>d;
if(d!=0)
b[1+2*(i-1)+(j-1)]=d;
}
}
cout<<"这两个三带状矩阵相乘后结果是："<<endl;
for(i=1;i<=n;i++)//行
{
for(j=i-1;j<=i+1;j++)//列
{
sum=0;
if(s[1+2*(i-1)+(j-1)]!=0)
{
y=j;//y是要乘的带状矩阵的列
if(i==1)//k代表了从第i行的第几个元素开始做乘法，k之前的值都为0，没有必要做乘法
k=1;
else
k=i-1;
for(int w=k;w<=min(i+1,n);w++)//w代表了从第k开始做乘法，，到第i+1结束n-1，当在最后一行的时候，k最多取到n
{
if(b[1+2*(w-1)+(y-1)]!=0 && (abs(y-w)==1|| abs(y-w)==0))//判断要乘的那个数是合法的，，即行数与列数相差1或者是0
sum=sum+s[1+2*(i-1)+(w-1)]*b[1+2*(w-1)+(y-1)];//需要累加起来
}
}
if(sum!=0)
{
h[1+2*(i-1)+(j-1)]=sum;
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(s[1+2*(i-1)+(j-1)]!=0 && (abs(j-i)==1|| abs(j-i)==0))
cout<<h[1+2*(i-1)+(j-1)]<<" ";
else cout<<" ";
}
cout<<endl;
}
cout<<"这两个三带状矩阵相加后的结果是："<<endl;
for( i=1;i<=3*n-2;i++)
{
s[i]+=b[i];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(s[1+2*(i-1)+(j-1)]!=0 && (abs(j-i)==1|| abs(j-i)==0))
cout<<s[1+2*(i-1)+(j-1)]<<" ";
else cout<<" ";
}
cout<<endl;
}
}
else
cout<<"不能进行运算"<<endl;
return 0;
}
三带状矩阵和下三角矩阵相加
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int a[50];
cout<<"请输入下三角矩阵的阶数";
int n;
cin>>n;
int s=(n*(n+1))/2;
printf("请输入%d个值",s);
for(int i=1;i<=s;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i>=j)
cout<<a[i*(i-1)/2+j]<<" ";
else
cout<<"0 ";
}
cout<<endl;
}
cout<<"请输入要加的三带矩阵的阶数";
int m,d;
int b[20];
cin>>m;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cin>>d;
if(d!=0)
b[1+2*(i-1)+(j-1)]=d;
}
}
s =max(m,n);
cout<<"两个相加后的结果是"<<endl;
for(int i=1;i<=s;i++)
{
for(int j=1;j<=s;j++)
{
if( i-j==1 || i==j)//当三带状矩阵和小三角矩阵都有值的时候
cout<<a[i*(i-1)/2+j]+b[1+2*(i-1)+(j-1)]<<" ";
else if(i
cout<<b[1+2*(i-1)+(j-1)]<<" ";
else if(i>j)//当只有三带状矩阵有值的时候
cout<<a[i*(i-1)/2+j]<<" ";
else
cout<<"0 ";
}
cout<<endl;
}
return 0;
}
网友评论