当前位置: 首页 > 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表达式的有用方…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...