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