本文關鍵詞：稀疏矩陣，由筆耕文化傳播整理發(fā)布。

　　矩陣是線性代數(shù)中的一個知識，剛開始學習的時候可能感覺不到它有什么用處，最初的感覺就是對二維數(shù)據(jù)的操作。其實現(xiàn)實生活中矩陣的用處太大了，設計領域相當?shù)膹V泛。在此只討論稀疏矩陣的轉(zhuǎn)置問題；

　　可能看到矩陣就會想到二維數(shù)組，比如這樣一個矩陣：

　　你可能會想到用二維數(shù)組來存放此矩陣中的元素，就像這樣：int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}};

這樣好像也沒有什么不好。我們再來看看這個矩陣，五行五列，可以包含二十五個元素，但是此矩陣只有七個元素。但是我們在存放數(shù)據(jù)的時候分配了二十五塊int單元。這樣是不是有點太浪費了。如果我們只存儲這七個元素我想會節(jié)省一部分內(nèi)存空間。但是如果我們只存儲矩陣中的元素還是不行的，因為只有元素我們就無法還原矩陣，我們還需要此元素的行列值。這樣就好辦了。我們聲明一個結(jié)構(gòu)體來表示一個元素。就像這樣：

1 typedef struct juzhen 2 { col; value; };

　　這樣存儲一個元素就會用到三個存儲單元，七個就是二十一個存儲單元，可能與二十五個沒多大差別，但是如果矩陣的行列是一個很大的值，而且又是稀疏矩陣，這樣做就可以節(jié)省很大的空間。這種存儲結(jié)構(gòu)只限于稀疏矩陣。

　　解決了存儲結(jié)構(gòu)，就開始矩陣的轉(zhuǎn)置吧�。�！

　　首先我們需要一個矩陣，就按照上圖給的矩陣好了，按照此矩陣做一個二維數(shù)組：

1 int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}};

　　就像這樣；我們需要定義一個數(shù)組來表示稀疏矩陣，并賦值；

1 #define MAX_TERM 15 juzhen a[MAX_TERM]; chushi({ i,j; 9 int count_a = 1; 10 for(i = 0;i < N;i++) 11 { 12 for(j = 0;j < N;j++) 13 { 14 if(text[i][j] != 0) 15 { 16 a[count_a].row = i; 17 a[count_a].col = j; 18 a[count_a].value = text[i][j]; 19 count_a++; 20 } 21 } 22 } a[a[ count_a; 28 }

　　在初始化矩陣數(shù)組的時候為了方便轉(zhuǎn)置矩陣時的操作，我們把數(shù)組的第一個元素設置為矩陣的列數(shù)，行數(shù)和元素總數(shù)；

　　矩陣有了，，存放矩陣元素的數(shù)組也有了。接下來就是轉(zhuǎn)置矩陣的函數(shù)了。

　　我們在轉(zhuǎn)置矩陣的時候會需要一個數(shù)組來保存轉(zhuǎn)置后的矩陣，定義為：

struct juzhen b[MAX_TERM];//轉(zhuǎn)置后的矩陣

　　主要思想，兩層循環(huán)，第一層循環(huán)控制矩陣的行，第二層循環(huán)控制數(shù)組a的行。由于轉(zhuǎn)置矩陣即把矩陣中元素的列行對換一下，并且按照行排序；所以我們在第二層循環(huán)中做一個判斷，if(a[j].col == i) 【i控制第一層循環(huán)，j控制第二層循環(huán)】 如果為真值則執(zhí)行：

b[count_b].row = a[j].col; b[count_b].col = a[j].row; b[count_b].value = a[j].value;

整個函數(shù)如下：

void zhuanzhi_1(struct juzhen a[MAX_TERM],struct juzhen b[MAX_TERM]) //轉(zhuǎn)置矩陣方法一 { int i,j; int count_b = 1; //b的當前元素下標 b[0].row = a[0].col;　　 b[0].col = a[0].row; b[0].value = a[0].value; for(i = 0;i < a[0].col;i++) { for(j = 1;j <= a[0].value;j++) { if(a[j].col == i)　　　　//有種排序效果 { b[count_b].row = a[j].col; b[count_b].col = a[j].row; b[count_b].value = a[j].value; count_b++; } } } }

　　用此方法可以有效的轉(zhuǎn)置矩陣，我們來看一下此函數(shù)的時間復雜度：O(cols * elements)——矩陣的列*矩陣的元素總和；

　　如果元素很多就會浪費很多的時間。有沒有辦法讓兩層循環(huán)變成一層循環(huán)呢？付出空間上的代價，換取時間效率；

　　我們只用一層循環(huán)來遍歷數(shù)組a中所有元素，并把該元素放到指定的位置。這樣我們就需要一個數(shù)組star來存放第i個元素所在位置。在定義這個數(shù)組之前，我們還需要一個數(shù)組term來實現(xiàn)統(tǒng)計矩陣第i行元素的數(shù)量。這樣我們才能更方便的知道第i個元素應該存放的位置。

n = a[0].value; int i,j,k; int b_star; for(i = 0;i < N;i++) term[i] = 0; for(j = 0;j <= n;j++) term[a[j].col]++; star[0] = 1; for(k = 1;k < N;k++) star[k] = star[k - 1] + term[k - 1];

第一個循環(huán)初始化term，每個元素都為零。第二個循環(huán)是為了統(tǒng)計第i行元素的數(shù)量。第三個循環(huán)是設置第i個元素所在的位置。因為數(shù)組a的第一個元素是存放行列和元素的總數(shù)，因此第三個循環(huán)要從k = 1開始。此時兩個數(shù)組的元素為：

下一步就是遍歷a中的所有元素，然后根據(jù)a[i].col的值來把a[i].value放到指定的位置。

b[0].col = a[0].col; b[0].row = a[0].row; b[0].value = a[0].value; for(i = 1;i <= n;i++) { b_star = star[a[i].col]++; b[b_star].col = a[i].row; b[b_star].row = a[i].col; b[b_star].value = a[i].value; }

需要注意的是b的第一個元素與a中的第一個元素是同樣的。b_star = star[a[i].col]++;因為當term[1] = 2;而star[1] = 3;就是a[i].col = 1時有兩個元素，第一個元素的位置是star[a[i].col];而第二個元素的位置就是star[a[i].col] + 1所以在此用star[a[i].col]++。為下一個元素設置相應的位置；

完整函數(shù)：

void zhuanhuan_2(struct juzhen a[MAX_TERM],struct juzhen b[MAX_TERM]) { n = a[0].value; int i,j,k; int b_star; for(i = 0;i < N;i++) term[i] = 0; for(j = 1;j <= n;j++) term[a[j].col]++; star[0] = 1; for(k = 1;k < N;k++) star[k] = star[k - 1] + term[k - 1]; b[0].col = a[0].col; b[0].row = a[0].row; b[0].value = a[0].value; for(i = 1;i <= n;i++) { b_star = star[a[i].col]++; b[b_star].col = a[i].row; b[b_star].row = a[i].col; b[b_star].value = a[i].value; } }

此函數(shù)每個循環(huán)體的執(zhí)行次數(shù)分別為cols cols elements elements 時間復雜度為O(cols + elements)和O(cols * elements)相差好多，尤其是clos 和 elements很大的時候；

完整的測試程序：

完整代碼

1 #include

  本文關鍵詞：稀疏矩陣，由筆耕文化傳播整理發(fā)布。