劉汝佳-數據結構入門【業(yè)界相關】

1、數據結構入門,清華大學 劉汝佳,1,專業(yè)課堂,什么是數據結構,數據結構的含義 數據 關系 操作 例子：數組 數據：a1, a2, , an 關系：前驅/后繼 操作：隨機存取，插入，刪除 數據結構為算法服務 根據算法對數據的操作要求，設計合適的數據結構 實現同一套操作，可以用多種數據結構 如何降低時空復雜度，又方便實現,2,專業(yè)課堂,抽象數據類型(ADT,算法對數據結構的要求 維護一個電話薄，方便進行插入刪除和查找 操作：插入，刪除，查找 如何實現？ 算法不關心！ 只要提供這些操作都可以！ 抽象數據類型：集合,3,專業(yè)課堂,邏輯結構,抽象數據類型沒有辦法轉化成程序 需要設計邏輯結構！ 所有電話記

2、錄形成線性結構，記錄的順序無要求 無序線性表 有了邏輯結構，可以設計算法 插入：直接插到表的頭部或者尾部 刪除：直接刪除，再把兩段合并在一起 查找：從頭開始沿著表找一遍 這個算法仍然不能轉化成程序 甚至無法進行復雜度分析,4,專業(yè)課堂,物理結構,邏輯結構需要進一步轉化成物理結構 邏輯結構：無序線性表 物理結構：數組 插入：插到尾部比較方便，O(1) 刪除：“合并兩半”導致元素移動，最壞O(n) 查找：最壞O(n) 物理結構：鏈表 插入：插到頭部比較方便，O(1) 刪除：找到位置后O(1) 查找：O(n) 不同的物理結構，得到不同的效果,5,專業(yè)課堂,另一種邏輯結構,有序線性表 物理結構：數組

3、插入最壞O(n) 刪除最壞O(n) 查找最壞O(logn)：二分查找 物理結構：鏈表 插入（找到后）最壞O(1) 刪除（找到后）最壞O(1) 查找最壞O(n)，平均n/2,6,專業(yè)課堂,比較一下,7,專業(yè)課堂,如何學習數據結構,了解常見的抽象數據類型 對每種ADT，了解常見的邏輯結構 設計邏輯結構是最難的！ 對給定的邏輯結構，自己設計物理結構 物理結構一般只是數組和鏈結構 數組可以隨機訪問（設計下標計算公式） 經典例子：哈希表，二叉堆，并查集，線段樹 鏈結構應該根據元素間關系（鏈接）進行“移動” 經典例子：伸展樹，二項堆，跳躍表 *特殊算法需要自己歸納出ADT并設計邏輯結構 PQ樹，后綴樹,8

4、,專業(yè)課堂,常見的抽象數據類型,棧 壓棧（入棧），彈棧（出棧），判斷空 隊列 入隊，出隊，判斷空 串 取前綴/后綴，匹配 字典 插入，刪除，查找 優(yōu)先隊列 插入，取最小值，刪除最小值，合并,9,專業(yè)課堂,入門學什么,棧和隊列 串：匹配 樹：表示和遍歷 圖：遍歷和拓撲排序 *基本檢索算法 *基本排序算法,10,專業(yè)課堂,棧,外特性：后進先出(LIFO) 交卷子 KTV的“點歌單” 作用：保護現場 邏輯結構：只在一端操作的線性表 數組實現：元素stack : array1.maxn of integer，棧頂指針top 入棧：inc(top); stacktop := ele; inc(top)

5、top := top + 1 出棧：ele := stacktop; dec(top) dec(top) top := top - 1 空棧條件：top = 0,11,專業(yè)課堂,鐵軌問題,例1：1,2,3,4,5 yes；例2：5,4,3,2,1 yes 例3：3,2,4,5,1 yes；例4：3,1,4,5,2 no,12,專業(yè)課堂,隊列,外特性：先進先出(FIFO) 食堂排隊 吸管里的飲料 作用：維持順序 數組實現：元素queue0.maxn-1，隊首front，隊尾rear 入隊：inc(rear); queuerear := ele; 出隊：ele := queuefront; inc

6、(front) 隊空條件：front rear 問題：出隊的元素還在數組里，不是很浪費嗎？ 循環(huán)隊列 把隊列看成環(huán)行的，則 入隊：rear := (rear + 1) mod maxn; 不定義為queue1.maxn的原因 出隊：front := (front + 1) mod maxn; 可能存在隊滿的情況：條件也是front rear （想一想，如何解決,13,專業(yè)課堂,小球鐘時間與運動,14,專業(yè)課堂,球鐘的狀態(tài)表示,含有小球的四個部件 分鐘軌道：ball1.4 5分鐘軌道：ball1.11 小時軌道：ball1.11 底部軌道：ball1.n 問題：雖然都是線性結構，但如何操作？ 分

7、鐘、5分鐘、小時：棧！ 底部小球：隊列,15,專業(yè)課堂,球鐘的模擬,完全模擬 時間復雜度O(t)，t為模擬的時間，可能很大 經過12小時 小球又全部回到底部軌道 但順序和以前不一樣了！ 設一開始各個小球的編號依次為1,2,3n 新順序是1,2,3n的一個排列！ 一個例子：1,2,3,4,5 2,4,5,1,3 小球1的位置變化：1421 小球3的位置變化：353 小球1,2,3,4,5分別經過3,3,2,3,2個12小時回到原地 總時間為2,3 = 6 時間復雜度：O(n) （想一想，為什么不是O(n2),16,專業(yè)課堂,種子填充法,17,專業(yè)課堂,怎樣找連通區(qū)域,走迷宮沒有分身術 棧(DFS

8、) 撒墨水 隊列(BFS) 連通區(qū)域的種類 四連 八連 怎樣高效的實施,18,專業(yè)課堂,四連區(qū)域和八連區(qū)域,四連 dx : array1.4 of integer = 1, -1, 0, 0; dy : array1.4 of integer = 0, 0, -1, 1; for direction :=1 to 4 do newx := x + dxdirection; newy := y + dydirection; 八連？自己試一試！ 空間呢？ 六角形呢,19,專業(yè)課堂,回到原題,如何找臉？ 四連？八連？ 如何找臉上的元素？ 四連？八連？ 如何判斷兩個臉是否一樣？ 左上角坐標 比較矩形區(qū)

9、域？ 如何表示,20,專業(yè)課堂,種子填充有用嗎,求：上確界(J)和下確界(G,21,專業(yè)課堂,二分檢索算法,猜一個1n的整數，需要多少次？ 每次告訴你猜大了還是猜小了 可能的范圍總是一個區(qū)間（怎么證明？） 區(qū)間總會一個中點 不管是大還是小，都可以排除約一半的可能性 最壞需要多少次？ log2n次。（想一想，怎么證明？） 如果是在一個排序好的數組中查找一個整數呢？ 本質是一樣的 如何處理找不到的情形？ 算法名稱：二分檢索,22,專業(yè)課堂,進一步的考慮,如果不告訴你整數的范圍，怎么辦？ 每次擴大兩倍？ 每次猜Fn？ 如何分析性能？（想一想） 問題變換 優(yōu)化 判定 例：電纜問題 網線數目給定 每根要

10、求盡量長 不能拼接，只能切割,23,專業(yè)課堂,基本排序算法,常見算法 插入排序 選擇排序 歸并排序 快速排序 分類 基于比較？ 穩(wěn)定,24,專業(yè)課堂,插入排序,依次處理各個元素。處理第i個時，保持前i-1個有序 找到合適的位置（唯一?。?一個一個找 因為有序嘛.二分檢索？ 插進去！數組需要移動元素，鏈表不需要 討論：二分檢索查找有多大意義？ 適合場所：原始數據基本有序！ 應用：為粗排序做的“收尾”工作 例子：快速排序的邊界,25,專業(yè)課堂,選擇排序,所有元素一起處理多遍。第i次找到第i大元素 找大最大元素：O(n) 讓這個最大的不會再成為最大 刪除？ 變成最小值？ 移動到無關區(qū)域？ 反復找當前

11、最大值，就找到了第2,3,n大,26,專業(yè)課堂,兩個應用,輸入有間隔？ 選擇排序？取決于未來的輸入？ 插入排序：來一個插一個 因果系統！ 在線算法 給期末考試成績表做排名，希望先知道前10 插入排序？如果前10名是最后10個元素 選擇排序：選的前10個就是前10名！ 結論：排序算法的選擇要看實際應用,27,專業(yè)課堂,歸并排序,兩個有序表，怎么合起來？ 1, 2, 4, 7, 9 3, 5, 6, 10, 11 合并：n 分治sort(i, j)，設時間為T(n) 排前一半：sort(i, mid), 時間T(n/2) 排后一半：sort(mid+1, j)，時間T(n/2) 合并起來：n T(

12、n) = 2T(n/2) + n T(n) = O(nlogn,28,專業(yè)課堂,一個例子,目標：從小到大排序 從下數第k個開始往上翻 (a) (b) (c) 3 1,29,專業(yè)課堂,一個應用,逆序對數目：i aj 枚舉：O(n2). n = mid，遞歸處理 i mid j，如何求？ 合并的時候順便求！ 還是這個例子 1, 2, 4, 7, 9 3, 5, 6, 10, 11 取后一半元素時，前一半還剩多少個就是 時間復雜度：O(nlogn). n = 100,000,30,專業(yè)課堂,快速排序,找一個數x 讓x左邊的數都比x小 讓x右邊的數都比x大 分別給兩邊排序 核心：如何調整x左右的數？

13、從兩邊往中間掃描 在x左邊第一個比x大的地方停下來 在x右邊第一個比x小的地方停下來 兩個交換，正好都滿足要求 例子：1, 8, 2, 9, 6, 4, 7, 3, 5 第一次交換8和5：1, 5, 2, 9, 6, 4, 7, 3, 8 第二次交換9和3：1, 5, 2, 3, 6, 4, 7, 9, 8 第三次交換6和4：1, 5, 2, 3, 4, 6, 7, 9, 8 兩個指針匯合，完成 時間復雜度：O(n,31,專業(yè)課堂,快速排序分析,最好情況：均分成兩半，則是O(nlogn) 最壞情況：分成長度為1和n-1，則是O(n2) 想一想，為什么是O(n2) 這是不是說明快速排序比歸并排序

14、差？ 顯然不是，否則就不會叫“快速排序”了嘛 想一想，為什么？ 最壞情況出現的概率 應該分析平均情況！限于篇幅，此處略。 結論為O(nlogn)，而且系數比歸并排序小 一些小細節(jié) n = 10時用插入排序加速 x如何選？中間？隨機（隨機數產生開銷）？ 警告！快速排序不穩(wěn)定！原因？如何修改,32,專業(yè)課堂,快速排序應用,士兵排隊問題 n=10,000個士兵在網格中，位置用(x, y)表示 士兵可以沿四個方向移動 進入某一行且排在一起 假設格子可以容納所有士兵 分析 行：中位數 or 平均數？ 列？（請思考） 中位數如何求？ 快速排序？O(nlogn) 其實不需要分別排序，只需要根據k的大小只處理

15、一邊 平均情況：O(n,33,專業(yè)課堂,有更快的排序方法嗎,計數排序 分數：0100的整數 開一個count0.100的數組，記錄個數 for i:=1 to n do inc(countscorei); 就可以了！O(n)！ 但是 有附加關鍵碼（姓名，學號） 穩(wěn)定性要求？ 怎么會這么快？ 關鍵碼范圍限制（如果范圍是0100,000，但n=10,000，就） 不是基于比較的！而是直接根據關鍵碼范圍 如果只提供比較呢？交互式題目,34,專業(yè)課堂,基于比較的排序時間下限,簡單起見，不考慮相等的情形 可以獲得多少信息？ 一次比較，兩種結果 k次比較2k種結果 需要獲得多少信息？ n個數的排列有n!種 最后只剩一種可能性時，排序完成 需要比較多少次？ 比較k次以后最好只能保證剩n!/2k種可能性 n!/2k=1時，即k=log(n!)時排序完成 log(n!) = (nlogn,35,專業(yè)課堂,排序的應用,a) 改變第二行，交換一、三列 (b,36,專業(yè)課堂,迷題的解答,先行后列 行的情況：2n 列的情況：n! (b)的第1列是(a)的哪一行變化而來 各行情況都知道 是否能重排各列？ 方法一：枚舉判斷：O(n3) 方法二： 按同一比較方法排序：O(n2logn) 元素相同的不同的排列排序結果唯一！ 總時間復雜度：O(n3logn) 優(yōu)化,37,專業(yè)課