二級公共基礎(chǔ)知識(基本版).ppt

全國計算機等級考試 二級公共基礎(chǔ)知識 第一章數(shù)據(jù)結(jié)構(gòu)與算法 30 考試大綱1 算法的基本概念 算法復(fù)雜度的概念和意義 時間復(fù)雜度與空間復(fù)雜度 2 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的圖形表示 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念 3 線性表的定義 線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算 4 棧和隊列的定義 棧和隊列的順序存儲結(jié)構(gòu)及其基本運算 5 線性單鏈表 雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算 6 樹的基本概念 二叉樹的定義及其存儲結(jié)構(gòu) 二叉樹的前序 中序和后序遍歷 7 順序查找與二分法查找算法 基本排序算法 交換類排序 選擇類排序 插入類排序 知識點歸納 算法的基本概念所謂算法是指解題方案的準確而完整的描述 嚴格來說 一個算法必須具有以下五個主要特征 有窮性確定性可行性輸入輸出綜上 所謂算法 是一組嚴格定義運算順序的規(guī)則 而且每一個規(guī)則都是有效且明確的 此順序?qū)⒃谟邢薜拇螖?shù)終止 算法的基本概念 算法的組成要素算法中對數(shù)據(jù)的運算和操作算法的控制結(jié)構(gòu)算法設(shè)計基本方法列舉法歸納法遞推遞歸減半遞推回溯法 算法的復(fù)雜度 算法的復(fù)雜度可分為時間復(fù)雜度和空間復(fù)雜度 是衡量算法優(yōu)劣的量度 1 算法的時間復(fù)雜度算法的時間復(fù)雜度是指執(zhí)行算法所需要的工作量 一般情況下 算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f n 算法的時間量度記作 T n O f n 表示隨問題規(guī)模n的增大 算法執(zhí)行時間的增長率和f n 的增長率相同 稱為算法的 漸進 時間復(fù)雜度 算法的復(fù)雜度 何估算算法的時間復(fù)雜度 任何一個算法都是由一個 控制結(jié)構(gòu) 和若干 原操作 組成的 因此一個算法的執(zhí)行時間可以看成是所有原操作的執(zhí)行時間之和 原操作 i 的執(zhí)行次數(shù) 原操作 i 的執(zhí)行時間 則算法的執(zhí)行時間與所有原操作的執(zhí)行次數(shù)之和成正比 從算法中選取一種對于所研究的問題來說是基本操作的原操作 以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法時間復(fù)雜度的依據(jù) 這種衡量效率的辦法所得出的不是時間量 而是一種增長趨勢的量度 它與軟硬件環(huán)境無關(guān) 只暴露算法本身執(zhí)行效率的優(yōu)劣 算法的復(fù)雜度 算法的空間復(fù)雜度算法的空間負雜度是指執(zhí)行這個算法所需要的內(nèi)存空間 空間復(fù)雜度作為算法所需存儲空間的量度 記作 S n O g n 其中n為問題的規(guī)模 表示隨問題規(guī)模的增大 算法運行所需存儲量的增長率與g n 的增長率相同 數(shù)據(jù)結(jié)構(gòu) 利用計算機進行數(shù)據(jù)處理是計算機應(yīng)用的一個重要領(lǐng)域 數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題 數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系 即數(shù)據(jù)的邏輯結(jié)構(gòu) 在對數(shù)據(jù)進行處理時 各數(shù)據(jù)元素在計算機中的存儲關(guān)系 即數(shù)據(jù)的存儲結(jié)構(gòu) 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述 它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示 與數(shù)據(jù)在計算機中的存儲位置無關(guān) 是獨立于計算機的 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的表示 存儲結(jié)構(gòu)的主要內(nèi)容是指在存儲空間中使用一個存儲結(jié)點來存儲一個數(shù)據(jù)元素 在存儲空間中建立各存儲結(jié)點之間的關(guān)聯(lián) 來表示數(shù)據(jù)元素之間的邏輯關(guān)系 常見的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 線性結(jié)構(gòu)在數(shù)據(jù)元素的非空有限集合中 線性結(jié)構(gòu)的邏輯特征如下 存在一個唯一的被稱為 第一個 的數(shù)據(jù)元素存在一個唯一的被稱為 最后一個 的數(shù)據(jù)元素除第一個之外 集合中的每個數(shù)據(jù)元素均有且只有一個直接前驅(qū)除最后一個之外 集合中的每個數(shù)據(jù)元素均有且只有一個直接后繼非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是 一個結(jié)點可能有多個直接前驅(qū)和直接后繼 樹和圖都屬于非線性結(jié)構(gòu) 線性表 通常以下列n個數(shù)據(jù)元素的序列 表示線性表 a1 a2 ai an 序列中數(shù)據(jù)元素的個數(shù)n定義為線性表的表長 n 0時的線性表被稱為空表 稱i為ai在線性表中的位序 線性表的順序存儲 線性表的順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素 即以 存儲位置相鄰 表示 位序相繼的兩個數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系 并以表中第一個元素的存儲位置作為線性表的起始地址 稱作線性表的基地址 所有數(shù)據(jù)元素的存儲位置均可由第一個數(shù)據(jù)元素的存儲位置得到ADR ai ADR a1 i 1 C 基地址一個數(shù)據(jù)元素所占存儲量 線性表的插入和刪除運算 插入運算是指在線性表的某個指定位置增加一個新結(jié)點 一般情況下 要在第i 1 i n 個元素之前插入一個新元素時 首先要從最后一個元素開始 直到第i個元素之間共n i 1個元素依次向后移動一個位置 然后將新元素插入到第i項 刪除運算是指撤銷結(jié)構(gòu)中的某個結(jié)點 一般情況 要刪除第i 1 i n 個元素 要從第i 1個元素開始 直到第n個元素 共n i個元素依次向前移動一個位置 棧 棧是限定僅在表的一端進行插入和刪除操作的線性表 允許插入和刪除的一端稱為棧頂 另一端稱為棧底 棧頂元素總是最后被插入的元素 從而也是最先被刪除的元素 棧底元素總是最先被插入 也是最后被刪除的元素 因此 棧是一種后進先出的線性表 通常用指針top指示棧頂位置 用指針bottom指示棧底位置 棧的順序存儲及運算 用一維數(shù)組S 1 m 作為棧的順序存儲空間 m為棧的最大容量 top 0表示棧為空 top m表示棧滿 棧的操作入棧 在棧頂位置插入一個新元素 棧頂指針top加1 退棧 取出棧頂元素并賦值給一個指定的變量 棧頂指針top減1 取棧頂元素 將棧頂元素的值賦給一個指定的變量 不刪除棧頂元素 棧頂指針不變 棧 如果某棧的入棧順序是ABCDEF 則出棧順序不可能是哪個 A DCEFBAB ABCDEFC EDFCABD CBAEDF 隊列 隊列是一種先進先出的線性表 它只允許在表的一端插入元素 隊尾 在另一端刪除元素 隊頭 通常定義頭指針front指向隊頭元素的前一個位置 定義尾指針rear指向隊尾元素的位置 隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu) 向隊尾插入一個元素的操作稱為入隊 從隊頭刪除一個元素的操作稱為退隊 循環(huán)隊列 將隊列存儲空間的最后一個位置繞到第一個位置 形成邏輯上的環(huán)狀空間 循環(huán)隊列初始狀態(tài)為空 即front rear m 入隊操作時 rear加1 若rear m 1 則置rear 1 退隊操作時 front加1 若front m 1 則置front 1 在循環(huán)隊列為空或為滿時 均有front rear 因此需要設(shè)置標志s進行區(qū)分 定義s 0表示隊列為空 s 1表示隊列非空 單鏈表 線性表的鏈式存儲結(jié)構(gòu)的特點是用一組任意的存儲單元 可以連續(xù) 也可以不連續(xù) 存儲線性表的數(shù)據(jù)元素 為了表示每個數(shù)據(jù)元素ai與其直接后繼元素ai 1之間的邏輯關(guān)系 對數(shù)據(jù)元素ai來說 除了存儲其本身的信息 數(shù)據(jù)域 之外 還需要存儲其后繼元素的存儲位置信息 指針域 指針域中存儲的信息稱為指針或鏈 N個結(jié)點鏈接成一個鏈表 即為線性表的鏈式存儲結(jié)構(gòu) 由于結(jié)點中只包含一個指針域 故稱為單鏈表 單鏈表 通常以單鏈表中第一個數(shù)據(jù)元素的存儲地址作為作為單鏈表的地址 稱為頭指針 整個鏈表的存儲必須從頭指針開始 順序存取 頭指針指示鏈表中第一個結(jié)點的存儲位置 最后一個數(shù)據(jù)元素沒有直接后繼 其指針域為空 單鏈表的插入和刪除 雙向鏈表和循環(huán)鏈表 在雙向鏈表中的結(jié)點包含兩個指針域 其中一個指向直接后繼 另一個指向直接前驅(qū) 循環(huán)鏈表的特點是表中最后一個結(jié)點的指針域指向第一個結(jié)點 整個鏈表成為一個由鏈指針相鏈接的環(huán) 據(jù)此 從表中任一節(jié)點出發(fā)均可找到表中其它結(jié)點 在循環(huán)鏈表中增加了一個表頭結(jié)點 其指針域指向第一個元素結(jié)點 頭指針則指向頭結(jié)點 樹及其基本概念 樹是一種簡單的非線性結(jié)構(gòu) 在樹中 所有的數(shù)據(jù)元素之間具有明顯的層次性關(guān)系 樹是 n 0 個結(jié)點的有限集合 在任意一棵非空樹中 1 有且僅有一個特定的結(jié)點稱為根結(jié)點 2 當n 1時 其余的結(jié)點可分為m個互不相交的子集T1 T2 Tm 其中每個有限子集本身又是一棵樹 并且稱為根的子樹 集合為空的樹簡稱為空樹 樹中的元素稱為結(jié)點 樹的主要術(shù)語 結(jié)點的度 結(jié)點擁有的子樹數(shù) 葉節(jié)點 終端結(jié)點 度為0的結(jié)點 雙親 孩子和兄弟 結(jié)點的子樹的根節(jié)點稱為該結(jié)點的孩子 該結(jié)點稱為孩子結(jié)點的雙親結(jié)點 同一個雙親結(jié)點的孩子互稱為兄弟 層次 結(jié)點的層次從根開始定義 根為第一層 根的孩子為第二層 深度 樹中結(jié)點的最大層次稱為樹的深度或高度 二叉樹 二叉樹是n n 0 個數(shù)據(jù)元素的有限集 它或為空集 或者含有唯一的稱為根的元素 且其余元素分成兩個互不相交的子集 每個子集自身也是一棵二叉樹 分別稱為根的左子樹和右子樹 二叉樹是另一種樹型結(jié)構(gòu) 其特點是每個結(jié)點至多有兩棵子樹 并且二叉樹的子樹有左右之分 其順序不能任意顛倒 二叉樹的基本性質(zhì) 性質(zhì)1在二叉樹的第i層上至多有2i 1個結(jié)點 i 1 性質(zhì)2深度為k的二叉樹至多有2k 1個結(jié)點 k 1 性質(zhì)3對任何一棵二叉樹T 如果其終端結(jié)點數(shù)為n0 度為2的結(jié)點數(shù)為n2 則 n0 n2 1性質(zhì)4具有n個結(jié)點的二叉樹 其深度至少為 log2n 1 滿二叉樹和完全二叉樹 滿二叉樹除最后一層外 每一層上的所有結(jié)點都有兩個子節(jié)點 也就是說每一層上的結(jié)點數(shù)都達到最大值 即在滿二叉樹的第k層上有2k 1個結(jié)點 且深度為m的滿二叉樹有2m 1個結(jié)點 完全二叉樹除最后一層外 每一層上的結(jié)點數(shù)均達到最大值 在最后一層上只缺少右邊的若干結(jié)點 具有n個結(jié)點的完全二叉樹 其深度為 log2n 1 從以上定義可知 滿二叉樹也是完全二叉樹 反之則不然 二叉樹的基本性質(zhì) 性質(zhì)5如果對一棵有n個結(jié)點的完全二叉樹 其深度為 log2n 1 的結(jié)點按層序 從第1層到第 log2n 1層 每層從左到右 從1起開始編號 則對任一編號為i的結(jié)點 1 i n 則 1 如果i 1 則編號為i的結(jié)點是二叉樹的根 無雙親 如果i 1 則其雙親結(jié)點parent i 的編號是 i 2 2 如果2i n 則編號為i的結(jié)點無左孩子 編號為i的結(jié)點為葉子結(jié)點 否則其左孩子結(jié)點lChild i 的編號是2i 3 如果2i 1 n 則編號為i的結(jié)點無右孩子 否則其右孩子結(jié)點rChild i 的編號是結(jié)點2i 1 二叉樹的鏈式存儲結(jié)構(gòu) 在二叉樹的鏈式存儲結(jié)構(gòu)中 每個結(jié)點設(shè)置三個域 即數(shù)據(jù)域 左指針域和右指針域 兩個指針域分別存儲左右子樹根節(jié)點的存儲位置 即指針 二叉樹的鏈式存儲結(jié)構(gòu) 二叉樹的遍歷 二叉樹的遍歷指不重復(fù)地訪問二叉樹的所有結(jié)點 從二叉樹的結(jié)構(gòu)定義得知 二叉樹是由 根結(jié)點 左子樹 和 右子樹 三部分構(gòu)成 則遍歷二叉樹的操作可分解為 訪問根結(jié)點 遍歷左子樹 和 遍歷右子樹 三個子操作 并且由二叉樹的遞歸定義可知 遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣 遞歸 進行 二叉樹的遍歷 先序遍歷 ABDEGHCFIJ中序遍歷 DBGEHACIJF后序遍歷 DGHEBJIFCA 二叉樹的遍歷 如果一棵樹的先序遍歷序列是ABDEGHCFIJ 中序遍歷序列是DBGEHACIJF 畫出這棵樹并寫出后序序列 如果一棵樹的中序遍歷序列是BDACFE后序遍歷序列是DBFECA 二叉樹的遍歷 1 某二叉樹的前序遍歷結(jié)點訪問順序是ABDGCEFH 中序遍歷的結(jié)點訪問順序是DGBAECHF 則后序遍歷的結(jié)點訪問順序是 2 已知一棵二叉樹的中根序列和后根序列分別為BDCEAFHG和DECBHGFA 試畫出這棵二叉樹 二叉樹的遍歷 查找 查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素 順序查找順序查找一般是指在線性表中查找指定元素 基本方法如下 從線性表的第一個元素開始 依次將線性表中的元素與被查找元素進行比較 若相等則表示找到 即查找成功 若線性表中的所有元素與被查找元素都不相等 則查找失敗 如果線性表為無序表 即表中元素的排列是無序的 則不管線性表采用順序存儲還是鏈式存儲 都必須使用順序查找 如果線性表有序 但采用鏈式存儲結(jié)構(gòu) 則也必須使用順序查找 查找 二分查找 折半查找 二分查找法只適用于順序存儲的有序表 先確定待查目標元素所在范圍 區(qū)間 然后逐步縮小范圍直至找到該元素 或者當查找區(qū)間縮小到0也沒有找到目標元素為止 查找過程中 給定值首先和處于待查區(qū)間 中間位置 的關(guān)鍵字進行比較 若相等 則查找成功 否則將查找區(qū)間縮小到 前半個區(qū)間 或 后半個區(qū)間 之后繼續(xù)進行查找 折半查找 二分查找 排序 排序是指將一個無序序列整理成按值遞增或遞減 本章均采用遞增規(guī)則 的有序序列 排序可以在各種不同的存儲結(jié)構(gòu)上實現(xiàn) 本章所介紹的算法以順序存儲的線性表為排序?qū)ο?在程序設(shè)計語言中就是一維數(shù)組 排序的算法種類很多 主要包括交換類排序 插入類排序 選擇類排序等 交換類排序 冒泡排序基本思想 從表頭開始掃描線性表 在掃描的過程中依次比較相鄰兩個元素的大小 若前面的元素大于后面的元素 則交換它們的位置 顯然 在掃描過程中 不斷地將將相鄰元素間較大的向后移動 最后將線性表中最大的元素移到表尾 然后 從后向前掃描剩下的線性表 同樣在掃描的過程中依次比較相鄰兩個元素的大小 若后面的元素小于前面的元素 則交換位置 在掃描過程中 不斷地將將相鄰元素間較小的向前移動 最后將線性表中最小的元素移到表頭 對剩下的線性表重復(fù)上述過程 直到剩余線性表為空為止 此時線性表變?yōu)橛行?冒泡排序示例 第一遍 從前向后 第一遍 從后向前 第二遍 從前向后 第二遍 從后向前 快速排序 基本思想 從線性表中選取一個元素 設(shè)為T 將線性表后面小于T的元素移動到前面 將前面大于T的元素移動到后面 將線性表分為兩個部分 子表 T放到分界線的位置 這個過程稱為線性表的分割 通過一次分割 就以T為分界將線性表分為兩個子表 前面的子表中的所有元素均不大于T 而后面子表中的元素均不小于T 按照上述原則對子表繼續(xù)進行分割 直到子表為空 則整個線性表有序 快速排序 操作步驟 首先 在表的第一個元素 最后一個元素和中間元素中選取一個中值 設(shè)為P k 并將P k 賦值給T 再將表中的第一個元素移到P k 的位置 設(shè)兩個指針i j分別指向表的起始和最后位置 反復(fù)操作以下兩步 將j逐漸減小 并逐次比較P j 和T 直到發(fā)現(xiàn)一個P j T為止 并將P i 移到P j 的位置上 上述兩步操作交替進行 直到i和j指向同一個位置 再將T移動到P i 的位置上 完成一次分割 31 暫存樞軸記錄T 12 12 68 68 23 23 45 45 31 31 快速排序的一次分割過程 31 插入類排序 簡單插入排序基本思想 將待排序列表分成兩部分 已排序部分和未排序部分 每次掃描將未排序列表中的第一個元素取出并插入到已排序列表中的合適位置 包含n個元素的列表最多需要n 1次掃描 簡單插入排序示例 原始序列 第1趟 第2趟 第3趟 第4趟 第5趟 希爾排序 基本思想 將整個無序序列分割成若干個小的子序列分別進行插入排序 子序列的分割方法 將相隔某個增量h的元素構(gòu)成一個子序列 在排序過程中 逐次減小這個增量 最后當h減到1時 進行一次插入排序 排序完成 增量序列一般取ht n 2k k 1 2 log2n 希爾排序 h 6 h 1 h 3 完成 選擇類排序 簡單選擇排序基本思想 將待排序列表分成兩部分 已排序部分和未排序部分 找到未排序部分中的最小元素并把它和未排序部分中的第一個元素進行交換 經(jīng)過一次選擇和交換 列表中已排序部分增加一個元素 未排序部分減少一個元素 每次把一個元素從未排序部分移動到已排序部分稱為完成一次分類掃描或稱為一趟排序 一個包含n個元素的列表需要進行n 1次掃描完成排序 簡單選擇排序示例 原始序列 第1趟 第2趟 第3趟 第4趟 第5趟 第二章程序設(shè)計基礎(chǔ) 15 考試大綱1 程序設(shè)計方法與風(fēng)格 2 結(jié)構(gòu)化程序設(shè)計 3 面向?qū)ο蟮某绦蛟O(shè)計方法 對象 方法 屬性及繼承與多態(tài)性 知識點歸納 程序設(shè)計方法程序設(shè)計是一門技術(shù) 需要相應(yīng)的理論 方法和工具來支持 就程序設(shè)計方法和技術(shù)的發(fā)展而言 主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計和面向?qū)ο蟮某绦蛟O(shè)計階段 在程序設(shè)計中 通常采用 自頂向下 逐步求精 的方法 即把一個模塊的功能逐步分解 細化為一系列具體的步驟 進而轉(zhuǎn)換成一系列用某種程序設(shè)計語言編寫的程序 程序設(shè)計風(fēng)格 除了程序設(shè)計設(shè)計方法和技術(shù)之外 程序風(fēng)格也是非常重要的 良好的程序設(shè)計風(fēng)格概括起來包括以下及格方面 源程序文檔化數(shù)據(jù)說明的方法語句的結(jié)構(gòu)輸入和輸出 程序設(shè)計風(fēng)格 源程序文檔化標識符的命名程序的注釋序言性注釋功能性注釋程序的視覺組織數(shù)據(jù)的說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化說明語句中變量的安排有序化使用注釋說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計風(fēng)格 語句結(jié)構(gòu)在一行內(nèi)只寫一條語句程序編寫應(yīng)優(yōu)先考慮清晰性除非對效率有特殊要求 程序編寫要做到清晰第一 效率第二首先要保證程序正確 然后才要求提高速度避免使用臨時變量而使程序的可讀性下降避免不必要的轉(zhuǎn)移盡可能使用庫函數(shù)避免使用復(fù)雜的條件語句盡量減少使用 否定 條件的條件語句數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化要模塊化 使模塊功能盡可能單一化利用信息隱蔽 確保每一個模塊的獨立性從數(shù)據(jù)出發(fā)構(gòu)造程序不要修補不好的程序 要重寫編寫 程序設(shè)計風(fēng)格 輸入和輸出對所有輸入數(shù)據(jù)檢驗合法性檢查輸入項的各種重要組合的合法性輸入格式要簡單 以使輸入的步驟和操作盡可能簡單輸入數(shù)據(jù)時 應(yīng)允許使用自由格式應(yīng)允許缺省值輸入一批數(shù)據(jù)時 最好使用輸入結(jié)束標志在以交互式輸入 輸出方式進行輸入時 要在屏幕上使用提示符明確提示輸入的請求 同時在數(shù)據(jù)輸入結(jié)束時 應(yīng)在屏幕上給出狀態(tài)信息當程序設(shè)計語言對輸入格式有嚴格要求時 應(yīng)保持輸入格式與輸入語句的一致性 給所有的輸出加注釋 并設(shè)計輸出報表格式 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計的原則自頂向下 程序設(shè)計時 應(yīng)先考慮總體 后考慮細節(jié) 先考慮全局目標 后考慮局部目標 不要一開始就過多追求細節(jié) 先從最上層總目標開始設(shè)計 逐步使問題具體化 逐步求精 對復(fù)雜的問題 應(yīng)設(shè)計一些子目標過渡 逐步細化 模塊化 一個復(fù)雜問題肯定是有若干簡單問題構(gòu)成 模塊化是把程序要解決的總目標分解為分目標 再進一步分解為具體的小目標 每個小目標成為一個模塊 嚴格限制GOTO語句的使用 結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)和特點 程序由一些基本結(jié)構(gòu)組成 任何一個程序都可以用三種基本控制結(jié)構(gòu)組成 順序結(jié)構(gòu) 選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu) 并且具有如下特點 單入口 單出口 結(jié)構(gòu)中無死循環(huán) 程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系 一個大型程序應(yīng)按功能分割成一些模塊 并把這些模塊按層次關(guān)系進行組織 在程序設(shè)計時應(yīng)采用自頂向下 逐步細化的實施方法 面向?qū)ο蟪绦蛟O(shè)計 面向?qū)ο蠓椒ǖ幕靖拍? 對象 類和屬性在面向?qū)ο蟪绦蛟O(shè)計中 對象是程序的基本單位 對象可以表示客觀世界中的任何實體 是對問題域中某個實體的抽象 每個對象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來定義 類是對一組具有共同屬性和相似行為的對象的一種抽象 描述了屬于該類的所有對象的性質(zhì) 2 方法方法有稱為操作或服務(wù) 它描述了對象執(zhí)行的功能 若通過消息傳遞 還可為其他對象使用 面向?qū)ο蠓椒ǖ幕靖拍?3 繼承 繼承是對象方法的一個重要特征 指一個類 子類 直接使用另一個類 父類 的所有屬性和方法 它可以減少相似類的重復(fù)說明 從而體現(xiàn)一般性和特殊性的原則 4 多態(tài)性 多態(tài)性可以用 一個對外界面 多個內(nèi)部實現(xiàn) 來表示 可以通過方法重載和方法重寫來實現(xiàn)多態(tài) 重載指一個類中可以有多個具有相同名稱的方法 由傳遞給它們的不同個數(shù)和類型的參數(shù)來決定執(zhí)行那個方法 重寫指子類可以重新實現(xiàn)父類的某些方法 使其具有自己的特征 多態(tài)性機制增加了面向?qū)ο筌浖到y(tǒng)的靈活性 提高了軟件的可重用性和可擴充性 5 消息 面向?qū)ο笙到y(tǒng)中的對象之間是通過消息機制彼此相互合作的 消息是一個對象與另一個對象之間傳遞的信息 它請求對象執(zhí)行某一處理或回答某一要求的信息 面向?qū)ο蟪绦蛟O(shè)計的特點 按照人的思維方式對客觀世界進行抽象穩(wěn)定性好可重用性好易于開發(fā)大型軟件可維護性好 第三章軟件工程基礎(chǔ) 考試大綱1 軟件工程基本概念 軟件生命周期的概念 軟件工具與軟件開發(fā)環(huán)境 2 結(jié)構(gòu)化分析方法 數(shù)據(jù)流圖 數(shù)據(jù)字典 軟件需求規(guī)格說明書 3 結(jié)構(gòu)化設(shè)計方法 總體設(shè)計與詳細設(shè)計 4 軟件測試的方法 白盒測試與黑盒測試 測試用例設(shè)計 軟件測試的實施 單元測試 集成測試和系統(tǒng)測試 5 程序的調(diào)試 靜態(tài)調(diào)試與動態(tài)調(diào)試 知識點歸納 軟件定義和特點計算機軟件式計算機系統(tǒng)中與硬件相互依存的另一部分 是包括程序 數(shù)據(jù)及相關(guān)文檔的完整集合 計算機軟件具有如下特點 軟件是一種邏輯實體 具有抽象性軟件生產(chǎn)沒有明顯的制造過程軟件在運行 使用期間不存在磨損 老化問題軟件的開發(fā) 運行對計算機系統(tǒng)具有依賴性軟件復(fù)雜性高 成本昂貴軟件開發(fā)涉及諸多社會因素 軟件危機 所謂軟件危機是指在計算機軟件開發(fā)和維護過程中所遇到的一系列嚴重問題 包括 軟件需求的增長得不到滿足軟件開發(fā)成本和進度無法控制軟件質(zhì)量難以保證軟件不可維護或可維護性低軟件成本不斷提高軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長 軟件工程 為了消除軟件危機 提出了軟件工程學(xué) 軟件工程是應(yīng)用于計算機軟件定義 開發(fā)和維護的一整套方法 工具 文檔 實踐標準和工序 軟件工程的三要素方法工具過程 軟件工程過程 軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動 它包括兩方面含義 1 軟件工程過程是指為獲得軟件產(chǎn)品 在軟件工具支持下由軟件工程師完成的一系列工程活動 通常包括四種基本活動 P Plan 軟件規(guī)格說明D Do 軟件開發(fā)C Check 軟件確認A Action 軟件演進2 從軟件開發(fā)的觀點看 軟件工程過程是使用適當?shù)馁Y源 為開發(fā)軟件進行的一組開發(fā)活動 在活動結(jié)束時將輸入 用戶需求 轉(zhuǎn)化為輸出 軟件產(chǎn)品 軟件生命周期 軟件從提出 實現(xiàn) 使用 維護到停止使用的過程稱為軟件的生命周期 一般包括以下幾個階段 可行性研究與計劃制定需求分析軟件設(shè)計軟件實現(xiàn)軟件測試運行和維護 軟件工程目標與原則 軟件工程的目標是在給定成本 進度的前提下 開發(fā)出具有有效性 可靠性 可理解性 可維護性 可重用性 可適應(yīng)性 可移植性 可追蹤性和可互操作性且滿足用戶需求的軟件產(chǎn)品 為達到上述目標 在軟件開發(fā)的過程中 必須遵循軟件工程的基本原則 抽象信息隱蔽模塊化局部化確定性一致性完備性可驗證性 軟件開發(fā)工具與軟件開發(fā)環(huán)境 軟件開發(fā)工具對過程和方法提供自動或半自動的支持 當這些工具被集成起來使得一個工具產(chǎn)生的信息可以被另外一個工具使用時 一個支持軟件開發(fā)的系統(tǒng)就建立起來了 稱為計算機輔助軟件工程 CASE CASE集成了軟件 硬件和一個軟件工程數(shù)據(jù)庫 包含了有關(guān)分析 設(shè)計 程序構(gòu)造和測試的重要信息 從而創(chuàng)建了一個軟件開發(fā)環(huán)境 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法大多使用自頂向下 逐層分解的系統(tǒng)分析方法來定義系統(tǒng)需求 在結(jié)構(gòu)化分析的基礎(chǔ)上 完成系統(tǒng)的規(guī)格說明 建立系統(tǒng)的一個自頂向下的任務(wù)分析模型 結(jié)構(gòu)化分析方法是一種建模技術(shù) 模型的核心是數(shù)據(jù)辭典 它描述了所有在目標系統(tǒng)中使用和生成的數(shù)據(jù)對象 結(jié)構(gòu)化分析常用的工具 數(shù)據(jù)流圖 DFD 描述數(shù)據(jù)在系統(tǒng)中如何被傳送或變換以及描述如何對數(shù)據(jù)流進行變換的功能 用于功能建模 數(shù)據(jù)字典判定樹判定表 數(shù)據(jù)流圖 數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具 它從數(shù)據(jù)傳遞和加工的角度 來刻畫數(shù)據(jù)流從輸入系統(tǒng)到從系統(tǒng)輸入的移動變換過程 數(shù)據(jù)流圖的基本元素外部實體數(shù)據(jù)流處理 加工 數(shù)據(jù)存儲 數(shù)據(jù)字典 數(shù)據(jù)字典是關(guān)于數(shù)據(jù)的信息的集合 對數(shù)據(jù)流圖中的各個元素進行完整的定義和說明 數(shù)據(jù)流圖和數(shù)據(jù)字典共同構(gòu)成系統(tǒng)的邏輯模型 數(shù)據(jù)字典通常包含的信息有 名稱 別名 何處使用 如何使用 內(nèi)容描述以及補充信息等 軟件需求 軟件需求包括 功能需求 性能需求 環(huán)境需求 可靠性需求 安全保密需求 用戶界面需求 資源使用需求 成本消耗需求 開發(fā)進度需求等 需求分析應(yīng)交付的主要文檔是軟件需求規(guī)格說明書 SRS 結(jié)構(gòu)化設(shè)計 結(jié)構(gòu)化設(shè)計就是采用最佳的可能方法設(shè)計系統(tǒng)的各個組成部分以及個成分之間的內(nèi)部聯(lián)系的技術(shù) 也就是說 結(jié)構(gòu)化設(shè)計是這樣一個過程 它決定用哪些方法把哪些部分聯(lián)系起來 才能解決好某個具體的有清楚定義的問題 從工程管理的角度看 軟件設(shè)計分兩步完成 1 概要設(shè)計 即總體設(shè)計 將軟件需求轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)和軟件的系統(tǒng)結(jié)構(gòu) 常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖 StructureChart 2 詳細設(shè)計 即過程設(shè)計 通過對結(jié)構(gòu)表示進行細化 得到軟件詳細的數(shù)據(jù)結(jié)構(gòu)和算法 過程設(shè)計常用的工具有 程序流程圖 N S圖 PAD圖 過程設(shè)計語言PDL 偽碼 軟件測試 定義 使用人工或自動手段來運行或測定某個系統(tǒng)的過程 其目的在于檢驗它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實際結(jié)果之間的差別 軟件測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 一個好的測試用例是指可能找到迄今為止尚未發(fā)現(xiàn)的錯誤的用例 一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試 測試不能表明軟件中不存在錯誤 它只能說明軟件中存在錯誤 測試技術(shù)與方法綜述 從是否需要執(zhí)行被測試軟件的角度 可將測試分為靜態(tài)測試和動態(tài)測試 靜態(tài)測試主要包括代碼檢查 靜態(tài)結(jié)構(gòu)分析 代碼質(zhì)量度量等 動態(tài)測試是基于計算機的測試 是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 或者說 是根據(jù)軟件開發(fā)的各個階段的規(guī)格說明和程序的內(nèi)部結(jié)構(gòu)而精心設(shè)計的一批測試用例 并利用這些測試用例去運行程序 以發(fā)現(xiàn)程序錯誤的過程 測試技術(shù)與方法綜述 按照功能劃分 可將軟件測試分為黑盒測試和白盒測試 黑盒測試將測試對象看作一個黑盒 不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性 只依據(jù)程序的需求規(guī)格說明 檢查程序的功能是否符合它的功能說明 這種測試又稱為功能測試或數(shù)據(jù)驅(qū)動測試 白盒測試把測試對象看作一個透明的盒子 利用程序內(nèi)部的邏輯機構(gòu)及有關(guān)信息 設(shè)計或選擇測試用例 對程序的所有邏輯路徑進行測試 通過在不同點檢查程序的狀態(tài) 確定實際的狀態(tài)是否與預(yù)期的一致 這種測試又稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試 軟件測試的實施 軟件測試按四個步驟進行 單元測試 對軟件設(shè)計的最小單位 模塊進行正確性的測試 其目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯誤 集成測試 是測試和組裝軟件的過程 它是在把模塊按照設(shè)計要求組裝起來的同時進行測試 主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤 確認測試 任務(wù)是驗證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求 以及軟件配置是否完全 正確 系統(tǒng)測試 將通過確認測試的軟件 作為整個計算機系統(tǒng)的一個元素 與計算機硬件 外設(shè) 支持軟件 數(shù)據(jù)以及人員等其他系統(tǒng)元素組合在一起 在實際運行環(huán)境中對其進行一系列的集成測試和確認測試 程序調(diào)試 程序調(diào)試的任務(wù)是診斷和修正程序中的錯誤 調(diào)試的方法 強行排錯法回溯法原因排除法 第四章數(shù)據(jù)庫設(shè)計基礎(chǔ) 考試大綱1 數(shù)據(jù)庫的基本概念 數(shù)據(jù)庫 數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)庫系統(tǒng) 2 數(shù)據(jù)模型 實體聯(lián)系模型及E R圖 從E R圖導(dǎo)出關(guān)系數(shù)據(jù)模型 3 關(guān)系代數(shù)運算 包括集合運算及選擇 投影 連接運算 數(shù)據(jù)庫規(guī)范化理論 4 數(shù)據(jù)庫設(shè)計方法和步驟 需求分析 概念設(shè)計 邏輯設(shè)計和物理設(shè)計的相關(guān)策略 知識點歸納 數(shù)據(jù)庫的定義1 長期存放在計算機內(nèi) 有組織的 可共享的數(shù)據(jù)集合 數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織 描述和存儲 具有較小的冗余度 較高的數(shù)據(jù)獨立性和易擴展性 2 數(shù)據(jù)庫是由一個互相關(guān)聯(lián)的數(shù)據(jù)的集合和一組用以訪問這些數(shù)據(jù)的程序組成的 數(shù)據(jù)庫管理系統(tǒng) DBMS 數(shù)據(jù)庫管理系統(tǒng)是一個幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應(yīng)用程序的集合 因此 數(shù)據(jù)庫管理系統(tǒng)也就是一個可以幫助完成定義 構(gòu)造和操縱數(shù)據(jù)庫等處理目的的通用軟件系統(tǒng) 其主要功能如下 數(shù)據(jù)模式定義數(shù)據(jù)存取的物理構(gòu)建數(shù)據(jù)操縱數(shù)據(jù)的完整性 安全性定義和檢查數(shù)據(jù)庫的并發(fā)控制和故障恢復(fù)數(shù)據(jù)的服務(wù)為完成上述功能 DBMS提供了相應(yīng)的語言 數(shù)據(jù)定義語言 DDL 數(shù)據(jù)操縱語言 DML 數(shù)據(jù)控制語言 DCL 數(shù)據(jù)庫系統(tǒng) 數(shù)據(jù)庫系統(tǒng)是由數(shù)據(jù)庫 數(shù)據(jù)庫管理系統(tǒng) 數(shù)據(jù)庫管理員 硬件平臺和軟件平臺等幾個部分組成的完整的運行實體 數(shù)據(jù)庫系統(tǒng)的特點數(shù)據(jù)的集成性數(shù)據(jù)的高共享性和低冗余性數(shù)據(jù)的獨立性數(shù)據(jù)統(tǒng)一管理和控制 數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu) 三級模式概念模式 數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述 全體用戶的數(shù)據(jù)視圖外模式 又稱為用戶模式 是每個用戶的局部數(shù)據(jù)描述 用戶的數(shù)據(jù)視圖內(nèi)模式 又稱為物理模式 是數(shù)據(jù)庫物理存儲結(jié)構(gòu)和物理存取方法的描述二級映射概念模式到內(nèi)模式的映射外模式到概念模式的映射 數(shù)據(jù)模型 數(shù)據(jù)是現(xiàn)實世界符號的抽象 數(shù)據(jù)模型是現(xiàn)實世界數(shù)據(jù)特征的抽象 它從抽象層次上描述了系統(tǒng)的靜態(tài)特征 動態(tài)行為和約束條件 為數(shù)據(jù)庫系統(tǒng)的信息表示和操作提供一個抽象的框架 數(shù)據(jù)模型描述的內(nèi)容包括三部分 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)約束數(shù)據(jù)模型按不同的應(yīng)用層次分成三種類型 概念數(shù)據(jù)模型邏輯數(shù)據(jù)模型物理數(shù)據(jù)模型 實體聯(lián)系 ER 模型 概念模型是面向現(xiàn)實世界的 其出發(fā)點是有效地模擬顯示世界 給出數(shù)據(jù)的概念化結(jié)構(gòu) 實體聯(lián)系模型是一種廣泛使用的概念模型 該模型將現(xiàn)實世界的要求轉(zhuǎn)化為實體 聯(lián)系和屬性等幾個基本概念 并用ER圖直觀地表示出來 ER模型的基本概念 實體 概念世界中的基本單位 它們是客觀存在且能相互區(qū)別的事物 凡具有共性的實體可以組成一個集合稱為實體集 屬性 屬性用來描述實體的特征 一個實體可以有多個屬性 每個屬性可以有值 一個屬性的取值范圍稱為該屬性的值域 聯(lián)系 聯(lián)系反映概念世界中的實體集之間存在的一定關(guān)系 一對一聯(lián)系 1 1 一對多聯(lián)系