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

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

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

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

文章标签：
算法
微雨入寒窗
目录
相关文章
技术员阿伟
|
11月前
|
缓存 编解码 并行计算
《AMD显卡游戏适配手册：解决画面闪烁、着色器编译失败的核心技术指南》
本文聚焦游戏跨显卡适配中的典型痛点，针对NVIDIA显卡运行流畅、AMD显卡却出现画面闪烁、着色器编译失败等问题，深度拆解底层成因与根治方案。文章指出，问题核心源于AMD与NVIDIA的硬件架构（SIMD/SIMT）、指令集支持、驱动优化方向的本质差异，以及开发时单一显卡适配的思维惯性。通过驱动版本精准选型与残留清理、着色器编译规则降级兼容与分卡预编译、纹理压缩格式与渲染设置针对性调整、双显卡同步测试与长效迭代体系搭建等六大核心逻辑，提供从底层技术优化到实操落地的全流程指南。
技术员阿伟
868 7
架构实验室1
|
SQL 运维 JavaScript
Yearning目前最流行的开源数据库审核平台
Yearning帮你减小日常变更数据库的风险，规范有序记录进行数据库变更操作
架构实验室1
2524 0
Yearning目前最流行的开源数据库审核平台
shiro~
ES数据删除优化
ES数据删除优化
shiro~
736 0
悟空爬虫
|
3月前
|
人工智能 前端开发 JavaScript
你的时区正在告诉 Claude Code，你是中国人
Claude Code 通过系统时区（UTC+8）、浏览器语言、中文字体等6项本地指纹识别中国用户，无需依赖IP。开源工具 claude-tester 可本地检测你的“AI身份分”（满分100），揭示被忽视的隐私暴露面——时区、字体、Emoji 风格皆成线索。纯前端，零数据上传。
悟空爬虫
634 2
你的时区正在告诉 Claude Code，你是中国人
霍格沃兹测试开发学社
|
3月前
|
SQL 人工智能 安全
一个文件夹 + 一个Markdown文件 = 你的第一个Skill
本文介绍如何用“Skill”（技能包）提升AI编程效率：只需新建文件夹+SKILL.md，即可封装项目规范、知识库与提示词，让AI秒懂业务上下文。5分钟上手，零代码实现精准代码审查、测试生成等专业能力，助力工程师高效抢救遗留系统。
霍格沃兹测试开发学社
560 1
weigeshuoyun
|
4月前
|
存储 弹性计算 文件存储
阿里云文件存储NAS对接完全指南：从零搭建到生产级调优
本文系统讲解阿里云文件存储NAS的完整对接流程。从NAS的核心概念与产品优势入手，深入解析通用型与极速型NAS的选型策略。详细演示通过控制台一键挂载、Linux手动mount、Windows SMB映射、容器CSI插件等多种对接方式，并给出/etc/fstab自动挂载配置。在权限管理方面，完整覆盖权限组白名单、NFS ACL细粒度控制与RAM访问控制三层安全体系。针对高并发场景，提供nconnect参数调优、NFS缓存参数优化、NFSv4.1升级等性能提升方案。同时涵盖跨VPC访问、云企业网互通、VPN网关连接本地数据中心等高级网络场景。最后给出监控告警配置、成本优化策略与常见问题排查方法，帮
weigeshuoyun
514 1
Lottie2026
|
3月前
|
数据采集 存储 前端开发
淘宝商品评论数据爬取：Python实战指南
本文提供一套轻量、稳定、可落地的淘宝评论爬虫方案，基于Python实现接口抓包、动态UA、随机延时、分页采集与数据清洗，适配竞品调研、舆情分析等小规模数据分析场景。含完整可运行代码及反爬避坑指南。
Lottie2026
793 0
阿里云云工开物
|
12月前
|
人工智能 运维 数据可视化
申报开启丨2025年10月批次阿里云协同育人项目申报指南，支持所有学科
阿里云联合教育部启动2025年产学合作协同育人项目，面向本科高校征集教学改革、实践基地建设与师资培训项目，聚焦AI+X课程、AIGC设计、智能编码、大数据分析等方向，提供资金、技术与资源支持，深化产教融合，共育创新人才。申报截止11月30日。
阿里云云工开物
767 1
游客3b5njzfykzfdk
|
5月前
|
JSON 监控 API
V4-Flash 轻量化模型接入，​D​М‌X​Α‌РΙ 优化边缘端部署延迟
V4-Flash是DeepSeek于2026年推出的轻量化MoE大模型，支持1M上下文、384K输出与双模式推理，兼顾强能力与低延迟；结合DMXAPI标准化接入，可实现统一鉴权、流控、可观测与多模型路由，显著优化边缘部署效率与生产稳定性。（239字）
游客3b5njzfykzfdk
652 0
coder一枚
|
6月前
|
人工智能 监控 API
【JVS养虾宝典】实测JVS Claw自动发送邮件，免费替代OpenClaw的新一代AI龙虾
JVS Claw是阿里云推出的AI龙虾助手，JVS Claw官网：https://t.aliyun.com/U/IJbaxg 基于OpenClaw框架深度优化，开箱即用、免配置、零依赖，支持云端自动收发邮件等任务。新手友好，免费试用7天，真正实现“说话即执行”。
coder一枚
658 4

热门文章

最新文章

  • 1
    PHPMailer发送邮件
  • 2
    PostgreSQL Oracle 兼容性之 - WM_SYS.WM_CONCAT
  • 3
    高德服务单元化方案和架构实践
  • 4
    为什么大部分人做不了架构师？这2点是关键
  • 5
    下载频道规则
  • 6
    Monorepo，大型前端项目管理模式实践
  • 7
    MYSQL匿名登录 导致创建不了数据库
  • 8
    openAI的Red Team
  • 9
    云计算|OpenStack|使用VMware安装华为云的R006版CNA和VRM---初步使用（二）
  • 10
    php冒泡排序
  • 1
    开始 AI 编程前，到底需要准备什么？
    39
  • 2
    AI 编程是什么？5 个真实开发场景带你快速入门
    32
  • 3
    阿里云SSL数字证书多少钱？免费0元、付费版证书品牌不同、类型不同，收费价格也不同
    27
  • 4
    阿里云万小智AI建站3.0如何收费？最新轻量版、标准版和高级版费用整理
    29
  • 5
    阿里云AI模型夜间优惠怎么个事儿？Night Plan申请及使用流程
    34
  • 6
    如何搭建企业官网？阿里云万小智AI建站，一句话建站，成本15元搞定！
    32
  • 7
    阿里云SSL证书多少钱一年？免费版3个月时长，付费版SSL证书费用列举
    26
  • 8
    亲测：阿里云万小智AI建站15元企业官网上线，一句话网站发布上线！
    33
  • 9
    阿里云百炼Token Plan指南：介绍、费用、订阅、API Key 和 Base URL获取及使用全流程
    32
  • 10
    阿里云万小智AI建站标准版和高级版有什么区别？选择对比经验分享
    34

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！