1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：QomolangmaH 分类：Toy博客 阅读(54) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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中的哪个元素？

结构体

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

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

初始化

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。

元素设置

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

元素获取

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。

打印矩阵

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。打印完一行后，换行继续打印下一行。

主函数

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 函数打印了下三角矩阵的内容。

输出结果

【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组,数据结构,数据结构,矩阵,线性代数,1024程序员节

代码整合

#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的计算公式，即可实现对称矩阵的压缩存储。
  要实现对称矩阵的压缩存储，只需要在上述下三角矩阵的压缩存储上稍作修改即可：

元素设置

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 数组中的索引，并将值赋给该位置的元素。

元素获取

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 数组中的索引，并返回相应位置的元素值。

主函数

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;
}

输出结果

【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组,数据结构,数据结构,矩阵,线性代数,1024程序员节文章来源地址https://www.toymoban.com/news/detail-720432.html

代码整合

#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;
}

到了这里，关于【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包