稀疏矩阵的十字链表法

稀疏矩阵的十字链表法是一种用于表示稀疏矩阵的数据结构。它将矩阵中的非零元素存储在一个带表头的环形链表中，每一行和每一列都有一个对应的链表。同时，还有一个带表头的环形链表存储所有的表头结点，其中表头结点的row和col分别代表总行数和总列数。这种数据结构可以实现稀疏矩阵的加法、减法、乘法、转置、求最值、插入、查看、删除等基本功能。菜单栏采用hash表存储稀疏矩阵，给每个矩阵存储一个名字，hash函数进行寻找。通过这种方法，可以有效地节省存储空间，并且提高了矩阵运算的效率。

相关问题

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();
    }
}

c++稀疏矩阵的十字链表

以下是C++中稀疏矩阵的十字链表实现：

#include<iostream>
using namespace std;

// 十字链表结构体
typedef struct OLNode{
    int i, j; // 该非零元素的行列下标
    int e; // 该非零元素的值
    struct OLNode *right, *down; // 该非零元素所在行列链表的后继指针
}OLNode, *OLink;

typedef struct{
    OLink *rhead, *chead; // 行列链表头指针数组
    int m, n, k; // 稀疏矩阵的行数、列数、非零元素个数
}CrossList;

// 创建稀疏矩阵的十字链表
void CreateSMatrix_OL(CrossList &M){
    int m, n, k;
    cout << "请输入稀疏矩阵的行数、列数、非零元素个数：" << endl;
    cin >> m >> n >> k;
    M.m = m;
    M.n = n;
    M.k = k;
    M.rhead = new OLink[m+1]; // 行链表头指针数组
    M.chead = new OLink[n+1]; // 列链表头指针数组
    for(int i=1; i<=m; i++){
        M.rhead[i] = NULL;
    }
    for(int j=1; j<=n; j++){
        M.chead[j] = NULL;
    }
    cout << "请按行序输入每个非零元素的行、列、值：" << endl;
    for(int i=1; i<=k; i++){
        int row, col, value;
        cin >> row >> col >> value;
        OLink p = new OLNode;
        p->i = row;
        p->j = col;
        p->e = value;
        // 插入到行链表中
        if(M.rhead[row] == NULL || M.rhead[row]->j > col){
            p->right = M.rhead[row];
            M.rhead[row] = p;
        }
        else{
            OLink pre = M.rhead[row];
            while(pre->right && pre->right->j < col){
                pre = pre->right;
            }
            p->right = pre->right;
            pre->right = p;
        }
        // 插入到列链表中
        if(M.chead[col] == NULL || M.chead[col]->i > row){
            p->down = M.chead[col];
            M.chead[col] = p;
        }
        else{
            OLink pre = M.chead[col];
            while(pre->down && pre->down->i < row){
                pre = pre->down;
            }
            p->down = pre->down;
            pre->down = p;
        }
    }
}

// 输出稀疏矩阵的十字链表
void PrintSMatrix_OL(CrossList M){
    cout << "稀疏矩阵的十字链表为：" << endl;
    for(int i=1; i<=M.m; i++){
        OLink p = M.rhead[i];
        for(int j=1; j<=M.n; j++){
            if(p && p->j == j){
                cout << p->e << " ";
                p = p->right;
            }
            else{
                cout << "0 ";
            }
        }
        cout << endl;
    }
}

int main(){
    CrossList M;
    CreateSMatrix_OL(M);
    PrintSMatrix_OL(M);
    return 0;
}