c語言稀疏矩陣轉置矩陣
㈠ 求一個C++的稀疏矩陣類，要求能實現加法，減法和乘法，正常輸出。還能轉置。。。急！！！急！！！
#include <iostream.>
using namespace std;
const int MAXSIZE=100; // 定義非零元素的最多個數
const int MAXROW=10; // 定義數組的行數的最大值
typedef struct { // 定義三元組的元素
int i,j; //行數 列數
int e; //非零元的值
}Triple;
typedef struct { // 定義普通三元組對象
Triple data[MAXSIZE+1];
int a,b,c; //行數，列數，非零元個數
}TSMatrix;
typedef struct { // 定義帶鏈接信息的三元組對象
Triple data[MAXSIZE+2];
int rpos[MAXROW+1];
int a,b,c;
}RLSMatrix;
template <class P>
int shuru(P & T,int y){ //輸入矩陣，按三元組格式輸入
cout<<"輸入稀疏矩陣的行，列和非零元素個數:"<<endl;
cin>>T.a>>T.b>>T.c;
cout<<"請輸出非零元素的位置和值:"<<endl;
int k=1;
for(;k<=T.c;k++)
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;
return 1;
}
template <class P>
void shuchu(P T){ // 輸出矩陣，按標准格式輸出
int m,n,k=1;
for(m=0;m<T.a;m++){
for(n=0;n<T.b;n++){
if((T.data[k].i-1)==m&&(T.data[k].j-1)==n){
cout.width(4);
cout<<T.data[k++].e;}
else{
cout.width(4); cout<<"0"; }
}
cout<<endl;
}
}
void zhuan( ) // 求矩陣的轉置矩陣
{
TSMatrix M,T; //定義預轉置的矩陣
shuru(M, 0); //輸入矩陣
int num[MAXROW+1];
int cpot[MAXROW+1]; // 構建輔助數組
int q,p,t;
T.c=M.c; T.a=M.b; T.b=M.a;
if(T.c){
for(int col=1;col<=M.c;col++) num[col]=0;
for(t=1;t<=M.c;t++) ++num[M.data[t].j];
cpot[1]=1;
for(int i=2;i<=M.b;i++) cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元組中出現的位置
for(p=1;p<=M.c;p++){
col=M.data[p].j; q=cpot[col];
T.data[q].i=col; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
cout<<"輸入稀疏矩陣的轉置矩陣為"<<endl;
shuchu(T);
}
void Count(RLSMatrix &T) // 求取每一行中非零元素在三元組中出現的位置
{
int num[MAXROW+1];
for(int col=1;col<=T.a;col++) num[col]=0;
for(col=1;col<=T.c;col++) ++num[T.data[col].i];
T.rpos[1]=1;
for(int i=2;i<=T.a;i++) T.rpos[i]=T.rpos[i-1]+num[i-1]; }
typedef struct OLNode // 定義十字鏈表元素
{
int i,j; //該非零元的行列下標
int e; //非零元值
struct OLNode *right,*down; // 該非零元所在行表和列表的後繼元素
}OLNode,*OLink; typedef struct // 定義十字鏈表對象結構體
{
OLink *rhead,*chead; //
int a,b,c; // 系數矩陣的行數，列數，和非零元素個數
}CrossList; void CreateSMatrix_OL(CrossList & M) // 創建十字鏈表
{
int x,y,m;
cout<<"請輸入稀疏矩陣的行，列，及非零元素個數"<<endl;
cin>>M.a>>M.b>>M.c;
if(!(M.rhead=(OLink*)malloc((M.a+1)*sizeof(OLink)))) exit(0);
if(!(M.chead=(OLink*)malloc((M.b+1)*sizeof(OLink)))) exit(0);
for(x=0;x<=M.a;x++)
M.rhead[x]=NULL; // 初始化各行，列頭指針，分別為NULL
for(x=0;x<=M.b;x++)
M.chead[x]=NULL;
cout<<"請按三元組的格式輸入數組："<<endl;
for(int i=1;i<=M.c;i++){
cin>>x>>y>>m; // 按任意順序輸入非零元，（普通三元組形式輸入）
OLink p,q;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，用來存儲輸入的新元素
p->i=x; p->j=y; p->e=m;
if(M.rhead[x]==NULL||M.rhead[x]->j>y){
p->right=M.rhead[x]; M.rhead[x]=p;
}
else{
for(q=M.rhead[x];(q->right)&&(q->right->j<y);q=q->right); // 查找節點在行表中的插入位置
p->right=q->right; q->right=p; // 完成行插入
}
if(M.chead[y]==NULL||M.chead[y]->i>x){
p->down=M.chead[y]; M.chead[y]=p;
}
else{
for(q=M.chead[y];(q->down)&&(q->down->i<x);q=q->down); // 查找節點在列表中的插入位置
p->down=q->down; q->down=p; // 完成列插入 }
}
} void shuchu(CrossList T){ // 輸出十字鏈表，用普通數組形式輸出
for(int i=1;i<=T.a;i++){
OLink p=T.rhead[i];
for(int j=1;j<=T.b;j++){
if((p)&&(j==p->j)){
cout<<p->e; p=p->right;
}
else
cout<<"0";
}
cout<<endl;
}
}
void chengfa() //矩陣的乘法
{
CrossList M,N; // 創建兩個十字鏈表對象，並初始化
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"輸入的兩稀疏矩陣的積為："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; //定義輔助指針，pa，pb分別為M,N當前比較的元素，pre為pa的前驅元素
for(int x=1;x<=M.b;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.a;k++){ // 對M的每一行進行操作
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb){ // 把N中此行的每個元素取出，
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，存儲N中取出的元素
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j){ // 當M此行已經檢查完或者pb因該放在pa前面
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){ // 進行列插入
M.chead[p->j]=p; p->down=NULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j){ // 如果此時的pb元素因該放在pa後面，則取以後的pa再來比較
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j){ // 如果pa，pb位於同一個位置上，則將值相加
pa->e *= pb->e;
if(!pa->e){ // 如果相加後的和為0，則刪除此節點，同時改變此元素坐在行，列的前驅元素的相應值
if(NULL==pre) // 修改行前驅元素值
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down; // 修改列前驅元素值
else
hl[p->j]->down=p->down;
free(p); pb=pb->right;
}
else{
pa=pa->right; pb=pb->right;
}
}
}
}
shuchu(M);
}
void jianfa() //矩陣的減法
{
CrossList M,N; // 創建兩個十字鏈表對象，並初始化
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"輸入的兩稀疏矩陣的差矩陣為："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; //定義輔助指針，pa，pb分別為M,N當前比較的元素，pre為pa的前驅元素
for(int x=1;x<=M.b;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.a;k++){ // 對M的每一行進行操作
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb){ // 把N中此行的每個元素取出，
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，存儲N中取出的元素
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j){ // 當M此行已經檢查完或者pb因該放在pa前面
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){ // 進行列插入
M.chead[p->j]=p; p->down=NULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j){ // 如果此時的pb元素因該放在pa後面，則取以後的pa再來比較
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j){ // 如果pa，pb位於同一個位置上，則將值相加
pa->e -= pb->e;
if(!pa->e){ // 如果相加後的和為0，則刪除此節點，同時改變此元素坐在行，列的前驅元素的相應值
if(NULL==pre) // 修改行前驅元素值
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down; // 修改列前驅元素值
else
hl[p->j]->down=p->down;
free(p); pb=pb->right;
}
else{
pa=pa->right; pb=pb->right;
}
}
}
}
shuchu(M);
} void add() //矩陣的加法
{
CrossList M,N; // 創建兩個十字鏈表對象，並初始化
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"輸入的兩稀疏矩陣的和矩陣為："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; //定義輔助指針，pa，pb分別為M,N當前比較的元素，pre為pa的前驅元素
for(int x=1;x<=M.b;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.a;k++){ // 對M的每一行進行操作
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb){ // 把N中此行的每個元素取出，
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，存儲N中取出的元素
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j){ // 當M此行已經檢查完或者pb因該放在pa前面
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){ // 進行列插入
M.chead[p->j]=p; p->down=NULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j){ // 如果此時的pb元素因該放在pa後面，則取以後的pa再來比較
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j){ // 如果pa，pb位於同一個位置上，則將值相加
pa->e += pb->e;
if(!pa->e){ // 如果相加後的和為0，則刪除此節點，同時改變此元素坐在行，列的前驅元素的相應值
if(NULL==pre) // 修改行前驅元素值
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down; // 修改列前驅元素值
else
hl[p->j]->down=p->down;
free(p); pb=pb->right;
}
else{
pa=pa->right; pb=pb->right;
}
}
}
}
shuchu(M);
} int main() //主函數
{
cout<<"1:稀疏矩陣的加法。"<<endl;
cout<<"2:稀疏矩陣的乘法。"<<endl;
cout<<"3:稀疏矩陣的減法。"<<endl;
cout<<"4:稀疏矩陣的轉置."<<endl;
cout<<"0:退出程序。"<<endl;
char c=getchar();
if(c=='1')
add(); //調用矩陣相加函數
else
if(c=='2')
chengfa(); //調用矩陣相乘函數
else
if(c=='3')
jianfa(); //調用矩陣相減函數
else
if(c=='4')
zhuan( ); //調用矩陣轉置函數
else
exit(0); //退出
return 0;
}
㈡ c語言矩陣轉置問題
其實只是小問題，你自己都編的很好了。就是保存屏幕不在按入Q和Enter鍵屏幕不會馬上消失上面有問題：
你可以用兩個getchar（）函數來讀取鍵盤輸入，前一個數緩沖enter鍵，後一個等待鍵盤輸入，然後屏幕消失！
代碼已修改，如下：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20 /*矩陣中最大非零元的個數*/
typedef struct triple
{
int i; /*行標,本程序中從1開始的*/
int j; /*列標,本程序中從1開始的*/
int e; /*非零元*/
}Triple; /*三元組定義*/
typedef struct tabletype
{
int mu; /*矩陣的行數*/
int nu; /*列數*/
int tu; /*非零元個數*/
Triple data[MAXSIZE+1]; /*非零元的三元組表,*/
}Tabletype; /*三元組線性表*/
void out_matrix(Tabletype *); /*輸出 矩陣*/
/*以下為轉置程序,將a所指矩陣轉置，將結果存入b所指的矩陣中*/
int TransposeSMatrix(Tabletype *,Tabletype *);
int main( void )
{
char ch;
while(1)
{
printf(" @@@@@@@@@@本程序的功能是實現稀疏矩陣的普通轉置@@@@@@@@@@@@@@@@@@@\n");
printf(" @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");
/*源矩陣a*/
Tabletype 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} }};
Tabletype b; /*聲明矩陣b*/
printf("The source Matrix:\n");
out_matrix(&a);
if(TransposeSMatrix(&a,&b)) /*若a不為零矩陣則轉置a，存入b中*/
{ printf("After TransposeSMatrix: \n");
out_matrix(&b);
}
else
{
printf("The matrix is zeros:\n");
out_matrix(&a);
}
do{
printf("Input 'q' to quit and ENTER run again:");
if((ch = getchar()) == 'q' || ch == 'Q')
getchar(); //讀取enter
getchar();//任意字元
exit(0);
}while(ch!='\n');
system("cls");
}
return 1;
}
void out_matrix(Tabletype *a) /* 列印矩陣*/
{
int i,j,k = 0;
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 TransposeSMatrix(Tabletype *a,Tabletype *b)
{
int p,q,col;
b->mu = a->nu; /*原矩陣的行數為新矩陣的列數，願列數為新行數，非零元個數不變*/
b->nu = a->mu;
b->tu = a->tu;
if(b->tu) /*若a不為零矩陣*/
{
q = 0; /*b->data下標*/
for(col = 1; col < a->nu; col++)
for(p = 0;p < a->tu;p++) /*p為a->data的下標*/
if(col == a->data[p].j) /*按b->data[q]中的列標對a->data[p]進行掃描*/
{
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++;
}
return 1;
}
else /*a為零矩陣*/
return 0;
}
不知道是不是你的要求。希望能幫助你！
㈢ 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;
}
另外,站長團上有產品團購,便宜有保證