首页 > 其他分享 >【数据结构】数组、稀疏矩阵的操作、广义表

【数据结构】数组、稀疏矩阵的操作、广义表

时间：2024-02-21 09:35:49浏览次数：18  
标签：矩阵 三元组 数组 数据结构 data col row

数组

数组：按一定格式排列起来的，具有相同类型的数据元素的集合

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组

数组基本操作：一般来说，只有存取和修改这两种操作

数组一般采用顺序存储结构

二维数组的两种顺序存储方式

  1. 以行序为主序（C语言、Java、PASCAL）

  1. 以列序为主序（FORTRAN）

地址计算：

对于一维数组，有

\[Loc(i)= \begin{cases} a,&i = 0\\ Loc(i-1)+l=a+i*l,&i > 0\\ \end{cases} \]

其中

a 为数组的首地址

i 为一维数组的下标

l 为数组中每个元素的大小

对于二维数组（行序优先），有

\[Loc(i,j) = a+(n*i+j)*l \]

其中

a 为数组的首地址

n 为数组中每行的元素个数

l 为数组中每个元素的大小

对于三维数组（页、行、列的存放方式），有

\[Loc(i,j,k) = a + (i*m_2*m_3+j*m_3+k)*l \]

其中

a 为数组的首地址

\(m_2\) 为数组中每行的元素个数

\(m_3\) 为数组中每列的元素个数

l 为数组中每个元素的大小

矩阵

矩阵：一个由 \(m\times n\)个元素排成的 m 行 n 列的表

矩阵的常规存储：将矩阵描述为一个二维数组

不适宜常规存储的矩阵的特点：

  1. 有很多值相同的元素，且呈某种规律分布
  2. 零元素多

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间，对零元素不分配空间

特殊矩阵的压缩存储

什么是压缩存储？

若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间

特殊矩阵有哪些？

对称矩阵、对角矩阵、三角矩阵、稀疏矩阵等

对称矩阵

特点

在\(n \times n\)的矩阵 a 中，满足如下性质：

\[a_{ij} = a_{ji}\quad(1 \leq i,\ j \leq n) \]

存储方法

只存储下（上）三角（包括主对角线）的数据元素

对称矩阵的存储结构：

上下三角中的元素数均为：\(\frac {n(n+1)}{2}\)

可以以行序为主序，将元素存放在一个一维数组中

三角矩阵

特点

对角线以下（以上）的数据元素全部为常数 c

存储方法

重复的数据元素只占用一个存储空间，共占用\(n(n+1)/2+1\)个存储空间

对角矩阵

特点

在\(n\times n\)的矩阵中，所有非零元素都集中在以对角线为中心的带状区域中，区域外的值全为0

常见的有三对角矩阵、五对角矩阵、七对角矩阵

存储方法

稀疏矩阵

特点

矩阵中非零元素的个数较少（一般小于5%）

存储方法

存各非零元的值、行列位置和矩阵的行列数

存储结构

  1. 顺序存储结构：三元组表
  2. 链式存储结构：十字链表

表示方式

三元组表

#define MAXSIZE 100
typedef struct TupNode {
	int row;
	int col;
	int data;
}Triple;						
typedef struct TSMatrix {
	Triple data[MAXSIZE + 1];
	int row_size;
	int col_size;
	int non_zero_num;
}TSMatrix;

Triple：

定义三元组的类型，row 表示数据所在的行号，col 表示数据所在的列号，data 记录矩阵相应位置上的值

TSMatrix（Triple Sparse Matrix）：

定义三元组顺序表用来表示稀疏矩阵，表中包括一个三元组数组，该数组每个元素是三元组，还包括了所表示的稀疏矩阵的行与列的大小以及稀疏矩阵中非零元素的个数。

Triple data[MAXSIZE + 1]：三元组数组

row_size：稀疏矩阵行的大小

col_size：稀疏矩阵列的大小

non_zero_num：稀疏矩阵中非零元素的个数

三元组数组的0号位空间可用可不用，如果用的话，一种就是正常的存储矩阵数据，另一种就是用0号位来记录稀疏矩阵行与列的大小和稀疏矩阵中非零元素的个数，如果不用的话，就从数组的1号位开始存储数据。以下代码都是基于不使用数组中的0号位空间

三元组表的优点：便于进行按行序处理的矩阵运算

缺点：若按行序存取某一行中的非零元，则需要从头开始查找

十字链表

typedef struct OLNode
{
	int row, col;
	int value;
	struct OLnode* down, * right;
}OLNode;
typedef struct CrossList
{
	int row_size, col_size;
	int non_zero_num;
	OLNode* rhead, * chead;
}CrossList;

OLNode：表示矩阵中的每一个非零元

down：用于链接同一列中的下一个非零元素

right：用于链接同一行中的下一个非零元素

CrossList：表示矩阵

rhead：行链表的头指针

chead：列链表的头指针

rhead 和 chead 是一个指针数组的首元素，注意，这里的数组只是形式上的，实际上是由其 down 或 right 指针不断链接而成的一个链表

矩阵的转置

对于一个\(m \times n\)的矩阵 A，转置后则变成一个\(n \times m\)的矩阵 B，\(A[i][j]=B[i][j]\)

矩阵的值的位置发生了改变，原先的行号变成了列号，原先的列号变成了行号

实现思路

三元组顺序表 A 和 B，A 表示转置前的三元组顺序表，B 表示转置后的三元组顺序表，都以行序为主序

  • 思路1（先赋值后排序）

  1. 对于 A 中的每一个三元组，将其行的值赋给 B 中对应三元组中的列，列的值赋给行，数据不变

  2. 将 B 中的三元组按行序重新排列

  • 思路2（先排序后赋值）

对于 A 中的每一个三元组，按照列序，将其行的值赋给 B 中对应三元组中的列，列的值赋给行，数据不变

例如：假设有如下稀疏矩阵 A 和及其转置后的矩阵 B

则 A 的三元组表为

思路1的过程为

在排序时，只需要关注 row 的大小即可

思路2的过程为，按表 A 中的列号，从小到大，依次赋值给表 B，当列号（转置前）相同时，由于转置前的行号是按序的，所以转置后的列号也是按序的

代码实现

思路1

void trans_1(TSMatrix* A, TSMatrix* B)
{
	int i = 0;
	int j = 0;
	B->row_size = A->col_size;
	B->col_size = A->row_size;
	B->non_zero_num = A->non_zero_num;

	for (i = 1; i <= A->non_zero_num; i++)
	{
		B->data[i].row = A->data[i].col;
		B->data[i].col = A->data[i].row;
		B->data[i].data = A->data[i].data;
	}

	for (i = 1; i <= B->non_zero_num - 1; i++)
	{
		for (j = 1; j <= B->non_zero_num - i; j++)
		{
			if (B->data[j].row > B->data[j + 1].row)
			{
				swap_TupNode(&(B->data[j]), &(B->data[j + 1]));
			}
		}
	}
}
void swap_TupNode(TupNode* a, TupNode* b)
{
	TupNode temp;
	temp.row = a->row;
	temp.col = a->col;
	temp.data = a->data;

	a->row = b->row;
	a->col = b->col;
	a->data = b->data;

	b->row = temp.row;
	b->col = temp.col;
	b->data = temp.data;
}

当要按行序进行排序时，需要采用有稳定性的排序方法

以上代码中使用的是冒泡排序

for (i = 1; i <= B->non_zero_num - 1; i++)
{
	for (j = 1; j <= B->non_zero_num - i; j++)
	{
		if (B->data[j].row > B->data[j + 1].row)
		{
			swap_TupNode(&(B->data[j]), &(B->data[j + 1]));
		}
	}
}

思路2

void trans_2(TSMatrix* A, TSMatrix* B)
{
	int i = 0;
	int j = 0;
	int k = 1;
	B->row_size = A->col_size;
	B->col_size = A->row_size;
	B->non_zero_num = A->non_zero_num;
	
	for (i = 1; i <= A->col_size; i++)			//按原矩阵的列号开始遍历
	{
		for (j = 1; j <= A->non_zero_num; j++)	//遍历原矩阵中所有的三元组
		{
			if (A->data[j].col == i)			//从列号为1的三元组开始，逐个赋值给转置后的矩阵
			{
				B->data[k].row = A->data[j].col;
				B->data[k].col = A->data[j].row;
				B->data[k].data = A->data[j].data;
				k++;
			}
		}
	}
}

时间复杂度

设有\(m\times n\)的矩阵，非零元素个数为 t

对于思路1的代码

一般情况下， 算法的时间复杂度为\(O(t+n*t)\)，当 t 和 \(m\times n\)处于同一数量级时，算法的时间复杂度为\(O(m*n^2)\)

对于思路2的代码

一般情况下，算法的时间复杂度为\(O(n*t)\)，当 t 和 \(m\times n\)处于同一数量级时，算法的时间复杂度为\(O(m*n^2)\)

所以，矩阵转置算法的时间复杂度为

\[O(m\times n^2) \]

当 t 和 \(m\times n\)处于同一数量级的意思是，t 随 m、n 的增大而增大

矩阵的快速转置

实现思路

矩阵的快速转置算法只需要遍历一次原矩阵的三元组表，即可得出转置后矩阵的三元组表

思路如下：

创建数组 number，大小为 B.rowSize+1，不使用数组0号位的空间，记录转置后的矩阵中每行非零元素的个数，即转置前的矩阵中每列非零元素的个数

创建数组 position，大小为B.rowSize+1，不使用数组0号位的空间，记录转置后的矩阵中每行第一个非零元素在表中的位置

两个数组首元素都可以置为0

\[position[j] = \begin{cases} 1,&j=1\\ position[j-1]+number[j-1],&2\leq j\leq A.col\_size\\ \end{cases} \]

遍历原矩阵的三元组表，根据三元组的列值与 position 数组，赋值给转置后三元组表中相应位置的三元组，然后更新 position 数组

例如：

假设有如下三元组表及其转置后的三元组表

则其 number 和 position 数组为

i 0 1 2 3 4 5 6
number[i] 0 1 2 1 1 0 2
position[i] 0 1 2 4 5 6 6

当遍历到第一个三元组时，col 值为2，查找 position 数组，此时 position[2] == 2，于是将第一个三元组的值赋给转置后的三元组表中的2号位，position[2] 的值更新为3

以此类推

代码实现

void quick_trans(TSMatrix* A, TSMatrix* B)
{
	int number[MAXSIZE + 1] = { 0 };
	int position[MAXSIZE + 1] = { 0 };
	int i = 0;
	int j = 0;
	B->row_size = A->col_size;
	B->col_size = A->row_size;
	B->non_zero_num = A->non_zero_num;
	for (i = 1; i <= A->non_zero_num; i++)
	{
		int col = A->data[i].col;
		number[col]++;
	}
	position[1] = 1;
	for (i = 2; i <= A->col_size; i++)
	{
		position[i] = position[i - 1] + number[i - 1];
	}

	for (i = 1; i <= A->non_zero_num; i++)
	{
		int col = A->data[i].col;
		int index = position[col];
		B->data[index].row = A->data[i].col;
		B->data[index].col = A->data[i].row;
		B->data[index].data = A->data[i].data;
		position[col]++;
	}
}

时间复杂度

设有\(m\times n\)的矩阵，非零元素个数为 t

则矩阵的快速转置算法的时间复杂度为

\[O(n+t) \]

矩阵的乘法

理论基础

矩阵 A 为2*3矩阵

矩阵 B 为3*2矩阵

矩阵 C 为结果矩阵

计算过程：A 的逐行各元素乘 B 的逐列各元素

\[C[i][j] = A[i][k] \times B[k][j] \]

  • 矩阵的部分性质

  1. A 的列数等于 B 的行数时才可以相乘

  2. A 中列数为 n 的元素，只能和 B 中行数为 n 的元素相乘

  3. A 中某元素 a 和 B 中某元素 b 相乘时，得到的结果只存于 C 中行数和 a 相同，列数和 b 相同的位置

  4. C 的行数等于 A 的行数，C 的列数等于 B 的列数

代码实现

void Mult(TSMatrix* A, TSMatrix* B, TSMatrix* C)
{
	int i = 0;
	int j = 0;
	int k = 1;
	int index = 1;
	for (i = 1; i <= A->row_size; i++)
	{
		for (j = 1; j <= B->col_size; j++)
		{
			int sum = 0;
			for (k = 1; k <= A->col_size; k++)
			{
				sum = sum + get_value(A, i, k) * get_value(B, k, j);
			}
			if (sum != 0)
			{
				C->data[index].row = i;
				C->data[index].col = j;
				C->data[index].data = sum;
				index++;
			}
		}
	}
	C->row_size = A->row_size;
	C->col_size = B->col_size;
	C->non_zero_num = index - 1;
}

int get_value(TSMatrix* M, int i, int j)
{
	int k = 1;
	for (k = 1; k <= M->non_zero_num; k++)
	{
		if (M->data[k].row == i && M->data[k].col == j)
		{
			return M->data[k].data;
		}
	}
	return 0;
}

广义表

广义表是由零个或多个元素组成的有限序列，其中每个元素或者是原子，或者是一个广义表

广义表通常记作 GL = (a1, a2, a3, ... ,an)

其中，GL 为表名，n 为表的长度， 每一个 ai 为表的元素

一般用大写字母表示广义表，小写字母表示原子

表头：若 GL 非空（n >= 1），则其第一个元素 a1 就是表头，表头既可以是原子，也可以是子表

表尾：除表头之外其他元素组成的表

标签：矩阵,三元组,数组,数据结构,data,col,row
From： https://www.cnblogs.com/changbaiqiusha/p/18024457

相关文章

  • 代码随想录 day56 最长递增子序列 最长连续递增序列 最长重复子数组
    最长递增子序列dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度状态转移方程的含义：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列+1的最大值。最长连续递增序列dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。如果nums[i]>nums[i-1......
  • 代码随想录算法训练营第二十三天|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉
    669.修剪二叉搜索树 题目链接：669.修剪二叉搜索树-力扣（LeetCode）思路：本题原来想沿用上一次最后一道题的思路，用删除二叉搜索树特定值节点的方法来解决，但是会报错，找不出问题所在（在评论区也是一堆套用450代码报错的）。只能参考官网答案了。官网的方法没有用delete，但是思想是一直......
  • 情书密码—树状数组
    题目描述有消息称：绝恋找到了自己的MissRight，正准备自己的表白。绝恋已经写好了情书，但为了避免其它人截获，他对情书进行加密。为了打探绝恋的私密，你冒着生命危险终于搞到了这封情书。原以为可以轻易将情书解密，结果竟然发现聪明的绝恋并没有直接写出加密用的密码，而是在那粉红色的......
  • golang数组&切片&map
    数组数组声明funcmain(){ /*语法一*///数组名字[数组长度]数组类型 //声明一个数组长度为3类型是int会初始化为int类型的零值,默认值是[000] //声明数组的时候指定长度是一个常量，数组的不可改变，超出长度会报错 vararr[3]int //数组赋值 arr[0]=1......
  • 代码随想录算法训练营第二十三天 | 538.把二叉搜索树转换为累加树， 108.将有序数组转
     669.修剪二叉搜索树 已解答中等 相关标签相关企业 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low,high]中。修剪树 不应该 改变保留在树中的元素的相对结构(即，如果......
  • 矩阵乘法，矩阵快速幂
    矩阵乘法说白了就是c[i][j]=a[i][k]*b[k][j]矩阵快速幂就是把快速幂中整数乘法换成了矩阵乘法structma{ intm[5][5];}ans,base;macal(maa,mab){ matmp; for(inti=1;i<=2;i++) { for(intj=1;j<=2;j++) { tmp.m[i][j]=0; for(intk=......
  • 【学习笔记】后缀数组（SA）
    前言先把SA给写出来，SAM暂时还没学会，学会了应该也不会写，因为构造过程过于繁琐。本文可能对SA的算法流程和代码实现上的介绍相对简略，主要介绍一些常见用途。约定无特殊说明字符串的下标从\(1\)开始。无特殊说明\(s\)表示字符串，\(n\)表示字符串长度。“后缀\(i\)”......
  • 02 数据结构
    02数据结构Redis接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。因为一方面，这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快；另一方面，这要归功于它的数据结构。redis的数据结构String类型的底层实现只有一种数据结构，也就是简单......
  • Python用GAN生成对抗性神经网络判别模型拟合多维数组、分类识别手写数字图像可视化
    全文链接：https://tecdat.cn/?p=33566原文出处：拓端数据部落公众号生成对抗网络（GAN）是一种神经网络，可以生成类似于人类产生的材料，如图像、音乐、语音或文本。最近我们被客户要求撰写关于GAN生成对抗性神经网络的研究报告，包括一些图形和统计输出。近年来，GAN一直是研究的热门话题。F......
  • 数组扁平化
    普通的递归实functionflatten(arr){letresult=[];for(leti=0;i<arr.length;i++){if(Array.isArray(arr[i])){result=result.concat(flatten(arr[i]));}else{result.push(arr[i]);}}returnresult;}reducefu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99