#include <iostream.h>
#include <iomanip.h>
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;
}