数据结构：对象和数组的几个简单算法

范围的和

console.log(sum(range(1, 10)));
编写一个range函数，接受两个参数：start和end，然后返回包含start到end（包括end）之间的所有数字。

接着，编写一个sum函数，接受一个数字数组，并返回所有数字之和。运行示例程序，检查一下结果是不是 55。

附加题是修改range函数，接受第 3 个可选参数，指定构建数组时的步长（step）。如果没有指定步长，构建数组时，每步增长 1，和旧函数行为一致。调用函数range(1, 10, 2)，应该返回[1, 3, 5, 7, 9]。另外确保步数值为负数时也可以正常工作，因此range(5, 2, -1)应该产生[5, 4, 3, 2]。

function range(start, end, step) {
    var step = start > end ? -1 : 1
    var arr = []
    var len = Math.abs(start - end) + 1
    for (var i = 0; i<len; i++) {
        if(i === 0) {
            arr.push(start)
        }else {
            arr.push(arr[i-1]+(step||flag))
        }
    }
    return arr
}

function sum(arr) {
    return arr.reduce(function(a, b){
        return a+b
    })
}
console.log(range(1, 10));
// → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(range(5, 2, -1));
// → [5, 4, 3, 2]
console.log(sum(range(1, 10)));
// → 55

逆转数组

数组有一个reverse方法，它可以逆转数组中元素的次序。在本题中，编写两个函数，reverseArray和reverseArrayInPlace。第一个函数reverseArray接受一个数组作为参数，返回一个新数组，并逆转新数组中的元素次序。第二个函数reverseArrayInPlace与第一个函数的功能相同，但是直接将数组作为参数进行修改来，逆转数组中的元素次序。两者都不能使用标准的reverse方法。

function reverseArray(arr) {
    var len = arr.length
    var arr2 = [].concat(arr)
    for(var i=0;i<len;i++) {
        arr2[i] = arr[len-1-i]
    }
    return arr2
}

function reverseArrayInPlace(arr) {
    var len = arr.length
    var arr2 = [].concat(arr)
    for(var i=0;i<len;i++) {
        arr[i] = arr2[len-1-i]
    }
}

console.log(reverseArray(["A", "B", "C"]));
// → ["C", "B", "A"];
let arrayValue = [1, 2, 3, 4, 5];
reverseArrayInPlace(arrayValue);
console.log(arrayValue);
// → [5, 4, 3, 2, 1]

实现列表

对象作为一个值的容器，它可以用来构建各种各样的数据结构。有一种通用的数据结构叫作列表（list）（不要与数组混淆）。列表是一种嵌套对象集合，第一个对象拥有第二个对象的引用，而第二个对象有第三个对象的引用，依此类推。

let list = {
  value: 1,
  rest: {
    value: 2,
    rest: {
      value: 3,
      rest: null
    }
  }
};

使用列表的一个好处是，它们之间可以共享相同的子列表。举个例子，如果我们新建了两个值：{value: 0，result: list}和{value: -1，result: list}（list引用了我们前面定义的绑定）。这是两个独立的列表，但它们之间却共享了同一个数据结构，该数据结构包含列表末尾的三个元素。而且我们前面定义的list仍然是包含三个元素的列表。

编写一个函数arrayToList，当给定参数[1, 2, 3]时，建立一个和示例相似的数据结构。然后编写一个listToArray函数，将列表转换成数组。再编写一个工具函数prepend，接受一个元素和一个列表，然后创建一个新的列表，将元素添加到输入列表的开头。最后编写一个函数nth，接受一个列表和一个数，并返回列表中指定位置的元素，如果该元素不存在则返回undefined。

如果你觉得这都不是什么难题，那么编写一个递归版本的nth函数。

function listToArray(list) {
    var arr = []
    var obj = list
    arr.push(obj.value)
    while (obj.rest) {
        arr.push(obj.rest.value)
        obj = obj.rest
    }
    return arr
}

function prepend(val, list) {
    return {
        value: val,
        rest: list
    }
}

function nth(list, index) {
    if (typeof parseInt(index) !== 'number') {
        throw new Error('index must be a number!')
    }
    var index = parseInt(index)
    var ret = list
    for (var i = 0; i <= index; i++) {
        if (i > 0) {
            ret = ret.rest
        }
    }
    return ret.value
}

console.log(arrayToList([10, 20]));
// → {value: 10, rest: {value: 20, rest: null}}
console.log(listToArray(arrayToList([10, 20, 30])));
// → [10, 20, 30]
console.log(prepend(10, prepend(20, null)));
// → {value: 10, rest: {value: 20, rest: null}}
console.log(nth(arrayToList([10, 20, 30]), 1));
// → 20

深层比较

==运算符可以判断对象是否相等。但有些时候，你希望比较的是对象中实际属性的值。

编写一个函数deepEqual，接受两个参数，若两个对象是同一个值或两个对象中有相同属性，且使用deepEqual比较属性值均返回true时，返回true。

为了弄清楚通过身份（使用===运算符）还是其属性比较两个值，可以使用typeof运算符。如果对两个值使用typeof均返回"object"，则说明你应该进行深层比较。但需要考虑一个例外的情况：由于历史原因，typeof null也会返回"object"。

当你需要查看对象的属性来进行比较时，Object.keys函数将非常有用。

function deepEqual(obj1, obj2){
    var flag = true
    if (Object.keys(obj1).length !== Object.keys(obj2).length) {
        return false
    }
    for(var k in obj1){
        if(typeof obj1[k] === 'object' && obj1[k] !== null) {
            flag = deepEqual(obj1[k], obj2[k])
        } else {
            if(obj1[k] !== obj2[k]) {
                flag = false
            }
        }
    }
    return flag
}

let obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → true