面试题：C++ 指针与多维数组在复杂数据结构中的深度应用

1. 数据结构设计

我们可以设计一个结构体来表示稀疏矩阵中的非零元素，然后使用指针和多维数组来管理这些元素。

#include <iostream>
#include <vector>
#include <stdexcept>

// 定义稀疏矩阵元素结构体
struct SparseMatrixElement {
    int row;
    int col;
    int value;
    SparseMatrixElement(int r, int c, int v) : row(r), col(c), value(v) {}
};

// 定义稀疏矩阵类
class SparseMatrix {
private:
    int rows;
    int cols;
    std::vector<SparseMatrixElement> elements;

public:
    // 构造函数
    SparseMatrix(int r, int c) : rows(r), cols(c) {}

    // 创建矩阵（添加非零元素）
    void createElement(int row, int col, int value) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            throw std::out_of_range("Index out of range");
        }
        elements.emplace_back(row, col, value);
    }

    // 元素访问
    int accessElement(int row, int col) const {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            throw std::out_of_range("Index out of range");
        }
        for (const auto& elem : elements) {
            if (elem.row == row && elem.col == col) {
                return elem.value;
            }
        }
        return 0;
    }

    // 矩阵乘法
    SparseMatrix multiply(const SparseMatrix& other) const {
        if (cols != other.rows) {
            throw std::invalid_argument("Matrix dimensions do not match for multiplication");
        }
        SparseMatrix result(rows, other.cols);

        for (const auto& a : elements) {
            for (const auto& b : other.elements) {
                if (a.col == b.row) {
                    int newRow = a.row;
                    int newCol = b.col;
                    int newValue = a.value * b.value;

                    // 检查结果矩阵中是否已存在该位置的元素
                    bool found = false;
                    for (auto& resElem : result.elements) {
                        if (resElem.row == newRow && resElem.col == newCol) {
                            resElem.value += newValue;
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        result.elements.emplace_back(newRow, newCol, newValue);
                    }
                }
            }
        }
        return result;
    }

    // 打印矩阵（调试用）
    void printMatrix() const {
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                std::cout << accessElement(i, j) << " ";
            }
            std::cout << std::endl;
        }
    }
};

2. 内存使用优化

使用结构体数组：通过仅存储非零元素，相比于传统的多维数组，大大减少了内存使用。因为传统多维数组无论元素是否为零，都需要占用内存空间。
动态内存管理：使用 std::vector 来存储非零元素，std::vector 会自动管理内存，在添加或删除元素时动态调整内存大小，避免了手动内存管理的复杂性和内存泄漏风险。

3. 矩阵乘法效率优化

减少无效计算：在矩阵乘法实现中，只对非零元素进行乘法运算。通过遍历两个稀疏矩阵的非零元素，只有当 a.col == b.row 时才进行乘法运算并累加结果，避免了对零元素的无效乘法操作，从而提高了算法效率。

4. 内存管理和异常处理

内存管理：std::vector 负责管理 SparseMatrixElement 对象的内存，自动分配和释放内存，无需手动进行 new 和 delete 操作，减少了内存泄漏的可能性。
异常处理：
- 在 createElement 和 accessElement 函数中，通过检查索引是否在有效范围内，若超出范围则抛出 std::out_of_range 异常。
- 在 multiply 函数中，检查矩阵维度是否匹配，若不匹配则抛出 std::invalid_argument 异常，确保了函数调用的合法性和安全性。

你可以通过以下方式测试这个类：

int main() {
    try {
        SparseMatrix a(2, 3);
        a.createElement(0, 0, 1);
        a.createElement(0, 1, 2);
        a.createElement(1, 2, 3);

        SparseMatrix b(3, 2);
        b.createElement(0, 0, 4);
        b.createElement(1, 1, 5);
        b.createElement(2, 1, 6);

        SparseMatrix result = a.multiply(b);
        result.printMatrix();
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }
    return 0;
}

星途面试题库

面试题：C++ 指针与多维数组在复杂数据结构中的深度应用

知识考点

面试题答案

1. 数据结构设计

2. 内存使用优化

3. 矩阵乘法效率优化

4. 内存管理和异常处理