JS 数据结构与算法笔记

一、Array

• 数组是值的有序集合
• JavaScript 数组是无类型的，元素可以是任何类型
• 索引是基于0的32位数值，最大2的32次方减2
• JavaScript 数组是动态的，创建时无需声明固定大小，数组大小变化时也无需重新分配空间
• 稀疏数组（包含从0开始的不连续的数组）索引不一定连续
• 数组继承自Array.prototype中的属性
• 数组是对象的特殊形式，所以使用方括号访问数组元素如同使用方括号访问对象的属性，索引相当于整数属性
• 稀疏数组遍历时需要额外注意
• ES 5使用Array.isArray()判定是否是数组
• 字符串作为数组，除了使用字符串方法charAt(index)获取单个字符，还可以使用类似数组str[index]

//Array

//创建
var base = 0;
var array = [0, base+1, true, 3.14, {x:1, y:2}, [1, 2, 3], , "string", ]; //最后逗号不算在length中

//其他创建方式
var array1 = new Array(); //等于[]
var array2 = new Array(3); //仅仅确定3个元素，但是没有任何元素
var array3 = new Array(1, 2, 3); //显式创建
array3.length = 2 //删除掉最后一个元素

//稀疏数组
var array4 = [,,,] //相当于[undefined, undefined, undefined]
var array5 = [1,,3] //稀疏数组
var array6 = [,] //length为1，在ES5中可以自定义length为只读

console.log('------array length-----')
console.log('array.length:'+array.length)

console.log('------array for/in循环-----')
for (var index in array)
    console.log("array["+index+"]:"+array[index])

console.log('------array 单独访问-----')
console.log("array["+6+"]:"+array[6])

//数组添加
var array7 = []
array7[0] = 11;
array7.push(12, 'str')

console.log('------array7 遍历-----')
for (var index in array7)
    console.log("array7["+index+"]:"+array7[index])

//数组删除
var array8 = [1, 2, 3]
delete array8[1]

console.log('1 in array8: '+ (1 in array8))
console.log('array8.length: ' + array8.length)


//数组遍历，只谈下稀疏数组
var array9 = ['zero', , 'two']
console.log('------array9 稀疏数组遍历-----')
for (var index in array9)
    console.log("array9["+index+"]:"+array9[index])

for (var i = 0, len = array9.length; i < len; i++) {

    // console.log("array9[" + i + "]:" + array9[i])
    // array9[i].length; //在第二个元素时会报错

    if (array9[i]) //过滤掉null、undefined
        console.log(array9[i]+' length: '+array9[i].length);

}

数组测试截图

ECMAScript 3数组方法

• 定义在Array.prototype中

Array Function	Parameter	Instruction
join()	为空或者分隔符	将所有元素转为字符串，是String.split() 的逆向操作，如果参数为空，则以逗号分隔，返回字符串
reverse()	-	元素顺序颠倒，返回逆序数组
sort()	为空或者比较函数	默认以字母排序，undefined排末尾，比较函数传入两个参数，按返回值依次增大排序，返回排序后的数组
concat()	任意	合并到数组末尾，如果是多个参数或单独的数组，则依次合并，如果同时含有其他参数和数组，则数组会作为一个元素合并，返回合并好的新数组
slice()	一个参数：从此下标到结束，两个参数：从第一个下标到第二个但不含第二个下标所在的元素，负数：倒数，最后一个元素为-1	返回一个片段或子数组
splice()	参数少于等于两个：根据参数从原数组删除，返回删除的数组，第一个参数起始位置，第二个需要操作的个数，省略则到末尾	多于两个参数：在原数组从第一个参数指定的位置开始插入该参数
push()	为空或多个参数	数组作为栈进行入操作，末尾添加一个或多个参数
pop()	-	同上，出操作，删除最后一位
unshift()	为空或多个参数	同push，但从数组头部开始操作，原有元素后移
shift()	-	同pop，但从数组头部开始操作，原有元素前移
toString()	-	相当于无参的join() 方法，返回字符串，以逗号分隔，但是不包含任何数组元素值的分隔符
toLocaleString()	-	同上，本地化版

ECMAScript 5数组方法

Array Function	Parameter	Instruction
forEach()	指定函数	从头至尾遍历，为每个元素调用指定的方法，指定函数一个参数表数组元素值，三个参数则分别为数组元素、元素索引、数组本身，方法循环调用过程中如需提前终止，需要把forEach() 置于try块中
map()	指定函数	数组的元素分别传递给指定函数，函数每次的返回值组成新的数组并返回
filter()	判定函数	通过判断函数返回true或false，根据返回true的元素组成新的数组并返回
every()	判定函数	依次使用函数对数组元素进行判断，所有调用返回true则最终返回true，负责最终返回false
some()	判定函数	其中任何一个数组元素执行返回true则最终返回true，和every() 相反
reduce()	指定函数，第二个参数为空或初始值	指定函数传入前一个返回值和i个元素，依次传入，如果第二个参数为空，则第一个元素作为初始值，最终得到一个返回值，一般用于数组求和，求积等
reduceRight()	指定函数	同上，但是从右边开始
indexOf()	给定值	从头至尾搜索，返回给定值的索引，未找到返回-1
lastIndexOf()	给定值	同上，但反向搜索

二、Set

• ES6 提供的新数据结构
• 类似于数组，但成员的值唯一
• 无键名，只有键值，访问键名则返回键值

//Set 测试

const array = [1, 6, 3, 3, 9, 5, 5]

//数组转Set是自动去除重复值
const s = new Set(array)

console.log('size: '+s.size)

//forEach 循环
s.forEach((value, key) => console.log(value+' : '+key))

//Array的from方法将Set转为数组
console.log('Set转为数组：'+(Array.from(s).join()))

console.log('for...of 结合entries遍历')
for (let item of s.entries())
    console.log(item)

Set基本使用测试截图

属性

• Set.prototype.constructor 默认Set()
• Set.prototype.size

方法

• 基本操作方法

Array Function	Parameter	Instruction
add()	value	添加值，返回自身
delete()	value	删除值，返回删除结果的bool值
has()	value	判断是否存在该值，返回判断结果bool值
clear()	-	清空所有值，无返回

• 遍历方法
  keys()：返回键名的遍历器
  values()：返回键值的遍历器
  entries()：返回键值对的遍历器
  forEach()：使用回调函数遍历每个成员，同数组
  注：因Set无键名，所以键名键值相同

遍历应用

看到阮一峰总结的蛮好，拷贝过来

应用截图1
应用截图2
应用截图3

注：WeakSet 与Set 类似，但成员只能是对象

三、Map