【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组

4.2.1 矩阵的数组表示

【数据结构】数组和字符串（一）：矩阵的数组表示

4.2.2 特殊矩阵的压缩存储

  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储，会出现大量存储空间存放重复信息或零元素的情况，这样会造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。

• 对角矩阵：指除了主对角线以外的元素都为零的矩阵，即对 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主对角线上有非零元素，只需存储主对角线上的元素即可。
• 三角矩阵：指上三角或下三角的元素都为零的矩阵。同样地，只需存储其中一部分非零元素，可以节省存储空间。
• 对称矩阵：指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律，可以只存储其中一部分元素，从而减少存储空间。
• 稀疏矩阵：指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素，因此采用压缩存储的方法更为合适。常见的压缩存储方法有：压缩稠密行（CSR）、压缩稠密列（CSC）、坐标列表（COO）等。

a. 对角矩阵的压缩存储

【数据结构】数组和字符串（二）：特殊矩阵的压缩存储：对角矩阵——一维数组

b. 三角矩阵的压缩存储

  三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上三角矩阵，当且仅当i > j时有M(i, j)=0 . 方阵M是下三角矩阵，当且仅当i < j时有M(i,j)=0 。这里以下三角矩阵为例，讨论其压缩存储方法：

  考虑一个n×n维下三角矩阵，其第一行至多有1个非零元素，第二行至多有2个非零元素，……，第n行至多有n个非零元素，非零元素至多共有(1 2 … n) = n(n 1)/2个。可以用大小为n(n 1)/2的一维数组来存储下三角矩阵，换言之，就是要把下三角矩阵M的非零元素映射到一个一维数组d中。映射次序可采用按行优先或按列优先。

• 假设映射采取按行优先，非零元素M(i, j)会映射到一维数组d中的哪个元素？
  • 设元素M(i, j)前面有k个非零元素，则k可计算如下：
    • k = 1 2 … （i-1） （j-1）= i(i-1)/2 j-1
• 假设映射采取按列优先，非零元素M(i, j)会映射到一维数组d中的哪个元素？

结构体

代码语言：javascript复制

typedef struct {
    int size;       // 矩阵的维度
    int elements[MAX_SIZE];  // 存储下三角元素的数组
} LowerTriangularMatrix;

  结构体 LowerTriangularMatrix，包含两个成员变量：size 表示矩阵的维度，elements 是一个一维数组，用于存储下三角矩阵的元素。接下来，代码实现了几个函数来进行下三角矩阵的初始化、元素设置、元素获取以及打印矩阵的操作。

初始化

代码语言：javascript复制

void initialize(LowerTriangularMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化下三角元素数组
    for (int i = 0; i < size * (size   1) / 2; i  ) {
        matrix->elements[i] = 0;
    }
}

initialize 函数用于初始化下三角矩阵，接受一个指向 LowerTriangularMatrix 结构体的指针以及矩阵的维度作为参数。它将矩阵的维度存储在 size 成员变量中，并将 elements 数组中的所有元素初始化为 0。

元素设置

代码语言：javascript复制

void setElement(LowerTriangularMatrix *matrix, int row, int col, int value) {
    if (row < col) {
        printf("Error: Only elements in or below the main diagonal can be set.n");
    } else if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        int index = row * (row   1) / 2   col; // 计算压缩存储的索引
        matrix->elements[index] = value;
    }
}

setElement 函数用于设置下三角矩阵中指定位置的元素值。

• 它接受一个指向 LowerTriangularMatrix 结构体的指针，以及要设置的元素的行、列索引和值作为参数。
• 在设置元素之前，它会进行一些错误检查，例如判断行列索引是否有效以及是否在下三角矩阵的主对角线或以下。如果检查通过，它会计算出在压缩存储中的索引，并将指定位置的元素值设置为给定的值。

元素获取

代码语言：javascript复制

int getElement(LowerTriangularMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else if (row < col) {
        return 0;
    } else {
        int index = row * (row   1) / 2   col; // 计算压缩存储的索引
        return matrix->elements[index];
    }
}

getElement 函数用于获取下三角矩阵中指定位置的元素值。

• 它接受一个指向 LowerTriangularMatrix 结构体的指针，以及要获取的元素的行、列索引作为参数。
• 在获取元素之前，它也会进行行列索引的有效性检查。
  • 如果索引无效，它会打印错误消息并返回 0。
  • 如果指定位置在下三角矩阵的主对角线或以下，它会计算出在压缩存储中的索引，并返回相应的元素值。
  • 如果指定位置在主对角线以上，表示该位置应为零，因此直接返回 0。

打印矩阵

代码语言：javascript复制

void printMatrix(LowerTriangularMatrix *matrix) {
    for (int i = 0; i < matrix->size; i  ) {
        for (int j = 0; j < matrix->size; j  ) {
            printf("%d ", getElement(matrix, i, j));
        }
        printf("n");
    }
}

printMatrix 函数用于打印下三角矩阵。函数使用嵌套的循环遍历矩阵的所有行和列。对于每个位置，如果行索引大于等于列索引，表示该位置存在元素，需要打印 elements 数组中对应的值；否则，表示该位置不存在元素，打印 0。打印完一行后，换行继续打印下一行。

主函数

代码语言：javascript复制

int main() {
    LowerTriangularMatrix matrix;
    int size = 4;

    initialize(&matrix, size);

    setElement(&matrix, 0, 0, 1);
    setElement(&matrix, 1, 0, 2);
    setElement(&matrix, 1, 1, 3);
    setElement(&matrix, 2, 0, 4);
    setElement(&matrix, 2, 1, 5);
    setElement(&matrix, 2, 2, 6);
    setElement(&matrix, 3, 0, 7);
    setElement(&matrix, 3, 1, 8);
    setElement(&matrix, 3, 2, 9);
    setElement(&matrix, 3, 3, 10);

    printf("Lower Triangular Matrix:n");
    printMatrix(&matrix);

    return 0;
}

  在 main 函数中，首先创建了一个 LowerTriangularMatrix 结构体变量 matrix，并指定矩阵的维度为 4。然后，通过调用 initialize 函数初始化了矩阵。接下来，通过多次调用 setElement 函数设置了矩阵中的各个元素的值。最后，调用 printMatrix 函数打印了下三角矩阵的内容。

输出结果

代码整合

代码语言：javascript复制

#include <stdio.h>

#define MAX_SIZE 100

// 定义下三角矩阵结构体
typedef struct {
    int size;       // 矩阵的维度
    int elements[MAX_SIZE];  // 存储下三角元素的数组
} LowerTriangularMatrix;

// 初始化下三角矩阵
void initialize(LowerTriangularMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化下三角元素数组
    for (int i = 0; i < size * (size   1) / 2; i  ) {
        matrix->elements[i] = 0;
    }
}

// 设置下三角矩阵中指定位置的元素值
void setElement(LowerTriangularMatrix *matrix, int row, int col, int value) {
    if (row < col) {
        printf("Error: Only elements in or below the main diagonal can be set.n");
    } else if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        int index = row * (row   1) / 2   col; // 计算压缩存储的索引
        matrix->elements[index] = value;
    }
}

// 获取下三角矩阵中指定位置的元素值
int getElement(LowerTriangularMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else if (row < col) {
        return 0;
    } else {
        int index = row * (row   1) / 2   col; // 计算压缩存储的索引
        return matrix->elements[index];
    }
}

// 打印下三角矩阵
void printMatrix(LowerTriangularMatrix *matrix) {
    for (int i = 0; i < matrix->size; i  ) {
        for (int j = 0; j < matrix->size; j  ) {
            printf("%d ", getElement(matrix, i, j));
        }
        printf("n");
    }
}

int main() {
    LowerTriangularMatrix matrix;
    int size = 4;

    initialize(&matrix, size);

    setElement(&matrix, 0, 0, 1);
    setElement(&matrix, 1, 0, 2);
    setElement(&matrix, 1, 1, 3);
    setElement(&matrix, 2, 0, 4);
    setElement(&matrix, 2, 1, 5);
    setElement(&matrix, 2, 2, 6);
    setElement(&matrix, 3, 0, 7);
    setElement(&matrix, 3, 1, 8);
    setElement(&matrix, 3, 2, 9);
    setElement(&matrix, 3, 3, 10);

    printf("Lower Triangular Matrix:n");
    printMatrix(&matrix);

    return 0;
}

c. 对称矩阵的压缩存储

  n×n方阵M是对称矩阵，当且仅当对任意 i , j (1≤ i , j ≤ n)，均有M(i, j) = M( j, i) 。   因为对称矩阵中M(i, j)与M(j, i)的信息相同，所以只需存储其上三角部分或下三角部分的元素信息。这里参照下三角矩阵的压缩存储方法，即用大小为n(n 1)/2的一维数组来存储，关于对称矩阵中的下三角部分的元素M(i, j) (i ≥ j) ，与下三角矩阵压缩存储的映射公式一样，映射到d[k]（其中k= i(i-1)/2 ( j-1) ）；关于对称矩阵之上三角部分的元素M(i, j)（i< j，不包含对角线上的元素），因其元素值与下三角部分的M(j, i)相同，故应映射到下标为q的元素d[q]中（其中q=j(j-1)/2 (i-1) ）。 有了k和q的计算公式，即可实现对称矩阵的压缩存储。   要实现对称矩阵的压缩存储，只需要在上述下三角矩阵的压缩存储上稍作修改即可：

元素设置

代码语言：javascript复制

void setElement(SymmetricMatrix *matrix, int row, int col, int value) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        // 交换行和列的位置，确保 row <= col
        if (row > col) {
            int temp = row;
            row = col;
            col = temp;
        }

        int index = row * matrix->size   col - (row * (row   1) / 2); // 计算压缩存储的索引
        matrix->elements[index] = value;
    }
}

setElement 函数用于设置对称矩阵中指定位置的元素值。

• 在设置元素之前，会进行一些边界检查，并通过交换行和列的位置，确保 row <= col。
• 然后根据压缩存储的方式计算出对应位置在 elements 数组中的索引，并将值赋给该位置的元素。

元素获取

代码语言：javascript复制

int getElement(SymmetricMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else {
        // 交换行和列的位置，确保 row <= col
        if (row > col) {
            int temp = row;
            row = col;
            col = temp;
        }

        int index = row * matrix->size   col - (row * (row   1) / 2); // 计算压缩存储的索引
        return matrix->elements[index];
    }
}

getElement 函数用于获取对称矩阵中指定位置的元素值。

• 同样进行边界检查，并通过交换行和列的位置，确保 row <= col。
• 然后根据压缩存储的方式计算出对应位置在 elements 数组中的索引，并返回相应位置的元素值。

主函数

代码语言：javascript复制

int main() {
    SymmetricMatrix matrix;
    int size = 4;  // 假设对称矩阵的维度为4

    initialize(&matrix, size);

    // 设置对称矩阵的元素值
    setElement(&matrix, 0, 0, 1);
    setElement(&matrix, 1, 1, 2);
    setElement(&matrix, 2, 2, 3);
    setElement(&matrix, 1, 0, 4);
    setElement(&matrix, 2, 0, 5);
    setElement(&matrix, 2, 1, 6);

    // 打印对称矩阵
    printMatrix(&matrix);

    return 0;
}

输出结果

代码整合

代码语言：javascript复制

#include <stdio.h>

#define MAX_SIZE 100

// 定义对称矩阵结构体
typedef struct {
    int size;               // 矩阵的维度
    int elements[MAX_SIZE]; // 存储对称矩阵元素的数组
} SymmetricMatrix;

// 初始化对称矩阵
void initialize(SymmetricMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化对称矩阵元素数组
    for (int i = 0; i < size * (size   1) / 2; i  ) {
        matrix->elements[i] = 0;
    }
}

// 设置对称矩阵中指定位置的元素值
void setElement(SymmetricMatrix *matrix, int row, int col, int value) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        // 交换行和列的位置，确保 row <= col
        if (row > col) {
            int temp = row;
            row = col;
            col = temp;
        }

        int index = row * matrix->size   col - (row * (row   1) / 2); // 计算压缩存储的索引
        matrix->elements[index] = value;
    }
}

// 获取对称矩阵中指定位置的元素值
int getElement(SymmetricMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else {
        // 交换行和列的位置，确保 row <= col
        if (row > col) {
            int temp = row;
            row = col;
            col = temp;
        }

        int index = row * matrix->size   col - (row * (row   1) / 2); // 计算压缩存储的索引
        return matrix->elements[index];
    }
}

// 打印对称矩阵
void printMatrix(SymmetricMatrix *matrix) {
    for (int i = 0; i < matrix->size; i  ) {
        for (int j = 0; j < matrix->size; j  ) {
            printf("%d ", getElement(matrix, i, j));
        }
        printf("n");
    }
}

int main() {
    SymmetricMatrix matrix;
    int size = 4;  // 假设对称矩阵的维度为3

    initialize(&matrix, size);

    // 设置对称矩阵的元素值
    setElement(&matrix, 0, 0, 1);
    setElement(&matrix, 1, 1, 2);
    setElement(&matrix, 2, 2, 3);
    setElement(&matrix, 1, 0, 4);
    setElement(&matrix, 2, 0, 5);
    setElement(&matrix, 2, 1, 6);

    // 打印对称矩阵
    printMatrix(&matrix);

    return 0;
}

数组 压缩 字符串 存储 数据结构

0 人点赞