JavaScript数据结构和算法简述——数组

为什么先讲数组


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

线性结构大致包括:

  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)),那就太爽了哈。后面我们会向这一目标靠近。

3 4 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部