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

文章目录

  • 4.2.1 矩阵的数组表示
  • 4.2.2 特殊矩阵的压缩存储
    • a. 对角矩阵的压缩存储
    • b. 三角矩阵的压缩存储
      • 结构体
      • 初始化
      • 元素设置
      • 元素获取
      • 打印矩阵
      • 主函数
      • 输出结果
      • 代码整合
    • c. 对称矩阵的压缩存储
      • 元素设置
      • 元素获取
      • 主函数
      • 输出结果
      • 代码整合

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/103569.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

GEE案例——一个完整的火灾监测案例dNBR差异化归一化烧毁指数

差异化归一化烧毁指数 dNBR是"差异化归一化烧毁指数"的缩写。它是一种用于评估卫星图像中烧毁区域严重程度的遥感指数。dNBR值通过将火灾前的归一化烧毁指数(NBR)减去火灾后的NBR来计算得出。该指数常用于野火监测和评估。 dNBR(差异化归一化烧毁指数)是一种用…

EMC简述01

电磁兼容性&#xff08;EMC&#xff1a;Electromagnetic Compatibility&#xff09; 电磁兼容性&#xff08;EMC&#xff09;主要分为两种 一种是设备本身的电磁噪声对其他设备或人体带来的影响&#xff08;电磁干扰&#xff0c;EMI&#xff1a;Electromagnetic Interference…

计算机算法分析与设计(20)---回溯法(0-1背包问题)

文章目录 1. 题目描述2. 算法思路3. 例题分析4. 代码编写 1. 题目描述 对于给定的 n n n 个物品&#xff0c;第 i i i 个物品的重量为 W i W_i Wi​&#xff0c;价值为 V i V_i Vi​&#xff0c;对于一个最多能装重量 c c c 的背包&#xff0c;应该如何选择放入包中的物品…

轻量级导出 Excel 标准格式

一般业务系统中都有导出到 Excel 功能&#xff0c;其实质就是把数据库里面一条条记录转换到 Excel 文件上。Java 常用的第三方类库有 Apache POI 和阿里巴巴开源的 EasyExcel 等。另外也有通过 Web 模板技术渲染 Excel 文件导出&#xff0c;这实质是 MVC 模式的延伸&#xff0c…

React环境初始化

环境初始化 学习目标&#xff1a; 能够独立使用React脚手架创建一个React项目 1.使用脚手架创建项目 官方文档&#xff1a;(https://create-react-app.bootcss.com/)    - 打开命令行窗口    - 执行命令      npx create-react-app projectName    说明&#xff1a…

智安网络|探索语音合成技术的未来:揭秘人工智能配音技术的背后

随着人工智能技术的迅猛发展&#xff0c;配音行业也迎来了人工智能配音技术的崭新时代。人工智能配音技术通过语音合成和自然语言处理等技术手段&#xff0c;实现了逼真的语音合成&#xff0c;为影视、广告和游戏等领域带来了新的可能性。 第一部分&#xff1a;语音合成技术的…

天锐绿盾加密软件——企业数据透明加密、防泄露系统

天锐绿盾是一种企业级数据透明加密、防泄密系统&#xff0c;旨在保护企业的核心数据&#xff0c;防止数据泄露和恶意攻击。它采用内核级透明加密技术&#xff0c;可以在不影响员工正常工作的前提下&#xff0c;对需要保护的数据进行加密操作。 PC访问地址&#xff1a; https:/…

linux安装visual studio code

下载 https://code.visualstudio.com/ 下载.deb文件 安装 假如文件被下载到了 /opt目录下 进入Opt目录&#xff0c;右键从当前目录打开终端。 输入下面的安装命令。 sudo apt-get install ./code_1.83.1-1696982868_amd64.deb 安装成功。 配置 打开 visual studio cod…

宏集案例 | Panarama SCADA平台在风电场测量的应用,实现风电场的高效管理!

文章来源&#xff1a;宏集工业物联网 阅读原文&#xff1a;https://mp.weixin.qq.com/s/MLYhBWiWx7qQSApx_3xhmA 宏集Panorama SCADA平台在风电场测量的应用 宏集方案 01应用背景 随着煤碳、石油等能源的逐渐枯竭&#xff0c;人类越来越重视可再生能源的利用。风能作为一种…

小知识(5) el-table行样式失效问题

一、实现效果 子级呈现不同颜色去区分 二、最初代码 tips: 我这里使用的vue3 elementplus <el-table :row-class-name"tableRowClassName" >... </el-table>function tableRowClassName({ row, rowIndex }) {if (row.children.length 0) {return …

上海市道路数据,有63550条数据(shp格式和xlsx格式)

数据地址&#xff1a; 上海市道路https://www.xcitybox.com/datamarketview/#/Productpage?id391 基本信息. 数据名称: 上海市道路数据 数据格式: Shpxlsx 数据时间: 2020年 数据几何类型: 线 数据坐标系: WGS84坐标系 数据来源&#xff1a;网络公开数据 数据字段&am…

k8s-----19、Helm

Helm 1、引入2、概述2.1 重点2.2 V3版本的Helm2.2.1 与之前版本的不同之处2.2.2 V3版本的运行流程 3、安装和配置仓库、一些附带操作3.1 安装3.2 配置仓库3.3 常用命令3.4 添加helm的自动补齐 4、快速部署应用(weave应用)5、 自行创建Chart5.1 Chart目录内容解析5.2 简单安装部…

Pytorch指定数据加载器使用子进程

torch.utils.data.DataLoader(train_dataset, batch_sizebatch_size, shuffleTrue,num_workers4, pin_memoryTrue) num_workers 参数是 DataLoader 类的一个参数&#xff0c;它指定了数据加载器使用的子进程数量。通过增加 num_workers 的数量&#xff0c;可以并行地读取和预处…

maven-default-http-blocker (http://0.0.0.0/): Blocked mirror for repositories

前言 略 说明 新设备上安装了mvn 3.8.5&#xff0c;编译新项目出错&#xff1a; [ERROR] Non-resolvable parent POM for com.admin.project:1.0: Could not transfer artifact com.extend.parent:pom:1.6.9 from/to maven-default-http-blocker (http://0.0.0.0/): Bl…

建联合作1000+达人,如何高效管理?

随着社交媒体的发展&#xff0c;达人营销已成为品牌营销重要的方式之一&#xff0c;甚至可以说是必选项。 对于很多品牌商家来说&#xff0c;一次合作几百个不同类型、不同社媒平台的达人&#xff0c;已屡见不鲜。在电商大促前、主推单品爆品时&#xff0c;同时合作上千个达人&…

jenkins实践篇(1)——基于分支的自动发布

问题背景 想起初来公司时&#xff0c;我们还是在发布机上直接执行发布脚本来运行和部署服务&#xff0c;并且正式环境和测试环境的脚本都在一起&#xff0c;直接手动操作脚本时存在比较大的风险就是将环境部署错误&#xff0c;并且当时脚本部署逻辑还没有检测机制&#xff0c;…

vscode Coder Runner 运行C++

1. 设置Code Runner 2. 防止输入读不到&#xff0c;把在终端运行勾上。 3. 设置minw/bin的环境变量 安装mingw教程&#xff1a;https://blog.csdn.net/fancy_male/article/details/133992000 4. 见图

数据结构:选择题+编程题(每日一练)

目录 选择题&#xff1a; 题一&#xff1a; 题二&#xff1a; 题三&#xff1a; 题四&#xff1a; 题五&#xff1a; 编程题&#xff1a; 题一&#xff1a;单值二叉树 思路一&#xff1a; 题二&#xff1a;二叉树的最大深度 思路一&#xff1a; 本人实力有限可能对…

Go学习第八章——面向“对象”编程(结构体与方法)

Go面向“对象”编程&#xff08;结构体与方法&#xff09; 1 结构体1.1 快速入门1.2 内存解析1.3 创建结构体四种方法1.4 注意事项和使用细节 2 方法2.1 方法的声明和调用2.2 快速入门案例2.3 调用机制和传参原理2.4 注意事项和细节2.5 方法和函数区别 3 工厂模式 Golang语言面…