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

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

时间：2023-11-19 22:31:28浏览次数：36  
标签：size matrix int 矩阵 数组 数据结构 col row

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

输出结果

在这里插入图片描述

代码整合

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

输出结果

在这里插入图片描述

代码整合

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

标签：size,matrix,int,矩阵,数组,数据结构,col,row
From： https://blog.51cto.com/u_16363537/8475974

相关文章

  • C语言【数组】
    C语言【数组】一、数组的一些零碎的知识1、数组在内存中的空间是连续的，数组下标从0开始；数组中存储的类型是一致的（只能存储同一类型，这样可以快速定位某元素）2、指针可看作存储地址的变量，数组名可看作地址那个常量，所以数组名不可修改。可以改的是数组元素：a[0]或*a二、一维数......
  • 【Java基础】异或特点+交换变量数值+数组反转
    异或特点二进制位不同为true，相同为false一个数被另外一个数异或两次，该数不变交换变量数值利用上述异或第2个特点实现交换两个整数类型变量数值代码publicclassXor{publicstaticvoidmain(String[]args){inta=10,b=4;a=a^b;......
  • 数组相关知识的梳理
    数组相关知识的梳理一维数组定义inta[100];inta[]={1,2,6,5};总之，要让计算机识别出要给定义的数组多少的容量输入与输出多多使用循环结构输入Eg.inti,a[100];charch;for(i=0;i<=l0;i++){scanf("%d%c",&a[i],&ch);}输出Eg.for(i=0;i<=10;i++)......
  • 【Java基础】数组的动态初始化
    数组动态初始化：手动指定数组长度，系统为数组自动分配默认初始化值格式：数据类型[]数组名=new数据类型[长度];默认值的分类：整数：0小数：0.0布尔：false字符：'\u0000'（Unicode字符，常见的体现是空白字符）引用数据类型（数组、类、接口）：null......
  • STL和基本数据结构
    STL和基本数据结构一、vector用法：vector是STL的动态数组。圆桌问题ProblemDescription圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围......
  • 第11讲 矩阵空间、秩 1 矩阵和小世界图
    转载至：超详细MIT线性代数公开课笔记......
  • 并非所有的大括号都表示数组
    问题：下图中的公式为什么错误。解决：单元格中输入的“{3,5,8}”并非数组，而是一个文本字符串，不具备数组功能。可以改成以下公式：{=IF(SUM(N(A2=EVALUATE(C$1))),"OK","")}=IF(SUM(N(A2=--(0&TEXTSPLIT(C$1,{"{","}",","})))),"OK","")=IF(COUNTI......
  • 【教3妹学编程-算法题】三个无重叠子数组的最大和
    2哥 :3妹，咋啦？一副苦大仇深的样子？3妹：不开心呀不开心，羽生结弦宣布离婚。2哥 :羽生什么？3妹：羽生结弦！2哥 :什么结弦？3妹：羽生结弦！！！2哥：羽生结弦是谁？他离婚关你啥事啊？3妹：你不知道，他是日本著名花滑运动员，前几个月刚宣布结婚，没想到这么快就离了。真是短时间内震惊我两次！2哥 :哎，人家怎......
  • 矩阵
    矩阵顾名思义就是一个小破方阵类似这样0011010101110000这就是一个四行四列的矩阵,矩阵包含三个信息,长度,宽度,数值数值就是矩阵里每一位上的数值,通常用一个数值来存为了方便使用我们常写成结构体形式定义structMat{ intl,r;//长,宽 int......
  • 数组原生方法
    数组和字符串的转换方法：toString()、toLocalString()、join()其中join()方法可以指定转换为字符串时的分隔符。数组尾部操作的方法pop()和push()，push方法可以传入多个参数。数组首部操作的方法shift()和unshift()重排序的方法reverse()和sort()，sort()方法可以传入一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99