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

C++超詳細(xì)講解稀疏矩陣

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

稀疏矩陣

矩陣與稀疏矩陣的定義

Q:什么是矩陣

A:數(shù)學(xué)上,一個(gè)矩陣由 m 行 n 列的元素組成,是一個(gè) m 行,n 列的表,m 和 n 是矩陣的維度。一般地,寫(xiě)作 mxn(讀作“m乘n”)來(lái)指明一個(gè) m 行 n 列矩陣。矩陣的元素個(gè)數(shù)總計(jì)為 mn 個(gè)。如果 m 等于 n ,矩陣為方陣。

一般情況下,矩陣的標(biāo)準(zhǔn)存儲(chǔ)方式是一個(gè)二維數(shù)組 a[MAX_ROWS][MAX_COLS] 。利用這種存儲(chǔ)方式,可以通過(guò) a[i][j] ,通過(guò)行下標(biāo),列下標(biāo)快速找到任意元素的存儲(chǔ)位置。

Q:什么是稀疏矩陣

A:一個(gè)矩陣的絕大部分都為零元素,我們把這種矩陣稱(chēng)為稀疏矩陣。

如圖:矩陣中只有 2/15 是非零元素,這就是一個(gè)標(biāo)準(zhǔn)的稀疏矩陣

Q:二維數(shù)組儲(chǔ)存矩陣的缺點(diǎn)

A:如果一個(gè)矩陣中包含很多零元素(是稀疏矩陣),就會(huì)浪費(fèi)大量的存儲(chǔ)空間。因此,稀疏矩陣的存儲(chǔ)表示只需存儲(chǔ)非零元素。

Q:稀疏矩陣的存儲(chǔ)方式

A:通過(guò)對(duì)矩陣的分析,我們發(fā)現(xiàn)使用三元組 <row,col,value> 能夠唯一的刻畫(huà)矩陣的任意一個(gè)元素。這意味者可以使用三元數(shù)組來(lái)存儲(chǔ)表示稀疏矩陣。

代碼演示

#define MAX_TERMS 101	//定義最大長(zhǎng)度 
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)按照列的順序排序。

稀疏矩陣存儲(chǔ)為三元組

 
 
a[0]564
a[1]0015
a[2]1111
a[3]236
a[4]409

稀疏矩陣的轉(zhuǎn)置

詳細(xì)思路

為了轉(zhuǎn)置一個(gè)矩陣,必須交換它的行和列。也就是說(shuō),原矩陣的任意元素 a[i][j] 應(yīng)該成為其轉(zhuǎn)置矩陣的元素 b[j][i]

思路一

依次循環(huán)每一列,找到每一列的所有元素并把他們儲(chǔ)存在轉(zhuǎn)置矩陣的對(duì)應(yīng)的行上。

//偽代碼
for 對(duì)于 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++;
				}
	}
}

思路二

首先確定原矩陣中每一列的元素個(gè)數(shù),這也就是其轉(zhuǎn)置矩陣中每一行的元素個(gè)數(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 的矩陣,那么稱(chēng) mxn 的矩陣D為矩陣A與B的乘積,記作D=AB,其中矩陣D中的第 i 行第 j 列元素可以表示為:

注意:兩個(gè)稀疏矩陣的乘積可能不再是稀疏矩陣

詳細(xì)思路

我們可以按照行的順序計(jì)算D的元素,把元素存放到正確的位置,這樣就不用移動(dòng)已計(jì)算出的元素的位置。一般情況下,必須遍歷整個(gè)B才能得到第 j 列的所有元素。但是,我們可以先計(jì)算 B 的轉(zhuǎn)置,使列元素順序相續(xù)排序,可以避免重復(fù)多次遍歷整個(gè) B 。

對(duì)于找出的 A 的第 i 行和 B 的第 j 列的所有元素,做合并操作就能實(shí)現(xiàn)矩陣乘法。

代碼演示

void storesum(term a[],int *totald,int row,int column,int *sum)
{//如果 *sum!=0,它的行和列存儲(chǔ)位置為 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[])
//將兩個(gè)稀疏矩陣相乘 
{
	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中的下一項(xiàng)
					i++;break;
				case 0://添加項(xiàng),轉(zhuǎn)到a和b的下一項(xiàng) 
					sum+=(a[i++].value*new_b[j++].value); break;
				case 1://來(lái)到b的下一項(xiàng)
					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++超詳細(xì)講解稀疏矩陣的文章就介紹到這了,更多相關(guān)C++稀疏矩陣內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 詳解C++中的vector容器及用迭代器訪問(wèn)vector的方法

    詳解C++中的vector容器及用迭代器訪問(wèn)vector的方法

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

    opencv實(shí)現(xiàn)矩形檢測(cè)

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

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

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

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

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

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

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

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

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

    C語(yǔ)言實(shí)現(xiàn)可增容動(dòng)態(tài)通訊錄詳細(xì)過(guò)程

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

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

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

    Qt線程QThread開(kāi)啟和安全退出的實(shí)現(xiàn)

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

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

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

最新評(píng)論