數(shù)據(jù)結(jié)構(gòu)和算法是計算機科學中最重要的概念之一。如果您不熟悉計算機科學或編程见转，本文將為您提供有關(guān)數(shù)據(jù)結(jié)構(gòu)和算法的概述蹂析。這也是Landscape系列的第二集。
1.數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的組織和操作方式瓢娜。它試圖找到提高數(shù)據(jù)訪問效率的方法。在處理數(shù)據(jù)結(jié)構(gòu)時礼预，我們不僅關(guān)注一個數(shù)據(jù)眠砾，而且關(guān)注不同的數(shù)據(jù)集以及它們?nèi)绾我杂薪M織的方式相互關(guān)聯(lián)。
數(shù)組：數(shù)組是一種基于索引的數(shù)據(jù)結(jié)構(gòu)，這意味著每個元素都由索引引用褒颈。數(shù)組包含相同的數(shù)據(jù)類型元素柒巫。
鏈表：鏈表是一系列節(jié)點，其中每個節(jié)點都連接到其后的節(jié)點谷丸。這形成了數(shù)據(jù)存儲的鏈接堡掏。它由數(shù)據(jù)元素和對下一條記錄的引用組成。
樹：樹是由邊連接的節(jié)點的集合刨疼。每個節(jié)點指向許多節(jié)點泉唁。樹表示分層圖形形式。
二叉樹：二叉樹有1或2個子節(jié)點揩慕。它可以具有最少的零個節(jié)點亭畜，這在節(jié)點具有NULL值時發(fā)生。
二進制搜索樹：二叉搜索樹（BST）是二叉樹迎卤。左子樹包含其鍵小于節(jié)點鍵值的節(jié)點拴鸵，而右子樹包含其鍵大于或等于節(jié)點鍵值的節(jié)點。此外蜗搔，兩個子樹也是二叉搜索樹劲藐。二叉搜索樹可以有效地檢索數(shù)據(jù)。
矩陣：矩陣是一個雙維數(shù)組樟凄。它使用兩個索引行和列來存儲數(shù)據(jù)聘芜。
圖：圖包含一組節(jié)點和邊。節(jié)點也稱為頂點不同。邊緣用于連接節(jié)點厉膀。節(jié)點用于存儲和檢索數(shù)據(jù)。
棧：棧是LIFO數(shù)據(jù)結(jié)構(gòu)二拐，其中只能訪問頂層元素服鹅。數(shù)據(jù)通過推送添加，并通過pop頂部刪除百新。
隊列：隊列是FIFO數(shù)據(jù)結(jié)構(gòu)企软。在該結(jié)構(gòu)中，在一端插入新元件饭望，從另一端移除現(xiàn)有元件仗哨。
Max-Heap：堆是基于樹的數(shù)據(jù)結(jié)構(gòu)，其中樹的所有節(jié)點都按特定順序排列铅辞。最大堆是二叉樹厌漂。它是完整的。存儲在每個節(jié)點中的數(shù)據(jù)項大于或等于存儲在其子節(jié)點中的數(shù)據(jù)項斟珊。
Min-Heap： Min-heap是一個二叉樹苇倡。它是完整的。存儲在每個節(jié)點中的數(shù)據(jù)小于存儲在其子節(jié)點中的數(shù)據(jù)項。
Trie(前綴樹或字典樹)： Trie是一棵樹旨椒。在trie中晓褪，每個節(jié)點（根節(jié)點除外）存儲一個字符或一個數(shù)字。通過將trie從根節(jié)點向下遍歷到特定節(jié)點n综慎，可以形成字符或數(shù)字的公共前綴涣仿，其也由特里結(jié)構(gòu)的其他分支共享。
** 后綴樹（Suffix tree）：**后綴trie是包含給定文本的所有后綴的trie示惊。后綴特里允許特別快速地實現(xiàn)許多重要的字符串操作好港。
2. Java集合
Java集合框架是作為核心java的一部分包含的集合類型集。它提供了可以直接用于操作數(shù)據(jù)結(jié)構(gòu)的API或方法米罚，例如數(shù)組媚狰，鏈接列表，棧阔拳，隊列，集合和映射类嗤。如果掌握了java集合糊肠，它將為您節(jié)省大量時間并有助于解決復雜問題。
ArrayList： ArrayList類是List接口的可調(diào)整大小的數(shù)組實現(xiàn)遗锣。它實現(xiàn)所有可選的列表操作并允許所有元素货裹。
向量：向量與ArrayList非常相似，但Vector是同步且緩慢的精偿。它是一個遺留類弧圆，現(xiàn)在它可以與集合兼容。
String： String類用于創(chuàng)建和操作字符串笔咽。
LinkedList： LinkedList類是List和Deque接口的雙向鏈表實現(xiàn)搔预。LinkedList將其數(shù)據(jù)存儲為元素列表，并且每個元素都鏈接到其上一個和下一個元素叶组。
HashMap： HashMap是一個實現(xiàn)Map接口的集合類拯田。它需要一個哈希函數(shù)并使用hashCode（）和equals（）方法，以便分別在集合中放入和檢索元素甩十。
Hashtable： Hashtable類與HashMap類似船庇。它實現(xiàn)了Dictionary。Hashtable提供其鍵的枚舉侣监。它不允許null作為鍵或值鸭轮。請注意，由于HashMap是在稍后創(chuàng)建的橄霉，因此它是Hashtable的高級版本和改進版窃爷。Hashtable是同步的，速度較慢。HashMap比Hashtable更受歡迎吞鸭。
TreeMap： TreeMap實現(xiàn)了SortedMap接口寺董。它按其鍵的升序排序。操作的復雜性是O（logn）刻剥。
LinkedHashMap： LinkedHashMap保持插入順序遮咖。復雜性與HashMap O（1）相同。
HashSet： HashSet類實現(xiàn)Set接口造虏。不允許重復值御吞。它的元素沒有訂購。HashSet中允許使用NULL元素漓藕。
TreeSet： TreeSet使用樹結(jié)構(gòu)實現(xiàn)陶珠。TreeSet中的元素已排序。操作的復雜性是O（logn）享钞。
LinkedHashSet： LinkedHashSet維護插入順序揍诽。元素按照它們添加到Set中的相同順序進行排序。復雜性與HashSet O（1）相同栗竖。
Stack： Stack類擴展了Vector類暑脆，有五個操作來支持LIFO（后進先出）。Stack內(nèi)部有一個指針：TOP狐肢，它指的是Stack元素的頂部添吗。
PriorityQueue： PriorityQueue類是Queue的實現(xiàn)，每個元素都具有與之關(guān)聯(lián)的優(yōu)先級份名。優(yōu)先級隊列的元素根據(jù)其自然順序排序碟联，或者由隊列構(gòu)建時提供的比較器排序。
3.算法
算法是一種定義明確的過程僵腺，允許計算機解決問題鲤孵。有很多算法。在這里辰如，我列出了計算機科學中一些廣泛使用的算法：排序裤纹，搜索，重復編程和動態(tài)編程丧没。
排序：排序是一種算法鹰椒，由一系列指令組成，這些指令將數(shù)組作為輸入呕童，對數(shù)組執(zhí)行指定的操作漆际，有時稱為列表，并輸出排序的數(shù)組夺饲。簡單的排序算法是冒泡排序奸汇，選擇排序和插入排序施符。
冒泡排序：這是最簡單的排序算法。我們從數(shù)組的開頭開始擂找，如果第一個元素大于第二個元素戳吝，則交換前兩個元素。然后我們轉(zhuǎn)到下一對贯涎，依此類推听哭，不斷掃描數(shù)組，直到它被排序塘雳。O（n 2）平均值和最差值陆盘。
選擇排序：這是最直觀的，不一定有效败明。使用線性掃描找到最小元素并將其移動到前面（使用前面元素交換它）隘马。然后找到第二個最小的并移動它，再次進行線性掃描妻顶。繼續(xù)這樣做酸员，直到所有元素都到位。適合小文件讳嘱。O（n 2）平均值和最差值沸呐。
插入排序：它通過逐個移動元素對數(shù)組進行排序。每次迭代都會從輸入數(shù)據(jù)中刪除一個元素呢燥，并將其插入正在排序的列表中的正確位置。它對于較小的數(shù)據(jù)集是有效的寓娩，但對于較大的列表而言效率非常低叛氨。它比Selection Sort和Bubble Sort算法更好。O（n 2）平均值和最差值棘伴。
搜索：搜索是基于密鑰查找內(nèi)容寞埠。有線性搜索和二進制搜索。
線性搜索：線性搜索是一種在列表中查找目標值的方法焊夸。它按順序檢查列表中每個元素的目標值橙数，直到找到匹配項或者直到搜索完所有元素為止赘风。
二進制搜索：二進制搜索是一種有效的算法，用于從有序的項目列表中查找項目。它的工作原理是反復將列表中可能包含該項目的部分分成兩半; 直到你將可能的位置縮小到一個吁恍。復雜性從O（n）減少到O（logn）。
遞歸：遞歸是一種函數(shù)或算法自稱的計算機編程技術(shù)缠捌。它應包括具有終止條件的步驟睬罗。當條件滿足時，每個重復的其余部分從最后一個被調(diào)用到第一個重復處理鲁僚。通過遞歸解決的最著名的問題是因子數(shù)炊苫。
階乘數(shù)：數(shù)n的階乘是所有小于或等于n的正非零數(shù)的乘積裁厅。n的階乘由n！表示侨艾。
動態(tài)編程：動態(tài)編程是一種解決復雜問題的方法执虹，可以將其分解為更簡單的子問題集合，只需解決一次子問題唠梨，并存儲其解決方案袋励。下次出現(xiàn)相同的子問題時，可以查找先前計算的解姻成，從而節(jié)省計算時間插龄，但代價是存儲空間的適度支出。著名的動態(tài)編程問題是Fibonacci數(shù)科展。
斐波納契數(shù)：它們是一系列數(shù)字均牢，其中每個數(shù)字（斐波納契數(shù)）是前兩個數(shù)字的總和。最簡單的是系列1,1,2,3,5,8等才睹。
劃分和征服：分而治之算法通過遞歸地將問題分解為相同或相關(guān)類型的兩個或更多個子問題來工作徘跪，直到這些子問題變得足夠簡單直接解決。使用分而治之的著名問題是合并排序和快速排序琅攘。
合并排序：將數(shù)組分成兩半垮庐，對每一半進行排序，然后將它們合并在一起坞琴。這些半部分中的每一部分都應用了相同的排序算法哨查。最終，它合并了兩個單元素數(shù)組剧辐。O（nlogn）平均值和最差值寒亥。
快速排序：選取一個隨機元素并對數(shù)組進行分區(qū)，所有小于分區(qū)元素的數(shù)字都會出現(xiàn)在大于它的所有元素之前荧关。如果我們在元素周圍重復分區(qū)數(shù)組溉奕，那么數(shù)組最終將被排序。但由于分區(qū)元素不能保證為中位數(shù)忍啤，因此我們的排序可能非常慢加勤。O（nlogn）平均值，O（n 2）最差同波。
貪婪：貪婪算法做出的選擇似乎是當時最好的選擇鳄梅，即做出本地最優(yōu)選擇，希望這種選擇能夠帶來全局最優(yōu)解決方案未檩。貪婪算法解決的著名問題是霍夫曼編碼卫枝。
霍夫曼編碼：霍夫曼編碼是一種無損數(shù)據(jù)壓縮算法。其思想是為輸入字符分配可變長度代碼讹挎，分配代碼的長度基于相應字符的頻率校赤。
更多
觀看“數(shù)據(jù)結(jié)構(gòu)和算法的風景”（YouTube）視頻吆玖！
原文：https://www.lavivienpost.com/data-structures-and-algorithms/
作者： La Vivien
