发表于 | 分类于 |

chapter-7 字典

  • 键值对形式存储数据的数据结构
  • JavaScript的Object类就是以字典的形式设计的
  • 基础是Array类，可以对字典的键排序，JavaScript中是不能对对象的属性进行排序的。
  • JavaScript中一切皆对象，数组也是对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 字典实现
 */
function Dictionary () {
    this.datastore = new Array();
}
Dictionary.prototype = {
    constructor: Dictionary,
    // 添加
    add: function (key, value) {
        this.datastore[key] = value;
    },
    // 查找
    find: function (key) {
        return this.datastore[key];
    },
    // 删除
    remove: function (key) {
        delete this.datastore[key];
    },
    // 显示字典中所有的键值对
    showAll: function () {
        // 对键名进行重排序
        var arr = Object.keys(this.datastore).sort();
        for (var i = 0; i < arr.length; i++) {
            var key = arr[i];
            console.log(key + ' -> ' + this.datastore[key])
        }
    },
    // 字典元素个数
    count: function () {
        // 当数组的键的类型为字符串的时候，length属性就不管用了
        return Object.keys(this.datastore).length;
    },
    // 清除
    clear: function () {
        for (var key in this.datastore) {
            delete this.datastore[key];
        }  
    }
}
// 主程序
var pbook = new Dictionary();
// pbook.add('Mike', '123');
// pbook.add('David', '345');
// pbook.add('Cynthia', '456');
// console.log(pbook.find('David'));
// pbook.remove('David');
// pbook.showAll();
// console.log(pbook.count());
// pbook.clear();
// console.log(pbook.count());
// debugger
pbook.add('Raymond', '123');
pbook.add('David', '345');
pbook.add('Cynthia', '456');
pbook.add('Mike', '723');
pbook.add('Jennifer', '987');
pbook.add('Danny', '012');
pbook.add('Jonathan', '666');
pbook.showAll();

发表于 | 分类于 |

chapter-6 链表

数组的缺点

  • 很多语言里，数组的长度固定。填满后，加入新元素很困难。
  • 添加、删除元素也很麻烦，因为需要将数组中其他元素向前或向后平移，以反映刚刚进行了添加或删除操作。
  • JavaScript数组不存在上述问题，split方法不需要再访问数组中其他元素了，主要问题是：它们被实现成了对象，与其他语言相比，效率很低。
  • 如果数组使用中很慢，可以考虑用链表代替它，除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况。需要随机访问，数组是更好的选择。

定义链表

  • 一组节点组成的集合。
  • 每个节点使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。
  • 数组靠位置进行引用，链表靠相互之间的关系进行引用。
  • 遍历链表是跟着链接，从首元素走到尾元素（不包含头节点，作为链表的接入点），尾元素指向一个null节点。
  • 头节点是一个特殊固定节点。
  • 插入一个节点的效率很高，修改它前面的节点（前驱），使其指向新加入的节点，新加入的节点则指向原来前驱指向的节点。
  • 删除一个节点，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向null

设计一个基于对象的链表

  • 包含两个类：Node类用来表示节点，LinkedList类提供插入、删除、显示列表元素、及一些辅助方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找给定的节点前面的节点
    findPrevious (item) {
        var currNode = this.head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        // 找到待删除节点前面的节点
        var prevNode = this.findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        while (currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
}
// 主程序
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
1.jpeg

双向链表

  • 从链表的头节点遍历到尾节点很简单，但是反过来，从后向前遍历则没那么简单。给Node增加一个属性，存储指向前驱节点的链接。
  • 插入时，需要更多的工作，指出节点正确的前驱和后继。
  • 删除时，效率提高了，不需要再查找待删除节点的前驱节点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * 双向链表实现
 */
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
    // 保存前驱节点指向
    this.previous = null;
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找最后的节点
    findLast () {
        var currNode = this.head;
        while (currNode.next !== null) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // 新节点的前驱属性
        newNode.previous = current;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        var currNode = this.find(item);
        if (currNode.next !== null) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        while (currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    },
    // 反序显示双向链表中的元素
    dispReverse: function () {
        var currNode = this.head;
        currNode = this.findLast();
        while (currNode.previous !== null) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }
}
// 主程序
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
console.log('反转展示数据：============');
cities.dispReverse();

计算了一下时间：

  • 插入10000个Node的时间
    • 普通链表和双向链表差不多，普通链表240ms，双向链表250ms
  • 依次删除这全部10000个节点
    • 普通链表在150ms左右
    • 双向链表时间则较长，需要230ms左右
  • 随机删除一个元素（Math.random()）
    • 普通链表平均：0.283ms
    • 双向链表平均：0.196ms

所以书上写的双向链表更高效应该是指随机删除任意一个元素的平均时间

循环链表

  • 节点类型和单向链表类似，区别是，创建循环链表时，让其头节点的next属性指向它本身。
  • 希望可以从后向前遍历链表，但是又不想付出额外代价来创建一个双向链表，就需要使用循环链表。
  • 从循环链表的尾节点向后移动，就等于从后向前遍历链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * 循环链表实现
 */
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
    this.head.next = this.head;
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找给定的节点前面的节点
    findPrevious (item) {
        var currNode = this.head;
        while (currNode.next !== null && currNode.next.element !== 'head' && currNode.next.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        // 找到待删除节点前面的节点
        var prevNode = this.findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        // 检查头节点
        while (currNode.next !== null && currNode.next.element !== 'head') {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    },
    // 反序显示循环链表中的元素
    dispReverse: function () {
        var currNode = this.head;
        var prevNode = this.findPrevious(currNode.element);
        while (prevNode.element !== currNode.element && prevNode.element !== 'head') {
            console.log(prevNode.element);
            currNode = prevNode;
            prevNode = this.findPrevious(currNode.element);
        }
    }
}
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
// debugger
console.log('反转展示数据：============');
console.time();
cities.dispReverse();
console.timeEnd();// 1.213ms

一般正常情况所说的链表都是双向链表，比较快

发表于 | 分类于 |

chapter-5 队列

特性

  • 一种列表
  • 只能在队尾插入元素，队首删除元素
  • 存储按顺序排列的数据，先进先出（FIFO）
  • 用于提交操作系统执行的一系列进程

主要操作

  • 插入（入队）- 队尾插入新元素
  • 删除（出队）- 删除队头元素
  • 读取队头元素 - peek
  • 存储多少元素 - length
  • 清空所有元素 - clear

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function Queue () {
    this.dataStore = [];
}
Queue.prototype = {
    constructor: Queue,
    // 队列尾部添加一个元素
    enqueue: function (element) {
        this.dataStore.push(element);
    },
    // 删除队首元素
    dequeue: function () {
        return this.dataStore.shift();
    },
    // 读取队首元素
    front: function () {
        return this.dataStore[0];
    },
    // 读取队尾元素
    back: function () {
        return this.dataStore[this.dataStore.length - 1];
    },
    // 显示队列内所有元素
    toString: function () {
        return this.dataStore;
    },
    // 判断是否为空
    empty: function () {
        return this.dataStore.length === 0;
    }
}

测试结果：

使用

方块舞的舞伴分配问题

基数排序

  • 9个队列，每个对应1-9每个数字，所有队列保存在一个数组里，使用取余和除法操作决定个位和十位。先根据个位数值对其排序，在根据十位数字排序呢，结果即为排序好的数字
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    /**
     * 分配函数
     * @param {array[num]} nums 排序数字数组
     * @param {array} queues 队列数组，每一项代表分配的基数数字
     * @param {int} n 进制 
     * @param {int} digit 当前位数，1：个位、10：十
     */
    function distribute (nums, queues, n, digit) {
        for (var i = 0; i < n; i++) {
            if (digit === 1) {
                queues[nums[i] % 10].enqueue(nums[i]);
            } else {
                queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
            }
        }   
    }
    /**
     * 出队收集
     * @param {array} queues 队列数组
     * @param {array} nums 排序数组
     */
    function collect(queues, nums) {
        // debugger
        var i = 0;
        for (var digit = 0; digit < 10; digit++) {
            while (!queues[digit].empty()) {
                nums[i++] = queues[digit].dequeue();
            }
        }
    }
    // 执行程序
    var queues = [];
    for (var i = 0; i < 10; i++) {
        queues[i] = new Queue();
    }
    var nums = [];
    for (var i = 0; i < 10; i++) {
        nums[i] = Math.floor(Math.random() * 100);
    }
    console.log('原始数据：' + nums);
    // 个位分布排序
    distribute(nums, queues, 10, 1);
    collect(queues, nums);
    console.log('个位排序后数据：' + nums);
    // 十位分布排序
    distribute(nums, queues, 10, 10);
    collect(queues, nums);
    console.log('十位排序后数据：' + nums);
test 结果

优先队列

  • 一般情况下，队列中删除的元素遵循先入先出的原则。
  • 可以实现一个按优先权重限制的队列，高优先级先出，同优先级按先入先出处理。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    /**
     * 存储队列元素
     * @param {*} name 
     * @param {int} code 表示优先级
     */
    function Patient (name, code) {
        this.name = name;
        this.code = code;
    }
    // 重新定义dequeue函数
    // 顺序查找方法寻找优先级最高的元素（code越小，优先级越高）
    function dequeue () {
        var entry = 0;
        for (var i = 0; i < this.dataStore.length;i++) {
            if (this.dataStore[i].code < this.dataStore[entry].code) {
                entry = i;
            }
        }
        return this.dataStore.splice(entry, 1);
    }
    Queue.prototype.dequeue = dequeue;
    // 主程序
    var ed = new Queue();
    // 数据
    var data = [
        ['Smith', 5],
        ['Jones', 4],
        ['Fehrenbach', 6],
        ['Brown', 1],
        ['Ingram', 1]
    ];
    // 入队
    for (var dd = 0; dd < data.length; dd++) {
        var p = new Patient(data[dd][0], data[dd][1]);
        ed.enqueue(p);
    }
    console.log('初始数据：' + JSON.stringify(ed.dataStore));
    // 出队
    var index = 0;
    while (!ed.empty()) {
        var seen = ed.dequeue();
        // debugger
        data[index++] = seen[0];
    }
    console.log('排序后数据：' + JSON.stringify(data));

发表于 | 分类于 |

chapter-4 栈

特点

  • 高效的数据结构
  • 数据只能在栈顶添加或删除
  • 特殊的列表，栈内元素只能通过列表的一端访问，这一段称为栈顶。
  • 后入先出（LIFO）的数据结构
  • 任何不在栈顶的元素都无法访问，为了得到栈底的元素，必须先拿掉上面的元素
  • 入栈（push），出栈（pop）、预览栈顶元素（peek）

栈的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function Stack () {
    // 保存栈内元素
    this.dataStore = [];
    // 记录栈顶位置
    this.top = 0;
}
Stack.prototype = {
    constructor: Stack,
    // 向栈中压入元素
    push: function (element) {
        this.dataStore[this.top++] = element;
    },
    // 推出最后一个元素
    pop: function () {
        // 为什么不删除这个元素呢
        return this.dataStore[--this.top];
    },
    // 返回第top - 1个元素
    peek: function () {
        return this.dataStore[this.top - 1];
    },
    // 返回栈内元素个数
    length: function () {
        return this.top;
    },
    // 清空一个栈
    clear: function () {
        // 为什么不把dataStore也清空呢
        this.top = 0;
    }
}

测试结果

2.jpeg

实际问题

将数字n转换为以b为基数的数字，实现转换

  • 最高位为n%b，压入栈
  • 使用n/b代替n
  • 重复前两步，知道n = 0，没有余数
  • 弹出栈内元素，排列

只针对基数为2-9的情况（why？）

1.jpeg

操作符的参考资料：https://developer.mozilla.org/en-US/docs/Web/JavaS
cript/Reference/Operators/Assignment_Operators

数制间转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 数制间的相互转换
function mulBase (num, base) {
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    var converted = '';
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}
// 转换为二进制和八进制
mulBase(32, 2);// 100000
mulBase(125, 8);// 175

回文

  • 一个单词、短语或数字，从前往后写和从后往前写都是一样的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    function isPalindrome (word) {
        var s = new Stack();
        for (var i = 0; i < word.length;i++){
            s.push(word[i]);
        }
        var rword = '';
        while (s.length() > 0) {
            rword += s.pop();
        }
        if (word === rword) {
            return true;
        } else {
            return false;
        }
        console.log(s.dataStore)
    }
    isPalindrome('hello');// false
    isPalindrome('racecar');// true

递归演示

  • 模拟递归过程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // 使用栈模拟递归过程
    function factorial (n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    function fact (n) {
        var s = new Stack();
        while (n > 1) {
            s.push(n--);
        }
        var product = 1;
        while (s.length() > 0) {
            product *= s.pop();
        }
        return product;
    }
    factorial(5);// 120
    fact(5);// 120

发表于 | 分类于 |
  • 《数据结构与算法JavaScript描述》读书笔记之二
  • 列表
  • 未完

chapter-3 列表

  • 列表是一组有序的数据，每个列表中的数据项称为元素。
  • 在JavaScript中，列表中元素可以是任意数据类型。个数不限，但是使用中受到内存的限制

适合列表的数据结构

  • 数据存储的顺序不重要
  • 不必在一个很长的序列中查找元素
  • 列表中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    ### 特性
    - 空列表（不含元素）
    - 列表的length：包含的元素个数
    - 列表末尾append一个元素，也可以在给定的元素后或起始位置insert一个元素
    - remove删除元素
    - clear清空列表元素
    - toString显示列表中所有元素
    - getElement显示当前元素
    - 描述元素位置的属性：front，end前后
    - next()从当前元素移动到下一个元素
    - prev()从当前元素移动到当前元素的前一个元素
    - moveTo(n)直接移动到指定位置，移动到第N个位置
    - currPos列表当前位置
    ### 抽象数据类型定义
    #### 属性
    - listSize 元素个数
    - pos 当前位置
    #### 方法
    - length 返回元素个数
    - clear 清空列表中的所有元素
    - toString 返回列表字符串形式
    - getElement 返回当前位置元素
    - insert 在现有元素后插入新元素
    - append 列表末尾添加新元素
    - remove 删除某元素
    - front 当前位置移动到第一个元素
    - end 移动到最后一个元素
    - prev 后移一位
    - next 前移一位
    - currPos 返回列表当前位置
    - moveTo 当前位置移动到指定位置
    ### 实现
    ```javascript
    function List () {
        this.listSize = 0;
        this.pos = 0;
        // 保存列表元素
        this.dataStore = [];
    }
    // 实现一个列表
    List.prototype = {
        constructor: List,
        // 清空
        clear: function () {
            delete this.dataStore;
            //创建空数组， 设置新的空列表
            this.dataStore.length = 0;
            this.listSize = this.pos = 0;
        },
        // 辅助方法
        find: function (element) {
            // 是否可以用indexOf代替？？
            for (var i = 0; i < this.dataStore.length;i++){
                if (this.dataStore[i] === element) {
                    return i;
                }
            }
            // 错误校验
            return -1;
        },
        // 显示列表元素
        toString: function () {
            // 目的是显示当前状态
            return this.dataStore;
        },
        // 插入
        insert: function (element, after) {
            var insertPos = this.find(after);
            if (insertPos > -1) {
                this.dataStore.splice(insertPos + 1, 0, element);
                this.listSize++;
                return true;
            }
            return false;
        },
        // 给列表添加元素
        append: function (element) {
            // 新元素就位后，变量listSize加1
            this.dataStore[this.listSize++] = element;
        },
        // 从列表中删除元素
        /*  1. 先找到该元素（find）
            2. 然后删除他，(splice)
            3. 调整底层数组对象以填补删除该元素的空白*/
        remove: function (element) {
            var foundAt = this.find(element);
            if (foundAt > -1) {
                this.dataStore.splice(foundAt, 1);
                this.listSize--;
                return true;
            }
            return false;
        },
        // 移动到第一个元素
        front: function () {
            this.pos = 0;
        },
        // 移动到最后一个元素上
        end: function () {
            this.pos = this.listSize - 1;
        },
        // 向前一个
        prev: function () {
            if (this.pos > 0) {
                this.pos--;
            }
        },
        // 向后移动一个元素
        next: function () {
            if (this.pos < this.listSize - 1) {
                this.pos ++;
            }
        },
        // 元素个数
        length: function () {
            return this.listSize;
        },
        // 返回当前指向
        currPos: function () {
            return this.pos;
        },
        // 移动到某个指向
        moveTo: function (position) {
            this.pos = position;
        },
        // 返回当前指向的元素
        getElement: function () {
            return this.dataStore[this.pos];
        },
        // 判断给定值是否在列表中
        contains: function (element) {
            // indexOf??
            for (var i = 0; i < this.dataStore.length;i++) {
                if (this.dataStore[i] === element) {
                    return true;
                }
                return false;
            }
        },
        // this.pos 是否可以再次加1
        hasNext () {
            return this.pos < this.listSize - 1;
        },
        // this.pos 是否可以再次加1
        hasPrev () {
            return this.pos > 0;
        }
    };

测试结果：

1.jpeg

使用迭代器访问列表

  • front，end，prev，next，currPos实现了cList类的一个迭代器
  • 和数组索引的优点：
    • 访问时不用关心底层数据结构（貌似也是数组？？）
    • 添加元素时，索引值不对了，只要更新列表，不更新迭代器
    • 可以用不同数据类型存储方式实现，访问元素的api是统一的
      -（ ppppps：实在是不理解）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 迭代器访问
// 前向后遍历列表
for (names.front(); names.currPos() < names.length() - 1; names.next()) {
    console.log(names.getElement());
}
// 上面的叫迭代器遍历，下面的叫什么？？
names.front();
while (names.hasNext()) {
    console.log(names.getElement());
    names.next();
}
// 疑问：当列表的listSize和pos的位置不符的时候怎么处理，好奇怪？？
// 后向前遍历
for (names.end(); names.currPos() > 0; names.prev()) {
    console.log(names.getElement());
}
// 
names.end();
while (names.hasPrev()) {
    console.log(names.getElement());
    names.prev();
}

发表于 | 分类于 |
  • 《数据结构与算法JavaScript描述》读书笔记之一
  • 前两章为数组的方法复习

chapter-1 JavaScript编程环境和模型

语句

  • JavaScript中的switch语句和其他编程语言的一个主要区别是：在JavaScript中，用来判断的表达式可以是任意类型，不仅限于整型；而C++和Java等一些语言就要求该表达式必须为整型

    循环

  • while和for的用法：
    • 如果希望条件为真时执行一组语句，就选择while循环
    • 如果希望按执行次数执行一组语句，就选择for循环

      函数

  • 提供两种定义函数的方式：
    • 一种有返回值，目的是得到返回值
    • 一种没有返回值，也叫子程、void函数，目的是执行定义操作
  • JavaScript中，函数的参数传递方式都是按值传递，没有按引用传递的参数。但是JavaScript中有保存引用的对象，比如数组（可以按引用传递）。

    变量作用域

  • JavaScript拥有的是函数作用域，含义是JavaScript中没有块级作用域（可以在编写for循环的时候假设有），ES6的let可以实现

    递归

  • 任何可以被递归定义的函数，都可以被改写外迭代式的程序

chapter-2 数组

定义

  • 一个存储元素的线性集合（collection），元素可以通过索引来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。
  • JavaScript的数组是一种特殊的对象（效率不如其他语言高），表示偏移量的索引是该对象的属性，索引可能是整数（内部转换为字符串类型，因为JavaScript对象中的属性名必须是字符串）

    数组操作

    创建

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var numbers = [];// 创建
    numbers.length; // 长度
    var numbers = new Array(1,2,3,4,5);
    numbers.length; // 5
    var numbers = new Array(10); // 创建了一个长度为10的数组
    var numbers = 3;
    Array.isArray(numbers);// false 判断一个对象是否是数组
    // 字符串对象的split()方法也可以生成数组
    var sentence = 'the quick brown fox jumped over the lazy dog';
    words = sentence.split(' ');
1.jpeg

整体操作

浅复制：新数组依然指向原来的数组
深复制：原数组中的每一个元素都复制一份到新数组中

存取函数

一组用来访问数组元素的函数

  • indexOf 查找第一个匹配
  • lastIndexOf 查找最后一个匹配
  • join 返回字符串
  • toString 转换字符串
  • concat 合并多个数组创建新数组
  • splice 起始索引、截取长度、添加的元素
  • push，unshift 添加元素
  • pop， shift 删除元素
  • splice 添加元素
  • reverse 翻转
  • sort 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.indexOf('CCC');// -1
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.lastIndexOf('Bryan');// 4
// 添加
var nums = [1,2,3,7,8,9];
var newElement = [4,5,6];
nums.splice(3, 0, 4, 5, 6);
// 添加数组
var nums = [1,2,3,7,8,9];
var newElement = [4,5,6];
nums.splice(3, 0, newElement);
// 删除
var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
5.jpeg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var nums = [1,2,3,4,5];
nums.reverse();
// 按照字典顺序排序，假定元素都是字符串类型，即使是数字类型的元素，也被认为是字符串类型
var names = ['David', 'Mike', 'Cynthia', 'Claytou', 'Bryan', 'Raymond'];
names.sort();
var nums = [3,1,2,100,4,200];
nums.sort();
// 传入比较大小的函数，根据大小决定数组顺序
// 小 -> 大
var nums = [3,1,2,100,4,200];
nums.sort(function(num1, num2){
	return num1 - num2;
});
// 大 -> 小
var nums = [3,1,2,100,4,200];
nums.sort(function(num1, num2){
	return num2 - num1;
});
sort 说明
  • 若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
  • 若 a 等于 b，则返回 0。
  • 若 a 大于 b，则返回一个大于 0 的值。
  • 参考w3school：http://www.w3school.com.cn/jsref/jsref_sort.asp
2.jpeg

迭代器方法

不生成新数组的迭代器方法

执行操作或返回一个值

  • forEach
  • every 接受一个返回值，数组的每个元素使用该函数，如果所有的元素，该函数均返回true，则该方法返回true
  • some 接受一个返回值为布尔类型的函数，只要有一个元素使得该函数返回true，该方法返回true
  • reduce 累加值，不断对累加值和数组中后续元素调用该函数，例如数组求和
  • reduceRight
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // some every
    var nums = [2,4,6,8,9];
    function isEven(num) {
    	return num % 2 === 0;
    }
    nums.every(isEven);// false
    nums.some(isEven);// true
    // reduce reduceRight
    var nums = ['1','2','3','4','5','6','7','8','9'];
    function add(total, current) {
    	return total + current;
    }
    nums.reduce(add);
    nums.reduceRight(add);
3.jpeg
生成新数组的迭代器方法
  • map 原有函数应用某个函数，返回新数组
  • filter 传入一个返回值为boolean的函数，返回新数组（true）
1
2
3
4
5
6
7
8
9
10
11
12
13
// map
function first(word){
	return word[0];
}
var words = ['for', 'your', 'information'];
var newwords = words.map(first);
// filter
function isOdd (num) {
	return num % 2 !== 0;
}
var nums = [1,2,3,4,5,6,7,8,9];
nums.filter(isOdd);
4.jpeg

二维多维数组

类似一种由行和列构成的数据表格

6.jpeg 7.jpeg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 生成带默认值的二维数组
Array.matrix = function (numrows, numcols, initial) {
    var arr = [];
    for (var i = 0; i < numrows;i++) {
        var columns = [];
        for (var j = 0; j < numcols;j++) {
            columns[j] = initial;
        }
        arr[i] = columns;
    }
    return arr;
}
var nums = Array.matrix(5,5,0);
nums[1][2] = 3;
// 处理二维数组元素，按列访问，和按行访问
// 按行访问
var grades = [[89,77,78],[76,82,81],[91,94,89]];
var total = 0;
var average = 0;
for (var row = 0; row < grades.length;row++) {
    for (var col = 0; col < grades[row].length;col++ ){
        total += grades[row][col];
    }
    average = total / grades[row].length;
    console.log(total);
    console.log(average);
    total = 0;
    average = 0;
}
// 按列访问
for (var col = 0; col < grades.length; col++) {
    for (var row = 0; row < grades[col].length;row++){
        total += grades[row][col];
    }
    average = total / grades[col].length;
    console.log(average.toFixed(2));
    total = 0;
}

发表于 | 分类于 |
  • 《算法的乐趣》- 王晓华
  • 读书笔记，原文用C语言实现算法
  • 现在改用JavaScript实现算法

阿拉伯数字转换中文表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 单个数字转换：数组下标定义中文数字表
var chnNumChar = ['零', '一', '二', '三', '四', '五', '六', '七', '八', '九'];
// 节与权位识别。节：以万为单位截断。一维表
// 32位正数能表达的最大数，节权是万亿已经够了。最低的节没有节权，使用空字符串做占位符（算法设计的一致性处理技巧）
var chnUnitSection = ['', '万', '亿', '万亿'];
// 每个节内数字的权位
// 通过移位可以确定每个数字对应的权位；以移位次数做下标，查节权表即可
var chnUnitChar = ['', '十', '百', '千'];
// 算法设计：先对阿拉伯数字分节，确定节权位名称
// var chnStr = 1000;
function NumberToChinese(num) {
    // 输出字符串
    var chnStr = '';
    // 记录节的位置：0代表“”，1代表万，2代表亿
    var unitPos = 0;
    // 中转状态
    var strIns = '';
    // 是否需要补0
    var needZero = false;
    // 移位循环 每节取余10000
    while(num > 0) {
        var section = num % 10000;
        if (needZero) {
            chnStr = chnNumChar[0] + chnStr;
        }
        // 每小结转换中文
        strIns = SectionToChinese(section);
        // 是否需要节权位
        strIns += (section != 0) ? chnUnitSection[unitPos] : chnUnitSection[0];
        chnStr = strIns + chnStr;
        // 千位是0，需要下一个section补0
        needZero = (section < 1000)  && (section > 0);
        num = parseInt(num / 10000);
        unitPos++;
    }
    return chnStr;
}
// 将一个节的数字转换成中文数字
function SectionToChinese (section) {
    var chnStr = '';
    var strIns = '';
    var unitPos = 0;
    // 确保连续多个，只补一个中文0
    var zero = true;
    while (section > 0) {
        var v = section % 10;
        if (v === 0) {
            if ((section === 0) || !zero) {
                zero = true;
                chnStr =  chnNumChar[v] + chnStr;
            }
        } else {
            // 至少有一个数字不是
            zero = false;
            // 此位对应的中文数字
            strIns = chnNumChar[v];
            // 此位对应的中文权位
            strIns += chnUnitChar[unitPos];
            chnStr = strIns + chnStr;
        }
        // 移位
        unitPos++;
        section = parseInt(section / 10);
    }
    return chnStr;
}
var body = document.querySelector('body');
var num = 10010441;
var text = document.createTextNode(num + ' => '+ NumberToChinese(num));
// 输出 “10010441 => 一千零一万零四百四十一”
body.appendChild(text);

发表于 | 分类于 |

基础用法

  • display: flex | inline-flex; (适用于父类容器元素上)

父类元素属性

概览

  1. flex-direction
  2. flex-wrap
  3. flex-flow
  4. flex-flow
  5. justify-content
  6. align-items
  7. align-content

详细

  • flex-direction (适用于父类容器的元素上)
  • flex-direction: row | row-reverse | column | column-reverse
  • flex-wrap (适用于父类容器上)
  • flex-wrap: nowrap | wrap | wrap-reverse
  • flex-flow (适用于父类容器上)复合属性。
  • flex-flow: <‘flex-direction’> || <‘flex-wrap’>
  • justify-content (适用于父类容器上)
  • justify-content: flex-start | flex-end | center | space-between | space-around
  • 设置或检索弹性盒子元素在主轴（横轴）方向上的对齐方式
  • align-items (适用于父类容器上)
  • align-items: flex-start | flex-end | center | baseline | stretch
  • 设置或检索弹性盒子元素在侧轴（纵轴）方向上的对齐方式。
  • align-content (适用于父类容器上)
  • align-content: flex-start | flex-end | center | space-between | space-around | stretch
  • 设置或检索弹性盒堆叠伸缩行的对齐方式。

子类元素属性

概述

  1. order - 排序
  2. flex-grow
  3. flex-shrink
  4. flex-basis
  5. flex
  6. align-self

详解

  • order (适用于弹性盒模型容器子元素)
  • order: <integer>数值小的排在前面。可以为负值。
  • flex-grow (适用于弹性盒模型容器子元素)
  • 设置或检索弹性盒的扩展比率。
  • flex-grow: <number> (default 0)
  • flex-shrink (适用于弹性盒模型容器子元素)
  • 设置或检索弹性盒的收缩比率（根据弹性盒子元素所设置的收缩因子作为比率来收缩空间。）
  • flex-shrink: <number> (default 1)
  • flex-basis (适用于弹性盒模型容器子元素)
  • 设置或检索弹性盒伸缩基准值。
  • flex-basis: <length> | auto (default auto)
  • flex (适用于弹性盒模型子元素)
  • 复合属性。设置或检索伸缩盒对象的子元素如何分配空间。如果缩写flex:1, 则其计算值为：1 1 0
  • flex：none | [ flex-grow ] || [ flex-shrink ] || [ flex-basis ]
  • align-self (适用于弹性盒模型子元素)
  • 设置或检索弹性盒子元素自身在侧轴（纵轴）方向上的对齐方式。
  • align-self: auto | flex-start | flex-end | center | baseline | stretch

例子

demo github： https://github.com/zyziyun/flexbox-demo

1.jpeg 3.jpeg 2.jpeg

发表于 | 分类于 |

运行效率

  • 如果项目是多入口配置，在本地开发阶段不需要每次都跑全部的
  • 可以获取到运行命令行参数决定，跑哪些页面，加快速度
  • process.env.npm_config_argv或者使用yargs这个npm包获取命令行传入的参数
1
2
3
4
5
6
7
var scriptArg = process.env.npm_config_argv && JSON.parse(process.env.npm_config_argv);
var targetDir = scriptArg && scriptArg.original[2] && scriptArg.original[2].substr(1) || '';
var js = glob.sync('./' + (targetDir || '**') + '/*.js').reduce(function (prev, curr) {
    prev[curr.slice(6, -3)] = ['./' + curr.substr(6)];
    return prev;
}, {});
1
2
3
4
5
6
7
var argv = require('yargs').argv;
var list = argv._[0] || '*';
var js = glob.sync('./' + list + '/*.js').reduce(function (prev, curr) {
    prev[curr.slice(6, -3)] = [curr];
    return prev;
}, {});
  • process.env.npm_config_argv：在使用yarn run xxx的时候不能获取到参数，在使用npm run xxx的时候可以获取到
  • yargs这个包是都可以获取到的

路径问题

  • 问题描述：在上线和测试环境下代码发到cdn上，静态资源和页面地址不在一处，需要配置不同的前缀地址，才能引入线上script
  • 通过output -> publicPath 根据不同的环境变量变更path路径，解决加载问题
1
2
3
4
5
6
7
8
9
10
output: {
	path: path.resolve('./build'),
	filename: '[name].js',
	publicPath: env === 'development'
		? '/' : (
			env === 'production'
				? '//xxx.production.com/'
				: '//xxx.test.com/'
		)
}

htmlPlugin

普通配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var htmlFiles = glob.sync('./**/*.html');
var html = htmlFiles.map(function (item) {
    console.log(item.substr(6));
    return new HtmlWebpackPlugin({
        data: {
            build: true
        },
        filename: item.substr(6),
        template: 'ejs-compiled!' + item,
        inject: false,
        minify: {
            removeComments: true,
            collapseWhitespace: true,
            preserveLineBreaks: true,
            collapseInlineTagWhitespace: true,
            collapseBooleanAttributes: true,
            removeRedundantAttributes: true,
            useShortDoctype: true,
            caseSensitive: true,
            minifyJS: true,
            minifyCSS: true,
            quoteCharacter: '"'
        }
    });
});
  • 把html 连接到webpack的plugin属性上（concat）一个配置只能针对一个文件
  • data的内容，可以在template里获取到然后做相应的改动
  • filename：输出html的名称，可以带路径
  • template: 模板名称及使用什么编译器 ejs-compiled可以使用ejs语法
  • inject：是否把所有静态资源自动添加到html里，这里不使用，目前的模板配置是直接引入了入口的文件，后面在回调里添加hash实现，下图是模板文件：
1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE html>
<html lang="en">
<head>
  <%- include ../header.html -%>
  <title></title>
  <meta http-equiv="Cache-Control" content="no-cache">
</head>
<body>
  <div id="mount"></div>
  <script src="./xxx.js" defer></script>
</body>
</html>
  • 可以使用ejs的语法
  • minify：压缩模板配置
    • removeComments：删除注释
    • collapseWhitespace：删除多余的空格
    • preserveLineBreaks：保留每个标签tag的换行符
    • collapseInlineTagWhitespace：不保留行内元素两边的空格
    • collapseBooleanAttributes：使input的一些的布尔值的属性合并，不写等于了，例如：disabled
    • removeRedundantAttributes：删除多余的标签，例如没有赋值的style，class等
    • useShortDoctype：替换成较短的html5 doctype
    • caseSensitive：区分大小写的方式处理自定义标签
    • minifyJS：行内scripts标签，或者attribute里的是否压缩
    • minifyCSS：行内style标签，或者attribute里的是否压缩
    • quoteCharacter：对于attribute用什么符号

plugin完成后的一些操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function () {
	this.plugin('done', function (stats) {
		var replaceInFile = function (filePath, toReplace, replacement) {
			var str = fs.readFileSync(filePath, 'utf8');
			var out = str.replace(toReplace, replacement);
			fs.writeFileSync(filePath, out);
		};
		htmlFiles.map(function (item) {
			replaceInFile(path.join(config.build.assetsRoot, item.substr(6)),
				/(src|href)=\"([\/\w\.]+\.(js|css))\"/g,
				function ($0, $1, $2) {
					var file = $2.split('.');
					file.splice(-1, 0, stats.hash);
					file = file.join('.');
					return $1 + '="' + file + '"';
				}
			);
		});
	});
}

sass-loader

设置import相对路径，不过最后引用的时候用~开头，node_modules里的scss引用可以直接相对”~”引用

3.jpeg

https://github.com/webpack-contrib/sass-loader#imports

resolve

1
2
3
4
5
6
7
8
9
10
11
12
13
resolve: {
	extensions: ['', '.js', '.vue'],
	fallback: [path.join(__dirname, '../node_modules')],
	alias: {
		'vue$': 'vue/dist/vue',
		'scss': path.resolve(__dirname, '../src/modules/scss'),
		'vue-directive': path.resolve(__dirname, '../src/modules/vue-directive'),
		'request': path.resolve(__dirname, '../src/modules/request'),
		'common': path.resolve(__dirname, '../src/modules/common'),
		'vue-component': path.resolve(__dirname, '../src/modules/vue-component'),
		'vue-fragment': path.resolve(__dirname, '../src/modules/vue-fragment')
	}
}
  • extensions：扩展名
  • fallback：
  • alias：别名，具体定义一个别名的路径，方便引入modules
7.jpeg

webpack2把root，fallback迁移到了modules的配置里，告诉webpack解析的搜索路径
Explicit is better than implicit
alias清晰的比modules的好，效率？？

配置代理

  • 背景：本地开发嵌套iframe的页面的时候，两个项目的端口号不统一，导致iframe同源策略不允许互相操作跳转
  • 解决：配置到同一端口号的域名上。“devServer.proxy”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
devServer: {
	host: 'localhost',
	port: 8080,
	historyApiFallback: true,
	inline: true,
	hot: true,
	proxy: {
		'/pages': 'http://localhost:8899'
	},
	stats: {
		children: false,
		chunks: false
	}
}

注意点

  1. 路径是否正确，publicPath，path，如果是相对路径相对哪里，最好配置成path.resolve(__dirname, xxx)的形式
  2. 如果用的别人配置好的多文件的配置，检查loader是否有重复的，可能出现多个loader配置重复的问题，等于是模块解析了2次，会报错
  3. 拆分模块的情况下，一定要配置publicPath，确定异步加载的模块地址