1、 第九章 軟件工程與數據庫技術基礎第15講l目的要求目的要求 使學生掌握軟件工程與數據庫技術基礎知識使學生掌握軟件工程與數據庫技術基礎知識l教學重點教學重點 軟件工程、數據庫和數據結構的基本概念軟件工程、數據庫和數據結構的基本概念l教學難點教學難點 關系型數據庫關系型數據庫 ，算法，排序與查找，算法，排序與查找l教學課時教學課時 4課時課時l教學方法教學方法 課堂講授課堂講授2課時，上機課時，上機2課時課時l教學內容教學內容 第九章 軟件工程與數據庫技術基礎第九章 軟件開發與信息處理技術p 軟件工程基礎軟件工程基礎p 數據庫設計基礎數據庫設計基礎p 數據結構與算法數據結構與算法p 程序設計基礎

2、程序設計基礎p 多媒體技術簡介多媒體技術簡介 第九章 軟件工程與數據庫技術基礎9.1 軟件工程基礎 軟件的規模大小、復雜程度決定了軟件開發的難度，因此，必須采用科學的軟件開發方法，采用抽象、分解等科學方法降低復雜度，以工程的方法管理和控制軟件開發的各個階段，以保證大型軟件系統的開發具有正確性、易維護性、可讀性正確性、易維護性、可讀性和可重用性和可重用性 第九章 軟件工程與數據庫技術基礎9.1.1 軟件工程基本概念 軟件的發展大致分為四個階段：（如下圖）階段第一階段第二階段第三階段第四階段程序設計階段程序系統階段軟件工程階段（結構化方法發）軟件工程階段（面向對象方法）典型技術面向批處理有限的分布

3、自定義軟件多用戶實時數據庫軟件產品分布式系統嵌入“智能”低成本硬件消費者的影響強大的桌面系統面向對象技術專家系統人工神經網絡網絡計算機 第九章 軟件工程與數據庫技術基礎軟件危機和軟件工程v軟件危機主要表現在：軟件危機主要表現在：對軟件開發成本和進度的估計常常很不準確，經費預算經常突破，完成時間一再拖延；開發的軟件不能滿足用戶要求，用戶軟件不滿意的現象經常發生；開發的軟件可維護性差、可靠性差v軟件工程：軟件工程：運用系統的、規范的和可定量的方法開發、運行和維護軟件。它包含三個要素： 方法（Methodologies） 工具（Tools） 過程（Procedures） 第九章 軟件工程與數據庫技術

4、基礎軟件工程過程和軟件生命周期 軟件工程過程軟件工程過程 軟件生命周期軟件生命周期 軟件生命周期模型軟件生命周期模型 軟件工程的目標和原則軟件工程的目標和原則 軟件開發工具與軟件開發環境軟件開發工具與軟件開發環境 第九章 軟件工程與數據庫技術基礎 下圖為軟件生命周期各階段的任務：下圖為軟件生命周期各階段的任務：時期階段任務文檔軟件計劃問題定義理解用戶要求，劃清工作范圍計劃說明書可行性研究可行性方案及代價需求分析軟件系統的目標及應完成的工作需求規格說明書軟件開發概要設計系統的邏輯設計軟件概要設計說明書詳細設計系統模塊設計軟件詳細設計說明書軟件編碼編寫程序代碼程序、數據、詳細注釋軟件測試單元測試、

5、綜合測試測試后的軟件、測試大綱、測試方案與結果軟件維護軟件維護運行和維護維護后的軟件 第九章 軟件工程與數據庫技術基礎圖為軟件生命周期的瀑布模型和快速原形法模型軟件計劃需求分析軟件設計軟件編碼軟件測試軟件維護需求分析快速設計建立模型用戶評價模型修改原型生產產品 第九章 軟件工程與數據庫技術基礎軟件工程目標和原則目標：目標：在給定成本、進度的前提下，開發出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性并滿足用戶需求的產品 軟件工程理論和技術性研究的內容： 軟件開發技術和軟件管理技術原則：原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性 第九章

6、 軟件工程與數據庫技術基礎軟件開發工具與開發環境軟件開發工具：軟件開發工具：是為支持軟件人員開發和維是為支持軟件人員開發和維護活動而使用的軟件。護活動而使用的軟件。作用：作用：可以幫助開發人員完成一些繁瑣的程序編可以幫助開發人員完成一些繁瑣的程序編制和調試問題，是軟件開發人員將更多的精力和時制和調試問題，是軟件開發人員將更多的精力和時間投放到最重要的軟件需求和設計上，提高軟件開間投放到最重要的軟件需求和設計上，提高軟件開發的速度和質量。發的速度和質量。 第九章 軟件工程與數據庫技術基礎9.1.2 結構化分析方法p結構化方法（結構化方法（SructuredSructured Methodolog

7、y Methodology）：）：是計算學科的一種典型的系統開發方法，它采用了系統科學的思想方法，從層次的角度，自頂向下的分析和設計系統。p內容：內容：結構化分析（ Sructured Analysis） 結構化設計（ Sructured Design） 結構化程序設計（Sructured Program Design） 第九章 軟件工程與數據庫技術基礎軟件開發過程p 問題定義問題定義p 可行性研究可行性研究p 需求分析與需求分析方法需求分析與需求分析方法p 結構化分析方法概述結構化分析方法概述p 軟件需求規格說明書軟件需求規格說明書 第九章 軟件工程與數據庫技術基礎結構化分析方法使用的工具A

8、. 數據流圖（數據流圖（Data Flow DiagramData Flow Diagram）從數據傳遞和加工的角度，以圖形方式刻畫數據流從輸入到輸出的移動變換過程B. 數據字典（數據字典（Data DictionaryData Dictionary）需對數據流圖中的各個元素作完整的定義和說明，是數據流圖的補充工具C. 加工邏輯描述工具加工邏輯描述工具（常用：結構化自然語言、判定樹和判定表） 第九章 軟件工程與數據庫技術基礎9.1.3 結構化設計方法軟件設計的基本概念：軟件設計的基本概念：是一個把軟件需求轉化為軟件表示的過程，即把分析結果加工為在程序細節上接近于源程序的軟件表示（軟件描述）軟件

9、設計階段分為：軟件設計階段分為：p 系統的總體設計或概要設計（確定軟件系統結構）p 系統的詳細設計（進行各模塊的具體設計） 第九章 軟件工程與數據庫技術基礎概要設計p概要設計概要設計又稱為總體設計，它的任務是確定軟件結構p結構化設計方法的基本思想：結構化設計方法的基本思想：采用自頂向下的模塊化設計方法，按照模塊化原則和軟件設計策略，將需求分析得到的數據流圖，映射成由相對獨立、單一功能的模塊組成的軟件結構 第九章 軟件工程與數據庫技術基礎概要設計概要設計的圖形工具（層次圖、HIPO圖、軟件結構圖）軟件設計原理軟件結構設計原則面向數據流的設計方法（變換流分析設計和事務流分析設計）設計規格說明 第九

10、章 軟件工程與數據庫技術基礎軟件結構設計原則提高模塊獨立性模塊規模應該適中模塊的深度、寬度、扇出和扇入適當模塊的作用域應該在控制域之內降低模塊接口的復雜程度設計單入口和單出口模塊 第九章 軟件工程與數據庫技術基礎詳細設計u任務：為軟件結構圖中的每一個模塊確定實現算法和局部數據結構，并用某種工具描述出來結構化程序設計詳細設計工具（程序流程圖、盒圖N-S圖、PAD圖）詳細設計規格說明 第九章 軟件工程與數據庫技術基礎9.1.4 軟件測試一、軟件測試的目的與任務一、軟件測試的目的與任務目的：目的：確保軟件的質量，盡量找出軟件錯誤并加以糾正，而不是證明軟件沒有錯。任務：任務：測試任務（通過采用一定的測

11、試策略，找出軟件中的錯誤） 調試任務或糾錯任務（如果測試到錯誤，則定位軟件中的錯誤，加以糾正） 第九章 軟件工程與數據庫技術基礎二、軟件測試的準則二、軟件測試的準則三、軟件測試技術與方法綜述三、軟件測試技術與方法綜述 方法：靜態測試法 動態測試法 技術：白盒測試用例設計 黑盒測試用例設計 第九章 軟件工程與數據庫技術基礎白盒測試用例設計A、邏輯覆蓋、邏輯覆蓋 以程序的內部邏輯結構為基礎的測試用例設計技術，它要求測試人員十分清楚程序的邏輯結構，考慮的是測試用例對程序內部邏輯覆蓋的程度 根據覆蓋的目標，可分為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、路徑覆蓋B、基本路徑測試基本路徑測試 第九

12、章 軟件工程與數據庫技術基礎 黑盒測試用例設計分類：分類： 等價類劃分法 邊界值分析法 錯誤推測法 因果圖 第九章 軟件工程與數據庫技術基礎四、軟件測試的實施四、軟件測試的實施 單元測試 集成測試 確認測試 系統測試五、軟件測試計劃與測試分析報告五、軟件測試計劃與測試分析報告 測試測試是軟件生存周期中的一個獨立的關鍵的階段 第九章 軟件工程與數據庫技術基礎9.1.5 程序的調試程序調試可以分為：程序調試可以分為：靜態調試靜態調試（主要通過人的思維來分析源程序代碼和排錯，是主要的調試手段）動態調試動態調試（是靜態調試的輔助）主要的調試方法有： 強行排錯法 回溯法 原因排除法 第九章 軟件工程與數

13、據庫技術基礎9.2 數據庫設計基礎p 數據庫概念數據庫概念p 數據模型數據模型p 數據庫設計與管理數據庫設計與管理 第九章 軟件工程與數據庫技術基礎9.2.1 數據庫概念數據（數據（DataData）數據處理（數據處理（Data ProcessingData Processing）數據庫（數據庫（DatabaseDatabase，DBDB）數據庫管理系統（數據庫管理系統（Database Management SystemDatabase Management System，DBMSDBMS）數據庫管理員（數據庫管理員（Database AdministratorDatabase Admini

14、strator，DBADBA）數據庫系統（數據庫系統（ Database System Database System ，DBSDBS）數據庫應用系統（數據庫應用系統（ Database Application Database Application SystemSystem，DBASDBAS） 第九章 軟件工程與數據庫技術基礎數據庫系統的發展 人工管理階段人工管理階段 文件系統階段文件系統階段 數據庫系統階段數據庫系統階段（在關于數據庫的諸多新技術中，比較重要的三種是： 面向對象數據庫系統、知識庫系統，以及關系數據庫系統的擴充） 第九章 軟件工程與數據庫技術基礎數據庫系統的基本功能u 數據

15、定義功能數據定義功能u 數據操縱功能數據操縱功能u 數據庫運行控制功能數據庫運行控制功能u 數據庫的建立和維護功能數據庫的建立和維護功能 第九章 軟件工程與數據庫技術基礎數據庫系統的基本特點數據的結構化數據的結構化數據的高共享性和低冗余性數據的高共享性和低冗余性數據的獨立性數據的獨立性數據的統一管理與控制數據的統一管理與控制 第九章 軟件工程與數據庫技術基礎數據庫系統的內部結構體系數據庫系統的內部結構體系模式：模式：是數據庫中全體數據的邏輯結構和特征的描述，它僅僅涉及到型的描述，不涉及到具體的值。模式的一個具體值稱為模式的一個實例，同一個模式可以有多個實例。數據庫管理系統采用三級模式結構: 概

16、念模式 外模式（是概念模式的邏輯子集，也稱子模式或用戶模式） 內模式（也稱存儲模式） 并提供二級映像功能 第九章 軟件工程與數據庫技術基礎9.2.2 數據模型k數據模型（數據模型（data modeldata model）：）：是表示實體類型及實體之間聯系的模型k數據模式的三個要素：數據模式的三個要素： 數據結構數據結構 數據操作數據操作 數據的完整性約束條件數據的完整性約束條件 第九章 軟件工程與數據庫技術基礎 數據模型的三個級別：數據模型的三個級別： 概念數據模型概念數據模型 邏輯數據模型邏輯數據模型 物理數據模型物理數據模型 第九章 軟件工程與數據庫技術基礎數據模型的分類p E-R 模型

17、（實體聯系模型）模型（實體聯系模型） 是直接從現實世界中抽象出實體類型及實體間聯系，然后用實體聯系圖（E-R圖）表示數據模型p 層次模型層次模型（若用圖表示，它是一棵倒立的樹）p 網狀模型網狀模型（若用圖表示是一個網絡）是一個網絡）p 關系模型關系模型（數據的邏輯結構是一張二維表） 第九章 軟件工程與數據庫技術基礎9.2.3 數據庫設計與管理 數據庫及其應用系統的數據庫及其應用系統的設計步驟：設計步驟：p 用戶需求分析p 概念設計p 邏輯設計p 物理設計p 數據庫實施p 數據庫的維護 第九章 軟件工程與數據庫技術基礎數據庫設計的需求分析p 用戶的信息要求用戶的信息要求p 用戶的處理要求用戶的處

18、理要求p 對數據的安全性、完整性的要求對數據的安全性、完整性的要求 第九章 軟件工程與數據庫技術基礎數據庫的概念設計概念結構設計：概念結構設計：只講需求分析得到的用戶需求抽象為信息結構即概念模型的過程概念結構獨立于數據庫邏輯結構，也獨立于支持數據庫的DBMS。 它是現實世界與機器世界的中介，它一方面能夠充分反映現實世界，包括實體與實體之間的聯系，同時又易于向關系、網狀、層次等各種數據模式轉換。 第九章 軟件工程與數據庫技術基礎數據庫的邏輯設計 邏輯結構設計的步驟：邏輯結構設計的步驟：p將概念結構向一般關系模型轉化p將第一步得到的結構向特定的DBMS支持下的數據模型轉換p依據應用的需求和具體的D

19、BMS特征進行調整與完善 第九章 軟件工程與數據庫技術基礎數據庫的物理設計 確定數據的存儲安排確定數據的存儲安排 存取路徑的選擇和調整存取路徑的選擇和調整 確定系統配置確定系統配置 第九章 軟件工程與數據庫技術基礎數據庫管理數據庫的管理主要指：數據庫的管理主要指： 數據庫的實施和維護數據庫的實施和維護分三個步驟：分三個步驟： 數據的載入和應用程序的調試 數據庫的試運行 數據庫的運行和維護 第九章 軟件工程與數據庫技術基礎數據庫的維護在數據庫運行階段，對數據庫經常性的維護工作主要是由DBADBA完成的。包括： 數據庫的存儲和恢復 數據庫的安全性、完整性控制 數據庫性能的監督、分析和改進 數據庫的

20、重組織與重構造 第九章 軟件工程與數據庫技術基礎9.3 數據結構與算法 算法算法 數據結構的基本概念及術語數據結構的基本概念及術語 線性表線性表 棧棧 隊列隊列 樹與二叉樹樹與二叉樹 查找與排序查找與排序 第九章 軟件工程與數據庫技術基礎9.3.1 算法p定義：定義：是對特定問題求解步驟的一種描述。或者說，是為求解某問題而設計的步驟序列p特征：特征： 有窮性 確定性 有效性 輸入 輸出 第九章 軟件工程與數據庫技術基礎算法復雜度評價一個算法優劣的主要標準是： 算法的執行效率與存儲需求算法的執行效率與存儲需求算法的效率：指的是時間復雜度（Time Complexity）存儲需求：指的是空間復雜度

21、（Space Complexity ） 一般情況下，算法中的基本操作重復操作執行的次數是問題規模n的某個函數f(n),算法的時間復雜度記做 T(nT(n)=)=O(f(nO(f(n) 第九章 軟件工程與數據庫技術基礎9.3.2 數據結構的基本概念及術語數據與數據結構數據與數據結構數據數據 是描述客觀事物的數、字符以及所有能輸入到計算機中并被計算機程序加工處理的符號的集合數據元素數據元素 是數據的基本元素，即數據集合中的個體數據項數據項 具有獨立意義的最小數據單位數據對象數據對象 具有相同特性的數據元素的集合，是數據的子集結構結構 被計算機加工的數據元素之間存在的關系數據結構數據結構 帶有結構特

22、性的數據元素的集合 第九章 軟件工程與數據庫技術基礎數據的邏輯結構u 集合集合u 線性結構線性結構u 樹形結構樹形結構u 圖狀或網狀結構圖狀或網狀結構 第九章 軟件工程與數據庫技術基礎數據的存儲結構一、順序存儲結構一、順序存儲結構 主要特點：主要特點：v結點中只有自身信息域，沒有連接信息域，因此存儲密度大，存儲空間利用率高v可以通過計算直接確定數據結構中第i個結點的存儲地址Li，計算公式：L0+（i-1）m。（其中L0為第一個結點的存儲地址，m為每個結點所占用的存儲單元個數v插入、刪除運算不便，會引起大量結點的移動 第九章 軟件工程與數據庫技術基礎二、鏈式存儲結構主要特點：主要特點：結點中除自

23、身信息之外，還有表示連接信息的指針域，因此比順序存儲密度小，存儲空間利用率低邏輯上相鄰的結點物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結構的存儲表示插入、刪除操作靈活方便，不必移動結點，只要改變結點中的指針值即可 第九章 軟件工程與數據庫技術基礎 數據的運算數據的運算p檢索：在數據結構里查找滿足一定條件的結點p插入：往數據結構里增加新的結點p刪除：把指定的結點從數據結構里去掉p更新：改變指定結點的一個或多個域的值p排序：保持線性結構的結點序列里結點數不變，把結點按某種指定的順序重新排列 第九章 軟件工程與數據庫技術基礎9.3.3 線性表 線性表線性表是最常用的一種數據結構。線性表的邏輯結構

24、是n個數據元素的有限序列（a1,a2,an）順序表：順序表：指用順序存儲結構存儲的線性表鏈表：鏈表：用鏈式存儲結構存儲的線性表棧和隊列棧和隊列是對線性表的插入、刪除運算可以發生的位置加以限制的兩種特殊的線性表 第九章 軟件工程與數據庫技術基礎順序表和一維數組 各種高級語言里的一維數組就是用順序方式存儲的線性表，因此常用一維數組稱呼順序表一維數組稱呼順序表 若順序表中結點個數為n，則： 插入插入一個結點平均需要移動之結點個數為n/2，算法的時間復雜度是O(n)； 刪除刪除一個結點平均需移動結點個數為（n-1）/2，算法的時間復雜度是O(n) 第九章 軟件工程與數據庫技術基礎鏈 表線性鏈表（單鏈表

25、）：刪除算法的時間復雜度為O(n)，其主要執行時間是搜索刪除位置循環鏈表：指鏈表的最后一個結點的指針值指向第一個結點，整個鏈表形成一個環（如下圖）結點1結點2結點n 第九章 軟件工程與數據庫技術基礎9.3.4 棧棧：棧：是一種特殊的線性表，是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom）。空棧：空棧：指表中無元素p 棧中有元素a1,a2,an，如下頁圖所示，稱a1為棧底元素。新元素進棧要置于an之上，刪除或退棧先對an進行，即“后進先出后進先出”（LIFOLIFO）的操作原則p 棧的物理存儲可以用 順序存儲結構或鏈式存儲結構順序存儲結構或鏈式存儲結

26、構p 棧的運算還有取棧頂元素，檢查棧是否為空，清除等。 第九章 軟件工程與數據庫技術基礎棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPana2a1進棧出棧棧底棧結構(3)(1)(2)(5)(4)(6) 第九章 軟件工程與數據庫技術基礎9.3.5 隊列隊列：隊列：是限定所有的插入都在表的一端進行，所有的刪除都在表的另一端進行的線性表。進行刪除的一端叫隊列的頭，進行插入的一端叫隊列的尾，如下頁圖所示。 在隊列中，新元素總是加入到隊尾，每次刪除的總是對頭元素，即當前“最老的”元素，這就是“先進先出先進先出”（FIFOFIFO）的操作原則隊列的物理存儲可以用： 順序存儲結

27、構，也可用鏈式存儲結構 第九章 軟件工程與數據庫技術基礎隊列的示意（如下圖）隊列的示意（如下圖）出隊列出隊列 a1 a2 a3 a1 a2 a3 an an 入隊列入隊列 頭頭 尾尾 第九章 軟件工程與數據庫技術基礎隊列的插入和刪除示例初態插入A插入B刪除A插入C插入D刪除B插入EF FR RAFRRRRRRFFFFFFBABBBCCCCDDD溢出 第九章 軟件工程與數據庫技術基礎9.3.6 樹與二叉樹樹形結構樹形結構是一類重要的非線性結構，樹和二叉樹是最常見的樹形結構樹（樹（TreeTree）: :是一個或多個結點組成的有限集合T，有一個特定的結點稱為根（Root），其余的結點分為m（m0）

28、個不相交的集合T1，T2，Tm，每個集合又是一棵樹，稱作這個根的子樹（Subtree) 第九章 軟件工程與數據庫技術基礎樹形結構的常用術語樹形結構的常用術語結點的度（結點的度（DegreeDegree）：）：一個結點的子樹的個數一個結點的子樹的個數樹的度：樹的度：樹中各結點的度的最大值樹中各結點的度的最大值樹葉（樹葉（LeafLeaf）：度為度為0 0的結點的結點分支結點：分支結點：度不為0的結點雙親（雙親（ParentParent）、子女（）、子女（ChildChild）：）：結點的各子結點的各子樹的根稱作該結點的子女；相應的該結點稱作其樹的根稱作該結點的子女；相應的該結點稱作其子女的雙親子

29、女的雙親兄弟（兄弟（SiblingSibling）：）：具有相同雙親的結點互為兄具有相同雙親的結點互為兄弟弟結點的層數（結點的層數（LevelLevel）樹的深度（）樹的深度（DepthDepth）森林（森林（ForestForest） 第九章 軟件工程與數據庫技術基礎二 叉 樹p二叉樹（二叉樹（Binary TreeBinary Tree）: :是n（n0)個結點的有限集合，這個集合或者為空集（n=0），或者由一個根結點及兩棵不相交的、分別稱作這個根的坐姿樹和右子樹的二叉樹組成 二叉樹不是樹的特殊情形，二者的區別：區別： 二叉樹為有序樹二叉樹為有序樹p性質：1、在二叉樹的i層上，最多有2i-

30、1個結點（i1） 2、 深度為k的二叉樹最多有2k-1個結點(k1) 第九章 軟件工程與數據庫技術基礎完全二叉樹p一棵深度為k且具有2k-1個結點的二叉樹稱為滿二叉樹（滿二叉樹（Full Binary Tree Full Binary Tree ）p深度為k，有n個結點的二叉樹，當且僅當其妹一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹 第九章 軟件工程與數據庫技術基礎樹的二叉樹表示在樹（森林）與二叉樹間有一個自然的一一在樹（森林）與二叉樹間有一個自然的一一對應的關系，每一棵樹都能唯一的轉換到它對應的關系，每一棵樹都能唯一的轉換到它所對應的二叉樹所對應的二叉樹把樹

31、和森林轉化成對應的二叉樹：把樹和森林轉化成對應的二叉樹： 凡是兄弟就用線連起來，然后去掉雙親到子女的連線，只留下道第一個子女的連線不去掉 第九章 軟件工程與數據庫技術基礎二叉樹的存儲 二叉樹的存儲通常采用:鏈接方式鏈接方式。每個結點除存儲結點自身的信息外再設置兩個指針域IIink和rlink，分別指向結點的左子女和右子女，當結點的某個指針為空時，則相應的指針值為空（NIL）。 結點的形式為：IIinkIIinkinfoinforlinkrlink 第九章 軟件工程與數據庫技術基礎二叉樹的遍歷v遍歷一個樹形結構是指：遍歷一個樹形結構是指：按一定次序系統按一定次序系統的訪問該結構中的所有結點，使每

32、個結點恰好被的訪問該結構中的所有結點，使每個結點恰好被訪問一次訪問一次v前序遍歷法（前序遍歷法（NLRNLR次序）次序）訪問根，按前序遍歷左子樹，按前序遍歷右子樹訪問根，按前序遍歷左子樹，按前序遍歷右子樹v后序遍歷法（后序遍歷法（LRNLRN次序）次序）按后序遍歷左子樹，按后序遍歷右子樹，訪問根按后序遍歷左子樹，按后序遍歷右子樹，訪問根v中序遍歷法（中序遍歷法（LNRLNR次序）次序）按中序遍歷左子樹，訪問根，按中序遍歷右子樹按中序遍歷左子樹，訪問根，按中序遍歷右子樹 第九章 軟件工程與數據庫技術基礎9.3.7 查找查找p 查找：是數據結構中的基本運算p 衡量一個查找運算法的主要標志是： 查找

33、過程中對關節碼進行的平均比較次數，或稱平均檢索長度，以n的函數的形式表示，n是數據結構中的結點個數 第九章 軟件工程與數據庫技術基礎順序查找順序查找：順序查找：是線性表的最簡單的查找方法方法：方法：用待查關鍵碼與線性表中各結點的關鍵碼值逐個比較，若找出相等的關鍵碼值則查找成功，若找遍所有結點都不相等，則查找失敗優點：優點：對線性表的結點邏輯次序和存儲結構無要求缺點：缺點：平均檢索長度大假設表中各結點被查找的概率相同，即P=1/n,則順序查找成功的平均查找長度為平均查找長度為(n+1)/2(n+1)/2 第九章 軟件工程與數據庫技術基礎二分法查找二分法查找：二分法查找：是一種效率較高的線性表查找

34、方法。要進行二分法查找，線性表結點必須是按關鍵碼值排號順序的，且線性表以順序方式存儲方法：方法：首先用要查找的關鍵碼值與線性表中間位置結點的關鍵碼值相比較，這個中間結點把線性表分成兩個子表，比較相等則查找完成，不等則根據比較結果確定下一步的查找應在哪個子表中進行，如此下去，直到找到滿足條件的結點優點：優點：平均檢索長度小，為 2n。每經過一次關鍵碼比較，則將查找范圍縮小一半，因此經過2n次比較就可完成查找過程缺點：缺點：排序線性表花費時間，順序方式存儲插入、刪除不便 第九章 軟件工程與數據庫技術基礎9.3.8 排序排序：排序：是數據處理中經常使用的一種運算分類：分類： 直接插入排序直接插入排序

35、 選擇排序選擇排序 冒泡排序冒泡排序 快速排序快速排序 第九章 軟件工程與數據庫技術基礎A.直接插入排序的基本方法：每步將一個待排序記錄按其關鍵碼值的大小插入到前面已排序的文件中適當位置上，直到全部插入為止B.選擇排序的基本思想：每一趟在n-i+1(i=1,2,n-1）個記錄中選取關鍵碼最小的記錄作為有序序列中的第i個記錄。它為最簡單且為我們最熟悉的排序C.冒泡排序的基本方法：將待排序的記錄順次兩兩比較，若為逆序，則進行交換D.快速排序：又稱分區交換排序，是對冒泡排序的一種改進。 第九章 軟件工程與數據庫技術基礎p快速排序的基本方法：在待排序序列中任取一個記錄，以它為基準用交換的發方法將所有記

36、錄分成兩部分，關鍵碼比它小的在一個部分，關鍵碼值比它大的在另一個部分。再分別對兩個部分實施上述過程，一直重復到排序完成p下圖為四種排序方法的比較：排序方法排序方法平均時間平均時間最壞情況最壞情況輔助存儲輔助存儲直接插入排序直接插入排序選擇排序選擇排序冒泡排序冒泡排序快速排序快速排序O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )O(nO(n 2 2n n) )O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )O(1)O(1)O(1)O(1)O(1)O(1)O(O(2 2n n) ) 第九章 軟件工程與數據庫技術基礎9.4 程

37、序設計基礎p 程序設計語言發展程序設計語言發展p 程序設計方法與風格程序設計方法與風格p 結構化程序設計結構化程序設計p 面向對象的程序設計面向對象的程序設計 第九章 軟件工程與數據庫技術基礎程序設計指令：指令：能被計算機直接識別與執行的指示計算機進行某種操作的命令，CPU每執行一條指令，就完成一個基本運算。程序：程序：指令的序列即讓計算機解決某一問題而寫出的一系列指令程序設計：程序設計：編寫程序的過程程序設計語言：程序設計語言：用于描述計算機所執行的操作語言 第九章 軟件工程與數據庫技術基礎9.4.1 程序設計語言發展程序設計語言發展p機器語言：機器語言：采用計算機指令格式并以二進制編碼表達

38、各種操作的語言p匯編語言：匯編語言：一種符號語言，采用助記符來表達指令功能p高級語言：高級語言：是一種面向問題的語言p第四代語言：第四代語言：是非過程化語言 第九章 軟件工程與數據庫技術基礎9.4.2 程序設計方法與風格 良好程序設計風格的側重：良好程序設計風格的側重：p 源程序文檔如使用的符號名應具有一定的含義，以便對程序功能的理解；對源程序適當的進行注解，以便讀者理解程序；在程序中利用空格、空行、縮進等技巧使程序層次清楚p 對程序中的數據進行適當說明p 程序中的語句結構應該簡單直接，語句不復雜化p 要對程序的所有輸入數據檢查其合法性，檢查輸入項的各種重要組合的合理性，輸入格式要簡單，輸入允

39、許默認值，輸入一批數據后最好使用結束標志，在交互式輸入/輸出中使用屏幕提示信息格式 第九章 軟件工程與數據庫技術基礎9.4.3 結構化程序設計結構化程序設計 結構化程序設計的原則結構化程序設計的原則u 自頂向下自頂向下u 逐步求精逐步求精u 模塊化模塊化u 限制使用限制使用GOTOGOTO語句語句 第九章 軟件工程與數據庫技術基礎 結構化程序設計的基本結構與特點結構化程序設計的基本結構與特點 順序結構：順序結構：按照程序語句行的自然順序，按照程序語句行的自然順序，一條語句一條語句的往后執行程序一條語句一條語句的往后執行程序 選擇結構：選擇結構：又稱分支結構，它根據設定又稱分支結構，它根據設定的

40、條件，判斷應該選擇哪一條分支執行相應的條件，判斷應該選擇哪一條分支執行相應的語句序列的語句序列 循環結構：循環結構：又稱重復結構，它根據給定又稱重復結構，它根據給定的條件，判斷是否需要重復執行某一相同的的條件，判斷是否需要重復執行某一相同的或相似的程序段或相似的程序段 第九章 軟件工程與數據庫技術基礎結構化程序設計的優點自頂向下逐步求精的方法符合人類解決復雜問題的普遍規律，自頂向下逐步求精的方法符合人類解決復雜問題的普遍規律，可以顯著提高軟件開發的成功率和生產率可以顯著提高軟件開發的成功率和生產率先全局后局部、先整體后細節、先抽向后具體的逐步求精過先全局后局部、先整體后細節、先抽向后具體的逐步

41、求精過程開發出的程序有清晰的層次結構，使程序容易閱讀和理解程開發出的程序有清晰的層次結構，使程序容易閱讀和理解使用單入口單出口控制結構而不使用使用單入口單出口控制結構而不使用GOTOGOTO語句，使得程序的語句，使得程序的靜態結構和它的動態執行情況一致靜態結構和它的動態執行情況一致控制結構有確定邏輯模式，編寫程序代碼只限于使用很少幾控制結構有確定邏輯模式，編寫程序代碼只限于使用很少幾種直截了當的方式，使源程序清晰流暢，易讀易懂而且容易種直截了當的方式，使源程序清晰流暢，易讀易懂而且容易測試測試程序清晰和模塊化使得在修改和重新設計一個軟件時可以重程序清晰和模塊化使得在修改和重新設計一個軟件時可以

42、重用的代碼量最大用的代碼量最大程序的邏輯結構清晰，有利于程序正確性證明程序的邏輯結構清晰，有利于程序正確性證明 第九章 軟件工程與數據庫技術基礎9.4.4 面向對象的程序設計 面向對象方法的主要特點：從問題域中客觀存在的事物出發來構造軟件系從問題域中客觀存在的事物出發來構造軟件系統，用對象作為對這些事物的抽象表示，并以統，用對象作為對這些事物的抽象表示，并以此作為系統的基本構成單位此作為系統的基本構成單位事物的靜態特征用對象的屬性表示，動態特征事物的靜態特征用對象的屬性表示，動態特征用對象的服務表示用對象的服務表示對象的屬性與服務結合為一個獨立的實體，對對象的屬性與服務結合為一個獨立的實體，對

43、外屏蔽其內部細節，稱作封裝外屏蔽其內部細節，稱作封裝把具有相同屬性和相同服務的對象歸為一類，把具有相同屬性和相同服務的對象歸為一類，類是這些對象的抽象描述，每個對象是它的類類是這些對象的抽象描述，每個對象是它的類的一個實例的一個實例 第九章 軟件工程與數據庫技術基礎 面向對象方法的主要特點：通過在不同程度上運用抽象的原則，可以得到通過在不同程度上運用抽象的原則，可以得到較一般的類和較特殊的類較一般的類和較特殊的類復雜的對象可以用簡單的對象作為其構成部分，復雜的對象可以用簡單的對象作為其構成部分，稱為聚合稱為聚合對象之間通過消息進行通信，以實現對象之間對象之間通過消息進行通信，以實現對象之間的動

44、態聯系的動態聯系通過關聯表達對象之間的靜態關系通過關聯表達對象之間的靜態關系 第九章 軟件工程與數據庫技術基礎面向對象方法的概念 面向對象：面向對象： 面向對象面向對象= =對象對象+ +類類+ +繼承繼承+ +通信通信 如果一個軟件系統是使用這樣四個概念設計和實現的，則認為這個軟件系統是面向對象的。面向對象的程序的每一組成部分都是對象，計算是通過建立新的對象和對象之間的通信來執行的 第九章 軟件工程與數據庫技術基礎對 象 對象是構成世界的一個獨立單位，它具有自己的靜態特征和動態特征。靜態特征：靜態特征：指可以用某種數據來描述的特征動態特征：動態特征：指對象所表現的行為或對象所具有的功能定義：

45、定義：對象是系統中用來描述客觀事物的一個實體，它是構成系統的一個基本單位。一個對象由一組屬性和對這組屬性進行操作的一組方法構成。屬性：屬性：用來描述對象靜態特征的一個數據項方法：方法：用來描述對象動態特征的一個操作序列 第九章 軟件工程與數據庫技術基礎消息和方法一個系統由若干個對象組成，各個對象之一個系統由若干個對象組成，各個對象之間相互聯系、相互作用。間相互聯系、相互作用。計算機系統中，消息就是對象之間的紐帶，計算機系統中，消息就是對象之間的紐帶，是用來通知、命令或請求對象執行某個處是用來通知、命令或請求對象執行某個處理或回答某些信息。理或回答某些信息。消息可以是消息可以是數據流數據流，也可

46、以是，也可以是控制流控制流。一條消息可以發送給不同的對象，而消息一條消息可以發送給不同的對象，而消息的解釋則完全由接收對象完成。不同的對的解釋則完全由接收對象完成。不同的對象對相同形式的消息可以有不同的解釋象對相同形式的消息可以有不同的解釋 第九章 軟件工程與數據庫技術基礎類和實例類和對象之間的關系類和對象之間的關系 如同一個模具與用這個模具鑄造出來的鑄件之間的關系。類給出了屬于該類的全部對象的抽象定義，而對象則是符合這種定義的一個實體。一個對象又稱為類的一個實例（Instance）類也可稱作對象的模板（Template） 第九章 軟件工程與數據庫技術基礎繼 承 性p定義：定義：特殊類的對象擁

47、有其一般類的全特殊類的對象擁有其一般類的全部屬性與方法，稱作特殊類對一般類的繼部屬性與方法，稱作特殊類對一般類的繼承承p繼承關系是傳遞的繼承關系是傳遞的p繼承性對于軟件重用有很大益處繼承性對于軟件重用有很大益處 第九章 軟件工程與數據庫技術基礎封 裝 性封裝具有兩個涵義：封裝具有兩個涵義：一、是把對象的全部屬性和全部方法結合在一起，形成一個不可分割的獨立單位（即對象）二、也稱作“信息隱蔽”，即盡可能隱蔽對象的內部細節，對外形成一個邊界，只保留有限的對外接口使之與外部發生聯系 第九章 軟件工程與數據庫技術基礎多 態 性對象的多態性：對象的多態性： 指在一般類中定義的屬性或方法被特殊類繼承之后，可

48、以具有不同的數據類型表現出不同的行為。這使得同一個屬性或方法名在一般類及其各個特殊類中具有不同的語義 第九章 軟件工程與數據庫技術基礎9.5 多媒體技術簡介p多媒體技術的基本概念多媒體技術的基本概念p多媒體計算機系統多媒體計算機系統p多媒體計算機軟件系統多媒體計算機軟件系統p多媒體信息的數字化和壓縮技術多媒體信息的數字化和壓縮技術 第九章 軟件工程與數據庫技術基礎9.5.1 多媒體技術的基本概念定義：指信息表示媒體的多樣化。定義：指信息表示媒體的多樣化。多媒體的類型多媒體的類型感覺媒體感覺媒體 表示媒體表示媒體 顯示媒體顯示媒體 傳輸媒體傳輸媒體 存儲媒體存儲媒體多媒體技術就是利用計算機把文本、聲音、視頻、動畫、圖形和圖像等多種媒體進行綜合處理，使多種信息建立邏輯連接，集成為一個具有交互性的系統 第九章 軟件工程與數據庫技術基礎多媒體技術的特征 信息載體的多樣性信息載體的多樣性 交互性交互性 集成性集成性 實時性實時性 第九章 軟件工程與數據庫技術基礎多媒體信息中的媒體元素的類型p 文本（文本（TextText）p 圖形（圖形（GraphicGraphic）p 圖像（圖像（ImageIm