TAT.李強 JavaScript 數據結構和算法簡述——數組
In 未分類 on 2015年09月15日 by view: 12,229
7

為什么先講數組


數據結構可以簡單的被分為線性結構和非線性結構。

線性結構大致包括:

  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)), 那就太爽了哈。后面我們會向這一目標靠近。

原創文章轉載請注明:

轉載自AlloyTeam:http://www.ecomenagepro.com/2015/09/brief-javascript-data-structures-and-algorithms-the-array/

  1. 曾凱 2016 年 12 月 8 日

    總結得不錯

  2. 小縣 2016 年 6 月 14 日

    樓主,你確定底層是這么實現的嗎。如果真是這么實現的,那 Array.prototype.unshift() 這類從頭插入,或者刪除的,怎么實現的。感覺依照你的思路效率很低。

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

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

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

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

  5. 送福利了哦 2015 年 10 月 29 日

    [晴轉多云]

  6. jason 2015 年 9 月 16 日

    2. 數組元素的訪問 var getArrItem=array ; //獲取數組的元素值 getArrItem = “new value”; //給數組元素賦予新的值

    • TAT.李強

      TAT.李強 2015 年 9 月 16 日

      首先說博文里面這兩句代碼沒有相關性,每句代碼都是獨立的,只是介紹功能而已。再就是比如 var array = [1, 2, 3], getArrItem 拿到的是 arr 的值 2,而不是引用地址,這時候對 getArrItem 賦值不會改變原 array 的值。

發表評論