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

1、1.1 算法1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對(duì)特定問題求解步驟的一種描述。*：算法不等于程序，也不等于計(jì)算方法算法的基本特征（1）可行性。針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。（4）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個(gè)算法

2、執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無法執(zhí)行或執(zhí)行有錯(cuò)。一般說來，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效。3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。（2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要包括：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)

3、元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。線性表邏輯結(jié)構(gòu)線性結(jié)構(gòu)（一對(duì)一）非線性結(jié)構(gòu)隊(duì)列棧樹（一對(duì)多）圖（多對(duì)多）（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈?zhǔn)降取?）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。2）鏈?zhǔn)酱鎯?chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的

4、邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。1.4 棧和隊(duì)列1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。2、隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。1.6 樹與二叉

5、樹1、樹的基本概念樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。2、二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。*：根據(jù)二叉樹的概念可知

6、，二叉樹的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第k層上，最多有 個(gè)結(jié)點(diǎn)。性質(zhì)2 深度為m的二叉樹最多有個(gè) 個(gè)結(jié)點(diǎn)。性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 ，其中 表示取 的整數(shù)部分。3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。*：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。下圖a表示的是滿二叉樹，下圖b表示的是

7、完全二叉樹：完全二叉樹還具有如下兩個(gè)特性：性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 。性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(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)，它沒有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。若2kn，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。若2k+1n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。5、二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三種：（1）前序遍

8、歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。（2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。（3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。1.7 查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等

9、于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長(zhǎng)度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想：從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O（n）。下列兩種情況下只能采用順序查找：1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。2）即

10、使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。2、二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。查找過程：1）若中間項(xiàng)（中間項(xiàng)mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到；2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。*：二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列允許相鄰元素值相等。對(duì)于無序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

11、只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O（log2n）。1.8 排序技術(shù)排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。1、交換類排序法（方法：冒泡排序，快速排序）。2、插入類排序法（方法：簡(jiǎn)單插入排序，希爾排序）。3、選擇類排序法（方法：簡(jiǎn)單選擇排序，堆排序）。總結(jié)：各種排序法比較：第二章 程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”。主要應(yīng)注重和考慮下述一些因素：（1）源程序文檔化。1）符號(hào)名的命名。符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。2.2 結(jié)構(gòu)化

12、程序設(shè)計(jì)（面向過程的程序設(shè)計(jì)方法）1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。（1）自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。（2）逐步求精。對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。（3）模塊化。一個(gè)復(fù)雜問題，肯定是由若干稍簡(jiǎn)單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。（4）限制使用goto語(yǔ)句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。1）順序結(jié)

13、構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì)，即按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)。2）選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語(yǔ)句序列。3）重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何單入口/單出口的程序。2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來認(rèn)識(shí)、理解和描述客觀

14、事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)地反映問題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)：（1）與人類習(xí)慣的思維方法一致；（2）穩(wěn)定性好；（3）可重用軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程。性好；（4）易于開發(fā)大型軟件產(chǎn)品；（5）可維護(hù)性好。*：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作

15、組成。對(duì)象是屬性和方法的封裝體。屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變。操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是對(duì)象的動(dòng)態(tài)屬性。*：一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成。對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性好。（1）標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。 （2）分類性。指可以將具有相同屬性的操作的對(duì)象抽象成類。 （3）多態(tài)性。指同一個(gè)操作可以是不同對(duì)象的行為。 （4）封裝性。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的

16、具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對(duì)象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見的。從外面不能直接使用對(duì)象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。*：信息隱蔽是通過對(duì)象的封裝性來實(shí)現(xiàn)的。 （5）模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。類是指具有共同屬性、共同方法的對(duì)象的集合。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組

17、成包括：（1）接收消息的對(duì)象的名稱；（2）消息標(biāo)識(shí)符，也稱消息名；（3）零個(gè)或多個(gè)參數(shù)。*：在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其服務(wù)的方式是通過發(fā)送消息。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。*：類的繼承性是類之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性。多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。 第三章 軟件工程基礎(chǔ)3.1 軟件工程基本概念軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的目的就是要建造一

18、個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程，它包括3個(gè)要素：方法、工具和過程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。3、軟件生命周期軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：1）軟件定義階段：包括制定計(jì)劃和需求分析。

19、制定計(jì)劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計(jì)劃。需求分析：對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。2）軟件開發(fā)階段：軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改。*：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。2、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主

20、要工具，建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判定表。數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。上圖是數(shù)據(jù)流圖的基本圖形元素：3、軟件需求規(guī)格說明書（SRS）軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。軟件設(shè)計(jì)的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性。模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個(gè)定性指標(biāo)。內(nèi)聚性

21、：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。3.4 軟件測(cè)試1、軟件測(cè)試定義：使用人工或自動(dòng)手段來運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。*：軟件測(cè)試的目的：盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤，不能也不可能證明程序沒有錯(cuò)誤。2、軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過人工進(jìn)行。動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒測(cè)試方法。

22、（1）白盒測(cè)試白盒測(cè)試方法也稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。（2）黑盒測(cè)試黑盒測(cè)試方法也稱為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。3、軟件測(cè)試過程一般按4個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試。3.5 程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)該由編制源程序的程序員來完成。第四章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)4.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)管理系統(tǒng)（1）數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如整型、實(shí)型、字符型

23、等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。（2）數(shù)據(jù)庫(kù)（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)，亦即是數(shù)據(jù)庫(kù)集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一的構(gòu)造和存儲(chǔ)，而使它們可被不同應(yīng)用程序所使用。（3）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：1）數(shù)據(jù)模式定義。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫(kù)構(gòu)建模式，也就是為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架。2）數(shù)據(jù)存取的物理構(gòu)

24、建。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。3）數(shù)據(jù)操縱。數(shù)據(jù)庫(kù)管理系統(tǒng)為用戶使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)提供方便，它一般提供如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)的能力，而且還可以與某些過程性語(yǔ)言結(jié)合，使其具有強(qiáng)大的過程性操作能力。4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有內(nèi)在語(yǔ)義上的關(guān)聯(lián)性與一致性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫(kù)中數(shù)據(jù)正確的必要條件，因此必須經(jīng)常檢查以維護(hù)數(shù)據(jù)正確。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會(huì)引發(fā)數(shù)據(jù)的非法使用，因此必須要對(duì)數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時(shí)做檢查，這

25、就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性與安全性的維護(hù)是數(shù)據(jù)庫(kù)系統(tǒng)的基本功能。5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫(kù)是一個(gè)集成、共享的數(shù)據(jù)集合體，它能為多個(gè)應(yīng)用程序服務(wù)，所以就存在著多個(gè)應(yīng)用程序?qū)?shù)據(jù)庫(kù)的并發(fā)操作。在并發(fā)操作中如果不加控制和管理，多個(gè)應(yīng)用程序間就會(huì)相互干擾，從而對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成破壞。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)必須對(duì)多個(gè)應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞，這就是數(shù)據(jù)庫(kù)的并發(fā)控制。數(shù)據(jù)庫(kù)中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫(kù)管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢復(fù)，這就是數(shù)據(jù)庫(kù)的故障恢復(fù)。6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫(kù)管理系統(tǒng)提供對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。（4）數(shù)

26、據(jù)庫(kù)管理員（DBA）：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專業(yè)管理人員。（5）數(shù)據(jù)庫(kù)系統(tǒng)（DBS）：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。（6）數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。*：數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)庫(kù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。下表是數(shù)據(jù)管理三個(gè)階段的比較：人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)階段背景應(yīng)用背景科學(xué)計(jì)算科學(xué)計(jì)算、管理大規(guī)模管理硬件背景無直接存取存儲(chǔ)設(shè)備磁盤、磁鼓大容量磁備盤軟件背

27、景沒有操作系統(tǒng)有文件系統(tǒng)有數(shù)據(jù)庫(kù)管理系統(tǒng)處理方式批處理聯(lián)機(jī)實(shí)時(shí)處理、批處理聯(lián)機(jī)實(shí)時(shí)處理、分布處理、批處理特點(diǎn)數(shù)據(jù)的管理者用戶（程序員）文件系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)面向的對(duì)象某一應(yīng)用程序某一應(yīng)用現(xiàn)實(shí)世界數(shù)據(jù)的共享程度無共享，冗余度極大共享性差，冗余度大共享性高，冗余度小數(shù)據(jù)的獨(dú)立性不獨(dú)立，完全依賴于程序獨(dú)立性差具有高度的物理獨(dú)立性和一定的邏輯獨(dú)立性數(shù)據(jù)的結(jié)構(gòu)化無結(jié)構(gòu)記錄內(nèi)有結(jié)構(gòu)，整體無結(jié)構(gòu)整體結(jié)構(gòu)化，用數(shù)據(jù)模型描述數(shù)據(jù)控制能力應(yīng)用程序自己控制應(yīng)用程序自己控制由數(shù)據(jù)庫(kù)管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)能力3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)（1）數(shù)據(jù)的高集成性。（2）數(shù)據(jù)的高共享性與低冗余性。*：數(shù)

28、據(jù)庫(kù)系統(tǒng)可以減少數(shù)據(jù)冗余，但無法避免一切冗余。（3）數(shù)據(jù)獨(dú)立性：數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性兩級(jí)。1）物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲(chǔ)結(jié)構(gòu)，存取方式等）的改變，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化。2）邏輯獨(dú)立性：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。（4）數(shù)據(jù)統(tǒng)

29、一管理與控制。數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個(gè)方面：1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫(kù)中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。2）數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫(kù)訪問者以防止非法訪問。3）并發(fā)控制：控制多個(gè)應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系（1）數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級(jí)上，它還未

30、深入到設(shè)備級(jí)上（如磁盤及磁盤操作）。內(nèi)模式對(duì)一般用戶是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。（2）數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：1）概念模式/內(nèi)模式的映射：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)發(fā)生變化時(shí)，通過修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫(kù)的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨(dú)立性。2）外模式/概念模式的映射：實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式發(fā)生變化時(shí)，通過修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。4.2 數(shù)據(jù)模型1、數(shù)據(jù)模型（1）數(shù)據(jù)模型

31、的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。（2）數(shù)據(jù)模型所描述的內(nèi)容有三個(gè)部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是所研究的對(duì)象類型的集合，包括與數(shù)據(jù)類型、內(nèi)容、性質(zhì)有關(guān)的對(duì)象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對(duì)象。它用于描述系統(tǒng)的靜態(tài)特性。2）數(shù)據(jù)操作：數(shù)據(jù)操作是對(duì)數(shù)據(jù)庫(kù)中各種對(duì)象（型）的實(shí)例（值）允許執(zhí)行的操作的集合，包括操作的含義、符號(hào)、操作規(guī)則及實(shí)現(xiàn)操作的語(yǔ)句等。它用于描述系統(tǒng)的動(dòng)態(tài)特性。3）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)

32、系所具有的制約和依存規(guī)則，用以限定符號(hào)數(shù)據(jù)模型的數(shù)據(jù)庫(kù)狀態(tài)及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。（3）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類：1）概念數(shù)據(jù)模型：簡(jiǎn)稱概念模型，是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫。概念模型主要有：E-R模型(實(shí)體聯(lián)系模型)、擴(kuò)充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫(kù)系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫(kù)系統(tǒng)一級(jí)的實(shí)現(xiàn)。邏輯數(shù)據(jù)模型主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取?）物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)

33、構(gòu)的表示。2、實(shí)體聯(lián)系模型及E-R圖（1）E-R模型的基本概念：1）實(shí)體：現(xiàn)實(shí)世界中的事物。2）屬性：事物的特性。3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。E-R模型三個(gè)基本概念之間的聯(lián)接關(guān)系：1）實(shí)體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）實(shí)體（集）與聯(lián)系。*：E-R模型的基本成分是實(shí)體和聯(lián)系。（2）E-R模型的圖示法：1）實(shí)體集：用矩形表示。2）屬性：用橢圓形表示。3）聯(lián)系：用菱形表示。4）實(shí)體集與屬性間的聯(lián)接關(guān)系：用無向線段表示。5）實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。（3）數(shù)據(jù)庫(kù)管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。1）層次模型的

34、基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn)：A、每棵樹有且僅有一個(gè)無雙親結(jié)點(diǎn)，稱為根；B、樹中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。2）網(wǎng)狀模型是層次模型的一個(gè)特例，從圖論上看，網(wǎng)狀模型是一個(gè)不加任何條件限制的無向圖。3）關(guān)系模型采用二維表來表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。二維表的表框架由n個(gè)命名的屬性組成，n稱為屬性元數(shù)。每個(gè)屬性有一個(gè)取值范圍稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實(shí)際上，一個(gè)元組是由n個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值。學(xué)號(hào)姓名性別出生年月班級(jí)籍貫2007102張潔然男07-07-8

35、807動(dòng)畫1班天津2007203李一明男05-01-8707播音5班廣西南寧2007305王 麗女04-09-8807管理4班遼寧沈陽(yáng)2007406劉 宏男10-11-8807新聞3班江蘇南京*：同一個(gè)關(guān)系模型的任兩個(gè)元組值不能完全相同。主碼：或稱為關(guān)鍵字、主鍵，簡(jiǎn)稱碼、鍵，表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的，稱為關(guān)系的主碼或關(guān)鍵字。例如，學(xué)生的學(xué)號(hào)。主碼屬性不能取空值。外部關(guān)鍵字：或稱為外鍵，在一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組稱為該關(guān)系的外部關(guān)鍵字。外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?duì)應(yīng)的關(guān)鍵字值。例如，在學(xué)生表中含有的所屬班級(jí)名字，是班級(jí)表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。（4）關(guān)系中的數(shù)據(jù)約束：1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯一決定元組的，如為空值則其唯一性就成為不可能的了。2）參照完整性約束：關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，即在關(guān)系中的外鍵要么是