【文章內(nèi)容簡(jiǎn)介】 j]a[j+1]) { k=a[j]。a[j]=a[j+1]。a[j+1]=k。 } } } 2022/2/9 50 void main() { int i,b[N]={123,7,9,12,7,89,93,97,103,18}。 popsort(b,N)。 printf(排序結(jié)果為： \n)。 for(i=0。iN。i++) printf(%d ,b[i])。 } 排序技術(shù) ? 插入類排序法 ? 簡(jiǎn)單插入排序：指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。 ?從線性表的第 2個(gè)元素開始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中。 ?這種排序方法的效率與冒泡排序法相同。 ?在最壞情況下，簡(jiǎn)單插入排序需要 n(n1)/2次比較。 ? 希爾排序：將整個(gè)無(wú)序序列分割成若干個(gè)小的子序列分別進(jìn)行插入排序。 ?在最壞情況下，希爾排序所需的比較次數(shù)為 2022/2/9 51 簡(jiǎn)單插入排序的 C語(yǔ)言程序 2022/2/9 52 插入排序算法思路 假定這個(gè)數(shù)組的序是排好的 ,然后從頭往后 ,如果有數(shù)比當(dāng)前外層元素的值大 ,則將這個(gè)數(shù)的位置往后挪 ,直到當(dāng)前外層元素的值大于或等于它前面的位置為止 .這具算法在排完前 k個(gè)數(shù)之后 ,可以保證 a[1…k] 是局部有序的 ,保證了插入過程的正確性 . 編輯本段算法描述 一般來(lái)說(shuō)，插入排序都采用 inplace在數(shù)組上實(shí)現(xiàn)。具體算法描述如下： 1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序 2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描 3. 如果該元素（已排序）大于新元素，將該元素移到下一位置 4. 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置 5. 將新元素插入到下一位置中 6. 重復(fù)步驟 2 2022/2/9 53 include define N 10 void InsertSort(int array[],unsigned int n) { int i,j。 int temp。 for(i=1。in。i++) { temp = array[i]。//存儲(chǔ)臨時(shí)數(shù)據(jù) for(j=i 。 j0 amp。amp。 temp array[j1] 。 j) { array[j]=array[j1]。//原數(shù)組中滿足條件的元素右移 } array[j]=temp。//找到插入位置，插入數(shù)據(jù) } } 程序： 2022/2/9 54 void main() { int i,b[N]={123,7,9,12,7,89,93,97,103,18}。 InsertSort(b,N)。 printf(排序結(jié)果為： \n)。 for(i=0。iN。i++) printf(%d ,b[i])。 } 排序技術(shù) ? 選擇類排序 ? 簡(jiǎn)單選擇排序法：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。 ?簡(jiǎn)單選擇排序在最壞情況下需要比較 n(n1)/2次。 ? 堆排序 ?在最壞情況下，堆排序需要比較的次數(shù)為 nlog2n 2022/2/9 55 簡(jiǎn)單選擇排序的 C語(yǔ)言程序 2022/2/9 56 簡(jiǎn)單選擇排序的基本思想 n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果： ①初始狀態(tài)：無(wú)序區(qū)為 R[1..n]，有序區(qū)為空。 ② 第 1趟排序 在無(wú)序區(qū) R[1..n]中選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第 1個(gè)記錄 R[1]交換，使 R[1..1]和 R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加 1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1個(gè)的新無(wú)序區(qū)。 …… 2022/2/9 57 ③ 第 i趟排序 第 i趟排序開始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為 R[1..i1]和 R[i..n](1≤i≤n1)。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它 與無(wú)序區(qū)的第 1個(gè)記錄 R[i]交換，使 R[1..i]和 R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1個(gè)的新無(wú)序區(qū)。 這樣， n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果。 2022/2/9 58 include define N 10 void selectionsort(int a[],int n) { int i,j,k,temp。 for(i=0。i=n1。i++) { k=i。 for( j=i+1。j=n1。j++) if(a[k]a[j]) k=j。 if(k!=i) { temp=a[i]。 a[i]=a[k]。 a[k]=temp。 } } } 程序： 2022/2/9 59 void main() { int i,b[N]={123,7,9,12,7,89,93,97,103,18}。 selectionsort(b,N)。 printf(排序結(jié)果為： \n)。 for(i=0。iN。i++) printf(%d ,b[i])。 } 程序設(shè)計(jì)基礎(chǔ) ? 就程序設(shè)計(jì)方法和技術(shù)而言，程序設(shè)計(jì)主要經(jīng)歷了 結(jié)構(gòu)化程序設(shè)計(jì) 和 面向?qū)ο?的程序設(shè)計(jì)階段。 ? 要形成良好的設(shè)計(jì)風(fēng)格，主要應(yīng)注意和考慮下述一些因素： ? 源程序文檔化 ?符號(hào)的命名：符號(hào)名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解。 ?程序注釋： 序言性注釋 和 功能性注釋 ?視覺組織 ? 數(shù)據(jù)說(shuō)明 ? 語(yǔ)言結(jié)構(gòu)：除非對(duì)效率有特殊要求，程序編寫要做到清晰第一，效率第二。 ? 輸入和輸出 2022/2/9 60 結(jié)構(gòu)化程序設(shè)計(jì) ? 設(shè)計(jì)的主要原則： 自頂向下、逐步求精、模塊化、限制使用 goto語(yǔ)句。 自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。 逐步求精：對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。 模塊化：一個(gè)復(fù)雜問題，是由若干個(gè)簡(jiǎn)單問題構(gòu)成的。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。 限制使用 goto語(yǔ)句：濫用 goto語(yǔ)句有害，應(yīng)盡量避免。 2022/2/9 61 結(jié)構(gòu)化程序設(shè)計(jì) ? 結(jié)構(gòu)化程序的基本結(jié)構(gòu) ? 順序結(jié)構(gòu)、選擇結(jié)構(gòu)（分支結(jié)構(gòu)）、重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)） ? 采用結(jié)構(gòu)化程序設(shè)計(jì)方法編寫程序，可使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。 ? 僅用這三種基本控制結(jié)構(gòu)就可以表達(dá)出各種其他形式結(jié)構(gòu)的程序設(shè)計(jì)方法。 ? 結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用 ? 使用程序設(shè)計(jì)語(yǔ)言的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。 ? 選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口。 ? 程序語(yǔ)句組成容易識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口。 ? 復(fù)雜結(jié)構(gòu)應(yīng)該應(yīng)用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)。 ? 語(yǔ)言種所沒有的控制結(jié)構(gòu)，應(yīng)采用前后一致的方法來(lái)模擬。 ? 嚴(yán)格控制 goto語(yǔ)句的使用。 2022/2/9 62 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn) 與人類習(xí)慣的思維方式一致，穩(wěn)定性好，可重用性好，易于開發(fā)大型軟件產(chǎn)品，可維護(hù)性好。 ? 面向?qū)ο蠹夹g(shù)的基本概念 ? 對(duì)象：是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。一般只能通過執(zhí)行對(duì)象的操作來(lái)改變其屬性。對(duì)象可以做的操作表示它的動(dòng)態(tài)行為，通常把對(duì)象的操作稱為 方法或服務(wù) 。 2022/2/9 63 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 對(duì)象有如下一些基本特點(diǎn)： ? 標(biāo)識(shí)惟一性。指對(duì)象是可以區(qū)分的，由它的內(nèi)在本質(zhì)來(lái)區(qū)分。 ? 分類性。指將具有相同屬性和操作的對(duì)象抽象成類。 ? 多態(tài)性。指同一個(gè)操作可以是不同對(duì)象的行為。 ? 封裝性。用戶只需知道數(shù)據(jù)的取值范圍和可以對(duì)該對(duì)象進(jìn)行的操作，無(wú)需知道數(shù)據(jù)具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法，對(duì)象內(nèi)部，對(duì)外不可見。 ? 模塊獨(dú)立性好。對(duì)象內(nèi)部各元素結(jié)合緊密，內(nèi)聚性強(qiáng)。 2022/2/9 64 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 類 是具有共同屬性、共同方法的對(duì)象的集合。類是對(duì)象的抽象，它描 述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)。 ? 對(duì)象 對(duì)象是其對(duì)應(yīng)類的一個(gè)實(shí)例。 ? 消息 是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，類似于函數(shù)調(diào)用。 ? 繼承 是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。 一個(gè)類直接繼承其父類的數(shù)據(jù)和方法，子類可以有新的數(shù)據(jù)和方法。 單繼承指一個(gè)類只允許有一個(gè)父類；多繼承指一個(gè)類允許有多個(gè)父 類。 ? 多態(tài)性 同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)。 2022/2/9 65 軟件工程基礎(chǔ) ? 軟件工程基本概念 ? 結(jié)構(gòu)化分析方法 ? 結(jié)構(gòu)化設(shè)計(jì)方法 ? 軟件測(cè)試方法和技術(shù) ? 程序調(diào)試 2022/2/9 66 軟件工程基本概念 ? 軟件：是 程序、數(shù)據(jù)及相關(guān)文檔 的完整集合。 ? 軟件工程：是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。 ? 軟件工程學(xué)：用工程、科學(xué)和數(shù)學(xué)的原理與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法的一門工程科學(xué)。 ? 軟件工程 3要素： 方法、工具、過程 方法：完成軟件工程項(xiàng)目的技術(shù)手段。 工具：支持軟件的開發(fā)、管理、文檔生成。 過程：支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理，是把輸 入轉(zhuǎn)達(dá)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。 2022/2/9 67 軟件生命周期 ? 軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。 ? 軟件生命周期的三階段：軟件定義、軟件開發(fā)、運(yùn)行維護(hù) ? 主要活動(dòng)階段： ? 可行性研究與計(jì)劃制定。確定待開發(fā)軟件系統(tǒng)的開發(fā)目標(biāo)和總的要求，給出它的功能、性能、可靠性及接口等方面的可能方案，制定完成開發(fā)任務(wù)的實(shí)施計(jì)劃。 ? 需求分析。對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。編寫軟件說(shuō)明書及初步的用戶手冊(cè)。 ? 軟件設(shè)計(jì)。給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配及處理流程。可分為 概要設(shè)計(jì)和詳細(xì)設(shè)計(jì) 。編寫概要設(shè)計(jì)說(shuō)明書、詳細(xì)設(shè)計(jì)說(shuō)明書等。 ? 軟件實(shí)現(xiàn)。把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。 ? 軟件測(cè)試。在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。 ? 運(yùn)行和維護(hù)。將已交付的軟件投入運(yùn)行，并在運(yùn)行使用中不繼維護(hù)。 2022/2/9 68 開發(fā)工具與開發(fā)環(huán)境 ? 軟件開發(fā)工具與軟件開發(fā)環(huán)境的使用提高了軟件的開發(fā)效率、維護(hù)效率和軟件質(zhì)量。 ? 軟件開發(fā)工具為軟件工程方法提供了自動(dòng)或半自動(dòng)的軟件支持環(huán)境。 ? 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。 2022/2/9 69 軟件工程的目標(biāo)與原則 ? 軟件工程的目標(biāo) : 在給定成本、進(jìn)度的前提下，開發(fā)具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 ? 基于軟件工程的目標(biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括： 軟件開發(fā)技術(shù)和軟件工程管理 。 ? 為了達(dá)到軟件工程目標(biāo)，在軟件開發(fā)過程中，必須遵循軟件工程的基本原則。這些原則適用于所有的軟件項(xiàng)目。這些原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。 2022/2/9 70 結(jié)構(gòu)化分析方法 ? 需求分析階段的工作有： ? 需求獲取 ? 需求分析 ? 編寫需求規(guī)格說(shuō)明書 ? 需求評(píng)審 ? 常見的需求分析方法有： 結(jié)構(gòu)化分析方法、面向?qū)ο蟮姆治龇椒?。 2022/2/9 71 結(jié)構(gòu)化分析方法 ? 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件 需求分析 階段的運(yùn)用。 ? 它著眼于 數(shù)據(jù)流 ，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以 數(shù)據(jù)流圖 和 數(shù)據(jù)字典 為主要工具，建立系統(tǒng)的 邏輯模型 。 ? 判斷樹 ? 判斷表 2022/2/9 72 數(shù)據(jù)流圖 ? 是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的 功能 建模。 ? 它從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫數(shù)據(jù)流從輸入到輸出