稀疏矩阵转置算法
A. 稀疏矩阵与转置算法
#include<stdio.h>
#include<stdlib.h>
typedefstruct{
introw;
intcol;
intdata;
}xishu;//存储稀疏矩阵的结构(行，列，值)
#defineMAX_COL10
//staticvoidtranspose(xishua[],xishub[]);//普通算法
staticvoidfasttranspose(xishua[],xishub[]);//改进的算法
staticvoidcreate(inta[][6],intm,intn,xishub[],int*count);
staticvoidprint(int*count,xishua[]);
intmain(intargc,char**argv)
{
inta[6][6]={{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}};
xishub[10],c[10];
intcount=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(" beforetranpose ");
print(&count,b);//打印建立好的稀疏矩阵
//transpose(b,c);
fasttranspose(b,c);//建立转置矩阵
printf(" aftertranspos ");
print(&count,c);//打印转置矩阵
exit(0);
}
staticvoidprint(int*count,xishua[])
{
intk;
for(k=1;k<=*count;k++){
printf("%d %d %d ",a[k].row,a[k].col,a[k].data);
}
}
staticvoidcreate(inta[][6],intm,intn,xishub[],int*count)
{
inti,j;
*count=0;
b[0].row=m;
b[0].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[0].data=*count;
}
/***
staticvoidtranspose(xishua[],xishub[])
{
//该算法的时间代价为O(a[0].data*a[0].data)
intcount=0;
inti,col;
b[0].row=a[0].col;
b[0].col=a[0].row;
b[0].data=a[0].data;
printf("%d,%d,%d ",b[0].row,b[0].col,b[0].data);
printf("%d,%d,%d ",a[0].row,a[0].col,a[0].data);
for(col=0;col<a[0].col;col++){
for(i=1;i<=a[0].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;
}
}
}
}
***/
staticvoidfasttranspose(xishua[],xishub[])
{
//改进的算法，该算法的时间代价为O(a[0].col+a[0].data)
inti,pos;
introw_num[MAX_COL];
intstart_pos[MAX_COL];
b[0].row=a[0].col;
b[0].col=a[0].row;
b[0].data=a[0].data;
for(i=0;i<a[0].col;i++){
row_num[i]=0;
}
for(i=1;i<=a[0].data;i++){
row_num[a[i].col]++;
}
start_pos[0]=1;
for(i=1;i<a[0].col;i++){
start_pos[i]=start_pos[i-1]+row_num[i-1];
}
for(i=1;i<=a[0].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;
}
}
B. 稀疏矩阵的转置运算用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[0]未用
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[50]; //num[col]表示矩阵M中第col列中非零元个数
int cpot[50]; //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]=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下调试皆可通过
C. 稀疏矩阵快速转置
#define MAXSIZE 12500;
分号去掉
D. 稀疏矩阵一般的转置法
1、数据结构还没有学,但知道一点点思想. 三元组应该是用x,y来记录数在矩阵中的位置,z记录数的值. 转置矩阵就是把x、y交换下位置就可以了. 2、C语言中数组是行排列,一行一行的数就可以了.A占用字节数是5*6*4 按列存储的话就一列一列的数,好像有个公式,我给忘记了,自己推一下吧,挺简单的. 3、随便一本数据结构课本上都应该有类似代码,找一下吧,就不帮你写了,这么简单^_^.
E. 帮帮忙!!!如何用C语言实现稀疏矩阵的转置
（C语言）稀疏矩阵的快速转置算法/*矩阵的快速转置*/
#include <stdio.h>
#include <stdlib.h>
#include <process.h>
#define MAXSIZE 200 /*矩阵中最大非零元的个数*/
typedef struct triple
{
int i; /*行标,本程序中从1开始的*/
int j; /*列标，本程序中从1开始的*/
int e; /*非零元*/
}Triple; /*三元组定义*/
typedef struct tabletype
{
int mu; /*矩阵的行数*/
int nu; /*列数*/
int tu; /*非零元个数*/
Triple data[MAXSIZE]; /*非零元的三元组表,本程序中是从data[1]开始使用的*/
}Tabletype; /*三元组线性表*/
/*以下为函数声明，注意和书本上的参数类型不同，我用的形参全为指针*/
void CreatSMatrix(Tabletype *); /*生成矩阵*/
void DestroySMatrix(Tabletype *); /*销毁矩阵*/
void out_matrix(Tabletype *); /*打印 矩阵*/
int FastTransposeSMatrix(Tabletype *,Tabletype *); /*快速转置算法*/
int main( void ) /*主函数*/
{
char ch;
Tabletype a = {0,0,0,{0,0,0}}; /*初始化为0，便于输入数据时的无效检测*/
Tabletype b; /*声明矩阵b*/
while(1)
{
printf(" @@@@@@@@@@@@@@本程序的功能是实现稀疏矩阵的快速转置@@@@@@@@@@@@@@@\n");
printf(" @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
CreatSMatrix(&a);
printf("The source Matrix:\n");
out_matrix(&a);
if(FastTransposeSMatrix(&a,&b)) /*若a不为零矩阵则转置a，存入b中*/
{ printf("After TransposeSMatrix: \n");
out_matrix(&b);
}
else
{
printf("The matrix is zeros:\n");
out_matrix(&a);
}
/*以下为程序控制*/
printf("Input 'q' to quit and 'c' run again:");
do{
if((ch = getchar()) == 'q' || ch == 'Q')
{
DestroySMatrix(&a);
DestroySMatrix(&b);
exit(0);
}
}while((ch!='C') && (ch!='c'));
system("cls");
}
return 1;
}
void CreatSMatrix(Tabletype *a)
{
int i;
printf("请输入矩阵的行数、列数和非零元个数，用空格间隔:");
scanf("%d%d%d",&(a->mu),&(a->nu),&(a->tu));
for(i=1;i<= a->tu;)
{
printf("请输入矩阵中第%d个非零元（按行标、列标、值的顺序，空格间隔）:",i);
scanf("%d%d%d",&(a->data[i].i),&(a->data[i].j),&(a->data[i].e));
if(a->data[i].i < 1 || a->data[i].i > a->mu || a->data[i].j < 1 || a->data[i].j > a->nu) /*下标越界*/
{
printf("注意：下标越界输入数据无效!\n请重新输入:行标范围：1--%d,列标范围1--%d!!!\n",a->mu,a->nu);
continue;
}
if( ((a->data[i].i) < (a->data[i-1].i)) ||
(((a->data[i].i) == (a->data[i-1].i)) && ((a->data[i].j) <= (a->data[i-1].j)))) /*非按行顺序输入*/
{
printf("注意：输入数据无效!\n请按照按行存储的顺序输入数据!!!\n");
continue;
}
i++;
}
}
void DestroySMatrix(Tabletype *a)
{ /* 销毁稀疏矩阵a*/
(*a).mu=0;
(*a).nu=0;
(*a).tu=0;
}
void out_matrix(Tabletype *a) /* 打印矩阵*/
{
int i,j,k = 1;
for(i = 1 ;i <= a->mu; i++)
{
for(j = 1; j<= a->nu; j++)
{ /*判断是否为非零元*/
if((a->data[k].i == i)&&(a->data[k].j == j))
{
printf("%4d",a->data[k].e);
k++;
}
else
printf("%4d",0);
}
printf("\n");
}
}
int FastTransposeSMatrix(Tabletype *a,Tabletype *b)
{
int p,q,col;
int *num;
int *cpot;
b->mu = a->nu; /*原矩阵的行数为新矩阵的列数，原列数为新行数，非零元个数不变*/
b->nu = a->mu;
b->tu = a->tu;
num=(int *)malloc((b->nu+1)*sizeof(int)); /* 生成两个辅助数组*/
cpot=(int *)malloc((b->nu+1)*sizeof(int));
if(b->tu) /*若a不为零矩阵*/
{
for(col = 0;col <a->nu;col++) /*初始化矩阵a的每列中非零元的个数均为0*/
num[col] = 0;
for(col = 0; col <=a->tu ; col++)/*统计每列中非零元的个数*/
num[a->data[col].j]++;
cpot[1] = 1; /*确定每列中第一个非零元的位置*/
for(col = 2;col <= a->nu; col++)
cpot[col] = num[col-1]+cpot[col-1];
for(p = 1; p <= a->tu; p++) /*p为a-data的下标*/
{
col = a->data[p].j; /*交换元素*/
q = cpot[col];
b->data[q].i = a->data[p].j;
b->data[q].j = a->data[p].i;
b->data[q].e = a->data[p].e;
q++;
cpot[col]++;
}
free(num); /*释放两个辅助数组*/
free(cpot);
return 1; /*转置成功*/
}
else /*a为零矩阵*/
return 0;
F. 稀疏矩阵的转置算法程序
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;
}
G. 稀疏矩阵的转置算法有什么用
稀疏矩阵是某个固定值元素比较多的矩阵，使用三元组存储是为了减少存储该矩阵的存储空间，而其转置算法就是为了解决矩阵的基本转制功能。这个涉及线性数学，如果您对转置有什么需要了解的可以看看。矩阵可以解决很多的多项式问题，同时也是对图的一种描述方法，因此其转置功能作为矩阵的基本特性也就很重要。
H. 求稀疏矩阵快速转置算法及代码
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]=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[0]=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] ; /*至关重要!!当本列中 */
}
}
}
I. 哪位高手能给我一个稀疏矩阵的转置算法么急用！！！
此程序我做了测试没问题
编译软件（virtual c++ 6.0）望你能学习进步
#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#define MaxRows 100
#define MaxColumns 100
typedef int ElemType;
struct CrossNode
{
int row,col;
ElemType val;
CrossNode *down,*right;
};
struct CLMatrix
{
int m,n,t;
CrossNode *rv[MaxRows+1];
CrossNode *cv[MaxColumns+1];
};
void InitMatrix(CLMatrix &M)
{
M.m=0;M.n=0;M.t=0;
for(int i=1;i<=MaxRows;i++)
M.rv[i]=NULL;
for(i=1;i<=MaxColumns;i++)
M.cv[i]=NULL;
}
void InputMatrix(CLMatrix &M,int m,int n);
void OutputMatrix(CLMatrix &M,int m,int n);
void Transpose(CLMatrix &M,int m,int n);
void main()
{
CLMatrix Q,P,N;
InitMatrix(Q);
InitMatrix(P);
InitMatrix(N);
cout<<"请您输入矩阵的行数与列数：";
int m,n;
cin>>m>>n;
cout<<"请以三元组的形式进行输入:"<<endl;
InputMatrix(Q,m,n);
cout<<"您输入的稀疏矩阵为："<<endl;
OutputMatrix(Q,m,n);
cout<<"转置后的稀疏矩阵为："<<endl;
Transpose(Q,m,n);
}
void InputMatrix(CLMatrix &M,int m,int n)
{
M.m=m;M.n=n;
int row,col,val;
int k=0;
cin>>row>>col>>val;
while(row!=0)
{
k++;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr->row=row;
newptr->col=col;
newptr->val=val;
newptr->down=newptr->right=NULL;
cp=M.rv[row];
if(cp==NULL)
M.rv[row]=newptr;
else
{
while(cp->right!=NULL)
cp=cp->right;
cp->right=newptr;
}
cp=M.cv[col];
if(cp==NULL)
M.cv[col]=newptr;
else
{
while(cp->down!=NULL)
cp=cp->down;
cp->down=newptr;
}
cin>>row>>col>>val;
}
M.t=k;
}
void Transpose(CLMatrix &M,int m,int n)
{
CLMatrix S;
InitMatrix(S);
S.m=M.m;S.n=M.n;
for(int i=1;i<=S.m;i++)
{
for(int j=1;j<=S.n;j++)
{
int val=0;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr->row=i;
newptr->col=j;
newptr->val=val;
newptr->down=newptr->right=NULL;
cp=S.rv[i];
if(cp==NULL)
S.rv[i]=newptr;
else
{
while(cp->right!=NULL)
cp=cp->right;
cp->right=newptr;
}
cp=S.cv[j];
if(cp==NULL)
S.cv[j]=newptr;
else
{
while(cp->down!=NULL)
cp=cp->down;
cp->down=newptr;
}
}
}
for(i=1;i<=M.m;i++)
{
CrossNode *sp1=S.rv[i];
CrossNode *mp1=M.rv[i];
while(mp1!=NULL)
{
while(sp1->col<mp1->col)
sp1=sp1->right;
sp1->val=mp1->val;
mp1=mp1->right;
}
}
for(int x=1;x<=S.m;x++)
{
while(S.cv[x]!=NULL)
{
cout<<setw(4)<<S.cv[x]->val;
S.cv[x]=S.cv[x]->down;
}
cout<<endl;
}
}
void OutputMatrix(CLMatrix &M,int m,int n)
{
CLMatrix S;
InitMatrix(S);
S.m=M.m;S.n=M.n;
for(int i=1;i<=S.m;i++)
{
for(int j=1;j<=S.n;j++)
{
int val=0;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr->row=i;
newptr->col=j;
newptr->val=val;
newptr->down=newptr->right=NULL;
cp=S.rv[i];
if(cp==NULL)
S.rv[i]=newptr;
else
{
while(cp->right!=NULL)
cp=cp->right;
cp->right=newptr;
}
cp=S.cv[j];
if(cp==NULL)
S.cv[j]=newptr;
else
{
while(cp->down!=NULL)
cp=cp->down;
cp->down=newptr;
}
}
}
for(i=1;i<=M.m;i++)
{
CrossNode *sp1=S.rv[i];
CrossNode *mp1=M.rv[i];
while(mp1!=NULL)
{
while(sp1->col<mp1->col)
sp1=sp1->right;
sp1->val=mp1->val;
mp1=mp1->right;
}
}
for(int x=1;x<=S.m;x++)
{
while(S.rv[x]!=NULL)
{
cout<<setw(4)<<S.rv[x]->val;
S.rv[x]=S.rv[x]->right;
}
cout<<endl;
}
}