DataStructure资料结构.ppt

Data Structure 資料結構 副教授 翁志祁 義0321(星期三: 02-04) 結束 課程簡介 本課程在使同學瞭解各種資料結構，如Stacks, Queues, Linked Lists, Trees, Hash, Graph等。 並使 同學熟悉對這些資料結構的搜尋、讀寫 、插入、刪除 的演算法(algorithm)。更重要的是使學生在利用這些 資料結構及演算法解決問題時，同時能夠評估記憶體 使用空間和執行時間的複雜度(Complexity)。最終目 標是要讓同學能根據問題，選擇適當的資料結構及演 算法，正確地、且有效率地去解決問題。 結束 參考書籍與教學網站 lData Structures and Program Design in C,Kruse, Tondo, Leung, 全華圖書,2597-1300x338 l資料結構使用C語言，吳勁樺著. 金禾資訊(02)2789- 0561 l本課程教材可至下列網址下載: .tw/cweng/ l因為教材內容正在陸續的更新中，所以只需下載最 近要用到的章節。 結束 成績比重和輔導時間 期中考試 30% 期末考試 40% 平時成績 30%(含出席、作業、測驗) 星期一12:0013:00 星期二14:0016:00 星期三12:0013:00 星期四15:0017:00 結束 第一章 資料結構導論 本章重點 l認識資料與資訊 l演算法(Algorithm) l程式(program)與程式設計(programming) l演算法的效能分析 結束 1. 認識資料與資訊 資料(Data)，指的就是一種未經處理的原始文 字(Word)、數字(Number)、符號(Symbol)或 圖形(Graph)等，它所表達出來的只是一種沒 有評估價值的基本原素或項目。例如姓名或我 們常看到的課表、通訊錄等等都可泛稱是一種 資料。 結束 資料處理 資料處理就是用人力或機器設備，對資料進行 有系統的整理如記錄、排序、合併、整合、計算 、統計等，以使原始的資料符合需求，而成 為有用的資訊(Information) 結束 資料結構 l資料結構是在資料處理過程中，一種分析、組織資 料的方法(algorithm)與邏輯(logic)。它考慮到了資料 間的特性與相互關係(relationship)。 l程式設計師必須選擇一種資料結構來進行資料的新 增、修改、刪除、儲存等動作，如果在選擇資料結 構時作了錯誤的決定，那程式執行起來的速度將可 能變得非常沒有效率 。 結束 資料和資訊的角色是否一成不變 l不一定。同一份文件可能在某種況下為資料，而在 另一種狀況下則為資訊。 l例如美伊戰爭的戰役死傷人數報告，對你我這些平 民百姓而言，當然只是一份不痛不癢的資料 (Data)；不過對於英美聯軍指揮官而言，這份報份 可就是彌足珍貴的資訊(Information)。 結束 2.演算法(Algorithm) l資料結構加上演算法等於可執行程式。 l演算法在韋氏辭典定義為：在有限步驟內解 決數學問題的程序。 l在計算機領域可以把演算法定義成：為了解決某 一個工作或問題，所需要有限數目的機械性或重覆 性指令與計算步驟。 結束 演算法五個條件 l輸入(Input)：0個或多個輸入資料，這些輸入必需 有清楚的描述或定義。 l輸出(Output)：至少會有一個輸出結果，不可以沒 有輸出結果。 l明確性(Definiteness)：每一個指令或步驟必需是 簡潔明確而不含糊的。 l有限性(Finiteness)：在有限的步驟後一定會結束 ，不會產生無窮迴路。 l有效性(Effectiveness)：步驟清楚且可行，能讓使 用者用紙筆計算而求出答案。 結束 演算法常用的表現方法 l一般文字：中文、英文、數字等。 l虛擬語言：接近高階程式語言的寫法，經常使用的有 SPARKS、PASCA-LIKE等語言。 l表格或圖形：如陣列、樹狀圖、矩陣圖等。 l流程圖：資料流程圖)及控制流程圖可以算是一種通用的表 示法，也有固定的圖型符號。 l程序語言：目前資料結構的演算法經常是以可讀性高的高 階語言來表示，例如C語言、C+語言、Java語言、Visual Basic語言等，在本書中將以C語言來表達演算法 結束 演算法、程式、與流程圖的異同 l演算法和程序是有所區別，因為程式不一定要滿足 有限性的要求，如作業系統或機器上的運作程式； 除非當機，否則永遠在等待迴路(waiting loop)或記 錄機器運作狀況，這也違反了演算法五大原則之一 的有限性。 l只要是演算法都能夠利用程式流程圖表現，但因為 程式流程圖可包含無窮迴路，所以無法利用演算法 來表達。 結束 3. 程式(program)與程式設計(programming) 程式產生的五個階段: l需求認識：了解程式所要解決的問題是什麼，有那些 輸入及輸出等。 l設計規劃：根據需求，選擇適合的資料結構，並以任 何的表示方式來寫一個演算法以解決問題。 l分析討論：思考其他可能的演算法及資料結構，最後 再做出最適當的選擇。 l編寫程式：把分析的結論，寫成初步的程式碼。 l測試檢驗：最後必需確認程式的輸出是否符合需求， 這個步驟得細步的執行程式並進行許多的相關測試。 結束 它又分為三種基本結構(Basic Structure)： 基本結構名稱 概念圖 循序結構 逐步的撰寫敘述 選擇結構 依某些條件做邏輯斷 重複結構 依某些條件決定是否重複 執行某些敘述。 結構化程式設計 結束 結構化程式設計的優缺點 l優點：由上而下法讓程式可讀性更高，對於日 後修改維護幫助很大。再加上模組化的設計能 讓設計者分工合作，降低開發成本。 l缺點：由於維持可讀性高的要求，必須有較多的指 令，容易佔用記憶體空間，與非結構程式設計相比 ，執行速度也會較慢。 結束 q基本資料型態(atomic data type)或稱為 實質資料型態(physical data type) q結構型資料型態(structure data type)或 稱為虛擬資料型態(virtual data type) q抽象資料型態(Abstract Data Type：ADT) 資料儲存層次的分類 結束 基本資料型態 l一個基本的資料實體，例如一般程式語言中的整數 、實數、字元等等。基本上，每種語言都擁有略微 不同的基本資料型態。像C語言的基本資料型態為 整數(int)、字元(char)、單精度浮點數(float)與倍精 度浮點數(double)。 結束 結構型資料型態 l比實質資料型態更高一層，是指一個資料實體包含 其他的資料型態，例如字串(string)、集合(set)、陣 列(array)。 結束 抽象資料型態 l比結構型資料型態更高一層，ADT是指定義一些結 構型資料型態所具備的數學運算關係。也就是說， 使用者毋需考慮到ADT的製作細節，只要知道如何 使用即可。例如堆疊(stack)或佇列(queue)就是一種 很典型的ADT模式。 結束 4. 演算法的效能分析 Given a problem, there may be several possible implementations. Efficiency is the most important consideration including time and space. lComplexity Theory to estimate the time and space needed for a program. Its machine independent. lSpace Complexity of a program the amount of memory space needed to complete a program. lTime Complexity of a program the amount of computation (computer) time needed to complete a program. 結束 Space Complexity S(p) S(p)=Sc+Sp(I) lSc (Fix space requirement) including instruction space, constants, simple variables, and fix-size structures. The Sc is independent of the number and size of inputs and outputs. e.g. int i, sum=0, A100; lSp(I) (Variable space requirement) depends on a particular instance I of a problem. Instance I may be a function of number, size, or values of inputs and outputs. e.g. int *n; /score list of a course 結束 Time Complexity T(p) T(p)=Tc+Tp(I) lTc (Fix time requirement) compile time, Tc is independent of any instance of the problem. lTp(I) (Variable time requirement) execution time, depends on a particular instance I of a problem. e.g. matrix multiplication C =A *B (0,0) 0,1 0,2 0,3 0,n 0,0 1,0 2,0 n,0 (n*) + (n+) = 2n 2n* n*n + an2+bn+c = 2n3 +an2+bn+c 結束 Asymptotic Notations - for measuring space and time complexities lO(Big-oh) l(omega) l(theta) 結束 Big-oh的介紹 lO(g(n)可視為某演算法在電腦中所需執行時間不會 超過某一常數倍的g(n)，也就是說當某演算法的空 間或時間複雜度(space or time complexity)為O(g(n)( 讀成big-oh of g(n)或order is g(n)。 lDefinition: The function f(n) is said to be of order at most g(n) if there are positive constants c and n0 such that f(n)=n0. lTherefore, “Big oh” is the smallest upper bound of f(n). 結束 常見的Big-oh有下列幾種： lO(1)：稱為常數 (constant) lO(log2n)：稱為 (logarithmic) lO(log22n)：稱為 (log squared) lO(n)：稱為線性 (linear) lO(nlog2n)：稱為n log n lO(n2)：稱為平方 (quadratic) lO(n3)：稱為立方 (cubic) lO(2n)：稱為指數 (exponential) 結束 結束 (omega)的介紹 l也是一種複雜度的漸近表示法，如果說Big-oh是 執行時間量度的最壞情況，那就是執行時間量度 的最好狀況。以下是的定義： lDefinition: The function f(n) is said to be of order at least g(n) if there are positive constants c and n0 such that f(n)=cg(n) for all n, n=n0. lTherefore, “Big oh” is the largest lower bound of f(n). 結束 (theta)的介紹 l是一種比Big-O與更精確複雜度的漸近表示法。 定義如下： lDefinition: The function f(n) is (g(n) iff there exists positive constants c1, c2 and n0 , such that c1 g(n) =n0. lTherefore, “” is both the smallest upper bound and the greatest lower bound of f(n). 結束 Examples for asymptotic notations 1. 3n + 2 = (n), 3n +2 4n, for all n 2, c = 4. 2. 3n + 3 = (n), 3n +3 4n, for all n 3, c = 4. 3. 3n + 3 = (n2), 3n +2 3n2, for all n 2, c = 3. (2) is correct. (3) is wrong. “Big oh“ should be a smaller function of n. 4. 10n2 + 4n +2 = (n2), 10n2 + 4n +2 11n2, for all n 5, c = 11. 5. 62n + n2 = (2n), 62n + nn 72n, for all n 4, c = 7. 6. 3n +3 = (n), 3n +3 3n, for all n 1, c = 3. 7. 3n +3 = (1), 3n +3 3, for all n 1, c = 3. (6) is correct. (7) is wrong. “Omega” should be a larger function of n. 8. 3n +2 = (n) 3n3n +2 4n, for all n 2, c1 = 3, c2= 4 , and n0= 2. 結束 Example for S(p): addup values of n elements in an array called list. main( )float addup(float list , int n) float listn, temp = 0.0;float temp = 0.0; int i;int i; for( i=0; i step count = 2*n +3 = Tsum(n) = O(n) 結束 2. Tabular method void add( int a , int b , int c , int row, int col) Step per exec. freq. total int i, j; 0 0 0 for ( i=0; i Tadd(row, col) = O(row*col) Thus, if row col, one may want to exchange i and j to reduce the step count and execution time. 結束 3. Execution time Measurement #include 1. Clock2. Time Before execution, usestart = clock();start = time(NULL); After execution, usestop = clock();stop = time(NULL); Type returnclock_ttime_t result in sec. (stop - start)/ CLK_TCK;difftime(stop, start); When measuring the execution of a program, we have CLK_TCK= 18.2, beginclk = 66, stopclk = 193, diffclk = 127, tim