快速转置的原理是：如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中(上面那图是b.data)恰当位置。那么在对a.data中的三元组一次做转置时，便可直接放到b.data中恰当的位置上去。
设两个向量：num和cpot
num[col]表示矩阵M中第col列中的非零元素个数。
cpot[col]指M中第col列的第一个非零元在b.data中的恰当位置。
有下面两个公式：
cpot[0]=0;
cpot[col]=copt[col-1]+num[col-1] 1<=col<a.nu
对于一个三元表，行为i，列为j，值为v。需将其i与j的值对调才能得到新的三元表，但是如果直接进行转换，得到的新的三元表的顺序是混乱的，不符合三元表的规则。所以，课本首先介绍了一个用扫描来转置的算法（这个算法比较容易，在这里我就不说了），但是这个转置算法的时间复杂度太高，于是就有了接下来的快速转置算法。
要你对一个三元表进行步骤最少的转置，你可能会想，如果知道三元表中每一项在转置后的新的三元表中的位置，然后直接放进去，岂不是极大的缩小了时间复杂度？没错！快速转置法正是基于这种思想而设计的。
转置的时候直接从第一项读起，读取其j值，比如课本中a.data这个三元表的第一项的j值为2,因为j=2占据第3、4位，所以应该从第三位开始放，接下来如果读取的某一项的j值也是2,就放在第4位。因为j=2的项只有两个，所以第5位绝对不会被j=2的项占据，第5、6项本来就是留给j=3的。再比如当读到j=6的那项时，第8位是留给它的，就可以直接放进第8位了。这样，读取每一项，都能在三元表中找到相应的位置，这就是稀疏矩阵快速转置的原理。
#include<stdio.h>
#define M 6//行数
#define N 6//列数
#define Maxsize 8
typedef struct
{
int r;//行号
int c;//列号
int d;//元素值
}TupNode;//三元组类型
typedef struct
{
int rows;//行数
int cols;//列数
int num;//非零元个数
TupNode data[Maxsize];//非零元素的行列以及元素值的三元组信息
}TSMatrix;//三元表类，一个三元表相当于一个稀疏矩阵
void CreateMat(TSMatrix &t,int a[M][N])//创建一个三元表，从a数组里面获取数据
{
int i,j;
t.rows=M;t.cols=N;t.num=0;//初始化一张三元表
for(i=0;i<M;i++)//逐行扫描
{
for(j=0;j<N;j++)//逐列扫描
{
if(a[i][j]!=0)
{
t.data[t.num].r=i;//更新最大行数
t.data[t.num].c=j;//更新最大列数
t.data[t.num].d=a[i][j];//插入元素值
t.num++;//非零元素个数+1，因为是从0开始，所以只要执行if语句，个数就+1；
}
}
}
}
void DispMat(TSMatrix t)//输出一个稀疏矩阵的三元表
{
int k;
if(t.num<=0) return;//没有非零元素时直接返回
printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.num);//表头：行数，列数，非零元素数
printf("\t---------------------------------\n");
for(k=0;k<t.num;k++)//输出每一个非零元素的三元信息
{
printf("\t%d\t%d\t%d\n",t.data[k].r,t.data[k].c,t.data[k].d);
}
}
void show(TSMatrix t)//把矩阵直观的显示出来
{
int a[M][N];
int m,n,k;
for (m=0;m<M;m++)
{
for(n=0;n<N;n++)
{
a[m][n]=0;
}
}
for(k=0;k<t.num;k++)
{
n=t.data[k].c;
m=t.data[k].r;
a[m][n]=t.data[k].d;
}
for (m=0;m<M;m++)
{
for(n=0;n<N;n++)
{
printf("%3d",a[m][n]);
}
printf("\n");
}
}
void FastTranTat(TSMatrix m,TSMatrix &t)//快速转置函数
{
int numm[N];//记录每一列的非零元素的个数，一共有N列故数组长度为n
int cpot[Maxsize];//用于记录三元表中某个列数的第一个非零项在新三元表中的位置
t.cols=m.rows; t.rows=m.cols; t.num=m.num;//初始化矩阵t
if(t.num)
{
for(int i=0;i<m.cols;i++)
{
numm[i]=0;//初始化数组,先全部置为0；
}
for(int i=0;i<m.num;i++)
{
++numm[m.data[i].c];//求m中每一列含非零元的个数，预留出在新三元表中的位置
}
cpot[0]=0;//原三元表中第一例的首非零元在新三元表的第一列
for(int i=1;i<m.cols;i++)
{
cpot[i]=cpot[i-1]+numm[i-1];//求除了第一列其它每一列的第一个非零元在新·三元表中的位置
}
for(int p=0;p<m.num;p++)//遍历原三元表的每一项
{
t.data[cpot[m.data[p].c]].r=m.data[p].c;
/*
这一句有点绕，其实可以分成好几层临时变量来写，但是这样层层嵌套
更加直观一点。它其实
左边就是 旧三元表 某一个元素的列数里面的第一个非零
元素 在 新三元表中的位置，然后这个位置的行号。
右边是 旧三元表中某一元素的列号
然后，把右边赋给左边，也就是旧列号变新行号
由于每一个旧三元表中的元素都能得到相应的操作，所以遍历一次即可
一个萝卜一个坑的填进新三元表
*/
t.data[cpot[m.data[p].c]].c=m.data[p].r;//同理，不过是旧行号变新列号
t.data[cpot[m.data[p].c]].d=m.data[p].d;//元素值也要赋过来
cpot[m.data[p].c]++;//这句的意思是旧三元表某列首非零元在
//新三元表中的位置经过以上处理要向下
//移动一个位置，在新三元表里看，这个操作就是
//某一行号的元素处理完了，然后往下移动
//一个位置，下次如果还要处理这个行号的元素
//就直接用移动好的这个位置。因为每一行号的元素位置
//都被预留好了，所以不用担心溢出。
}
}
}
int main()
{
int a[6][6]={{0,12,9,0,0,0},{0,0,0,0,0,0},{-3,0,0,0,0,0},{0,0,0,24,0,0}
, {0,18,0,0,0,0},{15,0,0,-7,0,14}};
TSMatrix t,tb;
CreateMat(t,a);
printf("原矩阵三元表：\n");
DispMat(t);
printf("矩阵为\n\n");
show(t);
printf("转置后三元表\n");
FastTranTat(t,tb);
DispMat(tb);
printf("矩阵为\n\n");
show(tb);
}
0 条评论