前言

Algorithms + Data Structures = Programs

四月春光晴方好，斜风微醉不须归。北京的春，这么美，那么艳。青草联排，春花烂漫。不过，有的时候，这春风，倒是有点大出了格。就在刚才，一则新闻把我吓出了一身冷汗。北苑路北口，一位路人，被吹翻的广告牌砸中，一命呜呼了......我们公司恰巧就在北苑路上，这让我感叹不已。生命，如此脆弱。世事，如此无偿。愿逝者安息，一路走好。

这长长的一条都是北苑路

另外一件值得我感叹的事情就是我的“技术日更计划”。
我的技术日更计划在第二日就忘记更新了。日更计划胎死腹中，早早的夭了折。回头想想，这么多年来，我做过了无数的计划，好像基本上就没有实施成功的。早年间计划好好学英语，失败！初中计划学习雕刻，失败！高中计划造机器人，失败！高考志愿填报清华大学，麻蛋的，差了100多分，失败中的失败......就这样，我在反反复复的失败中，逐渐的麻木了，就像一个摔倒的人，再也没有站起来过.......我想我是百（po）毒（guan）不（po）侵（shuai）了，哈哈，哈哈哈哈哈哈哈.....

前几天，在聊express和koa的时候，本打算再更新一篇关于tcp/ip、http协议的相关文章的，不过，我整理了一下，发现这个部分的知识非常的庞杂，根本不是一两篇文章能说的清楚的，于是打算好好准备一下，憋个大招，来几篇nb的硬货。

由于，更换了写作主题，所有就写点基础的，写点我比较熟悉的。于是，我计划写几篇“小基文”，主题呢，就定为数据结构预算法。

面向对象

讲js的数据结构，一定要从面向对象开始讲起，具体为啥要先说面向对象呢？请各位看官，随我而来

大千世界，无奇不有，但是编程语言却统一的要命，都会进化成一个面向对象的编程语言，那么为啥非要用面向对象呢？没有面向对象可以吗？回答当然是可以的，但是，面向对象给编程开发带来的好处多多，它好用，便于思考程序要解决的业务问题。

在js中，面向对象来的有些奇葩。继承，需要依赖原型prototype。封装，需要依赖函数作用域和闭包。如果单纯就讲这些，就太无聊了，还是本着讲一些不一样的，讲一些平常你看不到的东西，我打算先说说在js中堆栈以及对象拷贝的原理。（因为，js语言已经走出了浏览器，来到了服务器后端。因此引入类的概念，public、private的概念就比较迫切了。ES6、ES7引入了class的概念，并正式启用了class的关键字，在不久的将来，js的面向对象将会更加饱满）

堆（heap）、栈（stack）

堆是堆内存的简称，栈是栈内存的简称。说到堆栈，我们讲的就是内存的使用和分配了，没有寄存器的事，也没有硬盘的事。

各种语言在处理堆栈的原理上都大同小异。堆是动态分配内存，内存大小不一，也不会自动释放。栈是自动分配相对固定大小的内存空间，并由系统自动释放。

js的基本类型就5种，Undefined、Null、不是new出来的布尔、数字和字符串，它们都是直接按值存储在栈中的，每种类型的数据占用的内存空间的大小是确定的，并由系统自动分配和自动释放。这样带来的好处就是，内存可以及时得到回收，相对于堆来说，更加容易管理内存空间。

js中其他类型的数据被称为引用类型的数据（如对象、数组、函数等），它们是通过拷贝和new出来的，这样的数据存储于堆中。其实，说存储于堆中，也不太准确，因为，引用类型的数据的地址指针是存储于栈中的，当我们想要访问引用类型的值的时候，需要先从栈中获得对象的地址指针，然后，在通过地址指针找到堆中的所需要的数据。

说来也是形象，栈，线性结构，后进先出，便于管理。堆，一个混沌，杂乱无章，方便存储和开辟内存空间。

传值与传址

var aArray = [8,8, "ass"];
var bArray = aArray ;
var cString = aArray [2];
alert(bArray);//88ass
alert(cString);//ass
   
b[3] = 6;
c = 7;
alert(a[3]);//6
alert(a[2]);//ass

上方例子得知，当我改变bArray中的数据时，aArray中数据也发生了变化，当改变cString的数据值时，aArray却没有发生改变。为什么？这就是传值与传址的区别。

因为aArray是数组，属于引用类型，所以它赋予给bArray的时候传的是栈中的地址（相当于新建了一个不同名“指针”），而不是堆内存中的对象的值。cString的到的是一个基本类型的赋值，因此，cString仅仅是从aArray堆内存中获取了一个数值，并直接保存在栈中。aArray、bArray都指向同一块堆内存，bArray修改的堆内存的时候，也就会影响到aArray，cString是直接在栈中修改，并且不能影响到aArray堆内存中的数据。

堆栈示意图

浅拷贝和深拷贝

上边说到的赋值方式就是浅拷贝，那么什么叫作深拷贝呢？就是要将aArray的每个基本类型的数据都遍历一遍，依次的赋值给bArray的对应字段。避免产生因为地址引用带来的问题。

面向对象尾记

面向对象的语言本身在处理对象和非对象上就进行了划分，从数据结构的角度来讲，对象就是栈的指针和堆中的数值。那么堆和栈，我们应该如何深入理解呢？请看下一节，数据结构。

数据结构

上一节里，我们已经遇到了堆和栈这两张种数据结构了，接下来，我们来正式的学习如何通过js来实现数据结构。

经典的数据结构大概就那么几种，list、stack、queue、linkedList、dictionary、hash、set、tree、graph......

数据结构与算法的结构化展示

数组

此处的数据结构，我都通关数组来实现，其他的实现方式，大家可以集思广益。

数组是基础，然后为数组封装好一个List构造函数，增加长度、插入、删除、索引、遍历等工具接口，这样就构造了一个列表。

列表只适用于数据无存储顺序，并且也不需要快速查找的那种小数据，说白了就是给数组穿了件衣服。

栈（Stack），具有后进先出的特点（LIFO，last in first out），是一种高效的列表，只对栈顶的数据进行添加和删除，这就好像一大摞盘子，每次都是取最上边的，每次也都会把新盘子放到最上边去。对栈的操作主要是压栈push和出栈并删除pop，还有peek方法，找到栈顶数据，并返回这个数据。当然，栈还会有其他一些基本的操作如empty属性、clear方法、length等。栈除了适合用于记录数值和地址以外，还适合协助数制间的转换，如二进制转换为八进制等。还可以模拟递归和处理回文（回文是正着排列的文字和倒着排列的文字都是一样的一种形式）。

队列（Queue），具有先进先出（FIFO，first in first out）的特点，是只能在队首取出或者删除元素，在队尾插入元素的列表。队列的用处很大，除了前边说的堆内存以外（堆内存中会存在队列的数据结构，当然，堆中还会有其他结构如树等），还有消息队列，还可以执行提交操作系统的一系列进程的任务，打印任务池，模拟银行或超市排队的顾客等。对队列的操作主要是入队push（enQueue过程）和出队shift（deQueue过程），还有front（读取队首数据）和back（读取队尾数据）。另外，在计算机早期，打孔纸的年代，还有一种基数排序法是使用队列实现的，虽然不怎么高效，但是很好玩。这个算法需要九个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即为排好序的数字。

基数排序法第一次排序个位排序 基数排序法第二次排序十位排序

链表

如c++和java这样的语言，数组是静态的，效率很高，长度固定，但是，当数组满了之后，再向其中增加数据就非常困难了。js中的数据是个对象，数组是动态的，没有了长度的限制，但是，数组的索引下标需要在js语言内部转换为js对象的属性名，因此效率打了折扣。因此，在实际应用中，除了有随机访问的需求之外，其他情况都可以用链表替换数组。

单向链表的js实现

数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。链表的头部是一个特殊的节点叫头节点，尾部一般是一个null节点。如下图：

如何向链表中插入数据

我们可以看出，链表中删除和插入一个节点特别简单，插入节点只需要改变前一个节点的指向，让前一个节点指向插入的节点，让插入的节点指向后一个节点。删除也简单，将待删除节点的前驱节点指向待删除节点的后继节点，同时
将待节点元素指向null，节点就删除成功了。linkedList可以快速的插入和删除，因此，redis中的一种存储结构用的就是list，可以用来记录访问网页的人员信息。

用js来实现链表，需要有两个基本结构。Node 类用来表示节点，LinkedList 类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。

node类

function Node(element) {
    this.element = element;
    this.next = null;
}

LinkedList类

function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.display = display;
}

LList 类提供了插入删除节点、在列表中查找给定的值等功能。head 节点的next 属性被初始化null，当有新元素插入时，next 会指向新的元素

双向链表的js实现

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给Node对象增加一个属性，该属性存储指向前驱节点的链接，这样就构造了一个双向链表。

function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
}

双链表的节点删除

环链表的js实现

链表的尾节点指向头节点。

环链表

字典及散列

js对象本身就具有字典的功能，往简单了讲，可以用object来模拟字典的实现。

散列使用的数据结构叫做散列表。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却效率低下。散列表是将数据映射到散列上，但是，有的时候会产生数据碰撞，这个时候就需要用开链法、线性探测法进行碰撞的解决。

集合

集合（set）是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重要特性是：一是集合中的成员是无序的，二是集合中不允许相同成员存在。

集合的数学定义：
1.不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。
2.如果两个集合的成员完全相同，则称两个集合相等。
3.如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的子集。

对集合的操作

并集：将两个集合中的成员进行合并，得到一个新集合。
交集：两个集合中共同存在的成员组成一个新的集合。
补集：属于一个集合而不属于另一个集合的成员组成的集合。

树

树是非线性，分层存储的数据结构。可用来存储文件系统或者有序列表。树都有一个根节点（root node），如果一个节点下边有其他节点，则该节点称为它们的父节点，这些节点为子节点

二叉树上查找、添加、删除数据是非常快的，查找比链表要快的多，增加和删除比数组要快的多。这是为什么呢？

树的示意图

二叉树

左节点，右节点，左孩子，右孩子

二叉查找树

较小的值保存在左孩子里，较大的值保存在右孩子里。这个特性使得查找的效率非常高。

遍历二叉查找树

中序遍历按照节点上的键值，以升序访问BST 上的所有节点。
先序遍历先访问根节点，然后以同样方式访问左子树和右子树。
后序遍历先访问叶子节点，从左子树到右子树，再到根节点。

总结与展望

简单总结一下本文提到的数据结构和算法：

数据结构有：

1.数组
2.列表
3.栈
4.队列
5.链表，对于列表进行了升级，每个链表里的元素都是单独的对象。该对象和它两边的元素相连。当需要插入和删除多个元素时，使用链表非常高效。
6.字典

7.散列表和散列算法
8.集合，数据集不允许有重复元素出现时可以使用集合。
9.树，特别是二叉查找树是一种存储有序元素的极佳选择。
10.图

算法有：

1.排序算法，
2.查找算法，线性查找，二分查找
3.动态规划、贪心算法

后记：递归

function factorial(number) {
    if (number == 1) {
        return number;
    }
    else {
        return number * factorial(number - 1);
    }
}
print(factorial(5));

//执行效果
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

对于大多数情况，JavaScript 都有能力处理递归层次较深的递归调用，但是保不齐有的算法需要的递归深度超出了JavaScript 的处理能力，这时我们就需要寻求该算法的一种迭代式解决方案了。任何可以被递归定义的函数，都可以被改写为迭代式的程序，要将这点牢记于心。