【数据结构】数组和字符串（五）：特殊矩阵的压缩存储：稀疏矩阵——压缩稀疏行（CSR）

2023-10-28 20:01
文章标签 数组 数据结构 字符串 特殊 存储 压缩 矩阵 csr 稀疏

本文主要是介绍【数据结构】数组和字符串（五）：特殊矩阵的压缩存储：稀疏矩阵——压缩稀疏行（CSR），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 4.2.1 矩阵的数组表示
  • 4.2.2 特殊矩阵的压缩存储
    • a. 对角矩阵的压缩存储
    • b~c. 三角、对称矩阵的压缩存储
    • d. 稀疏矩阵的压缩存储——三元组表
    • e. 压缩稀疏行（Compressed Sparse Row，CSR）矩阵
      • 结构体
      • 创建CSR矩阵
      • 元素设置
      • 初始化
      • 打印矩阵
      • 销毁CSR矩阵
      • 主函数
      • 代码整合

4.2.1 矩阵的数组表示

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

4.2.2 特殊矩阵的压缩存储

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

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

a. 对角矩阵的压缩存储

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

b~c. 三角、对称矩阵的压缩存储

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

d. 稀疏矩阵的压缩存储——三元组表

【数据结构】数组和字符串（四）：特殊矩阵的压缩存储：稀疏矩阵——三元组表

e. 压缩稀疏行（Compressed Sparse Row，CSR）矩阵

  压缩稀疏行（Compressed Sparse Row，CSR）是一种常用的稀疏矩阵存储格式。CSR存储格式通过压缩非零元素的行指针和列索引，以及存储非零元素的值，来有效地表示稀疏矩阵。它包含以下几个关键组成部分：

  • row_ptr（行指针数组）：它是一个长度为rows + 1的数组，用于存储每一行在col_indices和elements数组中的起始索引位置。row_ptr[i]表示第i行的元素在col_indices和elements数组中的起始位置，而row_ptr[i+1] - row_ptr[i]表示第i行的非零元素个数。
  • col_indices（列索引数组）：它是一个长度为num_elements的数组，用于存储每个非零元素对应的列索引。col_indices[i]表示第i个非零元素所在的列索引。
  • elements（元素数组）：它是一个长度为num_elements的数组，用于存储每个非零元素的值。elements[i]表示第i个非零元素的值。

  CSR存储格式的主要优点是有效地压缩了稀疏矩阵的存储空间，只存储非零元素及其对应的行和列信息。此外，CSR格式还支持高效的稀疏矩阵向量乘法和稀疏矩阵乘法等操作。

结构体

typedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;

  • Element 结构体表示矩阵中的一个元素，包含三个成员变量：row（行索引）、col（列索引）和 value（元素值）。

  • CSRMatrix 结构体表示一个CSR矩阵，包含了矩阵的行数 rows、列数 cols、非零元素的个数 num_elements，以及三个指针成员变量 elements、row_ptr 和 col_indices。

创建CSR矩阵

CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows = rows;matrix.cols = cols;matrix.num_elements = num_elements;matrix.elements = (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr = (int*)malloc((rows + 1) * sizeof(int));matrix.col_indices = (int*)malloc(num_elements * sizeof(int));return matrix;
}
  • createCSRMatrix 函数用于创建一个CSR矩阵。
  • 接受矩阵的行数、列数和非零元素的个数作为参数，并返回创建的CSR矩阵。
  • 在函数内部，通过动态内存分配分别为 elements、row_ptr 和 col_indices 分配内存空间，并将 row_ptr 数组的所有元素初始化为0，最后返回创建的矩阵。

元素设置

void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row < 0 || row >= matrix->rows) {printf("Invalid row index.\n");return;}int index = matrix->row_ptr[row];matrix->elements[index].row = row;matrix->elements[index].col = col;matrix->elements[index].value = value;matrix->col_indices[index] = col;matrix->row_ptr[row]++;  // 递增索引值
}

  setElement 函数可用于设置（修改）CSR矩阵中某个位置的元素值。

  • 接受一个指向CSR矩阵的指针 matrix，以及要设置的元素的行索引、列索引和值作为参数。
  • 在函数内部，首先检查行索引是否有效，如果无效则打印错误信息并返回。
  • 然后，根据行索引找到对应行的起始位置，将元素的行索引、列索引和值分别赋给对应的矩阵元素，并更新 col_indices 数组和 row_ptr 数组中的值。

初始化

void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i = 0; i < num_elements; i++) {matrix->elements[i].value = values[i];matrix->elements[i].row = row_indices[i];matrix->elements[i].col = col_indices[i];matrix->col_indices[i] = col_indices[i];matrix->row_ptr[row_indices[i]]++;}int sum = 0;for (int i = 0; i <= matrix->rows; i++) {int temp = matrix->row_ptr[i];matrix->row_ptr[i] = sum;sum += temp;}
}

  initializeCSRMatrix 函数用于初始化CSR矩阵的数据。

  • 接受一个指向CSR矩阵的指针 matrix，以及包含非零元素的值、行索引和列索引的数组，以及非零元素的个数作为参数。
  • 通过遍历非零元素数组，将值、行索引和列索引分别赋给对应的矩阵元素，并更新 col_indices 数组和 row_ptr 数组中的值。row_ptr 数组的每个元素表示对应行的非零元素在 elements 数组中的起始位置，通过累加非零元素的个数来计算每行的结束位置。

打印矩阵

void printCSRMatrix(CSRMatrix matrix) {printf("CSR Matrix:\n");printf("Rows: %d, Cols: %d, Num Elements: %d\n", matrix.rows, matrix.cols, matrix.num_elements);printf("Values: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.elements[i].value);}printf("\n");printf("Row Pointer: ");for (int i = 0; i <= matrix.rows; i++) {printf("%d ", matrix.row_ptr[i]);}printf("\n");printf("Column Indices: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.col_indices[i]);}printf("\n");
}
void printMatrixForm(CSRMatrix matrix) {printf("Matrix Form:\n");for (int i = 0; i < matrix.rows; i++) {for (int j = 0; j < matrix.cols; j++) {int value = 0;for (int k = matrix.row_ptr[i]; k < matrix.row_ptr[i + 1]; k++) {if (matrix.elements[k].col == j) {value = matrix.elements[k].value;break;}}printf("%d ", value);}printf("\n");}
}
  • printCSRMatrix 函数用于打印CSR矩阵的信息：它接受一个CSR矩阵作为参数，并打印矩阵的行数、列数、非零元素的个数以及 elements、row_ptr 和 col_indices 数组的内容。
  • printMatrixForm 函数用于以矩阵形式打印CSR矩阵。它接受一个CSR矩阵作为参数，并按矩阵的行数和列数遍历矩阵元素，通过遍历 row_ptr 数组和 col_indices 数组来获取每个位置的元素值，并打印出矩阵的形式。

销毁CSR矩阵

void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix->elements);free(matrix->row_ptr);free(matrix->col_indices);matrix->elements = NULL;matrix->row_ptr = NULL;matrix->col_indices = NULL;
}

主函数

int main() {int rows = 9;int cols = 3;int num_elements = 5;CSRMatrix matrix = createCSRMatrix(rows, cols, num_elements);int col_indices[] = {0, 0, 0, 0, 1};int row_indices[] = {3, 5, 7, 8, 7};int values[] =      {2, 1, 3, 1, 4};initializeCSRMatrix(&matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(&matrix);return 0;
}

在这里插入图片描述

代码整合

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows = rows;matrix.cols = cols;matrix.num_elements = num_elements;matrix.elements = (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr = (int*)malloc((rows + 1) * sizeof(int));matrix.col_indices = (int*)malloc(num_elements * sizeof(int));memset(matrix.row_ptr, 0, (rows + 1) * sizeof(int));return matrix;
}
void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i = 0; i < num_elements; i++) {matrix->elements[i].value = values[i];matrix->elements[i].row = row_indices[i];matrix->elements[i].col = col_indices[i];matrix->col_indices[i] = col_indices[i];matrix->row_ptr[row_indices[i]]++;}int sum = 0;for (int i = 0; i <= matrix->rows; i++) {int temp = matrix->row_ptr[i];matrix->row_ptr[i] = sum;sum += temp;}
}void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row < 0 || row >= matrix->rows) {printf("Invalid row index.\n");return;}int index = matrix->row_ptr[row];matrix->elements[index].row = row;matrix->elements[index].col = col;matrix->elements[index].value = value;matrix->col_indices[index] = col;matrix->row_ptr[row]++;  // 递增索引值
}void printCSRMatrix(CSRMatrix matrix) {printf("CSR Matrix:\n");printf("Rows: %d, Cols: %d, Num Elements: %d\n", matrix.rows, matrix.cols, matrix.num_elements);printf("Values: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.elements[i].value);}printf("\n");printf("Row Pointer: ");for (int i = 0; i <= matrix.rows; i++) {printf("%d ", matrix.row_ptr[i]);}printf("\n");printf("Column Indices: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.col_indices[i]);}printf("\n");
}
void printMatrixForm(CSRMatrix matrix) {printf("Matrix Form:\n");for (int i = 0; i < matrix.rows; i++) {for (int j = 0; j < matrix.cols; j++) {int value = 0;for (int k = matrix.row_ptr[i]; k < matrix.row_ptr[i + 1]; k++) {if (matrix.elements[k].col == j) {value = matrix.elements[k].value;break;}}printf("%d ", value);}printf("\n");}
}void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix->elements);free(matrix->row_ptr);free(matrix->col_indices);matrix->elements = NULL;matrix->row_ptr = NULL;matrix->col_indices = NULL;
}int main() {int rows = 9;int cols = 3;int num_elements = 5;CSRMatrix matrix = createCSRMatrix(rows, cols, num_elements);int col_indices[] = {0, 0, 0, 0, 1};int row_indices[] = {3, 5, 7, 8, 7};int values[] =      {2, 1, 3, 1, 4};initializeCSRMatrix(&matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(&matrix);return 0;
}

这篇关于【数据结构】数组和字符串（五）：特殊矩阵的压缩存储：稀疏矩阵——压缩稀疏行（CSR）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/295610。

相关文章

C# $字符串插值的使用

C# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用
阅读更多...
详解MySQL中JSON数据类型用法及与传统JSON字符串对比

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引
阅读更多...
MySQL字符串常用函数详解

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、
阅读更多...
使用zip4j实现Java中的ZIP文件加密压缩的操作方法

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4
阅读更多...
SpringBoot3.X 整合 MinIO 存储原生方案

SpringBoot3.X 整合 MinIO 存储原生方案

《SpringBoot3.X整合MinIO存储原生方案》本文详细介绍了SpringBoot3.X整合MinIO的原生方案,从环境搭建到核心功能实现,涵盖了文件上传、下载、删除等常用操作,并补充了... 目录SpringBoot3.X整合MinIO存储原生方案：从环境搭建到实战开发一、前言：为什么选择MinI
阅读更多...
Java中的数组与集合基本用法详解

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问
阅读更多...
Python中反转字符串的常见方法小结

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函
阅读更多...
Linux中压缩、网络传输与系统监控工具的使用完整指南

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压：数据存储与传输的优化核心1. zip/unzip：通用压缩格式的便捷操作2.
阅读更多...
Python实现对阿里云OSS对象存储的操作详解

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os
阅读更多...
MySQL查询JSON数组字段包含特定字符串的方法

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案（推荐）2. 模糊匹配方案参数化查询示例使用场景建议性能优
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2