軟件開發(fā)與信息處理技術(shù).ppt

《軟件開發(fā)與信息處理技術(shù).ppt》由會員分享，可在線閱讀，更多相關(guān)《軟件開發(fā)與信息處理技術(shù).ppt（106頁珍藏版）》請在裝配圖網(wǎng)上搜索。

軟件開發(fā)與信息處理技術(shù) 軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)多媒體技術(shù)簡介 7 1軟件工程基礎(chǔ) 軟件的規(guī)模大小決定了軟件開發(fā)的難度 因此 必須采用科學(xué)的軟件開發(fā)方法 采用抽象 分解等科學(xué)方法降低復(fù)雜度 以工程的方法管理和控制軟件開發(fā)的各個階段 以保證大型軟件系統(tǒng)的開發(fā)具有正確性 易維護性 可讀性和可重用性 7 1 1軟件工程基本概念 軟件的發(fā)展大致分為四個階段 如下圖 軟件危機和軟件工程 軟件危機主要表現(xiàn)在 對軟件開發(fā)成本和進度的估計常常很不準確 經(jīng)費預(yù)算經(jīng)常突破 完成時間一再拖延 開發(fā)的軟件不能滿足用戶要求 用戶軟件不滿意的現(xiàn)象經(jīng)常發(fā)生 開發(fā)的軟件可維護性差 可靠性差軟件工程 運用系統(tǒng)的 規(guī)范的和可定量的方法開發(fā) 運行和維護軟件 它包含三個要素 方法 Methodologies 工具 Tools 過程 Procedures 軟件工程過程和軟件生命周期 軟件工程過程軟件生命周期軟件生命周期模型軟件工程的目標和原則軟件開發(fā)工具與軟件開發(fā)環(huán)境 下圖為軟件生命周期各階段的任務(wù) 圖為軟件生命周期的瀑布模型和快速原形法模型 軟件計劃 需求分析 軟件設(shè)計 軟件編碼 軟件測試 軟件維護 需求分析 快速設(shè)計 建立模型 用戶評價模型 修改原型 生產(chǎn)產(chǎn)品 軟件工程目標和原則 目標 在給定成本 進度的前提下 開發(fā)出具有有效性 可靠性 可理解性 可維護性 可重用性 可適應(yīng)性 可移植性 可追蹤性并滿足用戶需求的產(chǎn)品軟件工程理論和技術(shù)性研究的內(nèi)容 軟件開發(fā)技術(shù)和軟件管理技術(shù)原則 抽象 信息隱蔽 模塊化 局部化 確定性 一致性 完備性和可驗證性 軟件開發(fā)工具與開發(fā)環(huán)境 軟件開發(fā)工具 是為支持軟件人員開發(fā)和維護活動而使用的軟件 作用 可以幫助開發(fā)人員完成一些繁瑣的程序編制和調(diào)試問題 是軟件開發(fā)人員將更多的精力和時間投放到最重要的軟件需求和設(shè)計上 提高軟件開發(fā)的速度和質(zhì)量 7 1 2結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法 SructuredMethodology 是計算學(xué)科的一種典型的系統(tǒng)開發(fā)方法 它采用了系統(tǒng)科學(xué)的思想方法 從層次的角度 自頂向下的分析和設(shè)計系統(tǒng) 內(nèi)容 結(jié)構(gòu)化分析 SructuredAnalysis 結(jié)構(gòu)化設(shè)計 SructuredDesign 結(jié)構(gòu)化程序設(shè)計 SructuredProgramDesign 軟件開發(fā)過程 問題定義可行性研究需求分析與需求分析方法結(jié)構(gòu)化分析方法概述軟件需求規(guī)格說明書 結(jié)構(gòu)化分析方法使用的工具 數(shù)據(jù)流圖 DataFlowDiagram 從數(shù)據(jù)傳遞和加工的角度 以圖形方式刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程數(shù)據(jù)字典 DataDictionary 需對數(shù)據(jù)流圖中的各個元素作完整的定義和說明 是數(shù)據(jù)流圖的補充工具加工邏輯描述工具 常用 結(jié)構(gòu)化自然語言 判定樹和判定表 7 1 3結(jié)構(gòu)化設(shè)計方法 軟件設(shè)計的基本概念 是一個把軟件需求轉(zhuǎn)化為軟件表示的過程 即把分析結(jié)果加工為在程序細節(jié)上接近于源程序的軟件表示 軟件描述 軟件設(shè)計階段分為 系統(tǒng)的總體設(shè)計或概要設(shè)計 確定軟件系統(tǒng)結(jié)構(gòu) 系統(tǒng)的詳細設(shè)計 進行各模塊的具體設(shè)計 概要設(shè)計 概要設(shè)計又稱為總體設(shè)計 它的任務(wù)是確定軟件結(jié)構(gòu)結(jié)構(gòu)化設(shè)計方法的基本思想 采用自頂向下的模塊化設(shè)計方法 按照模塊化原則和軟件設(shè)計策略 將需求分析得到的數(shù)據(jù)流圖 映射成由相對獨立 單一功能的模塊組成的軟件結(jié)構(gòu) 概要設(shè)計 概要設(shè)計的圖形工具 層次圖 HIPO圖 軟件結(jié)構(gòu)圖 軟件設(shè)計原理軟件結(jié)構(gòu)設(shè)計原則面向數(shù)據(jù)流的設(shè)計方法 變換流分析設(shè)計和事務(wù)流分析設(shè)計 設(shè)計規(guī)格說明 軟件結(jié)構(gòu)設(shè)計原則 提高模塊獨立性模塊規(guī)模應(yīng)該適中模塊的深度 寬度 扇出和扇入適當模塊的作用域應(yīng)該在控制域之內(nèi)降低模塊接口的復(fù)雜程度設(shè)計單入口和單出口模塊 詳細設(shè)計 任務(wù) 為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu) 并用某種工具描述出來結(jié)構(gòu)化程序設(shè)計詳細設(shè)計工具 程序流程圖 盒圖 N S圖 PAD圖 詳細設(shè)計規(guī)格說明 7 1 4軟件測試 一 軟件測試的目的與任務(wù)目的 確保軟件的質(zhì)量 盡量找出軟件錯誤并加以糾正 而不是證明軟件沒有錯 任務(wù) 測試任務(wù) 通過采用一定的測試策略 找出軟件中的錯誤 調(diào)試任務(wù)或糾錯任務(wù) 如果測試到錯誤 則定位軟件中的錯誤 加以糾正 二 軟件測試的準則三 軟件測試技術(shù)與方法綜述方法 靜態(tài)測試法動態(tài)測試法技術(shù) 白盒測試用例設(shè)計黑盒測試用例設(shè)計 7 1 4軟件測試 白盒測試用例設(shè)計 邏輯覆蓋以程序的內(nèi)部邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù) 它要求測試人員十分清楚程序的邏輯結(jié)構(gòu) 考慮的是測試用例對程序內(nèi)部邏輯覆蓋的程度根據(jù)覆蓋的目標 可分為 語句覆蓋 判定覆蓋 條件覆蓋 判定 條件覆蓋 路徑覆蓋 基本路徑測試 黑盒測試用例設(shè)計 分類 等價類劃分法邊界值分析法錯誤推測法因果圖 四 軟件測試的實施單元測試集成測試確認測試系統(tǒng)測試五 軟件測試計劃與測試分析報告測試是軟件生存周期中的一個獨立的關(guān)鍵的階段 7 1 4軟件測試 未加入p243 7 1 5程序的調(diào)試 程序調(diào)試可以分為 靜態(tài)調(diào)試 主要通過人的思維來分析源程序代碼和排錯 是主要的調(diào)試手段 動態(tài)調(diào)試 是靜態(tài)調(diào)試的輔助 主要的調(diào)試方法有 強行排錯法回溯法原因排除法 7 2數(shù)據(jù)庫設(shè)計基礎(chǔ) 數(shù)據(jù)庫概念數(shù)據(jù)模型關(guān)系代數(shù)數(shù)據(jù)庫設(shè)計與管理 7 2 1數(shù)據(jù)庫概念 數(shù)據(jù) Data 數(shù)據(jù)處理 DataProcessing 數(shù)據(jù)庫 Database DB 數(shù)據(jù)庫管理系統(tǒng) DatabaseManagementSystem DBMS 數(shù)據(jù)庫管理員 DatabaseAdministrator DBA 數(shù)據(jù)庫系統(tǒng) DatabaseSystem DBS 數(shù)據(jù)庫應(yīng)用系統(tǒng) DatabaseApplicationSystem DBAS 數(shù)據(jù)庫系統(tǒng)的發(fā)展 人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段 在關(guān)于數(shù)據(jù)庫的諸多新技術(shù)中 比較重要的三種是 面向?qū)ο髷?shù)據(jù)庫系統(tǒng) 知識庫系統(tǒng) 以及關(guān)系數(shù)據(jù)庫系統(tǒng)的擴充 數(shù)據(jù)庫系統(tǒng)的基本功能 數(shù)據(jù)定義功能數(shù)據(jù)操縱功能數(shù)據(jù)庫運行控制功能數(shù)據(jù)庫的建立和維護功能 數(shù)據(jù)庫系統(tǒng)的基本特點 數(shù)據(jù)的結(jié)構(gòu)化數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)的統(tǒng)一管理與控制 數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 模式 是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述 它僅僅涉及到型的描述 不涉及到具體的值 模式的一個具體值稱為模式的一個實例 同一個模式可以有多個實例 數(shù)據(jù)庫管理系統(tǒng)采用三級模式結(jié)構(gòu) 概念模式 外模式 是概念模式的邏輯子集 也稱子模式或用戶模式 內(nèi)模式 也稱存儲模式 并提供二級映像功能 7 2 2數(shù)據(jù)模型 數(shù)據(jù)模型 datamodel 是表示實體類型及實體之間聯(lián)系的模型數(shù)據(jù)模式的三個要素 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的完整性約束條件 數(shù)據(jù)模型的三個級別 概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型 7 2 2數(shù)據(jù)模型 數(shù)據(jù)模型的分類 E R模型 實體聯(lián)系模型 是直接從現(xiàn)實世界中抽象出實體類型及實體間聯(lián)系 然后用實體聯(lián)系圖 E R圖 表示數(shù)據(jù)模型層次模型 若用圖表示 它是一棵倒立的樹 網(wǎng)狀模型 若用圖表示是一個網(wǎng)絡(luò) 關(guān)系模型 數(shù)據(jù)的邏輯結(jié)構(gòu)是一張二維表 7 2 3關(guān)系代數(shù) 關(guān)系代數(shù) 是一種抽象的查詢語言 是關(guān)系數(shù)據(jù)操縱語言的一種傳統(tǒng)表達方式 它是用對關(guān)系的運算來表達查詢的 包含 運算對象 運算符合運算結(jié)果三大要素關(guān)系代數(shù)的運算對象是關(guān)系 運算結(jié)果亦為關(guān)系 所以說 它是關(guān)系模型和關(guān)系數(shù)據(jù)庫的理論基礎(chǔ) 傳統(tǒng)的集合運算 并 Union 關(guān)系R和關(guān)系S的并記做R S 由屬于R或S的元組組成 結(jié)果仍為n目關(guān)系差 Difference 關(guān)系R和關(guān)系S的差記做R S 由屬于R不屬于S的元組組成 結(jié)果仍為n目關(guān)系交 Intersection 關(guān)系R和關(guān)系S的交記做R S 由屬于R且屬于S的元組組成 結(jié)果仍為n目關(guān)系廣義笛卡爾積兩個分別為n目和m目的關(guān)系R和S的廣義笛卡爾積R S是一個 n m 列的元組的集合 關(guān)系R和S及其三種傳統(tǒng)的集合運算 如下圖 關(guān)系R 關(guān)系S R S R S R S 專門的關(guān)系運算 選擇運算 是一個單目運算 是從關(guān)系R中選取滿足一定條件的元組子集 記做 其中 是選擇運算符 F是限定條件的布爾表達式 由邏輯運算符 等連接關(guān)系表達式組成 關(guān)系表達式的基本形式為 X Y 其中 X Y可以是屬性名 常量或簡單函數(shù) 投影 Projection 運算 也是一個單目運算 是從關(guān)系R中選取所需要的列組成一個新關(guān)系 記做 A R t A t R 其中 是投影運算符 A為關(guān)系R屬性的子集 t A 為R中元組相應(yīng)于屬性A的分量連接 Jion 運算 是從2個關(guān)系的笛卡爾積中選取屬性間滿足一定連接條件的元組集合 專門的關(guān)系運算 除 Division 給定關(guān)系R X Y 和S Y Z 其中X Y Z是屬性組 R中的Y與S中的Y可以有不同的屬性名 但必須出自相同的域集 R與S的除運算得到一個新關(guān)系P X P是R中滿足下列條件的元組在X屬性列上的投影 R在X上分量值為X的諸元素在Y上投影的集合包含S在Y上投影的集合 除操作是同是從行和列的角度進行運算 除操作符用 表示 專門的關(guān)系運算 7 2 4數(shù)據(jù)庫設(shè)計與管理 數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的設(shè)計步驟 用戶需求分析概念設(shè)計邏輯設(shè)計物理設(shè)計數(shù)據(jù)庫實施數(shù)據(jù)庫的維護 數(shù)據(jù)庫設(shè)計的需求分析 用戶的信息要求用戶的處理要求對數(shù)據(jù)的安全性 完整性的要求 數(shù)據(jù)庫的概念設(shè)計 概念結(jié)構(gòu)設(shè)計 只講需求分析得到的用戶需求抽象為信息結(jié)構(gòu)即概念模型的過程概念結(jié)構(gòu)獨立于數(shù)據(jù)庫邏輯結(jié)構(gòu) 也獨立于支持數(shù)據(jù)庫的DBMS 它是現(xiàn)實世界與機器世界的中介 它一方面能夠充分反映現(xiàn)實世界 包括實體與實體之間的聯(lián)系 同時又易于向關(guān)系 網(wǎng)狀 層次等各種數(shù)據(jù)模式轉(zhuǎn)換 數(shù)據(jù)庫的邏輯設(shè)計 邏輯結(jié)構(gòu)設(shè)計的步驟 將概念結(jié)構(gòu)向一般關(guān)系模型轉(zhuǎn)化將第一步得到的結(jié)構(gòu)向特定的DBMS支持下的數(shù)據(jù)模型轉(zhuǎn)換依據(jù)應(yīng)用的需求和具體的DBMS特征進行調(diào)整與完善 數(shù)據(jù)庫的物理設(shè)計 確定數(shù)據(jù)的存儲安排存取路徑的選擇和調(diào)整確定系統(tǒng)配置 數(shù)據(jù)庫管理 數(shù)據(jù)庫的管理主要指 數(shù)據(jù)庫的實施和維護分三個步驟 數(shù)據(jù)的載入和應(yīng)用程序的調(diào)試數(shù)據(jù)庫的試運行數(shù)據(jù)庫的運行和維護 數(shù)據(jù)庫的維護 在數(shù)據(jù)庫運行階段 對數(shù)據(jù)庫經(jīng)常性的維護工作主要是由DBA完成的 包括 數(shù)據(jù)庫的存儲和恢復(fù)數(shù)據(jù)庫的安全性 完整性控制數(shù)據(jù)庫性能的監(jiān)督 分析和改進數(shù)據(jù)庫的重組織與重構(gòu)造 7 3數(shù)據(jù)結(jié)構(gòu)與算法 算法數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語線性表棧隊列樹與二叉樹查找與排序 7 3 1算法 定義 是對特定問題求解步驟的一種描述 或者說 是為求解某問題而設(shè)計的步驟序列特征 有窮性確定性有效性輸入輸出 算法復(fù)雜度 評價一個算法優(yōu)劣的主要標準是 算法的執(zhí)行效率與存儲需求算法的效率 指的是時間復(fù)雜度 TimeComplexity 存儲需求 指的是空間復(fù)雜度 SpaceComplexity 一般情況下 算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f n 算法的時間復(fù)雜度記做T n O f n 7 3 2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)是描述客觀事物的數(shù) 字符以及所有能輸入到計算機中并被計算機程序加工處理的符號的集合數(shù)據(jù)元素是數(shù)據(jù)的基本元素 即數(shù)據(jù)集合中的個體數(shù)據(jù)項具有獨立意義的最小數(shù)據(jù)單位數(shù)據(jù)對象具有相同特性的數(shù)據(jù)元素的集合 是數(shù)據(jù)的子集結(jié)構(gòu)被計算機加工的數(shù)據(jù)元素之間存在的關(guān)系數(shù)據(jù)結(jié)構(gòu)帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合 數(shù)據(jù)的邏輯結(jié)構(gòu) 集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀或網(wǎng)狀結(jié)構(gòu) 7 3 2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 數(shù)據(jù)的存儲結(jié)構(gòu) 一 順序存儲結(jié)構(gòu)主要特點 結(jié)點中只有自身信息域 沒有連接信息域 因此存儲密度大 存儲空間利用率高可以通過計算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個結(jié)點的存儲地址Li 計算公式 L0 i 1 m 其中L0為第一個結(jié)點的存儲地址 m為每個結(jié)點所占用的存儲單元個數(shù)插入 刪除運算不便 會引起大量結(jié)點的移動 7 3 2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 二 鏈式存儲結(jié)構(gòu) 主要特點 結(jié)點中除自身信息之外 還有表示連接信息的指針域 因此比順序存儲密度小 存儲空間利用率低邏輯上相鄰的結(jié)點物理上不必鄰接 可用于線性表 樹 圖等多種邏輯結(jié)構(gòu)的存儲表示插入 刪除操作靈活方便 不必移動結(jié)點 只要改變結(jié)點中的指針值即可 數(shù)據(jù)的運算 檢索 在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點插入 往數(shù)據(jù)結(jié)構(gòu)里增加新的結(jié)點刪除 把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)里去掉更新 改變指定結(jié)點的一個或多個域的值排序 保持線性結(jié)構(gòu)的結(jié)點序列里結(jié)點數(shù)不變 把結(jié)點按某種指定的順序重新排列 7 3 2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 7 3 3線性表 線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu) 線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列 a1 a2 an 順序表 指用順序存儲結(jié)構(gòu)存儲的線性表鏈表 用鏈式存儲結(jié)構(gòu)存儲的線性表棧和隊列 是對線性表的插入 刪除運算可以發(fā)生的位置加以限制的兩種特殊的線性表 順序表和一維數(shù)組 各種高級語言里的一維數(shù)組就是用順序方式存儲的線性表 因此常用一維數(shù)組稱呼順序表若順序表中結(jié)點個數(shù)為n 則 插入一個結(jié)點平均需要移動之結(jié)點個數(shù)為n 2 算法的時間復(fù)雜度是O n 刪除一個結(jié)點平均需移動結(jié)點個數(shù)為 n 1 2 算法的時間復(fù)雜度是O n 鏈表 線性鏈表 單鏈表 刪除算法的時間復(fù)雜度為O n 其主要執(zhí)行時間是搜索刪除位置循環(huán)鏈表 指鏈表的最后一個結(jié)點的指針值指向第一個結(jié)點 整個鏈表形成一個環(huán) 如下圖 結(jié)點1 結(jié)點2 結(jié)點n 7 3 4棧 棧 是一種特殊的線性表 是限定僅在表尾進行插入和刪除運算的線性表 表尾稱為棧頂 top 表頭稱為棧底 bottom 空棧 指表中無元素棧中有元素a1 a2 an 如下頁圖所示 稱a1為棧底元素 新元素進棧要置于an之上 刪除或退棧先對an進行 即 后進先出 LIFO 的操作原則棧的物理存儲可以用順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)棧的運算還有取棧頂元素 檢查棧是否為空 清除等 棧的插入和刪除 TOP TOP TOP TOP TOP TOP 進棧 出棧 棧底 棧結(jié)構(gòu) 3 1 2 5 4 6 7 3 5隊列 隊列 是限定所有的插入都在表的一端進行 所有的刪除都在表的另一端進行的線性表 進行刪除的一端叫隊列的頭 進行插入的一端叫隊列的尾 如下頁圖所示 在隊列中 新元素總是加入到隊尾 每次刪除的總是對頭元素 即當前 最老的 元素 這就是 先進先出 FIFO 的操作原則隊列的物理存儲可以用 順序存儲結(jié)構(gòu) 也可用鏈式存儲結(jié)構(gòu) 隊列的示意 如下圖 出隊列a1a2a3 an入隊列頭尾 隊列的插入和刪除示例 初態(tài) 插入A 插入B 刪除A 插入C 插入D 刪除B 插入E F R A F R R R R R R F F F F F F B A B B B C C C C D D D 溢出 7 3 6樹與二叉樹 樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu) 樹和二叉樹是最常見的樹形結(jié)構(gòu)樹 Tree 是一個或多個結(jié)點組成的有限集合T 有一個特定的結(jié)點稱為根 Root 其余的結(jié)點分為m m 0 個不相交的集合T1 T2 Tm 每個集合又是一棵樹 稱作這個根的子樹 Subtree 樹形結(jié)構(gòu)的常用術(shù)語 結(jié)點的度 Degree 一個結(jié)點的子樹的個數(shù)樹的度 樹中各結(jié)點的度的最大值樹葉 Leaf 度為0的結(jié)點分支結(jié)點 度不為0的結(jié)點雙親 Parent 子女 Child 結(jié)點的各子樹的根稱作該結(jié)點的子女 相應(yīng)的該結(jié)點稱作其子女的雙親兄弟 Sibling 具有相同雙親的結(jié)點互為兄弟結(jié)點的層數(shù) Level 樹的深度 Depth 森林 Forest 二叉樹 二叉樹 BinaryTree 是n n 0 個結(jié)點的有限集合 這個集合或者為空集 n 0 或者由一個根結(jié)點及兩棵不相交的 分別稱作這個根的坐姿樹和右子樹的二叉樹組成二叉樹不是樹的特殊情形 二者的區(qū)別 二叉樹為有序樹性質(zhì) 1 在二叉樹的i層上 最多有2i 1個結(jié)點 i 1 2 深度為k的二叉樹最多有2k 1個結(jié)點 k 1 完全二叉樹 一棵深度為k且具有2k 1個結(jié)點的二叉樹稱為滿二叉樹 FullBinaryTree 深度為k 有n個結(jié)點的二叉樹 當且僅當其妹一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時 稱為完全二叉樹 樹的二叉樹表示 在樹 森林 與二叉樹間有一個自然的一一對應(yīng)的關(guān)系 每一棵樹都能唯一的轉(zhuǎn)換到它所對應(yīng)的二叉樹把樹和森林轉(zhuǎn)化成對應(yīng)的二叉樹 凡是兄弟就用線連起來 然后去掉雙親到子女的連線 只留下道第一個子女的連線不去掉 二叉樹的存儲 二叉樹的存儲通常采用 鏈接方式 每個結(jié)點除存儲結(jié)點自身的信息外再設(shè)置兩個指針域IIink和rlink 分別指向結(jié)點的左子女和右子女 當結(jié)點的某個指針為空時 則相應(yīng)的指針值為空 NIL 結(jié)點的形式為 二叉樹的遍歷 遍歷一個樹形結(jié)構(gòu)是指 按一定次序系統(tǒng)的訪問該結(jié)構(gòu)中的所有結(jié)點 使每個結(jié)點恰好被訪問一次前序遍歷法 NLR次序 訪問根 按前序遍歷左子樹 按前序遍歷右子樹后序遍歷法 LRN次序 按后序遍歷左子樹 按后序遍歷右子樹 訪問根中序遍歷法 LNR次序 按中序遍歷左子樹 訪問根 按中序遍歷右子樹 7 3 7查找 查找 是數(shù)據(jù)結(jié)構(gòu)中的基本運算衡量一個查找運算法的主要標志是 查找過程中對關(guān)節(jié)碼進行的平均比較次數(shù) 或稱平均檢索長度 以n的函數(shù)的形式表示 n是數(shù)據(jù)結(jié)構(gòu)中的結(jié)點個數(shù) 順序查找 順序查找 是線性表的最簡單的查找方法方法 用待查關(guān)鍵碼與線性表中各結(jié)點的關(guān)鍵碼值逐個比較 若找出相等的關(guān)鍵碼值則查找成功 若找遍所有結(jié)點都不相等 則查找失敗優(yōu)點 對線性表的結(jié)點邏輯次序和存儲結(jié)構(gòu)無要求缺點 平均檢索長度大假設(shè)表中各結(jié)點被查找的概率相同 即P 1 n 則順序查找成功的平均查找長度為 n 1 2 二分法查找 二分法查找 是一種效率較高的線性表查找方法 要進行二分法查找 線性表結(jié)點必須是按關(guān)鍵碼值排號順序的 且線性表以順序方式存儲方法 首先用要查找的關(guān)鍵碼值與線性表中間位置結(jié)點的關(guān)鍵碼值相比較 這個中間結(jié)點把線性表分成兩個子表 比較相等則查找完成 不等則根據(jù)比較結(jié)果確定下一步的查找應(yīng)在哪個子表中進行 如此下去 直到找到滿足條件的結(jié)點優(yōu)點 平均檢索長度小 為 2n 每經(jīng)過一次關(guān)鍵碼比較 則將查找范圍縮小一半 因此經(jīng)過 2n次比較就可完成查找過程缺點 排序線性表花費時間 順序方式存儲插入 刪除不便 7 3 8排序 排序 是數(shù)據(jù)處理中經(jīng)常使用的一種運算分類 直接插入排序選擇排序冒泡排序快速排序 直接插入排序的基本方法 每步將一個待排序記錄按其關(guān)鍵碼值的大小插入到前面已排序的文件中適當位置上 直到全部插入為止選擇排序的基本思想 每一趟在n i 1 i 1 2 n 1 個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個記錄 它為最簡單且為我們最熟悉的排序冒泡排序的基本方法 將待排序的記錄順次兩兩比較 若為逆序 則進行交換快速排序 又稱分區(qū)交換排序 是對冒泡排序的一種改進 快速排序的基本方法 在待排序序列中任取一個記錄 以它為基準用交換的發(fā)方法將所有記錄分成兩部分 關(guān)鍵碼比它小的在一個部分 關(guān)鍵碼值比它大的在另一個部分 再分別對兩個部分實施上述過程 一直重復(fù)到排序完成下圖為四種排序方法的比較 7 4程序設(shè)計基礎(chǔ) 程序設(shè)計語言發(fā)展程序設(shè)計方法與風(fēng)格結(jié)構(gòu)化程序設(shè)計面向?qū)ο蟪绦蛟O(shè)計 程序設(shè)計 指令 能被計算機直接識別與執(zhí)行的指示計算機進行某種操作的命令 CPU每執(zhí)行一條指令 就完成一個基本運算 程序 指令的序列即讓計算機解決某一問題而寫出的一系列指令程序設(shè)計 編寫程序的過程程序設(shè)計語言 用于描述計算機所執(zhí)行的操作語言 7 4 1程序設(shè)計語言發(fā)展 機器語言 采用計算機指令格式并以二進制編碼表達各種操作的語言匯編語言 一種符號語言 采用助記符來表達指令功能高級語言 是一種面向問題的語言第四代語言 是非過程化語言 7 4 2程序設(shè)計方法與風(fēng)格 良好程序設(shè)計風(fēng)格的側(cè)重 源程序文檔如使用的符號名應(yīng)具有一定的含義 以便對程序功能的理解 對源程序適當?shù)倪M行注解 以便讀者理解程序 在程序中利用空格 空行 縮進等技巧使程序?qū)哟吻宄Τ绦蛑械臄?shù)據(jù)進行適當說明程序中的語句結(jié)構(gòu)應(yīng)該簡單直接 語句不復(fù)雜化要對程序的所有輸入數(shù)據(jù)檢查其合法性 檢查輸入項的各種重要組合的合理性 輸入格式要簡單 輸入允許默認值 輸入一批數(shù)據(jù)后最好使用結(jié)束標志 在交互式輸入 輸出中使用屏幕提示信息格式 7 4 3結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計的原則自頂向下逐步求精模塊化限制使用GOTO語句 結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)與特點順序結(jié)構(gòu) 按照程序語句行的自然順序 一條語句一條語句的往后執(zhí)行程序選擇結(jié)構(gòu) 又稱分支結(jié)構(gòu) 它根據(jù)設(shè)定的條件 判斷應(yīng)該選擇哪一條分支執(zhí)行相應(yīng)的語句序列循環(huán)結(jié)構(gòu) 又稱重復(fù)結(jié)構(gòu) 它根據(jù)給定的條件 判斷是否需要重復(fù)執(zhí)行某一相同的或相似的程序段 7 4 3結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計的優(yōu)點 自頂向下逐步求精的方法符合人類解決復(fù)雜問題的普遍規(guī)律 可以顯著提高軟件開發(fā)的成功率和生產(chǎn)率先全局后局部 先整體后細節(jié) 先抽向后具體的逐步求精過程開發(fā)出的程序有清晰的層次結(jié)構(gòu) 使程序容易閱讀和理解使用單入口單出口控制結(jié)構(gòu)而不使用GOTO語句 使得程序的靜態(tài)結(jié)構(gòu)和它的動態(tài)執(zhí)行情況一致控制結(jié)構(gòu)有確定邏輯模式 編寫程序代碼只限于使用很少幾種直截了當?shù)姆绞?使源程序清晰流暢 易讀易懂而且容易測試程序清晰和模塊化使得在修改和重新設(shè)計一個軟件時可以重用的代碼量最大程序的邏輯結(jié)構(gòu)清晰 有利于程序正確性證明 7 4 4面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο蠓椒ǖ闹饕攸c 從問題域中客觀存在的事物出發(fā)來構(gòu)造軟件系統(tǒng) 用對象作為對這些事物的抽象表示 并以此作為系統(tǒng)的基本構(gòu)成單位事物的靜態(tài)特征用對象的屬性表示 動態(tài)特征用對象的服務(wù)表示對象的屬性與服務(wù)結(jié)合為一個獨立的實體 對外屏蔽其內(nèi)部細節(jié) 稱作封裝把具有相同屬性和相同服務(wù)的對象歸為一類 類是這些對象的抽象描述 每個對象是它的類的一個實例 面向?qū)ο蠓椒ǖ闹饕攸c 通過在不同程度上運用抽象的原則 可以得到較一般的類和較特殊的類復(fù)雜的對象可以用簡單的對象作為其構(gòu)成部分 稱為聚合對象之間通過消息進行通信 以實現(xiàn)對象之間的動態(tài)聯(lián)系通過關(guān)聯(lián)表達對象之間的靜態(tài)關(guān)系 7 4 4面向?qū)ο蟮某绦蛟O(shè)計 面向?qū)ο蠓椒ǖ母拍?面向?qū)ο?面向?qū)ο?對象 類 繼承 通信如果一個軟件系統(tǒng)是使用這樣四個概念設(shè)計和實現(xiàn)的 則認為這個軟件系統(tǒng)是面向?qū)ο蟮?面向?qū)ο蟮某绦虻拿恳唤M成部分都是對象 計算是通過建立新的對象和對象之間的通信來執(zhí)行的 對象 對象是構(gòu)成世界的一個獨立單位 它具有自己的靜態(tài)特征和動態(tài)特征 靜態(tài)特征 指可以用某種數(shù)據(jù)來描述的特征動態(tài)特征 指對象所表現(xiàn)的行為或?qū)ο笏哂械墓δ芏x 對象是系統(tǒng)中用來描述客觀事物的一個實體 它是構(gòu)成系統(tǒng)的一個基本單位 一個對象由一組屬性和對這組屬性進行操作的一組方法構(gòu)成 屬性 用來描述對象靜態(tài)特征的一個數(shù)據(jù)項方法 用來描述對象動態(tài)特征的一個操作序列 消息和方法 一個系統(tǒng)由若干個對象組成 各個對象之間相互聯(lián)系 相互作用 計算機系統(tǒng)中 消息就是對象之間的紐帶 是用來通知 命令或請求對象執(zhí)行某個處理或回答某些信息 消息可以是數(shù)據(jù)流 也可以是控制流 一條消息可以發(fā)送給不同的對象 而消息的解釋則完全由接收對象完成 不同的對象對相同形式的消息可以有不同的解釋 類和實例 類和對象之間的關(guān)系如同一個模具與用這個模具鑄造出來的鑄件之間的關(guān)系 類給出了屬于該類的全部對象的抽象定義 而對象則是符合這種定義的一個實體 一個對象又稱為類的一個實例 Instance 類也可稱作對象的模板 Template 繼承性 定義 特殊類的對象擁有其一般類的全部屬性與方法 稱作特殊類對一般類的繼承繼承關(guān)系是傳遞的繼承性對于軟件重用有很大益處 封裝性 封裝具有兩個涵義 一 是把對象的全部屬性和全部方法結(jié)合在一起 形成一個不可分割的獨立單位 即對象 二 也稱作 信息隱蔽 即盡可能隱蔽對象的內(nèi)部細節(jié) 對外形成一個邊界 只保留有限的對外接口使之與外部發(fā)生聯(lián)系 多態(tài)性 對象的多態(tài)性 指在一般類中定義的屬性或方法被特殊類繼承之后 可以具有不同的數(shù)據(jù)類型表現(xiàn)出不同的行為 這使得同一個屬性或方法名在一般類及其各個特殊類中具有不同的語義 7 5多媒體技術(shù)簡介 多媒體技術(shù)的基本概念多媒體計算機系統(tǒng)多媒體計算機軟件系統(tǒng)多媒體信息的數(shù)字化和壓縮技術(shù) 7 5 1多媒體技術(shù)的基本概念 定義 指信息表示媒體的多樣化 多媒體的類型感覺媒體表示媒體顯示媒體傳輸媒體存儲媒體多媒體技術(shù)就是利用計算機把文本 聲音 視頻 動畫 圖形和圖像等多種媒體進行綜合處理 使多種信息建立邏輯連接 集成為一個具有交互性的系統(tǒng) 多媒體技術(shù)的特征 信息載體的多樣性交互性集成性實時性 多媒體信息中的媒體元素的類型 文本 Text 圖形 Graphic 圖像 Image 音頻動畫視頻 多媒體信息處理的關(guān)鍵技術(shù) 視頻和音頻數(shù)據(jù)壓縮和解壓縮技術(shù)關(guān)于壓縮編碼的國際標準有 JPEG標準電視電話 會議電視P 64Kbit s CCITTH 261 標準MPEG 1標準多媒體硬件系統(tǒng)的專用芯片大容量的外部存儲器多媒體同步技術(shù) 多媒體技術(shù)的應(yīng)用領(lǐng)域 教育與培訓(xùn)桌面出版多媒體電子出版物多媒體通信多媒體聲光藝術(shù)品的創(chuàng)作 7 5 2多媒體計算機系統(tǒng) 多媒體計算機系統(tǒng)的組成 如下圖 多媒體計算機系統(tǒng) 軟件系統(tǒng) 硬件系統(tǒng) 多媒體應(yīng)用軟件媒體處理系統(tǒng)工具軟件多媒體數(shù)據(jù)處理軟件多媒體操作系統(tǒng)多媒體驅(qū)動軟件 多媒體輸入 輸出控制卡及接口多媒體計算機硬件多媒體外圍設(shè)備 多媒體計算機硬件系統(tǒng) 主機 常規(guī)的主板 CPU及VGA適配卡 多功能卡等多媒體適配卡 音頻卡 視頻卡 圖形卡和壓縮卡等外部存儲設(shè)備 軟盤驅(qū)動器 硬盤驅(qū)動器和CD ROM驅(qū)動器輸入設(shè)備輸出設(shè)備 7 5 3多媒體計算機軟件系統(tǒng) 多媒體應(yīng)用程序 多媒體處理系統(tǒng)工具 多媒體操作系統(tǒng) 媒體控制接口 音頻 視頻核心處理 音頻 視頻設(shè)備驅(qū)動程序 音頻 視頻設(shè)備 多媒體計算機軟件的層次結(jié)構(gòu) 如右圖 第五層 第四層 第三層 第二層 第一層 7 5 4多媒體信息的數(shù)字化和壓縮技術(shù) 音頻信息聲音的特征模擬音頻和數(shù)字音頻衡量一個數(shù)字聲音波形的質(zhì)量有 采樣頻率 采樣精度 聲道數(shù)三個要素數(shù)字音頻文件的存儲格式數(shù)字音頻文件的存儲量存儲量 采樣頻率 量化位數(shù) 8 聲道數(shù) 時間 圖像信息 圖像信息的性能指標分辨率圖像深度和顯示深度圖像文件的大小 圖像文件的存儲格式 BMP格式PCX格式GIF格式TIF格式JPG和PIC格式PCD格式CDR格式PSD格式IFF格式DIF格式 視頻信息 視頻的彩色空間表示RGB彩色空間YUV和YIQ彩色空間模擬視頻標準 NTSC制式PAL制式SECAM制式 數(shù)字視頻視頻序列的時間碼數(shù)字視頻標準與文件格式 數(shù)字視頻標準與文件格式 MPEG標準MPEG 1 1992年正式發(fā)布 MPEG 2 1994年制定 MPEG 4 1999年正式發(fā)布 AVI格式PM格式QuickTime格式 數(shù)據(jù)壓縮技術(shù) 無損壓縮行程編碼 RLE Huffman編碼算術(shù)編碼LZW編碼有損壓縮三種數(shù)據(jù)壓縮國際標準 JPEG 靜止圖像壓縮標準 MPEG 運動圖像壓縮編碼標準 H 261 視頻通信編碼標準