Microsoft PowerPoint - lecture5

Size: px

Start display at page:

Download "Microsoft PowerPoint - lecture5"

锤孙
6 years ago
Views:

1 下星期開始教室改至 R101 LINKED LISTS Michael Tsai 2010/10/15 作業二下星期四 due 請多利用下周二三四的 office hour

2 2 今日菜單上次講得不好的 Sparse Matrix Transpose 方法上次未講完的迷宮問題 Linked List 應用多項式相等集合很鬆的矩陣

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

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

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

6 6 讓我們來寫 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= 第一個方向 ; } } }

7 7 大家來吐 Array 的槽 Array 有什麼不好? 插入新 element 1 3 4新的空 5 刪除原本的 element Time complexity= O(??)

8 8 新朋友 : Linked List 要怎麼讓資料 1. 可以隨便亂排 2. 但是我們仍然知道他的順序? 答案 : 資料亂排但是, 另外存下一個是誰 index [0] [1] [2] [3] [4] 資料下一個是誰子毅林潔立中婷尹予迪開始 1

9 9 概念上, 應該是長這樣開始立中林潔子毅予迪婷尹 Null 真正的樣子 : index [0] [1] [2] [3] [4] 資料下一個是誰子毅林潔立中婷尹予迪開始 2

10 10 增加一個人? 開始立中林潔子毅予迪婷尹 Null 柏廷 index [0] [1] [2] [3] [4] [5] 資料下一個是誰子毅林潔立中婷尹予迪柏廷開始 2

11 11 刪掉一個人開始立中林潔子毅予迪婷尹 Null 柏廷 index [0] [1] [2] [3] [4] [5] 資料下一個是誰子毅林潔立中婷尹予迪柏廷開始 2

12 12 來看一些 code ( 用 malloc/free) 怎麼宣告一個 node 的 struct? struct listnode { }; int data; struct listnode *link; 怎麼拿一個新的 node? listnode *new; new=(struct listnode*)malloc(sizeof(struct listnode));

13 13 來看一些 code new 是指標, 指到一個 struct listnode 的變數. 那如果要拿這個變數裡面的 data 呢? 可以這樣寫 : (*new).data 或者, new >data 要拿 link 呢? (*new).link 或者, new >link

14 14 來看一些 code start 假設 start 指到第一個 struct listnode 那麼我要拿到 551 的下一個 listnode 的位址怎麼寫? start >link >link ( 連續技 )

15 15 製造兩個 node start struct listnode* start, *tmp; tmp=(struct listnode*)malloc(sizeof(struct listnode)); tmp->data=551; tmp->link=null; start=tmp; tmp=(struct listnode*)malloc(sizeof(struct listnode)); tmp->data=342; tmp->next=start; start=tmp;

16 16 插入一個新 node 在某 node 後面 struct listnode *x; // 指到要插入的 node 的位置 struct listnode *new; new=(struct listnode*)malloc(sizeof(struct listnode)); new->data=123; 下一步呢? 先處理 new->link 還是 x->link? new->link=x->link; x->link=new;

17 17 刪除某一個 node struct listnode *x; // 指到要刪除的 node 的位置 struct listnode *trail; // 指到 x 的前一個 node 的位置分兩種狀況處理 : x 是頭, 還有 x 不是頭 if (trail) //x 不是第一個 node trail->link=x->link; else start=x->link; free(x);

18 18 印出整個 list struct listnode *tmp; for(tmp=start; tmp; tmp=tmp->next) printf( %d, start->data);

19 19 Stack & Queue 上次最後提到, 如果是一塊記憶體要放很多 stack 或 queue 就很難做到很 efficient 例如如果某一 stack 滿了, 就要把一堆資料往後擠就不是 O(1) 了 T_T 解決 : 跟 Linked List 當朋友

20 20 Stack 要怎麼拿來當 stack 呢? ( 想想怎麼做主要的 operation) push & pop 請一位同學上來講解 start 立中林潔子毅予迪婷尹 Null 例 : push( 立中 ) start 當作 stack top 怎麼寫 code? 那 pop 呢?

21 21 Queue 類似 stack 的作法不過頭尾都要有一個指標從頭拿, 從尾放 front rear 林潔子毅予迪婷尹 Null 怎麼拿? (delete) struct listnode* tmp; tmp=front; front=front->link; tmp_data=tmp->data; free(tmp); return tmp_data;

22 22 new Queue 立中 front rear 林潔子毅予迪婷尹那怎麼放? 假設 new 是指到新的 node rear >link=new; new >link=null; rear=new;

23 23 < 動腦時間 > 有沒有什麼是 array 比 linked list 好的? 什麼時候用 array? 什麼時候用 linked list?

24 24 多項式陰魂不散多項式怎麼用 linked list 表示呢? struct polynode { int coef; int expon; struct polynode *link; }; 例 : a a

25 25 那麼, 多項式加法? 挑戰! 直接看 code! Time complexity = O(??) 那之前用 array 表示, 有什麼不好? 答案 : 用完的比較好回收不回收會怎樣? 怎麼回收? 請一位同學來解釋

26 26 回收很慢有幾項就要 O( 幾項 ) 的時間懶人方法 : 丟到一個回收桶, 之後需要的時候再撿出來希望丟 =O(1), 而且撿 =O(1) 怎麼做? 回收桶 3 14 a 關鍵 : 找尾巴很慢. ( 不是 O(1))

27 27 Circular List 開始的那個箭頭, 指在尾巴最後一個 node 指回開頭有什麼好處? 丟進回收桶 =O(1)!! temp 回收桶多項式 a 請看 program 4.15 on p.169 ( 用 circular list 來做多項式加法 )

28 28 來練習一些動作反過來 : 把 a 變成 b 怎麼弄? 請同學上來解釋 + 用白板寫程式

29 29 練習題把 list b 接到 list a 後面 (chain) 把一個新的 node 加到 circular list 的最前面找出長度 (circular list)

30 30 Singly v.s. doubly linked list Singly linked list: a Doubly linked list: a 有單就有雙什麼時候需要用雙? Singly linked list 只能往後, 不能往前 ( 要從最前面開始重新找 ) Doubly linked list 用在常常需要倒帶的時候 Doubly circular linked list???? ( 請一位同學來畫 )

31 31 暫停! 來回想一下我們學了哪些種類的 linked list Singly linked list Circular Non circular (chain) Doubly linked list Circular Non circular (chain)

32 32 應用題相等集合 (Equivalence Classes) 很鬆的矩陣 ( 又來了 )

33 33 相等集合則 3. 且, 則問題 : 給一批的關係, 請列出所有不同集合的成員. 舉例 : 0 4,3 1,6 10,8 9,7 4,6 8,3 5,2 11,11 0 則可以分成 0,2,4,7,11 ; 1,3,5 ; 6,8,9,10

34 34 怎麼解呢? 幾個提示 : 1. 用 linked list 的 array 記住每個數跟其他那些數相等 2. 印出來的時候記得那些數已經印過了 ( 不要重複 ) 3. 利用 stack 的概念黑板解釋 ( 做動畫會很困難 Orz) program 4.22 O(??)

35 35 很鬆的矩陣這個給同學自行閱讀 Section 4.7 到目前為止最複雜的資料結構但是! 其實沒有很深的學問. < 動腦時間 > ( 自己回家想 ) 用這麼複雜的資料結構, 什麼時候適用? Space complexity = O(??)

36 36 周末愉快下周開始可能教室更改到 R101 作業二下周四 5pm 前交有問題的話請多利用下周二三四的 office hour 作業加分題 : (1) 從開學到現在, 覺得哪個課題講得最好? 哪個課題最不清楚, 希望老師再講一次? (3%) (2) 對於老師到目前為止上課的方式, 提出一個具體的建議. (3%)

Linked Lists

LINKED LISTS Prof. Michael Tsai 2013/3/12 2 大家來吐 Array 的槽 Array 有什麼不好? 插入新 element 1 3 4新的 24 52 空 5 刪除原本的 element 1 3 42 25 5 Time complexity= O(??) 3 Array 的複雜度 Indexing ( 拿某一個元素 ) 在開頭 Insert/Delete