多维数组和广义表应用——参照课本P124、125实现稀疏矩阵的两种转置算法。

在C语言中，多维数组和广义表（也称为动态数组或链表）可以用来有效地处理稀疏矩阵。因为稀疏矩阵的主要特点是大部分元素为0，所以存储时通常不需要像常规矩阵那样占用大量空间。

**1. 用一维数组表示稀疏矩阵的转置（压缩存储）**

这种方法通常采用两个一维数组，一个存放行索引（下标），另一个存放对应的值。对于原矩阵中的元素A[i][j]，在转置后的矩阵中，其值放在新的数组中，位置是(A[j])[i]。课本可能建议使用哈希表或位图辅助查找，以便快速找到非零元素的位置。

typedef struct {
    int *row_indices;
    int *col_values;
    int row_count; // 原矩阵的行数
    int col_count; // 原矩阵的列数
} SparseMatrix;

// 转置函数
void transposeSparse(int **sparse, SparseMatrix *transpose) {
    for (int i = 0; i < sparse[0]->col_count; i++) {
        for (int j = 0; j < sparse->row_count; j++) {
            if (sparse[j][i]) { // 找到非零元素
                transpose->row_indices[transpose->row_count++] = i;
                transpose->col_values[transpose->row_count - 1] = sparse[j][i];
            }
        }
    }
}

**2. 使用广义表（动态数组）实现稀疏矩阵转置**

这里你可以用链表来表示每个元素，节点包含值、行号和列号。转置就是构建一个新的链表，其中原来的列成为新的行，反之亦然。

typedef struct Node {
    int value;
    int row;
    int col;
    struct Node* next;
} Node;

typedef struct {
    Node* first;
    int row_count;
    int col_count;
} SparseList;

// 转置函数
void transposeSparseList(SparseList *sparse, SparseList *transpose) {
    SparseList temp;
    for (Node *node = sparse->first; node != NULL; node = node->next) {
        transpose->first = createNode(node->col, node->value, transpose->first);
    }
    transpose->row_count = sparse->col_count;
    transpose->col_count = sparse->row_count;
}

// 创建新节点的辅助函数
Node* createNode(int row, int value, Node* head) {
    Node* newNode = malloc(sizeof(Node));
    newNode->value = value;
    newNode->row = row;
    newNode->col = 0; // 新的列由旧的行决定
    newNode->next = head;
    return newNode;
}

**相关问题：**
1. 如何利用一维数组更高效地存储稀疏矩阵？
2. 在使用广义表时，如何保证转置后数据结构的合理性？
3. 为什么要分别处理非零元素和空元素？
4. 如何优化这两个方法的空间复杂度？