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

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

1）什么叫算法？

算法就是計(jì)算或解決問(wèn)題的步驟。

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

區(qū)別在于，程序是以計(jì)算機(jī)能夠理解的編程語(yǔ)言編寫(xiě)的，可以在計(jì)算機(jī)上運(yùn)行，而算法是以人類(lèi)能夠理解的數(shù)學(xué)方式來(lái)描述的，用于編程之前。但，算法和編程沒(méi)有具體邊界。

3）如何選擇算法？

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

4）如何反映算法的運(yùn)行時(shí)間？

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

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

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

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

1）鏈表

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

小結(jié)：

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

拓展：

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

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

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

2）數(shù)組

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

3）棧

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

4）隊(duì)列

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

5）哈希表

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

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

6）堆

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

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

7）二叉查找樹(shù)

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

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

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

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

文章來(lái)源：www.toutiao.com/i6858491700608762380/