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

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

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

　　你可能會(huì)想到用二維數(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}};

這樣好像也沒有什么不好。我們?cè)賮砜纯催@個(gè)矩陣，五行五列，可以包含二十五個(gè)元素，但是此矩陣只有七個(gè)元素。但是我們?cè)诖娣艛?shù)據(jù)的時(shí)候分配了二十五塊int單元。這樣是不是有點(diǎn)太浪費(fèi)了。如果我們只存儲(chǔ)這七個(gè)元素我想會(huì)節(jié)省一部分內(nèi)存空間。但是如果我們只存儲(chǔ)矩陣中的元素還是不行的，因?yàn)橹挥性匚覀兙蜔o法還原矩陣，我們還需要此元素的行列值。這樣就好辦了。我們聲明一個(gè)結(jié)構(gòu)體來表示一個(gè)元素。就像這樣：

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

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

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

　　首先我們需要一個(gè)矩陣，就按照上圖給的矩陣好了，按照此矩陣做一個(gè)二維數(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}};

　　就像這樣；我們需要定義一個(gè)數(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ù)組的時(shí)候?yàn)榱朔奖戕D(zhuǎn)置矩陣時(shí)的操作，我們把數(shù)組的第一個(gè)元素設(shè)置為矩陣的列數(shù)，行數(shù)和元素總數(shù)；

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

　　我們?cè)谵D(zhuǎn)置矩陣的時(shí)候會(huì)需要一個(gè)數(shù)組來保存轉(zhuǎn)置后的矩陣，定義為：

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

　　主要思想，兩層循環(huán)，第一層循環(huán)控制矩陣的行，第二層循環(huán)控制數(shù)組a的行。由于轉(zhuǎn)置矩陣即把矩陣中元素的列行對(duì)換一下，并且按照行排序；所以我們?cè)诘诙䦟友h(huán)中做一個(gè)判斷，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;

整個(gè)函數(shù)如下：

void zhuanzhi_1(struct juzhen a[MAX_TERM],struct juzhen b[MAX_TERM]) //轉(zhuǎn)置矩陣方法一 { int i,j; int count_b = 1; //b的當(dāng)前元素下標(biāo) 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ù)的時(shí)間復(fù)雜度：O(cols * elements)——矩陣的列*矩陣的元素總和；

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

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

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];

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

下一步就是遍歷a中的所有元素，然后根據(jù)a[i].col的值來把a(bǔ)[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的第一個(gè)元素與a中的第一個(gè)元素是同樣的。b_star = star[a[i].col]++;因?yàn)楫?dāng)term[1] = 2;而star[1] = 3;就是a[i].col = 1時(shí)有兩個(gè)元素，第一個(gè)元素的位置是star[a[i].col];而第二個(gè)元素的位置就是star[a[i].col] + 1所以在此用star[a[i].col]++。為下一個(gè)元素設(shè)置相應(yīng)的位置；

完整函數(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ù)每個(gè)循環(huán)體的執(zhí)行次數(shù)分別為cols cols elements elements 時(shí)間復(fù)雜度為O(cols + elements)和O(cols * elements)相差好多，尤其是clos 和 elements很大的時(shí)候；

完整的測(cè)試程序：

完整代碼

1 #include

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