JavaScript 数据结构和算法简述——前言

In 未分类 on 2015年06月29日 by TAT.李强 view: 5,147

为什么要使用数据结构和算法（程序=数据结构+算法）

数据结构是对在计算机内存中（有时在磁盘中）的数据的一种安排。包括数组、链表、栈、二叉树、哈希表等。

算法是对这些结构中的数据进行各种处理。比如，查找一条特殊的数据项或对数据进行排序。

举一个简单的索引卡的存储问题，每张卡片上写有某人的姓名、电话、住址等信息，可以想象成一本地址薄，那么当我们想要用计算机来处理的时候，问题来了：

如何在计算机内存中安放数据？
所用算法适用于 100 张卡片，很好，那 1000000 张呢？
所用算法能够快速插入和删除新的卡片吗？
能够快速查找某一张卡片吗？
如何将卡片按照字母进行排序呢？

事实上，大多数程序比地址簿要复杂得多，想象一下航班预订系统的数据库，存储了旅客和航班的各种信息，需要许多数据结构组成。如果您很清楚这些问题，那么请您对我的博文给出宝贵意见，如果不清楚，那么在我的博文中可以给您一些适当的指引。

随着 NodeJs 技术的发展，可以在服务器端使用 javascript，控制 MongoDB 进行持久化数据存储。这就需要一些复杂的数据结构和算法来提高程序的性能，仅仅使用数组和 for 循环来处理数据是远远不够的。

数据结构概述

数据结构	优点	缺点
数组	插入快，如果知道下标，可以非常快的存取	查找慢，删除慢，大小固定
有序数组	比无序数组查找快	删除和插入慢，大小固定
栈	提供 “后进先出” 的存取方式	存取其他项很慢
队列	提供 “先进先出” 的存取方式	存取其他项很慢
链表	插入快，删除快	查找慢
二叉树	如果树保持平衡，查找、插入、删除都很快	删除算法比较复杂
红-黑树	树总是平衡的，查找、插入、删除都很快	算法比较复杂
2-3-4 树	对磁盘存储有用，树总是平衡的，查找、插入、删除都很快	算法比较复杂
哈希表	插入快，如果关键字已知则存取极快	删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分
堆	插入、删除快，对最大数据项的存取很快	对其他数据项存取慢
图	对现实世界建模	有些算法慢且复杂

算法概述

对大多数数据结构来说，都需要知道如何：

插入一条新的数据项
查找某一个特定的数据项
删除某一个特定的数据项
遍历某一数据结构中的各数据项
排序

另外，递归的概念在设计有些算法时，也是十分重要的。

javascript 面向对象编程

博文中的数据结构均被实现为对象，本节是为了给那些还没有接触过面向对象编程的读者准备的，但是，短短的一节并不能涵盖所有面向对象编程的思想，仅仅是让读者能够明白博文中的代码示例。
Javascript 是一种基于对象的语言，但是，又不是一种真正意义上的面向对象的语言，因为没有 class（类）的语法。

一、创建对象

创建对象就是把属性（property）和方法（method）封装成一个对象，或者从原型对象中实例化一个对象。

下面以实例化小狗对象为例，小狗具有名字和品种两个属性。

1、原始模式

var dog1 = {};

dog1.name = '二牛';

dog1.variety = '牛头梗';

var dog2 = {};

dog2.name = '二狗';

dog2.variety = '哈士奇';

这样封装对象虽然简单，但是有两个缺点，一是如果要创建多个实例的话，写起来会比较麻烦，二是这种写法并不能看出实例和原型之间有什么关系。

对原始模式进行改进，

function Dog(name, variety) {

return {

name: name,

variety: variety

};

}

var dog1 = Dog('二牛', '牛头梗');

var dog2 = Dog('二狗', '哈士奇');

改进后解决了代码重复的问题，但是 dog1 和 dog2 之间并没有内在联系，不是来自于同一个原型对象。

2、构造函数模式

构造函数，是内部使用了 this 的函数。通过 new 构造函数就能生成对象实例，并且 this 变量会绑定在实例对象上。使用构造函数可以解决从原型对象构建实例的问题。

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

var dog1 = new Dog('二牛', '牛头梗');

var dog2 = new Dog('二狗', '哈士奇');

print(dog1.name); // 二牛

print(dog2.name); // 二狗

验证实例对象与原型对象之间的关系：

print(dog1.cunstructor === Dog); // true

print(dog2.cunstructor === Dog); // true

print(dog1 instanceof Dog); // true

print(dog2 instanceof Dog); // true

这样看来构造函数模式解决了原始模式的缺点，但是它自己又引入了新的缺点，就是有些时候存在浪费内存的问题。比如说，我们现在要给小狗这个对象添加一个公共的属性 “type”（种类）和一个公共方法 “bark”（吠）：

function Dog(name, variety) {

this.name = name;

this.variety = variety;

this.type = '犬科';

this.bark = function() {

print('汪汪汪');

}

再去实例化对象，

AlloyTeam

AlloyTeam

为什么要使用数据结构和算法（程序=数据结构+算法）

数据结构概述

算法概述

javascript 面向对象编程

一、创建对象