十字链表储存稀疏矩阵及稀疏矩阵相乘 C代码

下面是用十字链表储存稀疏矩阵和实现稀疏矩阵相乘的 C 代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义十字链表节点
typedef struct {
    int row;  // 行下标
    int col;  // 列下标
    int value;  // 元素值
    struct Node* right;  // 指向右边的节点
    struct Node* down;  // 指向下方的节点
} Node;

// 定义十字链表
typedef struct {
    int rows;  // 矩阵的行数
    int cols;  // 矩阵的列数
    Node* row_heads;  // 行头节点数组
    Node* col_heads;  // 列头节点数组
} CrossList;

// 创建稀疏矩阵对应的十字链表
CrossList* createCrossList(int rows, int cols) {
    CrossList* matrix = (CrossList*)malloc(sizeof(CrossList));
    matrix->rows = rows;
    matrix->cols = cols;
    matrix->row_heads = (Node*)malloc(rows * sizeof(Node));
    matrix->col_heads = (Node*)malloc(cols * sizeof(Node));
    
    // 初始化头节点数组
    for (int i = 0; i < rows; i++) {
        matrix->row_heads[i].right = NULL;
        matrix->row_heads[i].down = NULL;
    }
    
    for (int j = 0; j < cols; j++) {
        matrix->col_heads[j].right = NULL;
        matrix->col_heads[j].down = NULL;
    }
    
    return matrix;
}

// 向十字链表中插入元素
void insertElement(CrossList* matrix, int row, int col, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->row = row;
    newNode->col = col;
    newNode->value = value;
    
    // 插入新节点到行链表中
    Node* row_head = &(matrix->row_heads[row]);
    Node* cur = row_head;
    while (cur->right != NULL && cur->right->col < col) {
        cur = cur->right;
    }
    newNode->right = cur->right;
    cur->right = newNode;
    
    // 插入新节点到列链表中
    Node* col_head = &(matrix->col_heads[col]);
    cur = col_head;
    while (cur->down != NULL && cur->down->row < row) {
        cur = cur->down;
    }
    newNode->down = cur->down;
    cur->down = newNode;
}

// 打印稀疏矩阵的十字链表表示
void printCrossList(CrossList* matrix) {
    for (int i = 0; i < matrix->rows; i++) {
        Node* node = matrix->row_heads[i].right;
        for (int j = 0; j < matrix->cols; j++) {
            if (node != NULL && node->col == j) {
                printf("%d ", node->value);
                node = node->right;
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
}

// 稀疏矩阵相乘
CrossList* multiplySparseMatrix(CrossList* matrix1, CrossList* matrix2) {
    if (matrix1->cols != matrix2->rows) {
        printf("Cannot multiply the matrices!");
        return NULL;
    }
    
    CrossList* result = createCrossList(matrix1->rows, matrix2->cols);
    
    for (int i = 0; i < matrix1->rows; i++) {
        Node* row_head = &(matrix1->row_heads[i]);
        Node* node1 = row_head->right;
        
        for (int j = 0; j < matrix2->cols; j++) {
            Node* col_head = &(matrix2->col_heads[j]);
            Node* node2 = col_head->down;
            
            int value = 0;
            while (node1 != NULL && node2 != NULL) {
                if (node1->col < node2->row) {
                    node1 = node1->right;
                } else if (node1->col > node2->row) {
                    node2 = node2->down;
                } else {
                    value += node1->value * node2->value;
                    node1 = node1->right;
                    node2 = node2->down;
                }
            }
            
            if (value != 0) {
                insertElement(result, i, j, value);
            }
        }
    }
    
    return result;
}

// 测试代码
int main() {
    CrossList* matrix1 = createCrossList(3, 3);
    insertElement(matrix1, 0, 0, 1);
    insertElement(matrix1, 0, 2, 2);
    insertElement(matrix1, 1, 1, 3);
    insertElement(matrix1, 2, 0, 4);
    insertElement(matrix1, 2, 2, 5);
    
    CrossList* matrix2 = createCrossList(3, 3);
    insertElement(matrix2, 0, 0, 1);
    insertElement(matrix2, 0, 1, 2);
    insertElement(matrix2, 1, 1, 3);
    insertElement(matrix2, 1, 2, 4);
    insertElement(matrix2, 2, 0, 5);
    
    CrossList* result = multiplySparseMatrix(matrix1, matrix2);
    printf("Result:\n");
    printCrossList(result);
    
    return 0;
}

这段代码实现了稀疏矩阵的十字链表存储以及稀疏矩阵的乘法操作。你可以根据需要修改矩阵的大小和元素值进行测试。