|
作者：張人大
代碼效率優(yōu)化復(fù)雜度 -- 一個關(guān)于輸入數(shù)據(jù)量n的函數(shù)- 時間復(fù)雜度 -- 昂貴
- 與代碼的結(jié)構(gòu)設(shè)計有著緊密關(guān)系
- 一個順序結(jié)構(gòu)的代碼，時間復(fù)雜度是O(1), 即任務(wù)與算例個數(shù) n 無關(guān)
- 空間復(fù)雜度 -- 廉價
- 與數(shù)據(jù)結(jié)構(gòu)設(shè)計有關(guān)
數(shù)據(jù)結(jié)構(gòu) -- 考慮如何去組織計算機中一定量的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)連接時空，用空間換取時間。數(shù)據(jù)處理 -- 了解問題，明確數(shù)據(jù)操作方法，設(shè)計出更加高效的數(shù)據(jù)結(jié)構(gòu)類型- 找到需要處理的數(shù)據(jù)，計算結(jié)果，再把結(jié)果保存下來
- 把結(jié)果存到新的內(nèi)存空間中
- 把結(jié)果存到已使用的內(nèi)存空間中
- 基本操作只有三個：增，刪，查
- 增和刪可以細分為數(shù)據(jù)結(jié)構(gòu)的中間以及最后的增和刪
- 查找可以細分為按照位置條件查找和數(shù)據(jù)數(shù)值特征查找
- 所有數(shù)據(jù)處理都是這些基本操著的組合和疊加
- 只有字典類型數(shù)據(jù)結(jié)構(gòu)能在 O(1) 的時間復(fù)雜度內(nèi)完成查找動作
- 回歸問題本源，明確數(shù)據(jù)被處理的動作，來解決數(shù)據(jù)結(jié)構(gòu)的問題
想了解更多，歡迎關(guān)注我的微信公眾號：Renda_Zhang
線性表n 個具有相同特性的元素的有限序列，Linear List數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系- 即除了頭尾元素外，其它數(shù)據(jù)元素都是首尾相接的
- 這句話只適用大部分線性表，而不是全部
- 比如，循環(huán)鏈表尾的指針指向首位結(jié)點
實現(xiàn)方式- 最常用的是鏈式表達，也叫線性鏈表或鏈表
- 每個結(jié)點包括具體的數(shù)據(jù)值和指向下一個結(jié)點的指針
- 單向鏈表，循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表
- 新增和刪除為 O(1) 時間復(fù)雜度，而查找為 O(n)
- 適合數(shù)據(jù)元素個數(shù)不確定，且經(jīng)常進行新增和刪除
- 鏈表的翻轉(zhuǎn)，快慢指針的方法，是必須掌握的內(nèi)容
- 使用數(shù)組實現(xiàn)，也叫順序存儲，順序表
類別- 一般線性表，可以自由的刪除和添加結(jié)點
- 受限線性表，主要包含棧和隊列
棧和隊列是特殊的線性表，本質(zhì)上他們都可以被看作是一類基本結(jié)構(gòu)線性表案例- 鏈表的翻轉(zhuǎn)
- 快慢指針
- 查找奇數(shù)個數(shù)的鏈表的中間位置結(jié)點的數(shù)值
- 判斷鏈表是否有環(huán)
棧后進先出的（限制后的）線性表，Last In First Out, Stack.新增和刪除操作只能在這個線性表的表尾進行，即在線性表基礎(chǔ)上加了限制- 新增: 壓棧 push, which adds an element to the collection
- 刪除: 出棧 pop, which removes the most recently added element
功能上，數(shù)組或者鏈表可以代替棧，但它們靈活性過高，數(shù)據(jù)量大時有風(fēng)險棧頂和棧底是用來表示這個棧的兩個指針- 棧頂 (top) 是表尾，用來輸入數(shù)據(jù)
- 棧底 (bottom) 是表頭
棧有順序表示和鏈式表示，分別稱作順序棧和鏈棧- 順序棧
- 可以借助數(shù)組來實現(xiàn)
- 數(shù)組的首元素存在棧底，尾元素放在棧頂
- 定義指針 top 來指示棧頂元素在數(shù)組的位置
- 棧中只有一個元素，則 top = 0
- 以 top 是否為 -1 來判定是否為空棧
- 棧頂 top 需小于棧的最大容量
- 出棧操作，只需要 top - 1 即可
- 鏈式棧
- 用鏈表的方式實現(xiàn)
- 通常把棧頂放在單鏈表的頭部
- top 指針替換了鏈表原來的尾指針，去掉了頭指針
- 出棧操作，將 top 指針指向棧頂元素的 next 指針即可
- 對比棧和一般線性表
- 相同點：
- 操作原理相似
- 時間復(fù)雜度一樣
- 都依賴當前位置指針進行數(shù)據(jù)對象的操作
- 區(qū)別：棧只能新增和刪除棧頂?shù)臄?shù)據(jù)結(jié)點
棧的案例
隊列先進先出 (限制后的) 線性表, First In First Out, Queue新增和刪除操作只能分別在隊尾和隊頭進行- 先進 - 隊列的數(shù)據(jù)新增操作只能在末端進行, add
- 不允許在隊列的中間某個結(jié)點后新增數(shù)據(jù)
- 先出 - 隊列的數(shù)據(jù)刪除操作只能在始端進行, remove
- 不允許在隊列的中間某個結(jié)點后刪除數(shù)據(jù)
隊列適合面對數(shù)據(jù)處理順序非常敏感的問題- 可以確定隊列長度最大值, 建議使用循環(huán)隊列
- 無法確定隊列長度時, 應(yīng)考慮使用鏈式隊列
front 和 rear 兩個指針- 隊頭 (front), 用來刪除數(shù)據(jù)
- 隊尾 (rear), 用來增加數(shù)據(jù)
隊列有兩種存儲方式, 即順序隊列和鏈式隊列- 順序隊列
- 依賴數(shù)組來實現(xiàn)
- 數(shù)據(jù)在內(nèi)存中也是順序存儲
- 進行新增插入操作時,
- 尾指針會向后移動
- 時間復(fù)雜度為 O(1)
- 如果只刪除頭的第一個元素時
- 每次刪除都需要把整個數(shù)組前移
- 時間復(fù)雜度為 O(n)
- 使用循環(huán)隊列
- 必須有一個固定的長度
- 實現(xiàn)刪除的時間復(fù)雜度為 O(1)
- 使用 flag 來判斷隊列空或滿
- 鏈式隊列
- 依賴鏈表來實現(xiàn)
- 數(shù)據(jù)依賴每個結(jié)點的指針互聯(lián)
- 是離散存儲線性結(jié)構(gòu)
- 實際上就是尾進頭出的單鏈線性表
- 在空間上更為靈活
- 通常會增加一個頭結(jié)點
- 讓 front 指針指向頭結(jié)點
- 頭結(jié)點不存儲數(shù)據(jù), 只是輔助標識
- 當進行數(shù)據(jù)刪除時, 實際刪除的是頭結(jié)點的后繼結(jié)點
- 隊列為空時, 頭尾指針都指向頭結(jié)點
- 對比隊列和一般線性表
- 隊列繼承了線性表的優(yōu)點和不足
- 是加了限制的線性表
隊列案例- 約瑟夫環(huán) - Josephus problem
數(shù)組數(shù)組可以看成是線性表的一種推廣，它屬于另外一種基本的數(shù)據(jù)結(jié)構(gòu)數(shù)組是數(shù)據(jù)結(jié)構(gòu)中的最基本結(jié)構(gòu)- 幾乎所有的程序設(shè)計語言都把數(shù)組類型設(shè)定為固定的基礎(chǔ)變量類型。
- 可以把數(shù)組理解為一種容器，它可以用來存放若干個相同類型的數(shù)據(jù)元素。
- 例如：
- 存放的數(shù)據(jù)是整數(shù)型的數(shù)組，稱作整型數(shù)組；
- 存放的數(shù)據(jù)是字符型的數(shù)組，則稱作字符數(shù)組；
- 另外還有一類數(shù)組比較特殊，它是數(shù)組的數(shù)組，也可以叫作二維數(shù)組。
- 可以把普通的數(shù)組看成是一個向量，那么二維數(shù)組就是一個矩陣。
- 數(shù)組在內(nèi)存中是連續(xù)存放的，數(shù)組內(nèi)的數(shù)據(jù)，可以通過索引值直接取出得到。
數(shù)組的索引就是對應(yīng)數(shù)組空間- 在進行新增、刪除、查詢操作的時候，完全可以根據(jù)代表數(shù)組空間位置的索引值進行。
- 只要記錄該數(shù)組頭部的第一個數(shù)據(jù)位置，然后累加空間位置即可。
數(shù)組的基本操作具有增刪困難、查找容易的特點，可以在任意位置增刪數(shù)據(jù)，所以數(shù)組的增刪操作會更為多樣。 - 新增操作
- 若插入數(shù)據(jù)在最后，則時間復(fù)雜度為 O(1)
- 如果中間某處插入數(shù)據(jù)，則時間復(fù)雜度為 O(n)
- 刪除操作
- 在數(shù)組的最后刪除一個數(shù)據(jù)元素，則時間復(fù)雜度是 O(1)
- 在這個數(shù)組的中間某個位置刪除一條數(shù)據(jù), 時間復(fù)雜度為 O(n)
- 查找操作
- 如果只需根據(jù)索引值進行一次查找，時間復(fù)雜度是 O(1)
- 要在數(shù)組中查找一個數(shù)值滿足指定條件的數(shù)據(jù)，則時間復(fù)雜度是 O(n)。
對比數(shù)組和鏈表- 鏈表的長度是可變的，數(shù)組的長度是固定的，在申請數(shù)組的長度時就已經(jīng)在內(nèi)存中開辟了若干個空間。如果沒有引用 ArrayList 時，數(shù)組申請的空間永遠是我們在估計了數(shù)據(jù)的大小后才執(zhí)行，所以在后期維護中也相當麻煩。
- 鏈表不會根據(jù)有序位置存儲，進行插入數(shù)據(jù)元素時，可以用指針來充分利用內(nèi)存空間。數(shù)組是有序存儲的，如果想充分利用內(nèi)存的空間就只能選擇順序存儲，而且需要在不取數(shù)據(jù)、不刪除數(shù)據(jù)的情況下才能實現(xiàn)。
數(shù)組的案例
字符串由 n 個字符組成的一個有序整體（ n >= 0 ）對比字符串和線性表- 字符串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。
- 字符串的基本操作和線性表有很大差別：
- 在線性表的基本操作中，大多以“單個元素”作為操作對象；
- 在字符串的基本操作中，通常以“串的整體”作為操作對象；
- 字符串的增刪操作和數(shù)組很像，復(fù)雜度也與之一樣。但字符串的查找操作就復(fù)雜多了，它是參加面試、筆試常常被考察的內(nèi)容。
特殊的字符串- 空串，指含有零個字符的串。例如，s = ''，書面中也可以直接用 ? 表示。
- 空格串，只包含空格的串。它和空串是不一樣的，空格串中是有內(nèi)容的，只不過包含的是空格，且空格串中可以包含多個空格。例如，s = ' '，就是包含了 3 個空格的字符串。
- 子串，串中任意連續(xù)字符組成的字符串叫作該串的子串。
- 原串通常也稱為主串。
字符串的存儲結(jié)構(gòu)與線性表相同，也有順序存儲和鏈式存儲兩種- 字符串的順序存儲結(jié)構(gòu)，是用一組地址連續(xù)的存儲單元來存儲串中的字符序列，一般是用定長數(shù)組來實現(xiàn)。有些語言會在串值后面加一個不計入串長度的結(jié)束標記符，比如 \0 來表示串值的終結(jié)。
- 字符串的鏈式存儲結(jié)構(gòu)，與線性表是相似的，但由于串結(jié)構(gòu)的特殊性（結(jié)構(gòu)中的每個元素數(shù)據(jù)都是一個字符），如果也簡單地將每個鏈結(jié)點存儲為一個字符，就會造成很大的空間浪費。因此，一個結(jié)點可以考慮存放多個字符，如果最后一個結(jié)點未被占滿時，可以使用 '#' 或其他非串值字符補全。
- 每個結(jié)點設(shè)置字符數(shù)量的多少，與串的長度、可以占用的存儲空間以及程序?qū)崿F(xiàn)的功能相關(guān)。
- 除了在連接串與串操作時有一定的方便之外，不如順序存儲靈活，在性能方面也不如順序存儲結(jié)構(gòu)好。
字符串的基本操作- 新增操作
- 和數(shù)組非常相似，都牽涉對插入字符串之后字符的挪移操作，所以時間復(fù)雜度是 O(n)。
- 對于特殊的插入操作時間復(fù)雜度也可以降低為 O(1)。例如，在 s1 的最后插入 s2，也叫作字符串的連接。
- 刪除操作
- 和數(shù)組同樣非常相似，也可能會牽涉刪除字符串后字符的挪移操作，所以時間復(fù)雜度是 O(n)。
- 對于特殊的刪除操作時間復(fù)雜度也可以降低為 O(1)。例如，在 s1 的最后刪除若干個字符，不牽涉任何字符的挪移。
- 查找操作
- 子串查找（字符串匹配）
- 在字符串 A 中查找字符串 B，則 A 就是主串，B 就是模式串。
- 主串的長度記為 n，模式串長度記為 m，則n>m。
- 字符串匹配算法的時間復(fù)雜度就是 n 和 m 的函數(shù)。
字符串匹配算法的案例
樹和二叉樹樹 -- Tree- 樹結(jié)構(gòu)在存在“一對多”的數(shù)據(jù)關(guān)系中，可被高頻使用，這也是它區(qū)別于鏈表系列數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵點。
- 樹是由結(jié)點和邊組成的，不存在環(huán)的一種數(shù)據(jù)結(jié)構(gòu)。
- 樹滿足遞歸定義的特性。如果一個數(shù)據(jù)結(jié)構(gòu)是樹結(jié)構(gòu)，那么剔除掉根結(jié)點后，得到的若干個子結(jié)構(gòu)也是樹，通常稱作子樹。
- 樹的結(jié)點的層次從根結(jié)點算起，根為第一層，根的“孩子”為第二層，根的“孩子”的“孩子”為第三層，依此類推。
- 樹中結(jié)點的最大層次數(shù)，就是這棵樹的樹深（稱為深度，也稱為高度）。
二叉樹 -- Binary Tree二叉樹每個結(jié)點最多有兩個子結(jié)點，分別稱作左子結(jié)點和右子結(jié)點。二叉樹中兩個特殊的類型- 滿二叉樹，定義為除了葉子結(jié)點外，所有結(jié)點都有 2 個子結(jié)點。
- 完全二叉樹，定義為除了最后一層以外，其他層的結(jié)點個數(shù)都達到最大，并且最后一層的葉子結(jié)點都靠左排列。它方便了順序存儲法的存儲方式。
存儲二叉樹的兩種辦法- 鏈式存儲法，也就是像鏈表一樣，每個結(jié)點有三個字段，一個存儲數(shù)據(jù)，另外兩個分別存放指向左右子結(jié)點的指針。
- 順序存儲法，就是按照規(guī)律把結(jié)點存放在數(shù)組里。如圖所示。
樹的基本操作遍歷- 前序遍歷，對樹中的任意結(jié)點來說，先打印這個結(jié)點，然后前序遍歷它的左子樹，最后前序遍歷它的右子樹。 public static void preOrderTraverse(Node node) { if (node == null) return; System.out.print(node.data + ' '); preOrderTraverse(node.left); preOrderTraverse(node.right); }
- 中序遍歷，對樹中的任意結(jié)點來說，先中序遍歷它的左子樹，然后打印這個結(jié)點，最后中序遍歷它的右子樹。 public static void inOrderTraverse(Node node) { if (node == null) return; inOrderTraverse(node.left); System.out.print(node.data + ' '); inOrderTraverse(node.right); }
- 后序遍歷，對樹中的任意結(jié)點來說，先后序遍歷它的左子樹，然后后序遍歷它的右子樹，最后打印它本身。 public static void postOrderTraverse(Node node) { if (node == null) return; postOrderTraverse(node.left); postOrderTraverse(node.right); System.out.print(node.data + ' '); }
二叉樹的增刪查操作很普通，時間復(fù)雜度與鏈表并沒有太多差別二叉查找樹 -- Binary Search Tree, BST特性- 在二叉查找樹中的任意一個結(jié)點，其左子樹中的每個結(jié)點的值，都要小于這個結(jié)點的值。
- 在二叉查找樹中的任意一個結(jié)點，其右子樹中每個結(jié)點的值，都要大于這個結(jié)點的值。
- 在二叉查找樹中，會盡可能規(guī)避兩個結(jié)點數(shù)值相等的情況。
- 對二叉查找樹進行中序遍歷，就可以輸出一個從小到大的有序數(shù)據(jù)隊列。
查找操作 -- 利用了“二分查找”，所消耗的時間復(fù)雜度為 O(logn)。- 首先判斷根結(jié)點是否等于要查找的數(shù)據(jù)，如果是就返回。
- 如果根結(jié)點大于要查找的數(shù)據(jù)，就在左子樹中遞歸執(zhí)行查找動作，直到葉子結(jié)點。
- 如果根結(jié)點小于要查找的數(shù)據(jù)，就在右子樹中遞歸執(zhí)行查找動作，直到葉子結(jié)點。
插入操作- 插入操作很簡單。從根結(jié)點開始，如果要插入的數(shù)據(jù)比根結(jié)點的數(shù)據(jù)大，且根結(jié)點的右子結(jié)點不為空，則在根結(jié)點的右子樹中繼續(xù)嘗試執(zhí)行插入操作。直到找到為空的子結(jié)點執(zhí)行插入動作。
- 二叉查找樹插入數(shù)據(jù)的時間復(fù)雜度是 O(logn)。這里的時間復(fù)雜度更多是消耗在了遍歷數(shù)據(jù)去找到查找位置上，真正執(zhí)行插入動作的時間復(fù)雜度仍然是 O(1)。
刪除操作- 情況一，如果要刪除的結(jié)點是某個葉子結(jié)點，則直接刪除，將其父結(jié)點指針指向 null 即可。
- 情況二，如果要刪除的結(jié)點只有一個子結(jié)點，只需要將其父結(jié)點指向的子結(jié)點的指針換成其子結(jié)點的指針即可。
- 情況三，如果要刪除的結(jié)點有兩個子結(jié)點，則有兩種可行的操作方式：
- 第一種，找到這個結(jié)點的左子樹中最大的結(jié)點，替換要刪除的結(jié)點。
- 第二種，找到這個結(jié)點的右子樹中最小的結(jié)點，替換要刪除的結(jié)點。
樹的案例字典樹 -- Dictionary Tree- 第一，根結(jié)點不包含字符；
- 第二，除根結(jié)點外每一個結(jié)點都只包含一個字符；
- 第三，從根結(jié)點到某一葉子結(jié)點，路徑上經(jīng)過的字符連接起來，即為集合中的某個字符串。
哈希表哈希表 -- Hash Table, 也叫作散列表。哈希表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它與數(shù)組、鏈表以及樹等我們之前學(xué)過的數(shù)據(jù)結(jié)構(gòu)相比，有很明顯的區(qū)別。- 線性表中的棧和隊列對增刪有嚴格要求，它們會更關(guān)注數(shù)據(jù)的順序。
- 數(shù)組和字符串需要保持數(shù)據(jù)類型的統(tǒng)一，并且在基于索引的查找上會更有優(yōu)勢。
- 樹的優(yōu)勢則體現(xiàn)在數(shù)據(jù)的層次結(jié)構(gòu)上。
- 哈希表優(yōu)勢體現(xiàn)在，無論有多少數(shù)據(jù)，查找、插入、刪除只需要接近常量的時間，即 O(1）的時間級。
核心思想實現(xiàn) “地址 = f (關(guān)鍵字)” 的映射關(guān)系，快速完成基于數(shù)據(jù)的數(shù)值的查找。 哈希函數(shù)的設(shè)計直接定制法哈希函數(shù)為關(guān)鍵字到地址的線性函數(shù)。如，H (key) = a*key + b。 這里，a 和 b 是設(shè)置好的常數(shù)。 數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字 key 都是由 s 位數(shù)字組成（k1,k2,…,Ks），并從中提取分布均勻的若干位組成哈希地址。 平方取中法如果關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)，并且頻率很高，我們就可以先求關(guān)鍵字的平方值，通過平方擴大差異，然后取中間幾位作為最終存儲地址。 折疊法如果關(guān)鍵字的位數(shù)很多，可以將關(guān)鍵字分割為幾個等長的部分，取它們的疊加和的值（舍去進位）作為哈希地址。 除留余數(shù)法預(yù)先設(shè)置一個數(shù) p，然后對關(guān)鍵字進行取余運算。即地址為 key mod p。 解決哈希沖突開放定址法常用的探測方法是線性探測法。比如有一組關(guān)鍵字 {34，35，36，45}，采用的哈希函數(shù)為 key mod 11。當插入 34，35，36 時可以直接插入，地址分別為 1、2、3。而當插入 45 時，哈希地址為 45 mod 11 = 1。然而，地址 1 已經(jīng)被占用，因此沿著地址 1 依次往下探測，直到探測到地址 4，發(fā)現(xiàn)為空，則將 45 插入其中。 鏈地址法將哈希地址相同的記錄存儲在一張線性鏈表中。如果出現(xiàn)沖突，就在對應(yīng)的位置上加上鏈表的數(shù)據(jù)結(jié)構(gòu)。 哈希表的基本操作哈希表中的增加和刪除數(shù)據(jù)操作，不涉及增刪后對數(shù)據(jù)的挪移問題- 如果是采用數(shù)組實現(xiàn)就需要考慮數(shù)據(jù)的挪移問題
哈希表查找的細節(jié)過程是：對于給定的 key，通過哈希函數(shù)計算哈希地址 H (key)。- 如果哈希地址對應(yīng)的值為空，則查找不成功。
- 反之，則查找成功。
哈希表的案例實時返回用戶的字符串搜索結(jié)果
|
