前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++经典算法题-稀疏矩阵

C++经典算法题-稀疏矩阵

作者头像
cwl_java
发布2020-02-13 23:18:28
8870
发布2020-02-13 23:18:28
举报
文章被收录于专栏:cwl_Java

46.Algorithm Gossip: 稀疏矩阵

说明

如果在矩阵中,多数的元素并没有资料,称此矩阵为稀疏矩阵(sparse matrix), 由于矩阵在程式中常使用二维阵列表示,二维阵列的大小与使用的记忆体空间成正比,如果多数的元素没有资料,则会造成记忆体空间的浪费,为 此,必须设计稀疏矩阵的阵列储存方式,利用较少的记忆体空间储存完整的矩阵资讯。

解法

在这边所介绍的方法较为简单,阵列只储存矩阵的行数、列数与有资料的索引位置及其值,在需要使用矩阵资料时,再透过程式运算加以还原,例如若矩阵资料如下 ,其中0表示矩阵中该位置没有料:

代码语言:javascript
复制
0	0	0	0	0	0
0	3	0	0	0	0
0	0	0	6	0	0
0	0	9	0	0	0
0 0 0 0 12 0

这个矩阵是5X6矩阵,非零元素有4个,您要使用的阵列第一列记录其列数、行数与非零元素个数: 5 6 4

阵列的第二列起,记录其位置的列索引、行索引与储存值:

代码语言:javascript
复制
1 1 3
2  3 6
3  2 9
4 4 12

所以原本要用30个元素储存的矩阵资讯,现在只使用了15个元素来储存,节省了不少记忆体的使用。

代码示例

代码语言:javascript
复制
#include <stdio.h> 
#include <stdlib.h>
    int main(void) {
        int num[5][3] = {{5, 6, 4},
            {1, 1, 3},
            {2, 3, 6},
            {3, 2, 9},
            {4, 4, 12}};
        int i, j, k = 1;

        printf("sparse matrix:\n"); for(i = 0; i < 5; i++) {
            for(j = 0; j < 3; j++) { printf("%4d", num[i][j]);
            }
            putchar('\n');
        }

        printf("\nmatrix还原:\n"); for(i = 0; i < num[0][0]; i++) {
            for(j = 0; j < num[0][1]; j++) { if(k < num[0][2] &&
                    i == num[k][0] && j == num[k][1]) {
                printf("%4d ", num[k][2]); k++;

            }
            else

            }

            printf("%4d ", 0);

            putchar('\n');
        }

        return 0;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/01/17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 46.Algorithm Gossip: 稀疏矩阵
    • 说明
      • 解法
        • 代码示例
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档