前端算法入門之「數據結構」

前端算法入門 -- 數據結構

1）什么叫算法？

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

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

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

3）如何選擇算法？

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

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

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

數據結構

為什么要有多種數據結構？

根據使用目的的不同，使用不同的數據類型，可以提供內存空間利用率。

1）鏈表

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

小結：

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

拓展：

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

雙向鏈表：當鏈表內部指針既可以從前一個數據指向后一個數據同時也可以從后一個元素指向前一個數據時，就形成了雙向鏈表。

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

2）數組

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

3）棧

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

4）隊列

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

5）哈希表

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

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

6）堆

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

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

7）二叉查找樹

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

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

數據結構到底選哪種要根據使用目的來確定，前端常用的為以上7種。

以上就是W3Cschool編程獅關于前端算法入門之「數據結構」的相關介紹了，希望對大家有所幫助。

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