enter image description here

第 1 章 数据结构和算法简介


当今世界是一个数字化的世界,科技已经影响了我们生活的方方面面,而这些科技背后运行的东西是程序!而程序本质是什么?

程序 = 数据结构 + 算法

是的,程序的本质就是数据结构和算法的综合体!

但是程序的目的是用来解决某个实际问题的!也就是说数据结构和算法是用来解决实际问题的!那么数据结构和算法与实际问题有什么关系呢?数据结构和算法如何解决实际问题的呢?数据结构狗和算法有哪些特征和分类呢?

这些问题,我们将马上来一一解答!

首先先让我们从整体上对本章内容做一下了解。

本章内容如下:

  • 生活中的数据结构和算法

  • 数据结构和算法的重要性

  • 为什么是PHP?

  • 认识ADT

  • 数据结构常见类型

  • 认识算法

1.1 生活中的数据结构和算法

生活中的数据结构?!

请你先不要吃惊!也许你认为数据结构只存在于计算机程序中特别抽象的东西!但是事实恰恰相反!数据结构实际上原产于“现实”!是的!这里的“现实”指定就是现实世界,指的是真实的生活!

首先让我们来看一个相信大家都经历过的场景:排队购票! 下面给出的图片可以帮你回忆这种场景!

enter image description here

像这种一个一个有序排列的场景实际上就是一种数据结构--队列!

下面再给你看一个真实的场景!计划便签!你想想我们做计划的时候都是一张张贴上去,但是要完成计划,都是从最上面开始!最先贴上去的反而最后完成!像这种后来反而先执行的场景就是一种典型的数据结构--栈!

enter image description here

ok!继续看下面一个!是我国的地区分级表!最上面的是伟大的中国,中国下面是省级,省级下面是市级!当然还可以再细分!那么像这种出现了层级关系的场景又是另外一种典型的数据结构--树!

enter image description here

咱们最后再看一个,下面是对A的一个朋友圈的描述,假设每个圆圈都代表了一个人!那么这些人之间,有的互相有关系,有些人之间并不认识。那么像这种互相之间可能有多种关系的场景,又描述了另外一种典型的数据结构--图!

enter image description here

再让我们举一个生活中算法的例子!

就那我们手机上的电话簿来说!或者你微信上的联系人列表!现在假设你要查找某个以T打头的联系人,请问你,你会从头开始一个一个查吗?你还是一下跳到第一个以T开头的位置开始找!我相信你会使用第二种方法!其实这个过程中,你既应用了一种数据结构--哈希表,也使用了一种高效的算法--二分查找。

好了,你也许会举出更多更多的例子出来!尤其是学完本套课程!你会发现身边处处都是数据结构!处处都是算法!

其实各种数据结构都是对生活特定场景的总结,然后起了个名字!算法呢,也是对解决问题过程的描述!生活中,你身边,到处都是他们的身影!

所以,数据结构和算法,是一门贴近实际,又是解决实际问题的非常有用的一门学科!

通过上面的内容,我们明白了其实数据结构和算法是基于生活的!了解这个是为了让我们有一个更真实的认知!

但是数据结构和算法到底有多重要呢?数据结构和算法是如何定义的呢?如何实现呢?有哪些类型呢!下面就让我们一个一个的解决这些问题!

1.2 数据结构和算法的重要性

要了解数据结构和算法的的重要性,先让我们给它们明确的定义!

首先让我们谈谈数据结构!

数据结构(data structure)就是计算机中存储和组织数据的一种特定的形式,其目的是为了让数据的关系更合理,处理更高效!

例外一种更加简洁的定义方式是

数据结构 = 数据 + 结构

其实我认为下面的这种方式固然简洁,但是也更直接说明了数据结构的本质!数据结构实际上包含了两个主要的方面!一方面描述了数据的存储,另一方面更加重要的是可以描述数据之间的关系!

想想我们的生活就知道了,排队时每个人后面只有一个,这就是一对一的线性关系!公司中一个上级管理多个直接的下级,这是分层的一对多的树形关系!朋友之间的关系很复杂,可以描述成多对多的图形关系!当然班级中各个同学之间从学习这个层面上讲,大家只是聚在一个班级中,相互还是独立的,这个我们就能描述成集合关系!所系其实按照数据之间的关系来分的话,数据结构可以分为下面几种:

  • 集合关系:简单的集中在一起;
  • 线性结构:一对一的关系;
  • 树形结构:一对多的层级关系;
  • 图形结构:多对多的关系。

通过这个分类,大家可以明白一个问题!结合实际问题,使用良好的数据结构来存储和描述该实际问题可以帮助我们更加高效的解决它!其实这个也很好理解!现实生活中我们为了更加高效的管理和解决实际问题还要分类管理我们的数据呢!例如文件要归档分类管理!例如图书要分类按照编号排放!例如你通讯录里的好友名单是不是亲人、好友、同事等等也要分类存放!所以,要把数据存入计算机一样的道理!都是为了更加高效的管理和使用数据!

所以采用良好的数据结构,对于能否高效的解决实际问题非常的重要!结合实际生活,这个更好理解!

OK,让我们再来谈谈算法!

什么是算法呢?

算法(algorithms)是针对特定的问题,经过精心设计的用来一步步解决该问题从而得到答案的过程。

听起来是不是有些熟悉?如果把上面的定义拿到生活中,我们可以用另外的词汇来代替算法--方法!

是的,生活中,我们把解决某个问题的步骤或过程叫做方法!而在计算机科学中,解决问题的步骤我们就称之为算法!其实呢,一样的道理!

这里举一个广为人知的栗子来说明什么是算法:如何把大象关进冰箱?

  • 首先要准备一台足够大的冰箱;
  • 把冰箱门打开;
  • 把大象装进冰箱;
  • 把冰箱门关上。

以上我们描述的就是“把大象装进冰箱”这个问题的解决步骤,我们称之为“解决这个特定问题的方法”。那么它是不是一个 “算法”呢?是的!它也是一个算法!你也许会说不是在计算机科学中,我们管解决问题的步骤才叫算法吗!对的,现在如果我告诉你我要把这个问题用计算机来解决!你还有疑问吗?或许对于大多数人而言,还是感觉彷徨!因为这里我们没有使用任何的计算机语言!没有使用C语言,java语言,甚至是我们这本教程里使用的PHP语言!但是这并不妨碍我使用了一门“语言”把这个问题描述明白了!而对于算法而言,它并不在意你是使用了计算机语言,还是自然语言,甚至是哑语!其实算法,从其含义上来说,算法是解决问题的步骤的思想的描述!而我们使用计算机语言来实现算法是算法的实现的过程仅仅是为了让计算机能执行!所以算法和算法的实现是两码事!

但凡是方法就有好坏!算法既也是方法!那么一个优秀的算法和一个常规的算法到底差别有多大呢?举一个我们都能感受到的例子:搜索!

假设给你100条有序的记录,要查找一条指定的记录,普通的算法是从头一条一条的比对,直到找到为止,最坏的情况下,你要找100次! 有一种二分查找法,要找7次就找到了! 如果是40亿条数据中找数据呢?第一种方法,最坏要找40亿次!用二分查找最多需要32次就找到了!吃惊吗?这就是差距!普通的算法可能需要几年,几十年才能搞定的东西,优秀的算法可能几秒钟就搞定了!

那么究竟数据结构和算法是什么关系呢?我很喜欢这样一个比喻:

数据结构和算法的关系就像米与巧妇!数据结构是米,是对事物本体的内容存储!算法是巧妇!她研究的是如何利用数据结构更好的解决实际问题!也就是把米做成更好吃的饭!米的质量越上乘,对巧妇的技艺要求就越低,同样,巧妇的厨艺越精湛,食品的味道越佳!如果米的质量和巧妇的手艺都好,那么吃到好美味的机会也就大大增加了!

任何的问题要想让计算机解决,那么首要的就要存入到计算机,所以一定会用到数据结构!选用合适的数据结构来存储,会让“米”的质量更好!要解决问题,就需要特定的步骤,就一定会用到算法!好的算法会让事情事半功倍!

所以,合适的数据结构和好的算法对于能够顺利甚至是高效的解决问题,都十分的重要!

1.3 为什么是PHP

首先,PHP是非常流行的脚本语言!数以万计的网络程序使用它进行编写!小到个人博客大到各大平台级别产品!既然如此流行,那么就有必要从各个层面来提高我们的能力来更快的解决问题!尤其是PHP是一门后端服务器语言,PHPer要处理大量的数据和逻辑,数据结构与算法是基本能力之一!

第二,PHP7的发布,从语言层面优化了效率,健壮性也得到很好的加强!显然这门语言也想要发挥更大的力量!这也就意味着我们会更多的应用这门语言解决问题!所以我们十分有必要学习更好的使用这门语言!这就要求我们可以更好的掌握数据结构和算法的相关知识!

再者,PHP本身提供了SPL,也就是标准PHP库!SPL内置了大量的数据结构!这说明PHP作为一门服务器语言,其实非常的注重数据结构和算法!当然这属于高级应用!为了能够更好的应用PHP这些高级的技术,我们十分有必要掌握数据结构和算法的原理!我们会在弄懂原理的基础上学习PHP的SPL的应用,相信这些知识的学习会使你真正步入PHP高手的殿堂!

当然,还有很多重要的理由让我们需要掌握PHP相关的数据结构与算法知识!比如你第一门学习的语言就是PHP!比如你不是计算机专业出身,不会C或者JAVA语言却又想学数据结构与算法!比如虽然都是数据结构与算法,但是语言本身有自己的特点,我们需要了解和结合PHP语言本身的特点来实现PHP化的数据结构和算法!无论有什么理由,数据结构与算法都是我们必要掌握的知识!

所以,从PHP语言本身,还是从我们自身能力的提高而言,PHPer都应该好好的掌握PHP版的数据结构和算法!

1.4 认识ADT

在了解ADT前,先让我们对PHP内会的数据类型做个简单的回顾!

PHP有8中内置的数据类型:布尔,整型,浮点型,字符串,数组,对象,资源和null。其实PHP变量也有一些静态语言的特性!但是,由于PHP是弱类型语言,在使用变量时,我们不用考虑对变量进行数据类型的初始化!当我们需要时,我们可以直接定义和使用变量!

目前我们已经了解了一些数据结构的相关知识!那么,我们可以使用PHP内置的这些数据类型来表达这些数据结构吗?有些或许可以,但是大多数的并不能直接来表达!你可以思考一下,PHP内置的这些数据类型虽然可以进行不限制数据类型的存储,但是它们的基本功能仅仅是数据的存储,并没有数据之间的关系内容的具体表达!至少大多数不是!但是现实的问题是相对复杂的,一个数据里面可能有多个子项,而且数据和数据之间存在的对应的关系,并且这种数据类型有属于它们特定的操作方法!显然,内置的数据类型就已经不能满足要求了。这就用到了ADT,也就是抽象数据类型。

ADT:抽象数据类型(abstract data type)的简称, 是指一个数学模型和定义在该模型上的一组操作!

你会发现ADT不仅定义了数据的存储还定义了这种类型数据的一系列操作!其实这个不难理解,你想想我们现实中的排队购票, 所有人都依次排好, 对于当前的队伍是不是有办理完购票的人员离开和 新来的人排到队尾,即出队和入队这两个关键操作!那么当前的队伍就是一个典型的队列数据结构,而入队和出队操作就是属于这种特殊的数据结构的两个关键操作!当前的队列和这些关键操作综合起来才是一个完整的队列ADT即队列抽象模型!其实简单一点想就是:

对于特定的一种ADT,其包含了该种类型数据的数据结构和对应的算法集合!

我们还需要理解的是,抽象数据类型ADT是一种逻辑上的概念!是我们对实际问题分析进行抽象总结出来的一种“自定义的数据类型”和一组操作!是的每个人都可以自定义ADT来使用!但是数据结构和算法的知识体系中已经对我们经常遇到的问题进行了总结和分类,所以,经常使用的ADT类型有:

  • 集合
  • 链表
  • 队列
  • 优先队列

在接下来的章节中,我们将学习更多类型的ADT并使用PHP来实现对应的数据结构,让我们一起加油!

1.5 数据结构常见类型

要了解数据结构的类型,先让我们来了解几个概念。

数据(data):是对客观事物使用特定的符号表示!在计算机科学中凡是能输入到计算机并能够被计算机处理的所有符号组成的集合是数据!

例如我们要研究班级A内学生成绩的分布情况,那么班级A里面所有的学生信息组成的集合就是数据!

数据元素(data element):数据的基本单位。

例如班级A内的一个学生就可以看做一个数据元素。

数据项(data item):数据元素的基本特征,是数据中不可分割的最小单位!

例如班级A内一名学生的学号就是一个数据项,姓名是另外一个数据项!

数据对象(data object):数据的子集,数据内性质相同的数据元素的集合。

例如班级A内按照成绩排名,优秀成绩的学生的集合就是一个数据对象!成绩良好的学生组成的集合是另一个数据对象!

那让我们总结一下这些概念的关系:

数据由一个个数据元素组成,数据元素包含多个数据项!
而数据可以按照某种性质标准分割成多个数据对象!一个数据对象内是由一定数量的符合该数据对象性质的数据元素组成。

以上这些概念我们这整个数据结构和算法的学习过程中都会用到,所以请大家务必好好思考并掌握这些内容!

下面就让我们看看数据结构的种类。

首先按照数据元素的存储关系我们可以将数据结构分为两种:

  • 线性数据结构
  • 非线性数据结构

在线性数据结构中,数据元素是线性并且连续排列的!就像现实中排队购票这样!数组,链表,队列,栈是线性结构的典型代表!而非线性结构的数据元素并不一定连续的,数据结构中的树和图是非线性结构的典型代表!

下面就让我们一起来畅游数据结构的世界,让我先带大家来认识一下我们接下来要学习的各种数据结构,在接下来的章节我们会更详细的学习这些数据结构。

就像我说的,我们的世界存在多种数据结构,但有些并不通用或常用。其实我们的前辈们已经总结了一些最常用的数据结构,它们是:

  • 数组
  • 链表
  • 队列
  • 优先队列
  • 集合
  • 哈希表

数组

数组是PHP中的一种内置数据类型,但是大家考虑过为什么PHP的数组可以存储不同类型数据呢?明明PHP语言是基于C语言打造的,在C语言中数组是固定大小的并且只能存储一种类型的数据!但在PHP中数组并不定长而且可以存储多种类型数据!这是如何实现的呢?其实PHP中的数组底层是基于有序的哈希表来构建的!哈希表的概念我们后面会讲!我们这里简单的认为关联数组就是哈希表就可以了。这样就意味着PHP数组实际就是哈希表这种数据结构。所以数组在PHP中我们可以认为是PHP内置的数据结构!确切的说我们可以使用数组来模拟多种数据结构!这些内容我们将在数组一章进行更多讲解!

链表

链表也是一种线性数据结构,与数组不同的是数组是逻辑上连续并且物理内存中也连续的结构!这就意味着在内存数组对应这着一块儿连续的空间。而链表只要求逻辑上连续就可以了,这样就意味着逻辑上连续的数据在内存中并不一定是连续的!在实际应用中,链表是非常实用的数据结构!在接下来的章节中,我们会学习链表的相关内容!其实链表有很多种类,例如单链表,循环链表,双向链表等等,当然这些内容后面会详细讲解,是不是充满期待!

队列

队列也是一种线性数据结构!这种数据结构真的可以描述我们常见的排队购票的场景!元素总是只能在队列的一头出去,而在队列的一头进入队列!所以队列是先进先出的结构,很特别吧?接着看,下面的结构也很特别!

优先队列

优先队列也是一种队列,只不过有点特别!这个可以拿医院排队来说明,虽然都是排队,但是总是急诊优先!也就说数据元素是有权重的!但整体而言,仍旧是一个队列!我们将详细学习这种数据结构!

栈也是一种线性数据结构!这个可以对比队列学习!因为与队列的先进先出不同,对于栈结构,数据元素是后进先出的!很特别?那到底有什么用呢!在哪用呢?留个悬念,我们会好好学习相关内容!

集合

集合不再是线性数据结构!它是松散的数据,代表了弱关系的数据元素的汇集!但是集合也很特殊,集合中的元素是不会重复的!这个特性就非常有用了,至于如何用!详情后面讲!

哈希表

哈希表又叫做散列表!正如前面介绍的,PHP的数组底层实现就是哈希表!简单的理解哈希表就是类似关联数组一样的键值对!至于其原理到底是什么,有哪些操作,在相关章节我们会揭开它都面纱!

树是非线性数据结构!而且是十分重要且常用的数据结构!树有很多种类,而且每一种都有大用处!我很激动能为你介绍树!在树的这一章我会带你一起学习内容十分丰富的这种结构!

其实堆是一种特殊的树!而且其用途也很广泛,例如堆排序,解决图论问题啊等等!堆又分为“大根堆”和“小根堆”,分别有什么用呢?在堆章节我们会详细研究和学习!

图又叫图论!也是一种非线性结构,而且是这些数据结构中最难 一种!它的内容非常的丰富!其用途也非常广泛!前面我们已经了解过它的一些简单场景,例如人与人的关系,交通规划!在图这一章我会带你进入图的世界,深入剖析图论的用法!

1.6 认识算法

到目前我们已经讨论了很多类型的数据结构!但是我们也了解到数据结构主要意义是解决问题的数据的存储问题!要真正的解决问题,还离不开另一项重要的内容:算法!

前面我们已经了解了算法的定义,算法是对特定问题解决步骤的描述,现实生活中我们称之为方法,计算机科学中表现为指令的序列。但是如何去判定是不是算法呢?或者说符合什么特点的我们可以称之为算法呢?让我们一起来分析一下。

1.6.1 算法的特性

算法具有五个基本特性:输入、输出、有穷性、确定性和可行性。

输入输出

算法允许具有零个或多个输入,但是必须至少有一个或多个输出。 算法允许输入这个不难理解,但有些情况例外,比如我们写一个函数只想输出固定的“hello world”就可以不需要输入参数了!但是算法是一定需要有输出的,因为解决完问题一定要有结果!那么对于算法而言输出的形式可以是打印输出,也可以是返回一个或多个值等。

有穷性

有穷性是指算法在执行有限的步骤之后,可以自动结束而不会出现无限循环,并且每一个步骤的执行时间都是在可接受的范围内。直白一些说就是算法的实现代码不能是死循环的!并且目标是1分钟内实现结果算法却要执行1年!这样虽然有穷但是并不是合格的算法!

确定性

确定性是指算法的每一步骤都具有确定的含义,不会出现二义性。举个例子来说就是有确定的输入就应该有固定的输出!不能是这次输入A得到结果B,下一次输入A却得到结果C!这就违反了确定性原则!

可行性

可行性是指再现有的条件下算法的每一个步骤都应该是可以实现的而不是只是空想或者你设计了一个20年之后可以实现的算法,这个在当下都是没有意义的。

现在我们应该明白符合以上五个特点的程序我们就可以看做是算法。但是解决一个问题的方法有多种,这就意味着可以对某一个问题设计多个算法来解决!那么如果要我们来设计算法来解决问题,要掌握什么原则才能设计出比较优良的算法呢?

1.6.2 算法设计和实现的原则

要设计出优良的算法,前辈们已经总结出了一些原则供我们来参考!这样我们就可以站在巨人的肩膀上写我们自己的算法了!

基本的原则有五个: 正确性、健壮性、高效性、环保性和可读性!

正确性

正确性是设计算的最基本的原则!如果不能正确的解决问题,那设计算法的意义又是什么呢?这个容易理解!但是所谓的“正确”在这里确是多层面的! - 算法的实现上没有错误。即我们编写的代码没有语法错误。 - 算法对于合法的输入应该能得到满足要求的输出结果! - 算法对非法的输入应该得到合适的反馈结果。 - 算法程序是精心选择的,甚至刁难的测试数据都能得到满足要求的结果。 - 算法是针对该问题的而不是针对其它问题的!否则满足上面四项也是错误的!

前面的容易理解,最后一条反例是:要设计一个排序的算法你却设计了一个搜索的算法,或许语法正确,数据输入也能得到结果,但是并不能解决目标问题。这种常识上的没有错误在这里也是不正确的!

健壮性

健壮性是在证确性的基础之上对算法更高层次的要求!是说程序是稳定可靠的!不能说运行一段时间程序就要挂掉!或者因为一次非法输入程序就崩溃了! 健壮性就是要求程序稳定运行!

高效性

高效性是说算法的时间效率尽量的高!也就是我们常常说的“做事儿的效率”!在这里就是算法解决问题的效率!其实这个也是大家常常去评判一个算法优劣的很重要的标准!

环保性

提到环保性,很多人是不是感觉莫名其妙!难道算法也要环保吗?环保除了人人有责,算法也有责?其实这里的环保性是指算法的资源利用越少越好!即我们常说的占用内存越低越好!其实这个也好理解!我们电脑上的资源都是有限的!对于算法而言,肯定是占用的内存的少一些是更有优势的!

可读性

最后一个原则往往被很多人忽略掉,但也是最重要的原则! 算法的实现最终是要靠程序的,在这里我们是要用PHP编写程序来实现算法!那么程序是不是一次性写完,以后就再也不会修改维护了呢?显然不是!

程序读的次数要远远多于写的次数!

编写过程中要读,维护修改要读,升级要读,甚至要删掉先要找到,这个也要先读!这也是为什么我说这条原则是最重要的原则!程序实际上是写给人看写给计算机执行的!软件的维护成本要远远高于制作成本!你可以想想一下面对一堆可读性非常差的代码和面对可读性非常好的代码的感受!我相信这一点有一定工作经验的人一定可以感同身受!

所以,为了设计和实现更好的算法,我们应该好好的参考这些经过验证的原则!希望大家都能设计和实现优秀的算法!

其实上述的五个设计原则不光可以帮助我们设计出优秀的算法,还可以作为我们评判一个算法好坏的原则!尤其是其中的高效性原则和环保性原则!因为这两个原则是可以量化的!所以我们往往也利用这两个原则来评判一个算法的质量!下面一章就让我们来看一下我们是如何利用这两个原则来评判算法的!

1.7 小结

本章我们了解了数据结构和算法即它们的重要性,并详细介绍了数据结构的分类,引入了ADT的概念。 本章介绍了很多概念,我们将在未来的学习中不断用到它们,希望大家能好好的掌握本章的这些内容