稀疏矩陣快速轉置演算法

⑴ 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;
}
另外,站長團上有產品團購,便宜有保證

⑵ 關於稀疏矩陣的數組存儲表示，轉置，輸出

#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 6.7\n其中2為行標，3為列標，6.7為數據元素"<<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]);
t.print();//輸出原矩陣
cout<<"轉制後的矩陣為：";
t.transpose();
}

⑶ 修改程序 利用三元組錶快速轉置矩陣

//重寫了，vc6下編譯通過
//作者：qmroom
//2008-11-049:00
//blog：http://blog.csdn.net/qmroom
//Email：qmroom#126.com#=@

#include"stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
usingnamespacestd;

structTrituple
{
introw;
intcol;
doublevalue;
Trituple():row(-1),col(-1),value(0){}
//friendostream&operator<<(ostream&os,constTrituple&tpl);
};

ostream&operator<<(ostream&os,constTrituple&tpl)
{
os<<tpl.row<<"\t"<<tpl.col<<"\t"<<tpl.value;
returnos;
}

structltTrituple
{
booloperator()(constTrituple&pos1,constTrituple&pos2)const
{
if(pos1.row!=pos2.row)
returnpos1.row<pos2.row;
returnpos1.col<pos2.col;
}
};

typedefvector<Trituple>VT;
typedefvector<Trituple>::const_iteratorIterator;

intmain(intargc,char*argv[])
{
Tritupletpl;
intnTemp;
VTvt;
Iteratoritr;

ifstreamfin("Trituple.txt");
while(!fin.eof())
{
fin>>tpl.row>>tpl.col>>tpl.value;
if(!fin.eof())
vt.push_back(tpl);
}
fin.close();

for(itr=vt.begin();itr!=vt.end();itr++)
{
nTemp=itr->row;
(int)(itr->row)=itr->col;
(int)(itr->col)=nTemp;
}

sort(vt.begin(),vt.end(),ltTrituple());
(vt.begin(),vt.end(),ostream_iterator<Trituple>(cout,"\n"));

return0;
}

⑷ C語言編寫稀疏矩陣的加，減，乘和轉置，要求用矩陣輸出

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define Max 12500
#define Elemtype int
typedef struct {
int i ,j ;
Elemtype e;
}Triple;
typedef struct {
Triple data[Max+1];
int mu,nu,tu;
}Tsmatrix;
int Createsmatrix(Tsmatrix &M)
{ int n;
cout<<"請輸入稀疏矩陣的元素個數n"<<endl;
cin>>n;
M.tu=n;
cout<<"請輸入稀疏矩陣的行數，列數："<<endl;
cin>>M.mu>>M.nu;
int i;
for(i=1;i<=n;i++){
cout<<"請輸入稀疏矩陣的行下標和列下標，及數據;"<<endl;
cin>>M.data[i].i>>M.data[i].j>>M.data[i].e ;
}
return 1;
}
int Transpose(Tsmatrix M , Tsmatrix &T)
{
T.mu=M.nu; T.nu=M.mu ; T.tu=M.tu;
if(T.tu){
int col , p , 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 1;
}
int Print(Tsmatrix M)
{

int i;int p=1;
{
for (i=1;i<=M.mu*M.nu;i++)
if(i==((M.data[p].i-1)*M.nu+M.data[p].j))
{
if(M.data[p].j==M.nu)
{ cout<<M.data[p].e<<endl; p++;}
else
{ cout<<M.data[p].e<<" "; p++;}
}
else if(i%M.nu==0) cout<<"0"<<endl;
else cout<<"0 ";
}
cout<<"\n"<<endl;
return 1;
}
int Addsmatrix(Tsmatrix a, Tsmatrix b, Tsmatrix &c)
{
int s=1,t=1,k=1; Elemtype temp;
if(a.mu!=b.mu||a.nu!=b.nu) return 0;
if(a.tu == 0) {c=b; return 1;}
if(b.tu==0) {c=a; return 1;}
if(a.tu==0 && b.tu==0) { c=a; return 1;}
while(!(s>a.tu && t>b.tu))
{
if(a.data[s].i>b.data[t].i)
{
c.data[k]=b.data[t];
k++ ;t++;
}
if(a.data[s].i<b.data[t].i)
{
c.data[k]=a.data[s];
k++ ;s++;
}
if(a.data[s].i==b.data[t].i)
{
if(a.data[s].j>b.data[t].j)
{
c.data[k]=b.data[t];
k++; t++;
}
if(a.data[s].j<b.data[t].j)
{
c.data[k]=a.data[s];
k++; s++;
}
if(a.data[s].j==b.data[t].j)
{
temp=a.data[s].e+b.data[t].e;
if(temp==0){s++;t++;}
else
{ c.data[k].e=temp;c.data[k].i=a.data[s].i;c.data[k].j=a.data[s].j;
s++;t++;k++;
}
}
}//if
if(s>a.tu&&t<=b.tu)
{
while(t<=b.tu)
{
c.data[k]=b.data[t];
k++; t++;
}
}
if(t>b.tu&&s<=a.tu)
{
while(s<=a.tu)
{
c.data[k]=a.data[s];
k++; s++;
}
}
}//while
c.tu=k-1; c.mu=a.mu; c.nu=a.nu;
}
return 1;int main()
{

Tsmatrix a,b,c;
Createsmatrix( a);
Createsmatrix( b);
Print(a);
Print(b);
Addsmatrix(a,b,c);
Print(c);
return 1;
}

⑸ 稀疏矩陣的轉置運算用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);
}

稀疏矩陣三元組轉置，你參考下

⑹ 採用基於稀疏矩陣的三元組壓縮存儲方法，實現m×n矩陣的快速轉置

#include<iostream>
using
namespace
std;
class
matrix
{
public:
int
data[100][100];
int
m,n;
};
typedef
int
spmatrix[100][3];
void
Init(matrix&
mx);//稀疏矩陣初始化
void
SpmDisplay(spmatrix
spm);//顯示三元組表示的矩陣
void
Compressmatrix(matrix
A,spmatrix
B);//將稀疏矩陣轉換為三元組矩陣
void
Transpmatrix(spmatrix
B,spmatrix&
C);//將三元組矩陣轉置
int
main()
{
matrix
mx;
spmatrix
spm1,spm2;
//矩陣初始化
Init(mx);
//矩陣轉為三元組
Compressmatrix(mx,spm1);
//顯示三元組矩陣
SpmDisplay(spm1);
//將三元組轉置存放到spm2中
Transpmatrix(spm1,spm2);
//顯示轉置後的三元組
SpmDisplay(spm2);
return
0;
}