欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

稀疏矩阵的三元组表示和转置

程序员文章站 2022-07-12 09:53:33
...

稀疏矩阵的三元组表示和转置

三元组表示

数据结构

  • 三元组类型
typedef struct
{
	int r;//行号
	int c;//列号
	int d;//元素值
}TupNode;//三元组类型
  • 三元组顺序表的类型
typedef struct
{
	int rows;//行数
	int cols;//列数
	int nums;//非零元素个数
	TupNode data[Maxsize];
}TSMatrix;//三元组顺序表的类型
  • 三元组由稀疏矩阵的创建
#include<iostream>
#define Maxsize 100
#define N 5
#define M 5
void Create(TSMatrix &t,int A[N][M])//创建三元组
{
	t.rows=N;//行和列
	t.cols=M;
	t.nums=0;//非零的元素的个数
	for(int i=0;i<N;i++)//依次的遍历所有的元素
	{
		for(int j=0;j<M;j++)
			if(A[i][j]!=0)//非0就直接放在三元组里面
			{
				num[j+1]++;     //这个num数组是在后面
				t.data[t.nums].r=i;//顺序取直接存有关
				t.data[t.nums].c=j;
				t.data[t.nums].d=A[i][j];
				t.nums++;
			}
	}
}
  • 三元组的输出
void Disp(TSMatrix t)//输出三元组
{
	if(t.nums<=0)
		return;
	for(int i=0;i<t.nums;i++)
		printf("\t%d\t%d\t%d\n",t.data[i].r+1,t.data[i].c+1,t.data[i].d);
}

转置

- 顺序存

直接在三元组里面找到在矩阵中没一列,然后重新放在三元组里面

void TranMat(TSMatrix ta,TSMatrix &tb)//顺序存
{
	int q=0;
	tb.rows=ta.rows;
	tb.cols=ta.cols;
	tb.nums=ta.nums;
	if(ta.nums!=0)
	{
		for(int i=0;i<ta.cols;i++)//依次找列
			for(int j=0;j<ta.nums;j++)//遍历所有的三元组
				if(ta.data[j].c==i)
				{
					tb.data[q].r=ta.data[j].c;
					tb.data[q].c=ta.data[j].r;
					tb.data[q].d=ta.data[j].d;
					q++;
				}
	}
}

- 顺序取直接存

发现转置的规律
引入两个数组作为辅助数据结构:
num[nu]:表示矩阵A中某列的非零元素的个数;
cpot[nu]:初始值表示矩阵A中某列的第一个非零元素在B中的位置。
num与cpot递推关系

  • cpot[0]=0;
  • cpot[col]=cpot[col-1]+num[col-1]; 1≤col<nu
  1. 设置转置后矩阵B的行数、列数和非零元素的个数;
  2. 计算A中每一列的非零元素个数;
  3. 计算A中每一列的第一个非零元素在B中的下标;
  4. 依次取A中的每一个非零元素对应的三元组;
    2.1 确定该元素在B中的下标pb;
    2.2 将该元素的行号列号交换后存入B中pb的位置;
    2.3 预置该元素所在列的下一个元素的存放位置;
int cp()//求cpot数组
{
	cpot[0]=0;
	int i;
	for(i=1;i<Maxsize;i++)
	{
		cpot[i]=cpot[i-1]+num[i];
	}
	return i;
		
}
void TranMat2(TSMatrix ta,TSMatrix &tb)//顺序取直接存
{
	tb.rows=ta.rows;
	tb.cols=ta.cols;
	tb.nums=ta.nums;
	int a=cp();
	for(int i=0;i<ta.nums;i++)
	{
		int pb=ta.data[i].c;
		tb.data[cpot[pb]].r=ta.data[i].c;
		tb.data[cpot[pb]].c=ta.data[i].r;
		tb.data[cpot[pb]].d=ta.data[i].d;
		cpot[pb]++;//这里很关键
		// ,2.3预置该元素所在列的下一个元素的存放位置;
	}
	
}
**很明显第二种方法的复杂度要小很多**