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

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

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