Ⅰ 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下調試皆可通過