js数据结构和算法学习(一)

本系列内容来源《学习Javascipt数据结构与算法》，源文件使用es5代码编写，在这里我使用ES6来编写相关实例

下面内容我是按书上顺序写的，不过并不是完全一致，加入了我自己的理解

环境安装与配置

// 项目目录如下
-dist
-src
    -main.js
index.html

• 目录下运行npm init -yes建立package.json文件

• 安装http-server

// 只是学习，没必要安装到全局
npm i --save-dev http-server
...
// 启动在当前目录下的服务器
./node_modules/http-server/bin/http-server

• 安装babel

npm i --save-dev babel-cli babel-preset-es2015

• 创建.babelrc文件，为babel转换设置相关规则

{
  "presets": ["es2015"],
  "plugins": []
}

数组相关方法

// 下面数组方法，都基于下面3个数组
let arr1 = [1, 2, 3];
let arr2 = [4, 5, 6];
let arr3 = [7, 8, 9];
let arr4 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let arr5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let arr6 = [1, 2, 3, 2, 1, 3];
let isEven = function (x) {
    return (x % 2 === 0);
}

let isEven2 = function (x) {
    console.log(x % 2 === 0);
}

下面方法[0]表示不改变原始数组，[1]表示改变原始数组

• concat:对数组进行连接，返回一个新数组 [0]

// 下面输出[1, 2, 3, 4, 5, 6, 7, 8, 9]
// arr1,arr2,arr3不变
arr1.concat(arr2, arr3); 

• join: 使用指定符号连接数组数据，返回一个字符串，默认为‘,’ [0]

arr1.join(); // '1,2,3'
arr1.join('-'); // '1-2-3';

• pop: 删除并返回数组的最后一个元素 [1]

arr1.pop(); // 3,此时arr1变为[1, 2]

• push: 向数组的末尾添加一个或更多元素，并返回新的长度。 [1]

arr1.push(4); // 3, arr1为[1, 2, 4]

• shift: 与pop功能相似，这个方法时删除并返回第一个元素 [1]

arr1.shift(); // 1, 此时arr1为[2, 4]

• unshift: 与push功能相似，向数组开头添加一个或更多元素，并返回新的长度 [1]

arr1.unshift(1); // 返回3，此时arr1为[1, 2, 4]

• reverse: 颠倒数组中元素的顺序。 [1]

arr1.reverse(); // [4, 2, 1]

• sort: 对数组进行排序，可以接受函数，设置排序的规则 [1]

arr4.reverse(); // 先故意倒序，[9, 8, 7...]
arr4.sort(); // 对数组进行排序, [1, 2, 3...]

• slice: 返回指定范围的数组元素(可以接受两个参数，开始位置start和结束位置end，包含开始位置的元素，不包含结束位置的元素，下标从0开始算) [0]

slice(start, end);

arr4.slice(0, 4); // [1, 2, 3, 4]

• splice: 向/从数组中添加/删除/替换项目，然后返回被删除的项目 [1]

splice(index,howmany,item);

// howmany设为0就不会删除元素，该方法变成向指定位置添加元素
// 此时arr4为[1, "a", 2, 3, 4, 5, 6, 7, 8, 9]
arr4.splice(1, 0, 'a'); // 没有元素删除，此时返回为[]
...
// howmany设为1就会删除元素，不过此时方法看起来是替换元素
// 此时arr4为[1, "b", 2, 3, 4, 5, 6, 7, 8, 9]
arr4.splice(1, 1, 'b'); // 返回["a"]，这是被删除的元素
...
// howmany设为2以上的数字，就能体现出删除元素的功能了
// 此时arr4为[1, "b", 3, 4, 5, 6, 7, 8, 9]
arr4.splice(1,2,'b'); // ["b", 2]

• map: 对数组的进行迭代，然后把每一次的执行结果组成一个新数组返回 [0]

// isEven参数x接收了arr5每个元素，并进行判断，并把判断结果返回成一个数组
// 返回新数组[false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]
arr5.map(isEven); 

• forEach: 与map方法类似，对数组进行迭代，区别在于不会返回新的数组 [0]

arr6.forEach(isEven); // 没有任何返回
arr6.forEach(isEven2); // 在控制台会输出每一个元素判断后的值

• filter: 对数组进行迭代，把符号条件的元素，组合成一个新数组 [0]

arr6.filter(isEven); // [2, 4, 6, 8, 10, 12, 14]

• some: 对数组进行迭代，只要某个数组元素符合条件，就会返回true [0]

arr6.some(isEven); // true,数组中存在偶数

• every: 对数组进行迭代，要求每个数组元素都要符合条件，才会返回true [0]

arr6.every(isEven); // false,数组中有奇数，不符合每个元素都是偶数的条件

• reduce: 对数组元素进行迭代，数组元素按顺序进行两两操作，并把结果继续传递当作下次计算的第一个元素，直至遍历到最后一个数组元素，并返回最后计算结果 [0]

reduce(累积变量, 当前变量, 当前位置, 原数组);
累积变量默认是数组第一个元素

arr2.reducce(function(a, b) {
    console.log(a, b);
    return a * b;
});
...
// 这时控制台输出为，20就是数组元素4，5的计算结果，最后返回的是20和6的计算结果
// 计算规则可以随意定位，并不局限于四则运算
4 5
20 6
< 120
...
arr2.reduce(function (a, b) {
  return a + '-' + b;
});
// 这是控制台输出'4-5-6'

• reduceRight: 规则和reduce一致，区别在于reduce是按数组顺序进行计算，reduceRight是按数组逆序进行计算 [0]

累积变量默认是数组最后一个元素

arr2.reduceRight(function (a, b) {
  return a + '-' + b;
});
// '6-5-4'

• indexOf: 数组迭代，查找数组中是否有指定元素，有的话返回出现的位置(数组下标，从0开始)，同时终止迭代，否则遍历完整个数组，如果整个数组都没有指定数组，该值返回-1 [0]

arr2.indexOf(6); // 2
arr2.indexOf(60); // -1
...
arr2.indexOf(5, 2); // -1，接受第二个参数表示从什么位置开始搜索
arr2.indexOf(5, 1); // 1

• lastIndexOf: 和indexOf方法类似，区别在于这个方法是查询元素最后出现的位置 [0]

arr6.indexOf(1); // 0
arr6.lastIndexOf(1); // 4

栈

栈是一种遵从后进先出(LIFO)原则的有序集合，新添加的或者待删除的元素都保存在栈的末尾，称为栈顶，另一端叫栈底

创建栈

// 原书是使用es5的写法，我这里换为es6
class Stack {
    constructor () {
        this.items = [];
    }
    push (element) {
        this.items.push(element);
    }
    pop () {
        return this.items.pop();
    }
    peek () {
        return this.items[this.items.length - 1];
    }
    isEmpty () {
        return this.items.length === 0;
    }
    size () {
        return this.items.length;
    }
    clear () {
        this.items = [];
    }
    print () {
        console.log(this.items.toString());
    }
}
let stack = new Stack();
console.log(stack.isEmpty());

在终端运行下面命令

babel ./src/main.js -o ./dist/main.js

如果想简单一些，可以把上面命令写到package.json的script中，通过npm run运行

"scripts": {
    "test": "echo \"Error: no test specified\" && exit 1",
    "build": " babel ./src/main.js -o ./dist/main.js"
},

编译完成后我们在index.html文件引入编译后的main.js，在之前启动的服务器刷新下，就能看到控制台输出true(也就是stack.isEmpty()的值)，在控制台我们可以尝试使用定义好的方法来验证相关功能，一个基本的栈就建立完成，总结下我们这个栈一共有如下几个功能：

• push: 向栈顶添加元素
• pop: 移除栈顶元素
• peek: 返回栈顶元素
• isEmpty: 判断栈中是否有元素
• clear: 清空栈中所有元素
• size: 返回栈中有多少元素

把十进制数字转为二进制

js本身有方法使用toString(2)就能得到一个二进制，不过这并不是底层算法，下面用算法，把一个十进制数字转为二进制

// 以10为例，下面的计算并不是严格意义上的计算公式，只是一种计算思路
10 / 2 = 5; // 余数为0
5 / 2 = 2;  // 余数为1
2 / 2 = 1;  // 余树为0
1 / 2 = 0;  // 余数为1，所以10的二进制为1010
// 以11为例
11 / 2 = 5; // 余数为1
5 / 2 = 2;  // 余数为1
2 / 2 = 1;  // 余数为0
1 / 2 = 0;  // 余数为1 

从上面的过程我们分析整个计算过程应该是先算出要转换的数字和2相除的整数为多少，如果这个整数值为0就终止整个计算过程，如果不是就继续与2相除，直至结果为0，期间产生的余数就是对应2进制的值

// 10进制转2进制算法代码
// 方法是使用上面栈定义的方法
let divideBy2 = function (decNumber) {
    let remStack = new Stack();
    let rem = 0;
    let binaryString = '';
    while (decNumber > 0) {
        rem = decNumber % 2 // 记录当前余树是多少
        remStack.push(rem);  // 存入栈中
        decNumber = parseInt(decNumber / 2); // 与2除取整
    }
    while (!remStack.isEmpty()) {
        binaryString += remStack.pop().toString();
    }
    return binaryString;
};

汉诺塔

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘(来源百度百科)。

汉诺塔的解法主要是对分治递归的理解，这个理解可以参考盗梦空间的多层梦境，从第一层梦境到第四层梦境，再从梦境中醒过来的过程。

书上和网上查到都提到使用栈解决汉诺塔，不过实现后发现其实使用栈也不过是记录数据的方式，并没有什么特别的地方(简单的东西说的那么高大上，琢磨了半天...)

递归解法

// 这里用了class的写法
// 使用时new hanoi(4);表示要移动圆盘数，别太大，会卡死
class hanoi {
    constructor (disc) {
        this.disc = disc; // 设定要移动多少圆盘
        this.src = 'A'; // 设定源支柱名词
        this.aux = 'B'; // 辅助支柱名词
        this.dst = 'C'; // 设定目标支柱名词
    }
    descMove ({disc = this.disc, src = this.src, aux = this.aux, dst = this.dst} = {}) {
        // 这个函数的意义是表示，某个圆盘，要从src(源支柱)移动到dst(目标支柱),aux是辅助支柱，
        if (disc) {
            // 至少有一个圆盘才会进行下面的逻辑
            // 下面函数进行的意义是指，如果至少是两个圆盘(因为是一个圆盘时，回调当前函数时disc为0，不会有任何输出)
            // 整个算法体现了分治递归的思路，我们是假设有三个支柱，A是源支柱，B是辅助支柱，C是目标支柱
            // 最终的目的是把A支柱上的所有圆盘移动到C支柱上，如果正向解这个问题，会很复杂，而且会涉及很多判断
            // 使用分治的思路，把问题简化，
            // 整体来看汉诺塔的算法是拆分成如下过程(最终结束的三步)
            // 先把(n-1)的圆盘，移动到辅助支柱
            // 把n圆盘移动到目标支柱
            // 再把(n-1)的圆盘，以辅助支柱为源支柱，源支柱为辅助支柱，进行再一次的递归，直至圆盘为1
            // 反过来看就是移动的过程
            this.descMove({disc : disc - 1, src: src, aux : dst, dst : aux});
            console.log(`移动${disc}号圆盘，从${src}移动到${dst}`);
            this.descMove({disc: disc - 1, src : aux, aux : src, dst: dst});
        }
    }
}

结合栈的解法

算法思路还是使用递归思路，区别在于使用栈来存储

// 这里使用了上面定义的栈
// 这里可以先验证pillarSrc和pillarDst
// 运行hanoi(3, pillarSrc, pillarAux, pillarDst);
// 再次查看两个栈的值，就能发现模拟的圆盘，从源支柱，移动到目标支柱上
let pillarSrc = new Stack(); // 源支柱
let pillarAux = new Stack(); // 辅助支柱
let pillarDst = new Stack(); // 目标支柱
let n = 3; // 初始时有多少圆盘
while (n--) {
    pillarSrc.push(n); // 在源支柱插入数据
}
let hanoi = (dist, src, aux, dst) => {
    console.log(dist);
    if (dist === 1) {
        // 当只有一个圆盘时，把圆盘从源支柱移动到目标支柱
        moveStack(src, dst);
    } else {
        hanoi(dist - 1, src, dst, aux);
        moveStack(src, dst);
        hanoi(dist - 1, aux, src, dst);
    }
}
let moveStack = (src, dst) => {
    if (!src.isEmpty()) {
        let moveElem = src.pop(); // 把源栈移出栈顶
        dst.push(moveElem); // 把从源栈演出的元素插入到目标支柱
    }
}

小礼物走一走，来简书关注我