当前位置: 首页 > news >正文

如何描述元素与元素间的逻辑关系?

逻辑结构反映的是数据元素之间的关系,它们与数据元素在计算机中的存储位置无关,是数据结构在用户面前所呈现的形式。根据不同的逻辑结构来分,数据结构可分为集合、线性结构、树形结构和图形结构4种形式,接下来分别进行简要介绍。

1)集合

在集合中,数据元素都属于这个集合,但数据元素之间并没有什么关系。它类似于数学中的集合,如图所示。

集合

集合

2)线性结构

线性结构中的元素具有一对一的关系,通过前一个结点可以找到后一个结点,图1-1的学生信息表就是一个线性结构,数据元素逐个排列。线性结构中前后两个结点互有联系。

线性结构分为顺序存储和链式存储两种。

顺序存储是由一段地址连续的空间来存储元素;链式存储是由分散的单元空间来存储元素,存储单元由指针相连接。简单的线性结构如图所示。
线性结构链式储存

在线性结构中,除头尾结点外,可以通过前一个结点来寻找后一个结点,也可以通过后一个结点来寻找前一个结点。

3)树形结构

树形结构中,数据元素之间存在一对多的层次关系。图1-4为一棵普通的树。除根结点外,树形结构的每一个结点都必须有一个且只有一个前驱结点,但可以有任意个后继结点。这些数据元素有自顶向下的层次关系。

树形结构

4)图形结构

图形结构中的数据元素存在多对多的关系,每个结点的前驱和后继结点都可以是任意个,如图1-5所示。

图形结构

按照逻辑结构,数据结构可以分为上述4种类型,在后续的深入学习中,本书会逐一详细讲解。

2.存储结构

数据结构除了按照逻辑结构来分,还可以按照存储结构来分。

存储结构反映的是数据元素在计算机中的存储形式,如何在计算机中正确地描述数据元素之间的逻辑关系,才是数据结构的关键与重点。常用的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列表4种,接下来分别进行简要介绍。

1)顺序存储结构

顺序存储结构是把逻辑上相邻的结点存储在地址连续的存储单元里,数据元素之间的关系由存储单元是否相邻来体现。这种存储结构通常用高级语言上的数组来描述,数据的逻辑关系与物理关系是一致的。以数组inta[5]={100,20,3,56,266}为例,其中的元素a[0]~a[4]在逻辑上是连续的,在存储器中的物理地址也是连续的,如图1-6所示。

顺序结构

使用顺序存储结构存储数据时,系统为数据元素分配一段连续的地址空间。顺序存储结构可以提高空间利用率,而且对于随机访问元素,其效率非常高,因为逻辑上相邻的数据元素,其存储地址也是紧邻的,所以可以按元素序号来快速查找到某一个元素。

但也正因如此,如果要对顺序存储结构实现元素的插入和删除,效率则非常低。因为如果要插入一个元素,需要将这个位置之后的所有元素都向后移动一个位置;同样,如果要删除一个元素,需要将这个位置之后的所有元素都向前移动一个位置。

顺序存储结构在使用时有空间限制,当需要存取元素的个数多于预先分配的空间时,会出现“溢出”问题;当元素个数少于预先分配的空间时,又会造成空间浪费。

2)链式存储结构

链式存储结构在空间上是一些不连续的存储单元,这些存储单元的逻辑关系通过附加的指针字段来表示,例如C/C++语言中的指针类型,通过这些指针的指向来表明结点之间的联系。图1-3(b)为链式存储结构的示意图,但在此图中没有标明指针的指向。在链式存储结构中,可以有指向后继元素的指针字段,也可以有指向前驱元素的指针字段,如图1-7和图1-8所示。

插入元素T

这样在插入元素时不必移动任何一个元素,高效简洁。同理,当删除某一个元素时,只需将其前后两个元素连接起来即可,也无须移动其他元素。

但链式存储结构无法进行元素的随机访问。

对链式存储结构而言,空间利用率也较低,因为分配的内存单元有一部分被用来存储结点之间的逻辑关系。但链式存储在存储元素时没有空间限制,顺序存储与链式存储都是按需分配,只是链式存储可以在需要时方便地分配新空间,不会造成空间不足或者浪费。

3)索引存储结构

这种存储结构主要是为了方便查找数据,它通常是在存储结点信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,它由两个字段组成:关键字与地址。其中关键字唯一标识一个结点,地址是指向结点的指针。这种结构类似于人们常用的字典,如图所示。

索引储存结构

索引存储结构

这种索引表一个索引项对应一个结点,叫作稠密索引。如果索引表中一个索引项对应一组结点,叫作稀疏索引,稀疏索引表如图1-11所示。

稀疏索引

稀疏索引

索引表可以快速地对数据进行随机访问。又因为在进行数据的插入和删除时,只需要更改索引表中的地址值,不必移动结点,所以在数据更改方面也具有较高的效率。但是索引存储结构在建立结点时会额外分配空间来建立一个索引表,因此降低了空间利用率。

4)散列存储结构

散列(hash)存储又称为哈希存储,是一种力图将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。它的基本思想是通过一定的函数关系(散列函数,也称为哈希函数)计算出一个值,将这个值作为元素的存储地址。

散列存储的访问速度是非常迅速的,只要给出相应结点的关键字,它会立即计算出该结点的存储地址。因此它是一种非常重要的存储方法。数据存储的几种方式各有其优点,也各有其用途,不能说哪一种存储结构就比另一种好。在使用时,它们既可以单独使用,也可以组合起来使用,具体要根据操作和实际情况来决定采取哪一种方式,或者哪几种方式结合使用。

相关文章:

如何描述元素与元素间的逻辑关系?

逻辑结构反映的是数据元素之间的关系,它们与数据元素在计算机中的存储位置无关,是数据结构在用户面前所呈现的形式。根据不同的逻辑结构来分,数据结构可分为集合、线性结构、树形结构和图形结构4种形式,接下来分别进行简要介绍。 …...

【3】linux命令每日分享——mv改名或移动

大家好,这里是sdust-vrlab,Linux是一种免费使用和自由传播的类UNIX操作系统,Linux的基本思想有两点:一切都是文件;每个文件都有确定的用途;linux涉及到IT行业的方方面面,在我们日常的学习中&…...

【2023最火教程】Python性能测试框架Locust实战教程(建议收藏)

01、认识Locust Locust是一个比较容易上手的分布式用户负载测试工具。它旨在对网站(或其他系统)进行负载测试,并确定系统可以处理多少个并发用户,Locust 在英文中是 蝗虫 的意思:作者的想法是在测试期间,放…...

深入浅出C++ ——手撕AVL树

文章目录前言一、AVL 树介绍二、AVL树节点的定义三、AVL树的插入四、AVL树的旋转五、AVL树的验证六、AVL树的删除七、AVL树的性能八、AVL树的实现前言 在前面的文章中介绍了map / multimap / set / multiset 容器,这几个容器的底层都是按照二叉搜索树来实现的。但是…...

将多个springboot项目的pom.xml文件整合

将多个springboot项目的pom.xml文件整合 0.0、前因 ​ 刚入公司敲代码时、发现一个项目中会包含多个子项目、每个子项目会代表一个功能模块、这属实是把我这个菜鸟惊叹到了。而这种分而治之的方式也引申出一个问题:各子项目的依赖如何统一管理? ​ 我…...

【Unity实战100例】Unity串口通讯的消息接收解析和发送指令

目录 一.串口通信介绍 1.串口通信 2.名词介绍 1.上位机: 2.下位机: 3.串行端口...

资源消耗降低 90%,速度提升 50%,解读 Apache Doris Compaction 最新优化与实现

背景LSM-Tree( Log Structured-Merge Tree)是数据库中最为常见的存储结构之一,其核心思想在于充分发挥磁盘连续读写的性能优势、以短时间的内存与 IO 的开销换取最大的写入性能,数据以 Append-only 的方式写入 Memtable、达到阈值…...

【Mysql】 锁

【Mysql】 锁 文章目录【Mysql】 锁1. 锁1.1 概述1.2 全局锁1.2.1 介绍1.2.2 语法1.2.2.1 加全局锁1.2.2.2 数据备份1.2.2.3 释放锁1.2.3 特点1.3 表级锁1.3.1 介绍1.3.2 表锁1.3.3 元数据锁1.3.4 意向锁1.4 行级锁1.4.1 介绍1.4.2 行锁1.4.3 间隙锁&临键锁1. 锁 1.1 概述…...

Android 流量统计

Android 流量统计最近项目上有一个应用流量统计的功能需要实现,在此总结一下 流量统计架构 在Android9.0之前,流量监控是基于xt_qtaguid模块的,通过读取/proc/net/xt_qtaguid/stats文件内容进行解析获取对应流量数据。 Android9.0之后&…...

如何保证数据的安全?对称和非对称加密,身份认证,摘要算法,数字证书等傻傻分不清?波哥图解带你彻底掌握

支付安全 1.基础概念 明文:加密前的消息叫“明文”(plain text) 密文:加密后的文本叫“密文”(cipher text) 密钥:只有掌握特殊“钥匙”的人,才能对加密的文本进行解密,…...

计算机网络概述

目录前言计算机网络的形成<font colorblue>计算机定义与分类计算机网络的定义计算机网络的分类1.按网络的覆盖范围分类2.按网络采用的传输技术分类按网络的拓扑分类计算机网络的组成计算机网络体系结构层次结构体系ISO/OSI 参考模型Tcp/ip体系结构这就是计算机网络的基础…...

小学生学Arduino---------点阵(二)动态图片以及文字

今天进阶了利用人眼视觉暂留原理制作动态的图片变换。 1、熟练掌握图片显示器的使用 2、创作多种动态图片、文字的显示 3、明确动态图片、文字显示过程 4、掌握图片显示器中清空指令的使用 5、搭建动态图片、文字的显示电路 6、编写动态图片、文字的程序 复习&#xff1a; 绘…...

【C语言】-程序编译的环境和预处理详解-让你轻松理解程序是怎么运行的!!

作者&#xff1a;小树苗渴望变成参天大树 作者宣言&#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 &#xff0c;就 给 作 者 点 点 关 注 吧&#xff01; 程序的编译前言一、 程序的翻译环境和执行环境二、 详解翻译环境2.1编译环境2.1.1预编…...

MapBox动态气泡图渲染教程

先来看效果: 视频效果: 屏幕录制2023-02-22 15.34.57 首先我们来介绍一下思路。对于mapbox和openlayers这样的框架来讲,气泡图中的气泡本质上就是一个div,就是将一个dom元素追加到canvas上的固定位置而已。 在mapbox中有marker的概念,官网也有示例: Attach a popup to …...

在 Ubuntu18.04 上编译安装 GMP

&#xff08;2021.08.04&#xff09;最近为了安装 IBM 的开源项目 HElib C&#xff0c;需要在服务器上先安装GMP和NTL&#xff0c;NTL需要依赖GMP&#xff0c;所以先来安装一下GMP&#xff0c;记录一下在服务器上安装成功的过程&#xff1a;&#xff09; 直接安装libgmp二进制文…...

到底什么样的条件才能被浙大MBA录取?攻略集合

新一年管理类联考已悄然启动&#xff0c;很多考生把目标也都放在了浙江大学MBA项目上&#xff0c;那么浙江大学MBA项目好考吗&#xff1f;报考流程是怎样的&#xff1f;杭州达立易考教育在这里给大家汇总整理了浙大MBA项目相关资讯&#xff0c;分享给想要报考浙大MBA的同学&…...

Impacket工具使用

Impacket工具说明 Impacker是用户处理网络协议的Python类集合,用于对SAB1-3或IPv4/IPv6 上的TCP/UPD/ICMP/IGMP/ARP/IPv4/IPv6/SMB/MSRPC/NTLM/Kerberos/WMI/LDAP 等进行低级的编程访问,数据包可以从头开始构建,也可以从原始数据包中解析, 面向对象API使用处理协议的深层结构变…...

华为OD机试真题Python实现【RSA 加密算法】真题+解题思路+代码(20222023)

RSA 加密算法 题目 RSA 加密算法在网络安全世界中无处不在 它利用了极大整数因数分解的困难度,数据越大安全系数越高 给定了一个32位正整数,请对其进行因数分解 找出哪两个素数的乘积 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 ## 输…...

App.vue中读取不到路由的信息

问题&#xff1a; ​ 首先定义了一个路由&#xff0c;并且在路由元里面存储了一个变量&#xff0c;在App.vue里面访问这个变量的时候却显示undefined&#xff01;在路由对应的组件中却能访问到&#xff01; 定义的路由元信息&#xff1a; 为啥访问不到…,懵逼的我在App.vue里…...

Lambda表达式详解

文章目录1、Lambda表达式简介2、如何使用Lambda表达式3、在哪里使用Lambda表达式3.1 函数式接口3.2函数描述符4、四大核心函数式接口4.1 Predicate4.2 Consumer4.3 Function4.4 Supplier5、方法引用5.1 方法引用的使用情况6、构造器引用7、数组引用8、复合Lambda表达式的有用方…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...

CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)

漏洞概述 漏洞名称&#xff1a;Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号&#xff1a;CVE-2023-25194 CVSS评分&#xff1a;8.8 影响版本&#xff1a;Apache Kafka 2.3.0 - 3.3.2 修复版本&#xff1a;≥ 3.4.0 漏洞类型&#xff1a;反序列化导致的远程代…...

比特币:固若金汤的数字堡垒与它的四道防线

第一道防线&#xff1a;机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”&#xff08;Hashing&#xff09;就是一种军事级的加密术&#xff08;SHA-256&#xff09;&#xff0c;能将信函内容&#xff08;交易细节&#xf…...