数据结构——矩阵压缩

发表于 2024-10-19 更新于 2025-06-12 分类于大二上，数据结构阅读次数：

数据结构——矩阵压缩

特殊矩阵的压缩

对称矩阵

关键点：

是选择上三角行主序存储还是下三角列主序存储
组的下标是从1开始还是0开始存储

三件矩阵

注意点：

理解下三角列序和下三角行序的差异，后者是计算a[i][j]后面的元素数量和，再用总数减去后面，得到前面元素数量；前者是直接计算a[i][j]前面元素数量
一位数组空间为n(n+1)/2+1，数组最后一位为0

对角矩阵

稀疏矩阵的压缩存储

三元组表

// 用于表示稀疏矩阵中非零元素的结构体
struct Triplet {
    int row;
    int col;
    int value;
};

// 用于表示稀疏矩阵的类
class SparseMatrix {
private:
    int rows;
    int cols;
    vector<Triplet> triplets; 

public:
    // 构造函数，用于初始化矩阵的维度
    SparseMatrix(int rows, int cols) : rows(rows), cols(cols) {}

    // 添加非零元素到矩阵的方法
    void add_element(int row, int col, int value) {
        if (value != 0) {
            triplets.push_back({ row, col, value });
        }
    }

    // 以三元组形式显示稀疏矩阵的方法
    void display() const {
        for (const auto& triplet : triplets) {
            cout << "行: " << triplet.row << ", 列: " << triplet.col << ", 值: " << triplet.value << endl;
        }
    }

    // 将稀疏矩阵转换为密集矩阵表示的方法
    vector<vector<int>> to_dense() const {
        vector<vector<int>> dense_matrix(rows, vector<int>(cols, 0));
        for (const auto& triplet : triplets) {
            dense_matrix[triplet.row][triplet.col] = triplet.value;
        }
        return dense_matrix;
    }
};

朴素转置

因为矩阵A的列是矩阵B的行，所以以此遍历A的列，将其存入新的三元组顺序表

不能直接交换i和j的值的原因：因为三元组表是行优先顺序，如果直接交换就是列优先

vector<Triplet> transposeTripletMatrix(const vector<Triplet>& tripletMatrix) {
    // 获取原始三元组矩阵的行数、列数和非零元素个数信息
    int rows = tripletMatrix[0].row;
    int cols = tripletMatrix[0].col;
    int numNonZero = tripletMatrix[0].value;

    // 创建转置矩阵的三元组顺序表
    vector<Triplet> transposedMatrix;
    transposedMatrix.push_back({cols, rows, numNonZero});

    // 通过列的顺序插入非零元素到转置矩阵中
    if (numNonZero > 0) {
        for (int col = 0; col < cols; ++col) {
            for (int i = 1; i <= numNonZero; ++i) {
                if (tripletMatrix[i].col == col) {
                    transposedMatrix.push_back({tripletMatrix[i].col, tripletMatrix[i].row, tripletMatrix[i].value});
                }
            }
        }
    }

    return transposedMatrix;
}

快速转置

vector<Triplet> fastTransposeTripletMatrix(const vector<Triplet>& tripletMatrix) {
    // 获取原始三元组矩阵的行数、列数和非零元素个数信息
    int rows = tripletMatrix[0].row;
    int cols = tripletMatrix[0].col;
    int numNonZero = tripletMatrix[0].value;

    // 创建转置矩阵的三元组顺序表
    vector<Triplet> transposedMatrix(numNonZero + 1);
    transposedMatrix[0] = {cols, rows, numNonZero};

    if (numNonZero > 0) {
        // 初始化每一列中非零元素的个数和位置
        vector<int> count(cols, 0);
        vector<int> index(cols + 1, 2);

        // 统计每一列中非零元素的个数
        for (int i = 1; i <= numNonZero; ++i) {
            count[tripletMatrix[i].col]++;
        }

        // 计算每一列在转置矩阵中的起始位置
        for (int i = 1; i < cols; ++i) {
            index[i + 1] = index[i] + count[i - 1];
        }

        // 填充转置矩阵的三元组顺序表
        for (int i = 1; i <= numNonZero; ++i) {
            int col = tripletMatrix[i].col;
            int pos = index[col];
            transposedMatrix[pos] = {tripletMatrix[i].col, tripletMatrix[i].row, tripletMatrix[i].value};
            index[col]++;
        }
    }

    return transposedMatrix;
}

十字链表

定义

类中定义了两个链表数组，用于存储每一行和每一列的头节点指针

// 节点定义
struct OLNode {
    int row;         // 行号
    int col;         // 列号
    int value;       // 元素值
    OLNode* right;   // 指向右边的节点
    OLNode* down;    // 指向下面的节点

    OLNode(int r, int c, int val) : row(r), col(c), value(val), right(nullptr), down(nullptr) {}
};

// 十字链表类
class OrthogonalList {
private:
    int rows, cols;
    vector<OLNode*> row_heads; // 行头链表数组
    vector<OLNode*> col_heads; // 列头链表数组
}

构造函数

row_heads.resize(rows, nullptr); 是用于调整 row_heads 向量的大小，使其包含 rows 个元素，并将每个元素初始化为 nullptr。

OrthogonalList(int rows, int cols) : rows(rows), cols(cols) {
        row_heads.resize(rows, nullptr);
        col_heads.resize(cols, nullptr);
    }

插入函数

// 插入元素
void insert(int r, int c, int value) {
    if (value == 0) return;

    // 检查是否已存在节点，若存在则更新值
    OLNode* current = row_heads[r];
    while (current && current->col < c) {
        current = current->right;
    }
    if (current && current->col == c) {
        current->value = value; // 更新已有节点的值
        return;
    }

    OLNode* newNode = new OLNode(r, c, value);

    // 插入到行链表中
    if (!row_heads[r]) {
        //如果该行没有头节点，则成为该行头节点
        row_heads[r] = newNode;
    }
    else {
        current = row_heads[r];
        OLNode* prev = nullptr;
        //current向下遍历，直到遍历到该行链表的最后一个，或者到达插入的列的位置
        //注意，该插入方式如果遇到该位置已有节点存在的情况，会用新节点覆盖旧节点
        while (current && current->col < c) {
            prev = current;
            current = current->right;
        }
        //若prev存在，则说明头节点不为零，若为空则说明插在链表最前面
        if (prev) {
            prev->right = newNode;
        }
        else {
            row_heads[r] = newNode;
        }
        newNode->right = current;
    }

    // 插入到列链表中
    if (!col_heads[c]) {
        col_heads[c] = newNode;
    }
    else {
        current = col_heads[c];
        OLNode* prev = nullptr;
        while (current && current->row < r) {
            prev = current;
            current = current->down;
        }
        if (prev) {
            prev->down = newNode;
        }
        else {
            col_heads[c] = newNode;
        }
        newNode->down = current;
    }
}

打印函数

   // 打印矩阵
    void print() {
        for (int i = 0; i < rows; ++i) {
            OLNode* current = row_heads[i];
            for (int j = 0; j < cols; ++j) {
                if (current && current->col == j) {
                    cout << current->value << " ";
                    current = current->right;
                } else {
                    cout << "0 ";
                }
            }
            cout << endl;
        }
    }
};