희소 행렬 - 삼원 조

알고리즘 사상 은 엄 서 에서 비롯 되 고 실현 도 엄 서 를 바탕 으로 하 는 3 원 조 데이터 구조 이다.배우 고 싶 은 것 은 참고 할 수 있 고, 엄서 3 원 조 1 절 이다.

/*  Author : Moyiii
 *  Mail:  [email protected]
 *      -      
 *        ，         ，    。
 *      BUG，        ，      
*/
#include <iostream>
#include <cstdio>

using namespace std;

const int MAX_MATRIX_NUM = 100;
const int MAX_MATRIX_SIZE = 20;

//   
class Triple
{
public:
    int row;
    int col;
    int data;
};

//     
class SMatrix
{
public:
    void input();
    void copyMat(SMatrix &dest);
    //   
    static void addMat(SMatrix &a,SMatrix &b, SMatrix &dest);
    static void mulMat(SMatrix &a,SMatrix &b, SMatrix &dest);
    static void subMat(SMatrix &a,SMatrix &b, SMatrix &dest);
    static void countf(SMatrix &dest);
    //      
    void tran(SMatrix &dest);
    void print();
private:
    int nrow,ncol,nelems;
    //     ，         
    Triple datas[MAX_MATRIX_NUM];
    //              datas      
    int fpos[MAX_MATRIX_SIZE];
};

void SMatrix :: input()
{
     //          
    cout << "Please enter the num of row and colums:" ;
    cin >> nrow>> ncol;
    while(nrow < 0 || ncol < 0)
    {
        cout << "rows or colums must be positive integers" << endl;
        cout << "Please enter the num of row and colums:";
        cin >> nrow >> ncol;
    }
    cout << "Please input the num of non-zero elems:";
    cin >> nelems;
    while(nelems < 0 || nelems > MAX_MATRIX_NUM)
    {
        cout << "Num of nelems is invalid" << endl;
        cout << "Please input the num of non-zero elems:";
        cin >> nelems;
    }
    cout << "Please input n lines datas like: row col data:" << endl;
    for(int i = 0; i < nelems; ++i)
    {
        cin >> datas[i].row >>datas[i].col >> datas[i].data;
    }
    SMatrix :: countf(*this);
}

//  fpos  ，     。               
//           +         
void SMatrix :: countf(SMatrix &dest)
{
    int nums[dest.ncol];
    for(int i = 0; i < dest.ncol; ++i)
    {
        nums[i] = 0;
    }

    for(int i = 0; i < dest.nelems; ++i)
    {
        ++nums[dest.datas[i].row - 1];
    }

    dest.fpos[0] = 0;
    for(int i = 1; i <= dest.ncol; ++i)
    {
        dest.fpos[i] = dest.fpos[i-1] + nums[i-1];
    }
    dest.fpos[dest.nrow] = dest.nelems;
    return;
}

//          ，    
void SMatrix :: print()
{
    int index = 0;
    printf("  ");
    //       
    for(int i = 1; i <= ncol; ++i)
    {
        printf("%2d ",i);
    }
    printf("
");
    printf("  ");
    for(int i = 1; i <= ncol; ++i)
    {
        printf("%2c ",'-');
    }
    printf("
");
    for(int i = 1; i <= nrow; ++i)
    {
        //       
        printf("%d|",i);
        for(int j = 1; j <= ncol; ++j)
        {
            //      
            if(index > nelems)
            {
                printf("%2d ",0);
            }
            else
            {
                //       
                if(i == datas[index].row && j == datas[index].col)
                {
                    printf("%2d ",datas[index].data);
                    index++;
                }
                else
                {
                    printf("%2d ",0);
                }
            }
        }
        cout << endl;
    }
    cout << endl;
}

//         dest
void SMatrix :: copyMat(SMatrix &dest)
{
    if(&dest == this)
    {
        return;
    }

    for(int i = 0; i < this->nelems; ++i)
    {
        dest.datas[i] = this->datas[i];
    }
    dest.nelems = this->nelems;
    dest.ncol = this->ncol ;
    dest.nrow = this->nrow ;

    for(int i = 0; i < nrow; ++i)
    {
        dest.fpos[i] = this->fpos[i];
    }
    return;
}

//              。     。。
void SMatrix :: tran(SMatrix &dest)
{
    Triple temp[MAX_MATRIX_NUM];
    //           
    int nums[ncol];
    int tfpos[ncol];
    for(int i = 0; i < ncol; ++i)
    {
        nums[i] = 0;
    }

    for(int i = 0; i <nelems; ++i)
    {
        ++nums[datas[i].col - 1];
    }

    dest.fpos[0] = 0;
    tfpos[0] = 0;

    for(int i = 1; i <= ncol; ++i)
    {
        dest.fpos[i] = dest.fpos[i-1] + nums[i-1];
        tfpos[i] = dest.fpos[i];
    }

    int trows = this->ncol;
    int tcols = this->nrow;
    int telems = this->nelems;
    //            ，               
    for(int i = 0; i < telems; ++i)
    {
        int &t = tfpos[this->datas[i].col - 1];
        temp[t].col = this->datas[i].row;
        temp[t].row = this->datas[i].col;
        temp[t].data = this->datas[i].data;
        t++;
    }
    //             ，              。
    for(int i = 0; i < telems; ++i)
    {
        dest.datas[i] = temp[i];
    }
    dest.ncol = tcols;
    dest.nrow = trows;
    dest.nelems = telems;
    return;
}

//        ，  。       
void SMatrix :: addMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
    if(a.nrow != b.nrow || a.ncol != b.ncol)
    {
        cout << "Error, the two matrix are not the same size!" << endl;
        return;
    }
    int index = 0;
    int cura = 0,curb = 0;
    while(cura < a.nelems && curb < b.nelems)
    {
        int ra = a.datas[cura].row,rb = b.datas[curb].row;
        int ca = a.datas[cura].col,cb = b.datas[curb].col;
        //                 ，   
        if((ra-1)*a.nrow + ca < (rb-1)*b.nrow + cb)
        {
            dest.datas[index++] = a.datas[cura++];
        }
        else if((rb-1)*b.nrow + cb <(ra-1)*a.nrow + ca)
        {
            dest.datas[index++] = b.datas[curb++];
        }
        else
        {
            dest.datas[index] = a.datas[cura++];
            dest.datas[index++].data += b.datas[curb++].data;
            if(dest.datas[index].data == 0)
            {
                index--;
            }
        }
    }

    while(cura < a.nelems)
    {
        dest.datas[index++] = a.datas[cura++];
    }

    while(curb <b.nelems)
    {
        dest.datas[index++] = a.datas[curb++];
    }

    dest.ncol = a.ncol;
    dest.nrow = a.nrow;
    dest.nelems = index;
    SMatrix :: countf(dest);
    return ;
}

// b     -1，      
void SMatrix :: subMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
    SMatrix temp;
    b.copyMat(temp);
    for(int i = 0; i < temp.nelems; ++i)
    {
        temp.datas[i].data *= -1;
    }

    SMatrix :: addMat(a,temp,dest);
    return;
}


void  SMatrix :: mulMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
    //    a    b  ，  b ，    a    b  。
    //    ，         
    SMatrix temp;
    b.tran(temp);
    int trow = a.nrow;
    int tcol = b.ncol;
    int index = 0;
    //           ，          
    int res[tcol];

    for(int i = 0; i < a.nrow; ++i)
    {
        //res   i      ，   0 
        for(int k = 0; k < tcol; ++k)
        {
            res[k] = 0;
        }

        for(int j = 0; j < temp.nrow; ++j)
        {
            //     M[i][j]   
            int cura = a.fpos[i];
            int curb = temp.fpos[j];
            //      ，             
            while(cura < a.fpos[i+1] && curb < temp.fpos[j+1])
            {
                if(a.datas[cura].col < temp.datas[curb].col)
                {
                    ++cura;
                }
                else if(temp.datas[curb].col < a.datas[cura].col)
                {
                    ++curb;
                }
                else
                {
                    res[j] += temp.datas[curb].data * a.datas[cura].data;
                    curb++;
                    cura++;
                }
            }
        }

        for(int k = 0; k < tcol ; ++k)
        {
            //            
            if(res[k] != 0)
            {
                dest.datas[index].row = i + 1;
                dest.datas[index].col = k + 1;
                dest.datas[index].data = res[k];
                index++;
            }
        }
    }
    dest.nelems = index;
    dest.nrow = trow;
    dest.ncol = tcol;
    SMatrix :: countf(dest);
    return ;
}

/*      ,       
6 6
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
*/

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