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); // 把从源栈演出的元素插入到目标支柱
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,602评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,442评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,878评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,306评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,330评论 5赞 373
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,071评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,382评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,006评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,512评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,732评论 4赞 323
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,283评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2赞 354
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2赞 345

推荐阅读更多精彩内容

  • 数据结构和算法（上）
    1 序 2016年6月25日夜，帝都，天下着大雨，拖着行李箱和同学在校门口照了最后一张合照，搬离寝室打车去了提前租...
    RichardJieChen阅读 5,076评论 0赞 12
  • Python学习笔记[1]
    最近在慕课网学习廖雪峰老师的Python进阶课程，做笔记总结一下重点。 基本变量及其类型 变量 在Python中，...
    victorsungo阅读 1,656评论 0赞 5
  • 让你爱不释手的超有趣心理学
    1，心理学家的恶作剧之假精神病人实验 在心理学领域有一种现象被称为“贴标签效应”也就是暗示效应。所谓贴标签效应，具...
    晚晴521阅读 1,231评论 0赞 1