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

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

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