C++超詳細講解稀疏矩陣
稀疏矩陣
矩陣與稀疏矩陣的定義
Q:什么是矩陣
A:數(shù)學(xué)上,一個矩陣由 m 行 n 列的元素組成,是一個 m 行,n 列的表,m 和 n 是矩陣的維度。一般地,寫作 mxn(讀作“m乘n”)來指明一個 m 行 n 列矩陣。矩陣的元素個數(shù)總計為 mn 個。如果 m 等于 n ,矩陣為方陣。
一般情況下,矩陣的標(biāo)準存儲方式是一個二維數(shù)組 a[MAX_ROWS][MAX_COLS] 。利用這種存儲方式,可以通過 a[i][j] ,通過行下標(biāo),列下標(biāo)快速找到任意元素的存儲位置。
Q:什么是稀疏矩陣
A:一個矩陣的絕大部分都為零元素,我們把這種矩陣稱為稀疏矩陣。
如圖:矩陣中只有 2/15 是非零元素,這就是一個標(biāo)準的稀疏矩陣
Q:二維數(shù)組儲存矩陣的缺點
A:如果一個矩陣中包含很多零元素(是稀疏矩陣),就會浪費大量的存儲空間。因此,稀疏矩陣的存儲表示只需存儲非零元素。
Q:稀疏矩陣的存儲方式
A:通過對矩陣的分析,我們發(fā)現(xiàn)使用三元組 <row,col,value> 能夠唯一的刻畫矩陣的任意一個元素。這意味者可以使用三元數(shù)組來存儲表示稀疏矩陣。
代碼演示
#define MAX_TERMS 101 //定義最大長度 typedef struct{ int col; int row; int xalue; }term; term a[MAX_TERMS];
我們可以用 a[0].row 表示行的數(shù)目,用 a[0].col 表示列的數(shù)目,用 a[0].value 表示非零元素的總數(shù)。其他位置 row 域存放行下標(biāo), col 域存放列下標(biāo),value 域存放元素值。三元組按照行的順序排序,并且在同一行內(nèi)按照列的順序排序。
稀疏矩陣存儲為三元組
行 | 列 | 值 | |
---|---|---|---|
a[0] | 5 | 6 | 4 |
a[1] | 0 | 0 | 15 |
a[2] | 1 | 1 | 11 |
a[3] | 2 | 3 | 6 |
a[4] | 4 | 0 | 9 |
稀疏矩陣的轉(zhuǎn)置
詳細思路
為了轉(zhuǎn)置一個矩陣,必須交換它的行和列。也就是說,原矩陣的任意元素 a[i][j] 應(yīng)該成為其轉(zhuǎn)置矩陣的元素 b[j][i]
思路一
依次循環(huán)每一列,找到每一列的所有元素并把他們儲存在轉(zhuǎn)置矩陣的對應(yīng)的行上。
//偽代碼
for 對于 j 列的所有元素
把元素<i,j,value>放置在元素<j,i,value>中
代碼演示
void transpose(term a[],term b[]) //b是a的轉(zhuǎn)置 { int n,i,j,currentb; n=a[0].value; //元素總數(shù) b[0].row=a[0].col; //b的行數(shù)=a的列數(shù) b[0].co 1=a[0].row; //b的列數(shù)=a的行數(shù) b[0].value =n; if(n> 0) {// 非零矩陣 currentb=1; for(i=0;i<a[0].col;i++) //按a的列轉(zhuǎn)置 for(j=1;j<=n;j++) //找出當(dāng)前列的所有元素 if(a[j].col==i) {//元素是當(dāng)前列的,加入b b[currentb]. row=a[j]. col; b[currentb]. col=a[j]. row; b[currentb]. value=a[j]. value; currentb++; } } }
思路二
首先確定原矩陣中每一列的元素個數(shù),這也就是其轉(zhuǎn)置矩陣中每一行的元素個數(shù)。于是就可以得到轉(zhuǎn)置矩陣每行的起始位置,從而,可以將原矩陣的元素依次移到其轉(zhuǎn)置矩陣中的恰當(dāng)位置。
代碼演示
void fast transpose(term a[], term b[]) { //將a的轉(zhuǎn)置矩陣存放于b中 int row terms[MAX_COL], starting pos[MAX_COL]; int i,j, num_cols=a[0].col, num_terms=a[0].value; b[0].row=num_cols;b[0].col=a[0].row; b[0].value=num_terms; if(num_terms>0){//非零矩陣 for(i=0;i<num_cols;i++) row_terms[i]=0; for(i=1;i<=num_terms;i++) row_terms[a[i]. co]]++; starting_pos[0]=1; for(i=1;i<num cols;i++) starting_pos[i]=starting_pos[i-1]+row_terms[i-l]; for(i=1;i<=num_terms;i++){ j=starting_pos[a[i].col]++; b[j].row=a[i].col;b[j].col=a[i].row; b[j].value=a[i].value; } } }
稀疏矩陣的乘法
Q:什么是矩陣乘法
A:設(shè)A為 mxp 的矩陣,B為 pxn 的矩陣,那么稱 mxn 的矩陣D為矩陣A與B的乘積,記作D=AB,其中矩陣D中的第 i 行第 j 列元素可以表示為:
注意:兩個稀疏矩陣的乘積可能不再是稀疏矩陣
詳細思路
我們可以按照行的順序計算D的元素,把元素存放到正確的位置,這樣就不用移動已計算出的元素的位置。一般情況下,必須遍歷整個B才能得到第 j 列的所有元素。但是,我們可以先計算 B 的轉(zhuǎn)置,使列元素順序相續(xù)排序,可以避免重復(fù)多次遍歷整個 B 。
對于找出的 A 的第 i 行和 B 的第 j 列的所有元素,做合并操作就能實現(xiàn)矩陣乘法。
代碼演示
void storesum(term a[],int *totald,int row,int column,int *sum) {//如果 *sum!=0,它的行和列存儲位置為 d 中的 *totald+1 if(*sum) if(*tptald<MAX_TERMS) { d[++*totald].row=row; d[*totald].col=column; d[*totald].value=*sum; *sum=0; } else{ fprintf(stderr,"Numbers of terms in product exceeds %d\n",MAX_TERMS); exit(1); } } void mmult(term a[], term b[], term d[]) //將兩個稀疏矩陣相乘 { int i,j,column,totalb=b[0].value,totald=0; int rows_a=a[0].row,cols_a=a[0].col; totala=a[0].value;int cols_b=b[0].col; int row_begin=1, row=a[1].row, sum=0; int new_b[MAX-TERMS][3]; if(cols_a!=b[0].row){ fprintf(stderr,"Incompatible matrices\n"); exit(1); } fast_transpose(b.new_b); //設(shè)置邊界條件 a[totala+1].row=rows_a; new_b[totalb+1].row=cols_b; new_b[totalb+1].col=0; for(i=1;i<=totala;){ column=new_b[1].row; for(j=1;j<=totalb+1;){ //將a的行乘以b的列 if(a[i].row!=row){ storesum(d,&totald,row,column,&sum); i=row_begin; for(;new_b[j].row==column;j++) ; column=new_b[j]. row; } else if(new_b[j].row!=column){ storesum(d,&totald,row,column,&sum); i=row_begin; column=new_b[j].row; } else switch(COMPARE(a[i].col,new_b[j].col)){ case-1://轉(zhuǎn)到a中的下一項 i++;break; case 0://添加項,轉(zhuǎn)到a和b的下一項 sum+=(a[i++].value*new_b[j++].value); break; case 1://來到b的下一項 j++; } }// for j<=totalb+1 結(jié)束循環(huán) for(;a[i].row==row;i++) ; row_begin=i;row=a[i].row; }//for i<=totala 結(jié)束循環(huán) d[0].row=rows_a; d[0].col=cols_b;d[0].value=totald; }
到此這篇關(guān)于C++超詳細講解稀疏矩陣的文章就介紹到這了,更多相關(guān)C++稀疏矩陣內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
詳解C++中的vector容器及用迭代器訪問vector的方法
使用迭代器iterator可以更方便地解引用和訪問成員,當(dāng)然也包括vector中的元素,本文就來詳解C++中的vector容器及用迭代器訪問vector的方法,需要的朋友可以參考下2016-05-05一道超經(jīng)典的C++結(jié)構(gòu)體的題目
以下小編就為大家介紹一道超經(jīng)典的關(guān)于C++結(jié)構(gòu)體的題目。需要的朋友可以過來參考下2013-09-09C++ 內(nèi)存分配處理函數(shù)set_new_handler的使用
這篇文章主要介紹了C++ 內(nèi)存分配處理函數(shù)set_new_handler的使用,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02