【文章內(nèi)容簡(jiǎn)介】 查元素為 38，首先將與線性表的中間項(xiàng)比較，即與第 4個(gè)數(shù)據(jù)元素 30相比較， 38大于中間項(xiàng) 30的值，則在線性表 [38， 46， 47， 70]中繼續(xù)查找；接著與中間 項(xiàng)比較，即與第 2個(gè)元素 46相比較， 38小于 46，則在線性表 [38]中繼續(xù)查找， 最后一次比較相等，查找成功。 順序查找法每一次比較，只將查找范圍減少 1，而二分法查找，每比較一次， 可將查找范圍減少為原來(lái)的一半，效率大大提高。 對(duì)于長(zhǎng)度為 n的有序線性表，在最壞情況下，二分法查找只需比較 log2n次， 而順序查找需要比較 n次。 排序 1. 交換類(lèi)排序法 （ 1）冒泡排序法 首先，從表頭開(kāi)始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面 的元素大于后面的元素，則將它們互換，不斷地將兩個(gè)相 鄰元素中的大者往后移 動(dòng)，最后最大者到了線性表的最后。 然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面 的元素小于前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移 動(dòng)，最后最小者到了線性表的最前面。 對(duì)剩下的線性表重復(fù)上述過(guò)程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排 好序。 在最壞的情況下，冒泡排序需要比較次數(shù)為 n(n1)/2。 （ 2）快速排序法 任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過(guò)一次排 序，將待排元素分為左右兩個(gè)子序列，左子序列 元素的排序碼均小于或等于基準(zhǔn) 元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子 序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。 2. 插入類(lèi)排序法 ① 簡(jiǎn)單插入排序法，最壞情況需要 n(n1)/2次比較； ② 希爾排序法，最壞情況需要 O()次比較。 3. 選擇類(lèi)排序法 ① 簡(jiǎn)單選擇排序法，最壞情況需要 n(n1)/2次比較； ② 堆排序法，最壞情況需要 O(nlog2n)次比較。 相比以上幾種（除希爾排序法外），堆排序法的時(shí)間復(fù)雜度最小。 第 2章 程序設(shè) 計(jì)基礎(chǔ) 程序設(shè)計(jì)的方法與風(fēng)格 養(yǎng)成良好的程序設(shè)計(jì)風(fēng)格，主要考慮下述因素： （ 1）源程序文檔化 ①符號(hào)名的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功 能的理解； ②程序注釋?zhuān)涸谠闯绦蛑刑砑诱_的注釋可幫助人們理解程序。程序注釋 可分為序言性注釋和功能性注釋。語(yǔ)句結(jié)構(gòu)清晰第一、效率第二； ③視覺(jué)組織：通過(guò)在程序中添加一些空格、空行和縮進(jìn)等，使人們?cè)谝曈X(jué) 上對(duì)程序的結(jié)構(gòu)一目了然。 （ 2）數(shù)據(jù)說(shuō)明的方法 為使程序中的數(shù)據(jù)說(shuō)明易于理解和維護(hù)，可采用下列數(shù)據(jù)說(shuō)明 的風(fēng)格，見(jiàn) 表 21。 表 21 數(shù)據(jù)說(shuō)明風(fēng)格 數(shù)據(jù)說(shuō)明風(fēng)格 詳細(xì)說(shuō)明 次序應(yīng)規(guī)范化 使數(shù)據(jù)說(shuō)明次序固定，使數(shù)據(jù)的屬性容易查找，也有利于測(cè)試、排錯(cuò) 和維護(hù) 變量安排有序化 當(dāng)多個(gè)變量出現(xiàn)在同一個(gè)說(shuō)明語(yǔ)句中時(shí)，變量名應(yīng)按字母順序排序， 以便于查找 使用注釋 在定義一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)通過(guò)注解來(lái)說(shuō)明該數(shù)據(jù)結(jié)構(gòu)的特點(diǎn) （ 3）語(yǔ)句的結(jié)構(gòu)程序 語(yǔ)句的結(jié)構(gòu)程序應(yīng)該簡(jiǎn)單易懂，語(yǔ)句構(gòu)造應(yīng)該簡(jiǎn)單直接。 （ 4）輸入和輸出 輸入輸出比較簡(jiǎn)單，這里就不作介紹。 結(jié)構(gòu)化程序設(shè)計(jì) 1. 結(jié)構(gòu)化程序設(shè)計(jì)的原則 結(jié)構(gòu)化程序設(shè)計(jì)方法引入了工程思想和結(jié)構(gòu)化思想，使大型軟件的開(kāi)發(fā)和編 程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為：自頂向下、逐步求精、 模塊化和限制使用 goto語(yǔ)句。 ① 自頂向上：先考慮整體，再考慮細(xì)節(jié)；先考慮全局目標(biāo)，再考慮局部 目標(biāo)； ② 逐步求精：對(duì)復(fù)雜問(wèn)題應(yīng)設(shè)計(jì)一些子目標(biāo)作為過(guò)渡，逐步細(xì)化； ③ 模塊化：把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的 小目標(biāo)，把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊。 限制使用 goto語(yǔ)句：在 程序開(kāi)發(fā)過(guò)程中要限制使用 goto語(yǔ)句。 2. 結(jié)構(gòu)化程序的基本結(jié)構(gòu) 結(jié)構(gòu)化程序的基本結(jié)構(gòu)有三種類(lèi)型：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。 ① 順序結(jié)構(gòu)：是最基本、最普通的結(jié)構(gòu)形式，按照程序中的語(yǔ)句行的先后 順序逐條執(zhí)行； ② 選擇結(jié)構(gòu)：又稱(chēng)為分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)； ③ 循環(huán)結(jié)構(gòu)：根據(jù)給定的條件，判斷是否要重復(fù)執(zhí)行某一相同的或類(lèi)似的 程序段。循環(huán)結(jié)構(gòu)對(duì)應(yīng)兩類(lèi)循環(huán)語(yǔ)句：先判斷后執(zhí)行的循環(huán)體稱(chēng)為當(dāng)型循環(huán)結(jié)構(gòu)； 先執(zhí)行循環(huán)體后判斷的稱(chēng)為直到型循環(huán)結(jié)構(gòu)。 面向?qū)ο蠓椒? 面向?qū)ο蠓椒êw對(duì)象及對(duì)象屬性與方法、類(lèi)、繼承、多態(tài)性幾個(gè)基本要素。 1. 對(duì)象 通常把對(duì)象的操作也稱(chēng)為方法或服務(wù)。 屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過(guò)執(zhí)行對(duì)象的 操作來(lái)改變。屬性值應(yīng)該指的是純粹的數(shù)據(jù)值，而不能指對(duì)象。 操作描述了對(duì)象執(zhí)行的功能，若通過(guò)信息的傳遞，還可以為其他對(duì)象使用。 對(duì)象具有如下特征：標(biāo)識(shí)惟一性、分類(lèi)性、多態(tài)性、封裝性、模塊獨(dú)立性。 2. 類(lèi)和實(shí)例 類(lèi)是具有共同屬性、共同方法的對(duì)象的集合。它描述了屬于該對(duì)象類(lèi)型的所 有對(duì)象的性質(zhì)， 而一個(gè)對(duì)象則是其對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。 類(lèi)是關(guān)于對(duì)象性質(zhì)的描述，它同對(duì)象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的 一組合法操作。 3. 消息 消息是實(shí)例之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信 息，它統(tǒng)一了數(shù)據(jù)流和控制流。 一個(gè)消息由三部分組成：接收消息的對(duì)象的名稱(chēng)、消息標(biāo)識(shí)符（消息名）和 零個(gè)或多個(gè)參數(shù)。 4. 繼承 廣義地說(shuō)，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。 繼承分為單繼承與多重繼承。單繼承是指，一個(gè)類(lèi)只允許有一個(gè)父類(lèi)，即類(lèi) 等級(jí)為樹(shù)形結(jié)構(gòu)。多 重繼承是指，一個(gè)類(lèi)允許有多個(gè)父類(lèi)。 5. 多態(tài)性 對(duì)象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致 完全不同的行動(dòng)，該現(xiàn)象稱(chēng)為多態(tài)性。 第 3章 軟件工程基礎(chǔ) 軟件工程基本概念 1. 軟件定義與軟件特點(diǎn) 軟件指的是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)和相 關(guān)文檔的完整集合。 程序是軟件開(kāi)發(fā)人員根據(jù)用戶需求開(kāi)發(fā)的、用程序設(shè)計(jì)語(yǔ)言描述的、適合計(jì) 算機(jī)執(zhí)行的指令序列。 數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序的開(kāi)發(fā)、維護(hù)和使 用 有關(guān)的圖文資料。 可見(jiàn)，軟件由兩部分組成： .. 機(jī)器可執(zhí)行的程序和數(shù)據(jù)； .. 機(jī)器不可執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。 根據(jù)應(yīng)用目標(biāo)的不同，軟件可分應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具 軟件），見(jiàn)表 31。 表 31 軟件的分類(lèi) 名稱(chēng) 描述 應(yīng)用軟件 為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件 系統(tǒng)軟件 計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提 供各種服務(wù)的軟件 支撐軟件（或工具軟件） 支撐軟件是介于兩者之間，協(xié)助用戶開(kāi)發(fā) 軟件的工具性軟件 2. 軟件工程 為了擺脫軟件危機(jī)，提出了軟件工程的概念。軟件工程學(xué)是研究軟件開(kāi)發(fā)和 維護(hù)的普遍原理與技術(shù)的一門(mén)工程學(xué)科。所謂軟件工程是指采用工程的概念、原 理、技術(shù)和方法指導(dǎo)軟件的開(kāi)發(fā)與維護(hù)。軟件工程學(xué)的主要研究對(duì)象包括軟件開(kāi) 發(fā)與維護(hù)的技術(shù)、方法、工具和管理等方面。 軟件工程包括 3個(gè)要素：方法、工具和過(guò)程，見(jiàn)表 32。 表 32 軟件工程三要素 名稱(chēng) 描述 方法 方法是完成軟件工程項(xiàng)目的技術(shù)手段 工具 工具支持軟件的開(kāi)發(fā)、管理、文檔生成 過(guò)程 過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理 軟件生命周期 1. 軟件生命周期概念 軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱(chēng)為軟件生命周期。 軟件生命周期分為 3個(gè)時(shí)期共 8個(gè)階段， .. 軟件定義期：包括問(wèn)題定義、可行性研究和需求分析 3個(gè)階段； .. 軟件開(kāi)發(fā)期：包括概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)和測(cè)試 4個(gè)階段； .. 運(yùn)行維護(hù)期：即運(yùn)行維護(hù)階段。 軟件生命周期各個(gè)階段的活動(dòng)可以有重復(fù)，執(zhí)行時(shí)也可以有迭代，如圖 31 所示。 圖 31 軟件生命周期 2. 軟件生命周期各階段的主要任務(wù) 在圖 31中的軟件生命周期各階段的主要任務(wù)，見(jiàn)表 33。 表 33 軟件生命周期各階段的主要任務(wù) 任務(wù) 描述 問(wèn)題定義 確定要求解決的問(wèn)題是什么 可行性研究 與計(jì)劃制定 決定該問(wèn)題是否存在一個(gè)可行的解決辦法，指定完成開(kāi)發(fā)任務(wù)的實(shí)施計(jì)劃 需求分析 對(duì)待開(kāi)發(fā)軟件提出需求進(jìn)行分析并給出詳細(xì)定義。編寫(xiě)軟件規(guī)格說(shuō)明書(shū)及初 步的用戶手冊(cè)，提交評(píng)審 軟件設(shè)計(jì) 通常又分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)階段，給出軟件的結(jié)構(gòu)、模塊 的劃分、 功能的分配以及處理流程。這階段提交評(píng)審的文檔有概要設(shè)計(jì)說(shuō)明書(shū)、詳細(xì) 設(shè)計(jì)說(shuō)明書(shū)和測(cè)試計(jì)劃初稿 軟件實(shí)現(xiàn) 在軟件設(shè)計(jì)的