数据结构专题——那些难以理解的数据结构基本概念

本贴最后更新于 2342 天前,其中的信息可能已经事过景迁

不知有没有人和博主一样,在上大学的时候最头疼的一门课就是数据结构与算法了,其中枯燥的概念、冗长的伪代码都让博主昏昏欲睡。

尤其是严大妈在《数据结构》中开篇讲述的数据结构、数据类型与抽象数据类型的概念,让博主完美地将这三个概念混淆了很久(这里没有黑严大妈的意思……但是数据结构确实给当时没有认真听课的博主留下了深刻的印象)。

博主希望在这个系列的博文中将自己眼中的数据结构与各位同学进行分享,希望大牛们能不吝赐教或是对初学者能有一点帮助。

在本篇博文中我主要谈谈我对以下三个概念的理解,欢迎大家与我一起讨论。

  • 数据结构
  • 数据类型
  • 抽象数据类型

首先来看数据结构的概念:

数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。这种结构可以是逻辑结构或者是物理结构

逻辑结构是指数据之间的逻辑关系,比如

  • 当所有数据都属于一个集合,而彼此之间没有别的关系时,这就是逻辑上的集合关系,如下图;

c25091822d4541918a8b13f87773cf48-2017102821.11.48.png

  • 当数据之间有下图所展示的一一对应的关系时,就属于线性结构
    ceacc21e91f54dad9047fdca4835f8a2-2017102821.24.04.png

  • 当数据之间有下图所展示的一对多的关系时,就属于树形结构
    663d1a8bf22a46fe8ffee8be8c576860-2017102821.25.42.png

  • 当数据之间有下图所展示的多对多的关系时,就属于图形结构
    2fb5453f54464a8aacdac735766e1acb-2017102821.26.50.png

物理结构是指数据如何计算机中存储的形式

若数据被存放在连续的存储单元中,则属于顺序存储结构,这种数据结构中数据间的逻辑关系和物理关系是一致的。这种数据结构很简单,最常见的例子就是数组。当我们向计算机申请创建一个装有 10 个整型元素的数组时,计算机会在内存中找一块连续的空间,按照一个整型元素所需的内存大小乘以 10,为这个数组开辟所需的内存空间,其中第一个元素放在第一个位置,第二个元素放在第二个位置,依次摆放,如下图所示。

d6e8c50c58844f36bccc2b9c270983e0-2017102821.43.12.png

若数据被存放在任意的存储单元中,则属于链式存储结构,这种数据结构中的数据存放位置可以是连续的,也可以是不连续的。数据间的存储关系并不能反应它的逻辑关系,因此需要指针来存放元素的位置,这样通过地址就可以找到相关联元素的位置了,如下图所示。
ec1a2da5af3a4a67a4a46be266ced158-2017102821.47.38.png

根据上述的概念来看,我们平常所说的树(Tree)、线性表(List)、图(Graph)都属于数据结构,因为它们的元素满足逻辑结构中元素的特定逻辑关系。

同样,以 Java 语言为例,ArrayList(基于数组实现的线性表)、LinkedList(链表)也属于数据结构,因为他们的元素在计算机中是以顺序与链式的物理结构来存储的。

逻辑结构是面向逻辑关系的结构,而物理结构是面向计算机存储的结构。对于我们程序员来说我们更倾向于关注物理结构,因此我们更习惯叫 ArrayList 这种线性表的实现为数据结构。

接下来我们来看数据类型的概念:

数据类型:是指一组性质相同的值的集合及在此集合上的一些操作的总称。

同样以 Java 语言为例,每一个变量在被声明的时候我们都需要指明它的数据类型。因为内存需要知道你这个数据应该被分配多大的空间。

同样的一个变量 i=12, 如果它被声明为 byte 类型就会被分配 8 bits 的空间,而被声明为 int 类型就会被分配 32 bits 的空间。

通常来说,数据类型分为原子类型结构类型

原子类型就是不可再分的基本类型:整型、浮点型等等

结构类型就是由若干个原子类型组成符合类型。

以 Java 为例,原子类型就是 8 个基本数据类型,而结构类型就是引用类型。对于 C 语言、或是 C++ 而言,原子类型就是基本类型,结构类型就是 struct。

但是不同的硬件系统在将这些数据类型转换为底层语言时肯定会有不同。这点对于 C 语言来说尤为明显,比如 int 类型没有固定的取值范围,而是依赖于硬件系统来决定。

因此这些我们人为为数据划定的“类型”就有硬件的局限性了。

这也是抽象数据类型出现的原因。

抽象数据类型:是指一个数据模型及定义在该模型上的一组操作

抽象数据类型可以解决上述 int 类型在不同硬件上有不同取值的问题。

比如说,我们可以抽象出一个数据类型叫做整型。那么在任何硬件系统中需要用到的整数类型以及整数的操作都可以在这个抽象类型中声明。至于在某种编程语言中将它实现为 32 位的 int 类型还是 16 位的 int 类型抽象类型都不需要关心。

以 Java 语言为例,线性表 List 是一个抽象数据类型;但 ArrayList 与 LinkedList 就不是抽象数据类型,因为这两种具体的数据结构已经是线性表的具体实现了,并不具有抽象性。

三者的关系总结

  • 数据结构数据类型的关系

数据结构是由一个个的数据元素组成的,而这些数据在声明的时候都会属于某一种数据类型。

  • 数据结构抽象数据类型的关系

逻辑数据结构一般也可以看作抽象数据类型;但物理数据结构不是抽象数据类型,而是抽象数据类型的具体实现。

  • 数据类型抽象数据类型的关系

数据类型是人为规定的平台相关的类型;而抽象数据类型是将数学模型和模型的相关操作抽象出来

注:本文图片来源于程杰老师的《大话数据结构》

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 5 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    106 引用 • 152 回帖 • 2 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    21 引用 • 140 回帖 • 26 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 408 关注
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖 • 2 关注
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 688 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖 • 2 关注
  • JetBrains

    JetBrains 是一家捷克的软件开发公司,该公司位于捷克的布拉格,并在俄国的圣彼得堡及美国麻州波士顿都设有办公室,该公司最为人所熟知的产品是 Java 编程语言开发撰写时所用的集成开发环境:IntelliJ IDEA

    18 引用 • 54 回帖 • 1 关注
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    710 引用 • 1173 回帖 • 193 关注
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖
  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 232 回帖 • 17 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 247 回帖 • 211 关注
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 60 回帖 • 467 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    123 引用 • 168 回帖
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 430 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    25 引用 • 215 回帖 • 160 关注
  • gRpc
    10 引用 • 8 回帖 • 50 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    76 引用 • 37 回帖
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    163 引用 • 1446 回帖
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 249 关注
  • 微服务

    微服务架构是一种架构模式,它提倡将单一应用划分成一组小的服务。服务之间互相协调,互相配合,为用户提供最终价值。每个服务运行在独立的进程中。服务于服务之间才用轻量级的通信机制互相沟通。每个服务都围绕着具体业务构建,能够被独立的部署。

    96 引用 • 155 回帖
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖 • 2 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    171 引用 • 988 回帖
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    90 引用 • 59 回帖 • 4 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖