Ⅰ c++数据结构 稀疏矩阵转置实验
struct elm3 {
int row,col;
double d;
elm3():row(0),col(0),d(0){};
elm3(int i,int j,double data):row(i),col(j),d(data){};
};
template list<elm3 > parseMat;
parseMat m;
elem3 e;
int a[][4]={{2,0,0,1},{0,2,0,0},{1,0,3,0},{4,2,0,2}};
m.push_back(elm3(m,n,a[i][j]);
for(i=0;i<row;i++)
for(j=0;j<col;j++)
{
if(a[i][j]) m.push_back(elm3(i,j,a[i][j]);
};
paraseMat &SortMat(parseMat & x )
{
elm3 e=*x.begin();
x.erase(x.begin());
sort(x.begin(),x.end());
x.insert(x.begin(),e);
}
paraseMat Trans(const parseMat & x )
{
parseMat y;
parseMat::interator iter =x.begin() ;
y.push_back(elm3(iter->col,iter->row,0);
iter++;
while (iter!=x.end())
{
y.push_back(elm3(iter->col,iter->row,iter->d));
iter++;
}
SortMat(x);
}
void PrintMatrix(const parseMat & x,ostream os&=cout)
{
int i,j;
int m,n,d;
parseMat::interator iter =x.begin() ;
m =iter->row,n=iter->col;
iter++;
for(i=0;i<m;i++)
{
if(iter ==x.end() || iter->row > i )
for (j=0;j<n;j++)
{
os <<fixed<<setw(8)<<setprecision(2)<< 0 ;
}
else
{
for (j=0;j<n;j++)
{
if( iter!=x.end() && iter->row ==i && iter->col==j )
{
os <<fixed<<setw(8)<<setprecision(2)<<iter->d;
iter++;
}
else {os <<fixed<<setw(8)<<setprecision(2)<< 0 ;}
}
} os <endl;
}
}
Ⅱ 稀疏矩阵的转置运算用C语言
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
// c5-2.h 稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE 100 // 非零元个数的最大值
struct Triple
{
int i,j; // 行下标,列下标
ElemType e; //档判 非零元素值
};
struct TSMatrix
{
Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
};
// bo5-2.cpp 三元组稀疏矩阵的基本操作,包括算法5.1(9个)
Status CreateSMatrix(TSMatrix &M)
{ // 创建行慧改稀疏矩阵M
int i,m,n;
ElemType e;
Status k;
printf("请输入矩阵的行数,列数,非零元素数：");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
M.data[0].i=0; // 为以下比较顺序做准备
for(i=1;i<=M.tu;i++)
{
do
{
printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,M.mu,M.nu);
scanf("%d,%d,%d",&m,&n,&e);
k=0;
if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围
k=1;
if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错
k=1;
}while(k);
M.data[i].i=m;
M.data[i].j=n;
M.data[i].e=e;
}
return OK;
}
void DestroySMatrix(TSMatrix &M)
{ /碧闷/ 销毁稀疏矩阵M
M.mu=0;
M.nu=0;
M.tu=0;
}
void PrintSMatrix(TSMatrix M)
{ // 输出稀疏矩阵M
int i;
printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
printf("行 列 元素值\n");
for(i=1;i<=M.tu;i++)
printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
}
Status CopySMatrix(TSMatrix M,TSMatrix &T)
{ // 由稀疏矩阵M复制得到T
T=M;
return OK;
}
int comp(int c1,int c2) // 另加
{ // AddSMatrix函数要用到
int i;
if(c1<c2)
i=1;
else if(c1==c2)
i=0;
else
i=-1;
return i;
}
Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的和Q=M+N
Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;
if(M.mu!=N.mu)
return ERROR;
if(M.nu!=N.nu)
return ERROR;
Q.mu=M.mu;
Q.nu=M.nu;
Mp=&M.data[1]; // Mp的初值指向矩阵M的非零元素首地址
Np=&N.data[1]; // Np的初值指向矩阵N的非零元素首地址
Me=&M.data[M.tu]; // Me指向矩阵M的非零元素尾地址
Ne=&N.data[N.tu]; // Ne指向矩阵N的非零元素尾地址
Qh=Qe=Q.data; // Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址
while(Mp<=Me&&Np<=Ne)
{
Qe++;
switch(comp(Mp->i,Np->i))
{
case 1: *Qe=*Mp;
Mp++;
break;
case 0: switch(comp(Mp->j,Np->j)) // M、N矩阵当前非零元素的行相等,继续比较列
{
case 1: *Qe=*Mp;
Mp++;
break;
case 0: *Qe=*Mp;
Qe->e+=Np->e;
if(!Qe->e) // 元素值为0，不存入压缩矩阵
Qe--;
Mp++;
Np++;
break;
case -1: *Qe=*Np;
Np++;
}
break;
case -1: *Qe=*Np;
Np++;
}
}
if(Mp>Me) // 矩阵M的元素全部处理完毕
while(Np<=Ne)
{
Qe++;
*Qe=*Np;
Np++;
}
if(Np>Ne) // 矩阵N的元素全部处理完毕
while(Mp<=Me)
{
Qe++;
*Qe=*Mp;
Mp++;
}
Q.tu=Qe-Qh; // 矩阵Q的非零元素个数
return OK;
}
Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的差Q=M-N
int i;
for(i=1;i<=N.tu;i++)
N.data[i].e*=-1;
AddSMatrix(M,N,Q);
return OK;
}
Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的乘积Q=M*N
int i,j,h=M.mu,l=N.nu,Qn=0;
// h,l分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数，初值为0
ElemType *Qe;
if(M.nu!=N.mu)
return ERROR;
Q.mu=M.mu;
Q.nu=N.nu;
Qe=(ElemType *)malloc(h*l*sizeof(ElemType)); // Qe为矩阵Q的临时数组
// 矩阵Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为0
for(i=0;i<h*l;i++)
*(Qe+i)=0; // 赋初值0
for(i=1;i<=M.tu;i++) // 矩阵元素相乘，结果累加到Qe
for(j=1;j<=N.tu;j++)
if(M.data[i].j==N.data[j].i)
*(Qe+(M.data[i].i-1)*l+N.data[j].j-1)+=M.data[i].e*N.data[j].e;
for(i=1;i<=M.mu;i++)
for(j=1;j<=N.nu;j++)
if(*(Qe+(i-1)*l+j-1)!=0)
{
Qn++;
Q.data[Qn].e=*(Qe+(i-1)*l+j-1);
Q.data[Qn].i=i;
Q.data[Qn].j=j;
}
free(Qe);
Q.tu=Qn;
return OK;
}
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 求稀疏矩阵M的转置矩阵T。算法5.1
int p,q,col;
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.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;
}
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 快速求稀疏矩阵M的转置矩阵T。算法5.2
int p,q,t,col,*num,*cpot;
num=(int *)malloc((M.nu+1)*sizeof(int)); // 生成数组（[0]不用）
cpot=(int *)malloc((M.nu+1)*sizeof(int)); // 生成数组（[0]不用）
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
for(col=1;col<=M.nu;++col)
num[col]=0; // 设初值
for(t=1;t<=M.tu;++t) // 求M中每一列含非零元素个数
++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col) // 求第col列中第一个非零元在T.data中的序号
cpot[col]=cpot[col-1]+num[col-1];
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];
}
}
free(num);
free(cpot);
return OK;
}
void main()
{
TSMatrix A,B;
printf("创建矩阵A: ");
CreateSMatrix(A);
PrintSMatrix(A);
FastTransposeSMatrix(A,B);
printf("矩阵B(A的快速转置): ");
PrintSMatrix(B);
DestroySMatrix(A);
DestroySMatrix(B);
}
稀疏矩阵三元组转置，你参考下
Ⅲ 稀疏矩阵的转置，要求如下：（C语言编写代码）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxsize 12500
int num[maxsize]={0},copt[maxsize]={0};
typedef struct
{
int i,j;
int e;
}Triple;
struct TSMatrix
{
Triple data[maxsize+1];
int mu,nu,tu;
}M,T;
int main()
{
int i=1,j,k,col;
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
copt[1]=1;
while(scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e)!=EOF)
{
num[M.data[i].j]++;
i++;
}
printf("num:%d,",num[1]);
for(col=2;col<=M.nu;col++)
{
copt[col]=copt[col-1]+num[col-1];
printf("%d,",num[col]);
}
printf("\n");
printf("cpot:");
for(i=1;i<=M.nu;i++)
printf("%d,",copt[i]);
printf("\n");
for(j=1;j<=M.tu;j++)
{
col=M.data[j].j;
k=copt[col];
T.data[k].i=M.data[j].j;
T.data[k].j=M.data[j].i;
T.data[k].e=M.data[j].e;
copt[col]++;
}
for(i=1;i<=M.tu;i++)
printf("%d,%d,%d\n",T.data[i].i,T.data[i].j,T.data[i].e);
return 0;
}
Ⅳ 稀疏矩阵三元组表示以及转置
#include <stdio.h>
#define MAXSIZE 20 /*矩阵中最大非零元的个数*/
#define M 5
#define N 5
typedef struct triple
{
int r; /*行标,本程序中从1开始的*/
int c; /*列标,本程序中从1开始的*/
int d; /*非零元*/
}Triple; /*三元组定义*/
typedef struct
{
int rows; /*矩阵的行数*/
int cols; /*列数*/
int nums; /*非零元个数*/
Triple data[MAXSIZE+1]; /*非零元的三元组表,*/
}TSMatrix; /*三元组线性表*/
int TransposeSMatrix(TSMatrix *a,TSMatrix *b)
{
int p,q,col;
b->rows = a->cols; /*原矩阵的行数为新矩阵的列数，愿列数为新行数，非零元个数不变*/
b->cols = a->rows;
b->nums = a->nums;
if(b->nums) /*若a不为零矩阵*/
{ q = 0; /*b->data下标*/
for(col = 1; col < a->cols; col++)
for(p = 0;p < a->nums;p++) /*p为a->data的下标*/
if(col == a->data[p].c) /*按b->data[q]中的列标对a->data[p]进行扫描*/
{
b->data[q].r = a->data[p].c;
b->data[q].c = a->data[p].r;
b->data[q].d = a->data[p].d;
q++;
}
return 1;
}
else /*a为零矩阵*/
return 0;
}
void FastTransposeSMatrix(TSMatrix t,TSMatrix &tb)
{ int p,q=0,v; /*q为tb.data的下标*/
tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;
if (t.nums!=0)
{ for (v=0;v<t.cols;v++)
for (p=0;p<t.nums;p++) /*p为t.data的下标*/
if (t.data[p].c==v)
{ tb.data[q].r=t.data[p].c;
tb.data[q].c=t.data[p].r;
tb.data[q].d=t.data[p].d;
q++;
}
}
}
void DispMat(TSMatrix t)
{ int i;
if (t.nums<=0) return;
printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);
printf(" -------------------------------\n");
for (i=0;i<t.nums;i++)
printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,
t.data[i].d);
}
void display_matrix(TSMatrix *a) /* 打印矩阵*/
{ int r,c,d = 0;
for(r = 1 ;r <= a->rows; r++)
{
for(c = 1; c<= a->cols; c++)
{ /*判断是否为非零元*/
if((a->data[d].r == r)&&(a->data[d].c == c))
{ printf("%4d",a->data[d].d); d++; }
else
printf("%4d",0);
}
printf("\n");
}
}
int main()
{/*源矩阵a*/
TSMatrix a= {6,7,8,{ {1,2,12},{1,3,9},{3,1,-3},{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7} }};
TSMatrix b; /*声明矩阵b*/
printf("The source Matrix:\n");
DispMat(a);
printf(" ============矩阵原型============\n");display_matrix(&a);
FastTransposeSMatrix(a,b);
printf("After FastTransposeSMatrix(快速转换): \n");
DispMat(b);
printf(" ============矩阵原型============\n");display_matrix(&b);
TransposeSMatrix(&b,&a);
printf("After TransposeSMatrix（普通转换）: \n");
DispMat(a);
printf(" ============矩阵原型============\n");display_matrix(&a);
}
Ⅳ c++ 十字链表实现稀疏矩阵的转置
mplate <class Type>SparseMatrix<Type>
SparseMatrix<Type>::SparseMatrix::FastTranspose()
{
int *RowSize = new int[Cols]; /渣瞎/ 统计各列孙漏非零元素个数
int *RowStart = new int[Cols]; // 预计转置后各行存如凯空放位置
SparseMatrix b; // 存放转置结果
b.Rows = cols; b.cols = Rows; b.Terms = Terms;
if (Terms>0) //nonzero matrix
{
for (int i=0;i<Cols;i++) RowSize[i] = 0; //initialize
for (i=0;i<terms;i++) RowSize[smArray[i].col]++;
//RowStart[i]=starting position of row i in b
RowStart[0]=0;
for (i=1;i<Cols;i++) RowStart[i] = RowStart[i-1]+
RowSize[i-1];
for (i=0;i<Terms;i++) //move from a to b
{
int j=Rowstart[smArray[i].col];
b.smArray[j].row=smArray[i].col;
b.smArray[j].col= smArray[i].row;
b.smArray[j].value= smArray[i].value;
RowStart[smArray[i].col]++;
} //end of for
}
delete [ ]Rowsize;
delete [ ]Rowstart;
return b;
}
另外,站长团上有产品团购,便宜有保证
Ⅵ 求稀疏矩阵快速转置算法及代码
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] ; /*至关重要!!当本列中 */
}
}
}
Ⅶ 稀疏矩阵的转置运算用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下调试皆可通过