首页 > 其他分享 >【数据结构】五分钟自测主干知识(七)

【数据结构】五分钟自测主干知识(七)

时间:2024-03-12 23:29:21浏览次数:27  
标签:存储 元素 矩阵 链表 五分钟 数组 自测 数据结构 col

最近略忙,今天为大家献上数组一节的拓展知识,我们可以从中加深对数组存储对理解,同时温习数组降低存储量的方法,我们会以矩阵存储为典例。

主干知识,可以对照黑体字来进行自测~


数组

基本概念

一维数组是纯粹的线性表,数组的元素类型就是线性表的元素类型;

二维数组则可以看成“元素是一维数组”的线性表。

A^{(2)}=\left ( A_0^{(1)},A_1^{(1)},\dots,A_{m-1}^{(1)} \right )

其中                ​​​​​​​        ​​​​  A_i^{(1)}=\left ( a_{i,0},a_{i,1},a_{i,2},\dots,a_{i,n-1} \right ),\quad i=0,1,\dots,m-1

二维数组也可以看成是m\times n的一个阵列(矩阵) 

同理,三维数组也可以看成是二维数组的线性表,N维数组看成元素是N-1维数组的线性表。

A^{(N)}=\left ( A_0^{(N-1)},A_1^{(N-1)},\dots,A_{m-1}^{(N-1)} \right )

数组的主要操作有如下4个:

InitArray(&A,n,bound1,…,boundn)
操作结果:初始化一个n 维数组,各维长度由 boundl,…,boundn 给定。
参数说明:bound1,…,boundn 合法正整数。


DestroyArray(&A)
操作结果:销毁数组 A。
参数说明:数组 A 已经存在。


Value(A,&e, index1,…, indexn)
操作结果:把e赋值为A 的指定下标的元素值。
参数说明:数组A已经存在,下标不越界。


Assign(&A,e, index1,…, indexn)
操作结果:把 e的值赋给 A 的指定下标的元素。
参数说明:数组 A已经存在,下标不越界。 


数组的顺序存储表示

由于数组可能是多维的,而计算机的内存只能是一维的连续空间,必须把多维的数组转换成一个一维的序列才可以存储。

大多数语言以“”为主序存储 

a_{0,0},a_{0,1},\dots,a_{0,n-1},a_{1,0},a_{1,1},\dots,a_{1,n-1},\dots,a_{m-1,0},a_{m-1,1},\dots,a_{m-1,n-1}

假设二维数组A[m][n]中每个元素占用L个存储单元,则该数组中任意一个元素a_{i,j}在存储映像区的存储地址可以这样确定:

Loc[i,j]=Loc[0,0]+(i\times n+j)\times L

其中Loc[i,j]a_{i,j}的存储地址,Loc[0,0]a_{0,0}的存储地址,也就是数组A存储映像区的首地址,称为数组A的基地址

同样三维数组B[p][m][n]中任意一个元素在存储映像中地址可以这样确定:

Loc[i,j,k]=Loc[0,0,0]+(i\times m\times n+j\times n +k)\times L

显然,数组元素的地址是其下标的线性函数,存取每个元素所进行的运算及次数都是一样的,称具有这种特点的存储结构为随机存取存储结构


矩阵的压缩存储

矩阵在科学计算领域有广泛的应用。随计算机应用和科学领域的发展,出现了很多高阶矩阵的计算问题,有的甚至达到几十万阶,上千亿的数组元素。然而这些矩阵很多都是有规律的,或者包含大量的零值元素。

对这类矩阵进行压缩,不仅可以节约存储空间,而且可以避免大量零值元素参与计算。

如果相同值的元素或零值元素在矩阵中的分布具有一定的规律和特征,这类矩阵被称为特殊形状的矩阵。如果没有什么特征,则称为随机稀疏矩阵


特殊形状矩阵通常有三角形矩阵,条带状矩阵,对称阵等

三角形矩阵是指矩阵中上三角下三角是全零值元素或同值元素。

条带状矩阵则是只有主对角线附近的若干条对角线上含有非零元素。

利用二维数组存储这些大多是零值元素的矩阵,空间浪费显然巨大,我们知道二维数组在实际存储时也是转换为一维的序列存储的,不管是行主序还是列主序,都可以建立一个元素存储位置和下标的函数关系,利用该函数可以通过下标对数组元素实现随机存取。

那么既然特殊形状矩阵有这么多零值元素,我们能否不存储零值元素,通过修改函数关系而仍然实现对数组元素的随机存取呢?


假设 N 阶方阵(行列相等)A 的元素满足a_{ij}=a_{ji}(i,j=0,1,\dots,n-1),则称之为对称阵。对称阵中的一对元素可以只存储一个存储空间,于是可以把n^2个元素压缩存储到\frac{n(n+1)}{2}个存储单元里。假设以B[n(n+1)/2]来存储这些元素,按照行主序的次序把对称矩阵下半区(包括主对角线)存储到 B 中。

得到a_{i,j}的存储地址满足(L是每个元素占用的存储单元数):

Loc(a_{ij})=Loc(B[0])+((1+i)\times i/2+j)\times L \quad (i\geq j)

Loc(a_{ij})=Loc(B[0])+((1+j)\times j/2+i)\times L \quad (i< j)

对于三角形状矩阵,如下三角阵,完全可以参照对称阵来给出函数关系,只是 i<j 时元
素值是 0,不再需要以上第二个计算式。


另一种带状特殊矩阵也可以采用类似的思想来存储在一个一维的数组中,下面考虑三
对角矩阵,即只有主对角线及其两侧的对角线上可以有非零值。

 带状矩阵存储位置与坐标的函数关系是

\left\{\begin{matrix} Loc(a_{i,j})=Loc(B[0])+(2i+j)\times L,\quad \left | i-j \right |\leq 1\\ a_{ij}=0,\qquad \qquad \qquad \qquad \qquad \qquad \qquad\left | i-j \right |>1 \end{matrix}\right.


m\times n的矩阵中,若非零元素有t个,我们定义

\delta =\frac{t}{m\times n}

 为矩阵的稀疏因子,通常认为\delta \leq 0.05时为稀疏矩阵

由于无特值可循,因此需要记录非零元素的位置。这样就构成了一个三元组(i,j,a_{ij})

三元组顺序表存储的实现如下:

#define MAX_SIZE 1000
typedef int ElemType;
typedef struct {
	int i, j;
	ElemType e;
}Triple;
typedef struct {
	Triple data[MAX_SIZE];
	int mu, nu, tu;
}TSMatrix;

原先矩阵转置的算法为:

void transpose(ElemType M[][], ElemType T[][], int m, int n) {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			T[j][i] = M[i][j];
		}
	}
}

很明显这个算法的时间复杂度为O(m\times n)

接下来我们使用“按位就座”的思想,有了rpos数组,就可以一次完成所有的非零元的排放。

#define MAXN 100
void createrpos(TSMatrix M) {
	for (int col = 0; col < M.nu; col++)num[col] = 0;
	for (t = 0; t < M.tu; t++) {
		++num[M.data[t].j];//统计各列非零元
	}
	rpos[0] = 0;
	for (int col = 1; col < M.nu; col++) {
		rpos[col] = rpos[col - 1] + num[col - 1];//累计num数组获得rpos
	}
}

下面给出三元顺序表压缩存储的矩阵M求其转置矩阵T的算法(略去了col的int初始化和q,rpos等元素初始化)

void TRansposeTS(TSMatrix M, TSMatrix& T) {
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	if (!M.tu) return;
	createrpos(M);
	for (int p = 0; p < M.tu; p++) {
		col = M.data[p].j;
		q = rpos[col];
		T.data[q].i = M.data[p].j;
		T.data[q].j = M.data[p].i;
		T.data[q].e = M.data[p].e;
		++rpos[col];
	}
}

思想:查询当前元素在M中的列,在T中的行

交换i,j坐标,赋元素值

然后rpos指向T中下一个col行的非零元素位置


从上述算法可以看出,包括 createrpos 算法在内,共有 4 个串行工作的单循环,循环次
数分别是2 个 nu 次和 2 个 tu 次,因此总的时间复杂度是 O(M.nu+ M.tu)。其效率大大
高于二维数组存储的矩阵转置时间复杂度 O(m\times n)


由于 rpos 数组大大简化了三元组存储矩阵的运用,我们常常在建立三元组表的时候就
建立起这样的数组,表示矩阵“每一行的非零元在三元组顺序表中起始位置”的信息。这种
“带行链接信息”的三元组表被称为逻辑链接的顺序表

采用三元组存储来表示矩阵时,一般采用顺序表来存储三元组,但当在矩阵运算产生元组的增减时,就需要对顺序表进行元素的插入和删除了,这时也可以考虑使用链表来存储三元组。


对于稀疏矩阵的压缩,除了使用三元组存储外,有时还使用十字链表来存储。十字链表是这样表示的:为一个 m × n 的矩阵创建 m + n 个单链表,m 个行链表和n 个列链表,每个行链表包含该行的所有非零元,同样,每个列链表包含该列的所有非零元。m 个行链表和n个列链表的头指针分别构成一维数组,属于指针数组。这样每个非零元素既属于一个行链表也属于一个列链表。因此,每个非零元素都是两个链表的交叉结点,故称十字链表。十字链表的结点包含 5 个域,具体描述如下:

typedef struct OLNode {
	int i, j;
	ElemType e;
	OLNode* rownext, * colnext;
}OLNode,*OLink;
typedef struct {
	OLink* rhead, * chead;
	int m, n, t;
}CrossList;

删繁就简三秋树,正确使用数组能够使我们的空间存储大大减小,熟练掌握也有利于我们处理相对较大的数据集,同时降低时间复杂度,提升效率

下一讲,我将带来重要数据结构“树”的一部分内容

今天肝得有点晚,睡觉!

附下一讲链接:【数据结构】五分钟自测主干知识(八)

未完待链接

标签:存储,元素,矩阵,链表,五分钟,数组,自测,数据结构,col
From: https://blog.csdn.net/2301_79853895/article/details/136661683

相关文章

  • C语言数据结构实现酒店管理
    #include<stdio.h>#include<windows.h>#include<stdlib.h> #include<string.h>//用于用户验证 #defineMAX100//最大房间容量 #defineStytm20#definemAX1024//文件读取字符长 intfileHang(FILE*fp);intlength=0;//房间顺序 typedefintDataType;typ......
  • 数据结构——线性表2(链表)
    【基本知识】链表是一种常见的数据结构,用于存储和组织数据。它由一系列节点组成,每个节点包含两部分:数据(data)和指向下一个节点的指针(*next)。链表中的节点可以在内存中不连续地分布,通过指针将它们连接起来。链表有多种类型,其中最常见的是单向链表和双向链表。在单向链表中,......
  • 【数据结构】排序
    文章目录一、排序的概念及引用1、排序的概念2、常见的排序算法二、常见排序算法的实现1、插入排序2、直接插入排序一、排序的概念及引用1、排序的概念排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。稳定性:假定在待排......
  • 【数据结构】堆
    目录1、树的概念及结构1.1树的概念1.2树的相关概念1.3树的结构定义2、二叉树的概念及结构2.1二叉树的概念2.2特殊的二叉树2.3二叉树的性质3、堆的概念及结构3.1二叉树的存储方式3.1.1顺序存储3.1.2链式存储3.2堆的概念及结构4、堆的代码实现4.1堆的初始化(建堆)......
  • 数据结构——线段树 学习笔记
    数据结构——线段树学习笔记classseg_t{private:structemm{intl,r;structv;};vector<emm>a;voidpush_up(intk){}voidaction(intk,intv){}voidpush_down(intk){}voidbuild(vector<any>q,intk,intl,intr){a[k].l=......
  • 2024 年春节集训 _ 第二课 - 数据结构优化动态规划
    【例题\(1\)】递增子序列\(\color{white}{link}\)考虑\(dp.\)\(dp[i][j]\)表示以元素\(i\)为结尾,长度为\(k\)的方案数。那么显而易见就有一个转移方程:\[dp[i][j]=\sum_{a[k]<a[i],\k<i}dp[k][j-1]\]先抛去第二维度的\(j\),这是可以做一个关于\(a[i]\)值的大......
  • 探索数据结构:单链表的实战指南
    ✨✨欢迎大家来到贝蒂大讲堂✨✨......
  • js 解释数据结构
    一、 JSON.parse 妙用用如下语句打印:console.info(result);   console.info(result.data);   console.info(JSON.parse(result.data));   console.info(JSON.parse(result.data).data.PriceSheetId);   console.info(result.data.Data);打印......
  • C 语言整数单链表的表示和实现 数据结构课程设计报告
     数据结构课程设计报告专业名称:计算机科学与技术 课程名称:数据结构        实训题目:整数单链表的表示和实现                           实训环境:C语言实现(DevC++)                    ......
  • 【学习笔记】 - 基础数据结构 :Link-Cut Tree(进阶篇)
    前言LCT没题写可以去写树剖和一些线段树合并的题练手LCT的概念原本的树剖是对树进行剖分,剖分为重边和轻边LCT则是对于树分为虚边和实边,特殊的,LCT可以没有虚边(例:银河英雄传说v2)单独被包含在一个实链里的点称作孤立点在树剖中,我们使用线段树/树状数组来维护重链在Link-Cut......