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

//普通转置算法
//时间复杂度:O(tm);t是非零元个数，m是列数。每转置一列需要扫描全部三元数组
#include "stdafxh"
#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 "stdafxh"
#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]=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;
}

m是行数，n是列数，t是矩阵非零元素的个数，将矩阵a快速转置为b矩阵。
if(at!=0)
先判断a矩阵中非0元素的个数是不为0的，这样就可以进行下面的快速转置。
for(col=1; col<at; col++)
for(k=0;k<at;k++)num[adata[k]j]++;
这是统计a矩阵中每列的三元组的个数。从列开始，
pot[1]=0
for(col=2;col<an;col++) pot[col]=pot[col-1]+mun[col-1];
计算pot数组,pot[]是指b矩阵中每行第一个三元组的下标
最后的一个for循环是快速转置，将a矩阵的行转为b矩阵的列，a矩阵的列转为b矩阵的行，原来矩阵中的非0元素也做相应的调整。

矩阵加减注意格式
#include <stdioh>
#define maxsize 20
typedef int data;
typedef struct
{
int i,j;
data v;
}mat;
typedef struct
{
int m,n,t;
mat dtt[maxsize+1];
}matrix;
matrix a,b,c;
void transmat(matrix a,matrix b)
{
int p,q,col;
b->m=an;
b->n=am;
b->t=at;
if(at!=0)
{
q=1;
for(col=1;col<=an;col++)
for(p=1;p<=at;p++)
if(adtt[p]j==col)
{
b->dtt[q]j=adtt[p]i;
b->dtt[q]i=adtt[p]j;
b->dtt[q]v=adtt[p]v;
q++;
}
}
}
void creat(matrix x)
{
printf("\nn,m,t=");
scanf("%d,%d,%d",&x->n,&x->m,&x->t);
for(int i=1;i<=x->t;i++)
{
printf("\ni,j,v=");
scanf("%d,%d,%d",&x->dtt[i]i,&x->dtt[i]j,&x->dtt[i]v);
}
}
void mout(matrix x)
{
printf("\nn,m,t=");
printf("%d,%d,%d\n",xn,xm,xt);
for(int i=1;i<=xt;i++)
{
printf("\ni,j,v=");
printf("%d,%d,%d\n",xdtt[i]i,xdtt[i]j,xdtt[i]v);
}
}
void jiajian(matrix x,matrix y,matrix b)
{
int t;
printf("\n1加");
printf("\n2减\n\n");
scanf("%d",&t);
if(t==1)
{
int s=0,j=1,z=1;
b->m=xm;
b->n=xn;
for(int i=1;i<=b->n;i++)
{
for(;j<=xt,z<=yt;)
{
if(xdtt[j]i!=i&&ydtt[z]i!=i)
{
break;
}
else if(xdtt[j]i!=i)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=ydtt[z]v;
z++;
}
else if(ydtt[z]i!=i)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=xdtt[j]j;
b->dtt[s]v=xdtt[j]v;
j++;
}
else if(xdtt[j]j>ydtt[z]j)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=ydtt[z]v;
z++;
}
else if(xdtt[j]j==ydtt[z]j)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=ydtt[z]v+xdtt[j]v;
z++;
j++;
}
else if(xdtt[j]j<ydtt[z]j)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=xdtt[j]j;
b->dtt[s]v=xdtt[j]v;
j++;
}
}
}
b->t=s;
}
else if(t==2)
{
int s=0,j=1,z=1;
b->m=xm;
b->n=xn;
for(int i=1;i<=b->n;i++)
{
for(;j<=xt,z<=yt;)
{
if(xdtt[j]i!=i&&ydtt[z]i!=i)
{
break;
}
else if(xdtt[j]i!=i)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=-ydtt[z]v;
z++;
}
else if(ydtt[z]i!=i)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=xdtt[j]j;
b->dtt[s]v=xdtt[j]v;
j++;
}
else if(xdtt[j]j>ydtt[z]j)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=-ydtt[z]v;
z++;
}
else if(xdtt[j]j==ydtt[z]j)
{
if(xdtt[j]v-ydtt[z]v!=0)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=ydtt[z]j;
b->dtt[s]v=xdtt[j]v-ydtt[z]v;
}
z++;
j++;
}
else if(xdtt[j]j<ydtt[z]j)
{
s++;
b->dtt[s]i=i;
b->dtt[s]j=xdtt[j]j;
b->dtt[s]v=xdtt[j]v;
j++;
}
}
}
b->t=s;
}
}
int main(int argc, char argv[])
{
printf("1创建\n");
printf("2转置\n");
printf("3矩阵加减\n");
printf("4退出\n");
printf("\n\n\n");
int t;
while(~scanf("%d",&t))
{
if(t==1)
{
creat(&a);
}
else if(t==2)
{
transmat(a,&b);
mout(b);
}
else if(t==3)
{
creat(&c);
jiajian(a,c,&b);
mout(b);
}
else if(t==4)
break;
printf("\n\n\n");
printf("1创建\n");
printf("2转置\n");
printf("3矩阵加减\n");
printf("4退出\n");
printf("\n\n\n");
}
return 0;
}

#include<iostream>
using std::cout;
using std::cin;
using std::endl;
struct node
{
int r;//行标
int c;//列标
double dat;//数据
};
class triple
{
private:
int row;//行数
int col;//列数
int num;//非零个数
node ptr;//存放数组的首地址
public:
triple(int co,int ro,int nu):col(co),row(ro),num(nu)
{
ptr=new node[num];//分配num，盛放num个元素
cout<<"请输入"<<num<<"个三元组元素\n"<<"格式为： 2 3 67\n其中2为行标，3为列标，67为数据元素"<<endl;
for(int i=0;i<num;i++)
{
cin>>ptr[i]r;
cin>>ptr[i]c;
cin>>ptr[i]dat;
}
}
~triple(){delete[]ptr;}
void print()
{
int flag=ptr[0]r;
cout<<"第"<<flag<<"行元素为：";
for(int i=0;i<num;i++)
{
if(ptr[i]r!=flag)
{
cout<<"\n";
flag=ptr[i]r;
cout<<endl;
cout<<"第"<<flag<<"行元素为：";
}
cout<<"("<<ptr[i]r<<","<<ptr[i]c<<","<<ptr[i]dat<<")  ";
}
}
void transpose()
{
int flag=0;
for(int i=1;i<=col;i++)
{
for(int j=0;j<num;j++)
{
if(ptr[j]c==i)
{
if(flag!=ptr[j]c)
{
flag=ptr[j]c;
cout<<"\n第"<<ptr[j]c<<"行为：";
}
cout<<"("<<ptr[j]c<<","<<ptr[j]r<<","<<ptr[j]dat<<")  ";
}
}
}
}
};
void main()
{
cout<<"请输入数组的行列和元素个数：\n";
int a[3];
for(int i=0;i<3;i++)
{
cin>>a[i];
}
triple t(a[0],a[1],a[2]);
tprint();//输出原矩阵
cout<<"转制后的矩阵为：";
ttranspose();
}

我刚写了一个稀疏矩阵的代码，如下
#include <iostream>
#include <iomanip>
using namespace std;
template<class T>
//三元组
struct Trituple
{
int row;
int col;
T val;
};
//稀疏矩阵声明
template<class T>
class SparseMatrix
{
public:
SparseMatrix(int maxt=100);
~SparseMatrix();
bool TransposeTo(SparseMatrix &);
bool AddTo(const SparseMatrix&);
bool TransposeTo_Faster(SparseMatrix&);
void Input();
void Output();
private:
Trituple<T> data;
int rows,cols,terms;
int maxterms;
};
template<class T>
SparseMatrix<T>::SparseMatrix(int maxt)
{
maxterms=maxt;
data=new Trituple<T>[maxterms];
terms=rows=cols=0;
}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{
if (data!=NULL)
{
delete[] data;
}
}
//普通转置
template<class T>
bool SparseMatrix<T>::TransposeTo(SparseMatrix &B)
{
if (terms>Bmaxterms)
{
return false;
}
Brows=cols;
Bcols=rows;
Bterms=terms;
if (terms>0)
{
int p=0;
for (int j=1;j<=cols;j++)
{
for (int k=0;k<terms;k++)
{
if (data[k]col==j)
{
Bdata[p]row=j;
Bdata[p]col=data[k]row;
Bdata[p]val=data[k]val;
p++;
}
}
}
}
return true;
}
//快速转置
template<class T>
bool SparseMatrix<T>::TransposeTo_Faster(SparseMatrix& B)
{
if (terms>Bmaxterms)
{
return false;
}
Brows=cols;
Bcols=rows;
Bterms=terms;
if (terms>0)
{
int num,cpot;
num=new int[cols];
cpot=new int[cols];
for (int j=0;j<cols;j++)
{
num[j]=0;
}
for (int k=0;k<terms;k++)
{
num[data[k]col-1]++;
}
//求出B中每一行的起始下标cpot[]
cpot[0]=0;
for (int j=1;j<cols;j++)
{
cpot[j]=cpot[j-1]+num[j-1];
}
//执行转置 *** 作
for (int p,k=0;k<terms;k++)
{
p=cpot[data[k]col-1]++;
Bdata[p]row=data[k]col;
Bdata[p]col=data[k]row;
Bdata[p]val=data[k]val;
}
delete[] num;
delete[] cpot;
}
return true;
}
template<class T>
void SparseMatrix<T>::Input()
{
cout<<"intput the matrix' row:";
int row1;
cin>>row1;
cout<<"intput the matrix' col:";
int col1;
cin>>col1;
cout<<"input "<<row1<<""<<col1<<" matrix"<<endl;
int number;
rows=row1;
cols=col1;
for (int i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
{
cin>>number;
if (number!=0)
{
data[terms]row=i+1;
data[terms]col=j+1;
data[terms]val=number;
terms++;
}
}
}
}
template<class T> //输出好看，但是违背了最初的原则
void SparseMatrix<T>::Output()
{
T tempArray=new T[rows];
for (int i1=0;i1<rows;i1++)
{
tempArray[i1]=new int[cols];
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
tempArray[j][k]=0;
}
}
for (int i=0;i<terms;i++)
{
tempArray[data[i]row-1][data[i]col-1]=data[i]val;
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
cout<<setw(4)<<tempArray[j][k];
}
cout<<endl;
}
for (int l=0;l<rows;l++)
{
delete[] tempArray[l];
}
delete tempArray;
cout<<endl;
}
template<class T>
bool SparseMatrix<T>::AddTo(const SparseMatrix& B)
{
if (rows!=Brows||cols!=Bcols)
{
return false;
}
bool flag=false;
int tempTerms=terms;
for (int i=0;i<Bterms;i++)
{
flag=false;
for (int j=0;j<tempTerms;j++)
{
if (data[j]col==Bdata[i]col&&data[j]row==Bdata[i]row)
{
data[j]val+=Bdata[i]val;
flag=true;
}
}
if (flag==false)
{
data[++terms-1]col=Bdata[i]col; //数组下标 *** 作注意事项
data[terms-1]row=Bdata[i]row;
data[terms-1]val=Bdata[i]val;
}
}
return true;
}
int main()
{
cout<<"此程序演示稀疏矩阵的普通转置和快速转置 *** 作"<<endl;
SparseMatrix<int> sm(50);
SparseMatrix<int> sm1(50);
SparseMatrix<int> sm2(50);
smInput();
cout<<"sm is"<<endl;
smOutput();
smTransposeTo(sm1);
cout<<"Transposition of sm is "<<endl;
sm1Output();
smTransposeTo_Faster(sm2);
cout<<"Transposition of sm is "<<endl;
sm2Output();
SparseMatrix<int> sm3;
cout<<"input a new matrix"<<endl;
sm3Input();
cout<<"sm3 is"<<endl;
sm3Output();
if(smAddTo(sm3))
{
cout<<"after adding sm3 ,sm is"<<endl;
smOutput();
}
else
cout<<"the two matrix can't add"<<endl;
cout<<"Good job!"<<endl;
system("pause");
return 0;
}

#include <stdioh>
#include <stdlibh>
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[][6], int m, int n, xishu b[], int count);
static void print(int count, xishu a[]);
int main(int argc, char argv)
{
        int a[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} };
        xishu b[10], c[10];
        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[][6], int m, int n, xishu b[], int count)
{
        int i, 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;
}
/
static void transpose(xishu a[], xishu b[])
{
//该算法的时间代价为O(a[0]dataa[0]data)
        int count = 0;
        int i, col;
        b[0]row = a[0]col;
        b[0]col = a[0]row;
        b[0]data = a[0]data;
        printf("%d, %d, %d\n", b[0]row, b[0]col, b[0]data);
        printf("%d, %d, %d\n", 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;
                        }
                }
        }
}
/ 
static void fasttranspose(xishu a[], xishu b[])
{
//改进的算法，该算法的时间代价为O(a[0]col+a[0]data)
        int i, pos;
        int row_num[MAX_COL];
        int start_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;
        }
}

---