专栏首页最高权限比特流一文带你秒懂数据结构与算法的三大要素、五大特征!

一文带你秒懂数据结构与算法的三大要素、五大特征!

我叫《数据结构与算法》,是计算机世界的四大基石之一。

想来我应该是惹人怜爱的吧(认真脸),因为我仿佛听到了无数个初入计算机世界的同学的呐喊声(?)。

我作为一门简单学科,看到有很多的在半途弃我而去,我很是痛心疾首。于是,委托这位靓仔将我蕴藏的知识传播出去,让更多的人享受学习数据结构与算法的快乐。

咳咳~言归正传……

基本概念

首先我来自我拆解一下。请跟我读:数据、结构、算法

没错,正是这三部分构成了我。这可能和你的认知不同,以为我是由数据结构和算法够成的吧?

别急,请听我细细道来。

  1. 何为数据?

数据,是构成我的基石,没有数据,我就没有用武之地。 更夸张的说,没有数据,整个计算机世界可能都没了用武之地。

因为,数据是信息的载体。人类能够识别的数据,放到计算机世界中,不经过输入设备的转换,是无法被识别的。这种能被计算机识别的信息就叫做数据

比如,在Mysql数据库中,存储着这样一张数据表。

姓名

年龄

性别

23

李四

22

在我这里,诸如“姓名、年龄、性别”这样的表头属性被称作是数据项,而这些数据项构成了数据元素;最重要的是,数据元素是构成数据的基本单位

这里还有一个数据对象的概念,什么是数据对象?数据对象就是具有相同性质的数据元素的集合,且是数据的一个子集。那么在上述表格中就表示为“法外狂徒张三、23、男”和“李四、22、女”这样的集合。

当然,这些内容可以由更为简明的集合表示:

  1. 何为数据结构?

数据结构是数据相互之间存在的一种或者多种特定关系的数据元素的集合。

这么说你可能不是很明白,打个比方:

  • 一对恋人,他们就是一种一对一的关系,这是一种从逻辑上讲的关系,当然,排除海王这样的……
  • 教师与学生,明显是多对一的关系,一个老师可以教很多学生

上述的这两种情况,都是从逻辑上讲的,你肯定知道,还有其他种类的数据结构。

事实上,总共有三种数据结构,被我们称作是数据结构的三要素

  • 逻辑结构
  • 存储结构
  • 数据运算

数据结构三要素

  1. 数据的逻辑结构 数据的逻辑结构,按照字面意思理解就是数据元素之间的逻辑结构。你可以这样想,逻辑结构就是一种表面上的结构,表示着表面上人与人的逻辑关系。比如说一对恋人,男对女,这就是一种逻辑结构。

逻辑结构分为两种关系:

  • 线性关系
  • 非线性关系

所谓线性关系,就是诸如一对情侣这种一对一的关系,在数据结构中,线性表、栈和队列、串、数组、广义表都属于这种一对一的线性关系。

非线性关系是如一对多、多对一、多对多等的这种关系。比如前面举的例子教师与学生,典型的一对多关系。满足这种关系的数据结构有:集合、树、图。你可能会说,明明集合既不是一对一,也不是一对多。

是的,集合比较特殊。我们认为,集合中的数据元素,除了同属于一个集合外就没有其他的任何关系了,所以这也是一种非线性关系。

  1. 数据的存储结构

看到存储你会想到什么?硬盘、内存等存储介质,对吧?

实际上,存储结构说白了就是数据在计算机中的表示,即物理地址

包括数据元素的表示数据关系的表示

数据元素的表示,就是指数据在计算机中的地址;而数据关系的表示,就是表示数据之间有何种关系。

人们为了合理利用计算机的存储空间,研究出了四种存储方式:

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

顺序存储是最简单的一种存储方式,你只需要了解:**数据元素的逻辑关系就是其存储关系。**最简单的例子是顺序表,顺序表是连续空间上的一组元素。也就是说,逻辑上相邻的两个数,在存储地址上也相邻。这种存储方式,优点和缺点都很明显:

  • 优点:能够实现随机存取,也就是说,存取可以任意指定位置,不必遍历
  • 缺点:只能使用相邻的一片存储空间,也就是说存储空间可能成为限制,也许会产生大量的数据碎片

链式存储最为典型的代表就是单链表吧,从逻辑上看,单链表就像是一个由表头拉着的长锁链,但是其数据元素的具体位置是随机的,全部由指针指示存储位置。

  • 优点:不会出现碎片,能够充分利用所有存储单元
  • 缺点:每个元素因为存储指针而占用额外的存储空间,且只能实现顺序存取,即遍历

索引存储可能是最快的存储结构。我们可以把索引想象成PDF电子书的目录,有了目录,我们找相关内容肯定是十分简单的。索引存储是在存储数据元素的时候,同时建立数据元素的目录,这样就能快速检索了。

  • 优点:检索速度快
  • 缺点:附加索引表额外占用空间,增删数据时要修改索引表,花费更多时间

散列存储又称为哈希存储(HASH)。这种存储结构比较讨巧,是通过公式来计算数据真正的存储位置。比如说,我要存储数据1,公式是y=x+5,y表示存储地址,那么1就会被存放到位置6。当然,实际应用中计算公式肯定不会这么草率。

  • 优点:检索、增删结点的操作都很快
  • 缺点:若散列函数不好,则出现元素存储单元冲突(两个数据元素计算的地址一样),解决冲突会额外占用时间与空间
  1. 数据运算

数据运算包含两部分内容,即数据运算的定义和实现。

数据运算的定义是针对逻辑结构来讲的,指出了运算的功能。

数据运算的实现是针对存储结构来讲的,指出了运算的具体实现步骤。

数据运算这个时候是在是没啥可细说的,留待日后。

算法的五大特征

在说算法的五大特征之前,我们需要弄明白算法的定义:所谓算法,就是对特定问题的求解步骤的描述。

也就是说,算法是用来解决问题的,一个算法的执行,必然能够有结果,且这个结果符合我们预期的要求。

算法有五大特征,分别为:

  • 有穷性
    • 必须在执行有穷步骤后结束,且每一步都在有穷时间内完成。所以说,无限执行的算法是错误的,是不能被称作算法的。所以,写递归函数的时候千万当心。
  • 确定性
    • 每条指令必须有确切的含义,相同的输入只能得出相同的输出。即算法中不能出现含糊不清的表述,也不能出现两次相同输入,执行同一算法出现不同的结果的情况。
  • 可行性
    • 算法描述的操作都可以通过已经实现的基本运算执行有限次数实现。不能实现的算法要他何用?
  • 输入
    • 有零个或多个输入,注意,算法是可以没有输入的,但是必须有输出。
  • 输出
    • 有一个或多个输出,不能没有输出,没有输出的算法是错误的。

感谢各位阅读!以上就是这篇文章的全部内容啦!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 逻辑结构?存储结构?傻傻分不清……

    对于数据结构与算法的学习,我相信不管是新手还是老手,都会对“逻辑结构、存储结构”产生很多的疑问。你可能觉得不就是两个简单的概念嘛,早就了然于胸了。

    roobtyan
  • 漫谈计算机组成原理(四)主存

    本文承接《漫谈计算机组成原理(三)存储器概论》。在上一篇文章中,主要介绍了存储器的层次结构。而本文主要讲述存储器层次结构中的主存部分。 主存,给我们最直观的...

    roobtyan
  • 漫谈计算机组成原理(十)浮点数运算

    浮点数和定点数一样,都是计算机中数据的存储形式。定点数我们可以理解成纯小数或者纯整数,但是实际上在计算机中参与运算的数字并非都是定点数。比如,有些数据过大,比如...

    roobtyan
  • 大数据24小时 | 李彦宏“画饼”互惠金融,数据新闻第一人黄志敏离职转型抢滩大数据

    <数据猿导读> SAP推出最新数据仓库应用,帮助企业实现实时数字化运营;“麦谷科技”获同创伟业领投5000万元融资;财新传媒首席技术官黄志敏宣布离职……以下为您...

    数据猿
  • 声明性数据基础设施为数据驱动企业提供动力

    大数据、人工智能/ML和现代分析技术已经渗透到商业世界,成为企业战略的关键元素,以更好地服务客户、更快地创新和保持领先的竞争。数据是所有这些的核心。在本博客中,...

    CNCF
  • 张涵诚:大数据操作系统遐想

    本文为百分点产品市场总监张涵诚原创,授权CDA数据分析师发布,转载请获得授权 背景 到2025年,保守估算,全球将拥有1000亿连接,65亿互联网用户使用超过1...

    CDA数据分析师
  • 混合云环境中的数据保护

    静一
  • 企业云存储大幅降价乃至免费,背后暗藏的是数据的野心

    随着移动互联网的迅速发展,智能终端、可穿戴设备、智能家居、物联网以及基因测序正在快速普及。企业和用户每天接触的数据吞吐量呈现出指数级的增长趋势,我国社会正在步入...

    静一
  • 开发一个智能客服需要多少钱?

    现在很多网站的客服人员都会采用智能的聊天机器人回复客户的咨询问题,那如果要开发一个这样的聊天机器人,需要花费多少钱?

    人工智能的秘密
  • vivo 大规模特征存储实践

    本文旨在介绍 vivo 内部的特征存储实践、演进以及未来展望,抛砖引玉,吸引更多优秀的想法。

    2020labs小助手

扫码关注云+社区

领取腾讯云代金券