C语言数组学习之特殊矩阵的压缩存储

2024-07-28 14:44:45

1.数组的定义

数组是由n个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系

数组是线性表的推广

一维数组可以视为一个线性表
二维数组可视为其元素为定长线性表的线性表
数组一旦被定义，其维数和维界就不再改变，因此除了数组结构的初始化和销毁外，数组只能执行存储元素和修改元素的操作

在了解完数组的定义后，我们再了解一下数组在内存中是如何存储的

2.数组的存储结构

一个数组的所有元素在内存中占用一段连续的存储空间

一维数组的存储如下：

对于多维数组，比如二维数组来说，有两种映射方法：按行优先和按列优先

按行优先：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素

按列优先：先列后行，先存储列号较小的元素，列号相等先存储行号较小的元素

习题1

在了解数组在内存中的存储方式后，我们可以开始用数组来存储矩阵中的元素了！

3.对称矩阵

概念

对于一个n阶方阵A中的任意一个元素a_i,j都有a_i,j=a_j,i，则称为对称矩阵

对于一个对称矩阵我们可以将其中的元素划分为3个部分：上三角区，主对角线和下三角区

存储方法选择

土办法

用一个n*n的数组去完完整整地将整个矩阵中的元素给存储下来。

压缩存储法

我们发现对于n阶对称矩阵，上三角区的所有元素与下三角区的所有元素相同，若采用上述的土办法，将会浪费几乎一半的空间，因此我们将其中重复相同的元素只存放一次。

存储主对角线和下三角区

可见，采取行优先的原则将主对角线和下三角区的元素存入数组B当中

那么在数组B当中，a_i,j对应B[?]呢？我们可以自己通过计算得出一个映射公式

习题1

习题2

4.三角矩阵

概念

存储方法选择

土办法

用一个n*n的数组去完完整整地将整个矩阵中的元素给存储下来。

压缩存储法

与对称矩阵不同之处在于，存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次。

按行存储主对角线和下三角区+常量C

按行存储主对角线和上三角区+常量C

5.三对角矩阵

概念

对角矩阵称为带状矩阵；在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为零

存储方法选择

压缩存储法

习题1

6.稀疏矩阵

概念

矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵。

存储方法选择

三元组存储

十字链表法

到此这篇关于C语言数组学习之特殊矩阵的压缩存储的文章就介绍到这了,更多相关C语言矩阵的压缩存储内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言中杨氏矩阵与杨辉三角的实现方法

一.杨氏矩阵杨氏矩阵 1.杨氏矩阵的概念在数学中,杨表(英语:Young tableau),又称杨氏矩阵.是对组合表示理论和舒伯特演算很有用的工具.它提供了一种方便的方式来描述对称和一般线性群的群表示,并研究它们的性质.杨表是剑桥大学数学家 Alfred Young 在1900年推提出.然后,它被弗罗贝尼乌斯应用对称群的研究中.他们的理论由许多数学家进一步发展,包括PercyMacMahon.W. V. D. Hodge.G. de B. Robinson.吉安-卡洛·罗塔.Alain La
C语言实现图的邻接矩阵存储操作

利用邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连,并容易求得各个顶点的度. c语言代码实现如下: #include<stdio.h> #include<stdlib.h> #define MAX_VER_NUM 50 typedef char VertexType; typedef enum { DG,UDG }GraphType; typedef struct { VertexType vexs[MAX_VER_NUM]; //顶点向量 int arcs[MAX_VER_
C语言实现稀疏矩阵

本文实例为大家分享了C语言实现稀疏矩阵的具体代码,供大家参考,具体内容如下 #include "stdio.h" #define maxsize 10 typedef struct { int i,j; //非零元素的行.列 int v; //非零元素的值 }Triple; typedef struct { Triple data[maxsize]; int m,n; //矩阵的行.列 }TSMarix; InitTriple(TSMarix *M) { int i,j,k,v,t;
C语言数组学习之特殊矩阵的压缩存储

目录 1.数组的定义数组与线性表的关系 2.数组的存储结构习题1 3.对称矩阵概念存储方法选择习题1 习题2 4.三角矩阵概念存储方法选择 5.三对角矩阵概念存储方法选择习题1 6.稀疏矩阵概念存储方法选择首先最开始我们先回忆一下数组的概念 1.数组的定义数组是由n个相同类型的数据元素构成的有限序列,每个数据元素称为一个数组元素,每个元素在n个线性关系中的序号称为该元素的下标,下标的取值范围称为数组的维界. 数组与线性表的关系数组是线性表的推广一维数组可以视为一个
C++实现特殊矩阵的压缩存储算法

目录 1. 前言 2. 压缩对称矩阵 3. 压缩稀疏矩阵 3.1 三元组表 3.2 以列优先搜索 3.3 找出存储位置 4. 总结 1. 前言什么是特殊矩阵? C++,一般使用二维数组存储矩阵数据. 在实际存储时,会发现矩阵中有许多值相同的数据或有许多零数据,且分布呈现出一定的规律,称这类型的矩阵为特殊矩阵. 为了节省存储空间,可以设计算法,对这类特殊矩阵进行压缩存储,让多个相同的非零数据只分配一个存储空间:对零数据不分配空间. 本文将讲解如何压缩这类特殊矩阵,以及压缩后如何保证矩阵的常规操作
Go语言基础学习之数组的使用详解

目录 1. Array(数组) 2. 声明数组 3. 数组初始化 3.1 方式一 3.2 方式二 3.3 方式三 3.4 多维数组 4. 遍历数组&取值 5. 数组拷贝和传参数组相必大家都很熟悉,各大语言也都有数组的身影.Go 语言也提供了数组类型的数据结构. 1. Array(数组) 数组是同一种数据类型的固定长度的元素集合.在 Go 语言中,数组声明后长度就不能改变了,可以修改数组的元素,用法: // eg: 定义一个长度为 10 的 int 数组 var a [10]int 2. 声明数
go语言编程学习实现图的广度与深度优先搜索

目录图的实现 BFS DFS 图的实现所谓图就是节点及其连接关系的集合.所以可以通过一个一维数组表示节点,外加一个二维数组表示节点之间的关系. //图的矩阵实现 typedef struct MGRAPH{ nodes int[]; //节点 edges int[][]; //边 }mGraph; 然而对于一些实际问题,其邻接矩阵中可能存在大量的0值,此时可以通过邻接链表来表示稀疏图,其数据结构如图所示其左侧为图的示意图,右侧为图的邻接链表.红字表示节点序号,链表中为与这个节点相连的节点,
C语言数组栈实现模板

本文实例为大家分享了C语言数组栈实现模板的具体代码,供大家参考,具体内容如下 SeqStack.h #pragma once #define MAX_SIZE 1024 typedef struct SEQSTACK { void* data[MAX_SIZE]; int size; }SeqStack; SeqStack* Init_SeqStack(); // 初始化栈 void Push_SeqStack(SeqStack* stack, void* data); // 入栈 void*
详解C语言数组中是以列优先吗

如果我们按照C语言的方式存储它,也就是行优先存储的话,那么在内存中,它的形状是这样的: 这种存储方式又被称作C contiguous array. C语言数组结构列优先顺序存储的实现 (GCC编译). 从行优先转换为列优先存储方式,与行优先相比,不同之处在于改变了数组维界基址的先后顺序, 从而改变了映像函数常量基址. /** * @brief C语言数组列优先实现 * @author wid * @date 2013-11-02 * * @note 若代码存在 bug 或程序缺陷, 请留言
R语言数组实例用法及知识点总结

数组是可以在两个以上维度中存储数据的R数据对象. 例如 - 如果我们创建一个维度(2,3,4)的数组,则它创建4个矩形矩阵,每个矩阵具有2行和3列. 数组只能存储数据类型. 使用array()函数创建数组. 它使用向量作为输入,并使用dim参数中的值创建数组. 例以下示例创建一个由两个3x3矩阵组成的数组,每个矩阵具有3行和3列. # Create two vectors of different lengths. vector1 <- c(5,9,3) vector2 <- c(10,11
C语言数组详细介绍

目录什么是数组一维数组二维数组数组越界数组名结尾什么是数组数组(Array)是一种用来存储同一种类型的集合,是一种有序的线性结构表.并且数组元素的地址是连续的. 数组最大的优点就是支持随机访问,当想访问数组的某个数时,只需要找到数组的对应下标就可以直接找到该数组对应元素.但是数组也有相应的缺点,那就是数组的元素个数和数组空间大小在创建时就已经被固定死了,如果数组的空间没有使用完也会造成空间浪费,并且因为数组的地址是连续的,这本应该是一个优点的,但是这导致数组在进行删除或增加元素时
浅谈C语言数组元素下标为何从0开始

很多同学可能在学习数组时会有这个疑问,下标为什么不从1开始呢?从1开始不是更符合大家的日常习惯吗?生活中我们通常说第1个,而不是第0个.的确,有些计算机语言如早期的Pascal语言,数组元素的下标是从1开始的.难道是C语言故意要与众不同?要弄清楚这个问题,得先看一下计算机底层是怎样处理数组元素的.我们先编写了一个小程序,然后在visual studio中对其进行了反汇编.源程序和反汇编后的部分代码如下: 源程序: int arr[5]; //一个全局数组 int main() { int
C语言数组实现三子棋应用实例

本文实例为大家分享了C语言数组实现三子棋应用的具体代码,供大家参考,具体内容如下三子棋:(拆分部分如下) test.c 测试游戏逻辑 game.h关于游戏相关的函数声明,符号声明头文件的包含 game.c游戏相关函数的实现游戏进行的过程:(4种) 1.玩家获胜--*(游戏结束) 2.电脑获胜--#(游戏结束) 3.平局--Q(游戏结束) 4.游戏继续--C IsWin函数用来判断游戏的状态 game.c #include"game.h" #include<stdio.h&