軟件開發(fā)與信息處理技術(shù)課件(PPT 106頁)

1、第七章 軟件開發(fā)與信息處理技術(shù) 軟件工程基礎(chǔ) 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)與算法 程序設(shè)計(jì)基礎(chǔ) 多媒體技術(shù)簡介第1頁，共106頁。7.1 軟件工程基礎(chǔ) 軟件的規(guī)模大小決定了軟件開發(fā)的難度，因此，必須采用科學(xué)的軟件開發(fā)方法，采用抽象、分解等科學(xué)方法降低復(fù)雜度，以工程的方法管理和控制軟件開發(fā)的各個(gè)階段，以保證大型軟件系統(tǒng)的開發(fā)具有正確性、易維護(hù)性、可讀性和可重用性第2頁，共106頁。7.1.1 軟件工程基本概念 軟件的發(fā)展大致分為四個(gè)階段：（如下圖）階段第一階段第二階段第三階段第四階段程序設(shè)計(jì)階段程序系統(tǒng)階段軟件工程階段（結(jié)構(gòu)化方法發(fā)）軟件工程階段（面向?qū)ο蠓椒ǎ┑湫图夹g(shù)面向批處理有限的分布自定義軟件

2、多用戶實(shí)時(shí)數(shù)據(jù)庫軟件產(chǎn)品分布式系統(tǒng)嵌入“智能”低成本硬件消費(fèi)者的影響強(qiáng)大的桌面系統(tǒng)面向?qū)ο蠹夹g(shù)專家系統(tǒng)人工神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)計(jì)算機(jī)第3頁，共106頁。軟件危機(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）第4頁，共106頁。軟件工程過程和軟件生命周期 軟件工程過程 軟件生命周期 軟件生命周期

3、模型 軟件工程的目標(biāo)和原則 軟件開發(fā)工具與軟件開發(fā)環(huán)境第5頁，共106頁。 下圖為軟件生命周期各階段的任務(wù)：時(shí)期階段任務(wù)文檔軟件計(jì)劃問題定義理解用戶要求，劃清工作范圍計(jì)劃說明書可行性研究可行性方案及代價(jià)需求分析軟件系統(tǒng)的目標(biāo)及應(yīng)完成的工作需求規(guī)格說明書軟件開發(fā)概要設(shè)計(jì)系統(tǒng)的邏輯設(shè)計(jì)軟件概要設(shè)計(jì)說明書詳細(xì)設(shè)計(jì)系統(tǒng)模塊設(shè)計(jì)軟件詳細(xì)設(shè)計(jì)說明書軟件編碼編寫程序代碼程序、數(shù)據(jù)、詳細(xì)注釋軟件測試單元測試、綜合測試測試后的軟件、測試大綱、測試方案與結(jié)果軟件維護(hù)軟件維護(hù)運(yùn)行和維護(hù)維護(hù)后的軟件第6頁，共106頁。圖為軟件生命周期的瀑布模型和快速原形法模型軟件計(jì)劃需求分析軟件設(shè)計(jì)軟件編碼軟件測試軟件維護(hù)需求分析快

4、速設(shè)計(jì)建立模型用戶評(píng)價(jià)模型修改原型生產(chǎn)產(chǎn)品第7頁，共106頁。軟件工程目標(biāo)和原則目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性并滿足用戶需求的產(chǎn)品 軟件工程理論和技術(shù)性研究的內(nèi)容： 軟件開發(fā)技術(shù)和軟件管理技術(shù)原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性第8頁，共106頁。軟件開發(fā)工具與開發(fā)環(huán)境軟件開發(fā)工具：是為支持軟件人員開發(fā)和維護(hù)活動(dòng)而使用的軟件。作用：可以幫助開發(fā)人員完成一些繁瑣的程序編制和調(diào)試問題，是軟件開發(fā)人員將更多的精力和時(shí)間投放到最重要的軟件需求和設(shè)計(jì)上，提高軟件開發(fā)的速度和質(zhì)量。第9頁

5、，共106頁。7.1.2 結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法（Sructured Methodology）：是計(jì)算學(xué)科的一種典型的系統(tǒng)開發(fā)方法，它采用了系統(tǒng)科學(xué)的思想方法，從層次的角度，自頂向下的分析和設(shè)計(jì)系統(tǒng)。內(nèi)容：結(jié)構(gòu)化分析（ Sructured Analysis） 結(jié)構(gòu)化設(shè)計(jì)（ Sructured Design） 結(jié)構(gòu)化程序設(shè)計(jì)（Sructured Program Design）第10頁，共106頁。軟件開發(fā)過程 問題定義 可行性研究 需求分析與需求分析方法 結(jié)構(gòu)化分析方法概述 軟件需求規(guī)格說明書第11頁，共106頁。結(jié)構(gòu)化分析方法使用的工具 數(shù)據(jù)流圖（Data Flow Diagram）從數(shù)據(jù)傳

6、遞和加工的角度，以圖形方式刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過程 數(shù)據(jù)字典（Data Dictionary）需對(duì)數(shù)據(jù)流圖中的各個(gè)元素作完整的定義和說明，是數(shù)據(jù)流圖的補(bǔ)充工具 加工邏輯描述工具（常用：結(jié)構(gòu)化自然語言、判定樹和判定表）第12頁，共106頁。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ì)）第13頁，共106頁。概要設(shè)計(jì)概要設(shè)計(jì)又稱為總體設(shè)計(jì)，它的任務(wù)是確定軟件結(jié)構(gòu)結(jié)構(gòu)化設(shè)計(jì)方法的基本思

7、想：采用自頂向下的模塊化設(shè)計(jì)方法，按照模塊化原則和軟件設(shè)計(jì)策略，將需求分析得到的數(shù)據(jù)流圖，映射成由相對(duì)獨(dú)立、單一功能的模塊組成的軟件結(jié)構(gòu)第14頁，共106頁。概要設(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ī)格說明第15頁，共106頁。軟件結(jié)構(gòu)設(shè)計(jì)原則提高模塊獨(dú)立性模塊規(guī)模應(yīng)該適中模塊的深度、寬度、扇出和扇入適當(dāng)模塊的作用域應(yīng)該在控制域之內(nèi)降低模塊接口的復(fù)雜程度設(shè)計(jì)單入口和單出口模塊第16頁，共106頁。詳細(xì)設(shè)計(jì)任務(wù)：為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，并用某種工具描述出來結(jié)構(gòu)化

8、程序設(shè)計(jì)詳細(xì)設(shè)計(jì)工具（程序流程圖、盒圖N-S圖、PAD圖）詳細(xì)設(shè)計(jì)規(guī)格說明第17頁，共106頁。7.1.4 軟件測試一、軟件測試的目的與任務(wù)目的：確保軟件的質(zhì)量，盡量找出軟件錯(cuò)誤并加以糾正，而不是證明軟件沒有錯(cuò)。任務(wù)：測試任務(wù)（通過采用一定的測試策略，找出軟件中的錯(cuò)誤） 調(diào)試任務(wù)或糾錯(cuò)任務(wù)（如果測試到錯(cuò)誤，則定位軟件中的錯(cuò)誤，加以糾正）第18頁，共106頁。二、軟件測試的準(zhǔn)則三、軟件測試技術(shù)與方法綜述 方法：靜態(tài)測試法 動(dòng)態(tài)測試法 技術(shù)：白盒測試用例設(shè)計(jì) 黑盒測試用例設(shè)計(jì)7.1.4 軟件測試第19頁，共106頁。白盒測試用例設(shè)計(jì)、邏輯覆蓋 以程序的內(nèi)部邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計(jì)技術(shù)，它要求測

9、試人員十分清楚程序的邏輯結(jié)構(gòu)，考慮的是測試用例對(duì)程序內(nèi)部邏輯覆蓋的程度 根據(jù)覆蓋的目標(biāo)，可分為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、路徑覆蓋、基本路徑測試第20頁，共106頁。 黑盒測試用例設(shè)計(jì)分類： 等價(jià)類劃分法 邊界值分析法 錯(cuò)誤推測法 因果圖第21頁，共106頁。四、軟件測試的實(shí)施 單元測試 集成測試 確認(rèn)測試 系統(tǒng)測試五、軟件測試計(jì)劃與測試分析報(bào)告 測試是軟件生存周期中的一個(gè)獨(dú)立的關(guān)鍵的階段7.1.4 軟件測試第22頁，共106頁。未加入p243第23頁，共106頁。7.1.5 程序的調(diào)試程序調(diào)試可以分為：靜態(tài)調(diào)試（主要通過人的思維來分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段）動(dòng)

10、態(tài)調(diào)試（是靜態(tài)調(diào)試的輔助）主要的調(diào)試方法有： 強(qiáng)行排錯(cuò)法 回溯法 原因排除法第24頁，共106頁。7.2 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ) 數(shù)據(jù)庫概念 數(shù)據(jù)模型 關(guān)系代數(shù) 數(shù)據(jù)庫設(shè)計(jì)與管理第25頁，共106頁。7.2.1 數(shù)據(jù)庫概念數(shù)據(jù)（Data）數(shù)據(jù)處理（Data Processing）數(shù)據(jù)庫（Database，DB）數(shù)據(jù)庫管理系統(tǒng)（Database Management System，DBMS）數(shù)據(jù)庫管理員（Database Administrator，DBA）數(shù)據(jù)庫系統(tǒng)（ Database System ，DBS）數(shù)據(jù)庫應(yīng)用系統(tǒng)（ Database Application System，DBAS）第26頁

11、，共106頁。數(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ò)充）第27頁，共106頁。數(shù)據(jù)庫系統(tǒng)的基本功能 數(shù)據(jù)定義功能 數(shù)據(jù)操縱功能 數(shù)據(jù)庫運(yùn)行控制功能 數(shù)據(jù)庫的建立和維護(hù)功能第28頁，共106頁。數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)數(shù)據(jù)的結(jié)構(gòu)化數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨(dú)立性數(shù)據(jù)的統(tǒng)一管理與控制第29頁，共106頁。數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系模式：是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述，它僅僅涉及到型的描述，不涉及到具體的值。模式的一個(gè)具體值稱為模式的一個(gè)實(shí)例，同一個(gè)模式可以有多個(gè)實(shí)例

12、。數(shù)據(jù)庫管理系統(tǒng)采用三級(jí)模式結(jié)構(gòu):概念模式、 外模式（是概念模式的邏輯子集，也稱子模式或用戶模式） 內(nèi)模式（也稱存儲(chǔ)模式） 并提供二級(jí)映像功能第30頁，共106頁。7.2.2 數(shù)據(jù)模型數(shù)據(jù)模型（data model）：是表示實(shí)體類型及實(shí)體之間聯(lián)系的模型數(shù)據(jù)模式的三個(gè)要素： 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)操作 數(shù)據(jù)的完整性約束條件第31頁，共106頁。 數(shù)據(jù)模型的三個(gè)級(jí)別： 概念數(shù)據(jù)模型 邏輯數(shù)據(jù)模型 物理數(shù)據(jù)模型7.2.2 數(shù)據(jù)模型第32頁，共106頁。數(shù)據(jù)模型的分類 E-R 模型（實(shí)體聯(lián)系模型） 是直接從現(xiàn)實(shí)世界中抽象出實(shí)體類型及實(shí)體間聯(lián)系，然后用實(shí)體聯(lián)系圖（E-R圖）表示數(shù)據(jù)模型 層次模型（若用圖表示，它

13、是一棵倒立的樹） 網(wǎng)狀模型（若用圖表示是一個(gè)網(wǎng)絡(luò)） 關(guān)系模型（數(shù)據(jù)的邏輯結(jié)構(gòu)是一張二維表）第33頁，共106頁。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ǔ)第34頁，共106頁。傳統(tǒng)的集合運(yùn)算并（Union)關(guān)系R和關(guān)系S的并記做RS，由屬于R或S的元組組成，結(jié)果仍為n目關(guān)系差（Difference）關(guān)系R和關(guān)系S的差記做R-S，由屬于R不屬于S的元組組成，結(jié)果仍為n目關(guān)系交（Inters

14、ection）關(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)列的元組的集合第35頁，共106頁。關(guān)系R和S及其三種傳統(tǒng)的集合運(yùn)算（如下圖）ABCa1a2a3b1b2b3c1c2c3ABCa1a2a3b1b2b3c1c2c3ABCA1A1A2a1B1B2B2b3C1C2C1c2ABCb1c1ABCA1a2B2b2C2c1關(guān)系R關(guān)系SRSRSR-S第36頁，共106頁。專門的關(guān)系運(yùn)算選擇運(yùn)算：是一個(gè)單目運(yùn)算，是從關(guān)系R中選取滿足一定條件的元組子集。記做： 其中 是選擇運(yùn)算符；F是限定條件的布

15、爾表達(dá)式，由邏輯運(yùn)算符、等連接關(guān)系表達(dá)式組成。關(guān)系表達(dá)式的基本形式為：XY，其 中=、=、，X、Y可以是屬性名、常量或簡單函數(shù)第37頁，共106頁。投影（Projection）運(yùn)算：也是一個(gè)單目運(yùn)算，是從關(guān)系R中選取所需要的列組成一個(gè)新關(guān)系。記做： A（R）tA tR 其中是投影運(yùn)算符；A為關(guān)系R屬性的子集；tA為R中元組相應(yīng)于屬性A的分量連接（Jion）運(yùn)算：是從2個(gè)關(guān)系的笛卡爾積中選取屬性間滿足一定連接條件的元組集合專門的關(guān)系運(yùn)算第38頁，共106頁。除（Division）： 給定關(guān)系R（X，Y）和S（Y，Z）其中X，Y，Z是屬性組。R中的Y與S中的Y可以有不同的屬性名，但必須出自相同的域

16、集。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)算第39頁，共106頁。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ù)第40頁，共106頁。數(shù)據(jù)庫設(shè)計(jì)的需求分析 用戶的信息要求 用戶的處理要求 對(duì)數(shù)據(jù)的安全性、完整性的要求第41頁，共106頁。數(shù)據(jù)庫的概念設(shè)計(jì)概念結(jié)構(gòu)設(shè)計(jì)：只講需求分析得到的用戶需求抽象為信息結(jié)構(gòu)即概念模型的過程概念結(jié)構(gòu)獨(dú)立

17、于數(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)換。第42頁，共106頁。數(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)整與完善第43頁，共106頁。數(shù)據(jù)庫的物理設(shè)計(jì) 確定數(shù)據(jù)的存儲(chǔ)安排 存取路徑的選擇和調(diào)整 確定系統(tǒng)配置第44頁，共106頁。數(shù)據(jù)庫管理數(shù)據(jù)庫的管理主要指： 數(shù)據(jù)庫的實(shí)施和維護(hù)分三個(gè)步驟： 數(shù)據(jù)的載入和應(yīng)用程序的調(diào)試 數(shù)據(jù)庫的試運(yùn)行 數(shù)

18、據(jù)庫的運(yùn)行和維護(hù)第45頁，共106頁。數(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)造第46頁，共106頁。7.3 數(shù)據(jù)結(jié)構(gòu)與算法 算法 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 線性表 棧 隊(duì)列 樹與二叉樹 查找與排序第47頁，共106頁。7.3.1 算法定義：是對(duì)特定問題求解步驟的一種描述?；蛘哒f，是為求解某問題而設(shè)計(jì)的步驟序列特征： 有窮性 確定性 有效性 輸入 輸出第48頁，共106頁。算法復(fù)雜度評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)是： 算法的執(zhí)行效率與存儲(chǔ)需求算法的效率：指的

19、是時(shí)間復(fù)雜度（Time Complexity）存儲(chǔ)需求：指的是空間復(fù)雜度（Space Complexity ） 一般情況下，算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間復(fù)雜度記做 T(n)=O(f(n)第49頁，共106頁。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ù)元素

20、的集合第50頁，共106頁。數(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ù)語第51頁，共106頁。數(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ù)語第52頁，共106頁。二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)主要特點(diǎn)：結(jié)點(diǎn)中除自身信息之外，還有表示連接信息的指針域，因此比順序存儲(chǔ)密度小，

21、存儲(chǔ)空間利用率低邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示插入、刪除操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針值即可第53頁，共106頁。 數(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ù)語第54頁，共106頁。7.3.3 線性表 線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列（a1,a2,an）順序表：指用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的

22、線性表鏈表：用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表?xiàng)：完?duì)列是對(duì)線性表的插入、刪除運(yùn)算可以發(fā)生的位置加以限制的兩種特殊的線性表第55頁，共106頁。順序表和一維數(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)第56頁，共106頁。鏈 表線性鏈表（單鏈表）：刪除算法的時(shí)間復(fù)雜度為O(n)，其主要執(zhí)行時(shí)間是搜索刪除位置循環(huán)鏈表：指鏈表的最后一個(gè)結(jié)點(diǎn)的指針值指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)（如下圖）

23、結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)n第57頁，共106頁。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)算還有取棧頂元素，檢查棧是否為空，清除等。第58頁，共106頁。棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPana2a1進(jìn)棧出棧棧底棧結(jié)構(gòu)(3)(1)(2)(5)(4)(6

24、)第59頁，共106頁。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)第60頁，共106頁。隊(duì)列的示意（如下圖）出隊(duì)列 a1 a2 a3 an 入隊(duì)列 頭 尾第61頁，共106頁。隊(duì)列的插入和刪除示例初態(tài)插入A插入B刪除A插入C插入D刪除B插入EFRAFRRRRRRFFFFFFBABBBCCCCDDD溢出第6

25、2頁，共106頁。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（m0）個(gè)不相交的集合T1，T2，Tm，每個(gè)集合又是一棵樹，稱作這個(gè)根的子樹（Subtree)第63頁，共106頁。樹形結(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）：具有相

26、同雙親的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)的層數(shù)（Level）樹的深度（Depth）森林（Forest）第64頁，共106頁。二 叉 樹二叉樹（Binary Tree）:是n（n0)個(gè)結(jié)點(diǎn)的有限集合，這個(gè)集合或者為空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵不相交的、分別稱作這個(gè)根的坐姿樹和右子樹的二叉樹組成 二叉樹不是樹的特殊情形，二者的區(qū)別： 二叉樹為有序樹性質(zhì)：1、在二叉樹的i層上，最多有2i-1個(gè)結(jié)點(diǎn)（i1） 2、 深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)(k1)第65頁，共106頁。完全二叉樹一棵深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹（Full Binary Tree ）深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹，

27、當(dāng)且僅當(dāng)其妹一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹第66頁，共106頁。樹的二叉樹表示在樹（森林）與二叉樹間有一個(gè)自然的一一對(duì)應(yīng)的關(guān)系，每一棵樹都能唯一的轉(zhuǎn)換到它所對(duì)應(yīng)的二叉樹把樹和森林轉(zhuǎn)化成對(duì)應(yīng)的二叉樹： 凡是兄弟就用線連起來，然后去掉雙親到子女的連線，只留下道第一個(gè)子女的連線不去掉第67頁，共106頁。二叉樹的存儲(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)的形式為：IIinkinforlink第68頁，

28、共106頁。二叉樹的遍歷遍歷一個(gè)樹形結(jié)構(gòu)是指：按一定次序系統(tǒng)的訪問該結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次前序遍歷法（NLR次序）訪問根，按前序遍歷左子樹，按前序遍歷右子樹后序遍歷法（LRN次序）按后序遍歷左子樹，按后序遍歷右子樹，訪問根中序遍歷法（LNR次序）按中序遍歷左子樹，訪問根，按中序遍歷右子樹第69頁，共106頁。7.3.7 查找 查找：是數(shù)據(jù)結(jié)構(gòu)中的基本運(yùn)算 衡量一個(gè)查找運(yùn)算法的主要標(biāo)志是： 查找過程中對(duì)關(guān)節(jié)碼進(jìn)行的平均比較次數(shù)，或稱平均檢索長度，以n的函數(shù)的形式表示，n是數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)個(gè)數(shù)第70頁，共106頁。順序查找順序查找：是線性表的最簡單的查找方法方法：用待查關(guān)鍵碼與

29、線性表中各結(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)：平均檢索長度大假設(shè)表中各結(jié)點(diǎn)被查找的概率相同，即P=1/n,則順序查找成功的平均查找長度為(n+1)/2第71頁，共106頁。二分法查找二分法查找：是一種效率較高的線性表查找方法。要進(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)行，如此下去，直到找到

30、滿足條件的結(jié)點(diǎn)優(yōu)點(diǎn)：平均檢索長度小，為 2n。每經(jīng)過一次關(guān)鍵碼比較，則將查找范圍縮小一半，因此經(jīng)過2n次比較就可完成查找過程缺點(diǎn)：排序線性表花費(fèi)時(shí)間，順序方式存儲(chǔ)插入、刪除不便第72頁，共106頁。7.3.8 排序排序：是數(shù)據(jù)處理中經(jīng)常使用的一種運(yùn)算分類： 直接插入排序 選擇排序 冒泡排序 快速排序第73頁，共106頁。直接插入排序的基本方法：每步將一個(gè)待排序記錄按其關(guān)鍵碼值的大小插入到前面已排序的文件中適當(dāng)位置上，直到全部插入為止選擇排序的基本思想：每一趟在n-i+1(i=1,2,n-1）個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個(gè)記錄。它為最簡單且為我們最熟悉的排序冒泡排序的基本方法

31、：將待排序的記錄順次兩兩比較，若為逆序，則進(jìn)行交換快速排序：又稱分區(qū)交換排序，是對(duì)冒泡排序的一種改進(jìn)。第74頁，共106頁?？焖倥判虻幕痉椒ǎ涸诖判蛐蛄兄腥稳∫粋€(gè)記錄，以它為基準(zhǔn)用交換的發(fā)方法將所有記錄分成兩部分，關(guān)鍵碼比它小的在一個(gè)部分，關(guān)鍵碼值比它大的在另一個(gè)部分。再分別對(duì)兩個(gè)部分實(shí)施上述過程，一直重復(fù)到排序完成下圖為四種排序方法的比較：排序方法平均時(shí)間最壞情況輔助存儲(chǔ)直接插入排序選擇排序冒泡排序快速排序O(n2)O(n2)O(n2)O(n 2n)O(n2)O(n2)O(n2)O(n2)O(1)O(1)O(1)O(2n)第75頁，共106頁。7.4 程序設(shè)計(jì)基礎(chǔ) 程序設(shè)計(jì)語言發(fā)展 程序

32、設(shè)計(jì)方法與風(fēng)格 結(jié)構(gòu)化程序設(shè)計(jì) 面向?qū)ο蟪绦蛟O(shè)計(jì)第76頁，共106頁。程序設(shè)計(jì)指令：能被計(jì)算機(jī)直接識(shí)別與執(zhí)行的指示計(jì)算機(jī)進(jìn)行某種操作的命令，CPU每執(zhí)行一條指令，就完成一個(gè)基本運(yùn)算。程序：指令的序列即讓計(jì)算機(jī)解決某一問題而寫出的一系列指令程序設(shè)計(jì)：編寫程序的過程程序設(shè)計(jì)語言：用于描述計(jì)算機(jī)所執(zhí)行的操作語言第77頁，共106頁。7.4.1 程序設(shè)計(jì)語言發(fā)展機(jī)器語言：采用計(jì)算機(jī)指令格式并以二進(jìn)制編碼表達(dá)各種操作的語言匯編語言：一種符號(hào)語言，采用助記符來表達(dá)指令功能高級(jí)語言：是一種面向問題的語言第四代語言：是非過程化語言第78頁，共106頁。7.4.2 程序設(shè)計(jì)方法與風(fēng)格 良好程序設(shè)計(jì)風(fēng)格的側(cè)重：

33、源程序文檔如使用的符號(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)該簡單直接，語句不復(fù)雜化 要對(duì)程序的所有輸入數(shù)據(jù)檢查其合法性，檢查輸入項(xiàng)的各種重要組合的合理性，輸入格式要簡單，輸入允許默認(rèn)值，輸入一批數(shù)據(jù)后最好使用結(jié)束標(biāo)志，在交互式輸入/輸出中使用屏幕提示信息格式第79頁，共106頁。7.4.3 結(jié)構(gòu)化程序設(shè)計(jì) 結(jié)構(gòu)化程序設(shè)計(jì)的原則 自頂向下 逐步求精 模塊化 限制使用GOTO語句第80頁，共106頁。 結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)與特點(diǎn) 順序結(jié)構(gòu)：按照程序語句

34、行的自然順序，一條語句一條語句的往后執(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ì)第81頁，共106頁。結(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)有確定邏輯模式，編寫程序代碼

35、只限于使用很少幾種直截了當(dāng)?shù)姆绞?，使源程序清晰流暢，易讀易懂而且容易測試程序清晰和模塊化使得在修改和重新設(shè)計(jì)一個(gè)軟件時(shí)可以重用的代碼量最大程序的邏輯結(jié)構(gòu)清晰，有利于程序正確性證明第82頁，共106頁。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í)例第83頁，共106頁。 面向

36、對(duì)象方法的主要特點(diǎn)：通過在不同程度上運(yùn)用抽象的原則，可以得到較一般的類和較特殊的類復(fù)雜的對(duì)象可以用簡單的對(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ì)第84頁，共106頁。面向?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í)行的第85頁，共106頁。對(duì) 象 對(duì)象是構(gòu)成世界的一個(gè)獨(dú)立單位，它具有自己的靜態(tài)特征和動(dòng)態(tài)特征。靜態(tài)特征：指可以

37、用某種數(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è)操作序列第86頁，共106頁。消息和方法一個(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ì)相同形式的消息可以有不同的解釋第8

38、7頁，共106頁。類和實(shí)例類和對(duì)象之間的關(guān)系 如同一個(gè)模具與用這個(gè)模具鑄造出來的鑄件之間的關(guān)系。類給出了屬于該類的全部對(duì)象的抽象定義，而對(duì)象則是符合這種定義的一個(gè)實(shí)體。一個(gè)對(duì)象又稱為類的一個(gè)實(shí)例（Instance）類也可稱作對(duì)象的模板（Template）第88頁，共106頁。繼 承 性定義：特殊類的對(duì)象擁有其一般類的全部屬性與方法，稱作特殊類對(duì)一般類的繼承繼承關(guān)系是傳遞的繼承性對(duì)于軟件重用有很大益處第89頁，共106頁。封 裝 性封裝具有兩個(gè)涵義：一、是把對(duì)象的全部屬性和全部方法結(jié)合在一起，形成一個(gè)不可分割的獨(dú)立單位（即對(duì)象）二、也稱作“信息隱蔽”，即盡可能隱蔽對(duì)象的內(nèi)部細(xì)節(jié)，對(duì)外形成一個(gè)邊界，只保留有限的對(duì)外接口使之與外部發(fā)生聯(lián)系第90頁，共106頁。多 態(tài) 性對(duì)象的多態(tài)性： 指在一般類中定義的屬性或方法被特殊類繼承之后，可以具有不同的數(shù)據(jù)類型表現(xiàn)出不同的行為。這使得同一個(gè)屬性或方法名在一般類及其各個(gè)特殊類中具有不同的語義第91頁，共106頁。7.5 多媒體技術(shù)簡介多媒體技術(shù)的基本概念多媒體計(jì)算機(jī)系統(tǒng)多媒體計(jì)算機(jī)軟件系統(tǒng)多媒體信息的數(shù)字化和壓縮技術(shù)第92頁，共106頁。7.5.1 多媒體技術(shù)的基本概念定義：指信息表示媒體的多樣化。多媒體的類型感覺媒體 表示媒體 顯示媒體 傳輸媒