大學信息技術基礎——軟件設計基礎（第六章）算法是處理問題的策略

數據結構是問題的數學模型

數據結構+算法=程序6.1.1算法的基本概念算法是對問題解決步驟的描述程序可以作為算法的一種描述，但通常程序的編制不可能優(yōu)于算法的設計可行性確定性有窮性輸入輸出（一個算法可以有一個或多個輸出）1：什么是算法2：算法的特性6.1算法與程序6.1.2算法的表示自然語言——歧義性傳統(tǒng)流程圖起止框——輸入、輸出框——處理框——連接點——N-S圖順序結構選擇結構當型循環(huán)——注意：這種循環(huán)可能一次都不被執(zhí)行直到型循環(huán)——注意：這種循環(huán)至少被執(zhí)行一次6.1算法與程序6.1.2算法的表示偽代碼——介于自然語言和計算機語言間的算法描述工具計算機程序設計語言算法可以與計算機無關6.1算法與程序6.1.3算法設計的基本方法列舉法（窮舉法或枚舉法）掃描所有的可能性歸納法—— 列舉一些一般性的情況，經過分析，總 結出一般性的關系遞推法—— 從已知的初始條件出發(fā)，逐次推出各個 中間結果和最后結果遞歸法—— 將問題逐漸分解到最后的簡單問題，再 沿著分解的逆過程逐步綜合，直到解決 原問題遞歸法的程序舉例Publicdoublefactorial(intnum){ switch(num) { case1: return1; default: returnnum*factorial(num-1); }}6.1.3算法設計的基本方法分治法對問題分而治之回溯法—— 對解決問題的可能性的樹形采用線路嘗 試，如果不行再回溯嘗試的方法，常見 的是下棋的算法6.1.4算法的評價正確性執(zhí)行結果滿足預先規(guī)定的功能和性能要求可讀性—— 易讀易懂健壯性—— 對非法輸入數據做出恰當的反應或處理復雜性—— 所需計算機資源的多少時間復雜性：程序在計算機上運行所花費的時間空間復雜性：指執(zhí)行這個算法所需的內存空間6.1.5程序與程序設計語言程序程序包含兩方面：對象間的關系（數據結構），對象進行處理的加工規(guī)則（算法）程序設計語言機器語言—— 由二進制代碼組成，是唯一可以直接在 計算機上執(zhí)行的語言匯編語言—— 用助記符代替機器語言，是面向機器語 言，不同類型計算機，匯編語言不同6.1.5程序與程序設計語言高級語言——與機器指令系統(tǒng)無關第一種高級語言——FORTRAN編譯程序：一次性將源程序翻譯成目標程序，經過鏈接后產生可執(zhí)行程序解釋程序：指令逐條翻譯，逐條執(zhí)行編譯程序的執(zhí)行效率高于解釋程序6.2數據結構數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構

各數據元素在計算機中的存儲關系，即數據的存儲結構

對各種數據結構的運算6.2.1數據結構的基本概念數據數據元素（作為一個整體考慮的數據）數據對象（性質相同數據元素的集合）數據類型（值的集合及集合上的操作的總稱）數據結構是指相互間存在一定關系的數據元素的集合以及定義在其上的操作數據的邏輯結構是指反映數據元素間邏輯關系的數據結構6.2.1數據結構的基本概念數據的邏輯結構中要掌握的概念：前件、后件根節(jié)點、終端節(jié)點數據的存儲結構邏輯上相鄰的數據并不一定存儲在一起存儲結構上的基本操作插入、刪除、更新、查找、排序、遍歷6.2.2線性結構主要的數據結構：線性表、棧、隊列、鏈表特定：線性表——順序存儲結構棧 —— 先進后出隊列 —— 先進先出鏈表 —— 便于插入和刪除數據6.2.3非線性結構非線性結構主要包括：二叉樹的遍歷：先序遍歷、中序遍歷、后序遍歷

先序遍歷：根-左-右中序遍歷：左-根-右后序遍歷：左-右-根6.3程序設計方法6.3.1 程序設計的一般過程問題描述、算法設計、代碼編制、調試運行

編寫程序文檔

6.3.2 結構化程序設計結構化程序的基本結構與設計思想任何算法都可以由三種基本結構：順序、選擇、循環(huán)的組合來完成結構化設計的思想是以模塊化設計為中心模塊的基本特征：只有一個入口和一個出口6.3.2 結構化程序設計結構化程序的基本原則自頂向下，逐步求精單入口、單出口限制使用goto語句6.3.3面向對象程序設計面向對象的程序設計（OOP）起源Smalltalk語言常見的OOP語言：VisualBasic,VisualC++,

Java,Dephi等面向對象的一些基本概念類、對象、屬性、方法、事件、事件過程、事件驅動6.3.3面向對象程序設計面向對象程序設計的特點抽象數據抽象——反應對象的靜態(tài)特征行為抽象——反應對象的動態(tài)特征封裝繼承多態(tài)6.4軟件工程軟件工程的基本概念軟件的定義與特點軟件是程序、數據及相關文檔的完整集合行為抽象——反應對象的動態(tài)特征生命周期問題定義-可行性研究-需求分析-概要設計-詳細設計-實現-測試-運行-維護-退役軟件開發(fā)模型瀑布模型演化模型螺旋模型6.4.2軟件開發(fā)方法面向過程的方法面向對象的方法面向對象=對象+類+繼承+消息

軟件測試目的：檢驗是否滿足規(guī)定的需求或弄清預期結果與實際結果的差別