稀疏矩阵的三元组表示和转置
程序员文章站
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
- 设置转置后矩阵B的行数、列数和非零元素的个数;
- 计算A中每一列的非零元素个数;
- 计算A中每一列的第一个非零元素在B中的下标;
- 依次取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预置该元素所在列的下一个元素的存放位置;
}
}
**很明显第二种方法的复杂度要小很多**