前端算法入門之「數(shù)據(jù)結(jié)構(gòu)」

前端算法入門 -- 數(shù)據(jù)結(jié)構(gòu)

1）什么叫算法？

算法就是計算或解決問題的步驟。

2）算法和程序有什么區(qū)別？

區(qū)別在于，程序是以計算機能夠理解的編程語言編寫的，可以在計算機上運行，而算法是以人類能夠理解的數(shù)學方式來描述的，用于編程之前。但，算法和編程沒有具體邊界。

3）如何選擇算法？

同樣的問題，不同的開發(fā)者解法不同，不同的編程語言，寫法不同，為算法設立評判標準的目的在于選擇最優(yōu)標準的算法。評判算法的優(yōu)劣有兩個標準：一是從運行到計算出結(jié)果需要耗費空間的大小，另一個是從運行到計算出結(jié)果需要花費多少時間。分別稱為， 空間復雜度 、 時間復雜度 。通常，復雜度越低，耗費內(nèi)存越少，執(zhí)行越快，也更容易被人理解。一般， 最為重視的是算法的運行時間 。

4）如何反映算法的運行時間？

算法不同、設備不同、數(shù)據(jù)量不同都會導致算法時間有差異，通過理論計算出的運行時間是一個多項式，而我們需要能最直觀的了解到時間隨數(shù)據(jù)量變化的關(guān)系，常常會忽略掉非重要項，得到一個最簡單的并且最能反映運行時間趨勢的表達式，我們把：忽略掉不重要項、能最簡表示運行時間隨數(shù)據(jù)量變化關(guān)系寫成O（n）的形式，其中O是大寫，表示忽略重要項以外的內(nèi)容，讀音同order;n表示參與算法的數(shù)據(jù)量。

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

為什么要有多種數(shù)據(jù)結(jié)構(gòu)？

根據(jù)使用目的的不同，使用不同的數(shù)據(jù)類型，可以提供內(nèi)存空間利用率。

1）鏈表

鏈表是數(shù)據(jù)結(jié)構(gòu)之一，其數(shù)據(jù)呈線性排列；在內(nèi)存空間中，數(shù)據(jù)是分散存儲于內(nèi)存中的，每個數(shù)據(jù)都由兩部分組成，一部分是數(shù)據(jù)本身，另一部分是一個指針，它指向下一塊存儲空間。當對數(shù)據(jù)進行訪問時，只能順著指針指向一一往下訪問，直到找到或者訪問到末尾，如果鏈表中的數(shù)據(jù)量是n,那么，查找到一個數(shù)據(jù)，最快需要一次，最多需要查找n次；當需要在鏈表中添加或者刪除一個數(shù)據(jù)時，只需要改變其中某一個或兩個的數(shù)據(jù)指針即可，與鏈表的數(shù)據(jù)量無關(guān)，是常量級的。

小結(jié)：

鏈表數(shù)據(jù)是線性的，存儲空間是不連續(xù)的，訪問的時間復雜度為O（n）,增刪的時間復雜度為O(1)。

拓展：

循環(huán)鏈表：鏈表尾部的數(shù)據(jù)是沒有指針的，當為尾部數(shù)據(jù)添加一個指向鏈表頭部數(shù)據(jù)的指針時，鏈表指針之間就形成了環(huán)形結(jié)構(gòu)，稱為循環(huán)鏈表或環(huán)形鏈表。

雙向鏈表：當鏈表內(nèi)部指針既可以從前一個數(shù)據(jù)指向后一個數(shù)據(jù)同時也可以從后一個元素指向前一個數(shù)據(jù)時，就形成了雙向鏈表。

這里要注意：在給出定義時就說了，數(shù)據(jù)由數(shù)據(jù)體本身和指針共同組成，當指針增加時，數(shù)據(jù)需要的存儲空間也會增加，就會占用更多的內(nèi)存。同時，當指針越多，增刪數(shù)據(jù)時，需要改變的指針也就越復雜，需要改變指向的指針也越多。

2）數(shù)組

數(shù)組也是線性排列的數(shù)據(jù)結(jié)構(gòu)之一，它與鏈表不同的地方在于，數(shù)組在內(nèi)存空間的存儲是連續(xù)的。當訪問數(shù)組時，只需要根據(jù)數(shù)組索引找到對應位置即可，查找復雜度是常量級的，表示為O（1）；而當對數(shù)組進行增加時，如果在數(shù)組頭部增加，則需要先將數(shù)組擴容。然后將每一個元素都依次向后移動，這個過程復雜度是O（n）,而如果在數(shù)組尾部增加一個元素，復雜度變成了O（1），同理，刪除一個元素，尾部刪除時為O（1），頭部刪除時為O（n）。可以看出，相比于鏈表，數(shù)組雖然查詢方便了，但是操作復雜度卻高了。

3）棧

棧是一種線性數(shù)據(jù)結(jié)構(gòu)，當為棧添加一個元素時，這個元素被添加到了棧的最頂端，當取出元素時，只能單向的從最前面的位置讀取，然后才能讀取后面的元素，也就是說，最后被添加的，反而是最先被讀取的，因此，棧被稱為是后進先出（LIFO）模式，添加和刪除數(shù)據(jù)的方式也被稱為是入棧和出棧。由于棧具有的LIFO的特點，它常常被用來保存最新的數(shù)據(jù)。

4）隊列

隊列也是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，它與棧很像，都是單向的有序操作，但是，后進先出，而隊列就像排隊，先來的排在前面，后來的排在后面，屬于先進先出（FIFO）,要訪問后面的元素，只能把前面的元素都訪問完了，才能訪問到目標元素。添加和刪除隊列的操作也被稱為入隊和出隊。

5）哈希表

哈希表存儲的是以鍵值對組合的數(shù)據(jù)，一般，把鍵當做數(shù)據(jù)的標識，而把值當做數(shù)據(jù)的內(nèi)容。哈希表通常與哈希函數(shù)組合使用，在建立哈希表的過程中，需要使用哈希函數(shù)計算數(shù)據(jù)的哈希值，將其存在數(shù)組中，這樣在訪問時就可以快速使用數(shù)組的特性訪問到；如果在建立數(shù)組的時候存在多個位于同一個數(shù)組位置的值，則再次使用鏈表存儲相同的值。

哈希表的使用，加快了數(shù)組查詢的速度，在靈活性和高效性上有很大的優(yōu)勢。在編程中，關(guān)聯(lián)數(shù)組時常常會用到哈希表。

6）堆

堆是圖的一種，是二維的數(shù)據(jù)結(jié)構(gòu)，其示意可以用二位的樹狀圖表示，子節(jié)點的數(shù)據(jù)值總比父節(jié)點大。在堆中，頂端的數(shù)據(jù)始終是最小的，所以無論多少數(shù)據(jù)量，取出最小值的復雜度始終都是O（1）。另外，由于取出數(shù)據(jù)后需要將最后的數(shù)據(jù)移動到最頂端，然后一邊比較它與子節(jié)點數(shù)據(jù)的大小，一邊往下移動，所以，取出數(shù)據(jù)需要的運行時間和樹的高度成正比，假設數(shù)據(jù)量為n,根據(jù)堆的形狀特點可知，樹的高度為log2n,那么重構(gòu)樹的復雜度就是O（logn）.添加數(shù)據(jù)也一樣，在堆的最后添加數(shù)據(jù)，數(shù)據(jù)一邊比較它與父節(jié)點的大小，一邊往上移動，知道滿足堆的條件為止。

如果需要頻繁的從數(shù)據(jù)中取出最小值，那么，堆，是一種很好的選擇。

7）二叉查找樹

二叉查找樹也叫作二叉搜索樹，或二叉排序樹。是二維的圖結(jié)構(gòu)的一種。它的特點是：每個節(jié)點最多有兩個節(jié)點，分別稱為左子樹和右子樹，每一個節(jié)點上的值均大于其左子樹上的值，每個節(jié)點上的值均小于其右子樹上的值。

根據(jù)這兩個特點可知： 二叉查找樹查找最小值要往左下末端找，查找最大值要往右下末端找 。

數(shù)據(jù)結(jié)構(gòu)到底選哪種要根據(jù)使用目的來確定，前端常用的為以上7種。

以上就是W3Cschool編程獅關(guān)于前端算法入門之「數(shù)據(jù)結(jié)構(gòu)」的相關(guān)介紹了，希望對大家有所幫助。

文章來源：www.toutiao.com/i6858491700608762380/