LV03-01-数据结构-数据结构基础

发表于 分类于 ， ， 本文字数： 1.9k 阅读时长 ≈ 7 分钟

本文主要是数据结构——基础知识相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。

点击查看使用工具及版本
Windows windows11
Ubuntu Ubuntu16.04的64位版本
VMware® Workstation 16 Pro 16.2.3 build-19376536
SecureCRT Version 8.7.2 (x64 build 2214) - 正式版-2020年5月14日
开发板 正点原子 i.MX6ULL Linux阿尔法开发板
uboot NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)
linux内核 linux-4.15(NXP官方提供)
STM32开发板 正点原子战舰V3(STM32F103ZET6)
点击查看本文参考资料
参考方向 参考原文
------
点击查看相关文件下载
--- ---

一、什么是数据结构？

百度百科给到我们的数据结构的定义是：数据结构是计算机存储、组织数据的方式；数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究的是计算机数据间关系，包括了数据的逻辑结构和存储结构及其操作。

二、基本概念

  • 数据（ Data ）：数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。

  • 数据元素（ Data Element ）：数据元素是数据的基本单位，又称之为记录（ Record ）。一般来说，数据元素由若干基本项（或称字段、域、属性）组成。

  • 数据结构的三个方面

image-20220425161744667

三、数据的逻辑结构

逻辑结构表示的是数据运算之间的抽象关系，按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为线性结构和非线性结构两大类。按照数据间的逻辑关系再详细点分的话，主要有三种：一对一、一对多和多对多。

  • 一对一

类似集合（就是数据元素间除同属于一个集合外，无其它关系） ${1,2,3,…,n}$ 这类的数据，每个数据的左侧有且仅有一个数据与其相邻（除 1 外）；同样，每个数据的右侧也只有一个数据与其相邻（除 n 外），所有的数据都是如此，就说数据之间是一对一的逻辑关系。

image-20220425162153961

还有线性结构，例如线性表，栈和队列等。

image-20220425162320121
  • 一对多

如树形结构：

image-20220425162757592
  • 多对多

如图状结构

image-20220425163136390

四、数据的存储结构

存储结构就是逻辑结构在计算机中的具体实现方法。存储结构是通过计算机语言所编制的程序来实现的，因而是依赖于具体的计算机语言的。

  • 顺序存储（ Sequential Storage ）：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。例如 C 语言中的数组。
image-20220425164522972
  • 链式存储（ linked storage ）：将数据结构中各元素分布到存储器的不同点，用地址（或链指针）方式建立它们之间的联系。
image-20220425165100780
  • 索引存储：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。
image-20220425165903832
  • 散列存储：根据数据元素的特殊字段(称为关键字 key )，计算数据元素的存放地址，然后数据元素按地址存放。
image-20220425170840686