【正文】 。 （ 2） 回溯法 。 靜態(tài)調(diào)試主要是指通過人的思維來(lái)分析源程序代碼和排錯(cuò) ， 是主要的設(shè)計(jì)手段 ， 而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試 。 程序調(diào)試的基本步驟： （ 1） 錯(cuò)誤定位； （ 2） 修改設(shè)計(jì)和代碼 ， 以排除錯(cuò)誤； （ 3） 進(jìn)行回歸測(cè)試 ， 防止引進(jìn)新的錯(cuò)誤 。 4. 系統(tǒng)測(cè)試：目的是在真實(shí)的系統(tǒng)工作環(huán)境下檢驗(yàn)軟件是否能與系統(tǒng)正確連接 ， 發(fā)現(xiàn)軟件與系統(tǒng)需求不一致的地方 。 2. 集成測(cè)試：是測(cè)試和組裝軟件的過程 ， 目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤 。 3 軟件工程基礎(chǔ) 軟件測(cè)試實(shí)施 軟件測(cè)試過程一般按 4個(gè)步驟進(jìn)行： 1. 單元測(cè)試：對(duì)軟件設(shè)計(jì)中最小單位 —— 模塊進(jìn)行測(cè)試 ，目的發(fā)現(xiàn)模塊中錯(cuò)誤 。 1. 白盒測(cè)試：在程序內(nèi)部進(jìn)行 ， 主要用于完成軟件內(nèi)部操作的驗(yàn)證 。 軟件測(cè)試方法： ? 靜態(tài)測(cè)試：包括代碼檢查 、 靜態(tài)結(jié)構(gòu)分析 、 代碼質(zhì)量度量 。 3 軟件工程基礎(chǔ) 軟件測(cè)試 軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程 ， 其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別 。 ?表格工具：判定表 。 3 軟件工程基礎(chǔ) 詳細(xì)設(shè)計(jì) 是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu) ， 用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié) 。 2．軟件概要設(shè)計(jì) 軟件概要設(shè)計(jì)的基本任務(wù)是： （ 1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)； （ 2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)； （ 3）編寫概要設(shè)計(jì)文檔； （ 4）概要設(shè)計(jì)文檔評(píng)審。 ? 按內(nèi)聚性由弱到強(qiáng)：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚。 ? 在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。 ? 耦合性指模塊之間的相互依賴關(guān)系。 ? 內(nèi)聚性指一個(gè)模塊內(nèi)容各部分之間的緊密程度。 （ 4） 模塊獨(dú)立性 。 （ 2） 模塊化 。 ? 過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述 。 ? 數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義 。 3 軟件工程基礎(chǔ) 結(jié)構(gòu)化設(shè)計(jì)方法 軟件設(shè)計(jì)基本概念 ? 軟件設(shè)計(jì)的基本目標(biāo)：是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù) ， 軟件設(shè)計(jì)是確定系統(tǒng)的物理模型 。 （ 6） 附錄 。 （ 4） 性能描述 。 （ 3） 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù) 。需求分析 （ 得出新系統(tǒng)應(yīng)如何工作 ） 3. 新系統(tǒng)邏輯模型 結(jié)構(gòu)化分析的常用工具： （ 1） 數(shù)據(jù)流圖 、 （ 2） 數(shù)據(jù)字典 （ DD） 、 （ 3） 判定樹 、（ 4） 判定表 3 軟件工程基礎(chǔ) 軟件需求規(guī)格說(shuō)明書 作用： （ 1） 便于用戶與開發(fā)人員進(jìn)行交流 。 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流 ， 自頂向下 ， 逐層分解 ， 建立系統(tǒng)的處理流程 ， 以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具 ， 建立系統(tǒng)的邏輯模型 。 （ 1） 結(jié)構(gòu)化需求分析方法 。 ? 軟件工程原則包括抽象 、 信息隱蔽 、 模塊化 、 局部化 、 確定性 、 一致性 、 完備性和可驗(yàn)證性 。 ? 軟件工程管理包括：軟件管理學(xué) 、 軟件工程經(jīng)濟(jì)學(xué) 、 軟件心理學(xué)等內(nèi)容 。 ? 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理 。 3 軟件工程基礎(chǔ) 軟件工程的目標(biāo)和與原則 ? 目標(biāo)：在給定成本 、 進(jìn)度的前提下 ， 開發(fā)出具有有效性 、 可靠性 、 可理解性 、 可維護(hù)性 、 可重用性 、 可適應(yīng)性 、 可移植性 、 可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品 。圖 21中，機(jī)動(dòng)車類是對(duì)機(jī)動(dòng)車特征和功能的總體描述，機(jī)動(dòng)車 A是具體到某輛車的特征。 （ 5） 多態(tài)性 —— 多態(tài)性是指同樣的操作在接受不同消息時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象 。 繼承分單繼承和多重繼承 。 消息的組成包括 接收消息的對(duì)象的名稱； 消息標(biāo)識(shí)符 ， 也稱消息名； 零個(gè)或多個(gè)參數(shù) 。 所以類是對(duì)象的抽象 ， 對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例 。 屬性即對(duì)象所包含的信息 ， 操作描述了對(duì)象執(zhí)行的功能 ，操作也稱為方法或服務(wù) 。 （ 5） 可維護(hù)性好 。 （ 3） 可重用性好 。 2 程序設(shè)計(jì)基礎(chǔ) 面向?qū)ο蟪绦蛟O(shè)計(jì) 面向?qū)ο蠓椒ǖ?優(yōu)點(diǎn) ： （ 1） 與人類習(xí)慣的思維方法一致 。 2 程序設(shè)計(jì)基礎(chǔ) 結(jié)構(gòu)化程序設(shè)計(jì) 結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是 （ 必考 ） ： ； 2. 逐步求精； ； goto語(yǔ)句 。 （ 4） 輸入和輸出 。 （ 2） 數(shù)據(jù)說(shuō)明的方法 。 歸并排序時(shí) ， 需要利用與待排序數(shù)組相同的輔助數(shù)組作臨時(shí)單元 ， 故該排序方法的空間復(fù)雜度為 O(n)， 比前面介紹的其它排序方法占用的空間大 。 最壞情況比較 n(n1)/2 ????11)(niin???113ni7． 5 歸并排序 基本思想：將兩個(gè)有序子區(qū)間 （ 有序表 ） 合并成一個(gè)有序子區(qū)間 ， 一次合并完成后 ， 有序子區(qū)間的數(shù)目減少一半 ， 而區(qū)間的長(zhǎng)度增加一倍 ， 當(dāng)區(qū)間長(zhǎng)度從 1增加到 n（ 元素個(gè)數(shù) ） 時(shí) ， 整個(gè)區(qū)間變?yōu)橐粋€(gè) ， 即為有序序列 . 例如 ， 給定排序碼 46， 55， 13， 42， 94， 05， 17， 70， 二路歸并排序過程如圖 710所示 。 初始狀態(tài) [ 8 3 2 1 7 4 6 5 ] 第一次 [ 1 3 2 8 7 4 6 5 ] 第二次 [ 1 2 3 8 7 4 6 5 ] 第三次 [ 1 2 3 8 7 4 6 5 ] 第四次 [ 1 2 3 4 7 8 6 5 ] 第五次 [ 1 2 3 4 5 8 6 7 ] 第六次 [ 1 2 3 4 5 6 8 7 ] 第七次 [ 1 2 3 4 5 6 7 8 ] 圖 7 5 直接選擇排序的過程示例 直接選擇排序的效率分析 在直接選擇排序中 ， 共需要進(jìn)行 n1次選擇和交換 ， 每次選擇需要進(jìn)行 ni次比較 （ 1≤i≤n1） ， 而每次交換最 多需 3次移動(dòng) ， 因此 ， 總的比較次數(shù) C= =(n2n)/2， 總的移動(dòng)次數(shù) M= =3(n1)。 基本思想是：第一次從 array[0]~array[n1]中選取最小值 ， 與 array[0]交換 ， 第二次從 array[1]~array[n1]中選取最小值 ， 與 array[1]交換 ， 第三次從 array[2]~array[n1] 中選取最小值 ， 與 array[2] 交換 ， … ， 第 i次從 array[i1]~array[n1]中選取最小值 ， 與array[i1]交換 ， … , 第 n1次從 array[n2]~array[n1]中選取最小值 ， 與 array[n2]交換 ， 總共通過 n1次 ， 得到一個(gè)按排序碼從小到大排列的有序序列 。 快速排序是一種不穩(wěn)定的排序方法。 因此 ， 快速排序的最壞時(shí)間復(fù)雜度為 O(n2)。 已經(jīng)證明 ， 快速排序的平均時(shí)間復(fù)雜度也為 O（ nlog2n） 。 [ 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 ] i j [ 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 ] i j [ 1 7 5 5 1 3 4 2 9 4 0 5 46 7 0 ] i j [ 1 7 4 6 1 3 4 2 9 4 0 5 55 7 0 ] i j [ 1 7 05 1 3 4 2 9 4 4 6 55 7 0 ] i j [ 1 7 05 1 3 4 2 9 4 4 6 55 7 0 ] i j [ 1 7 05 1 3 4 2 9 4 4 6 55 7 0 ] i j [ 1 7 05 1 3 4 2 ] 4 6 [ 9 4 55 7 0 ] i j 圖 7 4 快速排序的一次劃分 3． 快速排序的效率分析 若快速排序出現(xiàn)最好的情形 （ 左 、 右子區(qū)間的長(zhǎng)度大致相等 ） ， 則結(jié)點(diǎn)數(shù) n與二叉樹深度 h應(yīng)滿足 log2nhlog2n+1 ， 所以總的比較次數(shù)不會(huì)超過 (n+1) log2n。 元素的比較和交換是從兩端向中間進(jìn)行的，排序碼較大的元素一次就能夠交換到后面，排序碼較小的記錄一次就能夠交換到前面，記錄每次移動(dòng)的距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。 由于其中的元素移動(dòng)較多 ， 所以屬于內(nèi)排序中速度較慢的一種 。 下面用圖 73給出冒泡排序算法的執(zhí)行過程 。 6． 3 交換排序 冒泡排序 基本思想 : 對(duì)待排序序列從后向前 （ 從下標(biāo)較大的元素開始 ） ，依次比較相鄰元素的排序碼 ， 若發(fā)現(xiàn)逆序則交換 ， 使排序碼較小的元素逐漸從后部移向前部 ， 就象水底下的氣泡一樣逐漸向上冒 。 下面用圖 72給出希爾排序算法的執(zhí)行過程 。 因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下 （ 接近最好情況 ） ， 效率是很高的 。 最壞情況比較 n(n1)/2 希爾排序 (縮小增量排序 ):1959年由 。 時(shí)間 :外層循環(huán)要進(jìn)行 n1次插入 ， 每次插入最少比較一次（ 正序 ） ， 移動(dòng)兩次；最多比較 i次 ， 移動(dòng) i＋ 2次 （ 逆序 ）（ i=1， 2， … ， n1） 。 0 1 2 3 4 5 初始狀態(tài) (1 7 ) 3 2 5 1 4 2 0 9 第一次插入 (3 1 7 ) 2 5 1 4 2 0 9 第二次插入 (3 1 7 2 5 ) 1 4 2 0 9 第三次插 入 (3 1 4 1 7 2 5 ) 2 0 9 第四次插入 (3 1 4 1 7 2 0 2 5 ) 9 第五次插入 (3 9 1 4 1 7 2 0 2 5 ) 圖 7 1 直接插入排序示例 3． 直接插入排序的效率分析 直接插入排序算法十分簡(jiǎn)單 。 例如 ， n=6， 數(shù)組 R的六個(gè)排序碼分別為： 17， 3， 25， 14，20， 9。 (按學(xué)號(hào)的遞增 ) 表 71 學(xué)生檔案表 學(xué)號(hào) 姓名 年齡 性別 99001 王曉佳 18 男 99002 林一鵬 19 男 99003 謝寧 17 女 99004 張麗娟 18 女 99005 周濤 20 男 99006 李小燕 16 女 為討論方便 ， 我們直接將排序碼寫成一個(gè)一維數(shù)組的形式 ， 并且在沒有聲明的情形下 ， 所有排序都按排序碼的值遞增排列 。 0 1 2 3 4 5 6 7 8 9 10 4 0 3 2 7 6 5 8 9