稀疏矩阵的转置算法（稀疏矩阵的转置 要求1）以三元组的方式存储稀疏矩阵 2）普通转置方法实现 3）快速转置方法实现）

本文目录

• 稀疏矩阵的转置 要求1）以三元组的方式存储稀疏矩阵 2）普通转置方法实现 3）快速转置方法实现
• 稀疏矩阵的转置运算用C语言
• 稀疏矩阵与转置算法
• 稀疏矩阵的转置
• 求稀疏矩阵快速转置算法及代码
• 稀疏矩阵三元组表示以及转置
• 稀疏矩阵的转置算法程序

稀疏矩阵的转置 要求1）以三元组的方式存储稀疏矩阵 2）普通转置方法实现 3）快速转置方法实现

//普通转置算法
//时间复杂度:O(t*m);t是非零元个数，m是列数。每转置一列需要扫描全部三元数组
#include “stdafx.h“
#include 《iostream》
struct element{
int value;
int i,j;
};
struct matrix{
int c,v,t;
struct element *data;
};

int main(int argc, char* argv)
{
int m,n,t;
int i,j,d;
int index;
matrix *mt,*lm;//lm是转置后的矩阵
element *e;

//原是矩阵的输入
printf(“输入矩阵的行数，列数，非零元个数n“);
scanf(“%d%d%d“,&m,&n,&t);
mt=new matrix;
mt-》c=m;
mt-》v=n;
mt-》t=t;
mt-》data=new element[t];
printf(“按行序输入矩阵的非零元，按三元组形式:行 列 数据n“);
index=0;
do{
scanf(“%d%d%d“,&i,&j,&d);
e=new element;
e-》i=i;e-》j=j;e-》value=d;
mt-》data[index]=*e;
index++;
}while(index《t);

//对矩阵转置
lm=new matrix;
lm-》data=new element[t];
i=0;j=0;index=0;
int k=0;
lm-》c=n;//行数和列数对掉，非零元总数不变
lm-》v=m;
lm-》t=t;
for(i=0;i《n;i++){//对所有三元组扫描
for(j=0;j《t;j++){//对原始矩阵的每一列扫描

if(mt-》data[j].j==i){//对每一列进行转置
//对此列上的元素对掉信息
lm-》data[k].i=mt-》data[j].j;
lm-》data[k].j=mt-》data[j].i;
lm-》data[k].value=mt-》data[j].value;
k++;
}
else continue;

}
}
index=0;
printf(“转置后的矩阵n“);
printf(“行 列 值n“);
while(index《t){
printf(“(%d %d %d)n“,lm-》data[index].i,lm-》data[index].j,lm-》data[index].value);
index++;
}
return 0;
}

快速转置代码如下:
//快速转置算法

#include “stdafx.h“
#include 《iostream》
struct element{
int value;
int i,j;
};
struct matrix{
int c,v,t;
struct element *data;
};
//每行第一个非零元位置数组position,每行非零元个数数组number
int *position;
int *number;
int main(int argc, char* argv)
{
int m,n,t;
int i,j,d;
int index;
matrix *mt,*lm;//lm是转置后的矩阵
element *e;

//原是矩阵的输入
printf(“输入矩阵的行数，列数，非零元个数n“);
scanf(“%d%d%d“,&m,&n,&t);
mt=new matrix;
mt-》c=m;
mt-》v=n;
mt-》t=t;
mt-》data=new element[t];

position=new int[m];
number=new int[m];

printf(“按行序输入矩阵的非零元，按三元组形式:行 列 数据n“);
index=0;
do{
scanf(“%d%d%d“,&i,&j,&d);
e=new element;
e-》i=i;e-》j=j;e-》value=d;
mt-》data[index]=*e;
index++;
}while(index《t);

//建立转置矩阵位置数组

matrix *bm=new matrix;
bm-》c=n;
bm-》v=m;
bm-》t=t;
bm-》data=new element[t];

for(i=0;i《n;i++)number[i]=0;
for(i=0;i《t;i++)number[mt-》data[i].j]++;
position=0;
for(i=1;i《n;i++){
position[i]=position[i-1]+number[i-1];
}
for(i=0;i《t;i++){
index=mt-》data[i].j;j=position[index];//原始数组第j列的第一个元素，当这一列再次有元素时，依次插入
bm-》data[j].i=mt-》data[i].j;
bm-》data[j].j=mt-》data[i].i;
bm-》data[j].value=mt-》data[i].value;
position[index]++;//此列下一个元素为上一个元素加1
}
//对矩阵快速转置
index=0;
printf(“n原三元组矩阵n“);
while(index《t){
printf(“（%d %d %d)n“,mt-》data[index].i,mt-》data[index].j,mt-》data[index].value);
index++;
}
index=0;
printf(“n转置后的三元组矩阵n“);
while(index《t){
printf(“（%d %d %d)n“,bm-》data[index].i,bm-》data[index].j,bm-》data[index].value);
index++;
}
return 0;
}

稀疏矩阵的转置运算用C语言

#include 《stdio.h》
#include 《stdlib.h》
#define OK 1
#define MAXSIZE 12500 //非零元个数最大值
typedef int Status;
typedef int ElemType;
typedef struct
{
int i,j; //非零元的行下标和列下标
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; //非零元三元组表，data未用
int mu,nu,tu; //矩阵的行数，列数，非零元个数
}TSMatrix;

/*Status TransposeSMatrix(TSMatrix M,TSMatrix *T)
{
//求稀疏矩阵M的转置矩阵T的一般算法
int q,col,p;
T-》mu=M.nu;
T-》nu=M.mu;
T-》tu=M.tu;
if(M.tu)
{
q=1;
for(col=1;col《=M.nu;col++)
for(p=1;p《=M.tu;p++)
if(M.data[p].j==col)
{
T-》data[q].i=M.data[p].j;
T-》data[q].j=M.data[p].i;
T-》data[q].e=M.data[p].e;
q++;
}
}
return OK;
}//TransposeSMatrix*/

Status FastTransposeSMatrix(TSMatrix M,TSMatrix *T)
{
//采用三元组顺序存储表示，求稀疏矩阵M的转置矩阵的快速转置算法
int col,t,q,p;
int num; //num[col]表示矩阵M中第col列中非零元个数
int cpot; //cpot[col]表示M中第col列的第一个非零元在T.data中恰当位置
T-》mu=M.nu;
T-》nu=M.mu;
T-》tu=M.tu;
if(M.tu)
{
for(col=1;col《=M.nu;col++)
num[col]=0;
for(t=1;t《=M.tu;t++)
num[M.data[t].j]++; //求M中每一列含非零元个数

cpot=1;
for(col=2;col《=M.nu;col++)
cpot[col]=cpot[col-1]+num[col-1];
//求第col列中第一个非零元在T.data中的序号

for(p=1;p《=M.tu;p++)
{
col=M.data[p].j;
q=cpot[col];
T-》data[q].i=M.data[p].j;
T-》data[q].j=M.data[p].i;
T-》data[q].e=M.data[p].e;
cpot[col]++;
}

}
return OK;
}//FastTransposeSMatrix

int main()
{
int i;
TSMatrix M,T;
system(“color 3e“);

printf(“请输入矩阵的非零元个数,矩阵的行数和列数:“);
scanf(“%d%d%d“,&M.tu,&M.mu,&M.nu);

for(i=1;i《=M.tu;i++)
{
printf(“请输入第%d个非零元的行坐标，列坐标，值:\n“,i);
scanf(“%d%d%d“,&M.data[i].i,&M.data[i].j,&M.data[i].e);
}
printf(“原矩阵为:\n“);
printf(“ i j e\n“);
for(i=1;i《=M.tu;i++)
printf(“%4d%4d%4d\n“,M.data[i].i,M.data[i].j,M.data[i].e);

// TransposeSMatrix(M,&T);
FastTransposeSMatrix(M,&T);

printf(“转置矩阵为:\n“);
printf(“ i j e\n“);
for(i=1;i《=T.tu;i++)
printf(“%4d%4d%4d\n“,T.data[i].i,T.data[i].j,T.data[i].e);

return 0;

}

/*
请输入矩阵的非零元个数,矩阵的行数和列数:8 6 6
请输入第1个非零元的行坐标，列坐标，值:
1 2 12
请输入第2个非零元的行坐标，列坐标，值:
1 3 9
请输入第3个非零元的行坐标，列坐标，值:
3 1 -3
请输入第4个非零元的行坐标，列坐标，值:
3 6 14
请输入第5个非零元的行坐标，列坐标，值:
4 3 24
请输入第6个非零元的行坐标，列坐标，值:
5 2 18
请输入第7个非零元的行坐标，列坐标，值:
6 1 15
请输入第8个非零元的行坐标，列坐标，值:
6 4 -7
原矩阵为:
i j e
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
转置矩阵为:
i j e
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Press any key to continue
*/

中间采用了两种转置算法，VC6下调试皆可通过

稀疏矩阵与转置算法

#include 《stdio.h》
#include 《stdlib.h》

typedef struct{
        int row;
        int col;
        int data;
}xishu;//存储稀疏矩阵的结构(行， 列，值)


#define MAX_COL 10
//static void transpose(xishu a, xishu b);//普通算法

static void fasttranspose(xishu a, xishu b);//改进的算法

static void create(int a, int m, int n, xishu b, int* count);
static void print(int* count, xishu a);

int main(int argc, char** argv)
{
        int a = { {0, 0, 0, 22, 0, -1}, {0, 71, 0, 0, 0, 0}, {0, 0, 0, 88, 0, 0},
                                                {0, 0, -9, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 7} };
        xishu b, c;
        int count = 0, i, k;

        for(i = 0; i 《 10; i++){
                b[i].row = c[i].row = 0;
                b[i].col = c[i].col = 0;
                b[i].data = c[i].data = 0;
        }//初始化


        create(a, 6, 6, b, &count);//建立一个以xishu为元素的数组来表示一个稀疏矩阵

        printf(“\nbefore tranpose\n“);
        print(&count, b);//打印建立好的稀疏矩阵


        //transpose(b, c);

        fasttranspose(b, c);//建立转置矩阵

        printf(“\nafter transpos\n“);
        print(&count, c);//打印转置矩阵

        exit(0);
}

static void print(int* count, xishu a)
{
        int k;

        for(k = 1; k 《= *count; k++){
               printf(“%d\t%d\t%d\n“, a[k].row, a[k].col, a[k].data);
        }
}

static void create(int a, int m, int n, xishu b, int* count)
{
        int i, j;

        *count = 0;
        b.row = m;
        b.col = n;

        for(i = 0; i 《 m; i++){
                for(j = 0; j 《 n; j++){
                        if(a[i][j] != 0){
                                (*count)++;
                                b[*count].row = i;
                                b[*count].col = j;
                                b[*count].data = a[i][j];
                        }
                }
        }
        b.data = *count;
}

/***
static void transpose(xishu a, xishu b)
{
//该算法的时间代价为O(a.data*a.data)

        int count = 0;
        int i, col;

        b.row = a.col;
        b.col = a.row;
        b.data = a.data;
        printf(“%d, %d, %d\n“, b.row, b.col, b.data);
        printf(“%d, %d, %d\n“, a.row, a.col, a.data);

        for(col = 0; col 《 a.col; col++){
                for(i = 1; i 《= a.data; i++){
                        if(a[i].col == col){
                                count++;
                                b[count].row = a[i].col;
                                b[count].col = a[i].row;
                                b[count].data = a[i].data;
                        }
                }
        }
}
***/ 
static void fasttranspose(xishu a, xishu b)
{
//改进的算法，该算法的时间代价为O(a.col+a.data)

        int i, pos;
        int row_num[MAX_COL];
        int start_pos[MAX_COL];

        b.row = a.col;
        b.col = a.row;
        b.data = a.data;

        for(i = 0; i 《 a.col; i++){
                row_num[i] = 0;
        }
        for(i = 1; i 《= a.data; i++){
                row_num[a[i].col]++;
        }

        start_pos = 1;
        for(i = 1; i 《 a.col; i++){
                start_pos[i] = start_pos[i-1] + row_num[i-1];
        }

        for(i = 1; i 《= a.data; i++){
                pos = start_pos[a[i].col];
                while(b[pos].data != 0){
                        pos++;
                }
                b[pos].row = a[i].col;
                b[pos].col = a[i].row;
                b[pos].data = a[i].data;
        }
}

稀疏矩阵的转置

首先说稀疏矩阵的存储，可以用
__int64 Key = (行《《32) + (列) 作为索引，使用 STL库的 map 存储。转置就是对Key的交换了，很简单！下面的例子：（GCC编译成功，MSVC的应该也可以,只是 __int64_t 变成__int64）
#include 《map》
#include 《stdio.h》
#include 《vector》
#include 《stdlib.h》
using namespace std;

class hashmap_mat
{
private:
map《unsigned __int64_t, double》 map_mat;
double m_idle_val;
public:
hashmap_mat(double idle_val = 0)
:m_idle_val(idle_val)
{}
~hashmap_mat(){map_mat.clear();}
public:
double operator () (unsigned int m,unsigned int n)
{
__int64_t key = (unsigned __int64_t)(((unsigned __int64_t)m)《《32)+n;
if (map_mat.find(key)==map_mat.end())
return m_idle_val;
return map_mat[key];
}
void setVal(unsigned int m,unsigned int n,double val)
{
__int64_t key = (unsigned __int64_t)(((unsigned __int64_t)m)《《32)+n;
map_mat[key] = val;
}
public:
void SwapT()
{
std::vector《unsigned __int64_t》 keys;
std::vector《double》 values;

for (map《unsigned __int64_t, double》::iterator p = map_mat.begin();
p!=map_mat.end();p++)
{
unsigned int m = (((*p).first)》》32) & 0x00ffffffff;
unsigned int n = ((*p).first) & 0x00ffffffff;
double v = (*p).second;
keys.push_back((unsigned __int64_t)(((unsigned __int64_t)n)《《32)+m);
values.push_back(v);
}
map_mat.clear();
size_t sz = keys.size();
for (size_t i = 0;i《sz;i++)
map_mat[keys[i]] = values[i];
}

};

int main()
{
//make a mat 20 * 20, has 1 elements nonzero
hashmap_mat mat(0);
//insert 3 items
mat.setVal(rand()%10,rand()%10,rand()%100/100.0);
mat.setVal(rand()%10,rand()%10,rand()%100/100.0);
mat.setVal(rand()%10,rand()%10,rand()%100/100.0);
printf(“Raw Matrix:\n“);
for (int i=0;i《10;i++)
{
for (int j=0;j《10;j++)
printf(“%3.2lf “,mat(i,j));
printf(“\n“);
}
//swap
mat.SwapT();
printf(“Swapped Matrix:\n“);
for (int i=0;i《10;i++)
{
for (int j=0;j《10;j++)
printf(“%3.2lf “,mat(i,j));
printf(“\n“);
}
return 0;
}

求稀疏矩阵快速转置算法及代码

typedef struct
{ int row ; /* 行下标 */
int col ; /* 列下标 */
elemtype value; /* 元素值 */
}Triple ;
typedef struct
{ int rn ; /* 行数 */
int cn ; /* 列数 */
int tn ; /* 非0元素个数 */
Triple data[MAX_SIZE] ;
}TMatrix ;
快速转置的算法
算法思想：直接按照稀疏矩阵A的三元组表a.data的次序依次顺序转换，并将转换后的三元组放置于三元组表b.data的恰当位置。
前提：若能预先确定原矩阵A中每一列的(即B中每一行)第一个非0元素在b.data中应有的位置，则在作转置时就可直接放在b.data中恰当的位置。因此，应先求得A中每一列的非0元素个数。
附设两个辅助向量num[ ]和cpot[ ] 。
◆ num[col]：统计A中第col列中非0元素的个数；
◆ cpot[col] ：指示A中第一个非0元素在b.data中的恰当位置。
显然有位置对应关系：
cpot=1
cpot[col]=cpot[col-1]+num[col-1] 2≦col≦a.cn
快速转置算法如下：
void FastTransMatrix(TMatrix a, TMatrix b)
{ int p , q , col , k ;
int num[MAX_SIZE] , copt[MAX_SIZE] ;
b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* 置三元组表b.data的行、列数和非0元素个数 */
if (b.tn==0) printf(“ The Matrix A=0\n” ) ;
else
{ for (col=1 ; col《=a.cn ; ++col) num[col]=0 ;
/* 向量num初始化为0 */
for (k=1 ; k《=a.tn ; ++k)
++num[ a.data[k].col] ;
/* 求原矩阵中每一列非0元素个数 */
for (cpot=1, col=2 ; col《=a.cn ; ++col)
cpot[col]=cpot[col-1]+num[col-1] ;
/* 求第col列中第一个非0元在b.data中的序号 */
for (p=1 ; p《=a.tn ; ++p)
{ col=a.data[p].col ; q=cpot[col] ;
b.data[q].row=a.data[p].col ;
b.data[q].col=a.data[p].row ;
b.data[q].value=a.data[p].value ;
++cpot[col] ; /*至关重要!!当本列中 */
}
}
}

稀疏矩阵三元组表示以及转置

visual studio下编译通过，测试结果正确，万一VC6编译不过请用TC2.0
//稀疏矩阵就是只记录非零元的位置和值，适合处理0比较多的矩阵
#include 《stdio.h》
#include 《malloc.h》

#define MAXSIZE 10

typedef struct node
{
int i,j,value; //i为行下标，j为列下标，value为该处的值
}NODE;
typedef struct mat
{
int mv,mc,mt; //mv为行数，mc为列数，mt为非零元个数
NODE v[MAXSIZE];
}MAT;
//view为输出稀疏矩阵
void view(MAT *a)
{
printf(“矩阵的三元组表示：\n“);
printf(“i j v\n“);
for(int k=0;k《a-》mt;k++)
printf(“%-6d%-6d%-6d\n“,a-》v[k].i,a-》v[k].j,a-》v[k].value);

}
//init为输入一个矩阵并存为稀疏矩阵
void init(MAT *a)
{
int k=0; //非零元的序号
//for(k=0;k《MAXSIZE;k++)
// a-》v[k].value=0; //先都初始化为零
a-》mt=0;
printf(“请输入行数和列数：\n“);
scanf(“%d%d“,&a-》mv,&a-》mc);
printf(“\n请依次输入矩阵的各个元素的值：\n“);
for(int m=1;m《=a-》mv;m++)
for(int n=1;n《=a-》mc;n++)
{
int t;
scanf(“%d“,&t);
//如果t为非零元，存入v[k]中
if(t!=0)
{
a-》v[k].i=m;
a-》v[k].j=n;
a-》v[k].value=t;
a-》mt++;
k++;
}
}
}
//矩阵a转置后存入矩阵b
void change(MAT *a,MAT *b)
{
b-》mv=a-》mc;
b-》mc=a-》mv;
b-》mt=a-》mt;
if(a-》mt)
{
int p=0,q=0;
for(int n=1;n《=a-》mc;n++)
for(int p=0;p《=a-》mc;p++)
{
if(a-》v[p].j==n) //v[p]是第n列的非零元
{
b-》v[q].i=a-》v[p].j;
b-》v[q].j=a-》v[p].i;
b-》v[q].value=a-》v[p].value;
q++;
}
}
}
}
void main()
{
MAT *a,*b;
b=(MAT *)malloc(sizeof(MAT));
a=(MAT *)malloc(sizeof(MAT));
init(a);
view(a);
change(a,b);
view(b);
}

稀疏矩阵的转置算法程序

template《class T》
SparseMatrix《T》 SparseMatrix《T》::Transpose()
{
SpareseMatrix《T》 b();
b.Rows=Cols;
b.Cols=Rows;
b.Trems=Terms;
if(Terms》0)
{
int i,k,CurrentB=0;
for(k=0;k《col;k++)
{
for(i=0;i《Terms;i++)
{
if(smArray[i].col==k)
{
b.smArray[CurrentB].row=k;
b.smArray[CurrentB].col=smArray[i].row;
b.smArray[CurrentB].value=smArray[i].value;
CurrentB++;
}
}
}
}
return b;
}