目录

一、什么是数据结构

二、什么是算法

三、数组

  1.数组的基本使用

        (1).创建和初始化数组

        (2). 数组长度和遍历数组

  2.数组的常见操作

        (1).添加元素

        (2).删除元素

        (3).任意位置

  3.数组的其他操作

        (1).常见方法

        (2).数组合并

        (3).迭代方法

        (4).reduce方法

一、什么是数据结构

“数据结构（data structure）是计算机中存储、阻止数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法”                                                        ——中文维基百科

        总而言之，数据结构就是在计算机中存储和组织数据的方式。

常用数据结构如下图所示：

        常见的数据结构较多，每一种都有其对应的应用场景，不同的数据结构的不同操作性能是不同的。 有的查询性能很快，有的插入头和尾速度很快，有的做范围查找很快，有的允许元素重复，有的不允许重复等等。在开发中如何选择，要根据具体的需求来选择。

二、什么是算法

        Algorithm这个单词本意是解决问题的办法，数据结构的实现是离不开算法的。

•  一个有限指令集，每条指令的描述不依赖于语言
•  接收一些输入（有些情况下不需要输入）
• 产生输出
• 一定在有限步骤之后终止

三、数组

  1.数组的基本使用

        (1).创建和初始化数组

//创建和初始化数组
var daysOfWeek = new Array()
var daysOfWeek = new Array(7)
var daysOfWeek = new Array('Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday')

• 使用new关键字，就能简单地声明并初始化一个数组
• 用这种方式，还可以创建一个指定长度地数组
• 可以直接将数组元素作为参数传递给它的构造器
• 用new创建数组并不是最好的方式，可以使用中括号的形式

  var daysOfWeek = ['Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday']

        (2). 数组长度和遍历数组

        获取数组的长度

alert(daysOfWeek.length)

        通过下标值来遍历数组

//使用 for 遍历数组
for(var i = 0; i < daysOfWeek.length; i++){
    alert( daysOfWeek[i] )
}

//使用 foreach 遍历数组
daysOfWeek.forEach( function(value) {
    alert(value)
})

  2.数组的常见操作

        数组的常见操作有：添加元素、删除元素、修改元素、获取元素

        (1).添加元素

        假设有一个数组为:numbers，初始化这个数组

var numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

       添加一个元素到数组的最后位置：

//方式一
numbers[numbers.length] = 10

//方式二
numbers.push(11)
numbers.push(12, 13)
alert(numbers)

        在数组首位插入一个元素

//在数组首位插入一个元素
for(var i = numbers.length; i > 0; i--){
    numbers[i] = numbers[i - 1]
}
numbers[0] = -1
alert(numbers) // -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

         上面代码的实现原理：

        上面代码的实现性能不高，在中间位置插入元素的效率比链表低

        另，在数组首位插入数据可以使用 unshift 方法

//通过unshift在首位插入数据
numbers.unshift(-2)
numbers.unshift(-4,-3)
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

        (2).删除元素

        删除数组最后的元素，可以使用pop()方法 

//删除最后的元素
numbers.pop()
alert(numbers)    //-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12

         删除首位的元素,自己实现代码：

//删除首位元素
for(var i = 0; i < numbers.length; i++){
    numbers[i] = numbers[i+1]
}
numbers.pop()
alert(numbers)

         移除首位元素可以直接使用shift方法来实现：

numbers.shift()
alert(numbers)

        (3).任意位置

        通过splice删除数据

//删除指定位置的几个元素
numbers.splice( 5,3 )
alert(numbers) //-4,-3,-2,-1,0,4,5,6,7,8,9,10,11,12,13

上面的代码会删除索引为5，6，7位置的元素，第一个参数表示索引起始的位置为5（实际上是第六个元素，因为索引是从0开始的），删除三个元素 

        使用splice来插入数据

//插入指定位置元素
numbers.splice(5,0,3,2,1)
alert(numbers)    //-4,-3,-2,-1,0,3,2,1,4,5,6,7,8,9,10,11,12,13

上面的代码会从索引为5 的位置开始插入数据，其他数据依次向后位移

第一个参数依然是索引值为5（第六个位置）

第二个参数为0时表示不是删除数据，而是插入数据

后面紧跟的是在这个位置要插入的数据，可以是其他类型的，比如字符串类型

        使用splice来修改数据

//修改指定位置的元素
numbers.splice(5,3,"a","b","c")
alert(numbers)    // -4,-3,-2,-1,0,a,b,c,4,5,6,7,8,9,10,11,12,13

上面的代码会从索引5的位置开始修改数据，修改多少个数据由第二个参数决定

第一个参数依然是索引的位置为5（第六个位置）

第二个参数是要将数组中多少个元素给替换掉，上面的代码是替换掉3个元素

后面跟着的就是要替换的元素

  3.数组的其他操作

        (1).常见方法

        (2).数组合并

        数组的合并很简单，使用concat即可（也可以直接+进行合并） 

//数组的合并
var nums1 = [1,2,3]
var nums2 = [100,200,300]
var newNums = nums1.concat(nums2)
alert(newNums)    //1,2,3,100,200,300

newNums = nums1 + nums2
alert(newNums)    //1,2,3,100,200,300

        (3).迭代方法

         every()方法

        every()方法是将数组中每一个元素传入到一个函数中，该函数返回true/false

        如果函数中每一个元素都返回true，那么结果为true，有一个为false，那么结果为false

        案例：判断一组元素中是否都包含某一个字符

//定义数组
var names = ['abc','cb','mba','dna']

//判断数组的元素是否都包含a字符
var flag = names.every(function(t){
    return t.indexOf('a') != -1
})
alert(flag)

        some() 方法

        some()方法是将数组中每一个元素传入到一个函数中，该函数返回true/false

        但是和every不同的是，一旦有一次函数返回了true，那么迭代就会结束，并且结果为true

        案例：判断数组的元素是否有包含a字符的字符

//定义数组
var names = ['abc','cb','mba','dna']

//判断数组的元素是否有包含a字符的字符
var flag = names.some(function(t){
    return t.indexOf('a') != -1
})
alert(flag)

        forEach()方法 

         forEach()方法仅仅是一种快速迭代数组的方式而已

        该方法不需要返回值

        forEach()的使用

//定义数组
var names = ['abc','cb','mba','dna']

//forEach的使用
names.forEach(function(t){
    alert(t)
})

        filter()方法

        filter()方法是一种过滤的函数

        首先会遍历数组中每一个元素传入到函数中

        函数的结果返回true，那么这个元素会被添加到最新的数组中，返回false，则忽略该元素

        最终会形成一个新的数组，该数组就是filter()方法的返回值

        案例：获取names中所有包含'a'字符的元素

//定义数组
var names = ['abc','cb','mba','dna']

//获取names中所有包含'a'字符的元素
var newNames = names.filter(function(t){
    return t.indexOf('a') != -1
})
alert(newNames)

        map()方法 

        map()方法提供的是一种映射函数

        首先会遍历数组中每一个元素传入到函数中

        元素会经过函数中的指令进行各种变换，生成新的元素，并且将新的元素返回

        最终会将返回的所有元素形成一个新的数组，该数组就是map()方法的返回值

        案例：在names中所有的元素后面拼接-abc

//定义数组
var names = ['abc','cb','mba','dna']

//在names中所有的元素后面拼接-abc
var newNames = names.map(function(t){
    return t + '-abc'
})
alert(newNames)

        (4).reduce方法

          以下是reduce方法需要的参数：

        arr.reduce(callback[,initialValue])

参数：

callback（一个在数组中每一项上调用的函数，接收四个函数）

        1.previousValue（上一次调用回调函数时的返回值，或者初始值）

        2.currentValue（当前正在处理的数组元素）

        3.currentIndex（当前正在处理的数组元素下标）

        4.array（调用reduce()方法的数组）

initialValue（可选的初始值。作为第一次调用回调函数时传给previousValue的值）

        使用for实现

//1.定义数组
var numbers = [1,2,3,4]
 
//2.for实现累加
var total = 0
for(var i = 0; i < numbers.length; i++){
    total += numbers[i]
}
alert(total) //10

         使用forEach简化for循环

                相对于for循环，forEach更符合我们的思维（遍历数组中的元素）

//3.使用forEach
var total =0
numbers.forEach(function(t){
    total += t
})
alert(total)

          使用reduce方法实现

//4.使用reduce方法
var total = numbers.reduce(function(t){
    return pre + cur
})
alert(total)

pre中每次传人的参数是不固定的,而是上次执行函数时的结果保存在了pre中

        第一次执行时,pre为0,cur为1

        第二次执行时,pre为1(0+1,上次函数执行的结果),cur为2

        第三次执行时,pre为3(1+2,上次函数执行的结果),cur为3

        第四次执行时,pre为6(3+3,上次函数执行的结果),cur为4

        当cur为4时,数组中的元素遍历完了,就直接将第四次的结果,作为reduce函数的返回值进行返回。

reduce和forEach比较其优势在哪?

reduce不需要在调用函数前先定义一个变量,只需要一个变量来接收方法最终的参数即可

reduce方法有返回值,而forEach没有。

        如果reduce方法有返回值,那么reduce方法本身就可以作为参数直接传递给另外一个需要reduce返回值的作为参数的函数,而forEach中只能先将每次函数的结果保存在一个变量,最后再将变量传入到参数中。

        这就是最近非常流行的函数式编程,也是为什么几乎每个可以使用函数式编程的语言都有reduce这个方法的原因。

关于initialvalue，其实就是第一次执行reduce中的函数时, pre的值,因为默认pre第一次执行时为0。