个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 35 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

1.稀疏矩阵 。

　对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）.

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

实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//稀疏矩阵及其压缩存储
#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.对称矩阵 。

实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//对称矩阵及其压缩存储
 
#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++ 数据结构实现稀疏矩阵与对称矩阵，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ 。

原文链接：http://blog.csdn.net/xhfight/article/details/52843248 。

最后此篇关于C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储的文章就讲到这里了,如果你想了解更多关于C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

35 4 0
文章推荐： 解决Python字典查找报Keyerror的问题
文章推荐： 摩尔庄园手游芝麻种子怎么获得 摩尔庄园手游芝麻有什么用
文章推荐： 摩尔庄园手游孔明灯在哪里领取 摩尔庄园手游孔明灯怎么放飞
文章推荐： 浅谈tf.train.Saver()与tf.train.import_meta_graph的要点
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com