大學(xué)信息技術(shù)基礎(chǔ)(第六章)

大學(xué)信息技術(shù)基礎(chǔ)——軟件設(shè)計基礎(chǔ)（第六章）算法是處理問題的策略

數(shù)據(jù)結(jié)構(gòu)是問題的數(shù)學(xué)模型

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

各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)

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

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

編寫程序文檔

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

Java,Dephi等面向?qū)ο蟮囊恍┗靖拍铑?、對象、屬性、方法、事件、事件過程、事件驅(qū)動6.3.3面向?qū)ο蟪绦蛟O(shè)計面向?qū)ο蟪绦蛟O(shè)計的特點抽象數(shù)據(jù)抽象——反應(yīng)對象的靜態(tài)特征行為抽象——反應(yīng)對象的動態(tài)特征封裝繼承多態(tài)6.4軟件工程軟件工程的基本概念軟件的定義與特點軟件是程序、數(shù)據(jù)及相關(guān)文檔的完整集合行為抽象——反應(yīng)對象的動態(tài)特征生命周期問題定義-可行性研究-需求分析-概要設(shè)計-詳細(xì)設(shè)計-實現(xiàn)-測試-運行-維護-退役軟件開發(fā)模型瀑布模型演化模型螺旋模型6.4.2軟件開發(fā)方法面向過程的方法面向?qū)ο蟮姆椒嫦驅(qū)ο?對象+類+繼承+消息

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