什么是軟件開發(fā)與信息處理技術(shù)？課件

第七章軟件開發(fā)與信息處理技術(shù)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)多媒體技術(shù)簡介第七章軟件開發(fā)與信息處理技術(shù)軟件工程基礎(chǔ)17.1軟件工程基礎(chǔ)

軟件的規(guī)模大小決定了軟件開發(fā)的難度，因此，必須采用科學(xué)的軟件開發(fā)方法，采用抽象、分解等科學(xué)方法降低復(fù)雜度，以工程的方法管理和控制軟件開發(fā)的各個階段，以保證大型軟件系統(tǒng)的開發(fā)具有正確性、易維護性、可讀性和可重用性7.1軟件工程基礎(chǔ)軟件的規(guī)模大小決定了軟27.1.1軟件工程基本概念

軟件的發(fā)展大致分為四個階段：（如下圖）階段第一階段第二階段第三階段第四階段程序設(shè)計階段程序系統(tǒng)階段軟件工程階段（結(jié)構(gòu)化方法發(fā)）軟件工程階段（面向?qū)ο蠓椒ǎ┑湫图夹g(shù)面向批處理有限的分布自定義軟件多用戶實時數(shù)據(jù)庫軟件產(chǎn)品分布式系統(tǒng)嵌入“智能”低成本硬件消費者的影響強大的桌面系統(tǒng)面向?qū)ο蠹夹g(shù)專家系統(tǒng)人工神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)計算機7.1.1軟件工程基本概念軟件的發(fā)展大致分3軟件危機和軟件工程軟件危機主要表現(xiàn)在：對軟件開發(fā)成本和進度的估計常常很不準確，經(jīng)費預(yù)算經(jīng)常突破，完成時間一再拖延；開發(fā)的軟件不能滿足用戶要求，用戶軟件不滿意的現(xiàn)象經(jīng)常發(fā)生；開發(fā)的軟件可維護性差、可靠性差軟件工程：運用系統(tǒng)的、規(guī)范的和可定量的方法開發(fā)、運行和維護軟件。它包含三個要素：方法（Methodologies）工具（Tools）過程（Procedures）軟件危機和軟件工程軟件危機主要表現(xiàn)在：對軟件開發(fā)成本和進度的4軟件工程過程和軟件生命周期

軟件工程過程

軟件生命周期

軟件生命周期模型

軟件工程的目標和原則軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件工程過程和軟件生命周期軟件工程過程5

下圖為軟件生命周期各階段的任務(wù)：時期階段任務(wù)文檔軟件計劃問題定義理解用戶要求，劃清工作范圍計劃說明書可行性研究可行性方案及代價需求分析軟件系統(tǒng)的目標及應(yīng)完成的工作需求規(guī)格說明書軟件開發(fā)概要設(shè)計系統(tǒng)的邏輯設(shè)計軟件概要設(shè)計說明書詳細設(shè)計系統(tǒng)模塊設(shè)計軟件詳細設(shè)計說明書軟件編碼編寫程序代碼程序、數(shù)據(jù)、詳細注釋軟件測試單元測試、綜合測試測試后的軟件、測試大綱、測試方案與結(jié)果軟件維護軟件維護運行和維護維護后的軟件下圖為軟件生命周期各階段的任務(wù)：時期階段任務(wù)文檔問題6圖為軟件生命周期的瀑布模型和快速原形法模型軟件計劃需求分析軟件設(shè)計軟件編碼軟件測試軟件維護需求分析快速設(shè)計建立模型用戶評價模型修改原型生產(chǎn)產(chǎn)品圖為軟件生命周期的瀑布模型和快速原形法模型軟件計劃需求分析軟7軟件工程目標和原則目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性并滿足用戶需求的產(chǎn)品

軟件工程理論和技術(shù)性研究的內(nèi)容：軟件開發(fā)技術(shù)和軟件管理技術(shù)原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性軟件工程目標和原則目標：在給定成本、進度的前提下，開發(fā)出具有8軟件開發(fā)工具與開發(fā)環(huán)境軟件開發(fā)工具：是為支持軟件人員開發(fā)和維護活動而使用的軟件。作用：可以幫助開發(fā)人員完成一些繁瑣的程序編制和調(diào)試問題，是軟件開發(fā)人員將更多的精力和時間投放到最重要的軟件需求和設(shè)計上，提高軟件開發(fā)的速度和質(zhì)量。軟件開發(fā)工具與開發(fā)環(huán)境軟件開發(fā)工具：是為支持軟件人員開發(fā)和維97.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）7.1.2結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法（Sructured10軟件開發(fā)過程

問題定義可行性研究需求分析與需求分析方法結(jié)構(gòu)化分析方法概述軟件需求規(guī)格說明書軟件開發(fā)過程問題定義11結(jié)構(gòu)化分析方法使用的工具

數(shù)據(jù)流圖（DataFlowDiagram）從數(shù)據(jù)傳遞和加工的角度，以圖形方式刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程

數(shù)據(jù)字典（DataDictionary）需對數(shù)據(jù)流圖中的各個元素作完整的定義和說明，是數(shù)據(jù)流圖的補充工具

加工邏輯描述工具（常用：結(jié)構(gòu)化自然語言、判定樹和判定表）結(jié)構(gòu)化分析方法使用的工具數(shù)據(jù)流圖（DataFlowD127.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è)計）7.1.3結(jié)構(gòu)化設(shè)計方法軟件設(shè)計的基本概念：是一個把軟件13概要設(shè)計概要設(shè)計又稱為總體設(shè)計，它的任務(wù)是確定軟件結(jié)構(gòu)結(jié)構(gòu)化設(shè)計方法的基本思想：采用自頂向下的模塊化設(shè)計方法，按照模塊化原則和軟件設(shè)計策略，將需求分析得到的數(shù)據(jù)流圖，映射成由相對獨立、單一功能的模塊組成的軟件結(jié)構(gòu)概要設(shè)計概要設(shè)計又稱為總體設(shè)計，它的任務(wù)是確定軟件結(jié)構(gòu)14概要設(shè)計概要設(shè)計的圖形工具（層次圖、HIPO圖、軟件結(jié)構(gòu)圖）軟件設(shè)計原理軟件結(jié)構(gòu)設(shè)計原則面向數(shù)據(jù)流的設(shè)計方法（變換流分析設(shè)計和事務(wù)流分析設(shè)計）設(shè)計規(guī)格說明概要設(shè)計概要設(shè)計的圖形工具（層次圖、HIPO圖、軟件結(jié)構(gòu)圖）15軟件結(jié)構(gòu)設(shè)計原則提高模塊獨立性模塊規(guī)模應(yīng)該適中模塊的深度、寬度、扇出和扇入適當模塊的作用域應(yīng)該在控制域之內(nèi)降低模塊接口的復(fù)雜程度設(shè)計單入口和單出口模塊軟件結(jié)構(gòu)設(shè)計原則提高模塊獨立性16詳細設(shè)計任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，并用某種工具描述出來結(jié)構(gòu)化程序設(shè)計詳細設(shè)計工具（程序流程圖、盒圖[N-S圖]、PAD圖）詳細設(shè)計規(guī)格說明詳細設(shè)計任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)177.1.4軟件測試一、軟件測試的目的與任務(wù)目的：確保軟件的質(zhì)量，盡量找出軟件錯誤并加以糾正，而不是證明軟件沒有錯。任務(wù)：測試任務(wù)（通過采用一定的測試策略，找出軟件中的錯誤）調(diào)試任務(wù)或糾錯任務(wù)（如果測試到錯誤，則定位軟件中的錯誤，加以糾正）7.1.4軟件測試一、軟件測試的目的與任務(wù)18二、軟件測試的準則三、軟件測試技術(shù)與方法綜述

方法：靜態(tài)測試法動態(tài)測試法

技術(shù)：白盒測試用例設(shè)計黑盒測試用例設(shè)計7.1.4軟件測試二、軟件測試的準則7.1.4軟件測試19白盒測試用例設(shè)計、邏輯覆蓋以程序的內(nèi)部邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù)，它要求測試人員十分清楚程序的邏輯結(jié)構(gòu)，考慮的是測試用例對程序內(nèi)部邏輯覆蓋的程度根據(jù)覆蓋的目標，可分為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、路徑覆蓋、基本路徑測試白盒測試用例設(shè)計、邏輯覆蓋20

黑盒測試用例設(shè)計分類：

等價類劃分法邊界值分析法錯誤推測法因果圖黑盒測試用例設(shè)計分類：21四、軟件測試的實施

單元測試集成測試確認測試系統(tǒng)測試五、軟件測試計劃與測試分析報告測試是軟件生存周期中的一個獨立的關(guān)鍵的階段7.1.4軟件測試四、軟件測試的實施7.1.4軟件測試22未加入p243未加入p243237.1.5程序的調(diào)試程序調(diào)試可以分為：靜態(tài)調(diào)試（主要通過人的思維來分析源程序代碼和排錯，是主要的調(diào)試手段）動態(tài)調(diào)試（是靜態(tài)調(diào)試的輔助）主要的調(diào)試方法有：強行排錯法回溯法原因排除法7.1.5程序的調(diào)試程序調(diào)試可以分為：247.2數(shù)據(jù)庫設(shè)計基礎(chǔ)

數(shù)據(jù)庫概念數(shù)據(jù)模型關(guān)系代數(shù)數(shù)據(jù)庫設(shè)計與管理7.2數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫概念257.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）7.2.1數(shù)據(jù)庫概念數(shù)據(jù)（Data）26數(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)的發(fā)展人工管理階段27數(shù)據(jù)庫系統(tǒng)的基本功能

數(shù)據(jù)定義功能數(shù)據(jù)操縱功能數(shù)據(jù)庫運行控制功能數(shù)據(jù)庫的建立和維護功能數(shù)據(jù)庫系統(tǒng)的基本功能數(shù)據(jù)定義功能28數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的結(jié)構(gòu)化數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)的統(tǒng)一管理與控制數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的結(jié)構(gòu)化29數(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)模式（也稱存儲模式）并提供二級映像功能數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系模式：是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和307.2.2數(shù)據(jù)模型數(shù)據(jù)模型（datamodel）：是表示實體類型及實體之間聯(lián)系的模型數(shù)據(jù)模式的三個要素：

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的完整性約束條件7.2.2數(shù)據(jù)模型數(shù)據(jù)模型（datamodel）：是31

數(shù)據(jù)模型的三個級別：

概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型7.2.2數(shù)據(jù)模型數(shù)據(jù)模型的三個級別：7.2.2數(shù)據(jù)模型32數(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)是一張二維表）數(shù)據(jù)模型的分類E-R模型（實體聯(lián)系模型）337.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ǔ)7.2.3關(guān)系代數(shù)關(guān)系代數(shù)：是一種抽象的查詢語言，是關(guān)34傳統(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)列的元組的集合傳統(tǒng)的集合運算并（Union)關(guān)系R和關(guān)系S的并記做R∪S，35關(guān)系R和S及其三種傳統(tǒng)的集合運算（如下圖）ABCa1a2a3b1b2b3c1c2c3ABCa1a2a3b1b2b3c1c2c3ABCA1A1A2a1B1B2B2b3C1C2C1c2ABCb1c1ABCA1a2B2b2C2c1關(guān)系R關(guān)系SR∩SR∪SR-S關(guān)系R和S及其三種傳統(tǒng)的集合運算（如下圖）ABCa1b1c136專門的關(guān)系運算選擇運算：是一個單目運算，是從關(guān)系R中選取滿足一定條件的元組子集。記做：其中σ

是選擇運算符；F是限定條件的布爾表達式，由邏輯運算符∧、∨等連接關(guān)系表達式組成。關(guān)系表達式的基本形式為：XθY，其中θ={>、≥、<、≤、=、≠}，X、Y可以是屬性名、常量或簡單函數(shù)專門的關(guān)系運算選擇運算：是一個單目運算，是從關(guān)系R中選取滿足37投影（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)系運算投影（Projection）運算：也是一個單目運算，是從關(guān)系38除（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)系運算除（Division）：專門的關(guān)系運算397.2.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的設(shè)計步驟：用戶需求分析概念設(shè)計邏輯設(shè)計物理設(shè)計數(shù)據(jù)庫實施數(shù)據(jù)庫的維護7.2.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的設(shè)計步40數(shù)據(jù)庫設(shè)計的需求分析

用戶的信息要求用戶的處理要求對數(shù)據(jù)的安全性、完整性的要求數(shù)據(jù)庫設(shè)計的需求分析用戶的信息要求41數(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è)計：只講需求分析得到的用戶需求抽象42數(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è)計邏輯結(jié)構(gòu)設(shè)計的步驟：43數(shù)據(jù)庫的物理設(shè)計

確定數(shù)據(jù)的存儲安排存取路徑的選擇和調(diào)整確定系統(tǒng)配置數(shù)據(jù)庫的物理設(shè)計確定數(shù)據(jù)的存儲安排44數(shù)據(jù)庫管理數(shù)據(jù)庫的管理主要指：

數(shù)據(jù)庫的實施和維護分三個步驟：數(shù)據(jù)的載入和應(yīng)用程序的調(diào)試數(shù)據(jù)庫的試運行數(shù)據(jù)庫的運行和維護數(shù)據(jù)庫管理數(shù)據(jù)庫的管理主要指：45數(shù)據(jù)庫的維護在數(shù)據(jù)庫運行階段，對數(shù)據(jù)庫經(jīng)常性的維護工作主要是由DBA完成的。包括：

數(shù)據(jù)庫的存儲和恢復(fù)數(shù)據(jù)庫的安全性、完整性控制數(shù)據(jù)庫性能的監(jiān)督、分析和改進數(shù)據(jù)庫的重組織與重構(gòu)造數(shù)據(jù)庫的維護在數(shù)據(jù)庫運行階段，對數(shù)據(jù)庫經(jīng)常性的維護工作主要是467.3數(shù)據(jù)結(jié)構(gòu)與算法

算法數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語線性表棧隊列樹與二叉樹查找與排序7.3數(shù)據(jù)結(jié)構(gòu)與算法算法477.3.1算法定義：是對特定問題求解步驟的一種描述?；蛘哒f，是為求解某問題而設(shè)計的步驟序列特征：

有窮性確定性有效性輸入輸出7.3.1算法定義：是對特定問題求解步驟的一種描述?；蛘?8算法復(fù)雜度評價一個算法優(yōu)劣的主要標準是：

算法的執(zhí)行效率與存儲需求算法的效率：指的是時間復(fù)雜度（TimeComplexity）存儲需求：指的是空間復(fù)雜度（SpaceComplexity）一般情況下，算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間復(fù)雜度記做T(n)=O(f(n))算法復(fù)雜度評價一個算法優(yōu)劣的主要標準是：497.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ù)元素的集合7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)50數(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)集合7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概念51數(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ù)語數(shù)據(jù)的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概52二、鏈式存儲結(jié)構(gòu)主要特點：結(jié)點中除自身信息之外，還有表示連接信息的指針域，因此比順序存儲密度小，存儲空間利用率低邏輯上相鄰的結(jié)點物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表示插入、刪除操作靈活方便，不必移動結(jié)點，只要改變結(jié)點中的指針值即可二、鏈式存儲結(jié)構(gòu)主要特點：53

數(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ù)語數(shù)據(jù)的運算檢索：在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點7.547.3.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列（a1,a2,…,an）順序表：指用順序存儲結(jié)構(gòu)存儲的線性表鏈表：用鏈式存儲結(jié)構(gòu)存儲的線性表棧和隊列——是對線性表的插入、刪除運算可以發(fā)生的位置加以限制的兩種特殊的線性表7.3.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線55順序表和一維數(shù)組各種高級語言里的一維數(shù)組就是用順序方式存儲的線性表，因此常用一維數(shù)組稱呼順序表

若順序表中結(jié)點個數(shù)為n，則：

插入一個結(jié)點平均需要移動之結(jié)點個數(shù)為n/2，算法的時間復(fù)雜度是O(n)；

刪除一個結(jié)點平均需移動結(jié)點個數(shù)為（n-1）/2，算法的時間復(fù)雜度是O(n)順序表和一維數(shù)組各種高級語言里的一維數(shù)組就是用順序方式56鏈表線性鏈表（單鏈表）：刪除算法的時間復(fù)雜度為O(n)，其主要執(zhí)行時間是搜索刪除位置循環(huán)鏈表：指鏈表的最后一個結(jié)點的指針值指向第一個結(jié)點，整個鏈表形成一個環(huán)（如下圖）…結(jié)點1結(jié)點2結(jié)點n鏈表線性鏈表（單鏈表）：刪除算法的時間復(fù)雜度577.3.4棧棧：是一種特殊的線性表，是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom）?？諚＃褐副碇袩o元素棧中有元素a1,a2,…,an，如下頁圖所示，稱a1為棧底元素。新元素進棧要置于an之上，刪除或退棧先對an進行，即“后進先出”（LIFO）的操作原則棧的物理存儲可以用

順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)棧的運算還有取棧頂元素，檢查棧是否為空，清除等。7.3.4棧棧：是一種特殊的線性表，是限定僅在表尾進行插58棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1進棧出棧棧底棧結(jié)構(gòu)(3)(1)(2)(5)(4)(6)棧的插入和刪除ABACBABAFEBAATOPTOPTOPT597.3.5隊列隊列：是限定所有的插入都在表的一端進行，所有的刪除都在表的另一端進行的線性表。進行刪除的一端叫隊列的頭，進行插入的一端叫隊列的尾，如下頁圖所示。在隊列中，新元素總是加入到隊尾，每次刪除的總是對頭元素，即當前“最老的”元素，這就是“先進先出”（FIFO）的操作原則隊列的物理存儲可以用：順序存儲結(jié)構(gòu)，也可用鏈式存儲結(jié)構(gòu)7.3.5隊列隊列：是限定所有的插入都在表的一端進行，所60隊列的示意（如下圖）出隊列a1a2a3…an入隊列頭尾隊列的示意（如下圖）出隊列a1a2a361隊列的插入和刪除示例初態(tài)插入A插入B刪除A插入C插入D刪除B插入EFRAFRRRRRRFFFFFFBABBBCCCCDDD溢出隊列的插入和刪除示例初態(tài)插入A插入B刪除A插入C插入D刪除B627.3.6樹與二叉樹樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，樹和二叉樹是最常見的樹形結(jié)構(gòu)樹（Tree）:是一個或多個結(jié)點組成的有限集合T，有一個特定的結(jié)點稱為根（Root），其余的結(jié)點分為m（m≥0）個不相交的集合T1，T2，…，Tm，每個集合又是一棵樹，稱作這個根的子樹（Subtree)7.3.6樹與二叉樹樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，樹和63樹形結(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）樹形結(jié)構(gòu)的常用術(shù)語結(jié)點的度（Degree）：一個結(jié)點的子樹的64二叉樹二叉樹（BinaryTree）:是n（n≥0)個結(jié)點的有限集合，這個集合或者為空集（n=0），或者由一個根結(jié)點及兩棵不相交的、分別稱作這個根的坐姿樹和右子樹的二叉樹組成二叉樹不是樹的特殊情形，二者的區(qū)別：

二叉樹為有序樹性質(zhì)：1、在二叉樹的i層上，最多有2i-1個結(jié)點（i≥1）2、深度為k的二叉樹最多有2k-1個結(jié)點(k≥1)二叉樹二叉樹（BinaryTree）:是n（65完全二叉樹一棵深度為k且具有2k-1個結(jié)點的二叉樹稱為滿二叉樹（FullBinaryTree）深度為k，有n個結(jié)點的二叉樹，當且僅當其妹一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹完全二叉樹一棵深度為k且具有2k-1個結(jié)點的二叉樹稱為滿二叉66樹的二叉樹表示在樹（森林）與二叉樹間有一個自然的一一對應(yīng)的關(guān)系，每一棵樹都能唯一的轉(zhuǎn)換到它所對應(yīng)的二叉樹把樹和森林轉(zhuǎn)化成對應(yīng)的二叉樹：凡是兄弟就用線連起來，然后去掉雙親到子女的連線，只留下道第一個子女的連線不去掉樹的二叉樹表示在樹（森林）與二叉樹間有一個自然的一一對應(yīng)的關(guān)67二叉樹的存儲

二叉樹的存儲通常采用:鏈接方式。每個結(jié)點除存儲結(jié)點自身的信息外再設(shè)置兩個指針域IIink和rlink，分別指向結(jié)點的左子女和右子女，當結(jié)點的某個指針為空時，則相應(yīng)的指針值為空（NIL）。結(jié)點的形式為：IIinkinforlink二叉樹的存儲二叉樹的存儲通常采用:鏈接方式。每個結(jié)點除存68二叉樹的遍歷遍歷一個樹形結(jié)構(gòu)是指：按一定次序系統(tǒng)的訪問該結(jié)構(gòu)中的所有結(jié)點，使每個結(jié)點恰好被訪問一次前序遍歷法（NLR次序）訪問根，按前序遍歷左子樹，按前序遍歷右子樹后序遍歷法（LRN次序）按后序遍歷左子樹，按后序遍歷右子樹，訪問根中序遍歷法（LNR次序）按中序遍歷左子樹，訪問根，按中序遍歷右子樹二叉樹的遍歷遍歷一個樹形結(jié)構(gòu)是指：按一定次序系統(tǒng)的訪問該結(jié)構(gòu)697.3.7查找

查找：是數(shù)據(jù)結(jié)構(gòu)中的基本運算

衡量一個查找運算法的主要標志是：查找過程中對關(guān)節(jié)碼進行的平均比較次數(shù)，或稱平均檢索長度，以n的函數(shù)的形式表示，n是數(shù)據(jù)結(jié)構(gòu)中的結(jié)點個數(shù)7.3.7查找查找：是數(shù)據(jù)結(jié)構(gòu)中的基本運算70順序查找順序查找：是線性表的最簡單的查找方法方法：用待查關(guān)鍵碼與線性表中各結(jié)點的關(guān)鍵碼值逐個比較，若找出相等的關(guān)鍵碼值則查找成功，若找遍所有結(jié)點都不相等，則查找失敗優(yōu)點：對線性表的結(jié)點邏輯次序和存儲結(jié)構(gòu)無要求缺點：平均檢索長度大假設(shè)表中各結(jié)點被查找的概率相同，即P=1/n,則順序查找成功的平均查找長度為(n+1)/2順序查找順序查找：是線性表的最簡單的查找方法71二分法查找二分法查找：是一種效率較高的線性表查找方法。要進行二分法查找，線性表結(jié)點必須是按關(guān)鍵碼值排號順序的，且線性表以順序方式存儲方法：首先用要查找的關(guān)鍵碼值與線性表中間位置結(jié)點的關(guān)鍵碼值相比較，這個中間結(jié)點把線性表分成兩個子表，比較相等則查找完成，不等則根據(jù)比較結(jié)果確定下一步的查找應(yīng)在哪個子表中進行，如此下去，直到找到滿足條件的結(jié)點優(yōu)點：平均檢索長度小，為㏒2n。每經(jīng)過一次關(guān)鍵碼比較，則將查找范圍縮小一半，因此經(jīng)過㏒2n次比較就可完成查找過程缺點：排序線性表花費時間，順序方式存儲插入、刪除不便二分法查找二分法查找：是一種效率較高的線性表查找方法。要進行727.3.8排序排序：是數(shù)據(jù)處理中經(jīng)常使用的一種運算分類：直接插入排序選擇排序冒泡排序快速排序7.3.8排序排序：是數(shù)據(jù)處理中經(jīng)常使用的一種運算73直接插入排序的基本方法：每步將一個待排序記錄按其關(guān)鍵碼值的大小插入到前面已排序的文件中適當位置上，直到全部插入為止選擇排序的基本思想：每一趟在n-i+1(i=1,2,…,n-1）個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個記錄。它為最簡單且為我們最熟悉的排序冒泡排序的基本方法：將待排序的記錄順次兩兩比較，若為逆序，則進行交換快速排序：又稱分區(qū)交換排序，是對冒泡排序的一種改進。直接插入排序的基本方法：每步將一個待排序記錄按其關(guān)鍵碼值的大74快速排序的基本方法：在待排序序列中任取一個記錄，以它為基準用交換的發(fā)方法將所有記錄分成兩部分，關(guān)鍵碼比它小的在一個部分，關(guān)鍵碼值比它大的在另一個部分。再分別對兩個部分實施上述過程，一直重復(fù)到排序完成下圖為四種排序方法的比較：排序方法平均時間最壞情況輔助存儲直接插入排序選擇排序冒泡排序快速排序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)快速排序的基本方法：在待排序序列中任取一個記錄，以它為基準用757.4程序設(shè)計基礎(chǔ)

程序設(shè)計語言發(fā)展程序設(shè)計方法與風(fēng)格結(jié)構(gòu)化程序設(shè)計

面向?qū)ο蟪绦蛟O(shè)計7.4程序設(shè)計基礎(chǔ)程序設(shè)計語言發(fā)展76程序設(shè)計指令：能被計算機直接識別與執(zhí)行的指示計算機進行某種操作的命令，CPU每執(zhí)行一條指令，就完成一個基本運算。程序：指令的序列即讓計算機解決某一問題而寫出的一系列指令程序設(shè)計：編寫程序的過程程序設(shè)計語言：用于描述計算機所執(zhí)行的操作語言程序設(shè)計指令：能被計算機直接識別與執(zhí)行的指示計算機進行某種操777.4.1程序設(shè)計語言發(fā)展機器語言：采用計算機指令格式并以二進制編碼表達各種操作的語言匯編語言：一種符號語言，采用助記符來表達指令功能高級語言：是一種面向問題的語言第四代語言：是非過程化語言7.4.1程序設(shè)計語言發(fā)展機器語言：采用計算機指令格式787.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.2程序設(shè)計方法與風(fēng)格良好程序設(shè)計風(fēng)格的側(cè)797.4.3結(jié)構(gòu)化程序設(shè)計

結(jié)構(gòu)化程序設(shè)計的原則

自頂向下逐步求精模塊化限制使用GOTO語句7.4.3結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計的原則80

結(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è)計的基本結(jié)構(gòu)與特點7.4.3結(jié)構(gòu)化程81結(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)清晰，有利于程序正確性證明結(jié)構(gòu)化程序設(shè)計的優(yōu)點自頂向下逐步求精的方法符合人類解決復(fù)雜問827.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ù)的對象歸為一類，類是這些對象的抽象描述，每個對象是它的類的一個實例7.4.4面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蠓椒ǖ闹?3

面向?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ū)ο蠓椒ǖ闹饕攸c：7.4.4面向?qū)ο蟮?4面向?qū)ο蠓椒ǖ母拍?/p>

面向?qū)ο螅?/p>

面向?qū)ο?對象+類+繼承+通信如果一個軟件系統(tǒng)是使用這樣四個概念設(shè)計和實現(xiàn)的，則認為這個軟件系統(tǒng)是面向?qū)ο蟮?。面向?qū)ο蟮某绦虻拿恳唤M成部分都是對象，計算是通過建立新的對象和對象之間的通信來執(zhí)行的面向?qū)ο蠓椒ǖ母拍蠲嫦驅(qū)ο螅?5對象對象是構(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)特征的一個操作序列對象對象是構(gòu)成世界的一個獨立單位，它具有自己的靜86消息和方法一個系統(tǒng)由若干個對象組成，各個對象之間相互聯(lián)系、相互作用。計算機系統(tǒng)中，消息就是對象之間的紐帶，是用來通知、命令或請求對象執(zhí)行某個處理或回答某些信息。消息可以是數(shù)據(jù)流，也可以是控制流。一條消息可以發(fā)送給不同的對象，而消息的解釋則完全由接收對象完成。不同的對象對相同形式的消息可以有不同的解釋消息和方法一個系統(tǒng)由若干個對象組成，各個對象之間相互聯(lián)系、相87類和實例類和對象之間的關(guān)系如同一個模具與用這個模具鑄造出來的鑄件之間的關(guān)系。類給出了屬于該類的全部對象的抽象定義，而對象則是符合這種定義的一個實體。一個對象又稱為類的一個實例（Instance）類也可稱作對象的模板（Template）類和實例類和對象之間的關(guān)系如同一個模具與用這個模具鑄造出來88繼承性定義：特殊類的對象擁有其一般類的全部屬性與方法，稱作特殊類對一般類的繼承繼承關(guān)系是傳遞的繼承性對于軟件重用有很大益處繼承性定義：特殊類的對象擁有其一般類的全部屬性與方法89封裝性封裝具有兩個涵義：一、是把對象的全部屬性和全部方法結(jié)合在一起，形成一個不可分割的獨立單位（即對象）二、也稱作“信息隱蔽”，即盡可能隱蔽對象的內(nèi)部細節(jié)，對外形成一個邊界，只保留有限的對外接口使之與外部發(fā)生聯(lián)系封裝性封裝具有兩個涵義：90多態(tài)性對象的多態(tài)性：

指在一般類中定義的屬性或方法被特殊類繼承之后，可以具有不同的數(shù)據(jù)類型表現(xiàn)出不同的行為。這使得同一個屬性或方法名在一般類及其各個特殊類中具有不同的語義多態(tài)性對象的多態(tài)性：917.5多媒體技術(shù)簡介多媒體技術(shù)的基本概念多媒體計算機系統(tǒng)多媒體計算機軟件系統(tǒng)多媒體信息的數(shù)字化和壓縮技術(shù)7.5多媒體技術(shù)簡介多媒體技術(shù)的基本概念927.5.1多媒體技術(shù)的基本概念定義：指信息表示媒體的多樣化。多媒體的類型感覺媒體表示媒體顯示媒體傳輸媒體存儲媒體多媒體技術(shù)就是利用計算機把文本、聲音、視頻、動畫、圖形和圖像等多種媒體進行綜合處理，使多種信息建立邏輯連接，集成為一個具有交互性的系統(tǒng)7.5.1多媒體技術(shù)的基本概念定義：指信息表示媒體的多樣93多媒體技術(shù)的特征

信息載體的多樣性交互性集成性實時性多媒體技術(shù)的特征信息載體的多樣性94多媒體信息中的媒體元素的類型文本（Text）圖形（Graphic）圖像（Image）音頻動畫視頻多媒體信息中的媒體元素的類型文本（Text）95多媒體信息處理的關(guān)鍵技術(shù)視頻和音頻數(shù)據(jù)壓縮和解壓縮技術(shù)關(guān)于壓縮編碼的國際標準有：

JPEG標準電視電話/會議電視P*64Kbit/s(CCITTH.261)標準MPEG-1標準多媒體硬件系統(tǒng)的專用芯片大容量的外部存儲器多媒體同步技術(shù)多媒體信息處理的關(guān)鍵技術(shù)視頻和音頻數(shù)據(jù)壓縮和解壓縮技術(shù)96多媒體技術(shù)的應(yīng)用領(lǐng)域

教育與培訓(xùn)桌面出版多媒體電子出版物多媒體通信多媒體聲光藝術(shù)品的創(chuàng)作多媒體技術(shù)的應(yīng)用領(lǐng)域教育與培訓(xùn)977.5.2多媒體計算機系統(tǒng)多媒體計算機系統(tǒng)的組成（如下圖）多媒體計算機系統(tǒng)軟件系統(tǒng)硬件系統(tǒng)多媒體應(yīng)用軟件媒體處理系統(tǒng)工具軟件多媒體數(shù)據(jù)處理軟件多媒體操作系統(tǒng)多媒體驅(qū)動軟件多媒體輸入/輸出控制卡及接口多媒體計算機硬件多媒體外圍設(shè)備7.5.2多媒體計算機系統(tǒng)多媒體計算機系統(tǒng)的組成（如下圖98多媒體計算機硬件系統(tǒng)主機：常規(guī)的主板、CPU及VGA適配卡、多功能卡等多媒體適配卡：音頻卡、視頻卡、圖形卡和壓縮卡等外部存儲設(shè)備：軟盤驅(qū)動器、硬盤驅(qū)動器和CD-ROM驅(qū)動器輸入設(shè)備輸出設(shè)備多媒體計算機硬件系統(tǒng)主機：常規(guī)的主板、CPU及VGA適配卡、997.5.3多媒體計算機軟件系統(tǒng)多媒體應(yīng)用程序多媒體處理系統(tǒng)工具多媒體操作系統(tǒng)（媒體控制接口）音頻/視頻核心處理音頻/視頻設(shè)備驅(qū)動程序音頻/視頻設(shè)備多媒體計算機軟件的層次結(jié)構(gòu)（如右圖）第五層第四層第三層第二層第一層7.5.3多媒體計算機軟件系統(tǒng)多媒體應(yīng)用程序多媒體處理系統(tǒng)工1007.5.4多媒體信息的數(shù)字化和壓縮技術(shù)

音頻信息聲音的特征模擬音頻和數(shù)字音頻衡量一個數(shù)字聲音波形的質(zhì)量有：采樣頻率、采樣精度、聲道數(shù)三個要素數(shù)字音頻文件的存儲格式數(shù)字音頻文件的存儲量存儲量=采樣頻率×量化位數(shù)/8×聲道數(shù)×?xí)r間7.5.4多媒體信息的數(shù)字化和壓縮技術(shù)音頻信息101圖像信息圖像信息的性能指標

分辨率圖像深度和顯示深度圖像文件的大小圖像信息圖像信息的性能指標102圖像文件的存儲格式BMP格式PCX格式GIF格式TIF格式JPG和PIC格式PCD格式CDR格式PSD格式IFF格式DIF格式圖像文件的存儲格式BMP格式PCX格式103視頻信息視頻的彩色空間表示

RGB彩色空間YUV和YIQ彩色空間模擬視頻標準（NTSC制式PAL制式SECAM制式）數(shù)字視頻視頻序列的時間碼數(shù)字視頻標準與文件格式視頻信息視頻的彩色空間表示104數(shù)字視頻標準與文件格式MPEG標準MPEG-1（1992年正式發(fā)布）MPEG-2（1994年制定）MPEG-4（1999年正式發(fā)布）AVI格式PM格式QuickTime格式數(shù)字視頻標準與文件格式MPEG標準105數(shù)據(jù)壓縮技術(shù)無損壓縮

行程編碼（RLE）Huffman編碼算術(shù)編碼LZW編碼有損壓縮三種數(shù)據(jù)壓縮國際標準：JPEG-靜止圖像壓縮標準、MPEG-運動圖像壓縮編碼標準、H.261-視頻通信編碼標準數(shù)據(jù)壓縮技術(shù)無損壓縮106第七章軟件開發(fā)與信息處理技術(shù)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)多媒體技術(shù)簡介第七章軟件開發(fā)與信息處理技術(shù)軟件工程基礎(chǔ)1077.1軟件工程基礎(chǔ)

軟件的規(guī)模大小決定了軟件開發(fā)的難度，因此，必須采用科學(xué)的軟件開發(fā)方法，采用抽象、分解等科學(xué)方法降低復(fù)雜度，以工程的方法管理和控制軟件開發(fā)的各個階段，以保證大型軟件系統(tǒng)的開發(fā)具有正確性、易維護性、可讀性和可重用性7.1軟件工程基礎(chǔ)軟件的規(guī)模大小決定了軟1087.1.1軟件工程基本概念

軟件的發(fā)展大致分為四個階段：（如下圖）階段第一階段第二階段第三階段第四階段程序設(shè)計階段程序系統(tǒng)階段軟件工程階段（結(jié)構(gòu)化方法發(fā)）軟件工程階段（面向?qū)ο蠓椒ǎ┑湫图夹g(shù)面向批處理有限的分布自定義軟件多用戶實時數(shù)據(jù)庫軟件產(chǎn)品分布式系統(tǒng)嵌入“智能”低成本硬件消費者的影響強大的桌面系統(tǒng)面向?qū)ο蠹夹g(shù)專家系統(tǒng)人工神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)計算機7.1.1軟件工程基本概念軟件的發(fā)展大致分109軟件危機和軟件工程軟件危機主要表現(xiàn)在：對軟件開發(fā)成本和進度的估計常常很不準確，經(jīng)費預(yù)算經(jīng)常突破，完成時間一再拖延；開發(fā)的軟件不能滿足用戶要求，用戶軟件不滿意的現(xiàn)象經(jīng)常發(fā)生；開發(fā)的軟件可維護性差、可靠性差軟件工程：運用系統(tǒng)的、規(guī)范的和可定量的方法開發(fā)、運行和維護軟件。它包含三個要素：方法（Methodologies）工具（Tools）過程（Procedures）軟件危機和軟件工程軟件危機主要表現(xiàn)在：對軟件開發(fā)成本和進度的110軟件工程過程和軟件生命周期

軟件工程過程

軟件生命周期

軟件生命周期模型

軟件工程的目標和原則軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件工程過程和軟件生命周期軟件工程過程111

下圖為軟件生命周期各階段的任務(wù)：時期階段任務(wù)文檔軟件計劃問題定義理解用戶要求，劃清工作范圍計劃說明書可行性研究可行性方案及代價需求分析軟件系統(tǒng)的目標及應(yīng)完成的工作需求規(guī)格說明書軟件開發(fā)概要設(shè)計系統(tǒng)的邏輯設(shè)計軟件概要設(shè)計說明書詳細設(shè)計系統(tǒng)模塊設(shè)計軟件詳細設(shè)計說明書軟件編碼編寫程序代碼程序、數(shù)據(jù)、詳細注釋軟件測試單元測試、綜合測試測試后的軟件、測試大綱、測試方案與結(jié)果軟件維護軟件維護運行和維護維護后的軟件下圖為軟件生命周期各階段的任務(wù)：時期階段任務(wù)文檔問題112圖為軟件生命周期的瀑布模型和快速原形法模型軟件計劃需求分析軟件設(shè)計軟件編碼軟件測試軟件維護需求分析快速設(shè)計建立模型用戶評價模型修改原型生產(chǎn)產(chǎn)品圖為軟件生命周期的瀑布模型和快速原形法模型軟件計劃需求分析軟113軟件工程目標和原則目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性并滿足用戶需求的產(chǎn)品

軟件工程理論和技術(shù)性研究的內(nèi)容：軟件開發(fā)技術(shù)和軟件管理技術(shù)原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性軟件工程目標和原則目標：在給定成本、進度的前提下，開發(fā)出具有114軟件開發(fā)工具與開發(fā)環(huán)境軟件開發(fā)工具：是為支持軟件人員開發(fā)和維護活動而使用的軟件。作用：可以幫助開發(fā)人員完成一些繁瑣的程序編制和調(diào)試問題，是軟件開發(fā)人員將更多的精力和時間投放到最重要的軟件需求和設(shè)計上，提高軟件開發(fā)的速度和質(zhì)量。軟件開發(fā)工具與開發(fā)環(huán)境軟件開發(fā)工具：是為支持軟件人員開發(fā)和維1157.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）7.1.2結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法（Sructured116軟件開發(fā)過程

問題定義可行性研究需求分析與需求分析方法結(jié)構(gòu)化分析方法概述軟件需求規(guī)格說明書軟件開發(fā)過程問題定義117結(jié)構(gòu)化分析方法使用的工具

數(shù)據(jù)流圖（DataFlowDiagram）從數(shù)據(jù)傳遞和加工的角度，以圖形方式刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程

數(shù)據(jù)字典（DataDictionary）需對數(shù)據(jù)流圖中的各個元素作完整的定義和說明，是數(shù)據(jù)流圖的補充工具

加工邏輯描述工具（常用：結(jié)構(gòu)化自然語言、判定樹和判定表）結(jié)構(gòu)化分析方法使用的工具數(shù)據(jù)流圖（DataFlowD1187.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è)計）7.1.3結(jié)構(gòu)化設(shè)計方法軟件設(shè)計的基本概念：是一個把軟件119概要設(shè)計概要設(shè)計又稱為總體設(shè)計，它的任務(wù)是確定軟件結(jié)構(gòu)結(jié)構(gòu)化設(shè)計方法的基本思想：采用自頂向下的模塊化設(shè)計方法，按照模塊化原則和軟件設(shè)計策略，將需求分析得到的數(shù)據(jù)流圖，映射成由相對獨立、單一功能的模塊組成的軟件結(jié)構(gòu)概要設(shè)計概要設(shè)計又稱為總體設(shè)計，它的任務(wù)是確定軟件結(jié)構(gòu)120概要設(shè)計概要設(shè)計的圖形工具（層次圖、HIPO圖、軟件結(jié)構(gòu)圖）軟件設(shè)計原理軟件結(jié)構(gòu)設(shè)計原則面向數(shù)據(jù)流的設(shè)計方法（變換流分析設(shè)計和事務(wù)流分析設(shè)計）設(shè)計規(guī)格說明概要設(shè)計概要設(shè)計的圖形工具（層次圖、HIPO圖、軟件結(jié)構(gòu)圖）121軟件結(jié)構(gòu)設(shè)計原則提高模塊獨立性模塊規(guī)模應(yīng)該適中模塊的深度、寬度、扇出和扇入適當模塊的作用域應(yīng)該在控制域之內(nèi)降低模塊接口的復(fù)雜程度設(shè)計單入口和單出口模塊軟件結(jié)構(gòu)設(shè)計原則提高模塊獨立性122詳細設(shè)計任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，并用某種工具描述出來結(jié)構(gòu)化程序設(shè)計詳細設(shè)計工具（程序流程圖、盒圖[N-S圖]、PAD圖）詳細設(shè)計規(guī)格說明詳細設(shè)計任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)1237.1.4軟件測試一、軟件測試的目的與任務(wù)目的：確保軟件的質(zhì)量，盡量找出軟件錯誤并加以糾正，而不是證明軟件沒有錯。任務(wù)：測試任務(wù)（通過采用一定的測試策略，找出軟件中的錯誤）調(diào)試任務(wù)或糾錯任務(wù)（如果測試到錯誤，則定位軟件中的錯誤，加以糾正）7.1.4軟件測試一、軟件測試的目的與任務(wù)124二、軟件測試的準則三、軟件測試技術(shù)與方法綜述

方法：靜態(tài)測試法動態(tài)測試法

技術(shù)：白盒測試用例設(shè)計黑盒測試用例設(shè)計7.1.4軟件測試二、軟件測試的準則7.1.4軟件測試125白盒測試用例設(shè)計、邏輯覆蓋以程序的內(nèi)部邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù)，它要求測試人員十分清楚程序的邏輯結(jié)構(gòu)，考慮的是測試用例對程序內(nèi)部邏輯覆蓋的程度根據(jù)覆蓋的目標，可分為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、路徑覆蓋、基本路徑測試白盒測試用例設(shè)計、邏輯覆蓋126

黑盒測試用例設(shè)計分類：

等價類劃分法邊界值分析法錯誤推測法因果圖黑盒測試用例設(shè)計分類：127四、軟件測試的實施

單元測試集成測試確認測試系統(tǒng)測試五、軟件測試計劃與測試分析報告測試是軟件生存周期中的一個獨立的關(guān)鍵的階段7.1.4軟件測試四、軟件測試的實施7.1.4軟件測試128未加入p243未加入p2431297.1.5程序的調(diào)試程序調(diào)試可以分為：靜態(tài)調(diào)試（主要通過人的思維來分析源程序代碼和排錯，是主要的調(diào)試手段）動態(tài)調(diào)試（是靜態(tài)調(diào)試的輔助）主要的調(diào)試方法有：強行排錯法回溯法原因排除法7.1.5程序的調(diào)試程序調(diào)試可以分為：1307.2數(shù)據(jù)庫設(shè)計基礎(chǔ)

數(shù)據(jù)庫概念數(shù)據(jù)模型關(guān)系代數(shù)數(shù)據(jù)庫設(shè)計與管理7.2數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫概念1317.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）7.2.1數(shù)據(jù)庫概念數(shù)據(jù)（Data）132數(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)的發(fā)展人工管理階段133數(shù)據(jù)庫系統(tǒng)的基本功能

數(shù)據(jù)定義功能數(shù)據(jù)操縱功能數(shù)據(jù)庫運行控制功能數(shù)據(jù)庫的建立和維護功能數(shù)據(jù)庫系統(tǒng)的基本功能數(shù)據(jù)定義功能134數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的結(jié)構(gòu)化數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)的統(tǒng)一管理與控制數(shù)據(jù)庫系統(tǒng)的基本特點數(shù)據(jù)的結(jié)構(gòu)化135數(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)模式（也稱存儲模式）并提供二級映像功能數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系模式：是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和1367.2.2數(shù)據(jù)模型數(shù)據(jù)模型（datamodel）：是表示實體類型及實體之間聯(lián)系的模型數(shù)據(jù)模式的三個要素：

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的完整性約束條件7.2.2數(shù)據(jù)模型數(shù)據(jù)模型（datamodel）：是137

數(shù)據(jù)模型的三個級別：

概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型7.2.2數(shù)據(jù)模型數(shù)據(jù)模型的三個級別：7.2.2數(shù)據(jù)模型138數(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)是一張二維表）數(shù)據(jù)模型的分類E-R模型（實體聯(lián)系模型）1397.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ǔ)7.2.3關(guān)系代數(shù)關(guān)系代數(shù)：是一種抽象的查詢語言，是關(guān)140傳統(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)列的元組的集合傳統(tǒng)的集合運算并（Union)關(guān)系R和關(guān)系S的并記做R∪S，141關(guān)系R和S及其三種傳統(tǒng)的集合運算（如下圖）ABCa1a2a3b1b2b3c1c2c3ABCa1a2a3b1b2b3c1c2c3ABCA1A1A2a1B1B2B2b3C1C2C1c2ABCb1c1ABCA1a2B2b2C2c1關(guān)系R關(guān)系SR∩SR∪SR-S關(guān)系R和S及其三種傳統(tǒng)的集合運算（如下圖）ABCa1b1c1142專門的關(guān)系運算選擇運算：是一個單目運算，是從關(guān)系R中選取滿足一定條件的元組子集。記做：其中σ

是選擇運算符；F是限定條件的布爾表達式，由邏輯運算符∧、∨等連接關(guān)系表達式組成。關(guān)系表達式的基本形式為：XθY，其中θ={>、≥、<、≤、=、≠}，X、Y可以是屬性名、常量或簡單函數(shù)專門的關(guān)系運算選擇運算：是一個單目運算，是從關(guān)系R中選取滿足143投影（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)系運算投影（Projection）運算：也是一個單目運算，是從關(guān)系144除（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)系運算除（Division）：專門的關(guān)系運算1457.2.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的設(shè)計步驟：用戶需求分析概念設(shè)計邏輯設(shè)計物理設(shè)計數(shù)據(jù)庫實施數(shù)據(jù)庫的維護7.2.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的設(shè)計步146數(shù)據(jù)庫設(shè)計的需求分析

用戶的信息要求用戶的處理要求對數(shù)據(jù)的安全性、完整性的要求數(shù)據(jù)庫設(shè)計的需求分析用戶的信息要求147數(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è)計：只講需求分析得到的用戶需求抽象148數(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è)計邏輯結(jié)構(gòu)設(shè)計的步驟：149數(shù)據(jù)庫的物理設(shè)計

確定數(shù)據(jù)的存儲安排存取路徑的選擇和調(diào)整確定系統(tǒng)配置數(shù)據(jù)庫的物理設(shè)計確定數(shù)據(jù)的存儲安排150數(shù)據(jù)庫管理數(shù)據(jù)庫的管理主要指：

數(shù)據(jù)庫的實施和維護分三個步驟：數(shù)據(jù)的載入和應(yīng)用程序的調(diào)試數(shù)據(jù)庫的試運行數(shù)據(jù)庫的運行和維護數(shù)據(jù)庫管理數(shù)據(jù)庫的管理主要指：151數(shù)據(jù)庫的維護在數(shù)據(jù)庫運行階段，對數(shù)據(jù)庫經(jīng)常性的維護工作主要是由DBA完成的。包括：

數(shù)據(jù)庫的存儲和恢復(fù)數(shù)據(jù)庫的安全性、完整性控制數(shù)據(jù)庫性能的監(jiān)督、分析和改進數(shù)據(jù)庫的重組織與重構(gòu)造數(shù)據(jù)庫的維護在數(shù)據(jù)庫運行階段，對數(shù)據(jù)庫經(jīng)常性的維護工作主要是1527.3數(shù)據(jù)結(jié)構(gòu)與算法

算法數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語線性表棧隊列樹與二叉樹查找與排序7.3數(shù)據(jù)結(jié)構(gòu)與算法算法1537.3.1算法定義：是對特定問題求解步驟的一種描述。或者說，是為求解某問題而設(shè)計的步驟序列特征：

有窮性確定性有效性輸入輸出7.3.1算法定義：是對特定問題求解步驟的一種描述?；蛘?54算法復(fù)雜度評價一個算法優(yōu)劣的主要標準是：

算法的執(zhí)行效率與存儲需求算法的效率：指的是時間復(fù)雜度（TimeComplexity）存儲需求：指的是空間復(fù)雜度（SpaceComplexity）一般情況下，算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間復(fù)雜度記做T(n)=O(f(n))算法復(fù)雜度評價一個算法優(yōu)劣的主要標準是：1557.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ù)元素的集合7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)156數(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)集合7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概念157數(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ù)語數(shù)據(jù)的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)7.3.2數(shù)據(jù)結(jié)構(gòu)的基本概158二、鏈式存儲結(jié)構(gòu)主要特點：結(jié)點中除自身信息之外，還有表示連接信息的指針域，因此比順序存儲密度小，存儲空間利用率低邏輯上相鄰的結(jié)點物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表示插入、刪除操作靈活方便，不必移動結(jié)點，只要改變結(jié)點中的指針值即可二、鏈式存儲結(jié)構(gòu)主要特點：159

數(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ù)語數(shù)據(jù)的運算檢索：在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點7.1607.3.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列（a1,a2,…,an）順序表：指用順序存儲結(jié)構(gòu)存儲的線性表鏈表：用鏈式存儲結(jié)構(gòu)存儲的線性表棧和隊列——是對線性表的插入、刪除運算可以發(fā)生的位置加以限制的兩種特殊的線性表7.3.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線161順序表和一維數(shù)組各種高級語言里的一維數(shù)組就是用順序方式存儲的線性表，因此常用一維數(shù)組稱呼順序表

若順序表中結(jié)點個數(shù)為n，則：

插入一個結(jié)點平均需要移動之結(jié)點個數(shù)為n/2，算法的時間復(fù)雜度是O(n)；

刪除一個結(jié)點平均需移動結(jié)點個數(shù)為（n-1）/2，算法的時間復(fù)雜度是O(n)順序表和一維數(shù)組各種高級語言里的一維數(shù)組就是用順序方式162鏈表線性鏈表（單鏈表）：刪除算法的時間復(fù)雜度為O(n)，其主要執(zhí)行時間是搜索刪除位置循環(huán)鏈表：指鏈表的最后一個結(jié)點的指針值指向第一個結(jié)點，整個鏈表形成一個環(huán)（如下圖）…結(jié)點1結(jié)點2結(jié)點n鏈表線性鏈表（單鏈表）：刪除算法的時間復(fù)雜度1637.3.4棧棧：是一種特殊的線性表，是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom）。空棧：指表中無元素棧中有元素a1,a2,…,an，如下頁圖所示，稱a1為棧底元素。新元素進棧要置于an之上，刪除或退棧先對an進行，即“后進先出”（LIFO）的操作原則棧的物理存儲可以用

順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)棧的運算還有取棧頂元素，檢查棧是否為空，清除等。7.3.4棧棧：是一種特殊的線性表，是限定僅在表尾進行插164棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1進棧出棧棧底棧結(jié)構(gòu)(3)(1)(2)(5)(4)(6)棧的插入和刪除ABACBABAFEBAATOPTOPTOPT1657.3.5隊列隊列：是限定所有的插入都在表的一端進行，所有的刪除都在表的另一端進行的線性表。進行刪除的一端叫隊列的頭，進行插入的一端叫隊列的尾，如下頁圖所示。在隊列中，新元素總是加入到隊尾，每次刪除的總是對頭元素，即當前“最老的”元素，這就是“先進先出”（FIFO）的操作原則隊列的物理存儲可以用：順序存儲結(jié)構(gòu)，也可用鏈式存儲結(jié)構(gòu)7.3.5隊列隊列：是限定所有的插入都在表的一端進行，所166隊列的示意（如下圖）出隊列a1a2a3…an入隊列頭尾隊列的示意（如下圖）出隊列a1a2a3167隊列的插入和刪除示例初態(tài)插入A插入B刪除A插入C插入D刪除B插入EFRAFRRRRRRFFFFFFB