1.2 数据结构的分类与应用

embedded/2024/11/14 20:02:25/

1.2 数据结构的分类与应用

  • 数据结构,就是字面意思,一门用来研究数据如何高效的在计算机中进行存储和查询的学科。
  • 几乎所有的数据结构,也都是从生活中和数学理论中,衍生而来。
    下表列出了常见的数据结构,我们先来熟悉一下他们的名字。
序号英文名中国大陆翻译中国香港翻译中国台湾翻译生活中的场景
1Array数组陣列陣列超市的货架上摆放着一排排的商品,每个格子只能放置一个商品,类似于数组的结构。
2Linked List链表鏈結列表鏈結串列人们在月台排队等车,每个人都知道前后两个人,类似于链表结构。
3Stack堆疊堆疊堆放盘子的方式,先放进去的盘子在底部,后放进去的在顶部,取盘子时也是从顶部开始取。这就类似于栈的先进后出(FILO)特性。
4Queue队列佇列佇列在银行办理业务时,客户需要按顺序排队等待叫号,符合队列先进先出(FIFO)的特性。
5Hash Table哈希表雜湊表雜湊表字典(如英汉词典),通过单词快速查找对应的释义,类似于哈希表的查找功能。
6Binary Tree二叉树二元樹二元樹家谱树,每个人有两个子女,分别在左右两侧,类似于二叉树的结构。
7Graph交通路网,各个城市通过公路、铁路等连接在一起,形成复杂的图结构。
8Heap堆積堆積优先级队列,如医院急诊室,根据病情严重程度安排就诊顺序,类似于堆的特性。

请注意,不同地区的翻译可能存在差异,但这里列出的是较为通用的翻译。

数组(Array)

  • 中国大陆将 Array 翻译为了数组,我认为在某种程度上会误导初学者。其实在更广义的场景中, Array 我们通常翻译为阵列或者队列。
    你可以把他理解成就是一个一个的数据紧挨着排好队的样子。当然数据可以是具体的数字也可以是一段话或者图片等。

在这里插入图片描述

链表(Linked List)

数组需要紧挨着的连续的存储空间,比如6个朋友去住酒店,他们要求房间都挨在一起,但不巧已经没有6个都挨在一起的房间了。不如他们妥协一下,分开住,7楼住2个房间,8楼住3个房间,10楼住1个房间,这就是链表。

链表中的每个元素,不需要挨在一起,只需要记住自己的后一个元素在哪里。

在这里插入图片描述

上面的链表我们通常称为单向链表,每个元素只记录自己的后继元素。
如果每个元素同时也记录了自己的前驱元素,称为双向链表。
在这里插入图片描述

栈(Stack)

栈,在中国大陆有些书籍教材也翻译为堆栈。字面意思为整齐的叠放。类似盘子或者书籍(平放)的常见摆放方式。栈这种数据结构,主要体现数据存入和取出的特殊顺序,为先进后出(FILO:First In Last Out),或者叫后进先出(LIFO:Last In First Out)。
我们比较熟悉的场景是,文件管理器和浏览器中通常都带有页面回退的功能,我们点击不同的链接进行页面跳转的时候,浏览器会将访问过的页面链接依次记录在栈中,而当点击返回按钮时,会依次取出栈中保存的页面链接,这个过程是后进先出的。

队列(Queue)

队列刚好与上面的栈相反,专门用来处理先来后到的事情。所以队列体现出的数据存入和取出的顺序为先进先出(FIFO:First In First Out)。比如我们将多首歌曲加入播放器的播放列表,默认情况下,播放器就会按照播放列表的顺序,依次播放歌曲。

哈希表(Hash Table)

Hash 是混杂、拼凑的意思,所以在中国香港和中国台湾通常将 Hash Table 翻译为杂凑表。中国大陆音译为哈希表或者书面一些的翻译为散列表。你可能已经被这些听起来乱七八糟的的名词给搞晕了。不过哈希表的原理和想解决的事情其实很简单。
我们试想一个场景,现在你想邀请你的几个朋友周末一起去看电影,这时你拿出手机打开通讯录,当你开始输入朋友的名字或者昵称来检索他的手机号时,哈希表就已经登场了。
所谓的哈希,就是将原来的数据(朋友的名字)通过一种哈希算法(散列算法),计算得到一个与之对应的新数据,称之为哈希值。哈希值本质上是用更加简短的数据来表示原有数据。
那哈希表有什么用呢?当你的通讯录非常大的时候,如果每次需要从头到尾找一遍,那么查找的时间复杂度为O(n),但如果使用哈希表存储通讯录,可以将时间复杂度变为O(1)。如果还记得关于时间复杂度知识的同学,应该能感受到这其中巨大的改变。

二叉树(Binary Tree)

树是一类数据结构的统称,他的名字很形象。我们生活中见到的树,露出地面的部分,下半部分通常是一个树干,上半部分通常会有庞杂的枝叶。

计算机的数据结构中的树,为了画图方便,将树干放在最上面,称之为 root(也就是根)。枝叶画在下面,类似下面这样。

细心的同学可能发现了,树和链表好像有相似之处。没错,树就是将链表的一对一,扩展成了一对多。对于计算机来说,所有的树都可以被等价转换为二叉树,而二叉树又比较符合计算机二进制的运算特点,所以我们通常使用和讨论最为广泛的,都是二叉树。

图(Graph)

这里的图,又是树的扩展,从一对多扩展为多对多。图中可以有多个元素,元素之间可以互相交错的产生多个关联,类似生活中的交通图或社交网络。

堆(Heap)

堆也是由二叉树演化而来,他的名字很形象,就像一个小土堆一样,通常会按照从大到小或者从小到大的顺序,将元素从上到下摆放在堆中,方便我们随时在堆顶取最大值或最小值。

      1╱   ╲2     3╱ ╲   ╱ ╲
4   5 6   7

http://www.ppmy.cn/embedded/137582.html

相关文章

七大经典基于比较排序算法【Java实现】

七种基于比较的排序算法 一.直接插入排序:1.1插入排序1.2希尔排序(缩小增量排序法) 二.选择排序2.1选择排序2.2堆排序(基于树(堆)的数据结构) 三.交换排序3.1冒泡排序3.1快速排序(大致分三种partition方法)…

MySQL第九章,数据访问和DAO模式

一、数据访问与Properties配置文件 数据访问是应用程序与数据库之间的交互过程。在Java开发中,我们通常使用JDBC(Java Database Connectivity)来实现数据访问。然而,直接编写JDBC代码可能会导致代码冗长、难以维护,并…

Springboot整合xxl-job

拉取xxl-job xxl-job: 一个分布式任务调度平台,其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线,开箱即用。 配置项目 执行sql语句 更改配置 启动 访问 任务调度中心http://127.0.0.1:8081/xxl-job-…

【图像压缩感知】论文阅读:Self-supervised Scalable Deep Compressed Sensing

tips:本文为个人阅读论文的笔记,仅作为学习记录所用。 Title:Self-supervised Scalable Deep Compressed Sensing Journal:IJCV 2024 代码链接:GitHub - Guaishou74851/SCNet: Self-Supervised Scalable Deep Comp…

反向代理模块

1 概念 1.1 反向代理概念 反向代理是指以代理服务器来接收客户端的请求,然后将请求转发给内部网络上的服务器,将从服务器上得到的结果返回给客户端,此时代理服务器对外表现为一个反向代理服务器。 对于客户端来说,反向代理就相当于…

vite-plugin-svg-icons 库作用

一、 图标管理与整合 1. 自动扫描与注册 该插件能够自动扫描指定目录下的 .svg 文件,并将这些文件注册为 Vue 组件。 这意味着开发者无需手动逐个导入 .svg 文件,大大简化了在 Vue 项目中使用 SVG 图标的过程。 例如:如果项目中有一个 ic…

teamviewer源代码 远程控制软件源代码 定制贴牌 自有知识产权

kkview 远程控制 远程桌面源代码 定制 贴牌,官网有联系方法 kkview.com 。 欢迎洽谈合作 已上架华为、小米应用市场,支持LINUX,WINDOWS.ANDROID,WEB.鸿蒙。 teamviewer源代码 远程控制源代码 定制贴牌 自有知识产权 主要功能: 远程桌面 一…

【Linux】多线程(概念,控制)

🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343🔥 系列专栏:https://blog.csdn.net/qinjh_/category_12625432.html 目录 再谈地址空间 线程概念 创建线程初识 线程的优点 线程的缺点 线程异常 L…