如何在压缩稀疏行中通过索引查找元素？

Question

我正在尝试用 Java 编写一个使用稀疏矩阵的程序，并且我已经编写了一个类来使用 CRS 格式存储它。给定类的问题部分是 get_element() 方法必须按索引返回元素。索引作为用户输入被接收。每次我输入索引时，我都会得到 0。尽管结果应该不同。也许问题出在构造函数内部。我不知道。

import java.util.Scanner;
import java.util.ArrayList;

public class CRS {
    
    private ArrayList<Integer> A = new ArrayList<Integer>();
    private ArrayList<Integer> LJ = new ArrayList<Integer>();
    private ArrayList<Integer> LI = new ArrayList<Integer>();
    
    public CRS(int[][] matrix) {
        int n = 0;
        for(int i=0;i<10*main.N;i++) {
            for(int j=0;j<10*main.N;j++) {
                if(matrix[i][j]!=0) {
                    A.add(matrix[i][j]);
                    LJ.add(j+1);
                    n++;
                }
            }
            LI.add(n);
        }
        LI.add(main.N+1);
    }
    
    public void print_all() {
        System.out.println("\nCRS");
        System.out.print("A ");
        for(int i=0;i<main.N;i++) {
            System.out.print(A.get(i)+" ");
        }
        System.out.print("\nLJ ");
        for(int i=0;i<main.N;i++) {
            System.out.print(LJ.get(i)+" ");
        }
        System.out.print("\nLI ");
        for(int i=0;i<LI.size();i++) {
            System.out.print(LI.get(i)+" ");
        }
    }
    
    public int get_element() {
        System.out.println("\n\nSearching for an element");
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter i:");
        int i = sc.nextInt();
        System.out.println("Enter j:");
        int j = sc.nextInt();
        int AA = 0;
        int N1=LI.get(i);
        int N2=LI.get(i+1);
        for(int k=N1;k<N2;k++) {
            if(LJ.get(k)==j) {
                AA=A.get(k);
            }
        }
        return AA;
    }
}

这是主类。

import java.io.*;
import java.util.*;

public class main {
    public static int N=2;

    public static void main(String[] args) {
        
        int [][] matrix = new int [10*N] [10*N];
        for(int n=0;n<N;) {
            int max_position=10*N-1;
            int min_value=1,max_value=12;
            int i = (int)(Math.random() * (max_position + 1));
            int j = (int)(Math.random() * (max_position + 1));
            if(matrix[i][j]==0) {
                matrix[i][j] = min_value + (int)(Math.random() * ((max_value - min_value) + 1));
                n++;
            }
        }
        System.out.println("Sparce matrix");
        for(int i=0;i<10*N;i++) {
            for(int j=0;j<10*N;j++) {
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
        
        CRS crs = new CRS(matrix);
        crs.print_all();
        System.out.println(crs.get_element());
    }

}

Answer 1

据我所知，您的代码有两个问题。

首先，在

get_element()

中

LI

的索引不正确:

public int get_element() {
    System.out.println("\n\nSearching for an element");
    
    Scanner sc = new Scanner(System.in);
    
    System.out.print("Enter i:");
    int i = sc.nextInt();
    
    System.out.print("Enter j:");
    int j = sc.nextInt();
    
    int AA = 0;
    
    // Correct indexing
    int N1 = LI.get(i - 1); 
    int N2 = LI.get(i);
    
    for (int k = N1; k < N2; k++) {
        if (LJ.get(k) == j) {
            AA = A.get(k);
        }
    }
    
    sc.close();
    
    return AA;
}

注意： 使用

scanner.close()

来防止程序中的内存泄漏非常重要。
注²：

System.out.print()

比

System.out.println()

更适合输入情况

其次，您应该在

main.N

构造函数中正确设置

CRS

值：

private List<Integer> A = new ArrayList<Integer>();
private List<Integer> LJ = new ArrayList<Integer>();
private List<Integer> LI = new ArrayList<Integer>();

public CRS(int[][] matrix) {
    int n = 0;
    for (int i = 0; i < 10 * main.N; i++) {
        for (int j = 0; j < 10 * main.N; j++) {
            if (matrix[i][j] != 0) {
                A.add(matrix[i][j]);
                LJ.add(j + 1);
                n++;
            }
        }
        LI.add(n);
    }
    LI.add(main.N * 10 + 1);
}

注意： 实例化数组时，最好使用接口 (

List<Integer>

) 而不是类，检查一下。