#include <iostream> 
#include <iomanip> 
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 mu,nu,tu; 
}TSMatrix; 
typedef struct { // 定義帶鏈接信息的三元組對象 
Triple data[MAXSIZE+2]; 
int rpos[MAXROW+1]; 
int mu,nu,tu; 
}RLSMatrix; 
template <class P> 
bool InPutTSMatrix(P & T,int y){ //輸入矩陣，按三元組格式輸入 
cout<<"輸入矩陣的行，列和非零元素個數:"<<endl; 
cin>>T.mu>>T.nu>>T.tu; 
cout<<"請輸出非零元素的位置和值:"<<endl; 
int k=1; 
for(;k<=T.tu;k++) 
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e; 

return true; 
} 
template <class P> 
bool OutPutSMatrix(P T){ // 輸出矩陣，按標準格式輸出 
int m,n,k=1; 
for(m=0;m<T.mu;m++){ 
for(n=0;n<T.nu;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; 
} 
return true; 
} 
// 求矩陣的轉置矩陣 
bool TransposeSMatrix( ){ 
TSMatrix M,T; //定義預轉置的矩陣 
InPutTSMatrix(M, 0); //輸入矩陣 
int num[MAXROW+1]; 
int cpot[MAXROW+1]; // 構建輔助數組 
int q,p,t; 
T.tu=M.tu; T.mu=M.nu; T.nu=M.mu; 
if(T.tu){ 
for(int col=1;col<=M.nu;col++) num[col]=0; 
for(t=1;t<=M.tu;t++) ++num[M.data[t].j]; 
cpot[1]=1; 
for(int i=2;i<=M.nu;i++) cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元組中出現的位置 
for(p=1;p<=M.tu;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; 
OutPutSMatrix(T); 
return true; 
} 

bool Count(RLSMatrix &T) 
{ 
int num[MAXROW+1]; 
for(int col=1;col<=T.mu;col++) num[col]=0; 
for(col=1;col<=T.tu;col++) ++num[T.data[col].i]; 
T.rpos[1]=1; 
for(int i=2;i<=T.mu;i++) T.rpos[i]=T.rpos[i-1]+num[i-1]; // 求取每一行中非零元素在三元組中出現的位置 

return true; 
} 
// 兩個矩陣相乘 
bool MultSMatrix ( ){ 
RLSMatrix M,N,Q; // 構建三個帶“鏈接信息”的三元組表示的數組 
InPutTSMatrix(M,1); // 用普通三元組形式輸入數組 
InPutTSMatrix(N,1); 
Count(M); Count(N); 
if(M.nu!=N.mu) return false; 
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; // Q初始化 
int ctemp[MAXROW+1]; // 輔助數組 
int arow,tp,p,brow,t,q,ccol; 
if(M.tu*N.tu){ // Q是非零矩陣 
for( arow=1;arow<=M.mu;arow++){ 
///memset(ctemp,0,N.nu); 
for(int x=1;x<=N.nu;x++) // 當前行各元素累加器清零 
ctemp[x]=0; 
Q.rpos[arow]=Q.tu+1; // 當前行的首個非零元素在三元組中的位置為此行前所有非零元素+1 
if(arow<M.mu) tp=M.rpos[arow+1]; 
else tp=M.tu+1; 
for(p=M.rpos[arow];p<tp;p++){ // 對當前行每個非零元素進行操作 

brow=M.data[p].j; // 在N中找到i值也操作元素的j值相等的行 
if(brow<N.mu) t=N.rpos[brow+1]; 
else t=N.tu+1; 
for(q=N.rpos[brow];q<t;q++){ // 對找出的行當每個非零元素進行操作 

ccol=N.data[q].j; 
ctemp[ccol] += M.data[p].e*N.data[q].e; // 將乘得到對應值放在相應的元素累加器里面 
} 
} 
for(ccol=1;ccol<=Q.nu;ccol++) // 對已經求出的累加器中的值壓縮到Q中 
if(ctemp[ccol]){ 
if(++Q.tu>MAXSIZE) return false; 
Q.data[Q.tu].e=ctemp[ccol]; 
Q.data[Q.tu].i=arow; 
Q.data[Q.tu].j=ccol; 
} 
} 
} 
OutPutSMatrix(Q); 
return true; 
} 
typedef struct OLNode{ // 定義十字鏈表元素 
int i,j; 
int e; 
struct OLNode *right,*down; // 該非零元所在行表和列表的后繼元素 
}OLNode,*OLink; 
typedef struct{ // 定義十字鏈表對象結構體 
OLink *rhead,*chead; 
int mu,nu,tu; // 系數矩陣的行數，列數，和非零元素個數 
}CrossList; 
bool CreateSMatrix_OL(CrossList & M){ // 創建十字鏈表 
int x,y,m; 

cout<<"請輸入矩陣的行，列，及非零元素個數"<<endl; 
cin>>M.mu>>M.nu>>M.tu; 
if(!(M.rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink)))) exit(0); 
if(!(M.chead=(OLink*)malloc((M.nu+1)*sizeof(OLink)))) exit(0); 
for(x=0;x<=M.mu;x++) 
M.rhead[x]=NULL; // 初始化各行，列頭指針，分別為NULL 
for(x=0;x<=M.nu;x++) 
M.chead[x]=NULL; 
cout<<"請按三元組的格式輸入數組："<<endl; 
for(int i=1;i<=M.tu;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; // 完成列插入 

} 
} 
return true; 
} 
bool OutPutSMatrix_OL(CrossList T){ // 輸出十字鏈表，用普通數組形式輸出 
for(int i=1;i<=T.mu;i++){ 
OLink p=T.rhead[i]; 
for(int j=1;j<=T.nu;j++){ 
if((p)&&(j==p->j)){ 
cout<<setw(3)<<p->e; p=p->right; 
} 
else 
cout<<setw(3)<<"0"; 
} 
cout<<endl; 
} 
return true; 
} 

//矩陣的加法 
bool AddSMatrix(){ 
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.nu;x++) hl[x]=M.chead[x]; 
for(int k=1;k<=M.mu;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; 
} 
} 

} 
} 
OutPutSMatrix_OL(M); 
return true; 
} 
int main(){ 
cout.fill('*'); 
cout<<setw(80)<<'*'; 
cout.fill(' '); 
// system("color 0C"); 
cout<<setw(50)<<"***歡迎使用矩陣運算程序***"<<endl; //輸出頭菜單 
cout.fill('*'); 
cout<<setw(80)<<'*'; 
cout.fill(' '); 
cout<<"請選擇要進行的操作："<<endl; 
cout<<"1:矩陣的轉置。"<<endl; 
cout<<"2:矩陣的加（減）法。"<<endl; 
cout<<"3:矩陣的乘法。"<<endl; 
cout<<"4:推出程序。"<<endl; 
char c=getchar(); 
if(c=='1') 
TransposeSMatrix( ); //調用矩陣轉置函數 
else 
if(c=='2') 
AddSMatrix(); //調用矩陣相加函數 
else 
if(c=='3') 
MultSMatrix (); //調用矩陣相乘函數 
else 
exit(0); //退出 
return 0; 
}