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