[TOC] ## 數據結構的存儲方式 數據結構的存儲方式只有兩種：數組（順序存儲）和鏈表（鏈式存儲） 其他數據結構都是數組與鏈表組成 - 「隊列」、「棧」這兩種數據結構既可以使用鏈表也可以使用數組實現。用數組實現，就要處理擴容縮容的問題；用鏈表實現，沒有這個問題，但需要更多的內存空間存儲節點指針。 - 「圖」的兩種表示方法，鄰接表就是鏈表，鄰接矩陣就是二維數組。鄰接矩陣判斷連通性迅速，并可以進行矩陣運算解決一些問題，但是如果圖比較稀疏的話很耗費空間。鄰接表比較節省空間，但是很多操作的效率上肯定比不過鄰接矩陣。 - 「散列表」就是通過散列函數把鍵映射到一個大數組里。而且對于解決散列沖突的方法，拉鏈法需要鏈表特性，操作簡單，但需要額外的空間存儲指針；線性探查法就需要數組特性，以便連續尋址，不需要指針的存儲空間，但操作稍微復雜些。 - 「樹」，用數組實現就是「堆」，因為「堆」是一個完全二叉樹，用數組存儲不需要節點指針，操作也比較簡單；用鏈表實現就是很常見的那種「樹」，因為不一定是完全二叉樹，所以不適合用數組存儲。為此，在這種鏈表「樹」結構之上，又衍生出各種巧妙的設計，比如二叉搜索樹、AVL 樹、紅黑樹、區間樹、B 樹等等，以應對不同的問題 ### 鏈表與數組區別 **數組**由于是緊湊連續存儲,可以隨機訪問，通過索引快速找到對應元素，而且相對節約存儲空間。但正因為連續存儲，內存空間必須一次性分配夠，所以說數組如果要擴容，需要重新分配一塊更大的空間，再把數據全部復制過去，時間復雜度 O(N)；而且你如果想在數組中間進行插入和刪除，每次必須搬移后面的所有數據以保持連續，時間復雜度 O(N)。 **鏈表**因為元素不連續，而是靠指針指向下一個元素的位置，所以不存在數組的擴容問題；如果知道某一元素的前驅和后驅，操作指針即可刪除該元素或者插入新元素，時間復雜度 O(1)。但是正因為存儲空間不連續，你無法根據一個索引算出對應元素的地址，所以不能隨機訪問；而且由于每個元素必須存儲指向前后元素位置的指針，會消耗相對更多的儲存空間。 ## 數據結構的基本操作 數據結構種類很多，但它們存在的目的都是在不同的應用場景，盡可能高效地增刪查改。 數組遍歷框架，典型的線性迭代結構 ``` void traverse(int[] arr) { for (int i = 0; i < arr.length; i++) { // 迭代訪問 arr[i] } } ``` 鏈表遍歷框架，兼具迭代和遞歸結構 ``` /* 基本的單鏈表節點 */ class ListNode { int val; ListNode next; } void traverse(ListNode head) { for (ListNode p = head; p != null; p = p.next) { // 迭代訪問 p.val } } void traverse(ListNode head) { // 遞歸訪問 head.val traverse(head.next) } ``` 二叉樹遍歷框架 ``` /* 基本的二叉樹節點 */ class TreeNode { int val; TreeNode left, right; } void traverse(TreeNode root) { traverse(root.left) traverse(root.right) } ``` N 叉樹的遍歷框架 ``` /* 基本的 N 叉樹節點 */ class TreeNode { int val; TreeNode[] children; } void traverse(TreeNode root) { for (TreeNode child : root.children) traverse(child); } ``` ### 刷題先刷二叉樹 二叉樹的題目都是一套這個框架就出來了 ``` void traverse(TreeNode root) { // 前序遍歷 traverse(root.left) // 中序遍歷 traverse(root.right) // 后序遍歷 } ``` 如:二叉樹中最大路徑和 ``` int ans = INT_MIN; int oneSideMax(TreeNode* root) { if (root == nullptr) return 0; int left = max(0, oneSideMax(root->left)); int right = max(0, oneSideMax(root->right)); ans = max(ans, left + right + root->val); return max(left, right) + root->val; } ``` 如:恢復一棵 BST ``` void traverse(TreeNode* node) { if (!node) return; traverse(node->left); if (node->val < prev->val) { s = (s == NULL) ? prev : s; t = node; } prev = node; traverse(node->right); } ```