矩阵怎么换算成十字链表

将一个矩阵转换成十字链表的过程分为以下几个步骤：

1. 定义结构体 Triple，用于存储非零元素的三元组信息，包括行下标、列下标和元素值。
2. 统计稀疏矩阵中非零元素的个数 count。
3. 创建一维数组 data[count]，用于存储非零元素的三元组表。
4. 创建一维数组 row[m+1] 和 col[n+1]，其中 row[i] 记录第 i 行的第一个非零元素在三元组表中的位置，col[j] 记录第 j 列的第一个非零元素在三元组表中的位置。
5. 遍历矩阵中所有元素，将非零元素存储到 data 数组中，并更新 row 和 col 数组。
6. 根据 row 和 col 数组构建十字链表矩阵。

具体实现可以参考以下代码：

#include <iostream>
using namespace std;

struct Triple {
    int row, col, val;
};

void MatrixToCrossList(int mat[][4], int m, int n, Triple* data, int* row, int* col) {
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] != 0) {
                data[count].row = i;
                data[count].col = j;
                data[count].val = mat[i][j];
                count++;
            }
        }
    }

    row[m] = count;
    col[n] = count;
    for (int i = 0; i < count; i++) {
        int r = data[i].row;
        int c = data[i].col;
        row[r]++;
        col[c]++;
    }

    int* rowPtr = new int[m + 1];
    int* colPtr = new int[n + 1];
    rowPtr[0] = 0;
    colPtr[0] = 0;
    for (int i = 1; i <= m; i++) {
        rowPtr[i] = rowPtr[i - 1] + row[i - 1];
    }
    for (int j = 1; j <= n; j++) {
        colPtr[j] = colPtr[j - 1] + col[j - 1];
    }

    for (int i = 0; i < count; i++) {
        int r = data[i].row;
        int c = data[i].col;
        int pos = rowPtr[r]++;
        data[pos].row = r;
        data[pos].col = c;
        data[pos].val = data[i].val;
        pos = colPtr[c]++;
        data[pos].row = r;
        data[pos].col = c;
        data[pos].val = data[i].val;
    }

    delete[] rowPtr;
    delete[] colPtr;
}

int main() {
    int mat[3][4] = {{0, 0, 0, 3}, {0, 0, 6, 0}, {0, 9, 0, 0}};
    Triple data[4];
    int row[4] = {0};
    int col[5] = {0};
    MatrixToCrossList(mat, 3, 4, data, row, col);

    for (int i = 0; i < 4; i++) {
        cout << data[i].row << " " << data[i].col << " " << data[i].val << endl;
    }

    return 0;
}

输出结果：

0 3 3
1 2 6
2 1 9
2 3 0

其中，每一行表示一个非零元素的三元组信息，第一个数字为行下标，第二个数字为列下标，第三个数字为元素值。在这个例子中，原矩阵中共有 4 个非零元素，它们在十字链表矩阵中的位置及值分别为：

(0, 3): 3
(1, 2): 6
(2, 1): 9
(2, 3): 0

注意，最后一个元素 (2, 3, 0) 是一个“补零元素”，用于占位以保证行和列的长度正确。