TAT.李強 JavaScript 數據結構和算法簡述——前言
In 未分類 on 2015年06月29日 by view: 5,146
13

為什么要使用數據結構和算法(程序=數據結構+算法)


? ? ? ? 數據結構是對在計算機內存中(有時在磁盤中)的數據的一種安排。包括數組、鏈表、棧、二叉樹、哈希表等。

? ? ? ? 算法是對這些結構中的數據進行各種處理。比如,查找一條特殊的數據項或對數據進行排序。

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

  • 如何在計算機內存中安放數據?
  • 所用算法適用于 100 張卡片,很好,那 1000000 張呢?
  • 所用算法能夠快速插入和刪除新的卡片嗎?
  • 能夠快速查找某一張卡片嗎?
  • 如何將卡片按照字母進行排序呢?


? ? ? ? 事實上,大多數程序比地址簿要復雜得多,想象一下航班預訂系統的數據庫,存儲了旅客和航班的各種信息,需要許多數據結構組成。如果您很清楚這些問題,那么請您對我的博文給出寶貴意見,如果不清楚,那么在我的博文中可以給您一些適當的指引。

? ? ? ? 隨著 NodeJs 技術的發展,可以在服務器端使用 javascript,控制 MongoDB 進行持久化數據存儲。這就需要一些復雜的數據結構和算法來提高程序的性能,僅僅使用數組和 for 循環來處理數據是遠遠不夠的。

數據結構概述


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

算法概述


? ? ? ? 對大多數數據結構來說,都需要知道如何:

  • 插入一條新的數據項
  • 查找某一個特定的數據項
  • 刪除某一個特定的數據項
  • 遍歷某一數據結構中的各數據項
  • 排序

? ? ? ? 另外,遞歸的概念在設計有些算法時,也是十分重要的。

javascript 面向對象編程


? ? ? ? 博文中的數據結構均被實現為對象,本節是為了給那些還沒有接觸過面向對象編程的讀者準備的,但是,短短的一節并不能涵蓋所有面向對象編程的思想,僅僅是讓讀者能夠明白博文中的代碼示例。
? ? ? ? Javascript 是一種基于對象的語言,但是,又不是一種真正意義上的面向對象的語言,因為沒有 class(類)的語法。

一、創建對象

? ? ? ? 創建對象就是把屬性(property)和方法(method)封裝成一個對象,或者從原型對象中實例化一個對象。

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

? ? ? ? 1、原始模式

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

? ? ? ? 對原始模式進行改進,

? ? ? ? 改進后解決了代碼重復的問題,但是 dog1 和 dog2 之間并沒有內在聯系,不是來自于同一個原型對象。

? ? ? ? 2、構造函數模式

? ? ? ? 構造函數,是內部使用了 this 的函數。通過 new 構造函數就能生成對象實例,并且 this 變量會綁定在實例對象上。使用構造函數可以解決從原型對象構建實例的問題。

? ? ? ? 驗證實例對象與原型對象之間的關系:

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

? ? ? ? 再去實例化對象,

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

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

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

? ? ? ? 3、Prototype 模式

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

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

二、繼承

現在有一個動物的構造函數:

有一個小狗的構造函數:

以下如不對 Animal 和 Dog 對象進行重寫,則使用該代碼進行代入,示例代碼中不再重復。
1、原型鏈繼承

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

第二點是不能在不影響所有實例對象的情況下,向父級構造函數傳遞參數,這一點不做示例,大家可以自行驗證下;

2、構造函數繼承

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

3、構造函數和原型鏈組合繼承

利用構造函數實現對實例屬性的繼承,使用原型鏈完成對原型屬性和方法的繼承,避免了原型鏈和構造函數的缺陷。

4、YUI 式繼承

由原型鏈繼承延伸而來,避免了實例對象的 prototype 指向同一個對象的缺點(Dog.prototype 包含一內部指針指向 Animal.prototype,同時 Dog 的所有實例也都包含一內部指針指向 Dog.prototype,那么任何對 Dog 實例上繼承自 Animal 的屬性或方法的修改,都會反映到 Dog.prototype)。讓 Dog 跳過 Animal,直接繼承 Animal.prototype,這樣省去執行和創建 Animal 實例,提高了效率。利用一個空對象作為媒介,空對象幾乎不占用內存,示例如下:

5、拷貝繼承(淺拷貝和深拷貝)

把父對象的屬性和方法,全部拷貝給子對象,也能實現繼承。

① 淺復制

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

當然,這也是 jquery 早期實現繼承的方式。

② 深復制

深拷貝,能夠實現真正意義上的數組和對象的拷貝。這時,在子對象上修改屬性(引用類型),就不會影響到父元素了。這也是目前 jquery 使用的繼承方式。

JavaScript 數據結構實現


可以下載 javascript shell(進入該頁面并滾動到底部,選擇系統版本進行下載)使用 shell 交互模式編寫代碼并執行。博文中主要利用 javascript 中數組和對象的特性對數據結構和算法進行描述,在描述原理的同時,使用 javascript 實現示例代碼。只有真正明白數據結構的基礎,才能對其應用自如。

【未完待續 JavaScript 數據結構和算法簡述——數組】

原創文章轉載請注明:

轉載自AlloyTeam:http://www.ecomenagepro.com/2015/06/javascript-shu-ju-jie-gou-he-suan-fa-jian-shu-qian-yan/

  1. bajian 2017 年 1 月 26 日

    print(dog1.bark() === dog2.bark()); // false 是不是寫錯了,上面等同于 undefined===undefined 吧,應該是想表達:print(dog1.bark === dog2.bark); // false

  2. 美圖共賞 2016 年 4 月 24 日

    點開有驚喜:https://www.baidu.com/s?ie=utf-8

  3. 游客 2016 年 4 月 8 日

    1. 在 strict 模式下,4,5 中的 Dog 都必須先聲明,否則會報錯>>ReferenceError: Dog is not defined
    2. deepCopy 方法有錯誤,Animal.prototype.feeling 賦值為數組,dog.feeling 輸出空字符串 “”

    • 游客 2016 年 4 月 8 日

      第 2 條請忽略,print 和 console.log 的輸出不同而已

      • 游客 2016 年 4 月 8 日

        哦,還是有問題的,deepCopy 函數還是有問題的,dog.feeling1 輸出是空數組

  4. 魯國人 2015 年 9 月 18 日

    > 由原型鏈繼承延伸而來,避免了實例對象的 prototype 指向同一個對象的缺點(Dog.prototype 和 Animal.prototype 指向了同一個對象,那么任何對 Dog.prototype 的修改,都會反映到 Animal.prototype)。………YUI 繼承前面這段說的不太對,Animal 和 Dog 的 prototype 并不是一個同一個對象,之所以使用 YUI 繼承,是由于 Dog 繼承 Animal 后,實例對象和原型上有重復多余的 Animal 屬性,例如你上列的 name 和 color 會重復

    • TAT.李強

      TAT.李強 2015 年 9 月 21 日

      感謝反饋哈。首先,我這里寫的是指向同一個對象哈,不是說的就是同一個對象,也就是都會指向同一塊內存地址,這時候修改子類的屬性或者方法,結果可想而知; 其次,YUI 式繼承確實是對原型鏈繼承的一個擴展和改進,所以在介紹完原型鏈后再介紹該繼承方式,來形成對比,它避免了原型鏈繼承的兩個問題,一是 prototype 指向同一個對象的缺點,二是省去執行和創建父類實例,提高了效率,你所說的屬性會重復的問題僅僅是其中的一點優勢吧。還望指教哈。

      • 魯國人 2015 年 9 月 22 日

        ^_^! 說成同一個對象是筆誤。你的 YUI 繼承方式說的是基于上面第 “3” 種還是 第 “1” 種基礎上得改進? 不過不管哪種,指向的也不是同一個對象的,上面的那句話有待推敲啊 “(Dog.prototype 和 Animal.prototype 指向了同一個對象,那么任何對 Dog.prototype 的修改,都會反映到 Animal.prototype)”====》Dog.prototype 和 Animal.prototype 指向的并不是同一個對象。Dog.prototype === Animal.prototype 并不會相等,相等的是:Dog.prototype.__proto__ === Animal.prototype

        • TAT.李強

          TAT.李強 2015 年 9 月 23 日

          再次感謝,這里這句話確實描述有問題,我修復一下。這里原本是想對原型鏈繼承的缺點做下簡單形象的描述。首先,(Dog.prototype 和 Animal.prototype 指向了同一個對象)對于這句話,.prototype 是一個對象的原型對象,而.__proto__則是對原型對象的引用,Dog.prototype 是 Animal 的一個實例,實例都包含一個指向原型對象的內部指針,所以直接用指向代替了__proto__,造成了概念的模糊。其次,(那么任何對 Dog.prototype 的修改,都會反映到 Animal.prototype)對于這句話,原意應該是任何對 Dog 實例上繼承自 Animal 的屬性或方法的修改,都會反映到 Dog.prototype,確實表述錯誤。 ,如果博文還有其他問題希望多提寶貴意見哈,感謝。

  5. Chris 2015 年 8 月 11 日

    寫的真全面,贊!一個小問題,原型鏈繼承中所有對象實例都指向 Dog.prototype.type 不對吧?type 是值類型

    • TAT.李強

      TAT.李強 2015 年 9 月 16 日

      ? 哪里寫的 ?

  6. 燕十三 2015 年 8 月 3 日

    大贊,期待后續

  7. lixiaodong 2015 年 7 月 29 日

    寫的真好

發表評論