稀疏矩陣轉置演算法
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;
}
}