算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序
一、簡述
1??數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，是計算機存儲灿里、組織數(shù)據(jù)的方式。再簡單描述一下：數(shù)據(jù)結(jié)構(gòu)就是描述對象間邏輯關(guān)系的學科程腹。8 種常用數(shù)據(jù)結(jié)構(gòu)：數(shù)組匣吊、鏈表、棧寸潦、隊列缀去、圖、樹甸祭、前綴樹缕碎、哈希表。
2??數(shù)據(jù)存儲結(jié)構(gòu)
簡單的講就是數(shù)據(jù)在計算機中的存儲方式池户。常用的數(shù)據(jù)存儲方式有兩種：順序存儲咏雌，非順序存儲凡怎。順序存儲就是把數(shù)據(jù)存儲在一塊連續(xù)的存儲介質(zhì)(硬盤或內(nèi)存等)中，反之就是非順序存儲赊抖。Java 中的數(shù)組就是典型的順序存儲统倒，鏈表就是非順序存儲。數(shù)組存儲數(shù)據(jù)時會開辟出一塊連續(xù)內(nèi)存氛雪，按順序存儲房匆。鏈表則是只需要知道下一個節(jié)點存儲的位置，就能把所有的數(shù)據(jù)連起來了报亩。所以單向鏈表的最后一個節(jié)點是指向 Null 的浴鸿。
二、數(shù)組(Array)
數(shù)組是數(shù)據(jù)結(jié)構(gòu)中最簡單弦追，也是最常用的結(jié)構(gòu)岳链，很多編程語言都內(nèi)置數(shù)組。其他數(shù)據(jù)結(jié)構(gòu)劲件，比如棧和隊列都是由數(shù)組衍生出來的掸哑。下圖展示了 1 個數(shù)組，它有 4 個元素零远。每一個數(shù)組元素的位置由數(shù)字編號苗分，稱為下標或者索引(index)。大多數(shù)編程語言的數(shù)組第一個元素的下標是 0牵辣。
根據(jù)維度區(qū)分摔癣，有兩種不同的數(shù)組：
1??一維數(shù)組(如上圖所示)
2??多維數(shù)組(數(shù)組的元素為數(shù)組)
所有的數(shù)據(jù)結(jié)構(gòu)都支持幾個基本操作：讀取Get粘捎、插入Insert、刪除Delete危彩。
因為數(shù)組在存儲數(shù)據(jù)時是按順序存儲的攒磨，存儲數(shù)據(jù)的內(nèi)存也是連續(xù)的，所以它的特點就是尋址讀取數(shù)據(jù)比較容易汤徽，插入和刪除比較困難娩缰。在讀取數(shù)據(jù)時，只需要告訴數(shù)組要從哪個位置(索引)取數(shù)據(jù)就可以了谒府，數(shù)組會直接把想要的位置的數(shù)據(jù)取出來拼坎。插入和刪除比較困難是因為這些存儲數(shù)據(jù)的內(nèi)存是連續(xù)的浮毯，要插入和刪除就需要變更整個數(shù)組中的數(shù)據(jù)的位置。舉個例子：一個數(shù)組中編號0->1->2->3->4這五個內(nèi)存地址中都存了數(shù)組的數(shù)據(jù)泰鸡，現(xiàn)在需要往4中插入一個數(shù)據(jù)债蓝，那就代表著從4開始，后面的所有內(nèi)存中的數(shù)據(jù)都要往后移一個位置盛龄，相當耗時饰迹。
三、鏈表(Linked List) 線性結(jié)構(gòu)
鏈表與數(shù)組看起來非常像余舶，但是內(nèi)存分配方式啊鸭、內(nèi)部結(jié)構(gòu)和插入刪除操作方式都不一樣。鏈表是一系列節(jié)點組成的鏈欧芽，每一個節(jié)點保存了數(shù)據(jù)以及指向下一個節(jié)點的指針莉掂。鏈表頭指針指向第一個節(jié)點葛圃，如果鏈表為空千扔，則頭指針為空或者為 null。鏈表可以用來實現(xiàn)文件系統(tǒng)库正、哈希表和鄰接表曲楚。
在 Java 中創(chuàng)建鏈表的過程和創(chuàng)建數(shù)組的過程不同，不會先劃出一塊連續(xù)的內(nèi)存褥符。因為鏈表中的數(shù)據(jù)并不是連續(xù)的龙誊，鏈表在存儲數(shù)據(jù)的內(nèi)存中有兩塊區(qū)域，一塊區(qū)域用來存儲數(shù)據(jù)喷楣，一塊區(qū)域用來記錄下一個數(shù)據(jù)保存在哪里(指向下一個數(shù)據(jù)的指針)趟大。當有數(shù)據(jù)進入鏈表時候，會根據(jù)指針找到下一個存儲數(shù)據(jù)的位置铣焊，然后把數(shù)據(jù)保存起來逊朽，然后再指向下一個存儲數(shù)據(jù)的位置。這樣鏈表就把一些碎片空間利用起來了曲伊，雖然鏈表是線性表叽讳，但是并不會按線性的順序存儲數(shù)據(jù)。
由于鏈表是以這種方式保存數(shù)據(jù)坟募，所以鏈表在插入和刪除時比較容易岛蚤，讀取數(shù)據(jù)時比較麻煩。舉個例子：一個鏈表中0->1->2->3->4這五個內(nèi)存地址中都存了數(shù)據(jù)懈糯，現(xiàn)在需要往2中插入一條數(shù)據(jù)涤妒，那么只需要更改1號和2號中記錄下一個數(shù)據(jù)的位置就行了，對其他數(shù)據(jù)沒有影響赚哗。刪除一條數(shù)據(jù)與插入類似她紫，很高效铁坎。但是如果是想要在鏈表其中取出一條數(shù)據(jù)，就需要從0號開始一個一個的找犁苏，直到找到想要的那條數(shù)據(jù)為止硬萍。
鏈表分為 2 種：
- 單向鏈表
- 雙向鏈表
鏈表的基本操作
- InsertAtEnd — 在鏈表結(jié)尾插入元素
- InsertAtHead — 在鏈表開頭插入元素
- Delete — 刪除鏈表的指定元素
- DeleteAtHead — 刪除鏈表第一個元素
- Search — 在鏈表中查詢指定元素
- isEmpty — 查詢鏈表是否為空
四、棧(stack) LIFO
棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)围详，數(shù)組和鏈表都可以生成棧朴乖。當數(shù)據(jù)進入到棧時會按照規(guī)則壓入到棧的底部，再次進入的數(shù)據(jù)會壓在前一次的數(shù)據(jù)上面助赞，以此類推买羞。在取出棧中的數(shù)據(jù)的時候會先取出最上面的數(shù)據(jù)，所以是先進后出雹食。
由于數(shù)組和鏈表都可以組成棧畜普，所以操作特點就需要看棧是由數(shù)組還是鏈表生成的了，然后就會繼承相應(yīng)的操作特點群叶。最常見的操作撤回(Ctrl+Z)吃挑，就是利用棧實現(xiàn)的。原理：把之前的應(yīng)用狀態(tài)(限制個數(shù))保存到內(nèi)存中街立，最近的狀態(tài)放到第一個舶衬。
棧的基本操作
- Push — 在棧的最上方插入元素
- Pop — 返回棧最上方的元素，并將其刪除
- isEmpty — 查詢棧是否為空
- Top — 返回棧最上方的元素赎离，并不刪除
五逛犹、隊列(Queue) FIFO
隊列與棧類似，都是采用線性結(jié)構(gòu)存儲數(shù)據(jù)梁剔。它們的區(qū)別在于虽画，棧采用 LIFO 方式，而隊列采用先進先出荣病，即 FIFO(First in First Out)码撰。數(shù)組和鏈表也都可以生成隊列。當數(shù)據(jù)進入到隊列中時也是先進入的在下面后進入的在上面众雷，但是出隊列的時候是先從下面出灸拍，然后才是上面的數(shù)據(jù)出，最晚進入的隊列的砾省，最后出鸡岗。
舉個簡單的例子：可以把棧和隊列看成是兩根管子，這兩根管子是用來存儲數(shù)據(jù)的编兄，有可能是數(shù)組生成的也有可能是鏈表生成的轩性，棧的這根管子有一頭是封死的，所以像這個管子放數(shù)據(jù)只能從一個口進狠鸳，拿出數(shù)據(jù)的時候也只能從這一個口拿出來揣苏。而隊列這根管子呢兩個口都是敞開的悯嗓，一個口負責進數(shù)據(jù)，另一個口負責出數(shù)據(jù)卸察，所以從一進口先進去的數(shù)據(jù)脯厨，在出口處會先被拿出來。
隊列的基本操作
- Enqueue — 在隊列末尾插入元素
- Dequeue — 將隊列第一個元素刪除
- isEmpty — 查詢隊列是否為空
- Top — 返回隊列的第一個元素
六坑质、圖(graph)
圖由多個節(jié)點(vertex)構(gòu)成合武，節(jié)點之間闊以互相連接組成一個網(wǎng)絡(luò)。(x, y)表示一條邊(edge)涡扼，它表示節(jié)點 x 與 y 相連稼跳。邊可能會有權(quán)值(weight/cost)。
圖分為兩種:
- 無向圖
- 有向圖
在編程語言中吃沪，圖有可能有以下兩種形式表示：
- 鄰接矩陣(Adjacency Matrix)
- 鄰接表(Adjacency List)
遍歷圖有兩周算法
- 廣度優(yōu)先搜索(Breadth First Search)
- 深度優(yōu)先搜索(Depth First Search)
七汤善、樹(Tree)
樹是一個分層的數(shù)據(jù)結(jié)構(gòu)，由節(jié)點和連接節(jié)點的邊組成票彪。樹是一種特殊的圖红淡，它與圖最大的區(qū)別是沒有循環(huán)。樹被廣泛應(yīng)用在人工智能和一些復(fù)雜算法中抹镊，用來提供高效的存儲結(jié)構(gòu)锉屈。下圖是一個簡單的樹以及與樹相關(guān)的術(shù)語：
樹有很多分類：
- N 叉樹(N-ary Tree)
- 平衡樹(Balanced Tree)
- 二叉樹(Binary Tree)
- 二叉查找樹(Binary Search Tree)
- 平衡二叉樹(AVL Tree)
- 紅黑樹(Red Black Tree)
- 2-3 樹(2–3 Tree)
其中荤傲，二叉樹和二叉查找樹是最常用的樹垮耳。
八、前綴樹
前綴樹(Prefix Trees 或者 Trie)與樹類似遂黍，用于處理字符串相關(guān)的問題時非常高效终佛。它可以實現(xiàn)快速檢索，常用于字典中的單詞查詢雾家，搜索引擎的自動補全甚至 IP 路由铃彰。下圖展示了“top”, “thus”和“their”三個單詞在前綴樹中如何存儲的：
單詞是按照字母從上往下存儲，“p”, “s”和“r”節(jié)點分別表示“top”, “thus”和“their”的單詞結(jié)尾芯咧。
九牙捉、哈希表(Hash)
哈希將某個對象變換為唯一標識符，該標識符通常用一個短的隨機字母和數(shù)字組成的字符串來代表敬飒。哈闲安可以用來實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)，其中最常用的就是哈希表(hash table)无拗。哈希表通常由數(shù)組實現(xiàn)带到。哈希表的性能取決于 3 個指標：
- 哈希函數(shù)
- 哈希表的大小
- 哈希沖突處理方式
