在普遍的印象中，矩陣是由方括號圍住，同時各個坐標的數字整齊的排列著。如下圖所示：
看到圖示後，第一反應當然是用一個二維數組來表示，即簡單又易懂。但我們又會碰到下圖所示矩陣：
看看這個矩陣，0好多啊（我們稱之為稀疏矩陣），若用二維數組來表示，會重復存儲了很多個0了，這樣浪費了空間。
故要采取一種特殊的方式來存儲這樣的矩陣，這裡就提出了數組的方式來存儲這樣的矩陣。
typedef struct
{
int row; //行坐標
int col; //列坐標
int value; //該點的值
} item;
這裡item表示矩陣中點，那麼一個稀疏矩陣（非0值的個數為num）的描述就如下：
用item[num+1]來表示一個矩陣，為啥要num+1，先作一點說明：
item數組的首值為{行數，列數，非0值個數}結構，除首值外，其余值表示的矩陣中非0值的行列坐標以及本身的值。先上個小例子，來解釋下：
已知上述矩陣非0值的個數為：16-7=9；用數組item test[9+1]來表示
通過這種方式來存儲，大大節約了空間，但同時帶來了一定的麻煩（主要是矩陣運算時，不太好理解）。
1、矩陣轉置運算
矩陣轉置：即把矩陣行值變列值，列值變成行值，對於二維數組而言，就是將二維數組的下標進行互換即可，原始：a[i][j]=value；轉換後：a[j][i]=value；
但轉置對於用數組表示的矩陣來說，理解起來也簡單，即將行列互換。
void transpose1(item* a,item* b)
{
int col = a[0].row;
int row = a[0].col;
int value = a[0].value;
b[0].row = row; //先將b[0]的值填充好
b[0].col = col;
b[0].value = value;
int num=1; //num表示b矩陣的數組下標，因為首值已經設好，故從1開始
for(int i=0;i<row;i++) //i為b的行標，裡層循環遍歷a矩陣，因為j從小到大，故獲得b矩陣的列標也是在同行標的情況下，從小到大排列
{
for(int j=1;j<=value;j++) //數組下標由小到大遍歷
{
if(a[j].col == i) //當a矩陣的列標與b的行標相等，則做如下處理
{
b[num].col = a[j].row; //從這可以看出，b的列標在同行標下，是從小到大排列的。
b[num].row = i;
b[num].value = a[j].value;
num++;
}
}
}
}
從代碼中，我們可以輕松看出，時間復雜度是比較大的，兩層循環的緣故；O(row*(value))；若value為row*col的話，這個開銷就非常大了。
書中提出了快速的轉置的方式，簡要描述如下：
a、首先找出轉置後的矩陣，每行非0的個數。（通過遍歷原始數組，對col的值進行次數統計）
b、獲取每行非0值的起始數組下標；（已經0行的起始數組下標為1，而1行的起始數組下標就是0行的起始下標+0行中非0值的個數，同理下推）
c、遍歷原始數組（從下標1開始），首先獲得結果數組的下標，由原始數組的列標（結果數組行標）根據b步驟來判斷循環的當前下標應該在結果數組的什麼位置。
說的好繞口，看程序。
void transpose(item* a,item* b)//a為原始矩陣，b為轉置後的矩陣。
{
int row = a[0].col;
int col = a[0].row;
int value = a[0].value;
b[0].row = row;
b[0].col = col;
b[0].value = value;
//先統計下各行非0的個數
//先初始個存儲各行非0的數組
int* p = new int[row];
for(int i=0;i<=row;i++)
{
p[i]=0;
}
for(int i=1;i<=value;i++)
{
p[a[i].col]++;
}
//推算每行的起始點
int* start = new int[row];
start[0] = 1;
for(int i=1;i<row;i++)
{
start[i] = start[i-1]+p[i-1];
}
for(int i=1;i<=value;i++)
{
int j = start[a[i].col]++;//用於獲取數組下標，注意下標右移
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
delete[] start;
delete[] p;
}
到此，我們也就完成了轉置運算。
2、矩陣的乘法
在上一篇中，講述過了矩陣乘法，這裡就不做贅述了
對於稀疏矩陣來說，乘法相對來說，處理起來比較煩鎖，並不像二維數組處理起來那麼無腦。因為並不能從兩個矩陣的非零值個數中，直接獲得乘積後的結果矩陣的非零值個數。例如：
可以看出來，處理還是比較復雜的。
void mult(item* a,item* b,item* result)
{
//根據矩陣相乘的具體算法步驟，即結果矩陣的（i,j）為a矩陣的i行與b矩陣的j列對應相乘，
//那麼我們可以做一個轉換，可以看成a矩陣的i行與b矩陣的轉置後的j行對應相乘，
//對應的根據是：a矩陣的列數與b轉置後的矩陣的列數相對應
//首先對右邊的矩陣進行轉置操作
int a_row = a[0].row,a_col = a[0].col,a_value = a[0].value;
int b_row = b[0].row,b_col = b[0].col,b_value = b[0].value;
if(a_col != b_row)
{
std::cout << "error";
return;
}
//c矩陣為b的轉置矩陣
//先獲取結果矩陣最大長度
item* c = new item[b_value+1];
transpose(b,c); //下面所述的row表示結果數組的行標，col表示結果數組的列標
int row = a[1].row; //結果矩陣的行標row一定是從這裡開始的
int col = 0; //列標col暫置為0
//_begin用於標記row行初始位置。
int _begin=1; //如：循環時，前面row行已經處理完了，這時a數組的前面row行對於後續計算也就沒意義了，這裡_begin的作用就是用於記錄a數組的row+1行位置作用
int sum,num=1; //sum存儲的結果數組（row,col）處的value值，num用於存儲結果數組的下標
for(int i=1;i<=a_value;) //從a數組1開始遍歷，直至a數組尾
{
col = c[1].row; //由於c為b數組轉置矩陣，其行標就是結果數組的列標col，由矩陣的乘法性質知，每次col都從c[1].row開始的，故每次循環開始時，要重置下。
sum = 0;
for(int j=1;j<=b_value+1;) //此處value+1的作用是應對這種情況：a數組未遍歷完，而j值已經取遍c的下標，而j++的作用導致超出c數組范圍，可能會越界，而下面的第一個if作用也正是處理這種狀況
{
if(j>b_value) //j值已經超出了b_value，意味著數組已被完全遍歷，說明當前行row的值已經完全找出了。
{
result[num].row = row; //這時我們就可以把之前記錄的sum填入結果數組中，同時下標num要自加1
result[num].col = col;
result[num].value = sum;
num++;
break; //當前行的所有非0值均已找出，可以跳出該循環了
}
if(i>a_value||a[i].row != row) //1、此時a矩陣該行已迭代完，沒有可算的值2、當前row行已經迭代完，若繼續迭代，行值就變了，
{
result[num].row = row; //所以此時也可以將sum值存入結果數組中，同時下標num要自加1.
result[num].col = col;
result[num].value = sum;
num++;
i = _begin; //為了計算當前行的下一個（下一個col值）非零值，i要為該行的起始位置開始遍歷
for(;j<=b_value&&c[j].row==col;j++);//主要作用為了將當前行值為col的全部遍歷過，但不作任何其他處理，然後進入下一col值
if(j>b_value)break; //可能出現j的值比b_value大，就要跳出循環了。
col = c[j].row; //將列值置為下一個col值
}
else if(c[j].row != col) //由於c數組的row表示結果數值的列值，該條件說明當前列值與c數組的row值不等，意味著結果數組的列值應該下移了。
{
result[num].row = row; //處理方式與上述有些類似
result[num].col = col;
result[num].value = sum;
num++;
i = _begin;
col = c[j].row;
}
else if(a[i].col < c[j].col) //下面3個條件很好理解。
{
i++;
}
else if(a[i].col == c[j].col)
{
sum += a[i++].value * c[j++].value;
}
else if(a[i].col > c[j].col)
{
j++;
}
}
for(;i<=a_value&&a[i].row == row;i++); //通過遞歸，將當前行迭代，直到進行下一個row行值。
if(i>a_value) //如果i的值超出最大值，說明已經算完所有行了。
break; //終止循環
row = a[i].row;
_begin = i; //同時記下此時row對應的開始下標。
}
result[0].row = a_row;
result[0].col = b_col;
result[0].value = num-1;
delete[] c;
}
有空會把圖給畫出來，幫助理解。
