目錄

1.稀疏矩陣概念

2.三元組表

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

?4.題目實(shí)現(xiàn)

1.稀疏矩陣概念

矩陣中，若數(shù)值為0的元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非0元素的數(shù)目，并且非0元素分布沒(méi)有規(guī)律時(shí)，則稱該矩陣為稀疏矩陣。

圖示：

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-782472.html

2.三元組表

在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定

若把稀疏矩陣中的三元組線性表按順序儲(chǔ)存結(jié)構(gòu)儲(chǔ)存，則稱為三元組順序表，簡(jiǎn)稱為三元組表。

下圖即為轉(zhuǎn)化：

?三元組順序表的數(shù)據(jù)類型聲明如下：

#define M //稀疏矩陣行數(shù)
#define N //稀疏矩陣列數(shù)
#define MAX //稀疏矩陣中非零元最多的個(gè)數(shù)
typedef int Elem;
typedef struct 
{
	int r;//行號(hào) 
	int c;//列號(hào) 
	Elem d;//元素值 
}TupNode;

typedef struct
{
	int rows;//行數(shù)
	int cols;//列數(shù)
	int nums;//非零元素個(gè)數(shù)
	TupNode data[MAX]; 
}TSMat;

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

? 1.一個(gè)m×n的矩陣A，它的轉(zhuǎn)置B是一個(gè)n×m的矩陣，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。
? 2.?將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡(jiǎn)單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B，要得到按行優(yōu)先順序存儲(chǔ)的b.data，就必須重新排列三元組的順序。
???????由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的
核心思想：行列互換。

解決思路：
1.將矩陣行、列維數(shù)互換；
2.將每個(gè)三元組中的i和j相互調(diào)換；
3. 重排三元組次序，使B中元素以N的行(M的列)為主序。

A原矩陣三元組表? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? B轉(zhuǎn)置后的三元組表

?顯然發(fā)現(xiàn)行列互換，對(duì)A中的列又1到7循環(huán)查找，然后放入B中的行。

矩陣轉(zhuǎn)置的實(shí)現(xiàn)思路是：不斷遍歷存儲(chǔ)矩陣的三元組表，每次都取出表中 j 列最小的那一個(gè)三元組，互換行標(biāo)和列標(biāo)的值，并按次序存儲(chǔ)到一個(gè)新三元組表中，。

例如，將圖 2a) 三元組表存儲(chǔ)的矩陣進(jìn)行轉(zhuǎn)置的過(guò)程為：

1. 新建一個(gè)三元組表（用于存儲(chǔ)轉(zhuǎn)置矩陣），并將原矩陣的行數(shù)和列數(shù)互換賦值給新三元組；
2. 遍歷三元組表，找到表中 j 列最小值 1 所在的三元組 (3,1,6)，然后將其行標(biāo)和列標(biāo)互換后添加到一個(gè)新的三元組表中，如圖 3所示：

?3.繼續(xù)遍歷三元組表，找到表中 j 列次小值為 2 的三元組，分別為 (1,2,1)、(2,2,3) 和 (3,2,5)，根據(jù)找到它們的先后次序?qū)⒏髯缘男袠?biāo)和列標(biāo)互換后添加到新三元組表中，如圖 所示：

?代碼實(shí)現(xiàn)：

void TranMat(TSMat *t,TSMat *tb)//t為A的三元組順序表，tb為B的三元組順序表
{
	int k,k1=0,v;                       //k1記錄tb中元素個(gè)數(shù)
	tb->rows=t->cols;tb->cols=t->rows;  //行列互換
    tb->nums=t->nums;
	if(t->nums!=0)                      //當(dāng)存在非零元時(shí)進(jìn)行轉(zhuǎn)置
	{
		for(v=0;v<t->cols;v++)          //按v=0.1....t.cols循環(huán)
		{
			for(k=0;k<t->nums;k++)      //k用于掃描t.data的所有元素
			{
				if(t->data[i].c==v)    //找到一個(gè)列號(hào)為v的元素
				{
					tb->data[k1].r=t->data[k].c;   //tb的行為t的列
					tb->data[k1].c=t->data[k].r;   //tb的列為t的行
					tb->data[k1].d=t->data[k].d;   //值不變
					k1++;                           //tb中元素的個(gè)數(shù)增加1.
				}
			}
		}

?4.題目實(shí)現(xiàn)

? ? 把給定的二維稀疏矩陣用三元組表表示和存儲(chǔ)，并進(jìn)行稀疏矩陣的轉(zhuǎn)置，輸出轉(zhuǎn)置后的稀疏矩陣的三元組表。

假如給定如下二維稀疏矩陣：

3? 0? 0? ?1? 0? 0

0? 4? 0? 0? 0? ?0

5? 0? 0 2? ?0? 0

代碼實(shí)現(xiàn)：

#include<stdio.h>
#define M 3
#define N 6
#define MAX 20
typedef int Elem;
typedef struct 
{
	int H;//行號(hào) 
	int L;//列號(hào) 
	Elem d;//元素值 
}TupNode;

typedef struct
{
	int rows;//行數(shù)
	int cols;//列數(shù)
	int nums;//非零元素個(gè)數(shù)
	TupNode data[MAX]; 
}TSMat;

void CreatMat(TSMat *B,Elem A[M][N])
{
	int i,j;
	B->rows =M;B->cols =N;B->nums =0 ;
	for(i=0;i<M;i++)
	{
		for(j=0;j<N;j++)
		{
			if(A[i][j]!=0)
			{
				B->data[B->nums].H=i;
				B->data[B->nums].L=j;
				B->data[B->nums].d=A[i][j];
				B->nums++;
			}
		}
	}
}//把二維稀疏矩陣用三元組表表示

void Print(TSMat *B)
{
	int i;
	if(B->nums<=0)
	{
		return ;
	}
	printf("%d   %d   %d\n",B->rows,B->cols,B->nums);
	printf("---------\n");
	for(i=0;i<B->nums;i++)
	{
		printf("%d   %d   %d\n",B->data[i].H,B->data[i].L,B->data[i].d);
	}
}//三元組表的輸出 

void TranMat(TSMat *B,TSMat *b)
{
	int i,j=0,k;
	b->rows=B->cols;b->cols=B->rows;b->nums=B->nums;
	if(B->nums!=0)
	{
		for(k=0;k<B->cols;k++)
		{
			for(i=0;i<B->nums;i++)
			{
				if(B->data[i].L==k)
				{
					b->data[j].H=B->data[i].L;
					b->data[j].L=B->data[i].H;
					b->data[j].d=B->data[i].d;
					j++;
				}
			}
		}
	}
} //稀疏矩陣的轉(zhuǎn)置 

int main()
{
	TSMat B,b;
	int i,j;
	int A[M][N]={{3,0,0,1,0,0},{0,4,0,0,0,0},{5,0,0,2,0,0}};//這里可以可以自己用兩個(gè)循環(huán)語(yǔ)句進(jìn)行輸入
	printf("原來(lái)的二維稀疏矩陣為:\n");
	for(i=0;i<M;i++)
	{
		for(j=0;j<N;j++)
		{
			printf("%d  ",A[i][j]);
		}
		printf("\n");
	}
	printf("二維稀疏矩陣用三元組表表示為:\n");
	CreatMat(&B,A);
	Print(&B);
	printf("稀疏矩陣三元組表的轉(zhuǎn)置為:\n");
	TranMat(&B,&b);
	Print(&b);
	return 0;
}

運(yùn)行結(jié)果圖片：

?

?

到了這里，關(guān)于稀疏矩陣的表示以及轉(zhuǎn)置的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！