欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++超詳細講解稀疏矩陣

 更新時間:2022年05月25日 10:50:06   作者:錫蘭Ceylan_  
今天小編就為大家分享一篇關(guān)于C++稀疏矩陣的轉(zhuǎn)置思路并實現(xiàn)乘法,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧

稀疏矩陣

矩陣與稀疏矩陣的定義

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]564
a[1]0015
a[2]1111
a[3]236
a[4]409

稀疏矩陣的轉(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的方法

    詳解C++中的vector容器及用迭代器訪問vector的方法

    使用迭代器iterator可以更方便地解引用和訪問成員,當(dāng)然也包括vector中的元素,本文就來詳解C++中的vector容器及用迭代器訪問vector的方法,需要的朋友可以參考下
    2016-05-05
  • opencv實現(xiàn)矩形檢測

    opencv實現(xiàn)矩形檢測

    這篇文章主要為大家詳細介紹了opencv實現(xiàn)矩形檢測,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • 一道超經(jīng)典的C++結(jié)構(gòu)體的題目

    一道超經(jīng)典的C++結(jié)構(gòu)體的題目

    以下小編就為大家介紹一道超經(jīng)典的關(guān)于C++結(jié)構(gòu)體的題目。需要的朋友可以過來參考下
    2013-09-09
  • C++獲取當(dāng)前進程IAT的方法

    C++獲取當(dāng)前進程IAT的方法

    這篇文章主要介紹了C++獲取當(dāng)前進程IAT的方法,實例講述了IAT(導(dǎo)入地址表)的獲取方法,在Windows應(yīng)用程序開發(fā)中有著非常實用的應(yīng)用價值,需要的朋友可以參考下
    2014-10-10
  • C++ 內(nèi)存分配處理函數(shù)set_new_handler的使用

    C++ 內(nèi)存分配處理函數(shù)set_new_handler的使用

    這篇文章主要介紹了C++ 內(nèi)存分配處理函數(shù)set_new_handler的使用,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-02-02
  • C++實現(xiàn)歌手比賽評分系統(tǒng)

    C++實現(xiàn)歌手比賽評分系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)歌手比賽評分系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • C語言實現(xiàn)可增容動態(tài)通訊錄詳細過程

    C語言實現(xiàn)可增容動態(tài)通訊錄詳細過程

    這篇文章主要為大家介紹了C語言實現(xiàn)簡易通訊錄的完整流程,此通訊錄還可以增容,并且每個環(huán)節(jié)都有完整代碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2022-05-05
  • C++中繼承的概念和定義

    C++中繼承的概念和定義

    這篇文章主要介紹了詳解C++ 中的概念和定義,幫助大家更好的理解和學(xué)習(xí)使用c++,感興趣的朋友可以了解下,希望能給你帶來幫助
    2021-08-08
  • Qt線程QThread開啟和安全退出的實現(xiàn)

    Qt線程QThread開啟和安全退出的實現(xiàn)

    本文主要介紹了Qt線程QThread開啟和安全退出的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • C++中std::allocator的使用案例詳解

    C++中std::allocator的使用案例詳解

    這篇文章主要介紹了C++中std::allocator的使用案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-09-09

最新評論