当前位置：首页 > C++ > 正文

C++十字链表详解（稀疏矩阵高效存储与操作指南）

主机测评网
C++
2025-12-16
711

在处理大规模稀疏矩阵（即大部分元素为零的矩阵）时，传统的二维数组会浪费大量内存。为了高效地存储和操作这类数据，C++十字链表是一种非常经典且实用的数据结构。本教程将从零开始，手把手教你理解并实现十字链表，即使你是编程小白也能轻松上手！

什么是十字链表？

十字链表（Orthogonal List）是用于表示稀疏矩阵的一种链式存储结构。它结合了行链表和列链表的优点：每个非零元素既属于某一行，也属于某一列，通过两个指针分别链接同行和同列的其他非零元素，形成“十字”交叉结构。

C++十字链表详解（稀疏矩阵高效存储与操作指南） C++十字链表稀疏矩阵存储 C++数据结构十字链表实现第1张

十字链表的节点结构

每个节点需要包含以下信息：

row：元素所在行号
col：元素所在列号
value：元素的值
right：指向同一行下一个非零元素的指针
down：指向同一列下一个非零元素的指针

此外，我们还需要两个辅助数组：rowHead 和 colHead，分别记录每行和每列的第一个非零元素。

C++代码实现

下面我们用 C++ 实现一个完整的十字链表类，支持插入非零元素和打印矩阵。

#include <iostream>#include <vector>using namespace std;// 十字链表节点class OLNode {public:    int row, col;    int value;    OLNode* right; // 指向同行下一个非零元    OLNode* down;  // 指向同列下一个非零元    OLNode(int r, int c, int v) : row(r), col(c), value(v), right(nullptr), down(nullptr) {}};class CrossList {private:    vector<OLNode*> rowHead; // 行头指针数组    vector<OLNode*> colHead; // 列头指针数组    int rows, cols, nums;     // 矩阵行数、列数、非零元个数public:    CrossList(int r, int c) : rows(r), cols(c), nums(0) {        rowHead.resize(rows, nullptr);        colHead.resize(cols, nullptr);    }    // 插入一个非零元素    void insert(int r, int c, int val) {        if (r < 0 || r >= rows || c < 0 || c >= cols || val == 0) return;        OLNode* newNode = new OLNode(r, c, val);        // 插入到行链表中（按列号升序）        if (!rowHead[r] || rowHead[r]->col > c) {            newNode->right = rowHead[r];            rowHead[r] = newNode;        } else {            OLNode* p = rowHead[r];            while (p->right && p->right->col < c) {                p = p->right;            }            newNode->right = p->right;            p->right = newNode;        }        // 插入到列链表中（按行号升序）        if (!colHead[c] || colHead[c]->row > r) {            newNode->down = colHead[c];            colHead[c] = newNode;        } else {            OLNode* p = colHead[c];            while (p->down && p->down->row < r) {                p = p->down;            }            newNode->down = p->down;            p->down = newNode;        }        nums++;    }    // 打印稀疏矩阵（以二维形式展示）    void printMatrix() {        cout << "\n稀疏矩阵（" << rows << "x" << cols << "）:\n";        for (int i = 0; i < rows; ++i) {            for (int j = 0; j < cols; ++j) {                int val = 0;                OLNode* p = rowHead[i];                while (p && p->col <= j) {                    if (p->col == j) {                        val = p->value;                        break;                    }                    p = p->right;                }                cout << val << "\t";            }            cout << endl;        }    }    // 析构函数（可选，用于释放内存）    ~CrossList() {        for (int i = 0; i < rows; ++i) {            OLNode* p = rowHead[i];            while (p) {                OLNode* temp = p;                p = p->right;                delete temp;            }        }    }};// 示例使用int main() {    CrossList matrix(4, 5);    // 插入非零元素    matrix.insert(0, 1, 3);    matrix.insert(1, 2, 7);    matrix.insert(2, 0, 5);    matrix.insert(2, 3, 9);    matrix.insert(3, 4, 2);    matrix.printMatrix();    return 0;}