三元組表的快速轉(zhuǎn)置算法

1.三元組表的使用場景

當(dāng)我們在存儲稀疏矩陣的時候（稀疏矩陣：矩陣中只包含有極少數(shù)的非0元素），由于稀疏矩陣只有少量關(guān)鍵元素（就是非0元素），我們將整個稀疏矩陣全部存儲是十分浪費存儲空間的，如何跳過這些非0元素，只存儲關(guān)鍵元素以節(jié)約存儲空間呢？這個時候，三元組表就出現(xiàn)了。三元組表保存關(guān)鍵數(shù)據(jù)在稀疏矩陣中的位置，以及元素的信息。

2.三元組表的存儲結(jié)構(gòu)

對于一個矩陣，行號、列號、元素值可以唯一的確定矩陣中一個元素，三元組的三元即存儲了這三個值，row代表行號，col代表列號，e代表元素值。對于三元組表來說，還必須給出矩陣的總行數(shù)，總列數(shù)以及非零元素的個數(shù)，這樣才能唯一地確定一個稀疏矩陣。

#define MaxSize 1000
typedef strut{ //1個元素的三元組
	int row,col;
	int e;
}Triple;

typedef struct{
	Triple data[MaxSize]; //三元組表數(shù)組
	int rows,cols,nums; //行數(shù)，列數(shù)，非零元素的個數(shù)
}TSMatrix;

因此，給定一個稀疏矩陣：

那么它的稀疏矩陣可以表示為：

3.三元組表的常規(guī)轉(zhuǎn)置算法

對于一個三元組表表示的稀疏矩陣，如何求出它的轉(zhuǎn)置矩陣呢？對于常規(guī)的轉(zhuǎn)置算法而言，我們只需要把三元組表中各個col和row互換，再將互換后的三元組表按照row（換完之后的）進(jìn)行從小到大排序即可。

常規(guī)算法：交換行、列號，再按行號排序

常規(guī)算法思路簡單，但是時間復(fù)雜度過高，因此不太建議使用常規(guī)算法轉(zhuǎn)置。

4.三元組表的快速轉(zhuǎn)置算法

思想：對被轉(zhuǎn)置矩陣的三元組表只掃描一次，使得所有的非零元素一次性存放到轉(zhuǎn)置后的三元組表中。
算法過程：

1. 使用數(shù)組num[ ]，統(tǒng)計各個列非零元素的個數(shù)，做法：遍歷三元組表的col，num[col ]++。
2. 使用數(shù)組pos[ ]，記錄各行第一個元素的起始位置，那么pos[1]則等于1，因為數(shù)組中的第一個元素的位置始終在第一位。其它元素的起始位置為pos[col]=pos[col-1]+num[col-1]，即當(dāng)前行的第一個元素的起始位置等于上一行的第一個元素的起始位置加上上一行非零元素的個數(shù)。
3. 有了完整的pos數(shù)組，就可以每次直接找到該列號轉(zhuǎn)置后在新的三元組表的行號的最終位置，省去了最終行號排序的步驟。

原始矩陣：

未轉(zhuǎn)置前的三元組表：

操作：

完整代碼實現(xiàn)：

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100

typedef struct{ //1個元素的三元組
	int row,col;
	int e;
}Triple;

typedef struct{
	Triple data[MaxSize]; //三元組表數(shù)組
	int rows,cols,nums; //行數(shù)，列數(shù)，非零元素的個數(shù)
}TSMatrix;

void Fast_TransposeTSMatrix (TSMatrix *T, TSMatrix *M)
{
	int col, t, p;
	int num[MaxSize], pos[MaxSize];
	pos[1] = 1; //第一個位置
	if (M->nums)
	{
		for (col = 1; col <= T->cols; col++) //各列元素個數(shù)初始化
			num[col] = 0;
		for (t = 1; t <= T->nums; t++) //記錄各列元素個數(shù)
			num[T->data[t].col] ++;
		
		for (col = 2; col <= T->cols; col++) //記錄起始位置
			pos[col] = pos[col-1] + num[col-1];
 
		for (p = 1; p <= T->nums; p++)
		{
			col = T->data[p].col; //行列交換
			M->data[pos[col]].row = T->data[p].col;
			M->data[pos[col]].col = T->data[p].row;
			M->data[pos[col]].e = T->data[p].e; //元素交換
			pos[col]++; //當(dāng)該位置存放一個三元組之后，則起始位置需要+1
		}
	}
	
}

int main(){
	TSMatrix T;
	TSMatrix M;
	T.cols=6; T.rows=4; T.nums=5;
	T.data[1].row=1; T.data[1].col=2; T.data[1].e=14;
	T.data[2].row=1; T.data[2].col=5; T.data[2].e=-5;
	T.data[3].row=2; T.data[3].col=2; T.data[3].e=-7;
	T.data[4].row=3; T.data[4].col=1; T.data[4].e=36;
	T.data[5].row=3; T.data[5].col=4; T.data[5].e=28;
	
	printf("轉(zhuǎn)置前的三元組表:\n"); 
	for(int i=1;i<=T.nums;i++){
		printf("%d %d %d\n",T.data[i].row,T.data[i].col,T.data[i].e);
	}
	Fast_TransposeTSMatrix(&T,&M);
	printf("快速轉(zhuǎn)置之后的三元組表:\n");
	for(int i=1;i<=T.nums;i++){
		printf("%d %d %d\n",M.data[i].row,M.data[i].col,M.data[i].e);
	}
	return 0;
}

運行結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-726971.html

到了這里，關(guān)于三元組表的快速轉(zhuǎn)置算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！