Data Structure Final Review.

Presentation on theme: "Data Structure Final Review."— Presentation transcript:

1 Data Structure Final Review

2 學習資料結構的最主要目的 能妥善利用電腦將資料有系統地安排， 建立資料與資料彼此間的關係，將所 有的資料做最適當的安排、儲存，以 方便資料的更新 (update) 及存取 (access)

3 目標 甚至發展出新的資料結構… 培養未來面對不同問題情況下 如何選擇適當資料結構之能力 學習如何應用上述資料結構 於已知問題
培養未來面對不同問題情況下 如何選擇適當資料結構之能力 學習如何應用上述資料結構 於已知問題 知道並熟悉各種資料結構

4 重點回顧 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式

5 The Von Neumann Model & Memory Access
Cache

6 寫程式？ 熟悉程式語言語法 決定資料結構 程式邏輯 Usually not that difficult (lots of 前人智慧)
Visualize your problem General case & special case (boundary) consideration & verification

7 程式 or 演算法的效率評估 除了實際衡量程式的執行時間外， 另外一種效益評估的方式則是透過 分析個別程式的複雜度(Complexity)
Big-O O(N), O(NlogN), etc

8 資料結構 - review 陣列(Array) : 電影院中的坐椅、排列整齊的椅子
鏈結串列(Linked List) : 在鐵軌上南來北往的火車，每一部火車將一節一節的車廂從頭到尾串連在一起，而連接各節車廂的連接器就是此鏈結串列的鏈結

9 Array vs Linked List Overhead? & Tradeoff? head 2004 1 1 1016 9
1 1 1016 Overhead? & Tradeoff? 2019/5/20

10 資料結構 - review 堆疊(Stack) : 到西餐廳享用歐式自助餐時，餐盤一個一個依照由下而上的順序整齊的擺置
佇列(Queue) : 中午用餐時間，我們經常會看到學校自助餐前面大排長龍，等待享用午餐的排隊人潮

11 資料結構 - review 樹狀結構(Tree Structure) : 電腦內部檔案儲存 的結構，或是歷屆學生的家族族譜，羽球比 賽的單循環賽程資料等 Binary (search) Tree Why binary (or ones with limited branches)? Implementation? Pro & con? AVL Tree? B-Tree Why it’s good? Add & delete entries

12 資料結構 - review

13 資料結構 - review 圖形及網路 : 全台灣省的省道與高速公路路 線圖、環島鐵路的路線圖、長榮航空公司的 全球航線圖
Graph or network? Representation? Min. cost spanning tree? Shortest path algorithm? Greedy Algorithm? Spanning Tree Protocol

14 資料結構 - review 排序(Sorting) & 搜尋 (Searching) Why sorting?
Bubble sort / Quick sort / Heap sort? Divide & conquer algorithm & quick sort? Searching & 斤斤計較

15 資料結構 - review 赫序函數(Hashing Function) : 利用一種技術 將特定的資料例如某一個學生的學號輸入， 就可以馬上找出他家裡的電話號碼、地 址，… Other applications?

16 資料結構 – final words 難嗎？

17 終身學習的能力 Being adaptable in a flat world, knowing how to learn how to learn will be one of the most important assets any worker can have, because job churn will come faster, because innovation will happen faster By Thomas Friedman, The World is Flat

18 認知理論 2019/5/20

19 Definitely the Final Words (of Wisdom) …
“Someday, in the distant future, our grandchildren's grandchildren will develop a new equivalent of our classrooms. They will spend many hours in front of boxes with fires glowing within. May they have the wisdom to know the difference between light and knowledge.” Plato (柏拉圖)？

20 Farewell & See You