1.数组、矩阵和广义表

发表于 | 分类于
字数统计: 434 | 阅读时长 ≈ 2

数组

在内存中的一块连续的存储空间，是最常用的数据结构

优点

  1. 支持随机访问
  2. 查找元素效率高：O(1)

缺点

  1. 增加、删除元素效率低：O(n)

常见操作

  1. 遍历

    1
    for(i = 0; i < n; i++){}

  2. 双指针

  3. 快慢指针

矩阵（二维数组）

形式如下：

1
2
3
4
[[a₀₀, a₀₁, a₀₂, ... , a₀n]
 [a₁₀, a₁₁, a₁₂, ... , a₁n]
 ...
 [an₀, an₁, an₂, ... , ann]]

优缺点同上

常见操作

  1. 矩阵转置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /*
     * This function transforms the A matrix into the B matrix.
    */
    void tranmat(int A[][maxSize], int B[][maxSize], int m, int n)
    {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                B[j][i] = A[i][j];
            }
        }
    }

  2. 矩阵相加

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /*
     * This function adds the A matrix to the B matrix and returns the C matrix.
    */
    void addmat(int C[][maxSize], int A[][maxSize], int B[][maxSize], int m, int n)
    {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = A[i][j] + B[i][j];
            }
        }
    }

  3. 矩阵相乘

    矩阵相乘的前提是A的行数 = B的列数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /*
     * This function multiples the A matrix by the B matrix and returns the C matrix.
     * A : m*n, B : n*k
    */
    void multmat(int C[][maxSize], int A[][maxSize], int B[][maxSize], int m, int n, int k)
    {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                C[i][j] = 0;
                for (int h = 0; h < n; h++) {
                    C[i][j] += A[i][h] + B[h][j];
                }
            }
        }
    }

特殊矩阵和稀疏矩阵

  1. 对称矩阵
    aij = aji
  2. 三角矩阵
    • 上三角阵
    • 下三角阵
  3. 对角矩阵
    主对角线及其上下两条线上存在数据，其他全为C
  4. 稀疏矩阵
    非零元素占少数，0占大多数的矩阵。

广义表

表内元素可以是原子或广义表的一种线性表的扩展元素。