JavaScript 数据结构与算法(一)前言

什么是数据结构?

数据结构的定义

  • 官方定义

  • 民间定义

    • “数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。” — 《数据结构、算法与应用》
    • “数据结构是 ADT(抽象数据类型 Abstract Data Type)的物理实现。” — 《数据结构与算法分析》
    • “数据结构(data structure)是计算机中存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来最优效率的算法。” —中文维基百科
  • 从自己角度认识

    在计算机中,存储和组织数据的方式。

数据结构在生活中应用

我们知道,计算机中数据量非常庞大,如何以高效的方式组织和存储呢?

例如:一个庞大的图书馆中存放了大量的书籍,我们不仅仅要把书放进入,还应该在合适的时候能够取出来。

图书摆放要使得两个相关操作方便实现:

  • 操作 1:新书怎么插入?
  • 操作 2:怎么找到某本指定的书?

图书各种摆放方式:

  • 方法 1:随便放

    • 操作 1:哪里有空位放哪里。
    • 操作 2:找某本书,累死。
  • 方法 2:按照书名的拼音字母顺序排放

    • 操作 1:新进一本《阿 Q 正传》, 按照字母顺序找到位置,插入。
    • 操作 2:二分查找法。
  • 方法 3:把书架划分成几块区域,按照类别存放,类别中按照字母顺序

    • 操作 1:先定类别,二分查找确定位置,移出空位。
    • 操作 2:先定类别,再二分查找。

结论:

  • 解决问题方法的效率,根据数据的组织方式有关。
  • 计算机中存储的数据量相对于图书馆的书籍来说数据量更大,数据更加多。
  • 以什么样的方式,来存储和组织我们的数据才能在使用数据时更加方便呢?
  • 这就是数据结构需要考虑的问题。

常见的数据结构

  • 数组(Array)
  • 栈(Stack)
  • 链表(Linked List)
  • 图(Graph)
  • 散列表(Hash)
  • 队列(Queue)
  • 树(Tree)
  • 堆(Heap)

注意:数据结构与算法与语言无关,常见的编程语言都有直接或间接的使用上述常见的数据结构。

什么是算法?

算法(Algorithm)的定义

  • 一个有限指令集,每条指令的描述不依赖于语言。
  • 接收一些输入(有些情况下不需要输入)。
  • 产生输出。
  • 一定在有限步骤之后终止。

算法通俗理解

  • Algorithm 这个单词本意就是解决问题的办法/步骤逻辑。
  • 数据结构的实现,离不开算法。

算法案例

假如上海和杭州之间有一条高架线,高架线长度是 1,000,000 米,有一天高架线中有其中一米出现了故障,请你想出一种算法,可以快速定位到处问题的地方。

  • 线性查找

    • 从上海的起点开始一米一米的排查,最终一定能找到出问题的线段。
    • 但是如果线段在另一头,我们需要排查 1,000,000 次,这是最坏的情况,平均需要 500,000 次。
  • 二分查找

    • 从中间位置开始排查,看一下问题出在上海到中间位置,还是中间到杭州的位置。
    • 查找对应的问题后,再从中间位置分开,重新锁定一般的路程。
    • 最坏的情况,需要多少次可以排查完呢? 最坏的情况是 20 次就可以找到出问题的地方。
    • 怎么计算出来的呢? log(1000000, 2),以 2 位底,1000000 的对数 ≈ 20。

结论:
你会发现,解决问题的办法有很多,但是好的算法对比于差的算法,效率天壤之别。