国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置

2年前作者：業(yè)余小程序猿分類：Toy博客閱讀(18)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

目錄

1.三元組表的定義

2.三元組表的數(shù)據(jù)結(jié)構(gòu)

3.三元組表的構(gòu)建

4.輸出三元組表

5.兩個(gè)三元組表相加

?代碼的流程圖?

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

6.三元組表的快速轉(zhuǎn)置

?算法思想

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

7.三元組表輸出矩陣

8.全部代碼

9.總結(jié)

1.三元組表的定義

????????三元組研究目的 對(duì)于在實(shí)際問(wèn)題中出現(xiàn)的大型的稀疏矩陣，若用常規(guī)分配方法在計(jì)算機(jī)中儲(chǔ)存，將會(huì)產(chǎn)生大量的內(nèi)存浪費(fèi)，而且在訪問(wèn)和操作的時(shí)候也會(huì)造成大量時(shí)間上的浪費(fèi)，為了解決這一問(wèn)題，從而產(chǎn)生了多種解決方案。 由于其自身的稀疏特性，通過(guò)壓縮可以大大節(jié)省稀疏矩陣的內(nèi)存代價(jià)。

????????主要是用來(lái)存儲(chǔ) 稀疏矩陣 的一種壓縮方式，也叫三元組表。 假設(shè)以順序 存儲(chǔ)結(jié)構(gòu) 來(lái)表示三元組表（triple table），則得到 稀疏矩陣 的一種壓縮存儲(chǔ)方式，即三元組順序表，簡(jiǎn)稱三元組表。

數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置

2.三元組表的數(shù)據(jù)結(jié)構(gòu)

#define MAX 1000

typedef struct
{
	int row,col,e;    //數(shù)據(jù)所在的行、列，數(shù)值
}Triple;

typedef struct
{
	Triple  data[MAX+1];
	int mu,nu,tu;		//矩陣的行數(shù)，列數(shù)和非零元個(gè)數(shù)
}TSMatrix;

3.三元組表的構(gòu)建

思路：從第一行開始遍歷查找非零元素，存入三元組表data[tu]中，data[tu].row=i，data[tu].col=j，data[tu].e=a[i][j]

void input(TSMatrix *p,int m,int n)
{
	int i,j;
	int a[100][100];
	for( i=1;i<=m;i++)    //隨機(jī)生成稀疏矩陣
	for(j=1;j<=n;j++)
	{
		if(1+rand()%4>=1+rand()%19)
			a[i][j]=1+rand()%99;
		else
			a[i][j]=0;
	}
	for(int i=1;i<=m;i++){    //打印出該稀疏矩陣
	for(int j=1;j<=n;j++)
	{

		printf("%4d",a[i][j]);
	}printf("\n");
	}
	p->tu=0;    //三元組表的總個(gè)數(shù)
	for(i=1;i<=m;i++)    //進(jìn)行查找非零元素進(jìn)行存儲(chǔ)
	for(j=1;j<=n;j++)
	{
		if(a[i][j]!=0)
		{
		p->data[p->tu].row=i;	//行
		p->data[p->tu].col=j;	//列
		p->data[p->tu].e=a[i][j];	//	數(shù)據(jù)
		++p->tu;
		}
	}

}

4.輸出三元組表

void printTriple(TSMatrix *p)
{
	printf("\n三元組：\n");
	for(int i=0;i<p->tu;i++)
	{
		printf("%4d %4d %4d\n",p->data[i].row,p->data[i].col,p->data[i].e);
	}
}

5.兩個(gè)三元組表相加

思路：兩個(gè)三元組分別標(biāo)記兩個(gè)遍歷用的i，j，每次都比較i和j所在位置的row、col值；先比較row的大小，如果i的row小于j的，那就先填i的，然后i++填下一個(gè)；如果i和j的row都相同，就去比col，然后i的col小于j，者填i，否則填j的。

如果A與B的row和col都相同，就把row和col分別相加，再存入C中

如果i遍歷完，j沒(méi)遍歷完，把j剩余的全放入新的三元組表中；如果i沒(méi)遍歷完，j遍歷完，把i剩余的全放入新的三元組表中。

通俗的解釋：這個(gè)就類似于小編之前的寫的順序表和合并的思路。大家也可以回顧一下兩個(gè)順序表的合并思路，聯(lián)系起來(lái)。數(shù)據(jù)結(jié)構(gòu)：兩個(gè)順序表合并算法_業(yè)余小程序猿的博客-CSDN博客

注意：只有兩個(gè)相同行列的矩陣才能相加，所以相加之前要先判斷一下能不能。

數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置

?代碼的流程圖

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


void sum(TSMatrix *A,TSMatrix *B,TSMatrix *C)
{
	C->mu=A->mu;    //只有兩個(gè)行列相同的矩陣才能相加
	C->nu=A->nu;    //所以用A或B都一樣
	C->tu=0;
	if(A->mu!=B->mu&&A->nu!=B->nu){
		printf("矩陣要大小相同才能相加！");
		return ;
	}
	int i=0,j=0;
	while(i<A->tu&&j<B->tu)
	{
		if(A->data[i].row<B->data[j].row)    //A的row<B的，C中加入A的
		{
			C->data[C->tu].row=A->data[i].row;	//行
			C->data[C->tu].col=A->data[i].col;	//列
			C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
			C->tu++;
			i++;
		}
		else if(A->data[i].row==B->data[j].row)    //A的row=B的，再繼續(xù)比較col
		{
			if(A->data[i].col<B->data[j].col)    //A的col<B的，C中加入A的
			{
			C->data[C->tu].row=A->data[i].row;	//行
			C->data[C->tu].col=A->data[i].col;	//列
			C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
			C->tu++;
			i++;			
			}
			else if(A->data[i].col>B->data[j].col) //A的col>B的，C中加入B的
			{
			C->data[C->tu].row=B->data[j].row;	//行
			C->data[C->tu].col=B->data[j].col;	//列
			C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
			C->tu++;
			j++;
			}
			else    //A的col=B的，先把A和B的row和col分別相加，再存入C中
			{
				if(B->data[j].e+A->data[i].e!=0)
				{
					C->data[C->tu].row=B->data[j].row;	//行
					C->data[C->tu].col=B->data[j].col;	//列
					C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
					C->tu++;
				}
				i++;
				j++;
			}
		}
		else    //A的row>B的，C中加入B的
		{
			C->data[C->tu].row=B->data[j].row;	//行
			C->data[C->tu].col=B->data[j].col;	//列
			C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
			C->tu++;
			j++;			
		}
	}
	while(i<A->tu)//如果A剩余，把A剩余的全放入C中
	{
		C->data[C->tu].row=A->data[i].row;	//行
		C->data[C->tu].col=A->data[i].col;	//列
		C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
		C->tu++;
		i++;		
	}
	while(j<B->tu)//如果B剩余，把B剩余的全放入C中
	{
		C->data[C->tu].row=B->data[j].row;	//行
		C->data[C->tu].col=B->data[j].col;	//列
		C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
		C->tu++;
		j++;
	}

}

6.三元組表的快速轉(zhuǎn)置

轉(zhuǎn)置定義：將矩陣的行列互換得到的新矩陣稱為轉(zhuǎn)置矩陣，轉(zhuǎn)置矩陣的行列式不變。

數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置

?算法思想

矩陣的轉(zhuǎn)置就是講行列互換位置，如果普通兩層循環(huán)進(jìn)行循環(huán)的，時(shí)間復(fù)雜度就會(huì)變成,。所以我們要想辦法把只進(jìn)行一層循環(huán)就能完成轉(zhuǎn)置。

所以就要設(shè)置兩個(gè)數(shù)值num[]和cpot[]，num[]用于存儲(chǔ)每列非零元素的個(gè)數(shù)，cpot[]用于存儲(chǔ)每列第一個(gè)非零元素的初始位置。知道了每列非零元素的初始位置和非零元素的個(gè)數(shù)，而且列都是按大小來(lái)排的，所以轉(zhuǎn)置時(shí)候一定的先遇到列數(shù)小的先放入，不用擔(dān)心大小順序會(huì)不同。于是就可以對(duì)三元組表進(jìn)行一次遍歷存儲(chǔ)。

數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置

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

void Transposition(TSMatrix *p,TSMatrix *q)
{
	q->nu=p->mu;
	q->mu=p->nu;
	q->tu=p->tu;//把行列數(shù)值對(duì)換，大小不變
	if(q->tu)    //如果三元組為空就不用
	{
		int i;
		int num[100],cpot[100];
		for(i=0; i<p->mu;i++)
			num[i]=0;		//初始化數(shù)組
		for(i=0;i<p->tu;i++)    //找出每列非零元個(gè)數(shù)，i=0存的第一列的
			++num[p->data[i].col - 1];
		cpot[0]=0;
		for(i=1;i<p->nu;i++)    //求每列第一個(gè)非零元素所在位置
			cpot[i]=cpot[i-1]+num[i-1];
		int a,b;
		for(i=0;i<p->tu;i++)    //進(jìn)行轉(zhuǎn)置
		{
			
			b=p->data[i].col-1;   
			a=cpot[b];    //找出每列所在位置 
			q->data[a].row = p->data[i].col;    //將其放入另外一個(gè)三元組表中
			q->data[a].col = p->data[i].row;
			q->data[a].e = p->data[i].e;
			++cpot[b];    //讓其下次找到該列中的下一個(gè)非零元素
		}

	}
	
}

????????時(shí)間復(fù)雜度：O(nu+tu)

????????三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需按行號(hào)存取某一行的非零元，則需從頭開始進(jìn)行查找。

7.三元組表輸出矩陣

void output(TSMatrix *p)
{
	printf("輸出矩陣：\n");
	int i,j,k=0,a=0;
	for(i=1;i<=p->mu;i++){
		for(j=1;j<=p->nu;j++)
		{
			if(p->data[k].row==i&&p->data[k].col==j)
			{
				printf("%3d",p->data[k].e);
				k++;
			}
			else
				printf("%3d",a);
		}
		printf("\n");
	}
}

8.全部代碼


#include<stdio.h>
#include<stdlib.h>
#define MAX 1000

typedef struct
{
	int row,col,e;
}Triple;

typedef struct
{
	Triple  data[MAX+1];
	int mu,nu,tu;		//矩陣的行數(shù)，列數(shù)和非零元個(gè)數(shù)
}TSMatrix;

void input(TSMatrix *p,int m,int n)
{
	int i,j;
	int a[100][100];
	for( i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		if(1+rand()%4>=1+rand()%19)
			a[i][j]=1+rand()%99;
		else
			a[i][j]=0;
	}
	for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++)
	{

		printf("%4d",a[i][j]);
	}printf("\n");
	}
	p->tu=0;
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		if(a[i][j]!=0)
		{
		p->data[p->tu].row=i;	//行
		p->data[p->tu].col=j;	//列
		p->data[p->tu].e=a[i][j];	//	數(shù)據(jù)
		++p->tu;
		}
	}

}

void printTriple(TSMatrix *p)
{
	printf("\n三元組：\n");
	for(int i=0;i<p->tu;i++)
	{
		printf("%4d %4d %4d\n",p->data[i].row,p->data[i].col,p->data[i].e);
	}
}

void sum(TSMatrix *A,TSMatrix *B,TSMatrix *C)
{
	C->mu=A->mu;
	C->nu=A->nu;
	C->tu=0;
	if(A->mu!=B->mu&&A->nu!=B->nu){
		printf("矩陣要大小相同才能相加！");
		return ;
	}
	int i=0,j=0;
	while(i<A->tu&&j<B->tu)
	{
		if(A->data[i].row<B->data[j].row)
		{
			C->data[C->tu].row=A->data[i].row;	//行
			C->data[C->tu].col=A->data[i].col;	//列
			C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
			C->tu++;
			i++;
		}
		else if(A->data[i].row==B->data[j].row)
		{
			if(A->data[i].col<B->data[j].col)
			{
			C->data[C->tu].row=A->data[i].row;	//行
			C->data[C->tu].col=A->data[i].col;	//列
			C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
			C->tu++;
			i++;			
			}
			else if(A->data[i].col>B->data[j].col)
			{
			C->data[C->tu].row=B->data[j].row;	//行
			C->data[C->tu].col=B->data[j].col;	//列
			C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
			C->tu++;
			j++;
			}
			else
			{
				if(B->data[j].e+A->data[i].e!=0)
				{
					C->data[C->tu].row=B->data[j].row;	//行
					C->data[C->tu].col=B->data[j].col;	//列
					C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
					C->tu++;
				}
				i++;
				j++;
			}
		}
		else
		{
			C->data[C->tu].row=B->data[j].row;	//行
			C->data[C->tu].col=B->data[j].col;	//列
			C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
			C->tu++;
			j++;			
		}
	}
	while(i<A->tu)
	{
		C->data[C->tu].row=A->data[i].row;	//行
		C->data[C->tu].col=A->data[i].col;	//列
		C->data[C->tu].e=A->data[i].e;	//	數(shù)據(jù)
		C->tu++;
		i++;		
	}
	while(j<B->tu)
	{
		C->data[C->tu].row=B->data[j].row;	//行
		C->data[C->tu].col=B->data[j].col;	//列
		C->data[C->tu].e=B->data[j].e;	//	數(shù)據(jù)
		C->tu++;
		j++;
	}

}

void Transposition(TSMatrix *p,TSMatrix *q)
{
	q->nu=p->mu;
	q->mu=p->nu;
	q->tu=p->tu;
	if(q->tu)
	{
		int i;
		int num[100],cpot[100];
		for(i=0; i<p->mu;i++)
			num[i]=0;		//初始化數(shù)組
		for(i=0;i<p->tu;i++)
			++num[p->data[i].col - 1];
		cpot[0]=0;
		for(i=1;i<p->nu;i++)
			cpot[i]=cpot[i-1]+num[i-1];
		int a,b;
		for(i=0;i<p->tu;i++)
		{
			
			b=p->data[i].col-1;
			a=cpot[b];
			q->data[a].row = p->data[i].col;
			q->data[a].col = p->data[i].row;
			q->data[a].e = p->data[i].e;
			++cpot[b];
		}

	}
	
}

void output(TSMatrix *p)
{
	printf("輸出矩陣：\n");
	int i,j,k=0,a=0;
	for(i=1;i<=p->mu;i++){
		for(j=1;j<=p->nu;j++)
		{
			if(p->data[k].row==i&&p->data[k].col==j)
			{
				printf("%3d",p->data[k].e);
				k++;
			}
			else
				printf("%3d",a);
		}
		printf("\n");
	}
}

int main()
{
	
	TSMatrix	A,B,C,T;
	printf("輸入A矩陣的行列數(shù)：\n");
	scanf("%d%d",&A.mu,&A.nu);
	input(&A,A.mu,A.nu);
	printTriple(&A);
	printf("\n輸入B矩陣的行列數(shù)：\n");
	scanf("%d%d",&B.mu,&B.nu);
	input(&B,B.mu,B.nu);
	printTriple(&B);
	sum(&A,&B,&C);
	printf("\nC的三元組：\n");
	printTriple(&C);
	output(&C);
	printf("\nA的轉(zhuǎn)置：\n");
	Transposition(&A,&T);
	printTriple(&T);
	output(&T);
	getchar();
	getchar();
	return 0;
}

9.總結(jié)

? ? ? ? 三元組表在考研中，很多自主命題的大學(xué)喜歡考這個(gè)。在2021年安徽大學(xué)計(jì)算機(jī)專業(yè)考研中就出了一個(gè)15分的三元組快速轉(zhuǎn)置的大題來(lái)考查學(xué)生（當(dāng)年平均分在七八十分左右）。因?yàn)閷?duì)于考生來(lái)說(shuō)，三元組表很少有學(xué)生會(huì)認(rèn)真思考，而且王道考研或者是其他考研資料，也很少講三元組表方面的知識(shí)點(diǎn)。所以讀者需要加強(qiáng)對(duì)三元組表的學(xué)習(xí)，尤其是快速轉(zhuǎn)置。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-431609.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：三元組的構(gòu)建、相加和快速轉(zhuǎn)置的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包