Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【数据结构】数组和字符串(二):特殊矩阵的压缩存储:对角矩阵——一维数组

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

作者头像
Qomolangma
发布于 2024-07-30 01:32:47
发布于 2024-07-30 01:32:47
20800
代码可运行
举报
文章被收录于专栏:深度学习深度学习
运行总次数:0
代码可运行

4.2.1 矩阵的数组表示

【数据结构】数组和字符串(一):矩阵的数组表示

4.2.2 特殊矩阵的压缩存储

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

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

a. 对角矩阵的压缩存储

  对于一个n×n维的对角矩阵M,由于非主对角线上的元素都为零,只需存储其n个对角元素的值即可。可以使用一维数组d[n]来压缩存储对角矩阵,其中d[i-1] (1≤ i ≤ n)存储M(i, i)的值。这种压缩存储方式可以显著减少存储空间的使用量,尤其在矩阵规模较大时效果更为明显。同时,在对角矩阵的运算中,由于非主对角线上的元素都为零,可以通过直接访问压缩后的数据来提高算法的效率。

结构体
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
typedef struct {
    int size;       // 矩阵的维度
    int diagonal[MAX_SIZE];  // 存储对角元素的数组
} DiagonalMatrix;

DiagonalMatrix 结构体定义了对角矩阵的结构,包括矩阵的维度 size 和存储对角元素的数组 diagonal

初始化
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void initialize(DiagonalMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化对角元素数组
    for (int i = 0; i < size; i++) {
        matrix->diagonal[i] = 0;
    }
}

initialize 函数用于初始化对角矩阵,接受一个指向 DiagonalMatrix 结构体的指针和矩阵的维度作为参数,在函数内部将矩阵的维度存储到 size 成员变量中,并将对角元素数组的所有元素初始化为0。

元素设置
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void setElement(DiagonalMatrix *matrix, int row, int col, int value) {
    if (row != col) {
        printf("Error: Only diagonal elements 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 {
        matrix->diagonal[row] = value;
    }
}

setElement 函数用于设置对角矩阵中指定位置的元素值,接受一个指向 DiagonalMatrix 结构体的指针、行索引、列索引和要设置的值作为参数。

  • 函数首先检查行索引和列索引是否相等,因为只有对角线上的元素可以被设置。
  • 检查行索引和列索引是否有效,即在矩阵范围内。
  • 如果通过了检查,将指定位置的对角元素设置为给定的值。
元素获取
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int getElement(DiagonalMatrix *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 {
        return matrix->diagonal[row];
    }
}

getElement 函数用于获取对角矩阵中指定位置的元素值,接受一个指向 DiagonalMatrix 结构体的指针、行索引和列索引作为参数。

  • 函数首先检查行索引和列索引是否有效,如果无效则打印错误信息并返回0。、
  • 然后再次检查行索引和列索引是否相等,如果不相等则表示该位置不是对角元素,返回0。
  • 如果通过了检查,返回指定位置的对角元素的值。
打印矩阵
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void printMatrix(DiagonalMatrix *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 函数用于打印对角矩阵,接受一个指向 DiagonalMatrix 结构体的指针作为参数。函数通过两层循环遍历矩阵的每个位置,调用getElement 函数获取并打印元素的值。

主函数
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int main() {
    DiagonalMatrix matrix;
    int size = 6;

    initialize(&matrix, size);
    // 读入数据并设置对角矩阵的元素
    for (int i = 0; i < size; i++) {
        int value;
        printf("\nEnter the value for element [%d][%d]: ", i, i);
        scanf("%d", &value);
        setElement(&matrix, i, i, value);
    }

    printf("Diagonal Matrix:\n");
    printMatrix(&matrix);
    return 0;
}

  在 main 函数中,首先定义了一个 DiagonalMatrix 类型的变量 matrix 和一个整数变量 size。然后调用 initialize 函数初始化矩阵,将矩阵的维度设置为4,并将对角元素分别设置为1、2、3和4。最后使用 printMatrix 函数打印矩阵。

输出结果
代码整合
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <stdio.h>

#define MAX_SIZE 100

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

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

    // 初始化对角元素数组
    for (int i = 0; i < size; i++) {
        matrix->diagonal[i] = 0;
    }
}

// 设置对角矩阵中指定位置的元素值
void setElement(DiagonalMatrix *matrix, int row, int col, int value) {
    if (row != col) {
        printf("Error: Only diagonal elements 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 {
        matrix->diagonal[row] = value;
    }
}

// 获取对角矩阵中指定位置的元素值
int getElement(DiagonalMatrix *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 {
        return matrix->diagonal[row];
    }
}

// 打印对角矩阵
void printMatrix(DiagonalMatrix *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() {
    DiagonalMatrix matrix;
    int size = 6;

    initialize(&matrix, size);
    // 读入数据并设置对角矩阵的元素
    for (int i = 0; i < size; i++) {
        int value;
        printf("\nEnter the value for element [%d][%d]: ", i, i);
        scanf("%d", &value);
        setElement(&matrix, i, i, value);
    }

    printf("Diagonal Matrix:\n");
    printMatrix(&matrix);
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-10-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
2540
【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组
【数据结构】数组和字符串(五):特殊矩阵的压缩存储:稀疏矩阵——压缩稀疏行(CSR)
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
2710
【数据结构】数组和字符串(五):特殊矩阵的压缩存储:稀疏矩阵——压缩稀疏行(CSR)
【数据结构】数组和字符串(八):稀疏矩阵的链接存储:十字链表的创建、插入元素、遍历打印(按行、按列、打印矩阵)、销毁
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
5650
【数据结构】数组和字符串(八):稀疏矩阵的链接存储:十字链表的创建、插入元素、遍历打印(按行、按列、打印矩阵)、销毁
【数据结构】数组和字符串(十):稀疏矩阵的链接存储:十字链表的矩阵操作(加法、乘法、转置)
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
1690
【数据结构】数组和字符串(十):稀疏矩阵的链接存储:十字链表的矩阵操作(加法、乘法、转置)
【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
1600
【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表
数据结构基础(一)数组,矩阵
有一个等式,数据结构+算法=程序,说明了数据结构对于计算机程序设计的重要性。数据结构是指数据元素的集合(或数据对象)及元素间的相互关系和构造方法。数据对象中元素之间的相互关系称为数据的逻辑结构,数据元素及元素之间关系的存储形式称为存储结构(或物理结构)。
AlbertYang
2020/09/08
1.5K0
数据结构基础(一)数组,矩阵
【数据结构】数组和字符串(七):特殊矩阵的压缩存储:三元组表的转置、加法、乘法操作
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
1950
【数据结构】数组和字符串(七):特殊矩阵的压缩存储:三元组表的转置、加法、乘法操作
文心一言 VS 讯飞星火 VS chatgpt (389)-- 算法导论25.1 2题
在许多数学和计算应用中,要求矩阵 W 的对角线元素 w_{ii} = 0 是出于特定的数学性质和算法需求。以下是一些常见的原因:
福大大架构师每日一题
2024/11/12
960
文心一言 VS 讯飞星火 VS chatgpt (389)-- 算法导论25.1 2题
【数据结构】数组和字符串(九):稀疏矩阵的链接存储:十字链表的插入、查找、删除操作
  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。
Qomolangma
2024/07/30
1150
【数据结构】数组和字符串(九):稀疏矩阵的链接存储:十字链表的插入、查找、删除操作
原 三对角矩阵
**三对角矩阵(tridiagonal):**M是一个三对角矩阵,当且仅当|i-j|>1时,M(i,j)=0。 在一个rows×rows的三对角矩阵中,非0元素排列在如下三条对角线上: 1)主对角
青木
2018/05/28
1.1K0
盘一盘 Python 特别篇 20 - SciPy 稀疏矩阵
和稠密矩阵相比,稀疏矩阵的最大好处就是节省大量的内存空间来储存零。稀疏矩阵本质上还是矩阵,只不过多数位置是空的,那么存储所有的 0 非常浪费。稀疏矩阵的存储机制有很多种 (列出常用的五种):
用户5753894
2020/08/06
2.1K0
leetcode-766-Toeplitz Matrix(每一条对角线元素的比较)
题目描述: A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz. Example 1: Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: True Explana
chenjx85
2018/05/21
7550
小白的机器学习实战——向量,矩阵和数组 小白的机器学习实战——向量,矩阵和数组
创建矩阵 import numpy as np # 创建矩阵 matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]) 向量 # 行向量 vector_row = np.array([1, 2, 3]) # 列向量 vector_column = np.array([[1],
尾尾部落
2018/09/04
1.1K0
【数据结构】串与数组
文章目录 4. 串与数组 4.1 串概述 4.2 串的存储 4.3 顺序串 4.3.1 算法:基本功能 4.3.2 算法:扩容 4.3.3 算法:求子串 4.3.4 算法:插入 4.3.5 算法:删除 4.3.6 算法:比较 4.4 模式匹配【难点】 4.4.1 概述 4.4.2 Brute-Force算法:分析 4.4.3 Brute-Force算法:算法实现 4.4.4 KMP算法:动态演示 4.4.5 KMP算法:求公共前后缀 next数组 -- 推导 4.4.6 KMP算法:求公共前后缀 next数
陶然同学
2023/02/26
4K0
【数据结构】串与数组
java数据结构之多维数组实现
矩阵中的所有数据通过一定的规律存储在一维数组中。其中k=j*(j-1)/2+i-1。其中j和i是矩阵中的j和i而k是一维数组的下标号。
林老师带你学编程
2022/11/30
4570
数据结构(5):数组
数组是由 n(n≥1)个相同类型的数据元素构成的有限序列,每个数据元素称为一个数组元素,每个元素在 n 个线性关系中的序号称为该元素的下标,下标的取值范围称为数组的维界。
不可言诉的深渊
2021/04/16
1K0
数组和广义表 原
数组是存储同一类型数据的数据结构,使用数组时需要定义数组的大小和存储数据的数据类型。
云飞扬
2019/03/12
7890
数组和广义表
                                                                            原
PHP数据结构(五) ——数组的压缩与转置
PHP数据结构(五)——数组的压缩与转置 (原创内容,转载请注明来源,谢谢) 1、数组可以看作是多个线性表组成的数据结构,二维数组可以有两种存储方式:一种是以行为主序,另一种是以列为主序。 2、当数组存在特殊情况时,为了节省存储空间,可以进行压缩存储,把相同值并有规律分布的元素只分配一个存储空间,对于零元素不进行存储。 有两种情况可以进行压缩存储——特殊矩阵与稀疏矩阵。 3、当数组为特殊的矩阵,例如数组为n阶对称矩阵(满足aij=aji)。对于该类型矩阵,可以只存储一半的数值加上对角线的内容,一共需要分配
用户1327360
2018/03/07
2.4K0
一维数组&二维数组&对称矩阵&三角矩阵&三对角矩阵地址的计算
一维数组的地址计算 设每个元素的大小是size,首元素的地址是a[1],则 a[i] = a[1] + (i-1)*size
lexingsen
2022/02/25
1.9K0
一维数组&二维数组&对称矩阵&三角矩阵&三对角矩阵地址的计算
经典算法之稀疏矩阵
在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵;与之相反,若非0元素数目占大多数时,则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。
用户3467126
2019/11/26
4.3K0
经典算法之稀疏矩阵
推荐阅读
【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组
2540
【数据结构】数组和字符串(五):特殊矩阵的压缩存储:稀疏矩阵——压缩稀疏行(CSR)
2710
【数据结构】数组和字符串(八):稀疏矩阵的链接存储:十字链表的创建、插入元素、遍历打印(按行、按列、打印矩阵)、销毁
5650
【数据结构】数组和字符串(十):稀疏矩阵的链接存储:十字链表的矩阵操作(加法、乘法、转置)
1690
【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表
1600
数据结构基础(一)数组,矩阵
1.5K0
【数据结构】数组和字符串(七):特殊矩阵的压缩存储:三元组表的转置、加法、乘法操作
1950
文心一言 VS 讯飞星火 VS chatgpt (389)-- 算法导论25.1 2题
960
【数据结构】数组和字符串(九):稀疏矩阵的链接存储:十字链表的插入、查找、删除操作
1150
原 三对角矩阵
1.1K0
盘一盘 Python 特别篇 20 - SciPy 稀疏矩阵
2.1K0
leetcode-766-Toeplitz Matrix(每一条对角线元素的比较)
7550
小白的机器学习实战——向量,矩阵和数组 小白的机器学习实战——向量,矩阵和数组
1.1K0
【数据结构】串与数组
4K0
java数据结构之多维数组实现
4570
数据结构(5):数组
1K0
数组和广义表 原
7890
PHP数据结构(五) ——数组的压缩与转置
2.4K0
一维数组&二维数组&对称矩阵&三角矩阵&三对角矩阵地址的计算
1.9K0
经典算法之稀疏矩阵
4.3K0
相关推荐
【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验