AI 助理
备案控制台
开发者社区 人工智能 文章 正文

稀疏矩阵的加，减，乘，转置

2017-05-19 2917
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 稀疏矩阵是指哪些多元素为零的矩阵。利用“稀疏的特点”进行储存和计算可以打打节省储存空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

1　需求分析

稀疏矩阵是指哪些多元素为零的矩阵。利用“稀疏的特点”进行储存和计算可以打打节省储存空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

以“带行逻辑链接信息”的三元组标表示稀疏矩阵，实现矩阵的转置，实现两个矩阵相加，相减和相乘的运算。稀疏矩阵的输入形势采用三元组表示，而运算结果的矩阵则以通常的阵列形势列出。

演示程序以用户和计算机的对话法师执行，数组的建立方式为边输入边建立。

由题目要求可知：首先应该输入矩阵的行数和列数，并判别给出的两个矩阵的行数，列数对于所要求作的运算是否相互匹配。

程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时，不会产生错误。

程序在vc6.0环境下设计。程序执行命令为：1.稀疏矩阵的转置；2.稀疏矩阵的乘法；3.稀疏矩阵的加法；4.稀疏矩阵的减法；5.退出；的工作。

1.1　用户角度

（1）从界面选择一种算法并输入一个或两个稀疏矩阵，输出运算的正确结果。

（2）界面简洁，操作方便。

1.2　开发工具的特点

Visual C++  6.0版本：

（1）具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点。

（2）界面简洁，占用资源少，操作方便。

（3）拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。

2　概要设计

                           图2.1

 

 

1．  基本操作：

InputTSMatrix

操作结果：输入三元组矩阵

OutputSMatrix

初始条件：矩阵已经存在

操作结果：输出矩阵

TranSMatrix()

初始条件：矩阵已经存在

操作结果：转置输入的矩阵

FastTranMat()

初始条件：矩阵已经存在

操作结果：快速转置输入的矩阵

MultSMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的积

AddMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的和

SubMatrix()

初始条件：矩阵A和矩阵B已经存在

操作结果：求矩阵A和矩阵B的减

 

 

 

模块调运关系如下：

3　详细设计

3.1定义储存矩阵三元组结构

#include <stdio.h>

#include <iomanip>

 

const int MAXSIZE = 100;        //定义非零元素的最多个数

const int MAXROW = 10;            //定义数组行数的最大值

const int SIZENUM = 10;

 

typedef struct                    //定义三元组元素

{

  int r, c;                    //矩阵的行号和列号

  int v;                        //矩阵元素值

}Triple;

 

typedef struct                    //定义普通三元组对象

{

  Triple data[MAXSIZE+1];

  int rpos[MAXROW+1];

  int rows, cols, nzeroNums;    //行数、列数、非零元素个数

}TSMatrix;

稀疏矩阵的三元组顺序表：为了节省存储空间，同样对稀疏矩阵进行压缩存储，即只存储稀疏矩阵的非零元素。但是为了实现矩阵的各种运算，还要必须同时记下他的行号和列号。这样，一个三元组（i，j，Aij）便唯一的确定了矩阵中的非零元素，其中i，j分别表示非零元素的行号和列号，Aij则表示非零元素的值。

3.2主要模块的详细分析

3.2.1　矩阵的主程序模块

Main函数主控调用其他模块并描述了以下界面：

 

3.2.1　矩阵的构造模块

void InputTSMatrix(TSMatrix *M)

{

   printf("输入矩阵的行数、列数和非零元素个数: ");

   scanf("%d%d%d",&M->rows,&M->cols,&M->nzeroNums);

   printf("请输入非零元素对应的行号、列号和相应的元素值:\n ");

   for (int i = 1; i <= M->nzeroNums; i++)

   {

       scanf("%d%d%d",&M->data[i].r,&M->data[i].c,&M->data[i].v);

   }

}

3.2.1　矩阵的运算模块

1）矩阵的转置

void TranSMatrix()

{

   TSMatrix M, T;

   InputTSMatrix(&M);

   int col, p, q = 1;

   T.rows = M.cols;

   T.cols = M.rows;

   T.nzeroNums = M.nzeroNums;

   if (T.nzeroNums)

   {

       for (col = 1; col <= M.cols; col++)

       {

          for (p = 1; p <= M.nzeroNums; p++)

          {

              if (M.data[p].c == col)

              {

                 T.data[q].r = M.data[p].c;

                 T.data[q].c = M.data[p].r;

                 T.data[q].v = M.data[p].v;

                 ++q;

              }

          }

       }

   }

   printf("运用普通转置算法, 输入矩阵的转置矩阵为:\n ");

    OutputSMatrix(T);

稀疏矩阵的转置的实现规则：

1.将矩阵的行列值相互交换。2.每个三元组的i、j相互交换。3.重新排列三元组之间的次序便可实现转置

 

2）矩阵的快速转置

void FastTranMat()

{

   TSMatrix M, T;

   int num[MAXROW+1];        //表示矩阵M中第col列非零元素的个数

   int cpot[MAXROW+1];        //表示矩阵M中第col列第一个非0元素在b.data中的位置

   int p, q, col, t;

   InputTSMatrix(&M);        //输入稀疏矩阵

   T.rows = M.cols;

   T.cols = M.rows;

   T.nzeroNums = M.nzeroNums;

   if (T.nzeroNums)

   {

       for (col = 1; col <= M.cols; col++)//M中各列元素初始化

       {

          num[col] = 0;

       }

       for (t = 1; t <= M.nzeroNums; t++)

       {

          ++num[M.data[t].c];            //求M中每一列非零元个数

       }

       //求第col列第一个非零元在b.data中的序号

       cpot[1] = 1;

       for (col = 2; col <= M.cols; col++)

       {

          cpot[col] = cpot[col-1] + num[col-1];

       }

       for (p = 1; p <= M.nzeroNums; p++)

       {

          col = M.data[p].c;         //稀疏矩阵M中每个元素对应的列号

          q = cpot[col];             //稀疏矩阵M中第一个非零元素位置

          T.data[q].r = M.data[p].c;

          T.data[q].c = M.data[p].r;

          T.data[q].v = M.data[p].v;

          ++cpot[col];

       }//end_for

   }//end_if

   printf("运用快速算法，输入矩阵的转置为:\n ");

   OutputSMatrix(T);

}

快速转置的思想是开辟两个数组用来存放每一行有效值的个数，另一个用来存转置后顺序表vector的起始位置。使得数组可以快速找到有效顺序在转置后顺序表里的位置。也就是说快速转置与普通转置比较来说快速转置更为有效计算机运算相对比较简单。

4）矩阵的加法

//两个稀疏矩阵的加法

int AddMatrix()

{

   TSMatrix A, B, C;

   int i = 1, j = 1, k = 1;    //i, j, k分别用以保存A、B、C非零元素个数

   int value = 0;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   if (A.rows != B.rows || A.cols != B.cols)

   {

       printf("两个稀疏矩阵的大小不等,不能相加!\n" );

       return 0;

   }

   if (A.rows == B.rows && A.cols == B.cols)

   {

       while (i <= A.nzeroNums && j <= B.nzeroNums)

       {

          if (A.data[i].r == B.data[j].r)

          {

              if (A.data[i].c < B.data[j].c)

              {

                 C.data[k].r = A.data[i].r;

                 C.data[k].c = A.data[i].c;

                 C.data[k].v = A.data[i].v;

                 k++;

                 i++;

              }

              else if (A.data[i].c > B.data[j].c)

              {

                 C.data[k].r = B.data[j].r;

                 C.data[k].c = B.data[j].c;

                 C.data[k].v = B.data[j].v;

                 k++;

                 j++;

              }

              else

              {

                 value = A.data[i].v + B.data[j].v;

                 if (value != 0)

                 {

                     C.data[k].r = A.data[i].r;

                     C.data[k].c = A.data[i].c;

                     C.data[k].v = value;

                     k++;

                 }

                 i++;

                 j++;

              }

          }

          else if (A.data[i].r < B.data[j].r)

          {

              C.data[k].r = A.data[i].r;

              C.data[k].c = A.data[i].c;

              C.data[k].v = A.data[i].v;

              k++;

              i++;

          }

          else

          {

              C.data[k].r = B.data[j].r;

              C.data[k].c = B.data[j].c;

              C.data[k].v = B.data[j].v;

              k++;

              j++;

          }//把剩余部分元素存入C中

          if (i > A.nzeroNums && j <= B.nzeroNums)

          {

              for (; j <= B.nzeroNums; j++)

              {

                 C.data[k].r = B.data[j].r;

                 C.data[k].c = B.data[j].c;

                 C.data[k].v = B.data[j].v;

                 k++;

              }

          }

          if (i <= A.nzeroNums && j > B.nzeroNums)

          {

              for (; i <= A.nzeroNums; i++)

              {

                 C.data[k].r = A.data[i].r;

                 C.data[k].c = A.data[i].c;

                 C.data[k].v = A.data[i].v;

                 k++;

              }

          }

       }

       C.rows = A.rows;

       C.cols = A.cols;

       C.nzeroNums = k-1;

       printf("输出两个稀疏矩阵的和:\n ");

       OutputSMatrix(C);

       return 1;

   }

   else

   return 0;

}

稀疏矩阵的加法：稀疏矩阵的加法与普通矩阵的加法一样，遵循普通矩阵的加法运算规则，也就是当矩阵A和矩阵B行数和列数必须相同才可以进行计算。

5）矩阵的减法

//两个稀疏矩阵的减法

int SubMatrix()

{

   TSMatrix A, B, C;

   int m = 1, n = 1, k = 1, temp;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   C.rows = A.rows;

   C.cols = A.cols;

   C.nzeroNums = 0;

   if (A.rows == B.rows && A.cols == B.cols)

   {

       while (m <= A.nzeroNums && n <= B.nzeroNums)

       {

          if (A.data[m].r == B.data[n].r)

          {

              if (A.data[m].c == B.data[n].c)

              {

                 temp = A.data[m].v - B.data[n].v;

                 if (temp != 0)

                 {

                     C.data[k].r = A.data[m].r;

                     C.data[k].c = A.data[m].c;

                     C.data[k].v = temp;

                     k++;

                 }

                 m++;

                 n++;

              }

              else if (A.data[m].c < B.data[n].c)

              {

                 C.data[k].r = A.data[m].r;

                 C.data[k].c = A.data[m].c;

                 C.data[k].v = A.data[m].v;

                 k++;

                 m++;

              }

              else

              {

                 C.data[k].r = B.data[n].r;

                 C.data[k].c = B.data[n].c;

                  C.data[k].v = -B.data[n].v;

                 k++;

                 n++;

              }

          }

          else if (A.data[m].r < B.data[n].r)

          {

              C.data[k].r = A.data[m].r;

              C.data[k].c = A.data[m].c;;

              C.data[k].v = A.data[m].v;

              k++;

              m++;

          }

          else

          {

              C.data[k].r = B.data[n].r;

              C.data[k].c = B.data[n].c;

              C.data[k].v = -B.data[n].v;

              k++;

              n++;

          }

       }//end_while

       if (m <= A.nzeroNums)

       {

          for (; m <= A.nzeroNums; m++)

          {

              C.data[k].r = A.data[m].r;

              C.data[k].c = A.data[m].c;

              C.data[k].v = A.data[m].v;

              k++;

          }

       }

       if (n <= B.nzeroNums)

       {

          for (; n <= B.nzeroNums; n++)

          {

              C.data[k].r = B.data[n].r;

              C.data[k].c = B.data[n].c;

              C.data[k].v = -B.data[n].v;

              k++;

          }

       }

       C.nzeroNums = k-1;

       printf("两个稀疏矩阵的差为:\n");

       OutputSMatrix(C);

       return 1;

   } //end_if

   else

   {

       printf("两个稀疏矩阵的大小不同，不能相减!\n");

       return 0;

   }

}

 

//得到矩阵元素M[i][j]的值

int value(TSMatrix M, int i, int j)

{

   int k;

   for (k = 1; k <= M.nzeroNums; k++)

   {

       if (M.data[k].r == i && M.data[k].c == j)

       {

          return M.data[k].v;

       }

   }

   return 0;

}

稀疏矩阵的减法：规则同加法一样，矩阵A和矩阵B的行数和列数相等时才可以进行计算。

6）矩阵的乘法

//矩阵乘法的算法

int MultMat()

{

   TSMatrix A, B, C;

   InputTSMatrix(&A);

   InputTSMatrix(&B);

   int i, j, k, temp = 0, p = 1;

   if (A.cols != B.rows)

   {

       printf("矩阵A的列数不等于矩阵B的行数不能相乘!\n");

       return 0;

   }

   else

   {

       for (i = 1; i <= A.rows; i++)

       {

          for (j = 1; j <= B.cols; j++)

          {

              temp = 0;

              for (k = 1; k <= A.cols; k++)

              {

                 temp += value(A, i, k) * value(B, k, j);

              }

              if (temp != 0)

              {

                 C.data[p].r = i;

                 C.data[p].c = j;

                 C.data[p].v = temp;

                 p++;

              }

          }

       }

       C.rows = A.rows;

       C.cols = B.cols;

       C.nzeroNums = p-1;

       OutputSMatrix(C);

       return 1;

   }

}

稀疏矩阵的乘法：同样遵循普通矩阵的乘法运算，当矩阵A与矩阵B相乘时则只有前者的列数等于后者的行数时该运算才有意义。

 

（4）矩阵的输出模块

//输出矩阵，按标准格式输出

void OutputSMatrix(TSMatrix M)

{

   int i, j, k = 1;

   for (i = 0; i < M.rows; i++)

   {

       for (j = 0; j < M.cols; j++)

       {

          if ((M.data[k].r-1) == i && (M.data[k].c-1) == j)

          {

              printf("%4d",M.data[k].v);

              k++;

          }

          else

          printf("%4d",0);

       }//end_j

       printf("\n");

   }//end_i

}

 

 

 

 

Main（）

Input（）

Transpose（）

Add（）

Sub（）

Mul（）

Output（）

模块调用关系图
 

3.3　主程序流程图

4　测试

稀疏矩阵的定义：矩阵中非零元素远远小于矩阵元素的个数，并且非零元素的分布没有一定的规律，则称该矩阵为稀疏矩阵。

该程序测试所使用的矩阵A、B和矩阵C分别如下：

5  0  0   12  0  0       0  0  0  0  15  3       1  0  4  0  0

0  0  16  0   0  0       4  0  0  0  0   0       0  1  0  0  0

   8  0  11  0  27  0       0  0  0  8  0   0       8  0  0  0  0

   0  0  0   0   0  0       1  13 0  0  0   0       0  0  7  0  0

        矩阵A                    矩阵B             5  1  0  0  0

0    0  0  0  3

矩阵C

文章标签：
算法
微雨入寒窗
目录
相关文章
米果粒
|
15天前
使用多维数组将两个矩阵相加
【10月更文挑战第30天】使用多维数组将两个矩阵相加。
米果粒
25 2
yma16
|
6月前
|
人工智能 小程序 BI
矩阵的转置、加和乘法写入C++
矩阵的转置、加和乘法写入C++
yma16
55 0
筱姌
|
6月前
L1-048 矩阵A乘以B
L1-048 矩阵A乘以B
筱姌
49 0
微芒不朽
|
6月前
|
索引
转置矩阵-暴力解法&一行代码
转置矩阵-暴力解法&一行代码
微芒不朽
40 0
软件开发架构
|
机器学习/深度学习 存储 人工智能
第3章 数组与矩阵——3.2 矩阵操作
第3章 数组与矩阵——3.2 矩阵操作
软件开发架构
134 1
软件开发架构
|
存储 NoSQL
第3章 数组与矩阵——3.5 稀疏矩阵
第3章 数组与矩阵——3.5 稀疏矩阵
软件开发架构
124 0
软件开发架构
|
存储
第3章 数组与矩阵——3.3 矩阵元素的运算(1)
第3章 数组与矩阵——3.3 矩阵元素的运算(1)
软件开发架构
80 0
软件开发架构
第3章 数组与矩阵——3.3 矩阵元素的运算(2)
第3章 数组与矩阵——3.3 矩阵元素的运算(2)
软件开发架构
50 0
软件开发架构
|
机器学习/深度学习 前端开发 rax
第3章 数组与矩阵——3.4 矩阵运算(1)
第3章 数组与矩阵——3.4 矩阵运算(1)
软件开发架构
89 0
软件开发架构
|
机器学习/深度学习 资源调度 算法
第3章 数组与矩阵——3.4 矩阵运算(2)
第3章 数组与矩阵——3.4 矩阵运算(2)
软件开发架构
126 0

热门文章

最新文章

  • 1
    Java 生成 UUID
  • 2
    一文读懂 Serverless 的起源、发展和落地实践
  • 3
    Fiddler抓包：下载、安装及使用
  • 4
    用CodeViz绘制函数调用关系图(call graph)
  • 5
    阿里AI上岗双11服装车间，能识别头发丝直径十分之一的瑕疵
  • 6
    SpringBoot开发案例之整合Dubbo提供者(一)
  • 7
    Dubbo架构介绍
  • 8
    警惕垃圾邮件借加沙新闻进行钓鱼攻击
  • 9
    美国博客刊文发布NetApp StoreVault停产通知
  • 10
    IntelliJ IDEA 12 创建Web项目 教程 超详细版
  • 1
    通义灵码与云计算平台的融合：基础与概述
    37
  • 2
    《深度解析：死锁的“前世今生”与防范之道》
    31
  • 3
    《探秘程序崩溃：核心转储（Core Dump）分析全攻略》
    34
  • 4
    今日 AI 开源｜共 12 项｜开源的DIY健康追踪项目，基于低成本的智能戒指构建私人的健康监测应用
    38
  • 5
    Open Interpreter：AI 赋能终端！在终端中对话AI模型进行编程，通过运行代码来完成各种计算机操作任务
    31
  • 6
    「Mac畅玩鸿蒙与硬件15」鸿蒙UI组件篇5 - Slider 和 Progress 组件
    40
  • 7
    ai断点怎么做?
    16
  • 8
    AI Shell：在命令行里“对话” AI ，微软推出将 AI 助手引入命令行的 CLI 工具，打造对话式交互命令行
    19
  • 9
    ai怎么设计迷宫字体效果?
    15
  • 10
    「Mac畅玩鸿蒙与硬件14」鸿蒙UI组件篇4 - Toggle 和 Checkbox 组件
    29

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云OSS设置跨域访问