[工學]數(shù)據(jù)結(jié)構(gòu)課件c版第一章(編輯修改稿)
2024-11-15 00:03 本頁面
【文章內(nèi)容簡介】 x, y) : NaturalNumber //前置條件： x, y為 NaturalNumber且 x+y≤MaxInt //后置條件：返回 x+y Subtract (x, y) : NaturalNumber //前置條件： x, y為 NaturalNumber且 x≥y //后置條件：返回 x y Data Structure— Ch1 Introduction 2021/11/10 mayan 抽象數(shù)據(jù)類型概念 抽象數(shù)據(jù)類型的定義 Equal (x, y) : Boolean //前置條件： x, y為 NaturalNumber //后置條件： if (x == y) 返回 True else 返回 False Successor (x) : NaturalNumber //前置條件： x為 NaturalNumber //后置條件： if (x == MaxInt) 返回 x else 返回 x+1 end NaturalNumber Data Structure— Ch1 Introduction 2021/11/10 mayan 抽象數(shù)據(jù)類型概念 抽象數(shù)據(jù)類型的表示與實現(xiàn) 抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。 從 C語言的角度理解，它有些類似 C語言中的結(jié)構(gòu)（ struct)類型，但增加了相關的服務。從 C++的角度理解，通過模板類來實現(xiàn)它。 在上機時要用具體語言實現(xiàn)，如 C或 C++等。 模板 (template)：適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法定義 ? 算法定義 ? 算法特性 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法定義 定義與特性 ? 定義：一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列。 ? 算法的特性： ? 有輸入 ：有 0個或多個輸入。 ? 有輸出 ：有一個或多個輸出 (處理結(jié)果 )。 ? 確定性：算法中每一條指令必須有確切的含義。不存在二義性。 ? 有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。 ? 可行性：一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 ? 評價算法的性能標準 ? 算法效率的度量 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 評價算法的性能標準 ? 評價一個好的算法有以下幾個標準 : ?正確性 (Correctness )：算法應滿足具體問題的需求。 ?可讀性 (Readability)：算法應該好讀。以有利于閱讀者對程序的理解。 ?健壯性 (Robustness)：算法應具有容錯處理。當輸入非法數(shù)據(jù)時，算法應對其做出反應，而不是產(chǎn)生莫名其妙的輸出結(jié)果。 ?效率（ Efficiency）：效率指的是算法執(zhí)行的時間和空間利用率。一般，這兩者與問題的規(guī)模有關。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 算法分析的目的在于分析算法的效率以求改進，算法分析的兩個主要方面是時間復雜度和空間復雜度。 ? 對一個算法要作出全面的分析可分成兩個階段進行，即事前分析和事后測試。 ?事前分析要求事前求出該算法的一個時間界限函數(shù)。 ?事后測試則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分析。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 算法的事后統(tǒng)計 事后分析要求在算法中的某些部位插裝時間函數(shù)time ( )，測定算法完成某一功能所花費時間。 插裝 time( ) 的計時程序 double start, stop。 time(amp。start)。 int k = seqsearch (a, n, x)。 time(amp。stop)。 double runTime = stop start。 cout n runTime endl。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 事實上，算法運行時間要受輸入規(guī)模、利用編譯程序生成的目標代碼的質(zhì)量、計算機程序指令系統(tǒng)的品質(zhì)和速度等制約。 Data Structure— Ch1 Introduction 2021/11/10 mayan 算法性能分析與度量 算法效率的度量 ? 算法的事前估計 算法的事前估
教學課件相關推薦
鄂ICP備17016276號-1