Data Structure - Ch6 Basic Data Structure

Chapter 6   Basic Data Structure

6.1   Recursion

• 遞迴的種類
• Directed recursion：函式直接呼叫本身。
• Indirected recursion：函式先呼叫另外的函式，再從另外函式呼叫原來的函式。
• Tail recursion : Directed recursion一種，特色是回傳的地方前面不會乘一個東西，還多加一個累積算到目前結果的變數，compiler最佳化會把尾遞迴展開，變成寫起來是遞迴，跑起來不是遞迴。

• [複習] recursive call敘述之處理
• 遇到recursive call, 保存當時的執行狀況push到stack中(parameter、local/temp variables、return address)
• Parameter Passing
• Call by reference：主副函式佔用相同的記憶體位置，Binding最快，主函式的參數值會跟著改變。
• Call by value：分派額外的記憶體位置，Binding最慢，主函式的參數值不變。 
• Call by name：佔用相同的記憶體位置，Binding比Call by value 快 Call by reference慢，主函式的參數值會跟著改變 
• 跳到call的程式開端執行執行時遇到end, 則如果stack不為空, pop stack, goto address, 直到真的end

• 常見遞迴演算法
• fibonacci (golden ratio)
• expo成長極快，小於1000之max, n = 16，所以計算題不要被嚇到唷！
• F99 = F98 + F97 = F100 - F98 = F101 - F100
• GCD 最大公因數（輾轉相除法，Euclid's algorithm ）
• GCD(A, B)  = B,                               if A mod B == 0
                        = GCD(B,A mod B), otherwise
• 組合數（Binomial Coefficient）
• Bin(n,m) = 1,                                              if (m==0 || n==m)
                   = Bin(n-1,m) + Bin(n-1,m-1), otherwise
• Ackerman’s Function
  A(m,n) = n+1,                          if m = 0
                = A(m-1,1),  if n = 0
                = A(m-1, A( m, n-1) ),  otherwise
• 河內塔
  T(n) = Ta(n-1) + Tb(1) + Tc(n-1) 步驟分解分析複雜度
          = 2T(n-1) + 1,   initial T(1)= 1
• Permutation
  若有n個不同的資料，則n個資料輪流當頭，剩餘資料去遞迴。注意印出順序!

6.2   Array

• 在二維陣列中，如何將二維陣列轉成一維陣列有兩種方式
• 以行為主 (Column-major)
• 已列為主 (Row-major)
• 已列為主的二維陣列要轉為一維陣列時，是將二維陣列由上往下一列一列讀入一維陣列，亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式。

• 多項式的表示方式 
• [方法一] 按照指數由高到低依序儲存係數
• 當指數很大且零項次極多時不適用，太浪費空間。
• ex : 3x^¹⁰⁰+6，(100+1)+1 = 102
• [方法二] 儲存非零項次的係數與指數
• 不適用於非零項次極多的多項式，否則此法所使用的儲存空間大約是方法一的兩倍 
• ex : 3x^¹⁰⁰+6，(2*2)+1 = 5
• [方法三] 利用Single linked list

• 稀疏矩陣 (Sparse Matrix)
• 以 [列,行,値] 來表示一個非零元素。 
• 假設 m×n 的稀疏矩陣,有 k 個非零元素,則準備一個size為 (k+1)×3的二維陣列。 
• 以Row-major方式依序存放資料

• KMP 演算法 (Knuth-Morris-Pratt Algorithm)
• 問題
• 模式匹配 (Pattern Matching)：給定一個主串(Text) S[1...n]、一個模板串(Pattern) P[1...m] 且 m ≤ n，問 P 是否為 T 的子串? 若是，則發生的位置為何?
• 概念
• 觀察暴力演算法，發現其作了很多不必要的工作，匹配到某一位失敗時，暴力法會直接檢查下一位，但那幾位其實是早已配對過的。
• 步驟
• KMP演算法使用兩個指標i, j分別指主串以及模板串,並且維持S[ i – j + 1 ... i ] = P[ 1 ... j ] 的特性，讓 i 不斷增加並使 j 隨其變化，也就是說，我們使他滿足以 S[i]結尾的 j 個元剛好匹配到 P 的前 j 個元(所以我們必須使 j 盡量的大)
• 更新 j 的動作只跟模板串 P 自己有關係，這也使得這個更新動作完全依靠先前的預處理變成是完全可能的，該preprocess function又稱為failure function。

• 複雜度分析


• KMP 演算法為最差情況為 O(n)的模式匹配演算法。
  均攤分析(aggregate analysis)的經典運用，所使用的方法正是最常用的累計分析，仔細觀察我們發現在整個過程中j 最多只能上升 n 次，因此j 也最多只有減少 n 次的機會，也就是說while 最多只執行 n 次。按照均攤分析的想法，均分到 n 次的迴圈中，每次只有 O(1)的負擔，當然是線性的! 用到預處理的過程也是同理的。

6.3   Link list

• Link list的種類
• Single Link List 
• Circular Link List：circular link list主要優勢
• 回收:O(1)
• 串接:O(1)
• 製作queue
• Double Link List：雙向鏈結串列可視為2個Circular Link List 
• Link list 應用
• Storage Pool：Free Node集中管理之處，通常 OS 以Single link list來管理Free Nodes，稱為AV-list (Available list). 
• 一般化串列 : Lisp語言的基礎
• C = ( a [atomic data] , C [sublist] )  ,  ex : A = (a, (b, c) )
• 利用Generalize list 觀念來表示多種變數的多項式，
• 使之有一個一致性的node structure，幾個變數gen list就有幾層

• [sparse matrix 另解] Linked Structure 
• 優點 : 非零項有所更動時，不需做大規模的移動。 
• 缺點：較浪費空間

6.4   Stack & Queue

• Stack：FILO
• Procedure Call/Recursive Call
• Parsing
• Reversing Data
• Infix, Prefix, Postfix transition 
• Infix to postfix
• 人類法
1. 補滿括號
2. operator取代最近右括號
3. 刪除左括號
• 程式法
1. stack the operator having higher priority 
2. Pop out the operator on the top of the stack when the incoming one has equal to or less than priority 
• [about parentheses]
• in-coming priority for “(” is high — to make sure that “(” can be pushed . 
• once “(” is in the stack, the priority is low — so that operators in the parentheses can be pushed. 
• A token “)” comes, pop out the stack until “(” is popped
• 如果要將中序式轉為前序式，則在讀取中序式時是由後往前讀取，而左右括號的處理方式相反，其餘不變，但輸出之前必須先置入堆疊，待轉換完成後再將堆疊中的 值由上往下讀出，如此就是前序表示式。 

• [議題]  Catalmnn Number 
• n 個 data之stack permutations個數 ＝ 1/(n+1)  (2n  n) = (2n n) - (2n n-1)
• = n個nodes可以形成的不同binary trees個數
• = n個左右括號的合法配對個數
• = (n+1)個matrix 相乘之可能乘法組合順序
• Queue
• FIFO Queue
• Priority Queue
• 不一定FIFO, 可支援插入任意權值元素, 刪除最大權值
• 製作：heap
• Double-end Priority Queue 
• 兩端皆支援insert和delete, 可刪min max
• 製作：min-max heap, Deap, SMMH …
• Queue 和Stack可互相製作，兩個換一個