java实现稀疏矩阵十字链表储存

以下是Java实现稀疏矩阵十字链表储存的示例代码：

//定义节点类
class OLNode {
    int row, col;
    int val;
    OLNode right, down;
}

//定义十字链表类
class CrossList {
    int rows, cols, nums;
    OLNode[] rowHeads, colHeads;

    //构造函数
    public CrossList(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;
        rowHeads = new OLNode[rows];
        colHeads = new OLNode[cols];

        //初始化行列头节点
        for (int i = 0; i < rows; i++) {
            rowHeads[i] = new OLNode();
            rowHeads[i].row = i;
            rowHeads[i].right = rowHeads[i];
        }
        for (int j = 0; j < cols; j++) {
            colHeads[j] = new OLNode();
            colHeads[j].col = j;
            colHeads[j].down = colHeads[j];
        }

        //遍历矩阵，创建节点并插入十字链表
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    OLNode node = new OLNode();
                    node.row = i;
                    node.col = j;
                    node.val = matrix[i][j];

                    //插入行链表
                    OLNode p = rowHeads[i];
                    while (p.right != rowHeads[i] && p.right.col < j) {
                        p = p.right;
                    }
                    node.right = p.right;
                    p.right = node;

                    //插入列链表
                    p = colHeads[j];
                    while (p.down != colHeads[j] && p.down.row < i) {
                        p = p.down;
                    }
                    node.down = p.down;
                    p.down = node;

                    nums++;
                }
            }
        }
    }

    //打印十字链表
    public void print() {
        for (int i = 0; i < rows; i++) {
            OLNode p = rowHeads[i].right;
            for (int j = 0; j < cols; j++) {
                if (p != rowHeads[i] && p.col == j) {
                    System.out.print(p.val + " ");
                    p = p.right;
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
    }
}

//测试代码
public class Main {
    public static void main(String[] args) {
        int[][] matrix = {{1, 0, 0, 0}, {0, 2, 0, 0}, {0, 0, 3, 0}, {0, 0, 0, 4}};
        CrossList crossList = new CrossList(matrix);
        crossList.print();
    }
}