稀疏矩陣的快速轉置算法
本篇部落客要内容摘要：
1. 什麼是稀疏矩陣
2. 稀疏矩陣的壓縮存儲
3. 稀疏矩陣的轉置（number one）
4. 稀疏矩陣的快速轉置(number two)
稀疏矩陣的壓縮存儲
什麼是稀疏矩陣？
/* 這是大學的以麼課《線性代數》學的，不知道大家還記得多少，在老師講到實作稀疏矩陣的壓縮存儲的時候，我知記得我當時考了75分，其它的就呵呵了-_-!!!
言歸正傳，稀疏矩陣，例如：
--------------
0 0 2 0 4
0 0 0 0 0
0 1 0 3 0
5 0 6 0 0
--------------
上面這個就是稀疏矩陣，仔細觀察，好像沒什麼規律吧，而且，習慣上我們把非 0 資料稱為有效資料，在這個矩陣中，明顯0要比有效資料多不少，這就是我麼為什麼要對壓縮存儲了； 避免浪費嘛！ 高效率，低消耗是我們程式員追求的完美！
那麼，問題來了，前面我們講過關于對稱矩陣的壓縮存儲http://blog.csdn.net/bitboss/article/details/52599692，用一維數組存儲下三角資料，那麼這裡該怎麼存？
相信大家都可以第一時間反應過來，把有效資料都拿出來存儲不就好了嘛，對，就是這樣，那麼稀疏矩陣的有效資料是無規律的，我們是不是還得把它們的坐标也存儲起來，否則是不是找不了。。。。。這塊有一個對象有三個屬性都要存起來，我們用什麼好呢？ 結構體，沒問題，這裡我選擇用結構體來存儲單獨的資料，而vector（順序表）存儲這些結構體，當然，并不是每個無效值都是0，我們還需要一個變量來表示我們的無效值，好了，，，架構成形了，，，來實作代碼吧！
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Triple //儲存資料的結構體
{
size_t _row;
size_t _col;
T _data;
Triple(size_t row = , size_t col = , const T& x = T())
:_row( row)
,_col( col)
,_data( x)
{}
};
template<class T>
class SparseMatrix
{
public:
SparseMatrix(T * arr, size_t m , size_t n, const T& invalid) //注意傳參的含義
:_m( m)
,_n( n)
,_invalid( invalid)
{
将有效資料都存入vector内;
for(size_t i = ; i < _m; i++)
{
for(size_t j = ; j < _n; j++)
{
if(arr [i*n + j] != _invalid) //有效資料的判定條件；
{
Triple<T > tmp(i,j,arr[i* n + j]);
_martix.push_back(tmp);
}
}
}
}
列印稀疏矩陣--就是從壓縮存儲還原的過程；
void Display()
{
int index = ;
for(size_t i = ; i < _m; i++)
{
for(size_t j = ; j < _n; j++)
{
if( index < _martix.size()&&
_martix[index]._row == i&&
_martix[index]._col == j)//判斷該位置是否放置有效資料；
{
cout<<_martix[index++]._data<< " ";
}
else //否則該位置放置無效資料
cout<<_invalid<< " ";
}
cout<<endl;
}
cout<<endl;
}
private:
size_t _m; //矩陣的行數
size_t _n; //矩陣的列數
T _invalid; //無效資料
vector<Triple <T> > _martix; //儲存資料所有結構體的vector
};
void testSparseMatrix()
{
int a[][] = //測試用例
{{, , , , },
{, , , , },
{, , , , },
{, , , , },
{, , , , },
{, , , , }};
SparseMatrix<int > s((int *)a, , , ); //注意類參數是一維數組指針，強制轉換；
s.Display ();
}
int main()
{
testSparseMatrix();
system( "pause");
return ;
}
上面就是稀疏矩陣的壓縮存儲，了解過之後，
我們就來看看稀疏矩陣的轉置
還是以這個矩陣為例：
0 0 2 0 4
0 0 0 0 0
0 1 0 3 0
5 0 6 0 0
轉置就是把一個矩陣的行變成新矩陣的列，同樣，列也變成新矩陣的行，上面的矩陣轉置為：
0 0 0 5
0 0 1 0
2 0 0 6
0 0 3 0
4 0 0 0
從四行五列變為五行四列；而我們的稀疏矩陣采用的行優先的壓縮存儲，壓縮存儲的順序
_
martix：2，4，1，3，5，6
//行優先存儲： 一行一行的存儲；
// 列優先存儲： 一列一列的存儲；
而轉置之後的矩陣也是按照行優先的壓縮存儲，，是不是剛好是原矩陣的列優先存儲；
_martix2：5，1，2，6，3，4
現在的問題是怎樣把原矩陣的壓縮存儲變為轉置矩陣的壓縮存儲？
這裡有兩種方法，我們先來看第一種：number one
時刻記住目的便是将原矩陣的行優先存儲變為列優先存儲，那麼過程就很簡單了，壓縮數組裡的每一個元素（結構體）都儲存有自己的下标，那先開辟一個和壓縮數組大小同樣的容器，然後周遊這個數組，第一次找出第0列的元素依次存入新的容器，交換容器内新元素的下标（轉置之後行和列與原先是相反的）接着第二次等等；直到新數組滿，過程如下：
_martix：，，，，，;（原壓縮數組）
_martix2: ;(新壓縮數組)
對照着原矩陣比較好找：
第一次周遊_martix找到列下标為0的元素依次放入_martix2
_martix2:5 ;
//注意：放入一個元素後都會把新數組中的元素下标交換！
第二次周遊_martix找到列下标為1的元素依次放入_martix2
_martix2:5， 1 ；
第三次周遊_martix找到列下标為2的元素依次放入_martix2
_martix2:5 ，1， 2， 6 ；
第四次周遊_martix找到列下标為3的元素依次放入_martix2
_martix2:5 ，1， 2， 6 ，3 ；
第五次周遊_martix找到列下标為4的元素依次放入_martix2
_martix2:5 ，1， 2， 6 ，3 ，4；
新的壓縮存儲數組有了，覆寫掉原來的壓縮存儲數組，那麼接下來在最後交換一下整個矩陣的行和列數（轉置之後行數和列數與之前相反）就可以列印了！
時間複雜度：O（列數*有效資料個數）
具體算法：（完整代碼在最後面）
//快速轉置算法 number one
void FastTransposition()
{
vector<Triple <T> > _martix2 ;
size_t n = _martix .size ();
_martix2 .resize(n);
size_t count = ;
for(size_t i = ; i < n ;i++)
{
for(size_t j = ; j < n; j++)
{
if(_martix[j]._col == i)
{
//swap(_martix[j]._col,_martix[j]._row);
_martix2 [count] = _martix [j];
swap(_martix2[count]._col,_martix2[count]._row);
count++;
}
}
}
for(size_t i = ; i< n; i++)
{
_martix [i] = _martix2 [i];
}
swap(_m,_n);
}
第二種方法： number two
第二種方法的産生就是為了減小時間複雜度，以空間換取效率的方法；把兩次循環變為一層循環；
首先呢，我們需要兩個數組，num[矩陣的列數] start[矩陣的列數]；
num[]的作用是統計原矩陣每一列有多少元素；
start[]的作用是計算出每一列的第一個元素在新的壓縮矩陣中的位置；
為什麼要這麼做？
第一種方法中我們需要不停的循環原壓縮數組，才能把新壓縮數組中元素的位置确定，比如：周遊列下标為0的元素依次放入_martix2中，就周遊了一遍；
現在我們想可不可以我每周遊到_martix中的一個元素，我就可以确定它在_martix2中對應的位置，
對照着原矩陣看：
0 0 2 0 4
0 0 0 0 0
0 1 0 3 0
5 0 6 0 0
比如：
_martix：2，4，1，3，5，6;（原壓縮數組）
我周遊到 2的時候，就放在第3個位置
_martix2: , , 2, , , ;
周遊到4的時候，就放在最後一個位置
_martix2: , , 2, , , 4;
以此類推，我們是不是周遊一遍_martix就可以了；那麼接下來的問題是我們根據什麼來确定在_martix2中的位置；
觀察原矩陣和_martix就會發現每一列的元素在_martix2中的存儲都是按照原矩陣從上到下有前後順序的；
_martix2：5，1，2，6，3，4；
比如：第一列隻有5，第二列隻有1，第三列 2的位置在 6的前面，第四列隻有3，第五列隻有4；
這個很容易就可以想明白，而_martix2采取的是原矩陣的列優先存儲每一列第一個元素肯定是在前一列元素之後，那麼隻要确定了每一列第一個元素在_martix2中的位置，就好辦了， 第一列的第一個的位置确定了，第一列剩下的元素就跟在後面，以此類推；
這就是為什麼我們會有num[]和start[]兩個數組的原因了；
當周遊_martix的時候，判斷元素的列下标，作為start[]的下标找出該元素的存儲位置，文字了解起來不容易想明白，還是實際示範一下，還是以上面的矩陣為例：
num[] = 1,1,2,1,1;//每一列有多少元素
注意：num,start的下标都代表的是列；
start[0] = 0;//第一列第一個元素的存放位置肯定是0下标出處（好好了解）；
start[1] = start[1 - 1] + num[1 - 1]; //第二列第一個元素的位置肯定要越過第一列的所有元素；
start[n] = start[n - 1] + num[n - 1];//規律就出來了，需要在這裡好好了解；
start[] = 0,1,2,4,5;
有了對應位置我們就可以給_martix2中放資料了；//代碼中看
需要注意的一點是假如我們把第n列的第一個元素放入_martix2後，對應的start[n]++；
為什麼呢？
start[]存放的是每一列第一個元素的位置的下标，第一個放進去之後，這一列第二個元素要放在這一列第一個元素的後面，而第一個的下标是start[n],是不是得往後推一個位置，以此類推；
例如：
原矩陣的第三列的第一個元素是2，2在_martix2中存放的位置是_martix2[start[3]];
而第三列第二個元素是6，6應該存放在2的後面，就應該放在_martix2[start[3]+1];
算法如下：
//快速轉置算法 number two
void FastTransposition2()
{
//typedef start[_martix[i]._col] pos;
vector<Triple <T> > _martix2 ;
size_t n = _martix .size ();
_martix2 .resize(n);
size_t num[] = {}; //統計原矩陣每列的元素個數
size_t start[] = {};//統計每一列第一個元素在_martix2中的存放下标位置
for(size_t i = ; i < n; i++)
num[_martix[i]._col]++;
//為什麼i從1開始？
//start[i] = 0;
for(size_t i = ; i < ; i++)
start[i] = start[i - ] + num[i - ];
for(size_t i = ; i < n; i++)
{
_martix2 [start[_martix[i]._col]] = _martix[i];
swap(_martix2[start[_martix[i]._col]]._col,_martix2[start[_martix[i]._col]]._row);
start[_martix[i]._col]++;
}
//最後這兩步和第一種的方法一樣，友善列印；
//最後覆寫_martix
for(size_t i = ; i< n; i++)
{
_martix [i] = _martix2 [i];
}
swap(_m,_n);
}
*/
//完整代碼
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Triple //儲存資料的結構體
{
size_t _row;
size_t _col;
T _data;
Triple(size_t row = , size_t col = , const T& x = T())
:_row( row)
,_col( col)
,_data( x)
{}
};
template<class T>
class SparseMatrix
{
public:
SparseMatrix(T * arr, size_t m , size_t n, const T& invalid) //注意傳參的含義
:_m( m)
,_n( n)
,_invalid( invalid)
{
//将有效資料都存入vector内;
for(size_t i = ; i < _m; i++)
{
for(size_t j = ; j < _n; j++)
{
if(arr [i*n + j] != _invalid) //有效資料的判定條件；
{
Triple<T > tmp(i,j,arr[i* n + j]);
_martix.push_back(tmp);
}
}
}
}
//快速轉置算法 number one
void FastTransposition()
{
vector<Triple <T> > _martix2 ;
size_t n = _martix .size ();
_martix2 .resize(n);
size_t count = ;
for(size_t i = ; i < n ;i++)
{
for(size_t j = ; j < n; j++)
{
if(_martix[j]._col == i)
{
//swap(_martix[j]._col,_martix[j]._row);
_martix2 [count] = _martix [j];
swap(_martix2[count]._col,_martix2[count]._row);
count++;
}
}
}
for(size_t i = ; i< n; i++)
{
_martix [i] = _martix2 [i];
}
swap(_m,_n);
}
//快速轉置算法 number two
void FastTransposition2()
{
//typedef start[_martix[i]._col] pos;
vector<Triple <T> > _martix2 ;
size_t n = _martix .size ();
_martix2 .resize(n);
size_t num[] = {}; //統計原矩陣每列的元素個數
size_t start[] = {};//統計每一列第一個元素在_martix2中的存放下标位置
for(size_t i = ; i < n; i++)
num[_martix[i]._col]++;
//為什麼i從1開始？
//start[i] = 1;
for(size_t i = ; i < ; i++)
start[i] = start[i - ] + num[i - ];
for(size_t i = ; i < n; i++)
{
_martix2 [start[_martix[i]._col]] = _martix[i];
swap(_martix2[start[_martix[i]._col]]._col,_martix2[start[_martix[i]._col]]._row);
start[_martix[i]._col]++;
}
for(size_t i = ; i< n; i++)
{
_martix [i] = _martix2 [i];
}
swap(_m,_n);
}
// 列印稀疏矩陣--就是從壓縮存儲還原的過程；
void Display()
{
int index = ;
for(size_t i = ; i < _m; i++)
{
for(size_t j = ; j < _n; j++)
{
if( index < _martix.size()&&
_martix[index]._row == i&&
_martix[index]._col == j)//判斷該位置是否放置有效資料；
{
cout<<_martix[index++]._data<< " ";
}
else //否則該位置放置無效資料
cout<<_invalid<< " ";
}
cout<<endl;
}
cout<<endl;
}
private:
size_t _m; //矩陣的行數
size_t _n; //矩陣的列數
T _invalid; //無效資料
vector<Triple <T> > _martix; //儲存資料所有結構體的vector
};
void testSparseMatrix()
{
int a[][] = //測試用例
{{, , , , },
{, , , , },
{, , , , },
{, , , , },
{, , , , },
{, , , , }};
SparseMatrix<int > s((int *)a, , , ); //注意類參數是一維數組指針，強制轉換；
//s.FastTransposition ();
s.FastTransposition2 ();
s.Display ();
}
int main()
{
testSparseMatrix();
system("pause");
return ;
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)