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

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

舉一個(gè)簡(jiǎn)單的索引卡的存儲(chǔ)問(wèn)題，每張卡片上寫有某人的姓名、電話、住址等信息，可以想象成一本地址薄，那么當(dāng)我們想要用計(jì)算機(jī)來(lái)處理的時(shí)候，問(wèn)題來(lái)了：

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

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

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

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

●如何將卡片按照字母進(jìn)行排序呢？

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

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

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

算法概述

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

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

●查找某一個(gè)特定的數(shù)據(jù)項(xiàng)

●刪除某一個(gè)特定的數(shù)據(jù)項(xiàng)

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

●排序

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

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

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

Javascript是一種基于對(duì)象的語(yǔ)言，但是，又不是一種真正意義上的面向?qū)ο蟮恼Z(yǔ)言，因?yàn)闆](méi)有class（類）的語(yǔ)法。

一、創(chuàng)建對(duì)象

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

下面以實(shí)例化小狗對(duì)象為例，小狗具有名字和品種兩個(gè)屬性。

1、原始模式

var dog1 = {};

dog1.name = '二牛';

dog1.variety = '牛頭梗';

var dog2 = {};

dog2.name = '二狗';

dog2.variety = '哈士奇';

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

對(duì)原始模式進(jìn)行改進(jìn)，

function Dog(name, variety) {

return {

name: name,

variety: variety

};

}

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

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

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

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

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

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

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

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

print(dog1.name); // 二牛

print(dog2.name); // 二狗

驗(yàn)證實(shí)例對(duì)象與原型對(duì)象之間的關(guān)系：

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

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

print(dog1 instanceof Dog); // true

print(dog2 instanceof Dog); // true

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

function Dog(name, variety) {

this.name = name;

this.variety = variety;

this.type = '犬科';

this.bark = function() {

print('汪汪汪');

}

}

再去實(shí)例化對(duì)象，

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

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

print(dog1.type); // 犬科

dog1.bark(); // 汪汪汪

print(dog2.type); // 犬科

dog2.bark(); // 汪汪汪

這樣看似沒(méi)有問(wèn)題，那么我寫另一段代碼來(lái)看一下問(wèn)題所在，

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

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

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

3、Prototype模式

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

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

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

二、繼承

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

function Animal() {

this.feeling = 'happy';

}

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

function Dog(name, variety) {

this.name = name;

this.variety = variety;

}

以下如不對(duì)Animal和Dog對(duì)象進(jìn)行重寫，則使用該代碼進(jìn)行代入，示例代碼中不再重復(fù)。

1、原型鏈繼承

Dog.prototype = new Animal();

Dog.prototype.constructor = Dog;

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

print(dog.feeling); // happy

原型鏈繼承存在兩個(gè)問(wèn)題：第一點(diǎn)是當(dāng)被繼承對(duì)象中包含引用類型的屬性時(shí)，該屬性會(huì)被所有實(shí)例對(duì)象共享，示例代碼如下；

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

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

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

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

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

利用構(gòu)造函數(shù)實(shí)現(xiàn)對(duì)實(shí)例屬性的繼承，使用原型鏈完成對(duì)原型屬性和方法的繼承，避免了原型鏈和構(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式繼承

由原型鏈繼承延伸而來(lái)，避免了實(shí)例對(duì)象的prototype指向同一個(gè)對(duì)象的缺點(diǎn)（Dog.prototype和Animal.prototype指向了同一個(gè)對(duì)象，那么任何對(duì)Dog.prototype的修改，都會(huì)反映到Animal.prototype）。讓Dog跳過(guò)Animal，直接繼承Animal.prototype，這樣省去執(zhí)行和創(chuàng)建Animal實(shí)例，提高了效率。利用一個(gè)空對(duì)象作為媒介，空對(duì)象幾乎不占用內(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、拷貝繼承（淺拷貝和深拷貝）

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

① 淺復(fù)制

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

但是，這樣的拷貝有一個(gè)問(wèn)題。那就是，如果父對(duì)象的屬性等于數(shù)組或另一個(gè)對(duì)象，那么實(shí)際上，子對(duì)象獲得的只是一個(gè)內(nèi)存地址，而不是真正拷貝，因此存在父對(duì)象被篡改的可能,比如在上例中適當(dāng)位置添加如下代碼會(huì)發(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

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

② 深復(fù)制

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ù)組和對(duì)象的拷貝。這時(shí)，在子對(duì)象上修改屬性（引用類型），就不會(huì)影響到父元素了。這也是目前jquery使用的繼承方式。

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

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