講師:郭育倫 d95037@csie.ntu.edu.tw 第3章 基本資料結構 講師:郭育倫 d95037@csie.ntu.edu.tw.

Presentation on theme: "講師:郭育倫 d95037@csie.ntu.edu.tw 第3章 基本資料結構 講師:郭育倫 d95037@csie.ntu.edu.tw."— Presentation transcript:

1 講師:郭育倫 d95037@csie.ntu.edu.tw
第3章 基本資料結構 講師:郭育倫

2 演算法導論，探矽工作室 本章學習重點 鏈結串列 堆疊 佇列 二元樹

3 摘要 程式 v.s. 適當的資料結構 回顧基本資料結構 讓程式容易維護 較高的執行效率 減少額外的記憶體空間
演算法導論，探矽工作室 摘要 程式 v.s. 適當的資料結構 讓程式容易維護 較高的執行效率 減少額外的記憶體空間 回顧基本資料結構 鏈結串列（linked list） 堆疊（stack） 佇列（queue） 二元樹（binary tree）

4 鏈結串列 陣列 v.s. 鏈結串列 單向鏈結串列 v.s. 雙向鏈結串列 環狀鏈結串列 基本操作 初始化 搜尋（線性時間） 插入 刪除
演算法導論，探矽工作室 鏈結串列 陣列 v.s. 鏈結串列 單向鏈結串列 v.s. 雙向鏈結串列 環狀鏈結串列 基本操作 初始化 搜尋（線性時間） 插入 刪除

5 演算法導論，探矽工作室 範例：鏈結串列的插入

6 演算法導論，探矽工作室 範例：鏈結串列的刪除

7 堆疊 先進後出（first in and last out，FILO） 實作方式 基本操作 陣列 鏈結串列 初始化 判斷狀態（空的？滿的？）
演算法導論，探矽工作室 堆疊 先進後出（first in and last out，FILO） 實作方式 陣列 鏈結串列 基本操作 初始化 判斷狀態（空的？滿的？） 堆入（push） 取出（pop）

8 演算法導論，探矽工作室 範例：堆疊的 pop & push

9 佇列 先進先出（first in first out，FIFO） 實作方式 基本操作 陣列 鏈結串列 環狀佇列（ring queue）
演算法導論，探矽工作室 佇列 先進先出（first in first out，FIFO） 實作方式 陣列 鏈結串列 環狀佇列（ring queue） 基本操作 初始化 判斷狀態（空的？滿的？） 放入資料（enqueue） 取出資料（dequeue）

10 範例：佇列的dequeue & enqueue
演算法導論，探矽工作室 範例：佇列的dequeue & enqueue

11 演算法導論，探矽工作室 樹 定義 一棵樹t可看成是一個非空的有限元素之集合，每個元素稱為節點（node），其中一個元素稱為根節點（root），或稱為樹根，剩下的元素（如果有的話）組成t的子樹（subtree） 這種包含根節點的樹也稱為有根樹（rooted tree） 節點之間的關係 節點之間的邊線（edge）代表兩者之間的階層關係 父節點（parent）、子節點（children）、兄弟節點（sibling） 沒有任何子節點的節點稱為樹葉（leaf），或稱為葉子 有任何子節點的節點稱為內部節點（internal node）

12 樹的其它性質 n元樹（multi-way tree） 階層（level） 深度（depth） 高度（height）
演算法導論，探矽工作室 樹的其它性質 n元樹（multi-way tree） 每個節點最多可允許n個子節點 階層（level） 樹根的階層為1，其子節點的階層為2，子節點的子節點為3 … 深度（depth） 樹根到此節點的路徑之長度，也就是經過多少個邊線 高度（height） 此節點到以此節點為樹根的子樹其最遠樹葉路徑的長度

13 演算法導論，探矽工作室 老王後代的樹狀族譜圖 最多到第3階層 樹的高度為2 節點小洋的深度為2 節點阿昌的高度為1

14 二元樹 定義 常見的應用 二元樹是樹的一個特例（但是允許是空的）
演算法導論，探矽工作室 二元樹 定義 二元樹是樹的一個特例（但是允許是空的） 每個節點最多只有二棵子樹，有左右之分，分別稱作左子樹（left subtree）和右子樹（right subtree），次序不能顛倒 常見的應用 （二元）堆積 二元搜尋樹

15 二元樹的特性 包含n個節點的二元樹，剛好有n-1個邊 在一棵二元樹的第i層最多有2i − 1個節點
演算法導論，探矽工作室 二元樹的特性 包含n個節點的二元樹，剛好有n-1個邊 在一棵二元樹的第i層最多有2i − 1個節點 高度為k的二元樹最多有2k+1 − 1個節點，最少有k+1個節點 包含n個節點的二元樹，其高度最大為n-1，最小為log2n

16 滿二元樹（full binary tree）
演算法導論，探矽工作室 滿二元樹（full binary tree） 一棵二元樹的高度為k且有2k+1 − 1個節點 最底層的節點都是葉子，其它層的節點都有2個子節點 可以對這棵滿二元樹的每個節點，依照由上到下、由左到右的順序，從0到2k+1 − 2進行編號

17 演算法導論，探矽工作室 高度(深度)為3的滿二元樹

18 完整二元樹(complete binary tree)
演算法導論，探矽工作室 完整二元樹(complete binary tree) 定義 一棵有n個節點的二元樹，按滿二元樹的編號方式對它進行編號，樹中所有節點和滿二元樹0到n-1編號完全一致 特性 有n個節點，則其深度為log2n 有n個節點，則其高度為h的節點最多有n/(2h+1)個，最少有0個（當n=0時），0 ≤ h ≤ log2n

19 完整二元樹(續) 深度為k，則它最少有2k個節點，最多有2k+1 − 1個節點。
演算法導論，探矽工作室 完整二元樹(續) 深度為k，則它最少有2k個節點，最多有2k+1 − 1個節點。 對於某個編號為i的節點，0 ≤ i ≤ n-1，則以下關係成立（當然，對滿二元樹也會成立）： 若編號i的節點不是樹根，其父節點的編號為(i-1)/2 編號i的節點，其左子節點的編號為i×2+1 編號i的節點，其右子節點的編號為i×2+2

20 演算法導論，探矽工作室 完整二元樹的範例

21 二元樹的實作方式 陣列 指標 優點 缺點 每個節點包括鍵值，以及指向左、右子節點的指標 一般二元樹都採用此方法
演算法導論，探矽工作室 二元樹的實作方式 陣列 優點 用數學計算即可得知某節點的父節點、左子節點、右子節點在陣列中的索引值 常用於完整二元樹(e.g.堆積) 缺點 空間的浪費 指標 每個節點包括鍵值，以及指向左、右子節點的指標 一般二元樹都採用此方法

22 演算法導論，探矽工作室 以陣列表示右傾斜二元樹？

23 二元樹的操作 配置新節點和初始化 加入節點 刪除節點 調整樹狀結構 搜尋某個鍵值相符合的節點 尋訪（traversal）
演算法導論，探矽工作室 二元樹的操作 配置新節點和初始化 加入節點 刪除節點 調整樹狀結構 搜尋某個鍵值相符合的節點 尋訪（traversal）

24 演算法導論，探矽工作室 二元樹的尋訪 常見的方法 前序尋訪、中序尋訪、後序尋訪 尋訪過程中，每個節點只會被拜訪（visit）過一次，並在尋訪時執行對該節點的所有運算，因此其時間和空間複雜度都為O(n) 可能的運算 列出所有節點的鍵值 統計節點的個數 刪除所有節點 ….

25 前序尋訪 void preOrder(NODE *ptr){ if(ptr){
演算法導論，探矽工作室 前序尋訪 void preOrder(NODE *ptr){ if(ptr){ visit(ptr);/* 處理以ptr為樹根的子樹主體 */ preOrder(ptr->left);/* 尋訪左子樹 */ preOrder(ptr->right);/* 尋訪右子樹 */ }

26 中序尋訪 void inOrder(NODE *ptr){ if(ptr){
演算法導論，探矽工作室 中序尋訪 void inOrder(NODE *ptr){ if(ptr){ inOrder(ptr->left);/* 尋訪左子樹 */ visit(ptr);/* 處理以ptr為樹根的子樹主體 */ inOrder(ptr->right);/* 尋訪右子樹 */ }

27 後序尋訪 void postOrder(NODE *ptr){ if(ptr){
演算法導論，探矽工作室 後序尋訪 void postOrder(NODE *ptr){ if(ptr){ postOrder(ptr->left);/* 尋訪左子樹 */ postOrder(ptr->right);/* 尋訪右子樹 */ visit(ptr);/* 處理以ptr為樹根的子樹主體 */ }

28 演算法導論，探矽工作室 結論 資料結構是儲存與組織資料的一種方式，可用來加速資料的存取與修改 介紹鏈結串列、堆疊、佇列、二元樹