稀疏矩阵

一、实验目的

二、实验内容

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;

}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,245评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,749评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,960评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,575评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,668评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,670评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,664评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,422评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,864评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,178评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,340评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,015评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,646评论 3赞 323
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,265评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,494评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,261评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,206评论 2赞 352

推荐阅读更多精彩内容

  • 2018-06-14
    在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,340评论 0赞 2
  • snapshot-1.0.0.js
    "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些阅读 2,028评论 0赞 2
  • 2018-06-25
    专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 8,984评论 0赞 13
  • 图像处理中的插值
    thiele插值算法 1点插值算法 function [C,c]=thiele(X,Y,Z)%X为插值点横坐标，Y...
    00crazy00阅读 1,986评论 0赞 4
  • 模拟一号店POST登陆算法
    var navigator = navigator || {};var window = window || {}...
    DF_Sky阅读 1,244评论 0赞 0