寒假前端学习(6)——学习JavaScript数据结构与算法(四):二叉搜索树

本系列的第一篇文章: 学习JavaScript数据结构与算法(一):栈与队列
第二篇文章:学习JavaScript数据结构与算法(二):链表
第三篇文章: 学习JavaScript数据结构与算法(三):集合
第四篇文章: 学习JavaScript数据结构与算法(四):二叉搜索树

我与二叉树的前尘往事

在刚学编程时,就知道有一种数据结构叫“树”,树中的翘楚是“二叉树”,“红黑树”等。
据说“树”构在编程界呼风唤雨无所不能。让无数程序员闻风丧胆。甚至在面试时,更是有“手写二叉树”,“翻转二叉树”等题目坐镇。

好吧,我承认这些在当时都把我吓住了。

但是当我颤抖着打开《学习JavaScript数据结构与算法》,开始敲下关于“树”的代码时,突然觉得,好像也没有那么难呢。
于是心怀激动,一口气敲完了书上的例子,中途也思考了很久,不断的在纸上演算等。但总的来说,还是学的很开心的。

树の简介

之前学的栈、队列、链表等数据结构,都是顺序数据结构。而树,将会是我们学的第一种非顺序数据结构。

放在现实里呢,有个很生动的例子,公司组织架构图。长这样:
公司组织架构图

而我们要学的树,长这样:
树の图示

节点简介

其中,树中的每个元素,都叫做节点。从节点延伸而下的,叫子节点
树顶部的节点叫根节点。每棵树只有一个根节点。(图中15就是根节点)
在节点中,有子节点的节点也称为内部节点,没有的话则被称为外部节点或者叶节点。
同时在节点中是有祖先和后代关系的,比如节点9的祖先就有13,7,6,15四个。

节点属性

深度: 节点的深度取决于其祖先的数量,节点9的深度就是4。
树的高度,树的高度体现为节点深度的最大值。
比如上图,节点深度最大值为4,则树的高度为4。

二叉树与二叉搜索树

二叉树的最大特点就在于,它的节点最多只有两个子节点:左侧子节点和右侧子节点。
二叉搜索树则是二叉树的一种,但它只允许你在左侧节点储存比父节点小的值,右侧只允许储存比父节点大的值。
像刚才的这幅图,就是二叉搜索树。
二叉搜索树

而我们本文要学习的内容,就是如何写一个二叉搜索树。

JavaScipt中二叉搜索树的实现

首先,创建一个构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 二叉搜索树的构造函数
*/
function BinarySearchTree() {
/**
* 二叉搜索树键的构造函数
* @param {Number} key 要生成的键值
*/
var Node = function(key) {
// 键值
this.key = key;
// 左子节点
this.left = null;
// 右子节点
this.right = null;
}
/**
* 二叉树的根节点,不存在时表示为Null
* @type {Null or Number}
*/
var root = null;
}

在之前提到过的双向链表中,每个节点包含两个指针,一个指向左侧节点,一个指向右侧节点。在二叉搜索树中,每个节点也有两个指针,一个指向左侧子节点,一个指向右侧子节点。但在二叉搜索树中,我们把节点成为,这是术语。

二叉搜索树需要有如下的方法:

  • insert(key): 向树中插入一个新的键
  • inOrderTraverse(): 通过中序遍历方式,遍历所有节点
  • preOrderTranverse(): 通过先序遍历方式,遍历所有节点
  • postOrderTranverse(): 通过后序遍历方式,遍历所有节点
  • min(): 返回树中最小的值
  • max(): 返回树中最大的值
  • search(key): 搜索某个值,在树中则返回true
  • remove(key): 从树中移除某个键

二叉搜索树的实现,基本都与递归有关(对我来说递归很绕,花了很久才理解)。如果不清楚递归相关概念,可以看看下面的参考链接。

什么是递归

insert方法:

说明:向树中插入一个新的键
实现:

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
/**
* 插入某个键到二叉树中
* @param {Number} key 要插入的键值
*/
this.insert = function(key) {
// 用传入的值生成二叉树的键
var newNode = new Node(key);
// 根节点为Null时,传入的键则为根节点
// 否则调用insertNode函数来插入子节点
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode)
}
};
/**
* 用于插入子节点。
* @param {Node} node 根节点
* @param {Node} newNode 要插入的节点
*/
var insertNode = function(node, newNode) {
//由于二叉搜索树的性质,所以当键值小于当前所在节点的键值
//则使得左子结点成为新的要比较的节点,进行递归调用
//如果左子结点为null,则将键值赋值给左子结点。
//如果键值大于当前所在节点的键值,原理同上。
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
};

inOrderTraverse方法:

说明:通过中序遍历方式,遍历所有节点
实现:

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
/**
* 中序遍历操作,常用于排序。会把树中元素从小到大的打印出来。
* 因为在javascript的递归中,遇到递归是,会优先调用递归的函数。直到递归不再进行。
* 然后会在递归调用的最后一个函数中执行其它语句。再一层层的升上去。
* 所以中序遍历会有从小到大的输出结果。
* 后续的先序和后续遍历和这个原理差不多,取决于callback放在哪儿。
*
* @param {Function} callback 获取到节点后的回调函数
*/
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
/**
* 中序遍历的辅助函数,用于遍历节点
* @param {Node} node 遍历开始的节点,默认为root
* @param {Function} callback 获取到节点后的回调函数
* @return {[type]} [description]
*/
var inOrderTraverseNode = function(node, callback) {
// 当前节点不为NULL则继续递归调用
if (node != null) {
inOrderTraverseNode(node.left, callback);
// 获取到节点后,调用的函数
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
};

假如我们这儿加入打印节点值的函数:

1
2
3
4
5
var printNode = function(value) {
console.log(value);
};
inOrderTraverse(printNode) // 输出排序后树的值

preOrderTranverse方法:

说明:通过先序遍历方式,遍历所有节点
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 前序遍历操作,常用于打印一个结构化的文档
* @param {Function} callback 获取到节点后的回调函数
*/
this.preOrderTranverse = function(callback) {
preOrderTranverseNode(root, callback);
};
/**
* 前序遍历的辅助函数,用于遍历节点
* @param {Node} node 遍历开始的节点,默认为root
* @param {Function} callback 获取到节点后的回调函数
*/
var preOrderTranverseNode = function(node, callback) {
if (node != null) {
callback(node.key);
preOrderTranverseNode(node.left, callback);
preOrderTranverseNode(node.right, callback);
}
};

postOrderTranverse方法:

说明:通过后序遍历方式,遍历所有节点
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 后序遍历操作,常用于计算所占空间
* @param {Function} callback 获取到节点后的回调函数
*/
this.postOrderTranverse = function(callback) {
postOrderTranverseNode(root, callback);
};
/**
* 后序遍历的辅助函数,用于遍历节点
* @param {Node} node 遍历开始的节点,默认为root
* @param {Function} callback 获取到节点后的回调函数
*/
var postOrderTranverseNode = function(node, callback) {
postOrderTranverseNode(node.left, callback);
postOrderTranverseNode(node.right, callback);
callback(node.key);
};

min方法:

说明:返回树中最小的值,由二叉搜索树的性质易知,最左侧的为最小值。则只需取得最左侧的值即可。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 返回树中最小的值
* @return {Function} min函数的辅助函数
*/
this.min = function() {
return minNode(root);
};
/**
* min函数的辅助函数
* @param {Node} node 查找开始的节点,默认为root
*/
var minNode = function(node) {
// 如果node存在,则开始搜索。能避免树的根节点为Null的情况
if (node) {
// 只要树的左侧子节点不为null,则把左子节点赋值给当前节点。
// 若左子节点为null,则该节点肯定为最小值。
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
};

max方法:

说明:返回树中最大的值,由min函数易知,最大值在最右侧。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 返回树中最大的值
* @return {Function} max函数的辅助函数
*/
this.max = function() {
return maxNode(root);
};
/**
* max函数的辅助函数
* @param {Node} node 查找开始的节点,默认为root
* @return {Key} 节点的值
*/
var maxNode = function(node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};

search方法:

说明: 搜索某个值,在树中则返回true
实现:

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
/**
* 搜索某个值是否存在于树中
* @param {Node} key 搜索开始的节点,默认为root
* @return {Function} search函数的辅助函数
*/
this.search = function(key) {
return searchNode(root, key);
};
/**
* search函数的辅助函数
* @param {Node} node 搜索开始的节点,默认为root
* @param {Key} key 要搜索的键值
* @return {Boolean} 找到节点则返回true,否则返回false
*/
var searchNode = function(node, key) {
// 如果根节点不存在,则直接返回null
if (node === null) {
return false;
} else if (key < node.key) {
searchNode(node.left, key)
} else if (key > node.key) {
searchNode(node.right, key)
} else {
// 如果该节点值等于传入的值,返回true
return true;
}
};

remove方法:

说明:从树中移除某个键,要应对的场景:

  1. 只是一个叶节点
  2. 有一个子节点
  3. 有两个子节点的节点
    因为要应付不同的场景,所以这是最麻烦的方法了。让我思考了好久才理解。如果你觉得看不懂的话,可以下载源代码把这一段写一遍。
    实现:
    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
    /**
    * 从树中移除某个键
    * @param {Key} key 要移除的键值
    * @return {Function} remove函数的辅助函数
    */
    this.remove = function(key) {
    root = removeNode(root, key);
    };
    /**
    * remove函数的辅助函数
    * @param {Node} node 搜索开始的节点,默认为root
    * @param {Key} key 要移除的键值
    * @return {Boolean} 移除成功则返回true,否则返回false
    */
    var removeNode = function(node, key) {
    // 如果根节点不存在,则直接返回null
    if (node === root) {
    return null;
    }
    // 未找到节点前,继续递归调用。
    if (key < node.key) {
    node.left = removeNode(node.left, key)
    return node;
    } else if (key > node.key) {
    node.right = removeNode(node.right, key)
    return node;
    } else {
    // 第一种场景:只是一个叶节点
    // 这种情况只需要直接把节点赋值为null即可
    if (node.left === null && node.right === null) {
    node = null;
    // 处理完直接return节点
    return node;
    }
    // 第二种场景:有一个子节点
    // 如果左节点为null,则代表右节点存在。
    // 于是把当前节点赋值为存在的那个子节点
    if (node.left === null) {
    node = node.right;
    // 处理完直接return节点
    return node;
    } else if (node.right == null) {
    node = node.left;
    // 处理完直接return节点
    return node;
    }
    // 第三种场景:有两个子节点
    // 首先加入辅助节点,同时找寻右子节点中的最小节点
    // 并把当前节点替换为右子节点中的最小节点
    // 同时为了避免节点重复,移除右子节点中的最小节点
    var aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    // 处理完直接return节点
    return node;
    }
    };
    /**
    * remove函数的辅助函数
    * @param {Node} node 查找开始的节点,默认为root
    * @return {Node} 最小的节点
    */
    var findMinNode = function(node) {
    // 如果node存在,则开始搜索。能避免树的根节点为Null的情况
    if (node) {
    // 只要树的左侧子节点不为null,则把左子节点赋值给当前节点。
    // 若左子节点为null,则该节点肯定为最小值。
    while (node && node.left !== null) {
    node = node.left;
    }
    return node;
    }
    return null;
    };

源代码:

源代码在此~

二叉搜索树-源代码

感想

写文章的时候,人有点感冒,晕晕乎乎的。不过写完之后就好多了,脑子清醒了许多。
二叉树这一章,就我而言感慨万分,也算是暂时满足了自己对数据结构中“树”的向往与愿望,也不是之前看数据结构中那种迷茫的感觉。

能用JavaScript亲手实现,还是非常开心的。

前端路漫漫,且行且歌~

寒假前端学习(5)——学习JavaScript数据结构与算法(三):集合

本系列的第一篇文章: 学习JavaScript数据结构与算法(一):栈与队列
第二篇文章:学习JavaScript数据结构与算法(二):链表
第三篇文章: 学习JavaScript数据结构与算法(三):集合
第四篇文章: 学习JavaScript数据结构与算法(四):二叉搜索树

集合(Set)

说起集合,就想起刚进高中时,数学第一课讲的就是集合。因此在学习集合这种数据结构时,倍感亲切。
集合的基本性质有一条: 集合中元素是不重复的。因为这种性质,所以我们选用了对象来作为集合的容器,而非数组。
虽然数组也能做到所有不重复,但终究过于繁琐,不如集合。

集合的操作

集合的基本操作有交集、并集、差集等。这儿我们介绍JavaScipt集合中交集、并集、差集的实现。至于这三个的具体概念,可以看图:
交集、并集、差集

JavaScipt中集合的实现

首先,创建一个构造函数。

1
2
3
4
5
6
7
8
9
10
/**
* 集合的构造函数
*/
function Set方法 {
/**
* 集合元素的容器,以对象来表示
* @type {Object}
*/
var items = {};
}

集合需要有如下方法:

  • has(value): 检测集合内是否有某个元素
  • add(value): 给集合内添加某个元素
  • remove(value): 移除集合中某个元素
  • clear(value): 清空集合
  • size(): 返回集合长度
  • values(): 返回集合转换的数组
  • union(otherSet): 返回两个集合的并集
  • intersection(otherSet): 返回两个集合的交集
  • difference(otherSet): 返回两个集合的差集
  • subset(otherSet): 判断该集合是否为传入集合的子集

has方法:

说明:集合中元素是不重复的。所以在其它任何操作前,必须用has方法确认集合是否有某个元素。这儿使用了hasOwnProperty方法来检测。
实现:

1
2
3
4
5
6
7
8
9
10
/**
* 检测集合内是否有某个元素
* @param {Any} value 要检测的元素
* @return {Boolean} 如果有,返回true
*/
this.has = function(value) {
// hasOwnProperty的问题在于
// 它是一个方法,所以可能会被覆写
return items.hasOwnProperty(value)
};

add方法:

说明: 给集合内添加某个元素。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 给集合内添加某个元素
* @param {Any} value 要被添加的元素
* @return {Boolean} 添加成功返回True。
*/
this.add = function(value) {
//先检测元素是否存在。
if (!this.has(value)) {
items[value] = value;
return true;
}
//如果元素已存在则返回false
return false;
};

remove方法:

说明: 移除集合中某个元素
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 移除集合中某个元素
* @param {Any} value 要移除的元素
* @return {Boolean} 移除成功返回True。
*/
this.remove = function(value) {
//先检测元素是否存在。
if (this.has(value)) {
delete items[value];
return true;
}
//如果元素不存在,则删除失败返回false
return false;
};

####clear方法:
说明: 清空集合
实现:

1
2
3
4
5
6
/**
* 清空集合
*/
this.clear = function() {
this.items = {};
};

size方法

说明: 返回集合长度,这儿有两种方法。第一种方法使用了Object.keys这个Api,但只支持IE9及以上。第二种则适用于所有浏览器。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 返回集合长度,只可用于IE9及以上
* @return {Number} 集合长度
*/
this.size = function() {
// Object.keys方法能将对象转化为数组
// 只可用于IE9及以上,但很方便
return Object.keys(items).length;
}
/**
* 返回集合长度,可用于所有浏览器
* @return {Number} 集合长度
*/
this.sizeLegacy = function() {
var count = 0;
for (var prop in items) {
if (items.hasOwnProperty(prop)) {
++count;
}
}
return count;
}

values方法

说明: 返回集合转换的数组,这儿也有两种方法。理由同上。使用了Object.keys,只能支持IE9及以上。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 返回集合转换的数组,只可用于IE9及以上
* @return {Array} 转换后的数组
*/
this.values = function() {
return Object.keys(items);
};
/**
* 返回集合转换的数组,可用于所有浏览器
* @return {Array} 转换后的数组
*/
this.valuesLegacy = function() {
var keys = [];
for (var key in items) {
keys.push(key)
};
return keys;
};

union方法

说明: 返回两个集合的并集
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 返回两个集合的并集
* @param {Set} otherSet 要进行并集操作的集合
* @return {Set} 两个集合的并集
*/
this.union = function(otherSet) {
//初始化一个新集合,用于表示并集。
var unionSet = new Set();
//将当前集合转换为数组,并依次添加进unionSet
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
//将其它集合转换为数组,依次添加进unionSet。
//循环中的add方法保证了不会有重复元素的出现
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
return unionSet;
};

intersection方法

说明: 返回两个集合的交集
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 返回两个集合的交集
* @param {Set} otherSet 要进行交集操作的集合
* @return {Set} 两个集合的交集
*/
this.intersection = function(otherSet) {
//初始化一个新集合,用于表示交集。
var interSectionSet = new Set();
//将当前集合转换为数组
var values = this.values();
//遍历数组,如果另外一个集合也有该元素,则interSectionSet加入该元素。
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
interSectionSet.add(values[i])
}
}
return interSectionSet;
};

difference方法

说明: 返回两个集合的差集
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 返回两个集合的差集
* @param {Set} otherSet 要进行差集操作的集合
* @return {Set} 两个集合的差集
*/
this.difference = function(otherSet) {
//初始化一个新集合,用于表示差集。
var differenceSet = new Set();
//将当前集合转换为数组
var values = this.values();
//遍历数组,如果另外一个集合没有该元素,则differenceSet加入该元素。
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet;
};

subset方法

说明: 判断该集合是否为传入集合的子集。这段代码在我自己写完后与书上一比对,觉得自己超级low。我写的要遍历数组三次,书上的只需要一次,算法复杂度远远低于我的。
实现:

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
/**
* 判断该集合是否为传入集合的子集
* @param {Set} otherSet 传入的集合
* @return {Boolean} 是则返回True
*/
this.subset = function(otherSet) {
// 第一个判定,如果该集合长度大于otherSet的长度
// 则直接返回false
if (this.size() > otherSet.size()) {
return false;
} else {
// 将当前集合转换为数组
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
// 第二个判定。只要有一个元素不在otherSet中
// 那么则可以直接判定不是子集,返回false
return false;
}
}
return true;
}
};

源代码

源代码在此~

集合-源代码

ES6中的集合

ES6也提供了集合,但之前看ES6的集合操作一直迷迷糊糊的。实现一遍后再去看,感觉概念清晰了很多。
具体的我掌握的不是很好,还在学习中,就不写出来啦~推荐看阮一峰老师的《ECMAScript 6入门》中对ES6 Set的介绍。

《ECMAScript 6入门》– Set和Map数据结构

感想

到了这儿,已经掌握了一些基本的数据结构。剩下的都是难啃的骨头了(对我而言)。

字典的散列表、图、树、排序算法。算是四大金刚,所以近期关于数据结构与算法系列的文章,可能会更新的很慢。对我来说,也算是一个坎。希望这个寒假,能跨过这个坎。

前端路漫漫,且行且歌~

寒假前端学习(4)——学习JavaScript数据结构与算法(二):链表

本系列的第一篇文章: 学习JavaScript数据结构与算法(一):栈与队列
第二篇文章:学习JavaScript数据结构与算法(二):链表
第三篇文章: 学习JavaScript数据结构与算法(三):集合
第四篇文章: 学习JavaScript数据结构与算法(四):二叉搜索树

链表简介

链表是一种常见的数据结构,也属于线性表,但不会按线性的顺序来储存数据。而是在每一个节点中,储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度),链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

接下来就是介绍两种常见的链表: 单向链表,双向链表在JavaScript中的实现。

单向链表

链表中最简单的形式就是单向链表,链表中的节点都包含两个部分,第一部分储存着自身信息,第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL,如图所示:
单向链表图示2

JavaScipt中单向链表的实现

首先,创建一个构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 单向链表构造函数
*/
function LinkedList() {
/**
* 单向链表中节点的构造函数
* @param {Any} element 要传入链表的节点
*/
var Node = function(element) {
this.element = element;
//下个节点的地址
this.next = null;
}
//单向链表的长度
var length = 0;
//单向链表的头结点,初始化为NULL
var head = null;
}

不难看出,单向链表构造函数比栈与队列要复杂许多。

单向链表需要有如下的方法:

  • append(element): 添加元素到链表尾部
  • insert(position,element): 向单向链表中某个位置插入元素
  • indexOf(element): 寻找某个元素在单向链表中的位置
  • remove(element): 移除给定的元素
  • removeAt(position): 移除单向链表中某个位置的元素
  • getHead(): 获取单向链表的头部
  • isAmpty(): 检查单向链表是否为空,为空则返回true
  • toString(): 将链表所有内容以字符串输出
  • size(): 返回单向链表长度

append方法:

说明: 向单向链表尾部添加元素。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 向单向链表尾部添加元素
* @param {Any} element 要加入链表的节点
*/
this.append = function(element) {
var node = new Node(element);
var current;
if (head == null) {
head = node;
} else {
// 当前项等于链表头部元素.
// while循环到最后一个,从而将该节点加入链表尾部。
current = head;
// 当next为null时,判定为false。退出循环。
while (current.next) {
current = current.next;
}
current.next = node;
}
length++;
};

insert方法:

说明: 向单向链表中某个位置插入元素。
实现:

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
/**
* 向单向链表中插入某个元素
* @param {Number} position 要插入的位置
* @param {Any} element 要插入的元素
* @return {Boolean} 插入成功返回true,失败返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position == 0) {
node.next = current;
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};

indexOf方法:

说明:寻找某个元素在单向链表中的位置。
实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 寻找某个元素在单向链表中的位置
* @param {Any} element 要寻找的元素
* @return {Number} 返回值>=0则代表找到相应位置
*/
this.indexOf = function(element) {
var current = head;
var index = -1;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};

remove方法:

说明: 移除给定的元素。
实现:

1
2
3
4
5
6
7
8
9
/**
* 移除给定的元素
* @param {Any} element 要移除的元素
* @return {Number} 返回值>=0表示移除成功
*/
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};

removeAt方法:

说明:移除单向链表中某个位置的元素。
实现:

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
/**
* 移除单向链表中某一个元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素,不成功则返回NULL
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var previous;
var index = 0;
if (position == 0) {
// 因为之前head指向第一个元素,现在把head修改为指向第二个元素。
// 核心概念在于链表前后全靠指针链接,而非数组一般。
// 所以只需要改变head的元素。
head = current.next;
} else {
while (index++ < position) {
// previous指要操作元素位置之前的那个元素,current表示之后的那个元素。
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};

getHead方法:

说明:获取单向链表的头部。
实现:

1
2
3
4
5
6
7
/**
* 获取单向链表的头部
* @return {Any} 单向链表的头部
*/
this.getHead = function() {
return head;
}

isAmpty、toString、size方法

实现:

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
/**
* 判断单向链表是否为空
* @return {Boolean} 为空则返回true,不为空则返回false
*/
this.isAmpty = function() {
return length === 0
};
/**
* 将链表所有内容以字符串输出
* @return {String} 要输出的字符串
*/
this.toString = function() {
var current = head;
var string = '';
while (current) {
string += current.element;
current = current.next;
}
return string;
};
/**
* 返回单向链表长度
* @return {Number} 单向链表的长度
*/
this.size = function() {
return length;
};

源代码

以上的就是单向链表在JavaScript中的实现,有兴趣的同学可以自己下载源代码查看。

单向链表-源代码

双向链表

双向链表与单向链表很是相像。在单向链表中,只有指向下一个节点的链接。但在双向链表中,还有指向上一个节点的链接,是双向的。
如图所示: 双向链表图示

JavaScipt中双向链表的实现

首先,依然是构造函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 双向链表的构造函数
*/
function DoublyLinkedList() {
/**
* 双向链表中节点的构造函数
* @param {Any} element 要传入链表的元素
*/
var Node = function(element) {
this.element = element;
this.prev = null;
this.next = null;
}
//双向链表的长度
var length = 0;
//双向链表的头结点,初始化为NULL
var head = null;
//双向链表的尾结点,初始化为NULL
var tail = null;
}

双向链表需要有如下的方法:

  • append(element): 添加元素到双向链表尾部
  • insert(position,element): 向双向链表中某个位置插入元素
  • removeAt(position): 移除双向链表中某个位置的元素
  • showHead(): 获取双向链表的头部
  • showLength(): 获取双向链表长度
  • showTail(): 获取双向链表尾部

append方法:

说明: 添加元素到双向链表尾部
实现:

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
/**
* 向链表尾部添加元素
* @param {Any} element 要加入链表的节点
* @return {Any} 加入链表的节点
*/
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var previous;
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};

insert方法:

说明: 向双向链表中某个位置插入元素。
实现:

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
/**
* 向链表中插入某个元素
* @param {Number} position 要插入的位置
* @return {Boolean} 插入成功返回true,失败返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var index = 0;
var previous;
var current = head;
if (position === 0) {
if (head === null) {
head = node;
tail = node;
} else {
current.prev = node;
node.next = current;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.prev = previous;
current.prev = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};

removeAt方法:

说明:移除双向链表中某个位置的元素。
实现:

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
/**
* 移除链表中某一个元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素,不成功则返回false
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var index = 0;
var previous;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current.prev;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return false;
}
};

showHead、showLength、showTail方法

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 获取链表的头部
* @return {Any} 链表的头部
*/
this.showHead = function() {
return head;
};
/**
* 获取链表长度
* @return {Number} 链表长度
*/
this.showLength = function() {
return length;
};
/**
* 获取链表尾部
* @return {Any} 链表尾部
*/
this.showTail = function() {
return tail;
};

源代码

源代码在此~

双向链表-源代码

感想

链表这一节,基本全部都是先按需求写代码,写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑,逻辑也很混乱。看来还是太年轻了。

有兴趣的同学,也可以自己试试只看要求先写代码,写完后再与书上比对,就知道自己的不足了。

前端路漫漫,且行且歌~

寒假前端学习(3)——学习JavaScript数据结构与算法(一):栈与队列

本系列的第一篇文章: 学习JavaScript数据结构与算法(一):栈与队列
第二篇文章:学习JavaScript数据结构与算法(二):链表
第三篇文章: 学习JavaScript数据结构与算法(三):集合
第四篇文章: 学习JavaScript数据结构与算法(四):二叉搜索树

学习起因

曾经有一次在逛V2EX时,碰到这么一个帖子。

数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐?

发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作。感觉到数学知识的匮乏,所以想补一补数学。

看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端。也同样感觉到了数学知识匮乏所带来的困顿。同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识。

当时也有人说:”前端需要什么数据结构与算法”,但是对于这个事情我有自己的看法。

我并不认为前端不需要算法之类的知识,在我看来前端具备坚实的计算机基础,对自身发展是极其有利的。我想做程序员。而不是一辈子的初级前端和码农。

也算是给自己的勉励吧。毕竟基础决定上限,再加上自己对计算机真的很感兴趣,所以学起来就算很累,但也是很幸福的。于是去网上选购了《学习JavaScript数据结构与算法》这本书,配合着去图书馆借阅的《大话数据结构》,开始了数据结构与算法的初步学习。

选用的书籍

这本书讲的内容很是不错,清晰易懂。同时用JavaScipt语言实现,学起来的难度低。值得一看呢。

书中前两章是对JavaScipt基础与数组常用操作的讲解,如果不清楚的话,推荐去看看下面这篇博客。

JavaScipt之数组操作

接下来就是数据结构的第一部分,栈。

栈是一种遵从后进先出原则(LIFO,全称为Last In First Out)的有序集合。栈顶永远是最新的元素。

举个例子就是:栈就像放在箱子里的一叠书 你要拿下面的书先要把上面的书拿开。(当然,你不能先拿下面的书。)

看图示也可明白。

栈的图示

JavaScipt中栈的实现

首先,创建一个构造函数。

1
2
3
4
5
6
7
8
/**
* 栈的构造函数
*/
function Stack() {
// 用数组来模拟栈
var item = [];
}

栈需要有如下的方法:

  • push(element(s)): 添加几个元素到栈顶
  • pop(): 移除并返回栈顶元素
  • peek(): 返回栈顶元素
  • isAmpty: 检查栈是否为空,为空则返回true
  • clear: 移除栈中所有元素
  • size: 返回栈中元素个数。
  • print: 以字符串显示栈中所有内容

push方法的实现

说明: 需要往栈中添加新元素,元素位置在队列的末尾。也就是说,我们可以用数组的push方法来模拟实现。

实现:

1
2
3
4
5
6
7
/**
* 将元素送入栈,放置于数组的最后一位
* @param {Any} element 接受的元素,不限制类型
*/
this.push = function(element) {
items.push(element);
};

pop方法的实现

说明: 需要把栈顶元素弹出,同时返回被弹出的值。可以用数组的pop方法来模拟实现。

实现:

1
2
3
4
5
6
7
/**
* 弹出栈顶元素
* @return {Any} 返回被弹出的值
*/
this.pop = function() {
return items.pop();
};

peek方法的实现

说明: 查看栈顶元素,可以用数组长度来实现。

实现:

1
2
3
4
5
6
7
/**
* 查看栈顶元素
* @return {Any} 返回栈顶元素
*/
this.peek = function() {
return items[items.length - 1];
}

其余方法的实现

说明: 前三个是栈方法的核心,其余方法则在此一次性列出。因为下文要讲的队列,会与这部分有很大重合。

实现:

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
/**
* 确定栈是否为空
* @return {Boolean} 若栈为空则返回true,不为空则返回false
*/
this.isAmpty = function() {
return items.length === 0
};
/**
* 清空栈中所有内容
*/
this.clear = function() {
items = [];
};
/**
* 返回栈的长度
* @return {Number} 栈的长度
*/
this.size = function() {
return items.length;
};
/**
* 以字符串显示栈中所有内容
*/
this.print = function() {
console.log(items.toString());
};

实际应用

栈的实际应用比较多,书中有个十进制转二进制的函数。(不懂二进制怎么算的话可以百度)下面是函数的源代码。

原理就是输入要转换的数字,不断的除以二并取整。并且最后运用while循环,将栈中所有数字拼接成字符串输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 将10进制数字转为2进制数字
* @param {Number} decNumber 要转换的10进制数字
* @return {Number} 转换后的2进制数字
*/
function divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while (!remStack.isAmpty()) {
binaryString += remStack.pop().toString();
}
return binaryString;
};

到此而言,栈的学习就告一段落了。因为源代码中注释较多,所以这儿就不贴出源代码的内容了。有兴趣的可以自己下载查看。

栈-源代码

队列

队列与栈是很相像的数据结构,不同之处在于队列是是先进先出(FIFO:First In First Out)的。

举个例子: 火车站排队买票,先到的先买。(插队的不算),是不是很好理解了~

JavaScipt中队列的实现

队列的实现和栈很像。首先依然是构造函数:

1
2
3
4
5
6
/**
* 队列构造函数
*/
function Queue() {
var items = [];
}

队列需要有如下的方法:

  • enqueue(element(s)): 向队列尾部添加几个项
  • dequeue(): 移除队列的第一项(也就是排在最前面的项)
  • front(): 返回队列的第一个元素,也就是最新添加的那个

其余方法与队列相同

enqueue方法的实现

说明: 向队列尾部添加几个项。

实现:

1
2
3
4
5
6
7
/**
* 将元素推入队列尾部
* @param {Any} ele 要推入队列的元素
*/
this.enqueue = function(ele) {
items.push(ele);
};

dequeue方法的实现

说明: 移除队列的第一项。

实现:

1
2
3
4
5
6
7
/**
* 将队列中第一个元素弹出
* @return {Any} 返回被弹出的元素
*/
this.dequeue = function() {
return items.shift()
};

front方法的实现

说明: 返回队列的第一个元素,也就是最新添加的那个。

实现:

1
2
3
4
5
6
7
/**
* 查看队列的第一个元素
* @return {Any} 返回队列中第一个元素
*/
this.front = function() {
return items[0];
};

以上的三个方法,就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用

书上的是个击鼓传花的小游戏。原理就是循环到相应位置时,队列弹出那个元素。最后留下的就是赢家。

源代码如下:

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
/**
* 击鼓传花的小游戏
* @param {Array} nameList 参与人员列表
* @param {Number} num 在循环中要被弹出的位置
* @return {String} 返回赢家(也就是最后活下来的那个)
*/
function hotPotato(nameList, num) {
var queue = new Queue();
for (var i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
var eliminated = '';
while (queue.size() > 1) {
for (var i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(eliminated + " Get out!")
}
return queue.dequeue()
}

具体实现,有兴趣的同学可以自己下载源代码,试一试。

队列-源代码

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书,直接看算法导论或者一些数据结构的书,都是很迷糊的。后来才发现,看书从自己能看懂的开始,由浅入深才是适合自己的学习方式。

前端路漫漫,且行且歌~

寒假前端学习(2)——HTML语义化标签探析

什么是HTML语义化

HTML语义化就是根据具体内容,选择合适的标签进行代码的编写。便于开发者阅读和写出更优雅的代码,同时让搜索引擎的爬虫能更好的识别。

为什么要语义化

  1. 有利于SEO:搜索引擎的爬虫是读不懂无语义的span和div的,因此语义化标签能使爬虫抓取更多的有效信息。
  2. CSS文件读取失败的准备:万一CSS文件挂了,语义化的HTML也能呈现较好的内容结构与代码结构。
  3. 方便其它设备的解析(如屏幕阅读器、盲人阅读器、移动设备)。
  4. 便于团队开发和维护。

具体的语义化标签探析

本文主要是为了探析部分HTML标签在语义化中的差别。同时也探索HTML5新加入的语义化标签。

1. ul/ol(列表标签)

ul和ol虽然都是列表项,但是具体使用时,差别还是很大的。

A. ul(无序列表)

说明: ul的英文全称为unordered list,翻译成中文就是无序列表。表示列表中的项目。是没有先后顺序的。网页中大部分列表均为无序列表。

1
2
3
4
5
6
<ul>
<li>Lxxyx的博客</li>
<li>Lxxyx的评论</li>
<li>联系Lxxyx</li>
</ul>
<!-- 列表中的三个项目,均没有前后顺序的分别。 -->

B. ol(有序列表)

说明: ol的英文全称为ordered list,表示列表中的项目。是有先后顺序的。这一点是ol和ul的本质区别。

1
2
3
4
5
6
<ol>
<li>1. Lxxyx的第一篇文章</li>
<li>2. Lxxyx的第二篇文章</li>
<li>3. Lxxyx的第三篇文章</li>
</ol>
<!-- 列表中的三个项目,有前后顺序的分别。 -->

2. dl,dt,dd(定义列表)

说明: dl,dt,dd是自定义列表,但是使用上又与前面的ul/ol有所不同。自定义列表不仅仅是一列项目,而是项目及其注释的组合。

  1. dl: 英文意思为definition list,作用是定义列表。
  2. dt: 英文意思为defines terms,作用是定义列表中的项目。
  3. dd: 英文意思为defines description,作用是定义列表中项目的注释。

举例:

1
2
3
4
5
6
<dl>
<dt>计算机</dt>
<dd>用来计算的仪器 ... ...</dd>
<dt>显示器</dt>
<dd>以视觉方式显示信息的装置 ... ...</dd>
</dl>

效果图:

dldtdd效果图

C. b/strong , i/em(强调标签)

说明: 在HTML中,b和strong都是加粗,i和em都是斜体。但是从HTML4到HTML5中,又发生了转变。所以有必要写下来。

1. b/strong(加粗)

说明:虽然b和strong的展示效果一样,都是将字体加粗表示。但是b在HTML5中又发生了变化。

  1. b标签(bold):

HTML4的定义:
The <b> tag is for “offset text conventionally styled in bold,without conveying any extra emphasis or importance.
// 意思为b标签仅仅表示加粗,不带有任何强调的意味。(只是为了排版或者好看)



HTML5的定义:
The b element represents a span of text to which attention is being drawn for utilitarian purposes without conveying any extra importance and with no implication of an alternate voice or mood.
// 意思为表示“文体突出”文字,通俗讲就是突出不安分的文字。像概要中的关键字,产品名。或者代表强调的排版方式

2.strong标签(全称是stronger emphasis):

<strong> represents a span of text with strong importance.a <strong> tag within another <strong> tag has even more importance.
// 意思为strong标签是语气加重,更为重要的强调,如果两个strong标签嵌套还表示极度重要。strong的重要程度是要大于em标签的

总结:b仅仅只是加粗,并没有任何语义。但是strong标签则有语气加重的强调的意思。

2. i/em(斜体)

说明:就像b和strong的关系一样。i和em的对应关系也很容易理解。

  1. i标签(全称是italic):

HTML4的定义:
The <i> tag is for “text conventionally styled in italic”. There is no semantic meaning.
// HTML4意思为i标签仅仅只是将字体显示为斜体,无任何语义化意思



HTML5的定义:
The i element now represents a span of text in an alternate voice or mood, or otherwise offset from the normal prose.
// 意思为i元素现在表现为在文章中突出不同意见或语气或的一段文本,例如外语,科技术语、或者是排版用的斜体文字

  1. em(全称是emphasis):

The <em> represents a span of text with emphatic stress.
// 意思是说em有强调的意思

总结:i仅仅只是斜体显示,并没有任何语义。但是em标签则有加强的语义在内。

3.em/strong(强调标签)

说明:在上面的介绍中,已经介绍了em和strong,个中差别,看英文既能分辨。
em的全称是:emphasis,意思为强调。
strong的全称是:stronger emphasis,意思就是语气更强的强调。
总结:em和strong标签均带有强调的语义,但是strong标签所表现的强调语气要大于em的。

总结与参考链接

这一部分,查阅的文档和资料太多了,看完了html4发现html5又更改了意思,只能跑去w3c去看规范。
总结:i和b在Html5中被赋予语义,不同于html4。em和strong的差别在于强调的程度。

参考链接:

Using <b> and <i> elements
HTML5: The Semantic Difference Between Bold and Strong

总结

暂时总结的就这么多了,重点在于b/strong , i/em几个标签的区别。也是目前前端学习中的盲点。
前两天看到一句话:

“很多人非常努力的学习JavaScript,认为学好了JavaScript就是一切。但是忽略了JavaScript其实是一门’胶水语言’的本质,它是用来粘合HTML和CSS的。”

看到这句话后,决定在寒假认真学习HTML与CSS。这些东西,虽说简单,但写好也很难。比如说最近学习的Sass,PS切图等。无论哪个,都属于技术盲点。

因为经验尚浅,所以如果有出错的地方,希望各位能帮忙指正。
最后附上本人博客地址和原文链接,希望能与各位多多交流。

Lxxyx的前端乐园
原文链接:寒假前端学习(2)——HTML语义化标签探析

寒假前端学习(1)——HTML meta标签总结与属性的使用介绍

之前学习前端中,对meta标签的了解仅仅只是这一句。

1
<meta charset="UTF-8">

但是打开任意的网站,其head标签内都有一列的meta标签。比如我博客的。
Lxxyx博客的meta标签

但是自己却很不熟悉,于是把meta标签加入了寒假学习计划的最前方。

简介

在查阅w3school中,第一句话中的“元数据”就让我开始了Google之旅。然后很顺利的在英文版的w3school找到了想要的结果。(中文w3school说的是元信息,Google和百度都没有相关的词条。但元数据在Google就有详细解释。所以这儿采用英文版W3school的解释。)

The tag provides metadata about the HTML document. Metadata will not be displayed on the page, but will be machine parsable.

不难看出,其中的关键是metadata,中文名叫元数据,是用于描述数据的数据。它不会显示在页面上,但是机器却可以识别。这么一来meta标签的作用方式就很好理解了。

用处

Meta elements are typically used to specify page description, keywords, author of the document, last modified, and other metadata.
The metadata can be used by browsers (how to display content or reload page), search engines (keywords), or other web services

这句话对meta标签用处的介绍,简洁明了。
翻译过来就是:meta常用于定义页面的说明,关键字,最后修改日期,和其它的元数据。这些元数据将服务于浏览器(如何布局或重载页面),搜索引擎和其它网络服务。

组成

meta标签共有两个属性,分别是http-equiv属性和name属性。

1. name属性

name属性主要用于描述网页,比如网页的关键词,叙述等。与之对应的属性值为content,content中的内容是对name填入类型的具体描述,便于搜索引擎抓取。
meta标签中name属性语法格式是:

1
<meta name="参数" content="具体的描述">。

其中name属性共有以下几种参数。(A-C为常用属性)

A. keywords(关键字)

说明:用于告诉搜索引擎,你网页的关键字。
举例:

1
<meta name="keywords" content="Lxxyx,博客,文科生,前端">

B. description(网站内容的描述)

说明:用于告诉搜索引擎,你网站的主要内容。
举例:

1
<meta name="description" content="文科生,热爱前端与编程。目前大二,这是我的前端博客">

C. viewport(移动端的窗口)

说明:这个概念较为复杂,具体的会在下篇博文中讲述。
这个属性常用于设计移动端网页。在用bootstrap,AmazeUI等框架时候都有用过viewport。

举例(常用范例):

1
<meta name="viewport" content="width=device-width, initial-scale=1">

D. robots(定义搜索引擎爬虫的索引方式)

说明:robots用来告诉爬虫哪些页面需要索引,哪些页面不需要索引。
content的参数有all,none,index,noindex,follow,nofollow。默认是all。

举例:

1
<meta name="robots" content="none">

具体参数如下:

1.none : 搜索引擎将忽略此网页,等价于noindex,nofollow。
2.noindex : 搜索引擎不索引此网页。
3.nofollow: 搜索引擎不继续通过此网页的链接索引搜索其它的网页。
4.all : 搜索引擎将索引此网页与继续通过此网页的链接索引,等价于index,follow。
5.index : 搜索引擎索引此网页。
6.follow : 搜索引擎继续通过此网页的链接索引搜索其它的网页。

E. author(作者)

说明:用于标注网页作者
举例:

1
<meta name="author" content="Lxxyx,841380530@qq.com">

F. generator(网页制作软件)

说明:用于标明网页是什么软件做的
举例(不知道能不能这样写):

1
<meta name="generator" content="Sublime Text3">

说明:用于标注版权信息
举例:

1
<meta name="copyright" content="Lxxyx"> //代表该网站为Lxxyx个人版权所有。

H. revisit-after(搜索引擎爬虫重访时间)

说明:如果页面不是经常更新,为了减轻搜索引擎爬虫对服务器带来的压力,可以设置一个爬虫的重访时间。如果重访时间过短,爬虫将按它们定义的默认时间来访问。
举例:

1
<meta name="revisit-after" content="7 days" >

I. renderer(双核浏览器渲染方式)

说明:renderer是为双核浏览器准备的,用于指定双核浏览器默认以何种方式渲染页面。比如说360浏览器。
举例:

1
2
3
<meta name="renderer" content="webkit"> //默认webkit内核
<meta name="renderer" content="ie-comp"> //默认IE兼容模式
<meta name="renderer" content="ie-stand"> //默认IE标准模式

2. http-equiv属性

介绍之前,先说个小插曲。看文档和博客关于http-equiv的介绍时,有这么一句。

http-equiv顾名思义,相当于http的文件头作用。

一开始看到这句话的时候,我是迷糊的。因为我看各类技术名词,都会习惯性的去记住它的英文全称。equiv的全称是”equivalent”,意思是相等,相当于。然后我脑子里出现了大大的迷惑:“HTTP相等?”

后来还准备去Segmentfault提问来着。结果在写问题的时候,突然反应出equivalent还有相当于的意思。意思就是相当于http的作用。至于文件头是哪儿出来的,估计是从其作用来分析的。我认为顾名思义并不能得出”相当于http的文件头作用”这个论断。

这个我所认为的http-equiv意思的简介。
相当于HTTP的作用,比如说定义些HTTP参数啥的。

meta标签中http-equiv属性语法格式是:

1
<meta http-equiv="参数" content="具体的描述">

其中http-equiv属性主要有以下几种参数:

A. content-Type(设定网页字符集)(推荐使用HTML5的方式)

说明:用于设定网页字符集,便于浏览器解析与渲染页面
举例:

1
2
3
<meta http-equiv="content-Type" content="text/html;charset=utf-8"> //旧的HTML,不推荐
<meta charset="utf-8"> //HTML5设定网页字符集的方式,推荐使用UTF-8

B. X-UA-Compatible(浏览器采取何种版本渲染当前页面)

说明:用于告知浏览器以何种版本来渲染页面。(一般都设置为最新模式,在各大框架中这个设置也很常见。)
举例:

1
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"/> //指定IE和Chrome使用最新版本渲染当前页面

C. cache-control(指定请求和响应遵循的缓存机制)

用法1.

说明:指导浏览器如何缓存某个响应以及缓存多长时间。这一段内容我在网上找了很久,但都没有找到满意的。
最后终于在Google Developers中发现了我想要的答案。

cache简介

举例:

1
<meta http-equiv="cache-control" content="no-cache">

共有以下几种用法:

  1. no-cache: 先发送请求,与服务器确认该资源是否被更改,如果未被更改,则使用缓存。
  2. no-store: 不允许缓存,每次都要去服务器上,下载完整的响应。(安全措施)
  3. public : 缓存所有响应,但并非必须。因为max-age也可以做到相同效果
  4. private : 只为单个用户缓存,因此不允许任何中继进行缓存。(比如说CDN就不允许缓存private的响应)
  5. maxage : 表示当前请求开始,该响应在多久内能被缓存和重用,而不去服务器重新请求。例如:max-age=60表示响应可以再缓存和重用 60 秒。

参考链接:HTTP缓存

用法2.(禁止百度自动转码)

说明:用于禁止当前页面在移动端浏览时,被百度自动转码。虽然百度的本意是好的,但是转码效果很多时候却不尽人意。所以可以在head中加入例子中的那句话,就可以避免百度自动转码了。
举例:

1
<meta http-equiv="Cache-Control" content="no-siteapp" />

D. expires(网页到期时间)

说明:用于设定网页的到期时间,过期后网页必须到服务器上重新传输。
举例:

1
<meta http-equiv="expires" content="Sunday 26 October 2016 01:00 GMT" />

E. refresh(自动刷新并指向某页面)

说明:网页将在设定的时间内,自动刷新并调向设定的网址。
举例:

1
<meta http-equiv="refresh" content="2;URL=http://www.lxxyx.win/"> //意思是2秒后跳转向我的博客

说明:如果网页过期。那么这个网页存在本地的cookies也会被自动删除。

1
2
3
<meta http-equiv="Set-Cookie" content="name, date"> //格式
<meta http-equiv="Set-Cookie" content="User=Lxxyx; path=/; expires=Sunday, 10-Jan-16 10:00:00 GMT"> //具体范例

最后

暂时总结的就这么多了,meta标签的自定义属性实在太多了。所以只去找了常用的一些,还有像Window-target这样已经基本被废弃的属性,我也没有添加。
一开始以为一两个小时就能学习完毕,结果没想到竟然花了五六个小时,各处查资料,推敲文字。敲击文字的时候,也感觉自己学习了非常多。比如基本的SEO,HTTP协议的再次理解等。

因为经验尚浅,所以如果有出错的地方,希望各位能帮忙指正。

最后附上本人博客地址和原文链接,希望能与各位多多交流。

Lxxyx的前端乐园
原文链接:寒假前端学习(1)——HTML meta标签总结

2016,寒假前端学习计划与进度

学前端大约半年有余,做项目学JS的过程也很开心。
但是前端知识算是多且杂的,很多时候自学,没有方向性。
于是寒假之前就在想,学啥好呢?

幸运的是在知乎上看到了大漠关于前端自学的回答。

后面我还经历了这样的一过程,我思考过三类问题,并且将他们列在一起:
1.哪些知识点懂了?
2.哪些知识似懂非懂?
3.哪些知识不懂?
接下来有了这样的三份清单之后,就能非常清楚自己知道自己,然后先解决第二个清单中的list,再解决第三个清单中的list。
最后建议,学习这个过程是不断渐进的,整个过程把握:多看、多想、多问和多做。这也是我自己的四多原则。如果你时间允许,多写写东西,总结自己的知识。现多看看规范。

我想做web前端,怎么学习–大漠的回答

于是按照大漠给的指引,自己做了一份自己的前端学习图(在文章最后部分)。寒假主要攻克那些似懂非懂的前端概念。学习过程中,也会把自己的所学所积累的发到博客上。

另外项目实践的话,现在自己也在做工作室内网改造的项目,还有一个自己的兴趣项目。改造学院官网。属于一次full stack的尝试。

南昌大学公共管理学院

Github的源代码

有学有练,其乐无穷。同时也希望能在大二的暑假,找到一份前端的实习。
Fighting!

寒假学习计划

进度

1.HTML meta标签部分攻克,耗时5小时左右。

文章链接:寒假前端学习(1)——HTML meta标签总结

2.HTML语义化部分攻克,耗时3小时左右。

文章链接:寒假前端学习(2)——HTML语义化标签探析

3.JavaScript数据结构与算法: 栈与队列,攻克。耗时2小时左右。

文章链接:寒假前端学习(3)——学习JavaScript数据结构与算法(一): 栈与队列

4.学习JavaScript数据结构与算法:链表,攻克。耗时4小时左右。

文章链接:寒假前端学习(4)——学习JavaScript数据结构与算法(二):链表

5.学习JavaScript数据结构与算法:集合,攻克。耗时3小时左右。

文章链接: 寒假前端学习(5)——学习JavaScript数据结构与算法(三):集合

6.学习JavaScript数据结构与算法:二叉搜索树,攻克。耗时10小时左右。

文章链接: 寒假前端学习(6)——学习JavaScript数据结构与算法(四):二叉搜索树

7.学习JavaScript之this,call,apply,理解。耗时7小时左右。

文章链接: 寒假前端学习(7)——学习JavaScript之this,call,apply

8.学习CSS浮动与清除浮动,加深理解。耗时6小时左右。

文章链接: 寒假前端学习(8)——理解CSS浮动与清除浮动

9.加深对CSS盒模型和其宽高计算的理解。耗时1小时。

文章链接: 寒假前端学习(9)——理解CSS盒模型与宽高计算

10.理解DOM事件与DOM事件流,耗时2小时。

文章链接:寒假前端学习(10)——理解DOM事件流的三个阶段

11.寒假前端学习总结

文章链接:2016,寒假前端学习总结

寒假结束

作用域三部曲之一:块级作用域

三部曲的简介

本篇文章,是介绍JavaScript中作用域部分。
自己这段时间也算是看了很多JavaScript的书,都是和作用域方面有关的。
ES6那是后话,暂时不提。这儿是ES5的情况。
考虑到内容过多。准备分为三部分来讲述。
分别是:块级作用域、IIFE与ES6 let、闭包。

第一篇文章,讲的就是块级作用域的内容。

什么是块级作用域?

在C语言,Java中,都有块级作用域的概念。举个最经典的例子。

1
2
3
4
5
for (int i = 0; i < count; ++i)
{
/* 这是C语言 */
}
printf("%d\n",i ); //出错,读取不到i的值

在循环结束后,变量i就不复存在。这就是块级作用域,变量只能在函数、循环运行是存在。一旦函数或循环运行完毕,变量就会被销毁。

原理

块级作用域的原理,是我看《大话数据结构》这本书中学习到的。
栈是一种LIFO的结构。先进后出。
以刚才的循环为例。
在运行for的时候,压栈,把for循环和对应的变量i压入栈内存。运行结束时便将栈内存弹出。里面的变量i也不复存在了。

为什么要有块级作用域

打个比方,如果一个项目有一百个人在同时开发。每个人都写了好几个循环。
如果没有块级作用域,那么在最后项目合并时候,将会有数不清的变量名冲突。比如说,100个i?
这种块级作用域中定义变量的方式,叫做局部变量。

JavaScript中的块级作用域

在JavaScript中,存在一个全局变量环境。但JavaScript的块级作用域是不完整的。
它可以有局部变量。像这样的。

1
2
3
4
5
6
7
function test() {
var i = 0;
console.log(i)
}
test();// 0
console.log(i);// error,i未被定义

这是局部变量的概念。其实非常好理解。
这个用var定义的变量。只有在函数执行的瞬间才存在,执行完毕就会被销毁。
如果不用var。直接

1
2
3
4
5
6
7
function test() {
i = 0;
console.log(i)
}
test();// i = 0
console.log(i);// i = 0

因为在函数内不用var关键字定义的变量,在函数运行后会成为全局变量。

而JavaScript没有块级作用域所暴露的问题,在循环就有体现。
假如在JavaScript运行一个for循环

1
2
3
4
for (var i = 0; i < 10; i++) {
//一些操作
}
console.log(i) // i = 10

你会发现i还会存在。此时的i,是在全局变量环境中的。
这是极其恐怖的事情,因为在当代的前端开发中,大型项目往往有很多人一起开发。但是全局变量环境只有一个。
那么也就是说,如果这样的话,项目中变量的冲突会极其严重。

那怎么解决?

这就是下一章要讲述的内容啦,会讲述JavaScript如何模仿块级作用域,同时也会讲述ES6原生实现的块级作用域。

闭包中循环部分的理解

第一个例子

1
2
3
4
5
6
7
var a = [];
for (var i = 0; i < 10; i++) {
a[i] = function () {
console.log(i);
};
}
a[6](); // 10

这是一段很经典的代码。之前一直无法理解,为什么console.log(i)的时候,i是i而不是a[i]所对应的值。

看似数组a中,每个元素都取到了相应的i

但是。数组a其实取到的是那个函数,i的话,其实是在运行的时候读取的。

如果运行a[6]();函数,那么实质上i从全局作用域中读取,此时的i已经是循环结束后的那个10了。

对此,只需稍作改造。

1
2
3
4
5
6
7
8
9
var a = [];
for (var i = 0; i < 10; i++) {
a[i] = (function(num) {
return function() {
console.log(num)
}
})(i)
}
a[6]();

我们把

1
2
3
a[i] = function () {
console.log(i);
};

改成了

1
2
3
4
5
a[i] = (function(num) {
return function() {
console.log(num)
}
})(i)

此时,循环中的i作为num的值传递给匿名立即执行函数,函数运行后返回一个函数,保持着对传进来的num的引用。十个函数便有十个闭包。

此时a[i]又等于函数。运行a[i]时,就会读取闭包所保存的变量。

第二个例子

1
2
3
4
5
6
7
8
9
10
/*
* 本意是想,每一秒输出一个i。
* 因为setTimeout的时间定位i*1000,
* 也就是1,2,3……秒时各执行一次
*/
for (var i = 0; i < 5; i++) {
setTimeout(function() {
console.log(i);
}, i * 1000);
}

本意是想,每一秒输出一个i。但却会输出5个5。

原因和上面的一样,for循环在一瞬间执行完毕。console.log(i);中的i,则会沿着原型链向上查找。

此时全局变量中的i,已经是for循环结束后的i了。

自己的解决方法

1
2
3
4
5
6
7
8
9
for (var i = 0; i < 5; i++) {
(function(num) {
return (function() {
setTimeout(function() {
console.log(num);
}, num * 1000);
})()
})(i)
}

这是一开始自己写的解决方法。。虽然能用,但是一大坨看起来很不爽。于是看了看别人写的,顿时那个汗颜啊。

1
2
3
4
5
6
7
for (var i = 0; i < 5; i++) {
(function(num) {
setTimeout(function() {
console.log(num)
}, num * 1000)
})(i)
}

自己的错误在于return了一个IIFE函数。事实上是没有必要的。循环中直接执行就行。

感想

到这儿的话,总算对闭包有所了解了。

包括之前迷迷糊糊的this值的四种状态,闭包会导致内存泄漏等问题。总算是了解了个清楚。下回写博客时候,给一起写出来。

let的基本用法,也是总算对闭包有所了解的地方

管理学与编程

为何有这个专栏?

自己是学人力资源管理出身的。算管理学下的一个分支学科。在一年多的大学生涯中,码了足够多的代码,也看了足够多的管理经典和畅销企业管理书籍。
所以总觉得管理学是个很神奇的东西。
于是开了这个栏目,准备一步一步的,把之前自己所学管理学的领悟与体会给记录下来。

管理学与编程的冲突

之前大一时候一直以为管理学与前端是不可兼容的。
就是那种要学管理,就不能学前端。学了前端,就不要学管理的感觉。认为时间有限,应该投入到一门事情上。
当时那个苦恼呀,总感觉课都不能好好上,因为在计算机科学和所学的社会科学中找不到一个平衡点。两者对立但不统一。

模块化开发与管理学

大二时候,依然会有这方面的苦恼。当时学习前端中,也遇到了个问题。模块化开发。于是在知乎上提了问。

如何学习前端模块化知识?

然后在上一节“社会调查与研究”的课程时。老师点我起来回答一个问题。问题中有A,B两种选择。当时的我认为只有A是正确答案。
于是我说:“虽然有两个选择,但我认为A就是正确答案,不会是B的。”
老师笑了笑,问我:“你确定?”
我说我很确定。
老师这回笑的更开心了。
“你怎么就没想过,答案既可以是A也可以是B,看似对立实则统一。”
老师给我说的话,让我想起了之前看过的一则故事:物理学中的“光的波粒二象性”。
既矛盾却又统一,这是大自然的哲学。

然后感觉一瞬间领悟了什么。写下了一篇笔记。因为内容多,所以图片较大,做成了链接。
图里就是当时的我,对管理学和编程的全部理解。从那一天开始,管理学和编程不再在我脑袋里打架。总算是松了一口气。

管理学与编程的灵感笔记