稀疏矩陣的壓縮存儲(chǔ)及轉(zhuǎn)置算法

只怪 博主智商無(wú)下限，花了一個(gè)周末終于把系數(shù)矩陣的壓縮存儲(chǔ)及其轉(zhuǎn)置給弄明白了，所以今天就和大家分享一下我的學(xué)習(xí)過(guò)程啦?。?！

稀疏矩陣是指矩陣中大多數(shù)元素為零的矩陣，從直觀上講，非零元素的個(gè)數(shù)低于總元素的30%時(shí)，這樣的矩陣稱為稀疏矩陣。

1.稀疏矩陣的三元組組表示法

對(duì)于稀疏矩陣的壓縮存儲(chǔ)，采取只存儲(chǔ)非零元素的方法，由于稀疏矩陣中非零元素的分布沒(méi)有規(guī)律，所以呢？？？在存儲(chǔ)非零元素的時(shí)候必須給每個(gè)元素做個(gè)標(biāo)記（非零元素在矩陣中所處的行號(hào)和列號(hào)）。

//稀疏矩陣三元組表類型的定義
struct Triple
{
T _value;
size_t _row;
size_t _col;

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

（1）Triple是包含三個(gè)域的結(jié)構(gòu)體類型，其元素是為了存儲(chǔ)非零元的三元組

2.稀疏矩陣的壓縮存儲(chǔ)

就上圖給出的矩陣而言，運(yùn)用三元組壓縮存儲(chǔ)的方法存儲(chǔ)后的結(jié)果是醬紫滴

源代碼是醬紫滴：

//用三元組表示實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)
	SpareMatrix(T* a,size_t m,size_t n,const T& invalid)
		:_rowsize(m)
		,_colsize(n)
		,_invalid(invalid)
	{
		for(size_t i=0;i<m;i++)
		{
			for(size_t j=0;j<n;j++)
			{
				if(a[i*n+j]!=invalid)
				{
				_a.push_back(Triple<T>(i,j,a[i*n+j]));
				}
			}
		}
	
	}

3.稀疏矩陣的列序遞增轉(zhuǎn)置法

采用被轉(zhuǎn)置矩陣按照列序遞增的的順序進(jìn)行轉(zhuǎn)置，并依此將將其送入轉(zhuǎn)置后的三元組表中，這樣子的話轉(zhuǎn)置后的三元組表恰好是以行序號(hào)為主的哦 。

具體做法：

（1）找出轉(zhuǎn)置后的第一行元素：第一遍從頭至尾掃描三元組表，找出所有_col為1的三元組，轉(zhuǎn)置后按順序放到開(kāi)辟好新的三元組表中

（2）找出轉(zhuǎn)置后的第二行元素：第一遍從頭至尾掃描三元組表，找出所有_col為2的三元組，轉(zhuǎn)置后按順序放到開(kāi)辟好新的三元組表中

 源代碼是醬紫滴：
//稀疏矩陣的轉(zhuǎn)置
SpareMatrix<T> Transport()
{
      SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  //給構(gòu)建好的匿名對(duì)象開(kāi)辟空間,但是不改變size的大小，開(kāi)辟后初始化的值為原來(lái)的。
  tmp._a.reserve(_a.size());
  for(size_t i=0;i<_colsize;i++)
  {
  size_t index=0;
  for(index=0;index<_a.size();index++)
  {
   if(_a[index]._col==i)
   {
   Triple <T> tp;
   tp._row=_a[index]._col;
   tp._col=_a[index]._row;
   tp._value=_a[index]._value;
   tmp._a.push_back(tp);
   }
  }
  }
  return tmp;
  
}

注釋：雖然構(gòu)建了一個(gè) SpareMatrix<T> tmp類型的對(duì)象但是并沒(méi)有給它開(kāi)辟和_a一樣大小的空間，所以要調(diào)用reserve或者resize兩個(gè)函數(shù)中任意一個(gè)即可，否則當(dāng)你在運(yùn)行程序的時(shí)候會(huì)奔潰哦，智商無(wú)下線的博主昨天就是犯了這個(gè)錯(cuò)誤，程序跑起來(lái)的時(shí)候，老是彈出這樣的框框：

最后調(diào)試了好久才發(fā)現(xiàn)問(wèn)題所在氣死寶寶啦，

算法分析：

算法主要耗費(fèi)在雙重循環(huán)中，其時(shí)間復(fù)雜度為o(_colsize*_a.size());

4.稀疏矩陣的一次定位快速轉(zhuǎn)置算法

算法思想：

（1）計(jì)算待轉(zhuǎn)置矩陣三元組表中每一列非零元素的個(gè)數(shù)，即轉(zhuǎn)置后矩陣三元組表每一行中非零元素的個(gè)數(shù)。

（2）計(jì)算待轉(zhuǎn)置矩陣每一列中第一個(gè)非零元素三元組表中的具體位置。

源代碼是醬紫滴：

/稀疏矩陣的快速轉(zhuǎn)置
SpareMatrix<T> FastTransport()
{
  SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  int* rowcounts=new int[tmp._rowsize];
  int* rowstart=new int[tmp._rowsize];
  memset(rowcounts,0,sizeof((int*)_colsize));
  memset(rowstart,0,sizeof((int*)_colsize));
  size_t index=0;
 
  //計(jì)算待轉(zhuǎn)置矩陣每一列非零元素的個(gè)數(shù)
  while(index<_a.size())
  {
  rowcounts[_a[index]._col]++;
  index++;
  }


//計(jì)算待轉(zhuǎn)置矩陣每一列第一個(gè)非零元素在三元組表中的位置
rowstart[0]=0;
for(size_t i=1;i<_colsize;i++)
{
rowstart[i]=rowstart[i-1]+rowcounts[i-1];
}

index=0;
//給_a的匿名對(duì)象開(kāi)辟_a大小的空間
    tmp._a.resize(_a.size());
while(index<_a.size())
{/*
size_t rowindex=_a[index]._col;*/
int& start=rowstart[_a[index]._col];

Triple<T> tp;
tp._value=_a[index]._value;
tp._row=_a[index]._col;
tp._col=_a[index]._row;
tmp._a[start++]=tp;
index++;
}
return tmp;
}

算法分析：

一次定位快速轉(zhuǎn)置算法時(shí)間主要耗費(fèi)在三個(gè)并列的循環(huán)中，因而時(shí)間復(fù)雜度為o(_a.size+_colsize).

完整的源代碼：

//稀疏矩陣的壓縮存儲(chǔ)
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
//稀疏矩陣三元組表類型的定義
struct Triple
{
T _value;
size_t _row;
size_t _col;

Triple(size_t row=0,size_t col=0,const T& value=T())
:_value(value)
,_row(row)
,_col(col)
{}

};
template<typename T>
//稀疏矩陣
class SpareMatrix
{
public:

SpareMatrix()
:_rowsize(0)
,_colsize(0)
,_invalid(0)
{}
//用三元組表示實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)
SpareMatrix(T* a,size_t m,size_t n,const T& invalid)
:_rowsize(m)
,_colsize(n)
,_invalid(invalid)
{
for(size_t i=0;i<m;i++)
{
for(size_t j=0;j<n;j++)
{
if(a[i*n+j]!=invalid)
{
_a.push_back(Triple<T>(i,j,a[i*n+j]));
}
}
}

}
//稀疏矩陣的轉(zhuǎn)置
SpareMatrix<T> Transport()
{
      SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  //給構(gòu)建好的匿名對(duì)象開(kāi)辟空間,但是不改變size的大小，開(kāi)辟后初始化的值為原來(lái)的。
  tmp._a.reserve(_a.size());
  for(size_t i=0;i<_colsize;i++)
  {
  size_t index=0;
  for(index=0;index<_a.size();index++)
  {
   if(_a[index]._col==i)
   {
   Triple <T> tp;
   tp._row=_a[index]._col;
   tp._col=_a[index]._row;
   tp._value=_a[index]._value;
   tmp._a.push_back(tp);
   }
  }
  }
  return tmp;
  
}
//稀疏矩陣的快速轉(zhuǎn)置
SpareMatrix<T> FastTransport()
{
  SpareMatrix<T> tmp;
  tmp._rowsize = _colsize;
  tmp._colsize = _rowsize;
  tmp._invalid=_invalid;
  int* rowcounts=new int[tmp._rowsize];
  int* rowstart=new int[tmp._rowsize];
  memset(rowcounts,0,sizeof((int*)_colsize));
  memset(rowstart,0,sizeof((int*)_colsize));
  size_t index=0;
 
  //計(jì)算待轉(zhuǎn)置矩陣每一列非零元素的個(gè)數(shù)
  while(index<_a.size())
  {
  rowcounts[_a[index]._col]++;
  index++;
  }


//計(jì)算待轉(zhuǎn)置矩陣每一列第一個(gè)非零元素在三元組表中的位置
rowstart[0]=0;
for(size_t i=1;i<_colsize;i++)
{
rowstart[i]=rowstart[i-1]+rowcounts[i-1];
}

index=0;
//給_a的匿名對(duì)象開(kāi)辟_a大小的空間
    tmp._a.resize(_a.size());
while(index<=_a.size())
{/*
size_t rowindex=_a[index]._col;*/
int& start=rowstart[_a[index]._col];

Triple<T> tp;
tp._value=_a[index]._value;
tp._row=_a[index]._col;
tp._col=_a[index]._row;
tmp._a[start++]=tp;
index++;
}
return tmp;
}
void display()
{
   size_t index=0;
for(size_t i=0;i<_rowsize;i++)
{
for(size_t j=0;j<_colsize;j++)
{
   if(index<_a.size() && _a[index]._row==i && _a[index]._col==j)
   {
        cout<<_a[index++]._value<<" ";
   }
   else
   {
   cout<<_invalid<<" ";
   }
}
cout<<endl;
}
cout<<endl;
}


protected:
vector<Triple <T> > _a;
size_t _rowsize;
size_t _colsize;
T _invalid;

};

void test()
{
    int a[4][4]={{1,0,0,0},
                 {2,2,0,0},
                 {0,1,3,0},
                 {1,0,0,4}};
SpareMatrix<int>sm1((int*)a,4,4,0);
sm1.display();

SpareMatrix<int> sm2=sm1.Transport();
sm1.display();

SpareMatrix<int> sm3=sm1.FastTransport();
sm1.display();
}
int main()
{
test();
getchar();
return 0;
}