資料結構簡介 2009.04 綠園.

Presentation on theme: "資料結構簡介 2009.04 綠園."— Presentation transcript:

1 資料結構簡介 綠園

2 資料與資訊 資料： 指一種未經處理的原始文字、數字、符號 或圖形。 資訊：
指一種未經處理的原始文字、數字、符號 或圖形。 資訊： 當資料經過特定的方式有系統的整理、歸　 納甚至進行分析後，就成為「資訊」。而 這處理過程就稱為「資料處理」。

3 資料與資訊 整理 + 分析 (演算法 + 資料結構) 電 腦 化 資料 資訊 【處理過程】

4 演算法與資料結構 資料結構與演算法是程式設計中最基本的內涵。 程式能否快速而有效率的完成預定的任務，取決於是否選對了資料結構。
程式是否能清楚而正確的把問題解決，則取決於演算法。 資料結構 + 演算法 = 可執行的程式

5 演算法(Algorithm)的條件 輸入(Input)：0個或多個輸入資料，這些輸入必須有清楚的描述或定義。
輸出(Output)：至少會有一個輸出結果，不可以沒有輸出結果。 明確性(Definiteness)：每一個指令或步驟必須是簡潔明確而不含糊的。 有限性(Finiteness)：在有限步驟後一定會結束，不會產生無窮迴路。 有效性(Effectiveness)：步驟清楚且可行，能讓使用者用紙筆計算而求出答案。

6 演算法效能分析 一個演算法效能的評估，經常是從時間與空間兩種因素來考量。 時間方面是指程式的執行時間，稱為「時間複雜度」。
空間方面則是指程式在電腦記憶體所佔的空間大小，稱為「空間複雜度」。 由於電腦硬體進展的日新月異及所使用電腦的不同，一般以演算法的執行時間為主要評估與分析的依據。

7 時間複雜度 O Big-oh：f(n)=O(g(n)) (讀作 Big-oh of g(n) 或 order is g(n))
某演算法在電腦中所需執行時間 f(n) 不超過某一常數倍的 g(n) ，稱 f(n) 的時間複雜度為 O(g(n)) 。 意謂存在兩個常數 c 與 n0 ， 對所有n ≥ n0， f(n) ≤ cg(n) 均成立。

8 時間複雜度範例一 【陣列元素相加】 執行次數 int sum(int arr[], int n) { int i, total=0; 1
　　 執行次數 int sum(int arr[], int n) { int i, total=0; for (i=0; i<n; i++) n+1 total += arr[i]; n return total; } ____________________________________________ 2n+3 　　則 f(n)=2n+3，存在c=5,n0=1， 　　 2n+3 ≤ 5n，因此 f(n)=O(n) 。

9 時間複雜度 O 就執行時間而言， O(1)為常數，O(n)為線性時間， O(n2)為二次函數，O(n3)為三次函數， O(2n)為指數，
這些漸近式為時間複雜度提供了一個度量的標準，我們可以証明： O(1)＜O(㏒n)＜O(n)＜O(n㏒n)＜O(n2)＜O(n3)＜O(2n)

10 時間複雜度 Ω big-omega Ω ： f(n) = Ω(g(n)) 如果說Big-oh是執行時間量度的最壞情況，
那 Ω 就是執行時間量度的最好情況。 意謂存在兩個常數 c 與 n0 ， 對所有n ≥ n0， f(n) ≥ cg(n) 均成立， 則稱 f(n) = Ω(g(n))。

11 時間複雜度 Θ big-theta Θ ： f(n) = Θ(g(n)) 意是存在常數 c1、c2 與 n0 ， 對所有的n ≥ n0 時，
c1g(n) ≤ f(n) ≤ c2g(n) 均成立， 則稱 f(n) = Θ(g(n))。

12 時間複雜度範例一 【陣列元素相加】 執行次數 int sum(int arr[], int n) { int i, total=0; 1
　　 執行次數 int sum(int arr[], int n) { int i, total=0; for (i=0; i<n; i++) n+1 total += arr[i]; n return total; } ____________________________________________ 2n+3

13 時間複雜度範例二 【矩陣相加】 執行次數 void add (int a[][], int b[][], int c[][], int n)
　　　　　執行次數 void add (int a[][], int b[][], int c[][], int n) { for (int i=0; i < n; i++) 　　　　n+1 for (int j=0; j < n; j++) 　 n(n+1) c[i][j] = a[i][j] + b[i][j] 　 n2 } ____________________________________________ 　　　　　2n2+2n+1 　　則 f(n)= 2n2+2n+1 ，存在c=5,n0=1， 　　 2n2+2n+1 ≤ 5n2，因此 f(n)=O(n2) 。

14 時間複雜度範例三 【矩陣相乘】 執行次數 void mul(int a[][], int b[][], int c[][], int n)
　　　　　執行次數 void mul(int a[][], int b[][], int c[][], int n) { int i, j, k, sum; for (i = 0; i < n; i++) n+1 for (j = 0; j < n; j++ ){ n(n+1) sum = 0; n2 for ( k = 0; k < n; k++ ) n2(n+1) sum = sum + a[i][k] * b[k][j]; n3 c[i][j] = sum; n2 } _________________________________________________ 　　　　　2n3+4n2+2n+2

15 資料結構 (Data Structure) 一個好的程式除了必須使用良好的演算法之外，也需要使用適當的資料結構來組織資料，才能節省資料的儲存空間，並提昇資料處理的速度。 資料結構是用來組織及管理資料的結構設計。 資料結構主要是在定義資料的放置方法及存取規則。

16 資料結構 (Data Structure) 續一
將資料作有系統的安排與組織，使資料建立成為一種便於取用與處理的結構，稱為資料結構。 資料依儲存層次上的不同可分為三種： 基本型資料型態(Atomic Data Type)： 字元(char)、整數(int)、實數(float)、布林(bool) 結構型資料型態(Sturcture Data Type)： 字串（string)、陣列(array)、結構(struct) 抽象型資料型態(Abstract Data Type)： 類別(class)、堆疊(stack)、佇列(queue)

17 資料結構 (Data Structure) 續二
典型的資料結構如下： 資料表格(Table) 堆疊(stack) 佇列(queue) 串列(list) 樹(tree) 圖形(graph) table, stack, queue：可用陣列表現出來。 list, tree, graph：適合用指標表現出來。