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