全國(guó)計(jì)算機(jī)二級(jí)考試基礎(chǔ)知識(shí)

1、.1算法的基本概念1、算法一般應(yīng)具有以下幾個(gè)基本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。算法是對(duì)解題方案的準(zhǔn)確而完整的描述，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效和明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。2、算法的基本要素（1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作。通常有4類：算術(shù)運(yùn)算，邏輯運(yùn)算，關(guān)系運(yùn)算和數(shù)據(jù)傳輸。（2）算法的控制結(jié)構(gòu)。算法的功能不僅僅取決于所選擇的操作，還與操作之間的執(zhí)行順序及算法的控制結(jié)構(gòu)有關(guān)。3、算法設(shè)計(jì)基本方法算法設(shè)計(jì)的基本方法有列舉法、歸納法和遞推法、遞歸法和減半遞推技術(shù)。4、算法的復(fù)雜度（在算法正確的前提下，評(píng)價(jià)算法的標(biāo)準(zhǔn)）（1）算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)

2、雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模的函數(shù)。（2）算法的空間復(fù)雜度算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。數(shù)據(jù)結(jié)構(gòu)，直接影響算法的選擇和效率。而數(shù)據(jù)結(jié)構(gòu)包括兩方面，即數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為4類基本邏輯結(jié)構(gòu)，即集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)圖是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象，它包含數(shù)據(jù)元素的映象和關(guān)系的映象。存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)

3、有兩種，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。時(shí)間復(fù)雜度與空間復(fù)雜度之間沒(méi)有必然的聯(lián)系。2數(shù)據(jù)結(jié)構(gòu)基本概念1、 數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的數(shù)年據(jù)元素集合的表示。2、 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指所映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合；二是數(shù)據(jù)元素之間的關(guān)系。3、 各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。3線性表和線性鏈表1、 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果

4、一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：（1） 有且只有一個(gè)根結(jié)點(diǎn)。（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)關(guān)系的關(guān)鍵字，則稱其為本關(guān)系的外關(guān)鍵字2、 線性表的基本概念 線性表是由n（n>=0）個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。3、線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中

5、是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面。在順序存儲(chǔ)結(jié)構(gòu)中，線性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線性表中的位置序號(hào)唯一確定。3、 線性鏈表 大的線性表，特別是元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。棧和隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6、。4、 線性鏈表的基本運(yùn)算 線性鏈表的基本運(yùn)算有：在非空線性鏈表中尋找包含指定元素值X的前一個(gè)結(jié)點(diǎn)P，線性鏈表的插入，線性鏈表的刪除。5、 循環(huán)鏈表及其基本運(yùn)算循環(huán)鏈表的結(jié)構(gòu)與一般的單鏈表相比，具有以下兩個(gè)特點(diǎn)：(1) 在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。(2) 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。(3) 在單鏈表中，增加頭結(jié)點(diǎn)的目的是方便運(yùn)算的實(shí)現(xiàn)。(4) 循環(huán)鏈表的主要優(yōu)點(diǎn)是從表中任一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到整個(gè)鏈表。(5) 線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是隨機(jī)存取

7、的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)4棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表。棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧的運(yùn)算、退棧運(yùn)算、讀棧頂元素。隊(duì)列是是允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表，它體現(xiàn)了“先來(lái)先服務(wù)”的原則。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上環(huán)狀空間，供隊(duì)列循環(huán)使用。循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m。循環(huán)隊(duì)列主要有兩個(gè)基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。5樹與二叉樹1、 樹的基本概念 樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。在樹

8、中，沒(méi)前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為結(jié)點(diǎn)的度。樹結(jié)構(gòu)具有明顯的層次關(guān)系，樹是是一種層次結(jié)構(gòu)。根結(jié)點(diǎn)在第1層。同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)在下一層。樹的最大層次稱為樹的深度。在樹中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一棵子樹。要樹中，葉子結(jié)點(diǎn)沒(méi)有子樹。2、 二叉樹的特點(diǎn)（1） 非空二叉樹只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有兩個(gè)棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與與右子樹。（2） 在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或右子樹）

9、也均為二叉樹。而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹中的每一個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹與右子樹。在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒(méi)有右子樹，也可以只有右子樹而沒(méi)有左子樹。當(dāng)一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹也沒(méi)有右子樹時(shí)，該結(jié)點(diǎn)即是葉子結(jié)點(diǎn)。3、 二叉樹的性質(zhì)（1） 在二叉樹的第K層上，最多有2 k-1(k1)個(gè)結(jié)點(diǎn)。（2） 深度為m的二叉樹最多有2 m-1個(gè)結(jié)點(diǎn)。（3） 在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。（4） 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分。4、 滿二叉樹與完全二叉樹（1） 滿二叉樹，

10、除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說(shuō)，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2 k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2 m-1個(gè)結(jié)點(diǎn)。（2） 完全二叉樹。除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。對(duì)于完全二叉樹來(lái)說(shuō)，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1.滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。5、 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

11、。與線性鏈表類似，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域與指針域。6、 二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問(wèn)二叉樹中的所有結(jié)點(diǎn)。在遍歷二叉樹的過(guò)程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷、后序遍歷。（1） 前序遍歷（DLR）。所謂前序遍歷是首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。因此，前序遍歷二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。（2） 中序遍歷（LDR）。所謂中序遍歷是首先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右

12、子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹。因此，中序遍歷二叉樹的過(guò)程也是一個(gè)遞歸的過(guò)程。（3） 后序遍歷（LRD）。所謂后序遍歷是首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后右子樹，最后訪問(wèn)根結(jié)點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸的過(guò)程。6查找技術(shù)1、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素。如果線性表中的第一個(gè)元素就是被查找的元素，則只需做一次比較就查找成功，最壞的情況是被查元素是線性表中的最后一個(gè)元素，或者被查元素在線性表中根本不存在，則為了查找這個(gè)元素需要與線性

13、表中所有的元素進(jìn)行比較。平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較。2、二分法查找二分法查找只適用于順序存儲(chǔ)的有序表。設(shè)有序線性表的長(zhǎng)度為n，被查元素為x，則對(duì)分查找的方法為：將x與線性表的中間項(xiàng)進(jìn)行比較，如果中間項(xiàng)的值等于x，則說(shuō)明查到，查找結(jié)束；如果x小于中間項(xiàng)的值，則在線性表的前半部分以相同的方法進(jìn)行查找；如果大于中間項(xiàng)的值，則在線性表的后半部分以相同的方法進(jìn)行查找，這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有該元素）為止。當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，效率比順序查找高得多。對(duì)于長(zhǎng)度為n的有序線性表，在最壞的情況下，二分

14、查找只需要比較log2n次。最簡(jiǎn)單的交換排序方法是冒泡排序法。7排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排序的有序序列。1、 交換類排序法 交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法和快速排序法都屬于交換類的排序方法。（1） 冒泡排序。假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n-1)/2。（2） 快速排序?？焖倥判蚍ǖ幕舅枷霝椋簭木€性表中選取一個(gè)元素，設(shè)為T，將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分，T插入到分界線的位置

15、處，這個(gè)過(guò)程稱為線性表的分隔。如果對(duì)分割后的各子表再按上述原則進(jìn)行分割，并且，這種分割過(guò)程可以一直做下去，直到所有子表為空為止，則此時(shí)的線性表就變成了有序表。2、 插入排序法 所謂插入排序，是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。（1） 簡(jiǎn)單插入排序法。在簡(jiǎn)單插入排序中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡(jiǎn)單插入排序需要n(n-1)/2次比較。（2） 希爾排序法。希爾排序的效率與所選取的增量序列有關(guān)。如果選取上述增量序列，則在最壞情況下，希爾排序所需要的比較次數(shù)為O（n1.5）.3選擇類排序（1） 簡(jiǎn)單選擇排序。簡(jiǎn)單選擇排序在最

16、壞情況下需要比較n(n-1)/2次。（2） 堆排序。在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。4常見的排序方法有插入排序（包括簡(jiǎn)單插入排序法和希爾排序法等）、交換排序（包括冒泡排序和快速排序法等）和選擇排序（包括簡(jiǎn)單選擇排序和堆排序等）。8程序設(shè)計(jì)方法與風(fēng)格1、 源程序文檔化（1） 符號(hào)的命名：符號(hào)名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解。（2） 程序注釋：正確的注釋能夠幫助讀者理解程序。注釋一般分為序言性注釋和功能性注釋。（3） 視覺組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?、 數(shù)據(jù)說(shuō)明的方法 數(shù)據(jù)說(shuō)明的風(fēng)格一般應(yīng)注意：數(shù)據(jù)說(shuō)明

17、的次序規(guī)范化；說(shuō)明語(yǔ)句中變量安排有序化；使用釋來(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)單直接。4、 輸入和輸出 輸入輸出的方式和格式應(yīng)盡可能方便用戶的使用。9結(jié)構(gòu)化程序設(shè)計(jì)1、 結(jié)構(gòu)化程序設(shè)計(jì)的原則 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則為自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。（1） 自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)；先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問(wèn)題具體化。（2） 逐步求精：對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作為過(guò)渡，逐步細(xì)化。（3） 模塊化：一個(gè)復(fù)雜問(wèn)題，是由若干個(gè)簡(jiǎn)單問(wèn)題構(gòu)成的。模塊化是把程序要解決的總目標(biāo)分解分目標(biāo)，

18、再進(jìn)一步分解為具體的小目標(biāo)，把每一個(gè)小目標(biāo)稱為一個(gè)模塊。（4） 限制使用goto語(yǔ)句：濫用goto語(yǔ)句有害，應(yīng)盡量避免。2、 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn) 采用結(jié)構(gòu)化程序設(shè)計(jì)方法編寫程序，可使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。程序設(shè)計(jì)語(yǔ)言僅用順序、選擇、重復(fù)3種基本控制結(jié)構(gòu)就可以表達(dá)出各種其他形式結(jié)構(gòu)的程序設(shè)計(jì)方法。（1） 順序結(jié)構(gòu)：順序結(jié)構(gòu)是順序執(zhí)行結(jié)構(gòu)，所謂順序執(zhí)行，就是按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序。（2） 選擇結(jié)構(gòu)：又稱為分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選項(xiàng)擇結(jié)構(gòu)。這種結(jié)構(gòu)根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句。（3） 重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，它根

19、據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段，利用重復(fù)結(jié)構(gòu)可簡(jiǎn)化大量的程序行。重復(fù)結(jié)構(gòu)有兩類循環(huán)語(yǔ)句，先判斷后執(zhí)行循環(huán)體的稱為當(dāng)型循環(huán)結(jié)構(gòu)，先執(zhí)行循環(huán)后判斷的稱為直到型循環(huán)結(jié)構(gòu)。遵循結(jié)構(gòu)化程序的設(shè)計(jì)原則，按結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)出的程序具有的優(yōu)點(diǎn)為：其一，程序易于理解、使用和維護(hù)；其二，提高了編程工作的效率，降低了軟件開發(fā)成本。3、 結(jié)構(gòu)化程序的設(shè)計(jì)原則和方法的應(yīng)用 在結(jié)構(gòu)圖化程序設(shè)計(jì)的具體實(shí)施中，要注意把握如下因素：（1） 使用程序設(shè)計(jì)語(yǔ)言的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。（2） 選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口。（3） 程序語(yǔ)句組成容易識(shí)別的塊，每

20、塊只有一個(gè)入口和一個(gè)出口。（4） 復(fù)雜結(jié)構(gòu)應(yīng)該應(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ǔ)句的使用。10面向?qū)ο蟮某绦蛟O(shè)計(jì)1、 面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)為：與人類習(xí)慣的思維方式一致；穩(wěn)定性好；可重用性好；易于開發(fā)大型軟件產(chǎn)品；可維護(hù)性好。2、 面向?qū)ο蠹夹g(shù)的基本概念（1） 對(duì)象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。（2） 類和實(shí)例。類是具有共同屬性、共同方法的對(duì)象的集合。類是對(duì)

21、象的抽象，它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象是其對(duì)應(yīng)類的一個(gè)實(shí)例。類同對(duì)象一樣，也包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。（3） 消息。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請(qǐng)求對(duì)象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。消息的使用類似于函數(shù)調(diào)用，消息中指定了某一個(gè)實(shí)例，一個(gè)操作和一個(gè)參數(shù)表。（4） 繼承。繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。在面向?qū)ο蠹夹g(shù)中，把類組成具有層次結(jié)構(gòu)的系統(tǒng)：一個(gè)類的上層可以有父類，下層可以有子類；一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動(dòng)地共享基類中定義的數(shù)據(jù)和方法。（5） 多態(tài)性。對(duì)象根據(jù)所接

22、受的信息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性。（6） 面向?qū)ο蠹夹g(shù)中包括以下幾個(gè)基本概念，即對(duì)象、類、方法、消息、繼承和封裝，其中封裝是一種信息隱蔽技術(shù)，目的在于將對(duì)象的使用者對(duì)象的和設(shè)計(jì)者分開。11軟件工程基本概念1、 軟件及軟件工程的定義 軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的，用程序設(shè)計(jì)語(yǔ)言描述的、適合計(jì)算機(jī)執(zhí)行的指令序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序開發(fā)、維護(hù)和使用有關(guān)的圖文資料。軟件工程學(xué)是用工程、科學(xué)和數(shù)學(xué)的原理與方法研制、維護(hù)計(jì)算機(jī)軟件

23、的有關(guān)技術(shù)及管理方法的一門工程學(xué)科。軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程包括3個(gè)要素，即方法、工具和過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具支持軟件的開發(fā)、管理、文檔生成；過(guò)程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。2、 軟件生命周期軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期。一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。還可將軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)3個(gè)階段。軟件生命周期的主要活動(dòng)階段是：可行性研究與計(jì)劃指定、需求分析、軟件設(shè)計(jì)、軟件測(cè)試、運(yùn)行和維護(hù)。3、 軟件

24、開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具與軟件開發(fā)環(huán)境的使用提高了軟件的開發(fā)效率、維護(hù)效率和軟件質(zhì)量。軟件工程的出現(xiàn)是由于軟件危機(jī)的出現(xiàn)。軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持，其中必要的測(cè)試數(shù)據(jù)屬于輔助資源。軟件結(jié)構(gòu)是以模塊化為基礎(chǔ)而組成的一種控制層次結(jié)構(gòu)。12結(jié)構(gòu)化分析方法1、 需求分析與需求分析方法 軟件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過(guò)程。 需求分析階段的工作，可概括為以下幾方面：需求獲取、需求分析、編寫需求規(guī)格說(shuō)明書、需求評(píng)審。 常見的需求分析方法有結(jié)構(gòu)化分析方法和面向?qū)ο蟮姆治龇椒ā?、 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化

25、分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。結(jié)構(gòu)化分析方法是著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具有數(shù)據(jù)流圖、數(shù)字字典、判斷樹、判斷表。（1） 數(shù)據(jù)流圖（DFD）。數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過(guò)程。數(shù)據(jù)流圖中的主要圖形元素如下圖。第一個(gè)是加工（轉(zhuǎn)換）；第二個(gè)是數(shù)據(jù)流；第三個(gè)是存儲(chǔ)文件（數(shù)據(jù)源）；第四個(gè)是源（潭）。 建立數(shù)據(jù)流圖的步驟：由外向里，自頂向下，逐層分解。（2

26、） 數(shù)據(jù)字典（DD）。數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表。數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。數(shù)據(jù)字典包含的信息有名稱、別名、何處使用如何使用、內(nèi)容描述、補(bǔ)充信息等。（3） 數(shù)據(jù)字典是各類數(shù)據(jù)描述的集合，它通常包括5個(gè)部分，即數(shù)據(jù)項(xiàng)，是數(shù)據(jù)的最小單位；數(shù)據(jù)結(jié)構(gòu)，是若干數(shù)據(jù)項(xiàng)有意義的集合；數(shù)據(jù)流，可以是數(shù)據(jù)項(xiàng)，也可以是數(shù)據(jù)結(jié)構(gòu)，表示某一處理過(guò)程的輸入或輸出；數(shù)據(jù)存儲(chǔ)，處理過(guò)程中存取的數(shù)據(jù)，常常是手工憑證、手工文檔或計(jì)算機(jī)文件；處理過(guò)程3、 軟件需求規(guī)格說(shuō)明書 軟件需求規(guī)格說(shuō)明書把在軟件計(jì)劃中確定的軟件范圍加以展開，制定

27、出完整的信息描述、詳細(xì)的功能說(shuō)明、恰當(dāng)?shù)臋z驗(yàn)標(biāo)準(zhǔn)以及其他與要求有關(guān)的數(shù)據(jù)。13結(jié)構(gòu)化設(shè)計(jì)方法1、 軟件設(shè)計(jì)的基本概念 從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。從工程管理角度來(lái)看，軟件設(shè)計(jì)分兩步完全，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。2、 軟件設(shè)計(jì)的基本原理 衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)。耦合性是模塊間互相聯(lián)結(jié)的緊密程度的度量。內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。一般較優(yōu)秀的軟件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚、低耦合。3、 概要設(shè)計(jì) 概要設(shè)計(jì)也稱總體設(shè)計(jì)。軟件概要設(shè)計(jì)的任務(wù)是：設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)、編寫概要設(shè)計(jì)文檔、概要設(shè)

28、計(jì)文檔評(píng)審。 常用的軟件設(shè)計(jì)工具為程序結(jié)構(gòu)圖。 典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)型。 設(shè)計(jì)準(zhǔn)則：提高模塊獨(dú)立性；模塊規(guī)模適中；深度、寬度、扇入和扇出適當(dāng)；使模塊的作用域在該模塊的控制域內(nèi)；應(yīng)減少模塊的接口和界面的復(fù)雜性；設(shè)計(jì)成單入口、單出口的模塊；設(shè)計(jì)功能可預(yù)測(cè)的模塊。4、 詳細(xì)設(shè)計(jì) 詳細(xì)設(shè)計(jì)為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 設(shè)計(jì)工具：圖形工具（程序流程圖、N-S、PAD、HIPO）、表格工具（判定表）、語(yǔ)言工具（偽碼）。結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是程序易讀性。軟件的過(guò)程設(shè)計(jì)是指系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述。軟件設(shè)計(jì)模塊

29、化的目的是降低復(fù)雜性。結(jié)構(gòu)化分析方法主要包括：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA-Structured analysis），面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法（JSD-Jackson system development method）和面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD-Data structured system development method）。14軟件測(cè)試1、 軟件測(cè)試方法和技術(shù) 軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程，其主要過(guò)程涵蓋了整個(gè)軟件生命期的過(guò)程。 若從是否需要執(zhí)行被測(cè)軟件的角度劃分，軟件測(cè)試方法和技術(shù)可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試方法。若按照功能劃分，可以分為黑盒

30、測(cè)試和白盒測(cè)試。（1） 白盒測(cè)試 白盒測(cè)試方法也稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。白盒測(cè)試把測(cè)試對(duì)象看做一個(gè)打開的盒子，允許測(cè)試人員利用程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。白盒測(cè)試的基本原則：保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次；保證所測(cè)模塊中每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。白盒測(cè)試的主要方法有邏輯覆蓋、基本路徑測(cè)試等。（2） 黑盒測(cè)試方法 黑盒測(cè)試方法也稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。黑盒測(cè)試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求和功能規(guī)格說(shuō)明，檢查程序的功能是否符合它的功能說(shuō)明。黑盒測(cè)

31、試在軟件接口處進(jìn)行。 黑盒測(cè)試主要診斷功能不對(duì)或遺漏、界面錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)訪問(wèn)錯(cuò)誤、性能錯(cuò)誤、初始化和終止條件錯(cuò)誤。 黑盒測(cè)試的主要診斷方法有等價(jià)類劃分法、邊界分析法、錯(cuò)誤推測(cè)法、因果圖法等，主要用于軟件確認(rèn)測(cè)試。2、 軟件測(cè)試的實(shí)施 軟件測(cè)試一般按4個(gè)步驟進(jìn)行，即單元測(cè)試、集成測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試。通過(guò)這些步驟的實(shí)施來(lái)驗(yàn)證軟件是否合格，能否交付用戶使用。軟件測(cè)試的目標(biāo)是在精心控制的環(huán)境下執(zhí)行程序，以發(fā)現(xiàn)程序中的錯(cuò)誤，給出程序可靠性的鑒定；調(diào)試也稱排錯(cuò)，它是一個(gè)與測(cè)試有聯(lián)系又有區(qū)別的概念。具體來(lái)說(shuō)，測(cè)試的目的是暴露錯(cuò)誤，評(píng)價(jià)程序的可靠性，而調(diào)試的目的是發(fā)現(xiàn)錯(cuò)誤的位置，并改正錯(cuò)誤。

32、15程序的調(diào)試程序進(jìn)行了成功的測(cè)試之后進(jìn)入調(diào)試階段，程序調(diào)試是診斷和改正程序中潛在的錯(cuò)誤。調(diào)試主要在開發(fā)階段。程序的調(diào)試活動(dòng)由兩部分組成，一是根據(jù)錯(cuò)誤的跡象確定程序中錯(cuò)誤的確切性質(zhì)、原因和位置。二是對(duì)程序進(jìn)行修改，排除錯(cuò)誤。程序調(diào)試的基本步驟為：錯(cuò)誤定位，修改設(shè)計(jì)和代碼，進(jìn)行回歸測(cè)試。軟件調(diào)試的方法從是否跟蹤和執(zhí)行程序的角度，可分為靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試。靜態(tài)調(diào)試主要指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試的。主要的調(diào)試方法為：強(qiáng)行排錯(cuò)法，回溯法，原因排除法。16數(shù)據(jù)庫(kù)系統(tǒng)的基本概念1、 數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)（1） 數(shù)據(jù)。數(shù)據(jù)是描述事物的符號(hào)記錄。（

33、2） 數(shù)據(jù)庫(kù)。數(shù)據(jù)庫(kù)是數(shù)據(jù)的集合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。（3） 數(shù)據(jù)庫(kù)管理系統(tǒng)。數(shù)據(jù)庫(kù)管理系統(tǒng)（Database Management System,DBMS）是位于用戶與操作系統(tǒng)之間的一個(gè)數(shù)據(jù)管理軟件。負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。（4） 數(shù)據(jù)庫(kù)管理系統(tǒng)提供給用戶的接口是宿主語(yǔ)言。（5） 數(shù)據(jù)庫(kù)管理員。由于數(shù)據(jù)庫(kù)的共享性，因此對(duì)數(shù)據(jù)庫(kù)的規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等需要有專人管理，稱他們?yōu)閿?shù)據(jù)管理員。主要工作有數(shù)據(jù)庫(kù)設(shè)計(jì)、數(shù)據(jù)庫(kù)維護(hù)、改善系統(tǒng)性能和提高系統(tǒng)效率等。（6） 數(shù)據(jù)庫(kù)系統(tǒng)。數(shù)據(jù)庫(kù)

34、系統(tǒng)(Database Sytem,DBS)由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)管理員（人員）、硬件平臺(tái)（系統(tǒng)平臺(tái)之一）和軟件平臺(tái)（系統(tǒng)平臺(tái)之一）5部分組成。在數(shù)據(jù)庫(kù)系統(tǒng)中，硬件平臺(tái)包括：計(jì)算機(jī)和網(wǎng)絡(luò)，軟件平臺(tái)包括：操作系統(tǒng)數(shù)據(jù)庫(kù)開發(fā)工具和接口軟件。（7） 數(shù)據(jù)庫(kù)管理系統(tǒng)的核心是數(shù)據(jù)管理系統(tǒng)。2、 數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展數(shù)據(jù)管理的發(fā)展經(jīng)歷了3個(gè)階段：（1） 人工管理階段主要用于科學(xué)計(jì)算，硬件沒(méi)有磁盤，數(shù)據(jù)被直接存取，軟件沒(méi)有操作系統(tǒng)。（2） 文件系統(tǒng)階段具有簡(jiǎn)單的數(shù)據(jù)共享和數(shù)據(jù)管理能力，無(wú)法提供統(tǒng)一的、完整的管理和數(shù)據(jù)共享能力。（3） 數(shù)據(jù)庫(kù)系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)階段具有以下特點(diǎn)：1、 數(shù)據(jù)的

35、集成性：采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)方式：按照多個(gè)應(yīng)用的需要組織全局的統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)；每個(gè)應(yīng)用的數(shù)據(jù)是全局結(jié)構(gòu)中的一部分。2、 數(shù)據(jù)的高共享性與低冗余性：數(shù)據(jù)共享可減少數(shù)制冗余及存儲(chǔ)空間，避免數(shù)據(jù)的不一致。3、 數(shù)據(jù)獨(dú)立性：這是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說(shuō)，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性分為物理獨(dú)立性和邏輯獨(dú)立性。4、 數(shù)據(jù)統(tǒng)一管理與控制：主要包含3個(gè)主面，即數(shù)據(jù)的完整性檢查、數(shù)據(jù)的安全性保護(hù)和并發(fā)控制。數(shù)據(jù)的恢復(fù)。5、 安全性控制：防止未經(jīng)授權(quán)的用戶有意或無(wú)意存取數(shù)據(jù)庫(kù)中的數(shù)據(jù)，以免數(shù)據(jù)被泄露、更改或破壞；完整

36、性控制：保證數(shù)據(jù)庫(kù)中數(shù)據(jù)及語(yǔ)義的正確性和有效性，防止任何對(duì)數(shù)據(jù)造成錯(cuò)誤的操作；并發(fā)控制：正確處理好多用戶、多任務(wù)環(huán)境下的并發(fā)操作，防止錯(cuò)誤發(fā)生；恢復(fù)：當(dāng)數(shù)據(jù)庫(kù)被破壞或數(shù)據(jù)不正確時(shí)，使數(shù)據(jù)庫(kù)能恢復(fù)到正確的狀態(tài)。3、 數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 數(shù)據(jù)庫(kù)的三級(jí)模式：概念模式、外模式、內(nèi)模式。 數(shù)據(jù)庫(kù)的二級(jí)映射：概念模式到內(nèi)模式的映射，外模式到概念模式的映射。內(nèi)模式是能夠給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方式。外模式是用戶的數(shù)據(jù)視圖。也就是用戶所見到的數(shù)據(jù)模式。概念模式是數(shù)據(jù)庫(kù)系統(tǒng)中全局邏輯結(jié)構(gòu)的描述，是全體用戶的公共數(shù)據(jù)視圖。數(shù)據(jù)庫(kù)技術(shù)的主要特點(diǎn)有以下幾個(gè)方面：數(shù)據(jù)的集成性，數(shù)據(jù)的高共享性與低冗余性，數(shù)

37、據(jù)獨(dú)立性，數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)的組織形式。分布式數(shù)據(jù)庫(kù)系統(tǒng)不具有的特點(diǎn)是數(shù)據(jù)冗余。而具有數(shù)據(jù)分布性、邏輯整體性、位置透明性和復(fù)制透明性、分布性。為用戶與數(shù)據(jù)庫(kù)系統(tǒng)提供接口的語(yǔ)言是匯編語(yǔ)言。（DDL）是數(shù)據(jù)描述語(yǔ)言，（DML）數(shù)據(jù)操縱語(yǔ)言。關(guān)系的完整性約束指關(guān)系的某種約束條件，包括實(shí)體完整性、參照完整性和用戶定義的完整性。其中，前兩種完整性約束由關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)自動(dòng)支持。17數(shù)據(jù)模型（數(shù)據(jù)庫(kù)設(shè)計(jì)的核心）1、 數(shù)據(jù)模型的基本概念 數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，而數(shù)據(jù)模型是數(shù)據(jù)特征的抽象。數(shù)據(jù)模型所描述的內(nèi)容有3個(gè)部分：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)

38、約束。數(shù)據(jù)模型按不同的應(yīng)用層次分成3種類型，分別是概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。 概念模型與具體的數(shù)據(jù)庫(kù)管理系統(tǒng)無(wú)關(guān)，與具體的計(jì)算機(jī)平臺(tái)無(wú)關(guān)。較為有名的概念模型有E-R模型、擴(kuò)充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。 邏輯數(shù)據(jù)模型又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫(kù)系統(tǒng)的模型。概念模型只有在轉(zhuǎn)換成數(shù)據(jù)模型后才能在數(shù)據(jù)庫(kù)中得以表示。大量使用過(guò)的邏輯數(shù)據(jù)模型有層次模型、網(wǎng)狀模型、關(guān)系模型（堅(jiān)實(shí)理論基礎(chǔ)）和面向?qū)ο竽Ｐ汀?物理數(shù)據(jù)模型又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。2、E-R模型 （1）E-R模型的基本概念現(xiàn)實(shí)世界中的事物可以抽象

39、成為實(shí)體，實(shí)體是概念世界中的基本單位，它們是客觀存在的且又能相互區(qū)別的事物。凡是有共性的實(shí)體可組成一個(gè)集合，稱為實(shí)體集。屬性刻畫了實(shí)體的特征。一個(gè)實(shí)體可以有若干個(gè)屬性。每個(gè)屬性可以有值，一個(gè)屬性的取值范圍稱為該屬性的值域或值集。（2）實(shí)體間的聯(lián)系 實(shí)體集間的聯(lián)系可以歸結(jié)為3類：a) 一對(duì)一的聯(lián)系，簡(jiǎn)記為1:1。b) 一對(duì)多的聯(lián)系，簡(jiǎn)記為M:1(m：1)或1:M（1:m）。c) 多對(duì)多的聯(lián)系，簡(jiǎn)記為M:N或m:n。（3）E-R模型的圖示法 E-R模型可以用一種直觀圖的形式來(lái)表示，這種圖稱為E-R圖。（4）一個(gè)關(guān)系中屬性個(gè)數(shù)為1時(shí)，稱此關(guān)系為一元關(guān)系。3、層次模型層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，自頂

40、向下，層次分明。由于層次模型形成早，受文件系統(tǒng)影響大，模型受限制多，物理成分復(fù)雜，操作與使用均不理想，且不適用于表示非層次性的聯(lián)系。4、 網(wǎng)狀模型 網(wǎng)狀模型是不加任何條件限制的無(wú)向圖。網(wǎng)狀模型在數(shù)據(jù)表示和數(shù)據(jù)操縱方面比層次模型更高效、更成熟。但網(wǎng)狀模型在使用時(shí)涉及系統(tǒng)內(nèi)部的物理因素較多，用戶使用操作并不方便，其數(shù)據(jù)模式與系統(tǒng)實(shí)現(xiàn)也不甚理想。5、 關(guān)系模型（1） 關(guān)系的數(shù)據(jù)結(jié)構(gòu)關(guān)系模型采用二維來(lái)表示，簡(jiǎn)稱表。二維表由表框架和表的元組組成。表框架由n個(gè)命名的屬性組成，每個(gè)屬性有一個(gè)取值范圍稱為值域。在框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組。在二維表中能唯一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼。二

41、維表中可能有若干個(gè)鍵，它們稱為該表的候選碼或候選鍵。從二維表的所有候選鍵中選取一個(gè)作為用戶使用的鍵稱為主鍵或主碼。表A中的某屬性集是某表B的鍵，則稱為該屬性集為A的外鍵或外碼。表中一定要有鍵，如果表中所有屬性的子集均不是鍵，則表中屬性的全集必為鍵。在關(guān)系元組的分量中允許出現(xiàn)空值表示信息空缺。主鍵中不允許出現(xiàn)空值。關(guān)系框架與關(guān)系元組構(gòu)成一個(gè)關(guān)系。一個(gè)語(yǔ)義相關(guān)的關(guān)系集合構(gòu)成一個(gè)關(guān)系數(shù)據(jù)庫(kù)。關(guān)系的框架稱為關(guān)系模式，而語(yǔ)義相關(guān)的關(guān)系模式集合構(gòu)成了關(guān)系數(shù)據(jù)庫(kù)模式。關(guān)系模式支持子模式，關(guān)系子模式是關(guān)系數(shù)據(jù)庫(kù)模式中用戶所見到的那部分?jǐn)?shù)據(jù)模式的描述。關(guān)系子模式也是二維表結(jié)構(gòu)，關(guān)系子模式對(duì)應(yīng)用戶數(shù)據(jù)庫(kù)稱為視圖。

42、（2） 關(guān)系的操縱關(guān)系模型的數(shù)據(jù)操縱，即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除及修改4種。（3） 關(guān)系中的數(shù)據(jù)約束關(guān)系模型允許定義3類數(shù)據(jù)約束，它們是實(shí)體完整性約束、參照完整性約束和用戶完整性約束。18關(guān)系代數(shù)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)建立在數(shù)學(xué)理論的基礎(chǔ)之上，使用關(guān)系代數(shù)可以表示關(guān)系模型的數(shù)據(jù)操作。由于操作是對(duì)關(guān)系的運(yùn)算，而關(guān)系是有序組的集合，因此，可以將操作看成是集合的運(yùn)算。1、 關(guān)系模型的基本運(yùn)算（1） 插入 設(shè)有關(guān)系R需插入若干元組，要插入的元組組成關(guān)系R，則插入可用集合并運(yùn)算表示為R并R。（2） 刪除 設(shè)有關(guān)系R需刪除若干元組，要?jiǎng)h除的元組組成關(guān)系R，則刪除可用集合差運(yùn)算表示為R-R。

43、（3） 修改 修改關(guān)系R內(nèi)的元組內(nèi)容可以用下面的方法實(shí)現(xiàn)：設(shè)需修改的元組構(gòu)成關(guān)系R，則先作刪除得R-R。設(shè)修改后的元組構(gòu)成關(guān)系R，此時(shí)將其插入即得到結(jié)果：（R-R）U R。（4） 查詢 投影運(yùn)算：投影運(yùn)算是在給定關(guān)系的某些域上進(jìn)行的運(yùn)算。經(jīng)過(guò)投影運(yùn)算后，會(huì)取消某些列，而且有可能出現(xiàn)一些重復(fù)元組。 選擇運(yùn)算：關(guān)系R通過(guò)選擇運(yùn)算后，由R中滿足邏輯條件的元組組成。 笛卡兒運(yùn)算：對(duì)于兩個(gè)關(guān)系的合并操作可以用笛卡兒積表示。設(shè)有n元關(guān)系R及m元關(guān)系S，它們分別有p、q個(gè)元組，則關(guān)系R與S經(jīng)笛卡兒積記為RXS.該關(guān)系是一個(gè)n+m元關(guān)系，元組個(gè)數(shù)是pXq，由R與S的有序組組合而成。2、 關(guān)系代數(shù)中的擴(kuò)充運(yùn)算（

44、1） 交運(yùn)算。關(guān)系R與S經(jīng)交運(yùn)算后所得到的關(guān)系是由那些既在R內(nèi)又在S內(nèi)的有序組所組成，記為RS（2） 除運(yùn)算。當(dāng)關(guān)系T=RXS時(shí)，則可將除運(yùn)算寫為T/RS。設(shè)有關(guān)系T、S，T能被R除的充分必要條件是：T中的域包含R中的所有屬性；T中有一些域不出現(xiàn)在R中。在除運(yùn)算中S的域由T中那些不出現(xiàn)在R中的域所組成。（3） 連接與自然連接運(yùn)算。連接運(yùn)算又可稱為連接運(yùn)算，通過(guò)它可以將兩個(gè)關(guān)系合并成一個(gè)大關(guān)系。注意：投影、選擇、連接是從二維表的列的方向來(lái)進(jìn)行運(yùn)算。19數(shù)據(jù)庫(kù)設(shè)計(jì)與管理 數(shù)據(jù)庫(kù)設(shè)計(jì)目前一般采用生命周期法，即將整個(gè)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的開發(fā)分解成目標(biāo)獨(dú)立的若干階段。它們是：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、編碼階段、測(cè)試階段、運(yùn)行階段、進(jìn)一步修改階段。1、 數(shù)據(jù)庫(kù)設(shè)計(jì)的需求分析 需求分析階段的任務(wù)是通過(guò)詳細(xì)調(diào)查現(xiàn)實(shí)世界要處理的對(duì)象，充分了解原系統(tǒng)的工作概況，明確用戶的各種需求，然后在此基礎(chǔ)