演算法與資料結構 製作單位: 高雄市立高雄中學.

Presentation on theme: "演算法與資料結構 製作單位: 高雄市立高雄中學."— Presentation transcript:

1 演算法與資料結構 製作單位: 高雄市立高雄中學

2 演算法 演算法的基本定義 應用方法和技巧來解決問題 如: 在地圖中找最短路徑 演算法設計前的步驟 了解問題分析解決步驟

3 演算法的表示方法 文字 流程圖 虛擬碼 自然語言 1+2+3+4+5+6+7+8+9=? 1. 令count=1，sum=0
2. sum=sum+count 3. count=count+1 4. if count> 9 then 執行(5) else 執行(2) 5. print sum 開始 總和＝0 count＝0 總和＝總和＋count count＝count＋1 count＞100 列印總和 結束 Y N

4 搜尋演算法的比較 搜尋演算法 依序搜尋法 二分搜尋法 〔2,5,11,34,22,7〕 搜尋出“22”
從第一個開始找起直到找到, 適用於未排序的資料 二分搜尋法 排序好的資料 與中位數做比較

5 排序演算法的比較 排序演算法 排序演算法的比較 交換排序法 選擇排序法 插入排序法 合併排序法 快速排序法 排序法名稱 優點 缺點
Exchange 交換次數很多 Insertion 適用於數列較小的情況 最耗時間 Merge 運作的時間最快 須要額外的空間來處理 Quick 須要額外空間來處理，但沒有Merge Sort須要的空間多。

6 交換排序法 拿第一個數與其他數做比較，只要數字比第一個小，則兩數交換，當全部的數都比過之後，最小數即找出，且放在第一個位置
排序法的比較 交換排序法 拿第一個數與其他數做比較，只要數字比第一個小，則兩數交換，當全部的數都比過之後，最小數即找出，且放在第一個位置 適用於未排序的資料 如〔27,7,2,9,4,85〕

7 排序法的比較 選擇排序法 搜尋出最小的，放在第一個位置，第二小的放在第二個位置，直至全部都排列完成 交換的次數較少

8 排序法的比較 插入排序法 用途在於將數字插入已排序的數列中

9 合併排序法 1.將數列分成兩個子數列，每一個數列擁有n/2個數字。
排序法的比較 合併排序法 1.將數列分成兩個子數列，每一個數列擁有n/2個數字。 2.排列每一個子數列，除非此子數列夠小（只剩一個數字），否則再繼續重覆（1）。 3.結合每一個子數列使之成為單一數列

10 快速排序法 先找一個指標（為求方便，通常是第一個數），將數列中大於這個指標的數，都放在右邊，反之則放在左邊
排序法的比較 快速排序法 先找一個指標（為求方便，通常是第一個數），將數列中大於這個指標的數，都放在右邊，反之則放在左邊 和合併排序法相似，但快速排序法的優點是比較節省空間

11 資料結構 何謂資料 陣列結構 資料就是一堆沒有經過整理的數據 資料結構就是，將資料先放在記憶體中，等有需要用的時候，再拿出來使用
一維陣列 Dim money(49) As Integer 二維陣列 Dim money(0 To 49) As Integer 多維陣列 Dim A(0 To 3 ,0 To 2) As Integer 字串陣列 Dim B(0 To 3,0 To 4,0 To 5,0 To 6) As Integer

12 資料結構—堆疊佇列與串列 堆疊 佇列 鏈結串列 後進先出（Last In First Out, LIFO） 如堆積木
堆疊的應用: 河內塔, 前序式or後序式or排序式 佇列 先進先出（First In First Out, FIFO） 如排隊 鏈結串列 單向鏈結 雙向鏈結 data link link data

13 樹狀結構 樹根（root） 節點（node） 子樹（subtree） 樹林（forest） 父節點（parent）
子節點（children） 終點節點（terminal node） 分支度（degree） 階度（level）

14 圖形結構