大白話講數據結構：矩陣的轉置和矩陣的乘法問題（2） （應該都能看懂的！）

（文末附上成功運行的完整代碼，包括輸入和遍歷輸出）

附：運行成功的截圖

上一次更新了一篇關於矩陣的轉置的文章，這次文章是我更加深入理解之後寫的。感覺上次關於這個問題並沒有講清楚，下面給大家仔細講一下。

矩陣就是一個m*n的數陣。一共有m行，n列。轉置矩陣就是將原矩陣中的第m行n列的一個數變成第n行m列的一個數。

在計算機中想要實現這一操作，一般思維過程需要考慮兩步（嚴蔚敏老師書上是3步）：

1.將兩個矩陣的行列互換，兩個矩陣中的元素個數應該相等；

2.將三元組中的行列值互換，並將三元組中的次序重排；

如果是一般的矩陣，可以用如下代碼：

M.tu=T.tu;/*tu表示非零元的個數，nu表示行，mu表示列*/M.mu=T.nu;M.nu=T.mu;for(int i=1;i<=T.mu;i++){ for(int j=1;T.nu;j++) { M[i][j]=T[j][i]; }}

是不是很容易就能實現了呢！

我們來分析一下上述矩陣的時間複雜度：兩個循環，很容易判斷出，時間複雜度是mu*nu。

但是如果是一個稀疏矩陣的話，用上面的方法就會很多餘，浪費大量時間。（稀疏矩陣就是在整個矩陣中的非零元素的個數占整個矩陣中元素個數的比值要小於0.05）。

稀疏矩陣中由於存在大量的0元素，所以為了節約時間和空間，人們想出了一些新的演算法。

比如下面這個演算法：

void TMaxtrix(TMatrix T, TMatrix &S){ int p, q; int k = 1; S.col = T.row; S.row = T.col; S.tn = T.tn; for (p = 1; p <= T.col; p++) { for (q = 1; q <= T.tn; q++) { if(T.data[q].j==p) {S.data[k].i = T.data[q].j; S.data[k].j = T.data[q].i; S.data[k].e = T.data[q].e; k++;} } }}

（大白話來解釋這個演算法）它的意思就是，有一個變數p，當它小於原矩陣T的列數的時候，它就要執行{}裡面的內容：有一個變數q，當它小於T的非零元素的個數時，執行{}中的內容：如果T中的第一個非零元素的列標等於p，執行{}中的內容：（和上面的演算法一樣，行列標互換，元素相等）。最後q，p，k全部加1。

分析這個演算法的時間複雜度，很容易就能夠知道為：col*tn。 也就是矩陣的列數乘以非零元素的個數。 如果，非零元素的個數遠遠小於矩陣的行數，那麼可想而知，這個演算法時很節約時間和空間的。

但是人們並不滿足於此，於是想出了更簡單的一個演算法，用來處理稀疏矩陣。 大致思路時這樣的：

矩陣無非就是一個數表嘛，如果我知道了一個矩陣中每一列的第一個非零元素和這一列所有的元素個數，那麼，我不就有可以把演算法進一步簡化了。 這樣來想的話，我們先定義一個數組num[],用他來表示每一列中的非零元素的個數，同時定義一個數組copt[]，用它來存放，每一列中，首非零元素的位置（在轉置矩陣中的位置！）。同時規定：copt[1]=1; 這樣的話，

copt[x]=copt[x-1]+num[x-1] (1<x<=tn); 這樣不就被我們表示出來了！

下面我們看看具體代碼：

void FrastTransMatrix(TMatrix T, TMatrix Q){ int num[NUMMAX]; int copt[MAXCOPT]; int q,k; Q.col = T.row; Q.row = T.col; Q.tn = T.tn; for ( q = 1; q <= T.col; q++) num[q] = 0;/*初始化num*/ for (int p = 1; p <= T.tn; p++) ++num[T.data[p].j];/*求每列的非零元個數*/ copt[1] = 1; for ( k = 2; k <= T.col; k++) { copt[k] = copt[k - 1] + num[k - 1];/*首非零元在Q中所對應的位置*/ } for (int m = 1; m <= T.tn; m++) { k = T.data[m].j; int s = copt[k]; Q.data[s].e = T.data[m].e; Q.data[s].i = T.data[m].j; Q.data[s].j = T.data[m].i; ++copt[k]; } }

根據上面的注釋應該時能懂的。 如果符號.和->不認識的話，可以看看之前的文章。

下面談談矩陣的乘法：

根據矩陣乘法定義，應該是行乘列，即行向量的對應的乘列向量累計計算結果。

這樣的話，我們很容易就能寫出矩陣乘法的基本演算法：

假設Q=MN，其中，M是m1n1,N是m2*n2. n1=m2.

for(i=1;i<=m1;i++) for(j=1;j<=n2;j++) { Q[i][j]=0; for(k=1;k<=n1;==k) Q[i][j]+=M[i][k]n[k][j]; }

附代碼：

#include "stdafx.h"#define MAXTRIX 10240#define NUMMAX 200#define MAXCOPT 200typedef struct Triple{ int i, j, e;}Triple;typedef struct TMatrix{ int row, col,tn; Triple data[MAXTRIX+1];}*Tmatrix;void Init_Maxtrix(TMatrix &T){ printf("矩陣的總數為:"); scanf_s("%d", &T.tn); printf("矩陣的行數為:"); scanf_s("%d", &T.row); printf("矩陣的列數為:"); scanf_s("%d", &T.col); for (int i = 1; i <= T.tn; i++) { printf("這是矩陣的第%d個非零元素",i); printf("它的行標為:"); scanf("%d",&T.data[i].i); printf("它的列標為："); scanf("%d",&T.data[i].j); printf("元素的值為："); scanf("%d",&T.data[i].e); } }void TMaxtrix(TMatrix T, TMatrix &S){ int p, q; int k = 1; S.col = T.row; S.row = T.col; S.tn = T.tn; for (p = 1; p <= T.col; p++) { for (q = 1; q <= T.tn; q++) { S.data[k].i = T.data[q].j; S.data[k].j = T.data[q].i; S.data[k].e = T.data[q].e; k++; } }}void FrastTransMatrix(TMatrix T, TMatrix Q){ int num[NUMMAX]; int copt[MAXCOPT]; int q,k; Q.col = T.row; Q.row = T.col; Q.tn = T.tn; for ( q = 1; q <= T.col; q++) num[q] = 0; for (int p = 1; p <= T.tn; p++) ++num[T.data[p].j]; copt[1] = 1; for ( k = 2; k <= T.col; k++) { copt[k] = copt[k - 1] + num[k - 1]; } for (int m = 1; m <= T.tn; m++) { k = T.data[m].j; int s = copt[k]; Q.data[s].e = T.data[m].e; Q.data[s].i = T.data[m].j; Q.data[s].j = T.data[m].i; ++copt[k]; } }void Travel_Maxtrix(TMatrix T){ for (int i = 1; i <= T.tn; i++) { printf("%d,%d,%d
",T.data[i].i,T.data[i].j,T.data[i].e); }}int main(){ TMatrix T; TMatrix M; Init_Maxtrix(T); TMaxtrix(T,M); Travel_Maxtrix(M); return 0;}

碼字不易，朋友們記得點個贊哈。

更多優質內容，請關注微信公眾號：生物信息與python