【数据结构】稀疏矩阵运算器（加、减、乘）

阳光穿透心脏的1/2处 2022-04-15 04:50 342阅读 0赞

### 问题描述 ###

稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器

### 基本要求 ###

以“带行逻辑连接信息”的三元组顺序表表示系数矩阵，实现两个矩阵相加、相减和想乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵以通常阵列形式列出

### 运行截图 ###

数据输入

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]  
输出结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70 1]

### 代码实现 ###

import java.util.Arrays;
    import java.util.Scanner;
    
    public class matrixTest {
        
        public static void main(String[] args) throws Exception {
        
            Matrix M = new Matrix();
            System.out.println("创建矩阵M：");
            M.CreateMatrix();
            Matrix N = new Matrix();
            System.out.println("创建矩阵N：");
            N.CreateMatrix();
            System.out.println("M：");
            M.PrintMatrix();
            System.out.println("N: ");
            N.PrintMatrix();
            Matrix Q = Matrix.add(M,N);
            System.out.println("M+N:");
            Q.PrintMatrix();
            Q = Matrix.sub(M,N);
            System.out.println("M-N:");
            Q.PrintMatrix();
            Q = Matrix.multiply(M,N);
            System.out.println("M*N: ");
            Q.PrintMatrix();
        }
    }
    class  Triple{
         //三元组
        int i,j;//非零元的行下标和列下标
        int e;//非零元的数值
    }
    class Matrix{
        
        Triple[] triples;//非零元三组表
        int mu,nu,tu;//矩阵的行数列数和非零元的个数
        int[] rops;//各行第一个非零元的在tripls数组里的位置表
        public void CreateMatrix() throws Exception{
        
            Scanner in = new Scanner(System.in);
            System.out.println("请输入矩阵的行数、列数，以及非零元的个数");
            mu = in.nextInt();
            nu = in.nextInt();
            tu = in.nextInt();
            if(tu>mu*nu) throw new Exception("输入非法，非零元个数大于矩阵元素的个数");
            triples = new Triple[tu+1];
            Arrays.fill(triples,null);
            rops = new int[mu+1];
            Arrays.fill(rops,0);//快速初始化rops数组，将rops数组里的值都致为0
            System.out.println("请依次输入非零元所在的行数、列数，以及数值,需要按照行的顺序输入");
            /** 这里规定非零元的顺序需要按照行的顺序输入的原因是：
            *要满足:
             *    rpos[row]指示的是矩阵的第row行的第一个非零元在triples里的序号，
             *    rpos[row+1]-1指向矩阵的第row行的最后一个非零元在triples里的序号
             * 这样就要满足非零元是按照行的顺序排列的
             */
            for (int k =1; k <=tu; k++) {
        
                Triple triple = new Triple();
                triple.i = in.nextInt();
                triple.j = in.nextInt();
                triple.e = in.nextInt();
                if(triple.i<=0||triple.j<=0) {
        
                    System.out.println("输入非法，行数和列数必须为正数,请重新输入");
                    k--;
                    continue;
                }
                else if (triple.e==0){
        
                    System.out.println("输入非法，非零元不能为0,请重新输入");
                    k--;
                    continue;
                }
                else{
        
                    triples[k]=triple;
                    if (rops[triple.i]==0)
                        rops[triple.i] =k;//记录每行第一个非零元的位置(只会在当前行有非零行的情况下记录)
                                                               //
                }
            }
            for (int k=mu;k>=1;k--){
         //处理那些没有非零元的行
                if (rops[k]==0){
        
                    if (k==mu)
                        rops[k]=tu+1;//如果最后一行没有非零元,需要特殊处理
                    else
                        rops[k]=rops[k+1];
                }
            }
        }
        public void PrintMatrix(){
        
            //以行列式形式输出矩阵
            int k=1;
            for (int r=1;r<=mu;r++){
        
                for(int c=1;c<=nu;c++){
        
    
                    if (k<=tu&&r==triples[k].i&&c==triples[k].j){
        
                        System.out.printf("%4d ",triples[k].e);
                        k++;
                    }
                    else
                        System.out.print("   0 ");
                }
                System.out.println();
            }
            System.out.println();
        }
        public static Triple copy(Triple t){
        
            //赋值函数，把传进来的对象的数据域复制给一个新建的对象，并把新建的对象返回
            Triple copy = new Triple();
            copy.i = t.i;
            copy.j = t.j;
            copy.e = t.e;
            return  copy;
        }
        public static Matrix add(Matrix M,Matrix N){
        
            if (M.mu==N.nu&&M.nu==N.nu){
         //两个矩阵的行数和列数相等才能相加
                Matrix Q = new Matrix();//Q存放 M+N 的结果
                Q.triples = new Triple[M.tu+N.tu+1];
                Q.mu=M.mu;
                Q.nu=M.nu;
                Q.tu=0;
                int m,n,k;
                m=n=k=1;
                while (m<=M.tu&&n<=N.tu) {
        //依次遍历M和N的三元组
                    if (M.triples[m].i < N.triples[n].i) {
         // 比较两个矩阵的行数，行数小的先放到Q的三元组里
                        Q.triples[k] = copy( M.triples[m]);
                        m++;
                    } else if (M.triples[m].i > N.triples[n].i) {
        
                        Q.triples[k] = copy(N.triples[n]);
                        n++;
                    } else {
         //行数都相等时，比较列的大小
                        if (M.triples[m].j < N.triples[n].j) {
         //列数小的放到Q的三元组里
                            Q.triples[k] = copy(M.triples[m]);
                            m++;
                        } else if (M.triples[m].j > N.triples[n].j) {
        
                            Q.triples[k] = copy(N.triples[n]);
                            n++;
                        } else {
         //行数、列数都相等的情况下
                            if (M.triples[m].e + N.triples[n].e != 0) {
         //如果对应位置的元素相加不等于0，则相加，并放到Q的三元组里
                                Q.triples[k] = copy(M.triples[m]);
                                Q.triples[k].e = M.triples[m].e + N.triples[n].e;
                                m++;
                                n++;
                            } else {
         //如果相加等于0，相当于该位置变为零元，则跳过
                                m++;
                                n++;
                                continue;
                            }
                        }
                    }
                    k++;
                    Q.tu++;
                }
                while (m<=M.tu){
         //M中剩余的三元组逐一放进Q中
                    Q.triples[k] = copy(M.triples[m]);
                    m++;
                    k++;
                    Q.tu++;
                }
                while (n<=N.tu){
        //N中剩余的三元组逐一放进Q中
                    Q.triples[k]=copy(N.triples[n]);
                    n++;
                    k++;
                    Q.tu++;
                }
                return Q;
            }else{
         //如果两个矩阵的行数和列数不相等
                System.out.println("这两个矩阵不能相加");
                return null;
            }
        }
        public static Matrix sub(Matrix M,Matrix N){
         //M-N
            /*
            * 因为前面已经实现M+N的方法，而M-N可以看做 M+(-N)
            * 所以只要把N的非零元都置成相反数，然后在进行M+N，就能实现M-N了
            * */
            if (M.mu==N.mu&&M.nu==N.nu){
        
                Matrix newN = new Matrix();//用newN存放N的非零元置成相反数后的矩阵
                newN.mu = N.mu;
                newN.nu = N.nu;
                newN.tu = N.tu;
                newN.triples = new Triple[newN.tu+1];
                for (int k =1;k<=newN.tu;k++){
        
                    newN.triples[k]=copy(N.triples[k]);
                    newN.triples[k].e =-newN.triples[k].e;
                }
                return add(M,newN);
            }else{
        
                System.out.println("这两个矩阵不能相减");
                return null;
            }
        }
        public static  Matrix multiply(Matrix M,Matrix N){
        
            if (M.nu!=N.mu){
         //如果M的列数不等于N的行数
                System.out.println("这两个矩阵不能相乘");
                return null;
            }
            Matrix Q = new Matrix();//初始化Q
            Q.mu = M.mu;
            Q.nu = N.nu;
            Q.triples = new Triple[Q.mu*Q.nu+1];//非零元的个数最多为矩阵的元素个数
            Q.tu = 0;
            if(M.tu*N.tu!=0){
        //如果M和N的非零元都不等于0
                int arow;//乘积元素在Q中的行号
                int ccol;//乘积元素在Q中的列号
                int brow;//对N当前行的每一个非零元对应在N中的行号
                int[] ctemp = new int[N.nu+1];//Q 中各行元素值累加器，ctemp[0]不用
                int tp,tq;
                for (arow=1;arow<=M.mu;arow++){
        //处理M的每一行
                    Arrays.fill(ctemp,0);//初始化Q中行元素值计数器
                    if(arow<M.mu)
                        tp = M.rops[arow+1];//tp指向M的当前行的下一行的第一个非零元的位置
                    else
                        tp = M.tu+1;
                    for (int p =M.rops[arow];p<tp;p++){
         //p指向M的当前行的第一个非零元的位置，并开始累加，直到下一行的第一个非零元tp为止
                        brow = M.triples[p].j;//对N当前行的每一个非零元，找到对应在N中的行号
                        if (brow<N.mu)
                            tq = N.rops[brow+1];//tq指向N当前行的下一行第一个非零元位置
                        else
                            tq = N.tu+1;
                        for (int q = N.rops[brow];q<tq;q++){
        //q指向N的当前行的第一个非零元的位置，并开始累加，直到下一行的第一个非零元tq为止
                            ccol =N.triples[q].j;//乘积元素在Q中的列号
                            ctemp[ccol] +=M.triples[p].e*N.triples[q].e;
    
                        }
                    }//Q中第arow行元素已求出
                    for (ccol=1;ccol<=Q.nu;ccol++){
         //设置Q中第arow的三元组
                        if (ctemp[ccol]!=0){
         //如果不是零元
                            Q.tu++;
                            Triple triple = new Triple();
                            triple.i = arow;
                            triple.j = ccol;
                            triple.e = ctemp[ccol];
                            Q.triples[Q.tu] = triple;
                        }
                    }
                }
    
            }
            return Q;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]: /images/20220415/dac591877ab847ac9ee494ed2f9953ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70 1]: /images/20220415/9ea641136f6e4644a7a36c0032af7297.png