為什么要使用數(shù)據(jù)結(jié)構(gòu)和算法

數(shù)據(jù)結(jié)構(gòu)是對在計算機內(nèi)存中（有時在磁盤中）的數(shù)據(jù)的一種安排。包括數(shù)組、鏈表、棧、二叉樹、哈希表等。

算法是對這些結(jié)構(gòu)中的數(shù)據(jù)進行各種處理。比如，查找一條特殊的數(shù)據(jù)項或?qū)?shù)據(jù)進行排序。

舉一個簡單的索引卡的存儲問題，每張卡片上寫有某人的姓名、電話、住址等信息，可以想象成一本地址薄，那么當我們想要用計算機來處理的時候，問題來了：

●如何在計算機內(nèi)存中安放數(shù)據(jù)？

●所用算法適用于100張卡片，很好，那1000000張呢？

●所用算法能夠快速插入和刪除新的卡片嗎？

●能夠快速查找某一張卡片嗎？

●如何將卡片按照字母進行排序呢？

事實上，大多數(shù)程序比地址簿要復雜得多，想象一下航班預訂系統(tǒng)的數(shù)據(jù)庫，存儲了旅客和航班的各種信息，需要許多數(shù)據(jù)結(jié)構(gòu)組成。如果您很清楚這些問題，那么請您對我的博文給出寶貴意見，如果不清楚，那么在我的博文中可以給您一些適當?shù)闹敢?/p>

隨著NodeJs技術(shù)的發(fā)展，可以在服務(wù)器端使用javascript，控制MongoDB進行持久化數(shù)據(jù)存儲。這就需要一些復雜的數(shù)據(jù)結(jié)構(gòu)和算法來提高程序的性能，僅僅使用數(shù)組和for循環(huán)來處理數(shù)據(jù)是遠遠不夠的。

數(shù)據(jù)結(jié)構(gòu)概述

---

數(shù)據(jù)結(jié)構(gòu)	優(yōu)點	缺點
數(shù)組	插入快，如果知道下標，可以非?？斓拇嫒?/td>	查找慢，刪除慢，大小固定
有序數(shù)組	比無序數(shù)組查找快	刪除和插入慢，大小固定
棧	提供“后進先出”的存取方式	存取其他項很慢
隊列	提供“先進先出”的存取方式	存取其他項很慢
鏈表	插入快，刪除快	查找慢
二叉樹	如果樹保持平衡，查找、插入、刪除都很快	刪除算法比較復雜
紅-黑樹	樹總是平衡的，查找、插入、刪除都很快	算法比較復雜
2-3-4樹	對磁盤存儲有用，樹總是平衡的，查找、插入、刪除都很快	算法比較復雜
哈希表	插入快，如果關(guān)鍵字已知則存取極快	刪除慢，如果不知道關(guān)鍵字則存取很慢，對存儲空間使用不充分
堆	插入、刪除快，對最大數(shù)據(jù)項的存取很快	對其他數(shù)據(jù)項存取慢
圖	對現(xiàn)實世界建模	有些算法慢且復雜

算法概述

對大多數(shù)數(shù)據(jù)結(jié)構(gòu)來說，都需要知道如何：

●插入一條新的數(shù)據(jù)項

●查找某一個特定的數(shù)據(jù)項

●刪除某一個特定的數(shù)據(jù)項

●遍歷某一數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)項

●排序

另外，遞歸的概念在設(shè)計有些算法時，也是十分重要的。

javascript面向?qū)ο?a target="_blank">編程

博文中的數(shù)據(jù)結(jié)構(gòu)均被實現(xiàn)為對象，本節(jié)是為了給那些還沒有接觸過面向?qū)ο缶幊痰淖x者準備的，但是，短短的一節(jié)并不能涵蓋所有面向?qū)ο缶幊痰乃枷耄瑑H僅是讓讀者能夠明白博文中的代碼示例。

Javascript是一種基于對象的語言，但是，又不是一種真正意義上的面向?qū)ο蟮恼Z言，因為沒有class（類）的語法。

一、創(chuàng)建對象

創(chuàng)建對象就是把屬性（property）和方法（method）封裝成一個對象，或者從原型對象中實例化一個對象。

下面以實例化小狗對象為例，小狗具有名字和品種兩個屬性。

1、原始模式

var dog1 = {};

dog1.name = '二牛';

dog1.variety = '牛頭梗';

var dog2 = {};

dog2.name = '二狗';

dog2.variety = '哈士奇';

這樣封裝對象雖然簡單，但是有兩個缺點，一是如果要創(chuàng)建多個實例的話，寫起來會比較麻煩，二是這種寫法并不能看出實例和原型之間有什么關(guān)系。

對原始模式進行改進，

function Dog(name, variety) {

return {

name: name,

variety: variety

};

}

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

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

改進后解決了代碼重復的問題，但是dog1和dog2之間并沒有內(nèi)在聯(lián)系，不是來自于同一個原型對象。

2、構(gòu)造函數(shù)模式

構(gòu)造函數(shù)，是內(nèi)部使用了this的函數(shù)。通過new構(gòu)造函數(shù)就能生成對象實例，并且this變量會綁定在實例對象上。使用構(gòu)造函數(shù)可以解決從原型對象構(gòu)建實例的問題。

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

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

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

print(dog1.name); // 二牛

print(dog2.name); // 二狗

驗證實例對象與原型對象之間的關(guān)系：

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

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

print(dog1 instanceof Dog); // true

print(dog2 instanceof Dog); // true

這樣看來構(gòu)造函數(shù)模式解決了原始模式的缺點，但是它自己又引入了新的缺點，就是有些時候存在浪費內(nèi)存的問題。比如說，我們現(xiàn)在要給小狗這個對象添加一個公共的屬性“type”（種類）和一個公共方法“bark”（吠）：

function Dog(name, variety) {

this.name = name;

this.variety = variety;

this.type = '犬科';

this.bark = function() {

print('汪汪汪');

}

}

再去實例化對象，

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

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

print(dog1.type); // 犬科

dog1.bark(); // 汪汪汪

print(dog2.type); // 犬科

dog2.bark(); // 汪汪汪

這樣看似沒有問題，那么我寫另一段代碼來看一下問題所在，

print(dog1.bark() === dog2.bark()); // false

從中我們可以看出問題，那就是對于每個實例對象而言，type屬性和bark方法都是一樣的，但是每次創(chuàng)建新的實例，都要為其分配新的內(nèi)存空間，這樣做就會降低性能，浪費空間，缺乏效率。

接下來我們就要思考怎樣讓這些所有實例對象都相同的內(nèi)容在內(nèi)存中只生成一次，并且讓所有實例的這些相同內(nèi)容都指向那個內(nèi)存地址？

3、Prototype模式

每一個構(gòu)造函數(shù)都有一個prototype屬性，指向另一個對象。這個對象的所有屬性和方法，都會被構(gòu)造函數(shù)的實例繼承?？梢岳眠@一點，把那些不變的屬性和方法，定義在prototype對象上。

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

Dog.prototype.type = '犬科';

Dog.prototype.bark = function() {

print('汪汪汪');

}

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

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

print(dog1.type); // 犬科

dog1.bark(); // 汪汪汪

print(dog2.type); // 犬科

dog2.bark(); // 汪汪汪

print(dog1.bark() === dog2.bark()); // true

這里所有實例對象的type屬性和bark方法，都指向prototype對象，都是同一個內(nèi)存地址。

二、繼承

現(xiàn)在有一個動物的構(gòu)造函數(shù)：

function Animal() {

this.feeling = 'happy';

}

有一個小狗的構(gòu)造函數(shù)：

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

以下如不對Animal和Dog對象進行重寫，則使用該代碼進行代入，示例代碼中不再重復。

1、原型鏈繼承

Dog.prototype = new Animal();

Dog.prototype.constructor = Dog;

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

print(dog.feeling); // happy

原型鏈繼承存在兩個問題：第一點是當被繼承對象中包含引用類型的屬性時，該屬性會被所有實例對象共享，示例代碼如下；

function Animal() {

this.colors = ['red', 'green', 'blue'];

}

function Dog() {

}

// 繼承Animal

Dog.prototype = new Animal();

Dog.prototype.constructor = Dog;

var dog1 = new Dog();

dog1.colors.push('black');

print(dog1.colors); // red,green,blue,black

var dog2 = new Dog();

print(dog2.colors); // red,green,blue,black

第二點是不能在不影響所有實例對象的情況下，向父級構(gòu)造函數(shù)傳遞參數(shù)，這一點不做示例，大家可以自行驗證下；

2、構(gòu)造函數(shù)繼承

function Dog(name, variety) {

Animal.apply(this, arguments);

this.name = name;

this.variety = variety;

}

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

print(dog.feeling); // happy

這是一種十分簡單的方法，使用apply或者call方法改變構(gòu)造函數(shù)作用域，將父函數(shù)的構(gòu)造函數(shù)綁定到子對象上。雖然解決了子對象向父對象傳遞參數(shù)的目的，但是借助構(gòu)造函數(shù)，方法都在構(gòu)造函數(shù)中定義，函數(shù)的復用就無從談起。

3、構(gòu)造函數(shù)和原型鏈組合繼承

利用構(gòu)造函數(shù)實現(xiàn)對實例屬性的繼承，使用原型鏈完成對原型屬性和方法的繼承，避免了原型鏈和構(gòu)造函數(shù)的缺陷。

function Animal(name) {

this.name = name;

this.colors = ['red', 'green', 'blue'];

}

Animal.prototype.sayName = function() {

print(this.name);

};

function Dog(name, age) {

// 繼承屬性

Animal.call(this, name);

this.age = age;

}

// 繼承方法

Dog.prototype = new Animal();

Dog.prototype.constructor = Dog;

Dog.prototype.sayAge = function() {

print(this.age);

}

var dog1 = new Dog('二狗', 1);

dog1.colors.push('black');

print(dog1.colors); // red,green,blue,black

dog1.sayName(); // 二狗

dog1.sayAge(); // 1

var dog2 = new Dog('二牛', 2);

print(dog2.colors); // red,green,blue

dog2.sayName(); // 二牛

dog2.sayAge(); // 2

4、YUI式繼承

由原型鏈繼承延伸而來，避免了實例對象的prototype指向同一個對象的缺點（Dog.prototype和Animal.prototype指向了同一個對象，那么任何對Dog.prototype的修改，都會反映到Animal.prototype）。讓Dog跳過Animal，直接繼承Animal.prototype，這樣省去執(zhí)行和創(chuàng)建Animal實例，提高了效率。利用一個空對象作為媒介，空對象幾乎不占用內(nèi)存，示例如下：

function Animal() {}

Animal.prototype.feeling = 'happy';

function extend(Child, Parent) {

var F = function(){};

F.prototype = Parent.prototype;

Child.prototype = new F();

Child.prototype.constructor = Child;

}

extend(Dog, Animal);

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

print(dog.feeling); // happy

5、拷貝繼承（淺拷貝和深拷貝）

把父對象的屬性和方法，全部拷貝給子對象，也能實現(xiàn)繼承。

① 淺復制

function Animal() {}

Animal.prototype.feeling = 'happy';

function extend(Child, Parent) {

var p = Parent.prototype;

var c = Child.prototype;

for (var i in p) {

c[i] = p[i];

}

}

extend(Dog, Animal);

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

print(dog.feeling); // happy

但是，這樣的拷貝有一個問題。那就是，如果父對象的屬性等于數(shù)組或另一個對象，那么實際上，子對象獲得的只是一個內(nèi)存地址，而不是真正拷貝，因此存在父對象被篡改的可能,比如在上例中適當位置添加如下代碼會發(fā)現(xiàn)：

Animal.prototype.colors = ['red', 'green', 'blue'];

Dog.colors.push('black');

print(Dog.colors); // red,green,blue,black

print(Animal.colors); // red,green,blue,black

當然，這也是jquery早期實現(xiàn)繼承的方式。

② 深復制

function Animal() {}

Animal.prototype.feeling = 'happy';

function deepCopy(Child, Parent) {

var p = Parent.prototype;

var c = Child.prototype;

for (var i in p) {

if (typeof p[i] === 'object') {

c[i] = (p[i].constructor === Array) ? [] : {};

deepCopy(p[i], c[i]);

} else {

c[i] = p[i];

}

}

}

deepCopy(Dog, Animal);

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

print(dog.feeling); // happy

深拷貝，能夠?qū)崿F(xiàn)真正意義上的數(shù)組和對象的拷貝。這時，在子對象上修改屬性（引用類型），就不會影響到父元素了。這也是目前jquery使用的繼承方式。

JavaScript數(shù)據(jù)結(jié)構(gòu)實現(xiàn)

可以下載javascript shell（進入該頁面并滾動到底部，選擇系統(tǒng)版本進行下載）使用shell交互模式編寫代碼并執(zhí)行。博文中主要利用javascript中數(shù)組和對象的特性對數(shù)據(jù)結(jié)構(gòu)和算法進行描述，在描述原理的同時，使用javascript實現(xiàn)示例代碼。只有真正明白數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，才能對其應(yīng)用自如。