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

对称矩阵及稀疏矩阵的压缩存储

1.稀疏矩阵

 对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse)。

  人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律。

实现代码:

//稀疏矩阵及其压缩存储
#pragma once 

#include <vector>
#include <iostream>
using namespace std; 

template<class T>
struct Triple
{
 size_t _r;
 size_t _c;
 T _value; 

 Triple(size_t row = 0, size_t col = 0, const T& value = T())
  :_r(row)
  ,_c(col)
  ,_value(value)
 {}
}; 

template <class T>
class SparseMatrix
{
public:
 SparseMatrix()
 :_row(0)
  ,_col(0)
  ,_illegal(T())
 {} 

 SparseMatrix(T* arr, size_t row, size_t col, const T& illegal)
  :_row(row)
  ,_col(col)
  ,_illegal(illegal)
 {
  for(size_t i = 0; i<row; ++i)
  {
   for(size_t j = 0; j<col; ++j)
   {
    if(arr[i*col+j] != illegal)
    {
     Triple<T> t(i,j,arr[i*col+j]);
     _matrix.push_back(t);
    }
   }
  }
 } 

 void Display()
 { 

  vector<Triple<T> >::iterator iter;
  iter = _matrix.begin();
  for(size_t i = 0; i<_row; ++i)
  {
   for(size_t j = 0; j<_col; ++j)
   {
    if(iter!=_matrix.end()
     &&iter->_r == i
     &&iter->_c == j)
    {
     cout << iter->_value <<" ";
     ++iter;
    }
    else
    {
     cout << _illegal <<" ";
    }
   }
   cout << endl;
  }
 cout << endl;
 }
 //普通转置(行优先存储)
 //列变行,从0列开始,将列数据一个一个放进转置矩阵
 SparseMatrix<T> Transpose()
 {
  SparseMatrix<T> tm;
  tm._row = _col;
  tm._col = _row;
  tm._illegal = _illegal;
  tm._matrix.reserve(_matrix.size()); 

  for(size_t i = 0; i<_col; ++i)
  {
   size_t index = 0;
   while(index < _matrix.size())
   {
    if(_matrix[index]._c == i)
    {
     Triple<T> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
     tm._matrix.push_back(t);
    }
    ++index;
   }
  }
  return tm;
 } 

 SparseMatrix<T> FastTranspose()
 {
  SparseMatrix<T> tm;
  tm._row = _col;
  tm._col = _row;
  tm._illegal = _illegal;
  tm._matrix.resize(_matrix.size()); 

  int* count = new int[_col];//记录每行的元素个数
  memset(count, 0, sizeof(int)*_col);
  int* start = new int[_col];//转置矩阵中元素的位置
  start[0] = 0; 

  size_t index = 0;
  while(index < _matrix.size())
  {
   count[_matrix[index]._c]++;
   ++index;
  } 

  for(size_t i=1; i<_col; ++i)
  {
   start[i] = start[i-1] + count[i-1];
  } 

  index = 0;
  while(index < _matrix.size())
  {
   Triple<T> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
   tm._matrix[start[_matrix[index]._c]++] = t; //核心代码
   ++index;
  } 

  delete[] count;
  delete[] start;
  return tm;
 }
protected:
 vector<Triple<T> > _matrix;
 size_t _row;
 size_t _col;
 T _illegal;
};

2.对称矩阵

实现代码:

//对称矩阵及其压缩存储 

#pragma once
#include <iostream>
using namespace std; 

template <class T>
class SymmetricMatrix
{
public:
 SymmetricMatrix(T* arr, size_t n)
  :_n(n)
  ,_matrix(new T[n*(n+1)/2])
 {
  size_t index = 0;
  for(size_t i = 0; i<n; ++i)
  {
   for(size_t j=0; j<n;++j)
   {
    if(i >= j)
    {
     _matrix[index] = arr[i*n+j];
     ++index;
    }
    else
    {
     continue;
    }
   }
  }
 }
 void Display()
 {
  for(size_t i =0; i < _n; ++i)
  {
   for(size_t j = 0; j < _n; ++j)
   {
   /* if(i<j)
    {
     swap(i,j);
     cout<<_matrix[i*(i+1)/2+j]<<" ";
     swap(i,j);
    }
    else
     cout<<_matrix[i*(i+1)/2+j]<<" ";
   */
    cout << Access(i,j) << " ";
   }
   cout << endl;
  }
  cout << endl;
 } 

 T& Access(size_t row, size_t col)
 {
  if(row<col)
  {
   swap(row, col);
  }
  return _matrix[row*(row+1)/2+col];
 }
 ~SymmetricMatrix()
 {
  if(_matrix != NULL)
  {
   delete[] _matrix;
   _matrix = NULL;
  }
 }
protected:
 T* _matrix;
 size_t _n; //对称矩阵的行列大小
};

以上就是C++ 数据结构实现稀疏矩阵与对称矩阵,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-08-10

数据结构之矩阵行列和相等的实例

以下为展示"矩阵行列和相等"的简单示例: 1.用c语言实现的版本 #include <stdio.h> #include <math.h> void main() { int a[16][16],i,j,n,k; printf("Please input n(1~15,it must be odd.): "); scanf("%d",&n); while(!(n>=1&&n<=15) |

python矩阵的转置和逆转实例

如下所示: # 矩阵的转置 def transpose(list1): return [list(row) for row in zip(*list1)] list1 = [[1, 4], [2, 5], [3, 6]] print(transpose(list1)) # [[1, 2, 3], [4, 5, 6]] 矩阵转置 用zip将一系列可迭代对象中的元素打包为元组,之后将这些元组放置在列表中,两步加起来等价于行列转置. # 矩阵逆转 def invert(list1): return [

Python计算矩阵的和积的实例详解

python的numpy库提供矩阵运算的功能,因此我们在需要矩阵运算的时候,需要导入numpy的包. 一.numpy的导入和使用 from numpy import *;#导入numpy的库函数 import numpy as np; #这个方式使用numpy的函数时,需要以np.开头. 二.矩阵的创建 由一维或二维数据创建矩阵 from numpy import *; a1=array([1,2,3]); a1=mat(a1); 创建常见的矩阵 data1=mat(zeros((3,3)));

java数据结构之二分查找法 binarySearch的实例

java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

C语言数据结构之使用链表模拟栈的实例

C语言数据结构之使用链表模拟栈的实例 以下是"使用链表模拟栈"的简单示例: 1. 用C语言实现的版本 #include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct node{ datatype data; struct node *next; } stack; stack* m_stack = NULL; /* 创建链表,从表头插入新元素 */ void creat(void

C++中实现矩阵的加法和乘法实例

C++中实现矩阵的加法和乘法实例 实现效果图: 实例代码: #include<iostream> using namespace std; class Matrix { int row;//矩阵的行 int col;//矩阵的列 int **a;//保存二维数组的元素 public: Matrix();//默认构造函数 Matrix(int r, int c); Matrix(const Matrix &is);//拷贝构造函数 void Madd(const Matrix &

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,

js图数据结构处理 迪杰斯特拉算法代码实例

这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /*//1.确定数据结构, mapf[i][j] 为点i到点j的距离 [ Infinity 2 5 Infinity Infinity Infinity Infinity 2 6 Infinity Infinity Infinity Infinity 7 1 Infinity Infinity 2 Infinity 4 Infinity

python矩阵转换为一维数组的实例

实例如下所示: >>>from compiler.ast import flatten >>>X matrix([[ 1, 17, 13, 221, 289, 169], [ 1, 17, 14, 238, 289, 196], [ 1, 17, 15, 255, 289, 225], [ 1, 18, 13, 234, 324, 169], [ 1, 18, 14, 252, 324, 196], [ 1, 18, 15, 270, 324, 225], [ 1, 1

Python图片转换成矩阵,矩阵数据转换成图片的实例

如下所示: # coding=gbk from PIL import Image import numpy as np # import scipy def loadImage(): # 读取图片 im = Image.open("lena.jpg") # 显示图片 im.show() im = im.convert("L") data = im.getdata() data = np.matrix(data) # print data # 变换成512*512 d