計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)VIP

二級(jí)共公基礎(chǔ)知識(shí)教程二級(jí)共公基礎(chǔ)知識(shí)教程 第一章數(shù)據(jù)結(jié)構(gòu)與算法 1 1 算法 算法 是指解題方案的準(zhǔn)確而完整的描述 算法不等于程序 也不等計(jì)算機(jī)方法 程序的編制不可能優(yōu)于算法的設(shè)計(jì) 算法的基本特征 是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則 每一個(gè)規(guī)則都是有效的 是明確的 此順序?qū)⒃谟邢薜拇螖?shù)下終止 特征包括 1 可行性 2 確定性 算法中每一步驟都必須有明確定義 不充許有模棱兩可的解釋 不允許有多 義性 3 有窮性 算法必須能在有限的時(shí)間內(nèi)做完 即能在執(zhí)行有限個(gè)步驟后終止 包括合理 的執(zhí)行時(shí)間的含義 4 擁有足夠的情報(bào) 算法的基本要素 一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作 二是算法的控制結(jié)構(gòu) 指令系統(tǒng) 一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合 基本運(yùn)算和操作包括 算術(shù)運(yùn)算 邏輯運(yùn)算 關(guān)系運(yùn)算 數(shù)據(jù)傳輸 算法的控制結(jié)構(gòu) 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 算法基本設(shè)計(jì)方法 列舉法 歸納法 遞推 遞歸 減斗遞推技術(shù) 回溯法 算法復(fù)雜度 算法時(shí)間復(fù)雜度和算法空間復(fù)雜度 算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量 算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間 1 2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面 1 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系 即數(shù)據(jù)的邏輯結(jié)構(gòu) 2 在對(duì)數(shù)據(jù)進(jìn)行處理時(shí) 各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系 即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合 數(shù)據(jù)的邏輯結(jié)構(gòu)包含 1 表示數(shù)據(jù)元素的信息 2 表示各數(shù)據(jù)元素之間的前后件關(guān)系 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序 鏈接 索引等 線性結(jié)構(gòu)條件 1 有且只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件 也最多有一個(gè)后件 非線性結(jié)構(gòu) 不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu) 1 3 線性表及其順序存儲(chǔ)結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成 數(shù)據(jù)元素的位置只取決于自己的序號(hào) 元素之間的相對(duì)位置 是線性的 在復(fù)雜線性表中 由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱(chēng)為記錄 而由多個(gè)記錄構(gòu)成的線性 表又稱(chēng)為文件 非空線性表的結(jié)構(gòu)特征 1 且只有一個(gè)根結(jié)點(diǎn) a1 它無(wú)前件 2 有且只有一個(gè)終端結(jié)點(diǎn) an 它無(wú)后件 3 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外 其他所有結(jié)點(diǎn)有且只有一個(gè)前件 也有且只有一個(gè)后件 結(jié) 點(diǎn)個(gè)數(shù) n 稱(chēng)為線性表的長(zhǎng)度 當(dāng) n 0 時(shí) 稱(chēng)為空表 線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn) 1 線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的 2 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 ai 的存儲(chǔ)地址為 ADR ai ADR a1 i 1 k ADR a1 為第一個(gè)元素的地址 k 代表每個(gè)元 素占的字節(jié)數(shù) 順序表的運(yùn)算 插入 刪除 詳見(jiàn) 14 16 頁(yè) 1 4 棧和隊(duì)列 棧是限定在一端進(jìn)行插入與刪除的線性表 允許插入與刪除的一端稱(chēng)為棧頂 不允許插入 與刪除的另一端稱(chēng)為棧底 棧按照 先進(jìn)后出 FILO 或 后進(jìn)先出 LIFO 組織數(shù)據(jù) 棧具有記憶作用 用 top 表 示棧頂位置 用 bottom 表示棧底 棧的基本運(yùn)算 1 插入元素稱(chēng)為入棧運(yùn)算 2 刪除元素稱(chēng)為退棧運(yùn)算 3 讀棧頂 元素是將棧頂元素賦給一個(gè)指定的變量 此時(shí)指針無(wú)變化 隊(duì)列是指允許在一端 隊(duì)尾 進(jìn)入插入 而在另一端 隊(duì)頭 進(jìn)行刪除的線性表 Rear 指 針指向隊(duì)尾 front 指針指向隊(duì)頭 隊(duì)列是 先進(jìn)行出 FIFO 或 后進(jìn)后出 LILO 的線性表 隊(duì)列運(yùn)算包括 1 入隊(duì)運(yùn)算 從隊(duì)尾插入一個(gè)元素 2 退隊(duì)運(yùn)算 從隊(duì)頭刪除一個(gè)元 素 循環(huán)隊(duì)列 s 0 表示隊(duì)列空 s 1 且 front rear 表示隊(duì)列滿 1 5 線性鏈表 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元 這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn) 簡(jiǎn)稱(chēng)結(jié)點(diǎn) 結(jié)點(diǎn)由兩部分組成 1 用于存儲(chǔ)數(shù)據(jù)元素值 稱(chēng)為數(shù)據(jù)域 2 用于存放指針 稱(chēng)為 指針域 用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn) 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù) 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù) 元素之間的邏輯關(guān)系可以不一致 而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的 鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu) 也可用于表示非線性結(jié)構(gòu) 線性鏈表 HEAD 稱(chēng)為頭指針 HEAD NULL 或 0 稱(chēng)為空表 如果是兩指針 左指針 Llink 指向前件結(jié)點(diǎn) 右指針 Rlink 指向后件結(jié)點(diǎn) 線性鏈表的基本運(yùn)算 查找 插入 刪除 1 6 樹(shù)與二叉樹(shù) 一 樹(shù)的基本概念 在樹(shù)結(jié)構(gòu)中 每一個(gè)結(jié)點(diǎn)只有一個(gè)前件 稱(chēng)為父結(jié)點(diǎn) 沒(méi)有前件的結(jié)點(diǎn)只有一個(gè) 稱(chēng)為樹(shù) 的根結(jié)點(diǎn) 簡(jiǎn)稱(chēng)為樹(shù)的根 在樹(shù)結(jié)構(gòu)中 每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件 它們都稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn) 沒(méi)有后件的結(jié)點(diǎn) 稱(chēng)為葉子結(jié)點(diǎn) 在樹(shù)結(jié)構(gòu)中 一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度 葉子結(jié)點(diǎn)的度為 0 樹(shù)的最大層次稱(chēng)為樹(shù)的深度 在一個(gè)算術(shù)表達(dá)式中 有運(yùn)算符和運(yùn)算對(duì)象 一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)算對(duì)象 例職 取正 等只有一個(gè)運(yùn)算對(duì)象 稱(chēng)為單目運(yùn)算符 二個(gè)運(yùn)算對(duì)象稱(chēng)為雙目運(yùn)算符 三目 運(yùn)算符 用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則如下 表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn) 稱(chēng)為運(yùn)算符結(jié)點(diǎn) 運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù) 在樹(shù)中的順序?yàn)閺淖蟮接?運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn) 二 二叉樹(shù)及其基本性質(zhì) 1 什么是二叉樹(shù) 二叉樹(shù)是一種很有用的非線性結(jié)構(gòu) 二就樹(shù)具有以下兩個(gè)特點(diǎn) 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn) 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù) 且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù) 由以上特點(diǎn)可以看出 在二叉樹(shù)中 每一個(gè)結(jié)點(diǎn)的度最大為 2 即所有子樹(shù) 左子樹(shù)或右 子樹(shù) 也均為二叉樹(shù) 而樹(shù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的 另外 二叉樹(shù)中的每 一個(gè)結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與右子樹(shù) 可以沒(méi)有其中的一個(gè) 也可以全沒(méi)有 二叉樹(shù)的基本性質(zhì) 性質(zhì) 1 在二叉樹(shù)的第 K 層上 最多有 K 1 個(gè)結(jié)點(diǎn) 性質(zhì) 2 濃度為 M 的二叉樹(shù)最多有 2m 1 個(gè)結(jié)點(diǎn) 深度為 m 的二叉樹(shù)是指二叉樹(shù)共有 m 層 性質(zhì) 3 在任意一棵二叉樹(shù)中度為 0 的結(jié)點(diǎn) 即葉子結(jié)點(diǎn) 總是比度為 2 的結(jié)點(diǎn)多一個(gè) 性質(zhì) 4 具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù) 其深度至少為 log2n 1 其中 log2n 表示取的整數(shù)部分 滿二叉樹(shù)與完全二叉樹(shù) 滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù) 滿二叉樹(shù) 所謂滿二叉樹(shù)是指這樣的一種二叉樹(shù) 除最后一層外 每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié) 點(diǎn) 這就是說(shuō) 在滿二叉樹(shù)中 每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值 即在滿二叉樹(shù)的第 K 層 上有 2K 1 個(gè)結(jié)點(diǎn) 且深度為 m 的滿二叉樹(shù)有 2m 1 個(gè)結(jié)點(diǎn) 完全二叉樹(shù) 所謂完全二叉樹(shù)是指這樣的二叉樹(shù) 除最后一層外 每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值 在 最后一層上只缺少右邊的若干結(jié)點(diǎn) 列確切地說(shuō) 如果從根結(jié)點(diǎn)起 對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下 自左至右用自然數(shù)進(jìn)行邊疆編 號(hào) 則深度為 m 且有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù) 當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 m 的滿二 叉樹(shù)中編號(hào)從 1 到 n 的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí) 稱(chēng)之為完全二叉樹(shù) 對(duì)于完全二叉樹(shù)來(lái)說(shuō) 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) 對(duì)于任何一個(gè)結(jié)點(diǎn) 若 其右分支下的子孫結(jié)點(diǎn)的最大層次為 p 則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)?p 或?yàn)?p 1 由滿二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出 滿二叉樹(shù)也是完全二叉樹(shù) 而完全二叉樹(shù)一般 不是滿二叉樹(shù) 完全二叉樹(shù)還具有以下兩個(gè)性質(zhì) 性質(zhì) 5 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n 1 性質(zhì) 6 設(shè)完全二叉樹(shù)共有 n 個(gè)結(jié)點(diǎn) 如果從根結(jié)點(diǎn)開(kāi)始 按層序 每一層從左到右 用 自然數(shù) 1 2 n 給結(jié)點(diǎn)進(jìn)行編號(hào) 則對(duì)于編號(hào)為 k k 1 2 n 的結(jié)點(diǎn)有以下結(jié)論 若 k 1 則該結(jié)點(diǎn)為根結(jié)點(diǎn) 它沒(méi)有父結(jié)點(diǎn) 若 k 1 則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 INT k 2 若 2k n 則編號(hào)為 k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn) 顯然也沒(méi)有 右子結(jié)點(diǎn) 若 2k 1 n 則編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2k 1 否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn) 三 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的遍歷 二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn) 在遍歷二叉樹(shù)的過(guò)程中 一般先遍歷左子樹(shù) 然后再遍歷右子樹(shù) 1 前序遍歷 DLR 所謂前序遍歷是指在訪問(wèn)根結(jié)點(diǎn) 遍歷左子樹(shù)與遍歷右子樹(shù)這三者中 首先訪問(wèn)根結(jié)點(diǎn) 然后遍歷左子樹(shù) 最后遍歷右子樹(shù) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先訪問(wèn)根結(jié)點(diǎn) 然 后遍歷左子樹(shù) 最后遍歷右子樹(shù) F C A D B E G H P 2 中序遍歷 LDR 所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn) 遍歷左子樹(shù)與遍歷右子樹(shù)這三者中 首先遍歷左子樹(shù) 然后訪問(wèn)根結(jié)點(diǎn) 最后遍歷右子樹(shù) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先遍歷左子樹(shù) 然 后訪問(wèn)根結(jié)點(diǎn) 最后遍歷右子樹(shù) A C B D F E H G P 3 后序遍歷 LRD 所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn) 遍歷左子樹(shù)與遍歷右子樹(shù)這三者中 首先遍歷左子樹(shù) 然后遍歷右子樹(shù) 最后訪問(wèn)根結(jié)點(diǎn) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先遍歷左子樹(shù) 然 后遍歷右子樹(shù) 最后訪問(wèn)根結(jié)點(diǎn) A B D C H P G E F 1 7 查找技術(shù) 一 順序查找 順序查找又稱(chēng)順序搜索 順序查找一般是指在線性表中查找指定的元素 其基本方法如下 從線性表的第一個(gè)元素開(kāi)始 依次將線性表中的元素與被查元素進(jìn)行比較 若相等則表示 找到 即查找成功 若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等 則表示 線性表中沒(méi)有要找的元素 即查找失敗 順序查找的效率是很低的 以下兩種情況只能采用順序查找 如果線性表無(wú)序表 即表中元素的排列是無(wú)序的 則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu) 都只能用順序查找 即使是有序線性表 如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 也只能用順序查找 二 二分法查找 二分法查找只適用于存儲(chǔ)的有序表 在此所說(shuō)的有序表是指線性表的中元素按值非遞減排 列 即從小到大 但允許相鄰元素值相等 設(shè)有序線性表的長(zhǎng)度為 n 被查元素為 x 則對(duì)分查找的方法如下 將 x 與線性表的中間項(xiàng)進(jìn)行比較 若中間項(xiàng)的值等于 x 則說(shuō)明查到 查找結(jié)束 若 x 小于中間項(xiàng)的值 則在線性表的前半部分 即中間項(xiàng)以前的部分 以相同的方法進(jìn)行 查找 若 x 大于中間項(xiàng)的值 則在線性表的后半部分 即中間項(xiàng)以后的部分 以相同的方法進(jìn)行 查找 這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為 0 說(shuō)明線性表中沒(méi)有這個(gè)元素 為止 顯然 當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找 并且 二分查找的效率要比順序查 找高得多 可以證明 對(duì)于長(zhǎng)度為 n 的有序線性表 在最壞情況下 二分查找只需要比較 log2n 次 而順序查找需要比較 n 次 1 8 排序技術(shù) 一 交換類(lèi)排隊(duì)序法 所謂交換類(lèi)排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法 冒泡排序法與 快速排序法都屬于交換類(lèi)的排序方法 1 冒泡排序法 基本過(guò)程如下 首先 從表頭開(kāi)始往后掃描線性表 在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小 若相鄰 兩個(gè)元素中 前面的元素大于后面的元素 則將它們互換 稱(chēng)之為消去了一個(gè)逆序 放最 大值 然后 從后到前掃描剩下的線性表 同樣 在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小 若相鄰兩個(gè)元素中 后面的元素大于前面的元素 則將它們互換 這樣就又消去了一個(gè)逆 序 放最小值 重復(fù)上述過(guò)程 直到剩下的線性有變空為止 此時(shí)的線性表已經(jīng)變?yōu)橛行?假設(shè)線性表的長(zhǎng)為 n 則在最壞情況下 冒泡排序需要經(jīng)過(guò) n 2 遍的蔥馨往后的掃描和 n 2 遍的從后往前的掃描 需要的比較的次數(shù)為 n n 1 2 2 快速排序法 快速排序法也是種互換類(lèi)的排序法 但由于它比冒泡排序法的速度快 因此稱(chēng)之為快速排 序法 基本思想如下 從線性表中選取一個(gè)元素 設(shè) T 將線性表后面小于 T 的元素移到前 而前大于 T 的元素 移支后面 結(jié)果就將線性表分成了兩部分 稱(chēng)為兩個(gè)子表 T 插入到其分界線的位置處 這個(gè)過(guò)程稱(chēng)為線性表的分割 通過(guò)對(duì)線性表的一次分割 就以 T 為分界線 將線性表分成 了前后兩個(gè)子表 且前面子表中的所有元素均不大于 T 而后面子表中的所有元素均不小 于 T 如此反復(fù) 則此時(shí)的線性表就變成了有序表 步驟 首先 在表的第一個(gè) 中間一個(gè)與最后一個(gè)元素中選取中項(xiàng) 設(shè)為 P K 并將 P K 賦給 T 再將表中的第一個(gè)元素移到 P K 的位置上 然后設(shè)置兩個(gè)指針 i 和 j 分別指向表的起始與最后的位置 反復(fù)操作以下兩步 4 將 j 逐漸減小 并逐次比較 P j 與 T 直到發(fā)現(xiàn)一個(gè) P j T 為止 將 P i 移到 P j 位置上 上述兩個(gè)操作交替進(jìn)行 直到指針 i 與 j 指向同一個(gè)位置 即 i j 為止 此時(shí)將 P i 的位 置上 分割需要記憶 用棧來(lái)實(shí)現(xiàn) 二 插入類(lèi)排序法 1 簡(jiǎn)單插入排序法 所謂插入排序 是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中 一般來(lái)說(shuō) 假設(shè)線性中前 j 1 元素已經(jīng)有序 現(xiàn)在要將線性表中第 j 個(gè)元素插入到前面的有 序子表中 插入過(guò)程如下 道德將第 j 個(gè)元素放到一個(gè)變量 T 中 然后從有序子表的最后一個(gè)元素 即線性表中第 j 1 個(gè)元素 開(kāi)始 往前逐個(gè)與 T 進(jìn)行比較 將大于 T 的元素均依次向后移動(dòng)一個(gè)位置 直到 發(fā)現(xiàn)一個(gè)元素不大于 T 為止 此時(shí)就將 T 即原線性表中的第 j 個(gè)元素 插入到剛移出的 空位置上 有序子表的長(zhǎng)度就變?yōu)?j 了 效率與冒泡法相同 在最壞情況下 簡(jiǎn)單插入排序需要 n n 1 2 次比較 2 希爾排序法 基本思想如下 將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序 子序列的分割方法如下 將相隔某個(gè)增量 H 的元素構(gòu)成一個(gè)子序列 在排序過(guò)程中 逐次減小這個(gè)增量 最后當(dāng) H 減到 1 時(shí) 進(jìn)行一次插入排序 排序就完成 增量序列一般取 h n 2k k 1 2 log2n 其中 n 為待排序序列的長(zhǎng)度 其效率與增量序列有關(guān) 在最壞情況下 需要的比較次數(shù)為 O 三 選擇類(lèi)排序法 簡(jiǎn)單選擇排序法 基本思想 掃描整個(gè)線性表 從中選出最小的元素 將它交換到表的最前面 然后對(duì)剩下 的子表采用同樣的方法 直到子表空為止 簡(jiǎn)單選擇排序法在最壞情況下需要比較 n n 1 2 次 堆排序法 方法 1 首先將一個(gè)無(wú)序序列建成堆 2 然后將堆頂元素 序列中的最大項(xiàng) 與堆中最后一個(gè)元素交換 最大項(xiàng)應(yīng)該在序列的 最后 不考慮已經(jīng)換到最后的那個(gè)元素 只考慮前 n 1 個(gè)元素構(gòu)成的子序 顯然 該子序 列已不是堆 但左 右子樹(shù)仍為堆 可以將該子序列調(diào)事為堆 反復(fù)做第 2 步 真到剩 下的子序列為空為止 適用規(guī)模較大的線性表 在最壞情況下 堆排序需要比較的次數(shù)為 O nlog2n 1 7 查找技術(shù) 一 順序查找 順序查找又稱(chēng)順序搜索 順序查找一般是指在線性表中查找指定的元素 其基本方法如下 從線性表的第一個(gè)元素開(kāi)始 依次將線性表中的元素與被查元素進(jìn)行比較 若相等則表示 找到 即查找成功 若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等 則表示 線性表中沒(méi)有要找的元素 即查找失敗 順序查找的效率是很低的 以下兩種情況只能采用順序查找 如果線性表無(wú)序表 即表中元素的排列是無(wú)序的 則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu) 都只能用順序查找 即使是有序線性表 如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 也只能用順序查找 二 二分法查找 二分法查找只適用于存儲(chǔ)的有序表 在此所說(shuō)的有序表是指線性表的中元素按值非遞減排 列 即從小到大 但允許相鄰元素值相等 設(shè)有序線性表的長(zhǎng)度為 n 被查元素為 x 則對(duì)分查找的方法如下 將 x 與線性表的中間項(xiàng)進(jìn)行比較 若中間項(xiàng)的值等于 x 則說(shuō)明查到 查找結(jié)束 若 x 小于中間項(xiàng)的值 則在線性表的前半部分 即中間項(xiàng)以前的部分 以相同的方法進(jìn)行 查找 若 x 大于中間項(xiàng)的值 則在線性表的后半部分 即中間項(xiàng)以后的部分 以相同的方法進(jìn)行 查找 這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為 0 說(shuō)明線性表中沒(méi)有這個(gè)元素 為止 顯然 當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找 并且 二分查找的效率要比順序查 找高得多 可以證明 對(duì)于長(zhǎng)度為 n 的有序線性表 在最壞情況下 二分查找只需要比較 log2n 次 而順序查找需要比較 n 次 1 8 排序技術(shù) 一 交換類(lèi)排隊(duì)序法 所謂交換類(lèi)排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法 冒泡排序法與 快速排序法都屬于交換類(lèi)的排序方法 1 冒泡排序法 基本過(guò)程如下 首先 從表頭開(kāi)始往后掃描線性表 在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小 若相鄰 兩個(gè)元素中 前面的元素大于后面的元素 則將它們互換 稱(chēng)之為消去了一個(gè)逆序 放最 大值 然后 從后到前掃描剩下的線性表 同樣 在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小 若相鄰兩個(gè)元素中 后面的元素大于前面的元素 則將它們互換 這樣就又消去了一個(gè)逆 序 放最小值 重復(fù)上述過(guò)程 直到剩下的線性有變空為止 此時(shí)的線性表已經(jīng)變?yōu)橛行?假設(shè)線性表的長(zhǎng)為 n 則在最壞情況下 冒泡排序需要經(jīng)過(guò) n 2 遍的蔥馨往后的掃描和 n 2 遍的從后往前的掃描 需要的比較的次數(shù)為 n n 1 2 2 快速排序法 快速排序法也是種互換類(lèi)的排序法 但由于它比冒泡排序法的速度快 因此稱(chēng)之為快速排 序法 基本思想如下 從線性表中選取一個(gè)元素 設(shè) T 將線性表后面小于 T 的元素移到前 而前大于 T 的元素 移支后面 結(jié)果就將線性表分成了兩部分 稱(chēng)為兩個(gè)子表 T 插入到其分界線的位置處 這個(gè)過(guò)程稱(chēng)為線性表的分割 通過(guò)對(duì)線性表的一次分割 就以 T 為分界線 將線性表分成 了前后兩個(gè)子表 且前面子表中的所有元素均不大于 T 而后面子表中的所有元素均不小 于 T 如此反復(fù) 則此時(shí)的線性表就變成了有序表 步驟 首先 在表的第一個(gè) 中間一個(gè)與最后一個(gè)元素中選取中項(xiàng) 設(shè)為 P K 并將 P K 賦給 T 再將表中的第一個(gè)元素移到 P K 的位置上 然后設(shè)置兩個(gè)指針 i 和 j 分別指向表的起始與最后的位置 反復(fù)操作以下兩步 4 將 j 逐漸減小 并逐次比較 P j 與 T 直到發(fā)現(xiàn)一個(gè) P j T 為止 將 P i 移到 P j 位置上 上述兩個(gè)操作交替進(jìn)行 直到指針 i 與 j 指向同一個(gè)位置 即 i j 為止 此時(shí)將 P i 的位 置上 分割需要記憶 用棧來(lái)實(shí)現(xiàn) 二 插入類(lèi)排序法 1 簡(jiǎn)單插入排序法 所謂插入排序 是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中 一般來(lái)說(shuō) 假設(shè)線性中前 j 1 元素已經(jīng)有序 現(xiàn)在要將線性表中第 j 個(gè)元素插入到前面的有 序子表中 插入過(guò)程如下 道德將第 j 個(gè)元素放到一個(gè)變量 T 中 然后從有序子表的最后一個(gè)元素 即線性表中第 j 1 個(gè)元素 開(kāi)始 往前逐個(gè)與 T 進(jìn)行比較 將大于 T 的元素均依次向后移動(dòng)一個(gè)位置 直到 發(fā)現(xiàn)一個(gè)元素不大于 T 為止 此時(shí)就將 T 即原線性表中的第 j 個(gè)元素 插入到剛移出的 空位置上 有序子表的長(zhǎng)度就變?yōu)?j 了 效率與冒泡法相同 在最壞情況下 簡(jiǎn)單插入排序需要 n n 1 2 次比較 2 希爾排序法 基本思想如下 將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序 子序列的分割方法如下 將相隔某個(gè)增量 H 的元素構(gòu)成一個(gè)子序列 在排序過(guò)程中 逐次減小這個(gè)增量 最后當(dāng) H 減到 1 時(shí) 進(jìn)行一次插入排序 排序就完成 增量序列一般取 h n 2k k 1 2 log2n 其中 n 為待排序序列的長(zhǎng)度 其效率與增量序列有關(guān) 在最壞情況下 需要的比較次數(shù)為 O 三 選擇類(lèi)排序法 簡(jiǎn)單選擇排序法 基本思想 掃描整個(gè)線性表 從中選出最小的元素 將它交換到表的最前面 然后對(duì)剩下 的子表采用同樣的方法 直到子表空為止 簡(jiǎn)單選擇排序法在最壞情況下需要比較 n n 1 2 次 堆排序法 方法 1 首先將一個(gè)無(wú)序序列建成堆 2 然后將堆頂元素 序列中的最大項(xiàng) 與堆中最后一個(gè)元素交換 最大項(xiàng)應(yīng)該在序列的 最后 不考慮已經(jīng)換到最后的那個(gè)元素 只考慮前 n 1 個(gè)元素構(gòu)成的子序 顯然 該子序 列已不是堆 但左 右子樹(shù)仍為堆 可以將該子序列調(diào)事為堆 反復(fù)做第 2 步 真到剩 下的子序列為空為止 適用規(guī)模較大的線性表 在最壞情況下 堆排序需要比較的次數(shù)為 O nlog2n 習(xí)題一 一 選擇題 1 算法的時(shí)間復(fù)雜度是指 A 執(zhí)行算法程序所需要的時(shí)間 B 算法程序的長(zhǎng)度 C 算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D 算法程序中的指令條數(shù) 2 算法的窨復(fù)雜度是指 A 算法程序的長(zhǎng)度 B 算法程序中的指令條數(shù) C 算法程序所占的存儲(chǔ)空間 D 算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間 3 下列敘述中正確的是 A 線性表是線性結(jié)構(gòu) B 材與隊(duì)列是非線性結(jié)構(gòu) C 線性鏈表是非線性結(jié)構(gòu) D 二叉樹(shù)是線性結(jié)構(gòu) 4 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 A 數(shù)據(jù)所占的存儲(chǔ)空間量 B 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表 示 C 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D 存儲(chǔ)在外存中的數(shù)據(jù) 5 下列關(guān)于隊(duì)列的敘述中正確的是 A 在隊(duì)列中只能插入數(shù)據(jù) B 在隊(duì)列中只能刪除數(shù)據(jù) C 隊(duì)列是先進(jìn)先出的線性表 D 隊(duì)列是先進(jìn)后出的線性表 6 下列關(guān)于棧的敘述中正確的是 A 在棧中只能插入數(shù)據(jù) B 在棧中只能刪除數(shù)據(jù) C 棧是先進(jìn)先出的線性表 D 棧是先進(jìn)后出的線性表 7 設(shè)有下列二叉樹(shù) 對(duì)此二叉樹(shù)中序遍歷的結(jié)果為 A ABCDEF B DBEAFC C ABDECF D DEBFCA 8 在深度為 5 的滿二叉樹(shù)中 葉子結(jié)點(diǎn)的個(gè)數(shù)為 A 32 B 31 C 16 D 15 9 對(duì)長(zhǎng)度為 n 的線性表進(jìn)行順序查找 在最壞情況下所需要的比較次數(shù)為 A n 1 B n C n 1 2 D n 2 10 設(shè)樹(shù) T 的度為 4 其中度為 1 2 3 4 的結(jié)點(diǎn)個(gè)數(shù)分別為 4 2 1 1 則 T 中的葉 子結(jié)點(diǎn)數(shù)為 A 8 B 7 C 6 D 5 二 填空題 1 在長(zhǎng)度為 n 的有序線性表中進(jìn)行二分查找 需要的比較次數(shù)為 2 設(shè)一棵完全二叉共有 700 個(gè)結(jié)點(diǎn) 則在該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn) 3 設(shè)一棵二叉樹(shù)中序遍歷結(jié)果為 DBEAFC 前序遍歷結(jié)果為 ABDECF 則后序遍歷結(jié)果 為 4 在最壞情況下 冒泡排序的時(shí)間復(fù)雜度為 5 在一個(gè)容量為 15 的循環(huán)隊(duì)列中 若頭指針 front 6 尾指針 rear 9 則該循環(huán)隊(duì)列中共 有 個(gè)元 第 2 章 程序設(shè)計(jì)基礎(chǔ) 2 1 程序設(shè)計(jì)方法與風(fēng)格 就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言 主要經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階 段 一般來(lái)講 程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所表現(xiàn)出的特點(diǎn) 習(xí)慣和邏輯思路 程序是由人 來(lái)編寫(xiě)的 為了測(cè)試和維護(hù)程序 往往還要新聞?dòng)浾吆透櫝绦?因此程序設(shè)計(jì)的風(fēng)格總 體而言應(yīng)該強(qiáng)調(diào)得意和清晰 程序必須是可以理解的 要形成良好的程序設(shè)計(jì)風(fēng)格 主要應(yīng)注重和考慮下述一些因素 1 源程序文檔化 2 源程序文檔化應(yīng)考慮如下幾點(diǎn) 1 符號(hào)名的命名 符號(hào)名的命名應(yīng)具有一定的實(shí)際含義 以便于對(duì)程序功能的 理解 2 程序注釋 下克的注釋能夠幫助讀者理解程序 3 禮堂組織 為使程序的結(jié)構(gòu)一目了然 可以在程序中利用空格 空行 縮進(jìn) 待技巧使程序?qū)哟吻逦?2 數(shù)據(jù)說(shuō)明的方法 在編寫(xiě)程序時(shí) 需要注意數(shù)據(jù)說(shuō)明的風(fēng)格 以便使程序中的數(shù)據(jù)說(shuō)明更易于理解和維護(hù) 一般應(yīng)注意如下幾點(diǎn) 1 數(shù)據(jù)說(shuō)明的次序規(guī)范化鑒于程序理解 新聞?dòng)浾吆途S護(hù)的需要 使數(shù)據(jù)說(shuō)明 次序固定 可以使數(shù)據(jù)的發(fā)生容易查找 也有利于測(cè)試 排錯(cuò)和維護(hù) 2 說(shuō)明語(yǔ)句中變量安排有序化 當(dāng)一個(gè)說(shuō)明語(yǔ)句說(shuō)明多個(gè)變量時(shí) 變量按照字 母順序?yàn)楹?3 使用注釋來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu) 3 語(yǔ)句的結(jié)構(gòu) 程序應(yīng)該簡(jiǎn)單易懂 語(yǔ)句構(gòu)造應(yīng)該簡(jiǎn)單直接 不應(yīng)該為提高效率而把語(yǔ)句復(fù)雜化 一般應(yīng) 注意如下 1 在一行內(nèi)只寫(xiě)一條語(yǔ)句 2 程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性 3 除非對(duì)效率有特殊要求 程序編寫(xiě)要做清晰第一 效率第二 4 首先要保證程序正確 然后才要求提高速度 5 避免使用臨時(shí)變量而使程序的可讀性下降 6 避免不必要的轉(zhuǎn)移 7 盡可能使用庫(kù)函數(shù) 8 避免采用復(fù)雜的條件語(yǔ)句 9 盡量減少使用 否定 條件的條件語(yǔ)句 10 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化 11 要模塊化 使模塊功能盡可能單一化 12 利用住處隱蔽 確保每一個(gè)模塊的獨(dú)立性 13 從數(shù)據(jù)出發(fā)去構(gòu)造程序 14 不要修補(bǔ)不好的程序 要重新編寫(xiě) 4 輸入和輸出 無(wú)論是批處理的輸入和輸出方式 還是交互式的輸入和輸出方式 在設(shè)計(jì)和編程時(shí)都應(yīng)該 考慮如下原則 1 對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性 2 檢查輸入項(xiàng)的各種重要組合的合理性 3 輸入格式要簡(jiǎn)單 以使得輸入的步驟和操作盡可能簡(jiǎn)單 4 輸入數(shù)據(jù)時(shí) 應(yīng)允許使用自由格式 5 應(yīng)允許缺省值 6 輸入一批數(shù)據(jù)時(shí) 最好使用輸入結(jié)束標(biāo)志 7 在以交互式輸入 輸出方式進(jìn)行輸入時(shí) 要在屏幕上使用提示符明確提示輸 入的請(qǐng)求 同時(shí)在數(shù)據(jù)輸入過(guò)程中的輸入結(jié)束時(shí) 應(yīng)在屏幕上給出狀態(tài)信息 8 當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí) 應(yīng)保持輸入格式與輸入語(yǔ)句的一 致性 給所有的輸入出加注釋 并設(shè)計(jì)輸出報(bào)表格式 2 2 結(jié)構(gòu)化程序設(shè)計(jì) 一 結(jié)構(gòu)化程序設(shè)計(jì)的原則 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下 逐步求精 模塊化 限制使用 goto 語(yǔ)句 1 自頂向下 程序設(shè)計(jì)時(shí) 應(yīng)先考慮總體 后考慮細(xì)節(jié) 先考慮全局目標(biāo) 后考 慮局部目標(biāo) 不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié) 先從最上層總目標(biāo)開(kāi)始設(shè)計(jì) 逐步使問(wèn) 題具體化 2 逐步求精 對(duì)復(fù)雜問(wèn)題 應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡 逐步細(xì)化 3 模塊化 一個(gè)復(fù)雜問(wèn)題 肯定是由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成 模塊化是把程序要 解決的總目標(biāo)分解為分目標(biāo) 再進(jìn)一步分解為具體的小目標(biāo) 把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊 4 限制使用 goto 語(yǔ)句 使用 goto 語(yǔ)句經(jīng)實(shí)驗(yàn)證實(shí) 1 濫用 GOTO 語(yǔ)句確實(shí)有害 應(yīng)晝避免 2 完全避免使用 GOTO 語(yǔ)句也并非是個(gè)明智的方法 有些地方使用 GOTO 語(yǔ)句 會(huì)使 程序流程更清楚 效率更高 3 爭(zhēng)論的焦點(diǎn)不應(yīng)該放在是否取消 GOTO 語(yǔ)句 而應(yīng)該放在用什么樣的程序結(jié)構(gòu)上 其中最關(guān)鍵的是 肯定以提高程序清晰性為目標(biāo)的結(jié)構(gòu)化方法 二 結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn) 1 順序結(jié)構(gòu) 順序結(jié)構(gòu)是簡(jiǎn)單的程序設(shè)計(jì) 它是最基本 最常用的結(jié)構(gòu) 所謂順序執(zhí)行 就是按照程序語(yǔ)句行的自然順序 一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序程序 2 選擇結(jié)構(gòu) 選擇結(jié)構(gòu)又稱(chēng)為分支結(jié)構(gòu) 它包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu) 這種結(jié)構(gòu)可 以根據(jù)設(shè)定的條件 判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列 3 重復(fù)結(jié)構(gòu) 重復(fù)結(jié)構(gòu)又稱(chēng)為循環(huán)結(jié)構(gòu) 它根據(jù)給定的條件 判斷是否需要重復(fù)執(zhí)行某一 相同的或類(lèi)似的程序段 利用重復(fù)結(jié)構(gòu)可簡(jiǎn)化大量的程序行 分為兩類(lèi) 一是先判斷后執(zhí) 行 一是先執(zhí)行后判斷 優(yōu)點(diǎn) 一是程序易于理解 使用和維護(hù) 二是編程工作的效率 降低軟件開(kāi)發(fā)成本 三 結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用 要注意把握如下要素 1 使用程序設(shè)計(jì)語(yǔ)言中的順序 選擇 循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏 輯 2 選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口 3 程序語(yǔ)句組成容易識(shí)別的塊 每塊只有一個(gè)入口和一個(gè)出口 4 復(fù)雜結(jié)構(gòu)應(yīng)該嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn) 5 語(yǔ)言中所沒(méi)有的控制結(jié)構(gòu) 應(yīng)該采用前后一致的方法來(lái)模擬 6 嚴(yán)格控制 GOTO 語(yǔ)句的使用 其意思是指 1 用一個(gè)非結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言去實(shí)現(xiàn)一個(gè)結(jié)構(gòu)化的構(gòu)造 2 若不使用 GOTO 語(yǔ)句會(huì)使功能模糊 3 在某種可以改善而不損害程序可讀性的情況下 2 3 面向?qū)ο蟮某绦蛟O(shè)計(jì) 一 關(guān)于面向?qū)ο蠓椒?面向?qū)ο蠓椒ǖ谋举|(zhì) 就是主張從客觀世界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng) 提倡用人類(lèi)在現(xiàn) 實(shí)生活中常用的思維方法來(lái)認(rèn)識(shí) 理解和描述客觀事物 強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn) 題域 也就是說(shuō) 系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)地反映問(wèn)題域中固有事物及 其關(guān)系 優(yōu)點(diǎn) 1 與人類(lèi)習(xí)慣的思維方法一致 面向?qū)ο蠓椒ê图夹g(shù)以對(duì)象為核心 對(duì)象是由數(shù)據(jù)和容許的操作組成的封裝體 與客觀實(shí) 體有直接的關(guān)系 對(duì)象之間通過(guò)傳遞消息互相聯(lián)系 以模擬現(xiàn)實(shí)世界中不同事物彼此之間 的聯(lián)系 面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向過(guò)程的方法有本質(zhì)不同 這種方法的基本原理是 使用 現(xiàn)實(shí)世界的概念抽象地思考問(wèn)題從而自然地解決問(wèn)題 它強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不 強(qiáng)調(diào)算法 它鼓勵(lì)開(kāi)發(fā)者在軟件開(kāi)發(fā)的絕大部分過(guò)程中都用應(yīng)用領(lǐng)域的要領(lǐng)去思考 2 穩(wěn)定性好 3 可重用性好 軟件重用是指在不同的軟件開(kāi)發(fā)過(guò)程中重復(fù)作用相同或相似軟件元素的過(guò)程 重用是提高 軟件生產(chǎn)率的最主要的方法 4 易于開(kāi)發(fā)大型軟件產(chǎn)品 5 可維護(hù)性好 1 用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件穩(wěn)定性比較好 2 用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件比較容易修改 3 用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件比較容易理解 4 易于測(cè)試和調(diào)試 二 面向?qū)ο蠓椒ǖ幕靖拍?1 對(duì)象 object 對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?對(duì)象可以用來(lái)表示客觀世界中的任何實(shí)體 也就是 說(shuō) 應(yīng)用領(lǐng)域中有意義的 與所要解決的問(wèn)題有關(guān)系的任何事物都可以作為對(duì)象 它既可 以是具體的物理實(shí)體的抽象 也可以是人為的概念 或者是任何有明確邊界的意義的東西 總之 對(duì)象是對(duì)問(wèn)題域中某個(gè)實(shí)體的抽象 設(shè)立某個(gè)對(duì)象就反映軟件系統(tǒng)保存有關(guān)它的信 息并具有與它進(jìn)行交互的能力 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體 是構(gòu)成系 統(tǒng)的一個(gè)基本單位 它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成 對(duì)象可以做的操作表示它的動(dòng)態(tài)行為 在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)中 通常把對(duì)象的 操作也稱(chēng)為方法或服務(wù) 屬性即對(duì)象所包含的信息 它在設(shè)計(jì)對(duì)象時(shí)確定 一般只能通過(guò)掛靠對(duì)象的操作來(lái)改變 操作描述了對(duì)象執(zhí)行的功能 若通過(guò)消息傳遞 還可以為其他對(duì)象使用 操作的過(guò)程對(duì)外 是封閉的 即用戶只能看到這一操作實(shí)施后的結(jié)果 這相當(dāng)于事先已經(jīng)設(shè)計(jì)好的各種過(guò)程 只需要調(diào)用就可以了 用戶不必去關(guān)心這一過(guò)程是如何編寫(xiě)的 事實(shí)上 這個(gè)過(guò)程已經(jīng)封 裝在對(duì)象中 用戶也看不到 對(duì)的這一特性即是對(duì)象的封裝性 對(duì)象有如下一些基本特點(diǎn) 1 標(biāo)識(shí)惟一性 指對(duì)象是可區(qū)分的 并且由對(duì)象有的內(nèi)在本質(zhì)來(lái)區(qū)分 而不是 通過(guò)描述來(lái)區(qū)分 2 分類(lèi)性 指可以將具有相同屬性的操作的對(duì)象抽象成類(lèi) 3 多太性 指同一個(gè)操作可以是不同對(duì)象的行為 4 封裝性 從外面看只能看到對(duì)象的外部特性 即只需知道數(shù)據(jù)的取值范圍和 可以對(duì)該數(shù)據(jù)施加的操作 根本無(wú)需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法 對(duì)象的內(nèi) 部 即處理能力的實(shí)行和內(nèi)部狀態(tài) 對(duì)外是不可見(jiàn)的 從外面不能直接使用對(duì)象的處理能 力 也不能直接修改其內(nèi)部狀態(tài) 對(duì)象的內(nèi)部狀態(tài)只能由其自身改變 5 模塊獨(dú)立性好 對(duì)象是面向?qū)ο蟮能浖幕灸K 它是由數(shù)據(jù)及可以對(duì)這 些數(shù)據(jù)施加的操作所組成的統(tǒng)一體 而且對(duì)象是以數(shù)據(jù)為中心的 操作圍繞對(duì)其數(shù)據(jù)所需 做的處理來(lái)設(shè)置 沒(méi)有無(wú)關(guān)的操作從模塊的獨(dú)立性考慮 對(duì)象內(nèi)部各種元素彼此結(jié)合得很 緊密 內(nèi)聚性強(qiáng) 2 類(lèi) Class 和實(shí)例 Instance 將屬性 操作相似的對(duì)象歸為類(lèi) 也就是說(shuō) 類(lèi)是具有共同屬性 共同方法的對(duì)象的集合 所以 類(lèi)是對(duì)象的抽象 它描述了屬于該對(duì)象類(lèi)型的所有對(duì)象的性質(zhì) 而一個(gè)對(duì)象則是其 對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例 要注意的是 當(dāng)使用 對(duì)象 這個(gè)術(shù)語(yǔ)時(shí) 既可以指一個(gè)具體的對(duì)象 也可以泛指一般的對(duì) 象 但是 當(dāng)使用 實(shí)例 這個(gè)術(shù)語(yǔ)時(shí) 必然是指一個(gè)具體的對(duì)象 例如 Integer 是一個(gè)整數(shù)類(lèi) 它描述了所有整數(shù)的性質(zhì) 因此任何整數(shù)都是整數(shù)類(lèi)的對(duì)象 而一個(gè)具體的整數(shù) 123 是類(lèi) Integer 的實(shí)例 由類(lèi)的定義可知 類(lèi)是關(guān)于對(duì)象性質(zhì)的描述 它同對(duì)象一樣 包括一組數(shù)據(jù)屬性和在數(shù)據(jù) 上的一組合法操作 3 消息 Message 面向?qū)ο蟮氖澜缡峭ㄟ^(guò)對(duì)象與對(duì)象間彼此的相互合作來(lái)推動(dòng)的 對(duì)象間的這種相互合作需 要一個(gè)機(jī)制協(xié)助進(jìn)行 這樣的機(jī)制稱(chēng)為 消息 消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞信 息 它請(qǐng)示對(duì)象執(zhí)行某一處理或回答某一要求的信息 它統(tǒng)一了數(shù)據(jù)流的控制流 消息的 使用類(lèi)似于函數(shù)調(diào)用 消息中指定了某一個(gè)實(shí)例 一個(gè)操作名和一個(gè)參數(shù)表 可空 接收 消息的實(shí)例執(zhí)行消息中指定的操作 并將形式參數(shù)數(shù)與參數(shù)表中相應(yīng)的值結(jié)合起來(lái) 消息 傳遞過(guò)程中 由發(fā)送消息的對(duì)象 發(fā)送對(duì)象 的觸發(fā)操作產(chǎn)生輸出結(jié)果 作為消息傳送至 接受消息的對(duì)象 接受對(duì)象 引發(fā)接受消息的對(duì)象一系列的操作 所傳送的消息實(shí)質(zhì)上是 接受對(duì)象所具有的操作 方法名稱(chēng) 有時(shí)還包括相應(yīng)參數(shù) 消息中只包含傳遞者的要求 它告訴接受者需要做哪些處理 但并不指示接受者應(yīng)該怎樣 完成這些處理 消息完全由接受者解釋 接受者獨(dú)立決定采用什么方式完成所需的處理 發(fā)送者對(duì)接受者不起任何控制作用 一個(gè)對(duì)象能夠接受不同形式 不同內(nèi)容的多個(gè)消息 相同形式的消息可以送往不同的對(duì)象 不同的對(duì)象對(duì)于形式相同的消息可以有不同的解釋 能夠做出不同的反映 一個(gè)對(duì)象可以同時(shí)往多個(gè)對(duì)象傳遞信息 兩個(gè)對(duì)象也可以同時(shí)向某 個(gè)對(duì)象傳遞消息 例如 一個(gè)汽車(chē)對(duì)象具有 行駛 這項(xiàng)操作 那么要讓汽車(chē)以時(shí)速 50 公里行駛的話 需傳遞 給汽車(chē)對(duì)象 行駛 及 時(shí)速 50 公里 的消息 通常 一個(gè)消息由下述三部分組成 1 接收消息的對(duì)象的名稱(chēng) 2 消息標(biāo)識(shí)符 也稱(chēng)為消息名 3 零個(gè)或多個(gè)參數(shù) 4 繼承 Inheritance 繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特征 繼承是使用己有的類(lèi)定義作為基礎(chǔ)建立新類(lèi)的定 義技術(shù) 已有的類(lèi)可當(dāng)作基類(lèi)來(lái)引用 則新類(lèi)相應(yīng)地可當(dāng)作派生類(lèi)來(lái)引用 廣義地說(shuō) 繼承是指能夠直接獲得已有的性質(zhì)和特征 而不必重復(fù)定義它們 面向?qū)ο筌浖夹g(shù)的許多強(qiáng)有力的功能和突出的優(yōu)點(diǎn) 都來(lái)源于把類(lèi)組成一個(gè)層次結(jié)構(gòu)的 系統(tǒng) 一個(gè)類(lèi)的上層可以有父類(lèi) 下層可以有子類(lèi) 這種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是 繼承性 一個(gè)類(lèi)直接繼承其父類(lèi)的描述 數(shù)據(jù)和操作 或特性 子類(lèi)自動(dòng)地共享基類(lèi)中定 義的數(shù)據(jù)和方法 繼承具有傳遞性 如果類(lèi) C 繼承類(lèi) B 類(lèi) B 繼承類(lèi) A 則類(lèi) C 繼承類(lèi) A 因此一個(gè)類(lèi)實(shí)際 上繼承了它上層的全部基類(lèi)的特性 也就是說(shuō) 屬于某類(lèi)的對(duì)象除了具有該類(lèi)所定義的特 性外 還具有該類(lèi)上層全部基類(lèi)定義的特性 繼承分為單繼承與多重繼承 單繼承是指 一個(gè)類(lèi)只允許有一個(gè)父類(lèi) 即類(lèi)等級(jí)為樹(shù)形結(jié) 構(gòu) 多重繼承是指 一個(gè)類(lèi)允許有多個(gè)父類(lèi) 多重繼承的類(lèi)可以組合多個(gè)父類(lèi)的性質(zhì)構(gòu)成 所需要的性質(zhì) 因此 功能更強(qiáng) 使用更方便 便是 使用多重繼承時(shí)要注意避免二義性 繼承性的優(yōu)點(diǎn)是 相似的對(duì)象可以共享程序代碼和數(shù)據(jù)結(jié)構(gòu) 從而大大減少了程序中的冗 余信息 提高軟件的可重用性 便于軟件個(gè)性維護(hù) 此外 繼承性便利用戶在開(kāi)發(fā)新的應(yīng) 用系統(tǒng)時(shí)不必完全從零開(kāi)始 可以繼承原有的相似系統(tǒng)的功能或者從類(lèi)庫(kù)中選取需要的類(lèi) 再派生出新的類(lèi)以實(shí)現(xiàn)所需要的功能 5 多太性 Polymorphism 對(duì)象根據(jù)所接受 的消息而做出動(dòng)作 同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行 動(dòng) 該現(xiàn)象稱(chēng)為多態(tài)性 在面向?qū)ο蟮能浖夹g(shù)中 多態(tài)性是指類(lèi)對(duì)象可以像父類(lèi)對(duì)象那 樣使用 同樣的消息既可以發(fā)送給父類(lèi)對(duì)象也可以發(fā)送給子類(lèi)對(duì)象 多態(tài)性機(jī)制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性 進(jìn)一步減少了信息冗余 而且顯著地 提高了軟件的可重用性和可擴(kuò)充性 當(dāng)擴(kuò)充系統(tǒng)功能增加新的實(shí)體類(lèi)型時(shí) 只需派生出與 新實(shí)體類(lèi)相應(yīng)的新的子類(lèi) 完全無(wú)需修改原有的程序代碼 甚至不需要重新編譯原有的程 序 利用多態(tài)性 用戶能夠發(fā)送一般形式的消息 而將所有的實(shí)現(xiàn)細(xì)節(jié)都留給接受消息的 對(duì)象 第 3 章 軟件工程基礎(chǔ) 3 1 軟件工程基本概念 一 軟件定義與軟件特點(diǎn) 計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分 是包括程序 數(shù)據(jù)及相關(guān)文檔的 完整集合 基中 程序是軟件開(kāi)發(fā)人員根據(jù)用戶需求開(kāi)發(fā)的用程序設(shè)計(jì)語(yǔ)言描述的 適合 計(jì)算機(jī)執(zhí)行的指令 語(yǔ)句 序列 數(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)的文檔 國(guó)標(biāo) GB 中對(duì)計(jì)算機(jī)軟件的定義為 與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序 規(guī)程 規(guī) 則 以及可能有的文件 文檔及數(shù)據(jù) 軟件在開(kāi)發(fā) 生產(chǎn) 維護(hù)和使用等方面與計(jì)算機(jī)硬件相比存在明顯的差異 深入理解軟件 的定義需要了解軟件的特點(diǎn) 1 軟件是一種邏輯實(shí)體 而不是物理實(shí)體具有抽象性 2 軟件的生產(chǎn)與硬件不同 它沒(méi)有明顯的制作過(guò)程 一旦研制開(kāi)發(fā)成功 可以 大量拷貝同一內(nèi)容的副本 所以對(duì)軟件的控制 必須著重在軟件開(kāi)發(fā)方面下功夫 3 軟件在運(yùn)行 使用期間不存在磨損 老化問(wèn)題 4 軟件的開(kāi)發(fā)運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性 受計(jì)算機(jī)系統(tǒng)的限制這導(dǎo)致了軟 件移植的問(wèn)題 5 軟件復(fù)雜性高 成本昂貴 6 軟件開(kāi)發(fā)涉及諸多的社會(huì)因素 軟件按功能可以分為 應(yīng)用軟件 系統(tǒng)軟件 支撐軟件 或工具軟件 應(yīng)用軟件是為解決 特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件 系統(tǒng)軟件是計(jì)算機(jī)管理自身資源 提高計(jì)算機(jī)使用效率并 為計(jì)算機(jī)用戶提供各種服務(wù)的軟件 支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟件之間 協(xié)助用戶 開(kāi)發(fā)軟件的工具性軟件 包括輔助和支持開(kāi)發(fā)和維護(hù)應(yīng)用軟件的工具軟件 二 軟件危機(jī)與軟件工程 軟件工程概念的出現(xiàn)源自軟件危機(jī) 所謂有軟件危機(jī)四伏是泛指在計(jì)算機(jī)軟件開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的嚴(yán)重問(wèn)題 實(shí)際上 幾科所有的軟件都不同程度地存在這些問(wèn)題 隨著計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)用領(lǐng)域的擴(kuò)大 計(jì)算機(jī)硬件性能 價(jià)格比和質(zhì)量穩(wěn)步提高 軟件 規(guī)模越來(lái)越大 復(fù)雜程度不斷增加 軟件成本逐年上升 質(zhì)量沒(méi)有可靠的保證 軟件已成 為計(jì)算機(jī)科學(xué)發(fā)展的 瓶頸 具體地說(shuō) 在軟件開(kāi)發(fā)和維護(hù)過(guò)程中 軟件危機(jī)主要表現(xiàn)在 1 軟件需求的增長(zhǎng)得不到滿足 用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生 2 軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制 開(kāi)發(fā)成本超出預(yù)算 開(kāi)發(fā)周期大大超過(guò)規(guī)定 日期的情況經(jīng)常發(fā)生 3 軟件質(zhì)量難以保證 4 軟件不可維護(hù)或護(hù)程度非常低 5 軟件的成本不斷提高 6 軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng) 總之 可以將軟件危機(jī)歸結(jié)為成本 質(zhì)量 生產(chǎn)率等問(wèn)題 軟件工程就是試圖用工程 科學(xué)和數(shù)學(xué)的大批量與方法研制 維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù) 及管理方法 關(guān)于軟件工程的定義 國(guó)標(biāo) GB 中指出 軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義 開(kāi)發(fā)和 維護(hù)的一整套方法 工具文檔 實(shí)踐標(biāo)準(zhǔn)的工序 1993 年 IEEE Institute of Electrical Electronic Engineers 電氣和電子工程師學(xué)會(huì) 給出了 一個(gè)更加綜合的定義 將系統(tǒng)化的 規(guī)范的 可度量的方法應(yīng)用于軟件的開(kāi)發(fā) 運(yùn)行和維 護(hù)的過(guò)程 即將工程化應(yīng)用于軟件中 軟件工程包括 3 個(gè)要素 即方法 工具和過(guò)程 方法是完成軟件工程項(xiàng)目的技術(shù)手段 工 具支持軟件的開(kāi)發(fā) 管理 文檔生成 過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制 管理 軟件工程的核心思想是把軟件產(chǎn)品看作是一個(gè)工程產(chǎn)品來(lái)處理 開(kāi)發(fā)軟件不能只考慮開(kāi)發(fā)期間的費(fèi)用 而且應(yīng)考慮軟件生命周期內(nèi)的全部費(fèi)用 因此 軟 件生命周期的概念就變得特別重要 在考慮軟件費(fèi)用時(shí) 不僅僅要降低開(kāi)發(fā)成本 更要降 低整個(gè)軟件生命周期的總成本 三 軟件工程過(guò)程與軟件生命周期 1 軟件工程過(guò)程 Software Engineering Process ISO9000 定義 軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng) 定義支持了軟件工程過(guò)程的兩方面內(nèi)涵 其一 軟件工程過(guò)程是指為獲得軟件產(chǎn)品 在軟 件工具支持下由軟件工程師完成的一系列軟件工程活動(dòng) 基于這個(gè)方面 軟件工程過(guò)程通 常包含 4 種基本活動(dòng) 1 P plan 軟件規(guī)格說(shuō)明 規(guī)定軟件的功能及其運(yùn)行時(shí)的限制 2 D do 軟件開(kāi)發(fā) 產(chǎn)生滿足規(guī)格說(shuō)明的軟件 3 C check 軟件確認(rèn) 確認(rèn)軟件能夠滿足客戶提出的要求 4 A action 軟件演進(jìn) 為滿足客戶的變更要求 軟件必須在使用的過(guò)程 中演進(jìn) 通常把用戶的要求轉(zhuǎn)變成軟件產(chǎn)品的過(guò)程也叫做軟件開(kāi)發(fā)過(guò)程 此過(guò)程包括對(duì)用戶的要求 進(jìn)行分析 解釋成軟件需求 把需求變換成設(shè)計(jì) 把設(shè)計(jì)用代碼來(lái)實(shí)現(xiàn)并進(jìn)行代碼測(cè)試 有些軟件還需要進(jìn)行代碼安裝和交付運(yùn)行 其二 從軟件開(kāi)發(fā)的觀點(diǎn)看 它就是使用適當(dāng)?shù)馁Y源 包括人員 硬軟件工具 時(shí)間等 為開(kāi)發(fā)軟件進(jìn)行的一組開(kāi)發(fā)活動(dòng) 在過(guò)程結(jié)束時(shí)將輸入 用戶要求 轉(zhuǎn)化為輸出 軟件產(chǎn) 品 所以 軟件工程的過(guò)程是將軟件工程的方法和工具綜合起來(lái) 以達(dá)到合理 及時(shí)地進(jìn)行計(jì) 算機(jī)軟件開(kāi)發(fā)的目的 軟件工程過(guò)程應(yīng)確定方法使用的順序 要求交付的文檔資料 為保 證質(zhì)量和適應(yīng)變化所需要的管理 軟件開(kāi)發(fā)各個(gè)階段完成的任務(wù) 2 軟件生命周期 software life cycle 通常 將軟件產(chǎn)品從提出 實(shí)現(xiàn) 使用維護(hù)到停止使用退役的過(guò)程稱(chēng)為軟件生命周期 一 般包括可行性研究與需求分析 設(shè)計(jì) 實(shí)現(xiàn) 測(cè)試 交付使用以及維護(hù)等活動(dòng) 還可以將軟件生命周期分為軟件定義 軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段 軟件生命周期 的主要活動(dòng)階段是 1 可行性研究與計(jì)劃制定 確定待開(kāi)發(fā)軟件系統(tǒng)的開(kāi)發(fā)目標(biāo)和總的要求 給出 它的功能 性能 可靠性以及接口等方面的可能方案 制定完成開(kāi)發(fā)任務(wù)的實(shí)施計(jì)劃 2 需求分析 對(duì)待開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義 編寫(xiě)軟件規(guī) 格說(shuō)明書(shū)及初步的用戶手冊(cè) 提交評(píng)審 3 軟件設(shè)計(jì) 系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員應(yīng)該在反復(fù)理解軟件需求的基礎(chǔ)上 給出軟件的結(jié)構(gòu) 模塊和劃分 功能的分配及處理流程 在系統(tǒng)比軟件復(fù)雜的情況下 設(shè) 計(jì)階段可分解成概要設(shè)計(jì)階段和詳細(xì)設(shè)計(jì)階段 編寫(xiě)概要設(shè)計(jì)說(shuō)明書(shū) 詳細(xì)設(shè)計(jì)說(shuō)明書(shū)和 測(cè)試計(jì)劃初稿 提交評(píng)審 4 軟件實(shí)現(xiàn) 把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼 即完成源程序的 編碼 編寫(xiě)用戶手冊(cè) 操作手冊(cè)等面向用戶的文檔 編寫(xiě)單元測(cè)試計(jì)劃 5 軟件測(cè)試 在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上 檢驗(yàn)軟件的各個(gè)組成部分 編寫(xiě)測(cè)試 分析報(bào)告 6 運(yùn)行和維護(hù) 將已交付的軟件投入運(yùn)行 并在運(yùn)行使用中不斷地維護(hù) 根據(jù) 新進(jìn)出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改 四 軟件工程的目標(biāo)與原則 1 軟件工程的目標(biāo) 軟件工程的目標(biāo)是 在給定成本 進(jìn)度的前提下 開(kāi)發(fā)出具有有效性 可靠性 可理解性 可維護(hù)性 可重用性 可適應(yīng)性 可移植性 可追蹤性和可互操作性且滿足用戶需求的產(chǎn) 品 軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是 付出較低的開(kāi)發(fā)成本 達(dá)到要求的軟件功能 取得較 好的軟件性能 開(kāi)發(fā)的軟件易于移植 需要較低的維護(hù)費(fèi)用 能按時(shí)完成開(kāi)發(fā) 及時(shí)交付 使用 基于軟件工程的目標(biāo) 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括 軟件開(kāi)發(fā)技術(shù)和軟 件工程管理 1 軟件開(kāi)發(fā)技術(shù) 軟件開(kāi)發(fā)技術(shù)包括 軟件開(kāi)發(fā)法學(xué) 開(kāi)發(fā)過(guò)程 開(kāi)發(fā)工具和軟件工程環(huán)境 其主體內(nèi)容是 軟件開(kāi)發(fā)方法學(xué) 軟件開(kāi)發(fā)方法學(xué)是根據(jù)不同的軟件類(lèi)型 按不同的觀點(diǎn)和原則 對(duì)軟件 開(kāi)發(fā)中應(yīng)遵循的策略 原則 步驟和必須產(chǎn)生的文檔資料都做出規(guī)定 從而使軟件的開(kāi)發(fā) 能夠進(jìn)入規(guī)范化和工程化的階段 以克服早期的手工方法生產(chǎn)中的隨意性和非規(guī)范性做法 2 軟件工程管理 軟件工程管理包括 軟件管理學(xué) 軟件工程經(jīng)濟(jì)學(xué) 軟件心理學(xué)等內(nèi)容 軟件工程管理是軟件按工程化生產(chǎn)時(shí)的重要環(huán)節(jié) 它要求按照預(yù)選制定的計(jì)劃 進(jìn)度和預(yù) 算執(zhí)行 以實(shí)現(xiàn)預(yù)期的經(jīng)濟(jì)效益和社會(huì)效益 軟件工程經(jīng)濟(jì)學(xué)是研究軟件開(kāi)發(fā)中成本的估算 成本效益分析的方法和技術(shù) 用經(jīng)濟(jì)學(xué)的 基本原理來(lái)研究軟件工程開(kāi)發(fā)中的經(jīng)濟(jì)效益問(wèn)題 軟件心理學(xué)是軟件工程領(lǐng)域具有挑戰(zhàn)性的一個(gè)全新的研究視角 它是從個(gè)體心理 人類(lèi)行 為 組織行為和企業(yè)文化等角度來(lái)研究軟件管理和軟件工程的 2 軟件工程的原則 為了達(dá)到上述的軟件工程目標(biāo) 在軟件開(kāi)發(fā)過(guò)程中 必須遵循軟件工程的基本原則 這些 基本原則包括抽象 信息隱蔽 模塊化 局部化 確定性 一致性 完備性和可驗(yàn)證性 1 抽象 抽取事物最基本的特性和行為 忽略非本質(zhì)細(xì)節(jié) 采用分層次抽象 自頂向下 逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性 2 信息隱蔽 采用封閉技術(shù)