为什么先讲数组


数据结构可以简单的被分为线性结构和非线性结构。

线性结构大致包括:

  1. 数组(连续存储);
  2. 链表(离散存储);
  3. 栈(线性结构常见应用,由链表或数组增删和改进功能实现);
  4. 队列(线性结构常见应用,由链表或数组增删和改进功能实现);

非线性结构大致包括:

  1. 树;
  2. 图;

其中,数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。由于数组十分容易懂,所以它被用来作为介绍数据结构的起点非常合适。

JavaScript 数组基础知识


在 ECMAScript 中数组是非常常用的引用类型了。ECMAScript 所定义的数组和其他语言中的数组有着很大的区别。那么首先要说的就是数组在 js 中是一种特殊的对象。

特点:

  1. 数组是一组数据的线性集合;
  2. js 数组更加类似 java 中的容器。长度可变,元素类型也可以不同;
  3. 数组的长度可以随时修改(length 属性);

常用操作方法:

  • push、pop
  • shift、unshift
  • splice、slice
  • concat、join、sort、reverse 等

JavaScript 数组操作


一、 数组方法:

1、 数组的创建

注意:虽然第三种方法创建数组指定了长度,但实际上所有情况下数组都是变长的,也就是说即使指定了长度为 5,仍然可以将元素存储在规定长度以外的,并且这时长度会随之改变。

2、 数组元素的访问

3、 数组元素的添加

4、 数组元素的删除

5、 数组的合并

6、 数组的拷贝

7、 数组元素的排序

8、 数组元素的字符串化

简单介绍了下数组各个方法的使用,也算是对 js 数组学习的一个 review 和总结,利用这些方法可以实现数组更复杂些的操作,具体大家可以自己去实践。可见,js 数组的功能很强大。

二、 数组属性

1、 length 属性

length 属性表示数组的长度,即其中元素的个数。因为数组的索引总是由 0 开始,所以一个数组的上下限分别是:0 和 length-1。和其他大多数语言不同的是,JavaScript 数组的 length 属性是可变的,这一点需要特别注意。当 length 属性被设置得更大时,整个数组的状态事实上不会发生变化,仅仅是 length 属性变大;当 length 属性被设置得比原来小时,则原先数组中索引大于或等于 length 的元素的值全部被丢失。下面是演示改变 length 属性的例子:

由上面的代码我们可以清楚的看到 length 属性的性质。但 length 对象不仅可以显式的设置,它也有可能被隐式修改。JavaScript 中可以使用一个未声明过的变量,同样,也可以使用一个未定义的数组元素(指索引超过或等于 length 的元素),这时,length 属性的值将被设置为所使用元素索引的值加 1。例如下面的代码:

代码中同样是先定义了一个包含 10 个数字的数组,可以看出其长度为 10。随后使用了索引为 15 的元素,将其赋值为 15,即 arr[15]=34,这时再输出数组的长度,得到的是 16。无论如何,对于习惯于强类型编程的开发人员来说,这是一个很令人惊讶的特性。事实上,使用 new Array() 形式创建的数组,其初始长度就是为 0,正是对其中未定义元素的操作,才使数组的长度发生变化。

综上,利用 length 属性可以方便的增加或者减少数组的容量。

2、 prototype 属性

返回对象类型原型的引用。prototype 属性是 object 共有的。

objectName.prototype

objectName 参数是 object 对象的名称。

对于数组对象,以下例子说明 prototype 属性的用途。

给数组对象添加返回数组中最大元素值的方法。要完成这一点,声明一个函数,将它加入 Array.prototype, 并使用它。

3、 constructor 属性

表示创建对象的函数。

object.constructor // object 是对象或函数的名称。

说明:constructor 属性是所有具有 prototype 的对象的成员。constructor 属性保存了对构造特定对象实例的函数的引用。

JavaScript 数组算法的 C 语言实现


使用没有指针的语言,个人觉得无法将数据结构和算法的精髓讲的出来,而且 js 底层已将数组相关算法封装好,所以这里不使用原生的 js 或者 java 等,而是使用 c 语言来实现。为了照顾没有学过指针的同学,我会尽可能的简单实现,并写好注释,画好图解,大家可以体会一下。

执行结果:

程序图解:

衡量算法的标准


需要详细了解的同学请阅读相关书籍。这里我简单介绍一下。

1、 时间复杂度

程序大概要执行的次数,而非执行的时间

通常使用大 O 表示法(含义:"order of" 大约是)来表示。比如无序数组的插入,无论数组中有多少数据项,都只需要在下一个有空的地方进行一步插入操作,那么可以说向一个无序数组中插入一个数据项的时间 T 是一个常数 K: T=K;又比如线性查找,查找特定数据项所需的比较次数平均为数据项总数的一半,因此可以说:T=KN/2,为了得到更加简洁的公式,可以将 2 并入 K,可以得到:T=KN。大 O 表示法同上面的公式比较类似,但是它省略了常数 K。当比较算法时,并不在乎具体的处理器或者编译器,真正需要比较的是对应不同的 N 值 T 是怎样变化的,而不是具体的数字。

用大 O 表示法表示数组相关算法运行时间:

算法 大 O 表示法
线性查找 O(N)
二分查找 O(logN)
无序数组的插入 O(1)
有序数组的插入 O(N)
无序数组的删除 O(N)
有序数组的删除 O(N)

注:O(1) 是优秀;O(logN) 是良好;O(N) 还可以;O(N2) 就差一些了。

2、 空间复杂度

算法执行过程中大概所占用的最大内存

3、 难易程度

写出来的算法不能只让自己看得懂,或者自己写完以后自己也看不懂了。。。

4、 健壮性

不能一用就崩溃。。。

为什么不用数组表示一切


仅用数组看似可以完成所有的工作,那么为什么不用它来进行所有的数据存储呢?

在一个无序数组中可以很快进行插入(O(1)),但是查找却要花费较多的时间 O(N)。在一个有序数组中可以查找的很快(O(logN)),但是插入却要 O(N)。对于有序和无序数组,由于平均半数的数据项需要移动,所以删除操作平均需要花费 O(N)。

如果有一种数据结构进行任何插入、删除和查找操作都很快(O(1) 或者 O(logN)), 那就太爽了哈。后面我们会向这一目标靠近。

原创文章转载请注明:

转载自AlloyTeam:http://www.alloyteam.com/2015/09/brief-javascript-data-structures-and-algorithms-the-array/

  1. 曾凯 2016 年 12 月 8 日

    总结得不错

  2. 小县 2016 年 6 月 14 日

    楼主,你确定底层是这么实现的吗。如果真是这么实现的,那 Array.prototype.unshift() 这类从头插入,或者删除的,怎么实现的。感觉依照你的思路效率很低。

  3. 美图共赏 2016 年 4 月 24 日

    点开有惊喜:https://www.baidu.com/s?ie=utf-8

  4. 美图共赏 2016 年 4 月 24 日

    点开有惊喜:https://www.baidu.com/s?ie=utf-8

  5. 送福利了哦 2015 年 10 月 29 日

    [晴转多云]

  6. jason 2015 年 9 月 16 日

    2. 数组元素的访问 var getArrItem=array ; //获取数组的元素值 getArrItem = “new value”; //给数组元素赋予新的值

    • TAT.李强

      TAT.李强 2015 年 9 月 16 日

      首先说博文里面这两句代码没有相关性,每句代码都是独立的,只是介绍功能而已。再就是比如 var array = [1, 2, 3], getArrItem 拿到的是 arr 的值 2,而不是引用地址,这时候对 getArrItem 赋值不会改变原 array 的值。

发表评论