Data structures & Algorithm

TODO 基础&算法&数据结构

数据结构和算法虽然对于目前的工作貌似没有太大作用，但是自己对这一快不清除，就如一块石头压在心上，所以也必须要解决，虽然很难，但是慢慢攻克吧。

网上一搜算法，绝对是各种文章，视频，还有什么教程培训之类的，暂不谈质量如何，首先对于我这种，时间是有限的，所以只能选择一个，最合适的一个，有些虽然好但是难，因为我也不是要一定深入到什么程度。能写基本的算法，有数据结构有一定认识就好了。

https://github.com/thejameskyle/itsy-bitsy-data-structures 从这开始吧，算是入门启蒙吧。

问题

• 抽象数据类型 与 实际的物理结构：我的疑惑是怎么存储如　堆栈　队列这些抽象数据结构　其与　高级语言中讲的数据类型：　数组，对象。。等的区别。　是否可以直接定义一个堆栈？？ 不同语言的基础数据类型有哪些区别？？

资源

• https://github.com/qiwsir/algorithm
• Chrome 书签的内容
• MOOC 课程：　http://www.icourse163.org/course/ZJU-93001#/info
• https://noah_1992.gitbooks.io/-/content/datastructure.html 别人的笔记
• https://www.coursera.org/learn/shuju-jiegou-suanfa 《数据结构与算法》（张铭、王腾蛟、赵海燕 编著） 感觉很可以啊。
• JS 各类排序的实现
• 在Javascript中学习数据结构与算法
• 我接触过的前端数据结构与算法
• 算法面试题

基础

Algorithm为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95 WIKI 讲的很清楚
https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA 图灵机的WIKI

数据 数据类型 数据结构

• 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据的本质是差异，每一种差异是一个值。数据的意义是用来对比。包含：数值性数据 和 非数值性数据

• 数据结构
  是计算机科学与技术领域常用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

  • 数据结构，分为数据的逻辑结构和物理结构
    
    • 数据的逻辑结构：数据元素之间的逻辑关系 => 集合结构；线性结构；树形结构；图形结构
    • 数据的物理结构：数据元素在计算机存储器中是如何存储的 => 顺序存储（存放在连续的内存地址中）；链式存储（数据通过指针指向下一个存储地址，不一定存储在连续的地址空间）

• 数据类型
  数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。

  • 数据类型是一个值的集合和定义在这个值上的一组操作的总称。
  • 按照值的不同，高级程序设计语言中数据类型可分为两类：一类是非结构的原子类型，另一类是结构类型。

• 抽象数据类型
  抽象数据类型的含义可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算（过程或函数）。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。

  • 抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。
  • 抽象数据类型只是在数据的逻辑结构上讨论问题，与数据的存储结构无关。

以上：http://blog.lwxyfer.com/data-struture-type/

基本概念

特征：

• 输入
• 输出
• 明确性
• 有限性
• 有效性

设计模式：

完全遍历 -- 不完全遍历

• 分治法
• 动态规划
• 贪婪算法
• 线性规划
• 简并法

实现：

• 递归
• 迭代
• 顺序计算、并行计算、分布式计算
• 确定性算法、非确定性算法
• 精确求解、近似求解

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务

复杂度

• 时间复杂度
  算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做
  

算法执行时间的增长率与f(n) 的增长率正相关，称作渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

• 空间复杂度
  算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

数据结构

思考这些的时候，其实数据是对应在内存中的位置的。

访问accessing
查询searching
插入insert
删除delete

不同的数据结构对应不同的操作有不同的效率。即时间复杂度和空间复杂度是不同的，需要根据自己的应用情况，选择不同的数据结构。

• LIST
• 哈希表 HASH TABLES
• 栈 stack
• 队列 QUEUES
• 图 GRAPHS
• 链表 Linked LIST
• 树 tree 吼TM多

外在的即写出来的表现形式，与内在的数据结构形式与实现。 注意分开理解。

具体实现时，需要确认 API 的规范性： 比如 增加一项，是 add 还是 push;

常见函数

• 对数 https://zh.wikipedia.org/wiki/%E5%AF%B9%E6%95%B0

线性结构

顺序存储结构

链表

https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8

在结构化存储数据集时，链表时数组的一种重要的替代方式。

线性表 linear list

广义表

多重链表

堆栈 Stack

• 概念
• 顺序存储的实现
  这里谈到用数组实现栈，那么他们的关系？？
• 链式存储的实现

队列 Queue

树

树与树的表示

• 静态查找

  • 顺序查找： 建立哨兵[哨兵是通识的词吗？]
  • 二分查找 binary search

• 动态查找

从定义上是可以理解的，但是对应到具体的语言里面去就蒙蔽了。

二叉树

存储

遍历