稀疏矩阵（三元组顺序表存储）6种操作的实现

/*
*任务描述：针对稀疏矩阵，实现10个基本操作
*   1：建立稀疏矩阵 ；
*   2：输出稀疏矩阵 ；
*   3：转置稀疏矩阵 ；
*   4：稀疏矩阵相加 ；
*   5：稀疏矩阵相减；
*   6：稀疏矩阵相乘 ；
主要函数：
*   1.void CreateMatrix(Matrix &M);//创建矩阵
*   2.void Output(Matrix M);//输出矩阵
*   3.void TransposeMatrix1(Matrix &M);//转置矩阵算法1
*   4.void TransposeMatrix2(Matrix &M);//转置矩阵算法2
*   5.void TransposeMatrix3(Matrix &M);//转置矩阵算法3
*   6.void AddMatrix(Matrix &M1,Matrix &M2);//矩阵相加
*   7.void SubtractMatrix(Matrix &M1,Matrix &M2);//矩阵相减
*   8.void MultiplyMatrix(Matrix &M,Matrix &N);//矩阵相乘
*   9.Status Check(Matrix M,int index,int row,int line);//检查矩阵M的数组data中第index个元素的行列数
*   10.void SortByRow(Matrix &M);//行优先冒泡排序
*   11.void SortByLine(Matrix &M);//列优先冒泡排序
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>


using namespace std;


#define OK 1
#define FALSE 0
#define MAXSIZE 10000


typedef int ElemType;
typedef int Status;


typedef struct
{
    int row;//非零元素所在的行
    int line;//非零元素所在的列
    ElemType elem;//非零元素大小
} Triple;//非零元素的三元组类型


typedef struct
{
    Triple data[MAXSIZE];//非零元素数组
    int rownum;//矩阵的行数
    int linenum;//矩阵的列数
    int elemnum;//矩阵的非零元素总数
} Matrix;//矩阵类型


void CreateMatrix(Matrix &M);//创建矩阵
void Output(Matrix M);//输出矩阵
void TransposeMatrix1(Matrix &M);//转置矩阵算法1
void TransposeMatrix2(Matrix &M);//转置矩阵算法2
void TransposeMatrix3(Matrix &M);//转置矩阵算法3
void AddMatrix(Matrix &M1,Matrix &M2);//矩阵相加
void SubtractMatrix(Matrix &M1,Matrix &M2);//矩阵相减
void MultiplyMatrix(Matrix &M,Matrix &N);//矩阵相乘
Status Check(Matrix M,int index,int row,int line);//检查矩阵M的数组data中第index个元素的行列数
void SortByRow(Matrix &M);//行优先冒泡排序
void SortByLine(Matrix &M);//列优先冒泡排序
void Interaction();//输出操作


int main()
{
    Interaction();


    Matrix M,N;
    int operate;
    while(cin>>operate)
    {
        switch(operate)
        {
        case 0:
            return 0;


        case 1:
            cout<<"请输入创建的稀疏矩阵的行数、列数、非0元素个数：";
            cin>>M.rownum>>M.linenum>>M.elemnum;
            CreateMatrix(M);
            break;


        case 2:
            Output(M);
            break;


        case 3:
            cout<<"转置矩阵共3种方法，请输入使用的方法序号（1/2/3）：";
            cin>>operate;


            switch(operate)
            {
            case 1:
                TransposeMatrix1(M);
                break;


            case 2:
                TransposeMatrix2(M);
                break;


            case 3:
                TransposeMatrix3(M);
                break;
            }
            break;


        case 4:
INPUT1:
            cout<<"请输入创建的稀疏矩阵的行数、列数、非0元素个数：";
            cin>>N.rownum>>N.linenum>>N.elemnum;
            if(M.rownum!=N.rownum||M.linenum!=N.linenum)
            {
                cout<<"矩阵相加的前提是两个矩阵的行数列数分别相等。请创建合法的矩阵。\n";
                goto INPUT1;
            }


            CreateMatrix(N);
            AddMatrix(M,N);
            break;


        case 5:
INPUT2:
            cout<<"请输入创建的稀疏矩阵的行数、列数、非0元素个数：";
            cin>>N.rownum>>N.linenum>>N.elemnum;
            if(M.rownum!=N.rownum||M.linenum!=N.linenum)
            {
                cout<<"矩阵相减的前提是两个矩阵的行数列数分别相等。请创建合法的矩阵。\n";
                goto INPUT2;
            }


            CreateMatrix(N);
            SubtractMatrix(M,N);
            break;


        case 6:
INPUT3:
            cout<<"请输入创建的稀疏矩阵的行数、列数、非0元素个数：";
            cin>>N.rownum>>N.linenum>>N.elemnum;
            if(M.linenum!=N.rownum)
            {
                cout<<"矩阵相乘的前提是矩阵1的列数等于矩阵2的行数。请创建合法的矩阵。\n";
                goto INPUT3;
            }


            CreateMatrix(N);
            MultiplyMatrix(M,N);
            break;
        default:
            cout<<"请输入正确的操作数字！\n";
        }
    }
    return 0;
}


void CreateMatrix(Matrix &M)//创建矩阵
{
    cout<<"请输入"<<M.elemnum<<"个非0元素的行数、列数（均从1开始）、元素大小：\n";
    for(int i=1; i<=M.elemnum; i++)
    {
        cin>>M.data[i].row>>M.data[i].line>>M.data[i].elem;
    }


    SortByRow(M);//将矩阵的所有非零元素按照行优先的顺序重新排列，便于后续操作
    cout<<"创建的稀疏矩阵为：\n";
    Output(M);
}


void Output(Matrix M)//输出矩阵
{
    int index=1;
    for(int row=1; row<=M.rownum; row++)
    {
        for(int line=1; line<=M.linenum; line++)
        {
            if(Check(M,index,row,line))//检测当前位置是否是非零元素
            {
                cout<<setw(4)<<M.data[index].elem;
                index++;
            }
            else
            {
                cout<<setw(4)<<0;
            }
        }
        cout<<endl;
    }
}


void TransposeMatrix1(Matrix &M)//转置矩阵算法1
{
    //算法描述：因为当前矩阵是行优先的，转置后变成列优先的（相对未转置前）。因此
    //枚举列数1——M.linenum，对于每一个列数line，按照原矩阵的顺序遍历一遍所有的非零元素，
    //找出列数等于line的非零元素并完成转置该元素。
    Matrix T;
    T.rownum=M.linenum;
    T.linenum=M.rownum;
    T.elemnum=M.elemnum;


    if(T.elemnum)
    {
        int index1=1;
        for(int line=1; line<=M.linenum; line++)//枚举列数1——M.linenum
        {
            for(int index2=1; index2<=M.elemnum; index2++)//遍历一遍所有的非零元素
            {
                if(M.data[index2].line==line)//找出列数等于line的非零元素
                {
                    //转置该元素
                    T.data[index1].row=M.data[index2].line;
                    T.data[index1].line=M.data[index2].row;
                    T.data[index1].elem=M.data[index2].elem;
                    index1++;
                }
            }
        }
    }


    M=T;//交接矩阵
    cout<<"转置后的稀疏矩阵为：\n";
    Output(M);
}


void TransposeMatrix2(Matrix &M)//转置矩阵算法2
{
    //算法描述：增加两个数组：num[M.linenum+1]与cpot[M.linenum+1]
    //num[line]：矩阵M第line列中非零元素的总个数；
    //cpot[line]：M中第line列当前非零元素在M.data[]中的下标（初始化为当前列中第一个非零元素的下标）
    //遍历一遍原矩阵，对当前遍历到的第index个元素，cpot[M.data[index].line]即为该元素在转置后的矩阵中
    //data数组中的下标，一步定位。
    Matrix T;
    T.rownum=M.linenum;
    T.linenum=M.rownum;
    T.elemnum=M.elemnum;


    if(T.elemnum)
    {
        int num[M.linenum+1];
        memset(num,0,sizeof(num));//初始化num数组
        for(int index=1; index<=M.elemnum; index++)//求num数组
        {
            num[M.data[index].line]++;
        }


        int cpot[M.linenum+1];
        int index=0;
        while(num[++index]==0);
        cpot[index]=1;//第一个该列中存在非零元素的列数在cpot中的值为1
        for(int index2=index+1; index2<=M.linenum; index2++)//递推求cpot数组
        {
            cpot[index2]=cpot[index2-1]+num[index2-1];
        }


        for(index=1; index<=M.elemnum; index++)
        {
            int line=M.data[index].line;
            int index1=cpot[line];//直接定位当前元素转置后在新矩阵data数组中的下标
            T.data[index1].row=M.data[index].line;
            T.data[index1].line=M.data[index].row;
            T.data[index1].elem=M.data[index].elem;
            cpot[line]++;//更新指示的位置
        }
    }


    M=T;
    cout<<"转置后的稀疏矩阵为：\n";
    Output(M);
}


void TransposeMatrix3(Matrix &M)//转置矩阵算法3
{
    //算法描述：不需要开辟新数组的内存，直接按照列优先的原则对
    //原矩阵的所有非零元素进行冒泡排序。排序后，对矩阵所有非零元素
    //交换行列数，即完成转置。
    SortByLine(M);//列优先排序


    for(int index=1; index<=M.elemnum; index++)
    {
        swap(M.data[index].line,M.data[index].row);//交换行列数
    }


    swap(M.linenum,M.rownum);
    cout<<"转置后的稀疏矩阵为：\n";
    Output(M);
}


void AddMatrix(Matrix &M1,Matrix &M2)//矩阵相加
{
    Matrix M;
    M.rownum=M1.rownum;
    M.linenum=M1.linenum;


    int index1=1,index2=1,index=1;
    for(int row=1; row<=M.rownum; row++)
    {
        for(int line=1; line<=M.linenum; line++)
        {
            if(Check(M1,index1,row,line)&&Check(M2,index2,row,line))
            {
                M.data[index].elem=M1.data[index1].elem+M2.data[index2].elem;
                M.data[index].row=row;
                M.data[index].line=line;
                index1++;
                index2++;
                index++;
            }
            else if(Check(M1,index1,row,line)&&!Check(M2,index2,row,line))
            {
                M.data[index].elem=M1.data[index1].elem;
                M.data[index].row=row;
                M.data[index].line=line;
                index1++;
                index++;
            }
            else if(!Check(M1,index1,row,line)&&Check(M2,index2,row,line))
            {
                M.data[index].elem=M2.data[index2].elem;
                M.data[index].row=row;
                M.data[index].line=line;
                index2++;
                index++;
            }
        }
    }
    M.elemnum=index-1;


    M1=M;
    Output(M);
    cout<<"相加后的矩阵是：\n";
    Output(M1);
}


void SubtractMatrix(Matrix &M1,Matrix &M2)//矩阵相减
{
    Matrix M;
    M.rownum=M1.rownum;
    M.linenum=M1.linenum;


    int index1=1,index2=1,index=1;
    for(int row=1; row<=M.rownum; row++)
    {
        for(int line=1; line<=M.linenum; line++)
        {
            if(Check(M1,index1,row,line)&&Check(M2,index2,row,line))
            {
                M.data[index].elem=M1.data[index1].elem-M2.data[index2].elem;
                M.data[index].row=row;
                M.data[index].line=line;
                index1++;
                index2++;
                index++;
            }
            else if(Check(M1,index1,row,line)&&!Check(M2,index2,row,line))
            {
                M.data[index].elem=M1.data[index1].elem;
                M.data[index].row=row;
                M.data[index].line=line;
                index1++;
                index++;
            }
            else if(!Check(M1,index1,row,line)&&Check(M2,index2,row,line))
            {
                M.data[index].elem=-M2.data[index2].elem;//此处变为其相反数
                M.data[index].row=row;
                M.data[index].line=line;
                index2++;
                index++;
            }
        }
    }
    M.elemnum=index-1;


    M1=M;
    cout<<"相减后的矩阵是：\n";
    Output(M1);
}


void MultiplyMatrix(Matrix &M,Matrix &N)//矩阵相乘
{
    //算法描述：先对矩阵N进行列优先排序（M已经为行优先）；
    // 在结果矩阵Q可能存在非零元素的情况下：
    //枚举Q的每一行row，每一列line，设Q在(row,line)处的值为temp，
    //在(row,line)下枚举矩阵M中行数等于row的所有元素M.data[index1]
    //在每个M.data[index1]下，枚举列数等于line的矩阵N 中的所有元素N.data[index3]，
    //对每个N.data[index3]，当N.data[index3].row等于M.data[index1].line时，两个元素位置匹配相乘即可，
    //累加到temp上（temp=temp+N.data[index3].elem*M.data[index1].elem）;
    //当前行列(row,line)遍历完成后，temp的值即可求出。
    //使用了四个下标：index1，index2，index3，index4
    //2和4是辅助更新的下标，详见程序。  9
    SortByLine(N);//对矩阵N进行列优先排序
    Matrix Q;
    Q.rownum=M.rownum;
    Q.linenum=N.linenum;
    Q.elemnum=0;


    int index=1;
    if(M.elemnum*N.elemnum)
    {
        int index1,index2=1;
        //index1是矩阵M的遍历器；
        //index2辅助更新M矩阵元素遍历起点，其值为矩阵M中第一个行数等于当前row的元素下标
        for(int row=1; row<=Q.rownum; row++)//枚举Q的每一行row
        {
            int index3,index4=1;
            //index3是矩阵N的遍历器；
            //index4辅助更新N矩阵元素遍历起点，其值为矩阵N中第一个列数等于当前line的元素下标
            for(int line=1; line<=Q.linenum; line++)//每一列line
            {
                int temp=0;//Q在(row,line)处的值
                for(index1=index2; index1<=M.elemnum&&M.data[index1].row==row; index1++)
                    //在index1不越界且M的第index1个元素在第row行的前提下遍历M的元素
                {
                    for(index3=index4; index3<=N.elemnum&&N.data[index3].line==line; index3++)
                        //在index3不越界且N的第index3个元素在第line列的前提下遍历N的元素
                    {
                        if(M.data[index1].line==N.data[index3].row)//两个元素位置匹配相乘即可
                        {
                            temp=temp+M.data[index1].elem*N.data[index3].elem;//累加到temp上
                        }
                    }


                    if(index1==M.elemnum||M.data[index1+1].row!=row)
                        //当矩阵M的所有在第row行的元素遍历完成一遍后（index1==M.elemnum针对矩阵M的最后一行）
                    {
                        index4=index3;
                        //此时N.data[index3].line=line+1，将该下标值复制到index4中，下次遍历下一列时无需从头开始
                    }
                }


                if(temp)
                {
                    Q.data[index].row=row;
                    Q.data[index].line=line;
                    Q.data[index].elem=temp;
                    index++;
                }


                if(line==Q.linenum)
                    //当矩阵Q的第row行求值完成后
                {
                    index2=index1;
                    //此时M.data[index1].row=row+1，将该下标值复制到index2中，下次遍历下一行时无需从头开始
                }
            }
        }
        Q.elemnum=index-1;
    }


    M=Q;
    cout<<"相乘后的稀疏矩阵为：\n";
    Output(M);
}


Status Check(Matrix M,int index,int row,int line)//检查矩阵M的数组data中第index个元素的行列数
{
    if(index<=M.elemnum&&M.data[index].row==row&&M.data[index].line==line)
    {
        return OK;
    }
    return FALSE;
}


void SortByRow(Matrix &M)//行优先冒泡排序
{
    if(M.elemnum)
    {
        for(int i=1; i<=M.elemnum; i++)
        {
            for(int j=i+1; j<=M.elemnum; j++)
            {
                if(M.data[i].row>M.data[j].row||(M.data[i].row==M.data[j].row&&M.data[i].line>M.data[j].line))
                {
                    swap(M.data[i],M.data[j]);
                }
            }
        }
    }
}


void SortByLine(Matrix &M)//列优先冒泡排序
{
    if(M.elemnum)
    {
        for(int i=1; i<=M.elemnum; i++)
        {
            for(int j=i+1; j<=M.elemnum; j++)
            {
                if(M.data[i].line>M.data[j].line||(M.data[i].line==M.data[j].line&&M.data[i].row>M.data[j].row))
                {
                    swap(M.data[i],M.data[j]);
                }
            }
        }
    }
}


void Interaction()//输出操作
{
    cout<<"请输入对应操作的序号：\n";
    cout<<"0：退出程序 ；\n";
    cout<<"1：建立稀疏矩阵 ；\n";
    cout<<"2：输出稀疏矩阵 ；\n";
    cout<<"3：转置稀疏矩阵 ；\n";
    cout<<"4：稀疏矩阵相加 ；\n";
    cout<<"5：稀疏矩阵相减；\n";
    cout<<"6：稀疏矩阵相乘 ；\n";
}