一、数据结构基本概念

数据结构基本概念

  • 一、数据结构基本概念
    • 1.基本概念和术语
      • 1.1数据(Data)
      • 1.2 数据元素(Data element)
      • 1.3 数据项 (Data Item)
      • 1.4 数据对象 (Data Object)
      • 1.5 数据结构 (Data Structure)
        • 1.5.1逻辑结构
          • 1.5.1.1 线性结构
          • 1.5.1.2 非线性结构
          • 1.5.1.3 集合结构
          • 1.5.1.4 线性结构
          • 1.5.1.5 树形结构
          • 1.5.1.6 图状结构或网状结构
        • 1.5.2 存储结构
          • 1.5.2.1顺序存储结构:
          • 1.5.2.2 链式存储结构:
          • 1.5.2.3 索引存储结构;
          • 1.5.2.4 散列存储结构或哈希存储结构:
      • 1.6 数据类型和抽象数据类型
        • 1.6.1 数据类型(Data Type)
        • 1.6.2 抽象数据类型 (Abatract Data Type,ADT)

一、数据结构基本概念

1.基本概念和术语

1.1数据(Data)

  • 是能输入计算机且能被计算机处理的各种符号的集合。

  • 是信息的载体。

  • 是对客观事物符号化的表示。

  • 能够被计算机识别、存储和加工。

      包括:数值型数据:整数、实数等;非数值型的数据:文字、图像、图形、声音等;
    

1.2 数据元素(Data element)

  • 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理;
  • 也简称为元素,或称为记录、结点或者顶点;
  • 一个数据元素由若干个数据项组成;

表1.1 学生表
|学号|  姓名 |    性别    |     出生日期      |      政治面貌     |
0001	关羽	男	2001.2.3	团员
0002	刘备	男	1999.3.4	党员
0003	张飞	男	2002.6.18	群众

1.3 数据项 (Data Item)

  • 构成数据元素的不可分割的最小单位。

表1.1 学生表
学号	姓名	性别	出生日期	政治面貌
0001	关羽	男	2001.2.3	团员
0002	刘备	男	1999.3.4	党员
0003	张飞	男	2002.6.18	群众

【注】数据、数据元素、数据项三者之间的关系:数据 > 数据元素 > 数据项

1.4 数据对象 (Data Object)

  • 是性质相同的数据元素的集合,是数据的一个子集
    【注】数据元素与数据对象:

  • 数据元素——组成数据的基本单位

      与数据的关系:是集合的个体。
    
  • 数据对象——性质相同的数据元素的集合

      与数据的关系:集合的子集。
    

1.5 数据结构 (Data Structure)

数据结构这门课着重关注的是数据元素之间的关系,和对这些数据元素的操作,而不是关心集体的数据项的内容。
  • 数据元素不是孤立存在的,它们之间存在着某种关系,数据元素相互之间的关系称为结构(Strcture)。
  • 是指相互之间存在一种或多种特定关系的数据元素集合。
  • 或者说,数据结构是带结构的数据元素的集合。

【注】

  • 同样的数据元素,可以组成不同的数据结构;

  • 不同的数据元素,可以组成相同的数据结构。

      数据结构包括以下三个方面的内容:1. 数据元素之间的逻辑关系,也称为逻辑结构2. 数据元素及其关系在计算机内存中的表示(又称为映像),成为数据的物理结构或者数据的存储结构3. 数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
    

数据结构的两个层次

1.逻辑结构

  • 描述数据元素之间的逻辑关系
  • 与数据的存储无关,独立于计算机
  • 是从具体问题抽象出来的数据模型

2.物理结构(存储结构)

  • 数据元素及其关系在计算机存储器中的结构(存储方式)
  • 是数据结构在计算机中的表示

3.逻辑结构与存储结构的关系:

  • 存储关系是逻辑关系的映像与元素本身的映像
  • 逻辑结构是数据结构的抽象,存储结构是数据结构的实现
  • 两者综合起来建立了数据元素之间的结构关系
1.5.1逻辑结构

逻辑结构的种类:

划分方式一:

  • 线性结构
  • 非线性结构

划分方式二:

  • 集合结构
  • 线性结构
  • 树形结构
  • 图状结构或者网状结构
1.5.1.1 线性结构

有且只有一个开始和一个终端结点,并且所有节点都最多只有一个直接前驱和一个直接后继。

例如:线性表、栈、队列、串
1.5.1.2 非线性结构

一个结点可能有多个直接前驱和直接后继

例如:树、图
1.5.1.3 集合结构

结构中的数据元素之间除了同属于一个集合的关系外,无任何其他关系

集合结构:由若干个元素组成,没有前驱后继关系,也没有父子关系。通常用于处理不同的数据类型,如包含整数、字符或者任意对象的集合。

在这里插入图片描述

1.5.1.4 线性结构

结构中的数据元素之间存在着一对一的线性关系

线性结构:由若干个数据元素组成,有明显的前驱后继关系,例如数组、链表、栈和队列。其中,数组是连续的内存空间,链表是离散的内存空间。
  • 除了第一个元素,所有元素都有唯一前驱
  • 除了最后一个元素,所有元素都有唯一后继
    在这里插入图片描述
1.5.1.5 树形结构

结构中的数据元素之间存在着一对多的层次关系

树状结构:由若干个节点组成,节点之间有明显的父子关系,根节点是整棵树的入口,叶子节点是没有子节点的节点。常见的树状结构有二叉树、堆、红黑树等等。

在这里插入图片描述

1.5.1.6 图状结构或网状结构

结构中的数据元素之间存在着多对多的任意关系

图结构:由若干个顶点和边组成,边可以是有向或无向的。每个顶点可以有一些相关的属性信息。图结构包括稠密图和稀疏图。稠密图指边数接近于节点数平方,而稀疏图指边数远小于节点数平方。

在这里插入图片描述

1.5.2 存储结构
1.5.2.1顺序存储结构:
  • 用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系有元素的存储位置来表示

      C语言中用数组来实现顺序存储结构
    

顺序存储:顺序存储是将数据元素按照其逻辑顺序连续地存储在一块连续的内存空间中。

	常见的顺序存储结构包括数组和顺序表。数组的元素在内存中是连续存储的,通过索引访问元素速度较快,但插入和删除操作需要移动元素,效率较低。

在这里插入图片描述

1.5.2.2 链式存储结构:
  • 用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系用指针来表示

      C语音中用指针来实现链式存储结构
    

链式存储:链式存储是通过使用指针或引用来连接数据元素,每个元素保存着指向下一个元素的指针。

常见的链式存储结构包括单链表、双链表和循环链表。链式存储结构能够动态地分配内存,插入和删除元素效率较高,但访问元素需要遍历链表从头到尾,效率较低。

在这里插入图片描述

1.5.2.3 索引存储结构;
	1.在存储节点信息的同时,还建立附加的索引表2索引表中的每一项成为一个索引项3.索引项的一般形式为:(关键字,地址)4.关键字是能唯一标识一个结点的那些数据项
  • 若每个节点在索引表中都有一个索引项,则该索引表称之为稠密索引(Dense Index)。
  • 若一组结点在索引表中只对应一个索引项,则该索引表称之为稀疏索引(Sparse Index)。

索引存储:索引存储是在数据记录外部建立附加的索引表,索引表中的每个记录包含两部分:索引项和数据地址。通过索引项可以快速定位到对应的数据。

	常见的索引存储结构包括有序索引、散列索引和倒排索引。索引存储结构通过维护索引表来提高数据的检索速度。

在这里插入图片描述

1.5.2.4 散列存储结构或哈希存储结构:
  • 根据结点的关键字直接计算出该节点的存储地址。

散列存储:散列存储是根据关键字直接计算出数据元素的存储位置,通过查找关键字和对应存储位置进行快速访问。

常见的散列存储结构包括散列表和哈希表。散列存储结构通过散列函数将关键字映射到存储位置,可以实现快速的插入、删除和查找操作。

在这里插入图片描述

1.6 数据类型和抽象数据类型

1.在使用高级程序设计语言编写程序时,必须对程序中出现的每个变量、常量或表达式,明确说明他们所属的数据类型2.一些最基础的数据结构可以用户数据类型来实现,如数组、字符串等3.而另一些常用的数据结构,如栈、队列、树、图等,不能直接用数据类型来表示4.高级语言中的数据类型明显的或隐含的规定了在程序执行期间变量和表达的所有可能得取值范围,以及在这些数值范围上所允许进行的操作

数据类型的作用:

  • 约束变量或常量的取值范围
  • 约束变量或常量的操作
1.6.1 数据类型(Data Type)

定义:数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称

数据类型=值的集合+值集合上的一组操作
  • 原子类型:其值不可再分的数据类型

     例如:int类型、bool类型等
    
  • 结构类型:其值可以在分解为若干个成分(分量)的数据类型

    例如:

    // 定义一个具体的结构类型,表示一个坐标信息                                                                                                        
    struct Coordinate{int x;   //横坐标int y;   //纵坐标
    

}

1.6.2 抽象数据类型 (Abatract Data Type,ADT)

定义:是指一个数学模型以及定义在此数学模型上的一组操作

  • 由用户定义,从问题抽象出数据模型(逻辑结构)

  • 还包括定义在数据模型上的一组抽象运算(相关操作)

  • 不考虑计算机内的具体存储结构与运算的具体实现算法

      抽象数据类型的形式定义:抽象数据类型可用(D,S,P)三元组表示其中:D是数据对象;S是D上的关系集;P是对D的基本操作集
    

一个抽象数据类型的定义格式如下:

ADT   抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT  抽象数据类型名
其中:数据对象、数据关系的定义用伪代码描述

基本操作的定义格式为:

  • 基本操作名(参数表)
  • 初始条件:<初始条件描述>
  • 操作结果:<操作结果描述>

基本操作定义格式说明:

  • 参数表: 赋值参数只为操作提供输入值

      引用参数以&打头,除可提供输入之外,还将返回操作结果
    
  • 初始条件:描述操作执行之前数据结构和参数应满足的条件

      若不满足,则操作失败,并返回相对应出错信息。若初始条件为空,则省略之。
    
  • 操作结果:说明操作正常完成之后,数据结构的变化状况和应返回的结果。

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

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

相关文章

基于JavaWeb+BS架构+SpringBoot+Vue校园一卡通系统的设计和实现

基于JavaWebBS架构SpringBootVue校园一卡通系统的设计和实现 文末获取源码Lun文目录前言主要技术系统设计功能截图订阅经典源码专栏Java项目精品实战案例《500套》 源码获取 文末获取源码 Lun文目录 第一章 概述 4 1.1 研究背景 4 1.2研究目的及意义 4 1.3国内外发展现状 4 1…

【C语言】指针——从底层原理到应用

C语言指针-从底层原理到花式技巧&#xff0c;用图文和代码帮你讲解透彻 目录 一、前言二、变量与指针的本质 1. 内存地址2. 32位与64位系统3. 变量4. 指针变量5. 操作指针变量 5.1 指针变量自身的值5.2 获取指针变量所指向的数据5.3 以什么样的数据类型来使用/解释指针变量所指…

[足式机器人]Part2 Dr. CAN学习笔记-动态系统建模与分析 Ch02-4 拉普拉斯变换(Laplace)传递函数、微分方程

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记-动态系统建模与分析 Ch02-4 拉普拉斯变换&#xff08;Laplace&#xff09;传递函数、微分方程 1. Laplace Transform 拉式变换2. 收敛域&#xff08;ROC&#xff09;与逆变换&#xff08;ILT&…

自编C++题目——战争

预估难度 困难 题目描述 国与国以河为界&#xff0c;有一天他们两国发生了战争&#xff0c;在边疆的战士开始了厮杀。小明是一个参谋&#xff0c;他也知道两国的兵都能打个人&#xff0c;所以他想让你帮忙安排布置兵&#xff0c;以击杀所有国的兵。 打仗规则 只能打在同一…

线性代数_同济第七版

contents 前言第1章 行列式1.1 二阶与三阶行列式1.1.1 二元线性方程组与二阶行列所式1.1.2 三阶行列式 1.2 全排列和对换1.2.1 排列及其逆序数1.2.2 对换 1.3 n 阶行列式的定义1.4 行列式的性质1.5 行列式按行&#xff08;列&#xff09;展开1.5.1 引理1.5.2 定理1.5.3 推论 * …

debug OpenBLAS library 和 应用示例

1. 构建openblas lib git clone gitgithub.com:OpenMathLib/OpenBLAS.git cd OpenBLAS/ 如果要安装在自定义文件夹中&#xff0c;可以修改 PREFIX 的定义&#xff1a; 将 PREFIX /opt/OpenBLAS 修改成 PREFIX ../local/ 然后构建&#xff1a; make -j make install 如果要…

Unity中BRP下的深度图

文章目录 前言一、在Shader中使用1、在使用深度图前申明2、在片元着色器中 二、在C#脚本中开启摄像机深度图三、最终效果 前言 在之前的文章中&#xff0c;我们实现了URP下的深度图使用。 Unity中URP下使用屏幕坐标采样深度图 在这篇文章中&#xff0c;我们来看一下BRP下深度…

时序预测 | Matlab基于CNN-LSTM-SAM卷积神经网络-长短期记忆网络结合空间注意力机制的时间序列预测(多指标评价)

时序预测 | Matlab基于CNN-LSTM-SAM卷积神经网络-长短期记忆网络结合空间注意力机制的时间序列预测(多指标评价) 目录 时序预测 | Matlab基于CNN-LSTM-SAM卷积神经网络-长短期记忆网络结合空间注意力机制的时间序列预测(多指标评价)预测效果基本介绍程序设计参考资料 预测效果 …

【动态规划】【字符串】C++算法:140单词拆分

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 字符串 LeetCode140:单词拆分 II 给定一个字符串 s 和一个字符串字典 wordDict &#xff0c;在字符串 s 中增加空格来构建一个句子&#xff0c;使得句子中所有的单词都在词典中。以任意顺序 返回…

LabVIEW在旋转机械故障诊断中的随机共振增强应用

在现代工业自动化领域&#xff0c;准确的故障诊断对于保障机械设备的稳定运行至关重要。传统的故障检测方法往往因噪声干扰而难以捕捉到微弱的故障信号。随着LabVIEW在数据处理和系统集成方面的优势日益凸显&#xff0c;其在旋转机械故障诊断中的应用开始发挥重要作用&#xff…

【linux】更改infiniband卡在Debian系统的网络接口名

在Debian或任何其他基于Linux的系统中&#xff0c;网络接口的名称由udev系统管理。通过创建udev规则&#xff0c;可以修改网络接口名称。以下是更改InfiniBand卡接口名称的一般步骤&#xff1a; 1. 找到网络接口的属性&#xff0c;以编写匹配的udev规则 可以使用udevadm命令查…

IoT 物联网 MQTT 协议 5.0 版本新特性

MQTT 是一种基于发布/订阅模式的轻量级消息传输协议&#xff0c;专门为设备资源有限和低带宽、高延迟的不稳定网络环境的物联网场景应用而设计&#xff0c;可以用极少的代码为联网设备提供实时可靠的消息服务。MQTT 协议广泛应用于智能硬件、智慧城市、智慧农业、智慧医疗、新零…

0-1背包问题-例题

题目摘自《卡码网》46题 题意理解 m种材料——对应m物品 大小问n的行李箱——对应大小为n的背包 所以该问题是一个0-1背包问题&#xff0c;采用动态规划的一般思路来解题。 解题思路&#xff1a; 动规五部曲&#xff1a; &#xff08;1&#xff09;定义二维dp数组&#xff0c;明…

springBoot-自动配置原理

以下笔记内容&#xff0c; 整理自B站黑马springBoot视频&#xff0c;抖音Holis 1、自动配置原理 1.收集Spring开发者的编程习惯&#xff0c;整理开发过程使用的常用技术列表一>(技术集A) 2.收集常用技术(技术集A)的使用参数&#xff0c;整理开发过程中每个技术的常用设置列表…

Python解析参数的三种方法

今天我们分享的主要目的就是通过在 Python 中使用命令行和配置文件来提高代码的效率 Let’s go! 我们以机器学习当中的调参过程来进行实践&#xff0c;有三种方式可供选择。第一个选项是使用 argparse&#xff0c;它是一个流行的 Python 模块&#xff0c;专门用于命令行解析&…

小家电type-c接口PD诱骗

小家电Type-C接口PD诱骗&#xff1a;未来充电的便捷与安全 随着科技的不断发展&#xff0c;Type-C接口已经成为了许多小家电产品的标配。而PD&#xff08;Power Delivery&#xff09;诱骗技术&#xff0c;作为一种新兴的充电技术&#xff0c;更是为小家电产品的充电带来了前所…

Transformer架构和对照代码详解

1、英文架构图 下面图中展示了Transformer的英文架构&#xff0c;英文架构中的模块名称和具体代码一一对应&#xff0c;方便大家对照代码、理解和使用。 2、编码器 2.1 编码器介绍 从宏观⻆度来看&#xff0c;Transformer的编码器是由多个相同的层叠加⽽ 成的&#xff0c;每个…

FreeRTOS——软件定时器

一、什么是定时器 简单可以理解为闹钟&#xff0c;到达指定一段时间后&#xff0c;就会响铃。 STM32 芯片自带硬件定时器&#xff0c;精度较高&#xff0c;达到定时时间后会触发中断&#xff0c;也可以生成 PWM 、输入捕获、输出 比较&#xff0c;等等&#xff0c;功能强大&a…

P12 音视频复合流——TS流讲解

前言 从本章开始我们将要学习嵌入式音视频的学习了 &#xff0c;使用的瑞芯微的开发板 &#x1f3ac; 个人主页&#xff1a;ChenPi &#x1f43b;推荐专栏1: 《C_ChenPi的博客-CSDN博客》✨✨✨ &#x1f525; 推荐专栏2: 《Linux C应用编程&#xff08;概念类&#xff09;_C…

电脑文件mfc100u.dll丢失的解决方法分析,怎么修复mfc100u.dll靠谱

mfc100u.dll丢失了要怎么办&#xff1f;其实很多人都遇到过这样的电脑故障吧&#xff0c;说这个mfc100u.dll文件已经不见了&#xff0c;然后一些程序打不开了&#xff0c;那么这种情况我们要怎么解决呢&#xff1f;今天我们就来给大家详细的说说mfc100u.dll丢失的解决方法。 一…