数据结构-数组(稀疏矩阵转置)和广义表

目录

  • 1、数组
      • 定义
    • 1)数组存储地址计算
      • 示例
        • ①行优先
        • ②列优先
    • 2)稀疏矩阵的转置
      • 三元组顺序表
        • 结构定义
      • ①普通矩阵转置
      • ②三元组顺序表转置稀疏矩阵
      • ③稀疏矩阵的快速转置
    • 3)十字链表
      • 结构定义
  • 2、广义表
      • 定义
    • 1)基本操作
      • ①GetHead
      • ②GetTail
    • 2)构造存储结构的两种方法
      • 表头表尾
        • 结构定义
    • 3)递归算法
      • ①求广义表深度
      • ②复制广义表
      • ③创建广义表

1、数组

定义

数组是一种用于存储多个相同类型数据的集合,其元素在内存中连续存放并按照一定的顺序排列。这种有序性和连续性使得数组在访问时具有较高的效率。数组的特点包括所有元素具有相同的数据类型、可以通过索引快速访问任意元素、支持各种操作如遍历和排序等,并且数组的定义和初始化方式在不同编程语言中有所不同。

1)数组存储地址计算

数组存储地址的计算主要依赖于数组的起始地址、元素的数据类型(即每个元素所占的字节数)以及元素的下标位置

一维数组的存储地址计算

首元素地址:假设一维数组A的首地址为L,且每个元素占用C个字节。则数组中任意元素A[i]的地址可以通过公式Loc(A[i]) = L + i * C来计算。
示例:如果数组A的首地址是1000,每个元素占4个字节,那么A[3]的地址就是1000 + 3 * 4 = 1012。

二维数组的存储地址计算

行优先存储:在行优先存储中,二维数组的元素按照行的顺序依次存储。对于二维数组B[m][n],元素B[i][j]的地址计算公式为Loc(B[i][j]) = Loc(B[0][0]) + (i * n + j) * C,其中C是每个元素占用的字节数。
列优先存储:在列优先存储中,二维数组的元素按照列的顺序依次存储。对于二维数组B[m][n],元素B[i][j]的地址计算公式为Loc(B[i][j]) = Loc(B[0][0]) + (j * m + i) * C。
示例:假设有一个3x4的二维数组B,按行优先存储,首地址为1000,每个元素占2个字节。那么B[2][3]的地址就是1000 + (2*4 + 3) * 2 = 1026。

多维数组的存储地址计算

对于更高维度的数组,地址计算方法类似,只是需要考虑更多维度的索引和步长。
例如,按行优先存储的三维数组D[m][n][p]的元素D[i][j][k]的地址计算公式为Loc(D[i][j][k]) = Loc(D[0][0][0]) + ((i * n * p + j * p + k) * C)。
列优先:Loc(D[i][j][k]) = Loc(D[0][0][0]) + (knm+j*m+i)*C

示例

数组A[9][3][5][8],首地址为100,每个元素占4个字节,求a[8][2][4][7]的地址

①行优先

100+(8358+258+48+7)*4

②列优先

100+(7539+439+29+8)*4

2)稀疏矩阵的转置

三元组顺序表

由于稀疏矩阵中含有大量的零元素,空间利用率很低,所以需要三元组顺序表来表示稀疏矩阵中的非零元素,它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中,节省存储空间并简化运算

在这里插入图片描述
在这里插入图片描述

结构定义
typedef struct{int i,j;//该非零元的行下标和列下标ElemType e;
}Triple;
typedef struct{Triple data[MAXSIZE + 1];//非零元三元组表,data[0]未用int mu,nu,tu;//矩阵的行数、列数和非零元总数
TSMatrix;

①普通矩阵转置

for(col = 1;col <= nu;++col)for(row = 1;row <= mu;++row)T[col][row] = M[row][col];

②三元组顺序表转置稀疏矩阵

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){//采用三元组表存储表示,求稀疏矩阵M的转置矩阵TT.mu = M.nu;  T.nu = M.mu;  T.tu = M.tu;if(T.tu){q = 1;for(col = 1; col <= M.nu; ++col)for(p = 1; p <= M.tu; ++p)if(M.data[p].j == 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;  ++q;}}return OK;
}//TransposeSMatrix

③稀疏矩阵的快速转置

如果能预先确定就诊M中每一列(即T中的每一行)的第一个非零元在b.data中应有的位置,那么在对a.data中的三元组一次作转置时,便可直接放到b.data中恰当的位置上去,提高运算效率。

为此,需要附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数,cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有
cpot[1] = 1;
cpot[col] = cpot[col - 1] + num[col - 1], 2 <= col <= a.nu
在这里插入图片描述

接下来就可以利用num和cpot向量快速确定转置后各元素在三元组表中的位置,提高运行效率

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){//采用三元组顺序表存储表示,求稀疏矩阵M的转置矩阵TT.mu = M.nu;  T.nu = M.mu;  T.tu = M.tu;if(T.tu){for(col = 1; col <= M.nu; ++col)num[col] = 0;for(t = 1; t <= M.tu; ++t)++num[M.data[t].j];//求M中每一列含非零元个数cpot[1] = 1;//求第col列中第一个非零元在b.data中的序号for(col = 2; col <= M.nu; ++col)cpot[col] = cpot[col - 1] + num[col - 1];for(p = 1; p <= M.tu; ++p){col = M.data[p].j;  q = cpot[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;  ++cpot[col];//当一列的第一个元素转置完成后,下一个需要转置的是三元组表的下一个位置}//for}//ifreturn OK;
//FastTransposeSMatrix

3)十字链表

十字链表是一种用于表示稀疏矩阵的特殊存储结构,它通过行优先的顺序将非零元素及其位置信息存储在一个线性表中。每个节点包含五个字段:行号、列号、值、向下指针和向右指针,从而形成一个十字交叉的链表结构。这种结构不仅节省了存储空间,还提高了运算效率,并使得对稀疏矩阵的操作更加灵活和高效。

在这里插入图片描述

结构定义

typedef struct OLNode{int i,j;//该非零元的行和列下标ElemType e;struct OLNode *right,*down;//该非零元所在行表和列表的后继链域
}OLNode; *OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;//稀疏矩阵的行数、列数、非零元总数
}CrossList;

2、广义表

定义

广义表是一种非线性的数据结构,它允许表中的元素既可以是单个数据项(原子),也可以是另一个广义表。这种结构使得广义表能够表示复杂的嵌套关系和层次结构。广义表的特点包括其元素的多样性(可以是原子或其他广义表)、结构的灵活性(可以嵌套任意深度)以及操作的复杂性(如求表头、表尾等)。在存储上,广义表通常采用链式结构来表示,以方便处理其复杂的嵌套关系。

1)基本操作

①GetHead

获取广义表的第一个元素,可以是原子,可以是列表

②GetTail

除了广义表中第一个元素的所有其他元素的集合,无论该元素是什么,都需要在外面额外套上一个(),即使是空表,或该值本来就有()

该部分主要是在给出一个广义表时能正确获取表头和表尾

2)构造存储结构的两种方法

表头表尾

结构定义
typedef struct GLNode{ElemTag tag;//公共部分,用于区分原子结点和表结点union{//原子结点和表结点的联合部分AtomType atom;//atom是原子结点的值域,AtomType由用户定义struct{struct GLNode *hp,*tp;}ptr;//ptr是表结点的指针域,ptr.hp和[tr.tp分别指向表头和表尾};
}*GList;//广义表类型

示例:
A = ()
B = (e)
C = (a,(b,c,d))
D = (A,B,C)
E = (a,E)//递归表 E = (a,(a,(a,…)))
在这里插入图片描述

另一种方法我还没理解,就不在这里说了

3)递归算法

由于广义表的定义本身就具有一定的递归性,且其子表问题与其本身的问题具有极高相似度、关联性,所有递归算法与广义表操作具有极好的适配性

①求广义表深度

int GListDepth(GList L){//采用头尾链表存储结构,求广义表L的深度。if C!L) return 1// 空表深度1if (L—> tag == ATOM) return 0;// 原子深度 0for (max=0, pp=L; PP; pp=pp->ptr. tp) {dep = GListDepth(pp—>Ptr.hp);// 求以 pp—>ptr.hp 为头指针的子表深度if (dep > max) max = dep;}return max + 1//非空表的深度是各元素的深度的最大值+1
}// GListDepth

②复制广义表

Status CopyGList(GList &T, GList L) {// 采用头尾链表存储结构,由广义表L复制得到广义表T。if(!L)  T = NULL;// 复制空表else {if(!(T= (GList) malloc(sizeof(GL.Node))))exit(OVERFLOW);// 建表结点T -> tag = L -> tag;if (L—> tag == ATOM) T -> atom = L -> atom;// 复制单原子else {CopyGList(T-> ptr. hp, L->ptr. hp) ;// 复制广义表L->ptr.hp 的一个副本T->ptr.hpCopyGList(T—> ptr. tp, L->ptr. tp);// 复制广义表L->ptr.tp 的一个副本T->ptr.tp} // else} // elsereturn OK;
}// CopyGList

③创建广义表

三种情况:

  1. 带括弧的空白串
  2. 长度为1的单字符串
  3. 长度>1的字符串

显然,前两种情况为递归的终结状态,子表为空表或只含一个原子结点,后一种情况为递归调用

Status CreateGList (GList &L, SString S) {//采用头尾链表存储结构,由广义表的书写形式串S创建广义表L。设 emp="()"if (StrCompare(S, emp))L=NULL//创建空表else {if (! (L = (GList) malloc (sizeof (GLNode)))) exit (OVERFLOW); //建表结点if (StrLength(S)==1){L->tag = ATOM; L->atom =S;}// 创建单原子广义表else {L->tag = LIST; p = L;SubString (sub, S, 2, Strength(S)2) ;// 脱外层括号do// 重复建n 个子表sever(sub,hsub);// 从 sub中分离出表头串hsubCreateGList(p->ptr. hp,hsub);q = p;if (!StrEmpty(sub)){// 表尾不空if (!(p = (GLode * ) malloc (sizeof (GLNode))))exit (OVERFLOW) ;p->tag = LIST; q->ptr.tp = p;}//if}while (! StrEmpty (sub)) ;q—>ptr. tp = NULL;}//else} // elsereturn OK;
}// CreateGListStatus sever(SString &str, SString &hstr) {// 将非空串 str 分割成两部分:hsub 为第一个‘,’之前的子串,str 为之后的子串n= StrLength(str); i=0;k=0//k记尚未配对的左括号个数do {// 搜索最外层的第一个逗号++i;SubString(ch, str,i,1);if(ch =='(')  十十k;else if (ch==‘)’)  --k;} while (i<n && (ch! =','|| k! =0));if (i<n){SubString (hstr, str, 1, i—1)SubString(str, str, i+1, n—i)} else {StrCopy (hstr, str); ClearString(str) }
} // sever

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466343.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

云集电商:如何通过 OceanBase 实现降本 87.5%|OceanBase案例

云集电商&#xff0c;一家聚焦于社交电商的电商公司&#xff0c;专注于‘精选’理念&#xff0c;致力于为会员提供超高性价比的全品类精选商品&#xff0c;以“批发价”让亿万消费者买到质量可靠的商品。面对近年来外部环境的变化&#xff0c;公司对成本控制提出了更高要求&…

【React.js】AntDesignPro左侧菜单栏栏目名称不显示的解决方案

作者&#xff1a;CSDN-PleaSure乐事 欢迎大家阅读我的博客 希望大家喜欢 使用环境&#xff1a;WebStorm 目录 问题概述 原因 解决方案 解决方法 潜在问题修改 最终效果呈现 额外内容 管理员界面路由配置 WebStorm背景更换 法一&#xff1a; 法二&#xff1a; 问题概…

一文透彻了解电容

文章目录 一、电容的作用二、电容的选择三、电容的分类四、多层陶瓷电容五、钽电容替代电解电容的误区六、旁路电容的应用问题七、电容的等效串联电阻 ESR八、电解电容的电参数九、电容器参数的基本公式十、电源输入端的 X,Y 安全电容 一、电容的作用 作为无源元件之一的电容&…

Python OpenCV 傅里叶变换

傅里叶变换 傅里叶变换比较难和不容易理解&#xff0c;有错的地方请见谅 傅里叶原理表明&#xff1a;任何连续测量的时序或信号&#xff0c;都可以表示为不同频率的正弦波信号的无限叠加。也就是说&#xff0c;傅里叶变换是一种特殊的积分变换&#xff0c;它能将满足一定条件的…

如何调整pdf的页面尺寸

用福昕阅读器打开pdf&#xff0c;进入打印页面&#xff0c;选择“属性”&#xff0c;在弹出的页面选择“高级” 选择你想调成的纸张尺寸&#xff0c;然后打印&#xff0c;打印出来的pdf就是调整尺寸后的pdf

WPF中如何简单的使用CommunityToolkit.Mvvm创建一个项目并进行 增删改查

目录 开始前准备的数据库dbblog如下&#xff1a; 第一步&#xff1a;创建项目后下载四个NuGet程序包 第二步&#xff1a;删除原本的MainWindow.XAML文件 并创建如下的目录结构 然后在View文件夹下面创建Login.XAML和Main.XAML 并且在App.XAML中将启动项改为Login.X…

基于python多准则决策分析的汽车推荐算法设计与实现

摘要 随着汽车市场的快速发展和消费者需求的多样化&#xff0c;汽车选择变得愈加复杂。为了帮助消费者在众多汽车选项中做出明智的决策&#xff0c;基于多准则决策分析&#xff08;MCDA&#xff09;的汽车推荐算法应运而生。本研究旨在设计和实现一种基于 Python 的汽车推荐系…

xftp连接中不成功 + sudo vim 修改sshd_config不成功的解决方法

我们使用sudo vim不成功&#xff0c;但是我们使用sudo su就可以 了&#xff01; root用户权利更大&#xff01; 喵的&#xff0c;终于成功了&#xff0c;一个xftp连接半天不成功。&#xff08;添加上面的内容就可以连接成功了↑&#xff09;

vue:Transition

1. Transition 1. 基本用法 <Transition> 是Vue 提供的 “内置组件动画组件”&#xff0c;与一般的CSS过渡动画不同的是&#xff0c;它通过在特点时刻给元素或组件增加、移除类名来实现——在一个元素或组件进入和离开 DOM 时应用过渡动画。 下面是一个基本用法&#…

Python 中的字符串匹配算法

在 Python 中&#xff0c;字符串匹配算法用于在一个字符串中寻找一个子串的出现位置&#xff0c;这是许多文本处理任务的核心。下面我将介绍几种常用的字符串匹配算法以及它们在 Python 中的实现方式。 1、问题背景 在 Python 中&#xff0c;字符串匹配是一个非常重要的操作&a…

配置本地策略路由示例

组网需求 RouterA与RouterB间有两条链路相连。 用户希望实现本机下发的不同长度的报文通过不同的下一跳地址进行转发&#xff0c;其中&#xff1a; 长度为64&#xff5e;1400字节的报文设置192.168.1.2作为下一跳地址。长度为1401&#xff5e;1500字节的报文设置192.168.2.2…

【大数据学习 | kafka高级部分】文件清除原理

2. 两种文件清除策略 kafka数据并不是为了做大量存储使用的&#xff0c;主要的功能是在流式计算中进行数据的流转&#xff0c;所以kafka中的数据并不做长期存储&#xff0c;默认存储时间为7天 那么问题来了&#xff0c;kafka中的数据是如何进行删除的呢&#xff1f; 在Kafka…

推荐一款基于Flash的交互式园林设计工具:Garden Planner

Garden Planner是一款由Artifact Interactive开发的基于Flash的交互式园林设计工具。它允许用户以拖放的方式安排植物、树木、建筑物和各种对象&#xff0c;使园林规划变得简单直观。此外&#xff0c;Garden Planner提供工具来快速创建铺路、路径和围栏&#xff0c;帮助用户设计…

微信小程序开发,诗词鉴赏app,诗词推荐实现(二)

微信小程序开发&#xff0c;诗词鉴赏app&#xff08;一&#xff09;&#xff1a; https://blog.csdn.net/jky_yihuangxing/article/details/143501681微信小程序开发&#xff0c;诗词鉴赏app&#xff0c;诗词推荐实现&#xff08;二&#xff09;:https://blog.csdn.net/jky_yih…

关于诊断中的各种时间参数

前言&#xff1a; 因为不会转载&#xff0c;故在这里贴出原文连接&#xff0c;写的非常好&#xff01;条理清晰&#xff0c;一遍看懂king110108 原文链接&#xff1a;UDS之时间参数总结篇_uds时间参数-CSDN博客 以下内容是我自己对这篇文章的一些备注和理解&#xff0c;以及从测…

技术干货|HyperMesh CFD功能详解:虚拟风洞 Part 2

在上期 Part 1文章中&#xff0c;我们介绍了从 v2023 版本开始&#xff0c;虚拟风洞VWT&#xff08;Virtual Wind Tunnel&#xff09;模块合并到HyperMesh CFD中。用户在VWT模块中完成LBM求解器ultraFluidX的前处理设置&#xff0c;导出参数文件XML和模型文件STL&#xff0c;并…

H7-TOOL的CAN/CANFD助手增加帧发送成功标识支持, 继续加强完善功能细节

2.27版本固件正式携带此功能&#xff0c;包括之前做的负载率检测和错误信息展示也将集成到这个版本固件中。 对于接收&#xff0c;我们可以直接看到效果&#xff0c;而发送不行&#xff0c;所以打算在发送的地方展示下发送成功标识。CAN发送不像串口&#xff0c;需要等待应答后…

mysql5安装

1.下载安装包 https://downloads.mysql.com/archives/community/ mysql-5.7.44-1.el7.x86_64.rpm-bundle.tar tar -xvf mysql-5.7.44-1.el7.x86_64.rpm-bundle.tar2.安装依赖 yum -y install perl yum -y install net-tools yum install numactl libaio libaio-devel -y也可…

大模型应用编排工具Dify二开之工具和模型页面改造

1.前言 简要介绍下 dify&#xff1a; ​ 一款可以对接市面上主流大模型的任务编排工具&#xff0c;可以通过拖拽形式进行编排形成解决某些业务场景的大模型应用。 背景信息&#xff1a; ​ 环境&#xff1a;dify-0.8.3、docker-21 ​ 最近笔者在做 dify的私有化部署和二次…

开放寻址法、链式哈希数据结构详细解读

一、开放寻址法&#xff08;Open Addressing&#xff09; 1. 定义 开放寻址法是一种哈希冲突解决策略&#xff0c;所有元素都存储在哈希表中。当发生冲突时&#xff0c;即两个键计算出的哈希值相同时&#xff0c;会按照一定的探查序列查找下一个可用的位置来存储新元素。 2.…