Microsoft PowerPoint - lecture4

Size: px

Start display at page:

Download "Microsoft PowerPoint - lecture4"

谖危
5 years ago
Views:

1 作業一解答下星期一也會上線. QUEUE & STACK Michael Tsai 2010/10/8 作業二今天會放上網站. 各位同學寫作業一辛苦了. 請發表對這次作業的感想.

2 2 今日菜單複雜的 KMP 例子上次沒有講完的 sparse matrix Stack Queue 計算機迷宮

3 3 Failure function 另外一個定義 (recursive) 1, where is the least int for which 1, if there is no satisfying the above f a b c a b d a b c a b c a b c a b d a b c a b c f

4 4 朋友三 : 矩陣怎麼存起來? 用二維陣列, a[row][col] 來存加法乘法都很容易

5 5 很鬆的矩陣浪費很多空間在存 T_T 有沒有什麼節省空間的方法可以存?

6 6 很鬆的矩陣存法 : index Row Col value

7 7 空間省了, 但是如果要做 transpose 直接把 row & col 的值交換? 這樣就沒有照順序了 ( 以 row 為主 ) index Row Col value

8 8 < 動腦時間 > 怎麼用 O(columns+elements) 的時間做完 transpose? 當不鬆的時候, 就變成 O(columns+elements) =O(columns+columns*rows)=O(columns*rows) 怎麼做? 當做回家習題請看 program 2.9 (p.78)

9 9 那麼, 矩陣乘法呢? 不順 ( 希望同樣 column 的會放在一起 ) 所以可以先 Transpose

10 10 實際乘乘看類似之前的鬆多項式加法比較兩邊的 row & col 數 a<b a 移到下一項 a==b 可以相乘, 乘起來以後的值存起來 a>b b 移到下一項

11 11 看看程式 program 2.10 和 2.11 (p.81) 這個程式比較複雜, 如果看不懂回家請再多花時間 Time complexity = O(??) 複雜度也很複雜, 請也多花時間

12 12 Stack Stack 是蝦密碗糕? 一串有順序的列表又叫 Ordered List 有什麼特別的地方? 頂 (Top) 底 (Bottom) 永遠從頂部拿與放拿 : Pop 放 : Push 看一個例子所以先放進去的, 會?? 出來?

13 13 Stack 所以是一個先進後出 (First In Last Out) 的資料結構那麼, 支援那些動作呢? 各動作又需要什麼參數? 請同學們列舉 : 做一個 Stack 放 (Push) 拿 (Pop) 是不是空的? 是不是滿了?

14 14 例子一 : 系統堆疊被程式拿來儲存呼叫 function 的相關資訊放什麼? 叫做 activation record 或 stack frame return address: 呼叫 function 的下一個指令應該去的地方 previous frame pointer: 指到前一個 stack frame 在 stack 裡面的位置 ( 底 ) local variables 看一個例子. 適不適用 recursive call? Stack overflow? sp fp Previous frame pointer Return address Local variables Previous frame pointer Return address

15 15 怎麼 implement 一個 stack? 請同學上來舉例說明提示 : Array 這個好朋友又出現了除了 array 以外, 還需要哪些東西? 紀錄頂部的 index 怎麼 implement 四個 operations? Push Pop 是不是空? 是不是滿?

16 16 滿了怎麼辦? int stack[max_size]; 如果裡面有超過 MAX_SIZE 元素, 就滿了. T_T 如果一開始我用 stack=(int*)malloc(sizeof(int)*max_size); 如何把 stack 變大? 複習 : realloc 做什麼用的? realloc 相關決定 : 要 realloc 成多大? realloc 完畢有沒有什麼要改的地方?

17 17 來一點複雜度分析如果每次都 realloc 成原本的兩倍大 capacity 存現在的 stack 大小 realloc(stack, 2*capacity*sizeof(int)); capacity*=2; 問題 : push n 次的時間複雜度為多少?

18 18 來一點複雜度分析問題 : push n 次的時間複雜度為多少? 假設 : Push 一個 element 是 O(1) Allocate 一個 element 是 O(1) 移動一個 element 是 O(1) 第一小問題 : 如果目前 capacity 是 2, 花在 realloc 的時間是多少? 第一小問題的子問題 : realloc 是 O(?) Worst case: Allocate 2*capacity 個 element 的位置, 然後移動 capacity 個 element 的資料到新地方答案??

19 19 來一點複雜度分析第一小問題 : 如果目前 capacity 是 2, 花在 realloc 的時間是多少? 第一小問題的子問題 : realloc 是 O(capacity) 那麼花在 realloc 的時間就是 2 2 2

20 20 來一點複雜度分析第二小問題 : 會使得目前的 stack 大小為 capacity=2, 應該已經 push 了幾次? 答案 : 至少已經 2 次了 Ο 喔耶. < 動腦時間 : 回家作業 > 如果每次增加為原本 capacity 的 c 倍, c>1, 那麼複雜度會有變化嗎? 為什麼?

21 21 Queue Queue 是蝦密咚咚? 也是 Ordered List 5 4 尾 (Rear) 和 Stack 有什麼不一樣? 1 0 頭 (Front) 從尾 (Rear) 放, 從頭 (Front) 拿拿 : Delete 放 : Add 所以先放進去的, 會?? 出來?

22 22 Queue 先放進去的, 會先出來所以是 First In First Out (FIFO) 那麼, 支援那些動作呢? 各動作又需要什麼參數? 請同學們列舉 : 做一個 Queue 放 (Add) 拿 (Delete) 是不是空的? 是不是滿了?

23 23 舉一個例子 Job scheduling 如果沒有使用 priority 的概念的話先來的 job 就先做 FIFO 的概念問題 : 程式要求作業系統做一個 job, 作業系統要照來的順序決定誰先使用資源. 作法 : 程式發出要求的時候, 就放入 queue 中資源空出來了, 就從 queue 拿出一個 job 來做結果 : FIFO < 動腦時間 > 如果放入一個 stack 會怎麼樣?

24 24 那麼, 怎麼 implement queue 呢? 一樣是 array 的朋友要記得頭跟尾的在 array 裡面的位置 (index) 但是這次有點問題滿了! 但是前面的空間沒有用到! 怎麼解決? 頭尾

25 25 解決方式 : 頭尾相接頭課本叫它 circular queue 這樣就可以保證 queue 儲存的 element 數目最多可以跟 array 大小一樣什麼時候是空? 什麼時候是滿? ( 能不能分辨空和滿?) 尾

26 26 那麼, 如果要使用動態大小呢? 一樣使用 realloc 來要到一塊更大的記憶體然後還有什麼工作要做? realloc 之後的樣子 : 看起來不太對尾頭請一位同學上來講解怎麼修正

27 27 問題 : 很多 stack 用一個 array 來存問題 : 如果現在我們有一個 array, 但是我希望用這個 array 存兩個 stack, 請問要怎麼 implement? 什麼時候 stack 滿了? push & pop 的動作怎麼做? 問題 : 那麼, 如果有 n 個 stack, 又要怎麼存在一個 array? 什麼時候 stack 滿了? 真的有滿嗎?

28 28 接下來講一些應用 : 計算機問題迷宮問題

29 29 應用一 : 計算機不是普通的計算機題目 : 如果打入一串如 1+2*3 5/(4+5)/5 的算式, 請寫一個演算法來算出這串算式的結果. 怎麼寫呢? 好複雜 T_T

30 30 先來看看算式長什麼樣子 1+2*3 5/(4+5)/5 裡面有 : Operand 1, 2, 3, 5, 4, 5, etc. Operator +* / 括號 (,) 特色 1: 左到右 (left to right associativity) 特色 2: 一般這種寫法叫做 infix (operator 夾在 operand 中間 ) 先後順序要 operator 去比大小例如乘除是大, 加減是小, 那麼就先乘除後加減

31 31 別種寫法 : postfix 把 operator 放到兩個 operands 的後面例如 2+3* * + a*b+5? (1+2)*7? a*b/c? (a/(b c+d))*(e a)*c? a/b c+d*? e a*c?

32 32 Postfix 有什麼好處? 沒有括號用 stack 幫忙就可以很容易地算出結果! 例子 : 6 2 / * + 從左邊讀過去讀到 6, 放 6 進 stack (stack: 6) 讀到 2, 放 2 進 stack (stack: 6 2) 讀到 /, 取兩個 operands (6 和 2), 算 6/2, 然後答案放回去 stack (stack: 3) 讀到 3, 放 3 進 stack (stack: 3 3) 讀到, 取兩個 operands(3 和 3), 算 3 3, 然後答案放回去 stack (stack: 0) 依此類推.( 請同學上來繼續完成 )

33 33 剩下來的小問題 : infix to postfix 小問題 : 怎麼把 infix expression 轉成 postfix expression? 第一種方法 : ( 適合紙上談兵 ) 1. 把整個 expression 2. 把所有的 operator 都移到 operand 的後面去, 方便去除所有括號 3. 去除所有括號但是實作上要怎麼做呢? ( 不希望做兩次 )

34 34 又是一個可以利用 stack 解決的問題方法 : 1. 從左至右讀取 expression 2. 碰到 operand 就直接輸出 3. 碰到 operator 時比較 stack 頂上的 operator 和目前讀到的 operator 哪一個比較大 (precedence) 如果目前讀到的 operator 比較大, 就把 operator 放到 stack 裡如果一樣大或者現在讀到的 operator 比較小, 就一直把 stack 裡面的 operator 拿出來印出來, 一直到 stack 是空的或者現在的 operator 比 stack 頂的 operator 大或者一樣為什麼可以這樣做? 裡面括號需要先印出, 但是卻是後讀到比較外面的先用 stack 記起來, FILO, 由內而外

35 35 例子一請一位同學來解說怎麼把 a+b*c 利用前述方法轉換成 postfix 那麼, 如果碰到括號怎麼辦?

36 36 括號括號內的有優先性因此當碰到右括號的時候, 就立刻把 stack 中的東西一直拿出來直到碰到左括號為止舉例 : a*(b+c) 輸出的內容, stack 內容 ( 最右邊為 top) a a, * a, *( ab, *( ab, *(+ abc, *(+ abc+*

37 37 還有一些小問題小問題 1: 左括號的大小到底是多少? 碰到左括號一定要放進去 stack 此時要是最大的左括號的下一個 operator 一定要可以放進去此時要是最小的結論 : 左括號有兩種大小在 stack 內的時候優先性為最小在 stack 內的時候優先性為最大其他 operator 的優先性則不管在 stack 內外都一樣

38 38 還有一些小問題 Q: 如何確保 stack 空的時候, 第一次碰到的 operator 可放進去? A: 在 stack 底部放入一個虛擬 operator 帶有最低的優先性 Q: 如何確保讀到 expression 最後的時候, 可以把 stack 裡面未取出的 operator 都拿出來? A: 字串最後可以加一個優先性最低的虛擬 operator

39 39 例題 a+(b*c/(d f)+e) 用白板解說 ( 請同學? :P) < 回家作業 > 請各位看一下 page 137 的 program 3.15 以了解怎麼寫 infix prefix 的轉換程式作業預告 : 會跟 prefix 相關例子 : a*b+c +*abc

40 40 最後來一個有趣的迷宮問題吧迷宮 : 0 是路, 1 是牆壁. 每一部可以往上下左右和四個斜角方向走一步. 問題 : 怎麼找出一條路從 (0,0) 走到 (7,7)? ( 不一定要最短 ) 提示 : 跟 stack 是朋友

41 41 走迷宮的時候, 人要怎麼走? 最重要的時候, 是碰到岔路的時候先記起來, 選其中一條走走看如果碰壁了 ( 一直沒有走到終點 ), 就退回最後一次碰到的岔路, 換另外一條岔路關鍵字 : 最後一次碰到的岔路 ( 不是最先碰到的 ) 所以是先進後出使用 stack 關鍵字 : 換另外一條岔路要記得上一次走過哪一條路了

42 42 一些細節 Q: 那麼, stack 裡面要存什麼呢? A: 岔路的地方的座標, 也就是 (row, col) 試過那些岔路了 ( 試到八個方向的哪個方向了 ) Q: 要怎麼預防繞圈圈? ( 永遠出不來 ) A: 標示所有已經走過的地方, 走過就不用再走了 < 注意 > 這是因為不用找最短的路

43 43 讓我們來寫 algorithm 把 (row_start, col_start, 第一個方向 ) 放入 stack while(stack 不是空的 ) { 從 stack 拿出一組岔路點 (row, col, dir) while( 還有別的 dir 還沒試 ) { 將 (row, col) 往 dir 方向移動, 得到 (row_n, col_n, dir). 如果 (row_n, col_n) 就是終點, 則結束如果 (row_n, col_n) 不是牆壁且沒有來過 { 標示 (row_n, col_n) 來過了把 (row, col, dir 的下一個方向 ) 放入 stack row=row_n; col=col_n; dir= 第一個方向 ; } } }

44 休息時間 44

45 45 周末快樂 ~ 作業二今天會出參考同學們的意見, 這次份量會減少請及早開始 ( 程式作業不簡單 ) Michael 辦公室在這一棟

stack_and_queue

stack_and_queue Stacks and Queues Prof. Michael Tsai 2017/02/21 Stack Stack represents an ordered and linear list Stack of plates Taken from and placed onto the top Pop: take an element Push: place an element Example