C++实现稀疏矩阵的压缩存储实例

什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律。在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据。我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放。下面我们来看一下代码实现。

#include<iostream>
#include<vector>
#include<assert.h>
using namespace std; 

template<class T>
class SparseMatrix
{
  //三元组
  template<class T>
  struct Trituple
  {
    Trituple()//给一个默认构造函数
    {}
    Trituple(size_t row, size_t col, const T& data)
      :_row(row)
      ,_col(col)
      ,_data(data)
    {}
    size_t _row;
    size_t _col;
    T _data;
  };
public:
  //稀疏矩阵的压缩存储
  SparseMatrix()
  {}
  SparseMatrix(int* arr, size_t row, size_t col, const T& invalid)
    :_row(row)
    ,_col(col)
    ,_invalid(invalid)
  {
    for(int i = 0; i < row; i++)
    {
      for(int j = 0; j < col; ++j)
      {
        if(arr[i*col+j] != invalid)//将有效值存储在一个一维数组中
        _sm.push_back(Trituple<T>(i,j,arr[i*col+j]));//将三元组的无名对象push进去
      }
    }
  }
  //访问稀疏矩阵中row行col中的元素
  T& Acess(int row, int col)
  {
    //1、
    /*for(int idx = 0; idx < _sm.size(); idx++)//遍历一遍
    {
      if(_sm[idx]._row == row && _sm[idx]._col == col)//当前行列与我们要访问那个元素行列相同时返回这个有效值
        return _sm[idx]._data;
    }
    return _invalid;*/ //否则返回无效值
    //2、
    vector<Trituple<T>>::iterator it = _sm.begin();//定义一个迭代器,指向起始位置
    while(it != _sm.end())//未到最后一个元素时
    {
      if(it->_row == row && it->_col == col)//行列相等输出值
        return it->_data;
      ++it;//迭代器向后移动
    }
    return _invalid;
  }
  //还原稀疏矩阵
  template<typename T>
  friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//重载<<
  {
    size_t idex = 0;
    for(size_t i = 0; i < s._row; i++)
    {
      for(size_t j = 0; j < s._col; j++)
      {
        if(idex < s._sm.size()/*防止数组越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j)
        {
          _cout<<s._sm[idex]._data<<" ";
          ++idex;
        }
        else
          _cout<<s._invalid<<" "; 

      }
      _cout<<endl;
    }
    return _cout;
  }
  //实现稀疏矩阵的逆置 时间复杂度O(M*N)(M为元素个数N为矩阵列数)
  SparseMatrix<T> Transport()
  {
    SparseMatrix<T> sm;
    sm._row = _col;
    sm._col = _row;
    sm._invalid = _invalid;
    for(size_t i = 0; i < _col; i++)
    {
      vector<Trituple<T>>::iterator it = _sm.begin();
      while(it != _sm.end())
      {
        if(it->_col == i)//从原矩阵第0列开始,将每列中的有效值依次放入新的稀疏矩阵
          sm._sm.push_back(Trituple<T> (i, it->_row, it->_data));
        ++it;
      }
    }
    return sm;
  }
  //实现稀疏矩阵的快速转置 时间复杂度O(N)+O(M)
  SparseMatrix<T> FastTransport()
  {
    SparseMatrix<T> sm;
    sm._col = _row;
    sm._row = _col;
    sm._invalid = _invalid;
    sm._sm.resize(_sm.size());//开辟空间
    //1、统计原矩阵中每一列有多少个有效元素
    int* pCount = new int[_col];//开辟原矩阵中列个数的空间
    memset(pCount, 0, _col*sizeof(pCount[0]));
    for(int i = 0; i < _sm.size(); i++)
      pCount[_sm[i]._col]++;
    //2、原矩阵每一列在新矩阵中的起始位值
    int* pAddr = new int[_col];
    memset(pAddr, 0, _col*sizeof(pAddr[0]));
    for(int i = 1/*从1开始,第一个位置起始为0已经放入*/; i < _sm.size(); i++)
    {
      pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一个起始位值+前一列有效元素个数
    }
    //3、放置元素到新空间
    for(int i = 0; i < _sm.size(); i++)
    {
      int& addr = pAddr[_sm[i]._col];
      sm._sm[addr] = Trituple<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data);
      addr++;
    }
    return sm;
  }
  //实现稀疏矩阵的加法操作1
  /*SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
  {
    int i = 0, j = 0, k = 0;
    T v;
    SparseMatrix<T> s;
    if(this->_col != sp._col || this->_row != sp._row)
      exit(1);
    s._row = sp._row;
    s._col = sp._col;
    s._invalid = sp._invalid;
    while(i < this->_sm.size() && j < sp._sm.size())
    {
      if(this->_sm[i]._row == sp._sm[j]._row)
      {
        if(this->_sm[i]._col < sp._sm[j]._col)
        {
          s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
          i++;
          k++;
        }
        else if(this->_sm[i]._col > sp._sm[j]._col)
        {
          s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
          j++;
          k++;
        }
        else
        {
          v = this->_sm[i]._data + sp._sm[j]._data;
          if(v)
          {
            s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, v));
            k++;
          }
          i++;
          j++;
        }
      }
      else if(this->_sm[i]._row < sp._sm[j]._row)
      {
        s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
        i++;
        k++;
      }
      else
      {
        s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
        j++;
        k++;
      }
    }
    return s;
  }*/
  //实现稀疏矩阵的加法操作2
  SparseMatrix<T> operator+(const SparseMatrix<T>& sp)
  {
    assert(_row == sp._row && _col == sp._col);//检测两个相加的矩阵行列是否相等
    SparseMatrix<T> ret;
    ret._row = _row;
    ret._col = _col;
    ret._invalid = _invalid;
    int iLidx = 0, iRidx = 0;//定义两个索引 

    while(iLidx < _sm.size() && iRidx < sp._sm.size())
    {
      size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左边矩阵的起始位值
      size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右边矩阵起始位值
      if(AddrLeft < AddrRight)//左<右,将左边有效值放入和矩阵中,左边的索引加加
      {
        ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
        iLidx++;
      }
      else if(AddrLeft > AddrRight)
      {
        ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
        iRidx++;
      }
      else//当左边等于右边判断相加后和是否为0,不为0放入
      {
        Trituple<T> temp(_sm[iLidx]);
        temp._data += sp._sm[iRidx]._data;
        if(temp._data)
        {
          ret._sm.push_back(temp);
          iLidx++;
          iRidx++;
        }
      }
    }
    while(iLidx < _sm.size())//左边还有剩余则放入剩余元素
    {
      ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
      iLidx++;
    }
    while(iRidx < sp._sm.size())
    {
      ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
      iRidx++;
    }
    return ret;
  }
private:
  size_t _row;
  size_t _col;
  vector<Trituple<T>> _sm;
  T _invalid;//无效值
}; 

int main()
{
  int arr[6][5] = {
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,0,0,0},
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,0,0,0}};
  int arr1[6][5] = {
    {1,0,3,0,5},
    {0,0,0,0,0},
    {0,0,2,4,0},
    {1,0,3,0,5},
    {0,0,0,1,0},
    {0,0,0,0,1}};
  SparseMatrix<int> s((int*)arr,6,5,0);
  SparseMatrix<int> s1((int*)arr1,6,5,0);
  cout<<"访问三行四列元素"<<endl;
  cout<<s.Acess(3,4)<<endl;
  cout<<s<<endl;
  cout<<"快速转置"<<endl;
  cout<<s.FastTransport();
  cout<<endl;
  cout<<"矩阵s:"<<endl;
  cout<<s<<endl;
  cout<<"矩阵s1:"<<endl;
  cout<<s1<<endl;
  cout<<"s+s1求和:"<<endl;
  cout<<s1+s<<endl;
  system("pause");
  return 0;
}

运行结果截图:

在上面的代码中用到C++模板、标准库中vector容器,以及迭代器实现了一些基本的操作,如访问稀疏矩阵中某个元素,输出稀疏矩阵、稀疏矩阵的转置以及快速转置还有两个稀疏矩阵的加法。

快速转置操作的基本思路是:

(1)统计原矩阵中每一列有多少个有效元素;

(2)原矩阵中每一列在新矩阵中的起始地址;

(3)放置元素到新空间中。

还需注意的是,在我们打印这个稀疏矩阵时虽然也可以直接调用访问元素的Acess接口,但是每次进去之后都得遍历一遍,时间复杂度较高,所以我们不采取这种办法,而是比较当前行列的值,若相等输出有效元素,不等则输出无效元素0。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-06-08

C++ 实现稀疏矩阵的压缩存储的实例

C++ 实现稀疏矩阵的压缩存储的实例 稀疏矩阵:M*N的矩阵,矩阵中有效值的个数远小于无效值的个数,且这些数据的分布没有规律. 稀疏矩阵的压缩存储:压缩存储值存储极少数的有效数据.使用{row,col,value}三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放. 实现代码: #include <iostream> #include <vector> using namespace std; template<class T> struct

C语言实现稀疏矩阵

本文实例为大家分享了C语言实现稀疏矩阵的具体代码,供大家参考,具体内容如下 #include "stdio.h" #define maxsize 10 typedef struct { int i,j; //非零元素的行.列 int v; //非零元素的值 }Triple; typedef struct { Triple data[maxsize]; int m,n; //矩阵的行.列 }TSMarix; InitTriple(TSMarix *M) { int i,j,k,v,t;

Python使用稀疏矩阵节省内存实例

推荐系统中经常需要处理类似user_id, item_id, rating这样的数据,其实就是数学里面的稀疏矩阵,scipy中提供了sparse模块来解决这个问题,但scipy.sparse有很多问题不太合用: 1.不能很好的同时支持data[i, ...].data[..., j].data[i, j]快速切片: 2.由于数据保存在内存中,不能很好的支持海量数据处理. 要支持data[i, ...].data[..., j]的快速切片,需要i或者j的数据集中存储:同时,为了保存海量的数据,也需

python实现稀疏矩阵示例代码

工程实践中,多数情况下,大矩阵一般都为稀疏矩阵,所以如何处理稀疏矩阵在实际中就非常重要.本文以Python里中的实现为例,首先来探讨一下稀疏矩阵是如何存储表示的. 1.sparse模块初探 python中scipy模块中,有一个模块叫sparse模块,就是专门为了解决稀疏矩阵而生.本文的大部分内容,其实就是基于sparse模块而来的. 第一步自然就是导入sparse模块 >>> from scipy import sparse 然后help一把,先来看个大概 >>> h

Python 稀疏矩阵-sparse 存储和转换

稀疏矩阵-sparsep from scipy import sparse 稀疏矩阵的储存形式 在科学与工程领域中求解线性模型时经常出现许多大型的矩阵,这些矩阵中大部分的元素都为0,被称为稀疏矩阵.用NumPy的ndarray数组保存这样的矩阵,将很浪费内存,由于矩阵的稀疏特性,可以通过只保存非零元素的相关信息,从而节约内存的使用.此外,针对这种特殊结构的矩阵编写运算函数,也可以提高矩阵的运算速度. scipy.sparse库中提供了多种表示稀疏矩阵的格式,每种格式都有不同的用处,其中dok_m

C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储

对称矩阵及稀疏矩阵的压缩存储 1.稀疏矩阵 对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse). 人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律. 实现代码: //稀疏矩阵及其压缩存储 #pragma once #include <vector> #include <iostream> using namespace std; templa

Java数据结构之稀疏矩阵定义与用法示例

本文实例讲述了Java数据结构之稀疏矩阵定义与用法.分享给大家供大家参考,具体如下: 稀疏矩阵非零元素的三元组类: package com.clarck.datastructure.matrix; /** * 稀疏矩阵的压缩存储 * * 稀疏矩阵非零元素的三元组类 * * @author clarck * */ public class Triple implements Comparable<Triple> { // 行号,列号, 元素值,默认访问权限 int row, colum, val

对称矩阵的压缩储存讲解

一.存储矩阵用一个二维数组即可: 二.什么是对称矩阵: 设一个N*N的方阵A,A中任意元素Aij,当且仅当 Aij == Aji(0 <= i <= N-1&& 0 <= j <= N-1),则矩阵A是对称矩阵.以矩阵的对角线为分隔,分为上三角和下三角 三.对称矩阵的压缩储存: 压缩存储称矩阵存储时只需要存储上三角/下三角的数据,所以最多存储n(n+1)/2个数据(相当于1+2+-+n,即等差数列求和). 对称矩阵和压缩存储的对应关系:下三角存储i>=j, S

基于C中一个行压缩图的简单实现代码

首先简单说一下什么是行压缩图,其实严格意义上应该是行压缩矩阵.正常情况下,矩阵是用二维数组简单存储的,但是如果是稀疏矩阵,也就是零很多的时候,这样比较浪费空间.所以就有各种节省空间的存储方式,三元组存储就是其中一种. 什么是三元组呢?一个三元组就是(row,col,value),这样把所有不为零的值组成一个向量.这种存储方式比二维数组节省了不少空间,当然还可以进一步节省,因为三元组里面row或者col重复存储了,一行或者一列存一次就行了,按这种思路走下去就是行压缩存储了. 那具体什么是行压缩存储

Java实现文件压缩与解压的示例[zip格式,gzip格式]

Java实现ZIP的解压与压缩功能基本都是使用了Java的多肽和递归技术,可以对单个文件和任意级联文件夹进行压缩和解压,对于一些初学者来说是个很不错的实例. zip扮演着归档和压缩两个角色:gzip并不将文件归档,仅只是对单个文件进行压缩,所以,在UNIX平台上,命令tar通常用来创建一个档案文件,然后命令gzip来将档案文件压缩. Java I/O类库还收录了一些能读写压缩格式流的类.要想提供压缩功能,只要把它们包在已有的I/O类的外面就行了.这些类不是Reader和Writer,而是Inpu

JavaScript数据结构之链表的实现

前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

超强、超详细Redis数据库入门教程

[本教程目录] 1.redis是什么 2.redis的作者何许人也 3.谁在使用redis 4.学会安装redis 5.学会启动redis 6.使用redis客户端 7.redis数据结构 – 简介 8.redis数据结构 – strings 9.redis数据结构 – lists 10.redis数据结构 – 集合 11.redis数据结构 – 有序集合 12.redis数据结构 – 哈希 13.聊聊redis持久化 – 两种方式 14.聊聊redis持久化 – RDB 15.聊聊redis持