희소 행렬 - 십자 링크

/*  Author : Moyiii
 *  Mail:  [email protected]
 *      -       
 *        ，         ，    。
 *      BUG，        ，      
*/

#include <iostream>

using namespace std;

class CNode
{
public:
    CNode(int r = -1, int c = -1, int d = 0)
    {
        row = r;
        col = c;
        data = d;
        right = down = NULL;
    }
    int row;
    int col;
    int data;
    CNode *right;
    CNode *down;
};

class CMatrix
{
public:
    CMatrix(int rows,int cols);
    ~CMatrix();
    void clear();
    void print();
    void copyMat(CMatrix &dest);

    //    
    void input();
    //      
    void tran(CMatrix &dest);

    //   
    static void addMat(CMatrix &a,CMatrix &b, CMatrix &dest);
    static void mulMat(CMatrix &a,CMatrix &b, CMatrix &dest);
    static void subMat(CMatrix &a,CMatrix &b, CMatrix &dest);

private:
    CNode **rowHead;
    CNode **colHead;
    int rowNum;
    int colNum;
    int dataNum;
};

CMatrix :: CMatrix(int rows, int cols)
{
    rowNum = rows;
    colNum = cols;
    dataNum = 0;
    rowHead = new CNode*[rowNum];
    colHead = new CNode*[colNum];
    for(int i = 0; i < rowNum; ++i)
    {
        rowHead[i] = NULL;
    }

    for(int i = 0; i < colNum; ++i)
    {
        colHead[i] = NULL;
    }

    if(!rowHead || !colHead)
    {
        cout << "Malloc Error!" << endl;
        return;
    }
}

void CMatrix :: clear()
{
    //       ，       ，   
    for(int i = 0; i < rowNum; ++i)
    {
        while(rowHead[i] != NULL)
        {
            CNode *p = rowHead[i];
            rowHead[i] = rowHead[i]->right;
            delete p;
        }
    }
    //    ，    
    for(int i = 0; i < colNum; ++i)
    {
        colHead[i] = NULL;
    }
    delete []rowHead;
    delete []colHead;
    dataNum = 0;
    rowNum = colNum = 0;
    return;
}

CMatrix :: ~CMatrix()
{
    clear();
}

//  ，           ，      
void CMatrix :: print()
{
    cout << "The Matrix is:" << endl;
    for(int i = 0; i < rowNum; ++i)
    {
        CNode *p = rowHead[i];
        int j = 0;
        while(j != colNum)
        {
            if(p && j == (p->col - 1))
            {
                cout << p->data << " ";
                j++;
                p = p->right;
            }
            else
            {
                cout << "0 ";
                j++;
            }
        }
        cout << endl;
    }
    cout << endl;
}

void CMatrix :: copyMat(CMatrix &dest)
{
    if(&dest == this)
    {
        return;
    }
    dest.clear();
    dest.rowHead = new CNode*[rowNum];
    dest.colHead = new CNode*[colNum];
    for(int i = 0; i < rowNum; ++i)
    {
        dest.rowHead[i] = NULL;
    }

    for(int i = 0; i < colNum; ++i)
    {
        dest.colHead[i] = NULL;
    }

    CNode* tempr[rowNum];
    CNode* tempc[colNum];
    for(int i = 0; i < rowNum; ++i)
    {
        tempr[i] = NULL;
    }

    for(int i = 0; i < colNum; ++i)
    {
        tempc[i] = NULL;
    }

    for(int i = 0; i < rowNum; ++i)
    {
        CNode *p = rowHead[i];
        //      ，      ，      。
        while(p != NULL)
        {
            //                 ，             
            //                        ，  temp  
            //                
            CNode * q = new CNode(p->row, p->col, p->data);

            if(tempr[i] == NULL)
            {
                tempr[i] = dest.rowHead[i] = q;
            }
            else
            {
                tempr[i]->right = q;
                tempr[i] = q;
            }
            if(tempc[q->col - 1] == NULL)
            {
                tempc[q->col - 1] = dest.colHead[q->col - 1] = q;
            }
            else
            {
                tempc[q->col - 1]->down = q;
                tempc[q->col - 1] = q;
            }
            p = p->right;
        }
    }
    dest.rowNum = rowNum;
    dest.colNum = colNum;
    dest.dataNum = dataNum;
}

void CMatrix :: input()
{
    cout << "Input the Node with its row col and data end with 0 0 0." << endl;
    int r,c,d;
    while((cin >> r >> c >> d) && c*r)
    {
        if(c < 0 || r < 0)
        {
            cout << "Invalid data!" << endl;
            continue;
        }
        CNode *p = new CNode(r,c,d);
        r = r - 1;
        c = c - 1;

        //                 ，          
        //                
        if(rowHead[r] == NULL || ((rowHead[r]->col - 1) > c))
        {
            p->right = rowHead[r];
            rowHead[r] = p;
        }
        else
        {
            CNode *q = rowHead[r];
            while(q->right && ((q->right->col - 1) < c))
            {
                q = q->right;
            }
            p->right = q->right;
            q->right = p;
        }

        if(colHead[c] == NULL ||((colHead[c]->row - 1) > r))
        {
            p->down = colHead[c];
            colHead[c] = p;
        }
        else
        {
            CNode *q = colHead[c];
            while(q->down && ((q->down->row - 1) < r))
            {
                q = q->down;
            }
            p->down = q->down;
            q->down = p;
        }
        dataNum++;
    }
    return;
}

void CMatrix :: tran(CMatrix &dest)
{
    //     ，   ，   ，       ，       
    if(this == &dest)
    {
        for(int i = 0; i < rowNum; ++i)
        {
            CNode *p = rowHead[i];
            while(p != NULL)
            {
                CNode *temp = p->right;
                p->right = p->down;
                p->down = temp;

                int tempn = p->col;
                p->col = p->row;
                p->row = tempn;
                p = p->down;
            }
        }

        CNode **temp = rowHead;
        rowHead = colHead;
        colHead = temp;

        int tempN = rowNum;
        rowNum = colNum;
        colNum = tempN;
        return;
    }

    //            ，       
    dest.clear();
    rowHead = new CNode*[rowNum];
    colHead = new CNode*[colNum];
    for(int i = 0; i < rowNum; ++i)
    {
        rowHead[i] = NULL;
    }

    for(int i = 0; i < colNum; ++i)
    {
        colHead[i] = NULL;
    }
    tran(*this);
    copyMat(dest);
    tran(*this);
    return;
}

//    ，    b    a，       。
//                ，          
//    ，             ，       
//            
void CMatrix :: addMat(CMatrix &a,CMatrix &b, CMatrix &dest)
{
    //  a   b   dest        
    dest.clear();
    dest.rowHead = new CNode*[a.rowNum];
    dest.colHead = new CNode*[a.colNum];
    for(int i = 0; i < dest.rowNum; ++i)
    {
        dest.rowHead[i] = NULL;
    }

    for(int i = 0; i < dest.colNum; ++i)
    {
        dest.colHead[i] = NULL;
    }
    if(a.rowNum != b.rowNum || a.colNum != b.colNum)
    {
        cout << "Two matrixs are not the same size!" << endl;
        return;
    }
    int rows = a.rowNum;
    int cols = a.colNum;

    // tempc          copyMat  temp     
    CNode* tempc[cols];
    for(int i = 0; i < cols; ++i)
    {
        tempc[i] = NULL;
    }

    //        
    for(int i = 0; i < rows; ++i)
    {
        CNode* cura = a.rowHead[i];
        CNode* curb = b.rowHead[i];
        CNode* curc = dest.rowHead[i];
        while(cura != NULL && curb != NULL)
        {
            CNode *p;
            //          
            if(cura->col < curb->col)
            {
                p = new CNode(cura->row, cura->col, cura->data);
                cura = cura->right;
            }
            else if(curb->col < cura->col)
            {
                p = new CNode(curb->row, curb->col, curb->data);
                curb = curb->right;
            }
            else
            {
               //     ，  
                p = new CNode(cura->row, cura->col, cura->data + curb->data);
                cura = cura->right;
                curb = curb->right;
            }
            //    ，        dest 
            if(p->data != 0)
            {
                if(curc == NULL)
                {
                    curc = dest.rowHead[i] = p;
                }
                else
                {
                    curc->right = p;
                    curc = p;
                }

                if(tempc[p->col - 1] == NULL)
                {
                    tempc[p->col - 1] = dest.colHead[p->col - 1] = p;
                }
                else
                {
                    tempc[p->col - 1]->down = p;
                    tempc[p->col - 1] = p;
                }
                dest.dataNum++;
            }

        }
        //         ，       ，          
        // a b           dest 。
        CNode *tcur;
        if(cura == NULL)
        {
            tcur = curb;
        }
        else
        {
            tcur = cura;
        }

        while(tcur != NULL)
        {
            CNode *p = new CNode(tcur->row, tcur->col, tcur->data);

            if(curc == NULL)
            {
                curc = dest.rowHead[i] = p;
            }
            else
            {
                curc->right = p;
                curc = p;
            }

            if(tempc[p->col - 1] == NULL)
            {
                tempc[p->col - 1] = dest.colHead[p->col - 1] = p;
            }
            else
            {
                tempc[p->col - 1]->down = p;
                tempc[p->col - 1] = p;
            }
            tcur = tcur->right;
            dest.dataNum++;
        }
    }
    dest.rowNum = rows;
    dest.colNum = cols;
}

//  ， b      a    
void CMatrix :: subMat(CMatrix &a,CMatrix &b, CMatrix &dest)
{
    dest.clear();
    dest.rowHead = new CNode*[a.rowNum];
    dest.colHead = new CNode*[a.colNum];
    for(int i = 0; i < dest.rowNum; ++i)
    {
        dest.rowHead[i] = NULL;
    }

    for(int i = 0; i < dest.colNum; ++i)
    {
        dest.colHead[i] = NULL;
    }
    CMatrix temp(b.rowNum, b.colNum);
    b.copyMat(temp);
    for(int i = 0; i < temp.rowNum; ++i)
    {
        CNode *p = temp.rowHead[i];
        while(p != NULL)
        {
            p->data *= -1;
            p = p->right;
        }
    }
    CMatrix :: addMat(a,temp,dest);
    return;
}


//  ，     。
void CMatrix :: mulMat(CMatrix &a,CMatrix &b, CMatrix &dest)
{
    if(a.colNum != b.rowNum)
    {
        cout << "The two Matrix can't not multiply!" << endl;
        return;
    }

    //      
    dest.clear();
    dest.rowHead = new CNode*[a.rowNum];
    dest.colHead = new CNode*[b.colNum];
    dest.rowNum = a.rowNum;
    dest.colNum = b.colNum;

    for(int i = 0; i < dest.rowNum; ++i)
    {
        dest.rowHead[i] = NULL;
    }

    for(int i = 0; i < dest.colNum; ++i)
    {
        dest.colHead[i] = NULL;
    }

    CNode* tempc[dest.colNum];
    for(int i = 0; i < dest.colNum; ++i)
    {
        tempc[i] = NULL;
    }
    //      ，         

    //  i,j            
    for(int i = 0; i < dest.rowNum; ++i)
    {
        CNode* curc = dest.rowHead[i];
        for(int j = 0;j < dest.colNum; ++j)
        {
            //      ！ a  i  b  j  ，             
            //    
            CNode* cura = a.rowHead[i];
            CNode* curb = b.colHead[j];
            int count = 0;

            //         
            while(cura != NULL && curb != NULL)
            {
                if(cura->col < curb->row)
                {
                    cura = cura->right;
                }
                else if(curb->row < cura->col)
                {
                    curb = curb->down;
                }
                else
                {
                    count += cura->data*curb->data;
                    cura = cura->right;
                    curb = curb->down;
                }
            }
            //        ，      。
            if(count != 0)
            {
                CNode *p = new CNode(i + 1,j + 1,count);
                if(curc == NULL)
                {
                    curc = dest.rowHead[i] = p;
                }
                else
                {
                    curc->right = p;
                    curc = p;
                }

                if(tempc[p->col - 1] == NULL)
                {
                    tempc[p->col - 1] = dest.colHead[p->col - 1] = p;
                }
                else
                {
                    tempc[p->col - 1]->down = p;
                    tempc[p->col - 1] = p;
                }
                dest.dataNum++;
            }
        }
    }
    return;
}

int main()
{
    CMatrix a(2,2);
    CMatrix b(2,3);
    CMatrix c(3,3);
    a.input();
    a.print();
    b.input();
    b.print();
    CMatrix :: mulMat(a,b,c);
    c.print();
    return 0;
}