全國計算機培訓(xùn)第一課講義(共23頁)

1、全國(qun u)計算機二級考試C語言基礎(chǔ)知識講義(jingy)第一部分(b fen) 數(shù)據(jù)結(jié)構(gòu)第一章 算法和數(shù)據(jù)結(jié)構(gòu) 一、算法概述 1.算法概念：一系列解決問題的清晰的指令 2.算法基本特征：有窮性（步驟有限）、確定性（動作明確）、可行性（動作可行）。 3.算法基本要素：（1）對數(shù)據(jù)的運算和操作：算術(shù)運算加、減、乘、除等 邏輯運算與、或、非 關(guān)系運算大于、小于、等于、不等于 數(shù)據(jù)傳輸賦值、輸入、輸出（2）控制結(jié)構(gòu)：各操作之間的執(zhí)行順序順序、選擇、循環(huán)4.算法設(shè)計基本方法：遞推法、遞歸法、窮舉搜索法、貪婪發(fā)、分治法、動態(tài)規(guī)劃法、迭代法5.良好算法的設(shè)計要求：正確性、可讀性、健壯性、高效率、低存

2、儲6.算法的復(fù)雜度（考點） 時間復(fù)雜度：執(zhí)行算法所需要的計算工作量，即基本運算次數(shù) 空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間 注：同一個算法用不同語言實現(xiàn)，或用不同編譯程序編譯，或在不同計算機上運行，效率不同。 一個算法所占用的存儲空間包括算法程序所占存儲空間、輸入的初始數(shù)據(jù)所占存儲空間和算法執(zhí)行過程中所需要的額外空間。二、數(shù)據(jù)結(jié)構(gòu)概述1.相關(guān)概念 數(shù)據(jù)：描述客觀事物的數(shù)字、字符以及所有能夠輸入到計算機中并被計算機處理的信息的總稱。表示形式除了數(shù)字、字符之外，還可以是英文、漢字或其他語種字母組成的詞組、語句、以及表示圖形、圖象和聲音等。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進(jìn)行考慮和

3、處理。數(shù)據(jù)元素除了可以是一個數(shù)字或一個字符串以外，它也可以由一個或多個數(shù)據(jù)項 （數(shù)據(jù)項：有獨立含義的數(shù)據(jù)的最小單位，有時也稱為字段） 組成?！纠?1.1】如圖1-1中每個學(xué)生的學(xué)籍信息作為一個數(shù)據(jù)元素，在表中占一行。每個數(shù)據(jù)元素由序號、學(xué)號、姓名、性別、英語成績等7個數(shù)據(jù)項組成。圖1-1學(xué)籍表數(shù)據(jù)(shj)對象：具有相同性質(zhì)的數(shù)據(jù)元素的集合(jh)，是數(shù)據(jù)的一個子集。圖1-1中的整個學(xué)籍表可以(ky)看成一個數(shù)據(jù)對象。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯上的聯(lián)系，是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。如：線性結(jié)構(gòu)（學(xué)籍表）、樹結(jié)構(gòu)（家族譜系）、圖結(jié)構(gòu)（交通或通信網(wǎng)問題）。數(shù)據(jù)邏輯結(jié)構(gòu)根據(jù)其前后件關(guān)系的

4、復(fù)雜程度分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 線性結(jié)構(gòu)：有且只有一個根結(jié)點、每個結(jié)點最多只有一個前件，最多只有一個后件。非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)，即為非線性結(jié)構(gòu)。特點：邏輯結(jié)構(gòu)體現(xiàn)數(shù)據(jù)元素間的抽象化相互聯(lián)系，并不涉及數(shù)據(jù)元素在計算機中具體的存儲方式，是獨立于算機的。 數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器里的實現(xiàn)，又稱物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機。 數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：(1) 順序存儲法：把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。 順

5、序存儲法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)（如圖1-2）。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。圖1-2順序存儲注：順序存儲的地址是連續(xù)的，邏輯結(jié)構(gòu)與物理結(jié)構(gòu)相吻合。(2) 鏈接存儲法：該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu),通常借助于程序語言的指針類型描述（如圖1-3）。兩種表示形式如下：李四張三張三二元關(guān)系：若用D表示數(shù)據(jù)元素的集合，R表示數(shù)據(jù)元素之間的前后件關(guān)系，則一個數(shù)據(jù)結(jié)構(gòu)可以表示為B=（D，R）。 圖形表示：數(shù)據(jù)結(jié)點或結(jié)點 數(shù)據(jù)元素前后件關(guān)系單鏈表 二叉列表 圖1-3 鏈接(lin ji)存儲注

6、：數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為(chn wi)根結(jié)點、沒有后件的結(jié)點稱為終端結(jié)點。(3)索引(suyn)存儲法：該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引（Dense Index）。若一組結(jié)點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引(Spare Index)。索引項的一般形式是：(關(guān)鍵字、地址)關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引項的地址指示結(jié)點所在的存儲位置；稀疏索引中索引項的地址指示一組結(jié)點的起始存儲位置。(4)散列存儲法：該方法的基本思想是：根據(jù)結(jié)點的關(guān)鍵字直接計算

7、出該結(jié)點的存儲地址。 小結(jié)：四種基本存儲方法，既可單獨使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映像。 總結(jié)：同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運算方便及算法的時空要求。第二章 線性表一、線性表 1.線性表的定義：一個含有n(n0)個結(jié)點的有限序列，該結(jié)點集合中有且僅有一個開始結(jié)點（只有一個后繼，沒有前驅(qū)）和一個終端結(jié)點（只有一個前驅(qū)，沒有后繼），其余結(jié)點均有一個前驅(qū)和一個后繼。 2.線性表的順序存儲：用一組連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。當(dāng)線性表以順序存儲的方式存儲時又叫做順序表。 順序表的基本特征：線性表

8、中的所有元素所占用的存儲空間是連續(xù)的線性表中的所有元素存儲順序是按邏輯順序依次存放的 順序表可執(zhí)行的基本操作：（1）插入：在順序表中指定位置插入一個新的元素（2）刪除：在順序表中刪除指定的元素（3）查找：在順序表中查找某個特定元素（4）排序：對順序表中的元素進(jìn)行排序3.線性表的鏈接存儲3.1單鏈表1.單鏈表的定義：單鏈表是一種鏈?zhǔn)酱鎯Φ臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的 HYPERLINK /view/1223079.htm t _blank 存儲單元存放線性表中的 HYPERLINK /view/38785.htm t _blank 數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素( H

9、YPERLINK /view/38785.htm t _blank 數(shù)據(jù)元素的映象) + HYPERLINK /view/159417.htm t _blank 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。單鏈表的邏輯結(jié)構(gòu)如圖2-1所示。表示空表的單鏈表只有一個單元，即表頭單元head，其中的指針是空指針null。單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)，為找第 i 個 HYPERLINK /view/38785.htm t _blank 數(shù)據(jù)元素，必須先找到第 i-1 個數(shù)據(jù)元素。圖2-1 單鏈表2.單鏈表的類定義(dngy)typedef int ElemTyp

10、e;/假設(shè)結(jié)點(ji din)的數(shù)據(jù)類型為整型struct NodeType/結(jié)點類型定義 ElemType data; /結(jié)點的數(shù)據(jù)域 NodeType *next;/結(jié)點(ji din)的指針域;建立單鏈表的過程是一個動態(tài)生成鏈表的過程，即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點，并逐個插入鏈表，其時間復(fù)雜度為O(n)。 3.單鏈表的插入(1)插入操作的三種情況：在已知P指針?biāo)赶虻慕Y(jié)點后插入一個元素x。在p指針?biāo)赶虻慕Y(jié)點前插入一個元素x。在線性表中值為y的元素插入一個值為x的數(shù)據(jù)元素。(2)操作目標(biāo)：插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。

11、 (3)插入步驟： 找到ai-1存儲位置p 生成一個數(shù)據(jù)域為x的新結(jié)點*s 令結(jié)點*p的指針域指向新結(jié)點 新結(jié)點的指針域指向結(jié)點ai。 (4)插入操作代碼實現(xiàn)在已知P指針?biāo)赶虻慕Y(jié)點后插入一個元素x。 s=new NodeType; s-data=x; s-next=p-next; p-next=s;在p指針?biāo)赶虻慕Y(jié)點前插入一個元素x。q=head;while(q-next!=p)q=q-next;s=new NodeType;s-data=x;s-next=p-next;q-next=s; 在線性表中值為y的元素插入一個值為x的數(shù)據(jù)元素。q=head; p=q-next;while(p!=

12、NULL)&(p-data!=X)q=p; p=p-next;s=new NodeType;s-data=x;s-next=p-next;q-next=s; 4.單鏈表的刪除(shnch)(1)刪除(shnch)操作的三種(sn zhn)情況：刪除p所指向結(jié)點的后繼結(jié)點（假設(shè)存在）刪除p所指向的結(jié)點。刪除線性表中值為x的數(shù)據(jù)元素。 (2)操作目標(biāo)：刪除運算是將表的第i個結(jié)點刪去。(3)操作步驟： 找到ai-1的存儲位置p（因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中） 令p-next指向ai的直接后繼結(jié)點（即把ai從鏈上摘下） 釋放結(jié)點ai的空間，將其歸還給存儲

13、池。 (4)刪除操作代碼實現(xiàn)刪除p所指向結(jié)點的后繼結(jié)點（假設(shè)存在）q=p-next;p-next=q-next;delete q;刪除p所指向的結(jié)點。q=headwhile(q-next!=p)q+;q-next=p-next;delete p;刪除線性表中值為x的數(shù)據(jù)元素 q=head; p=q-next; while(p!=NULL)&(p-data!=x) q=p; p+; q-next=p-next; delete p;注：設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1in時是合法的。 當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不

14、意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p！=NULL）且*p不是終端結(jié)點（即p-next！=NULL）時，才能確定被刪結(jié)點存在。3.2循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，將單鏈表稍加改動，讓表中最后一個結(jié)點的指針指向單鏈表的表頭結(jié)點，這樣就形成了一個環(huán)鏈表。圖2-2 單循環(huán)鏈表1.單循環(huán)鏈表在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點或開始結(jié)點即可（如圖2-2）。判斷空鏈表的條件是head=head-next;2.雙向鏈表 雙向鏈表中有兩條方向不同的鏈，即每個結(jié)點中除next域存放后繼結(jié)點地址外，還增加(zngji)一個指向其直接前趨的指針域。圖2-3 雙向循環(huán)(xnhu

15、n)鏈表注意(zh y)： 雙鏈表由頭指針head惟一確定的。 帶頭結(jié)點的雙鏈表的某些運算變得方便。 將頭結(jié)點和尾結(jié)點鏈接起來，為雙向循環(huán)鏈表（如圖2-3）。二、棧（考點）1.棧的定義 棧（Stack）是一種“特殊的”線性表，這種線性表上的插入和刪除運算限定在表的某一端進(jìn)行的。(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。(2)當(dāng)表中沒有元素時稱為空棧。(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡稱為LIFO表。 棧的操作是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中最新的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的

16、底部，要到最后才能刪除(如圖2-4)。 圖2-4 棧 上圖中元素是以a1，a2，an的順序進(jìn)棧，退棧的次序卻是an，an-1，a1。2.棧的存儲：與線性表類似棧也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)。注：棧支持子程序調(diào)用。2.1順序棧 棧的順序存儲結(jié)構(gòu)亦稱為順序棧，它是運算受限的順序表。 1. 順序棧的類型定義 const int MAXSIZE=100; /假定預(yù)分配的棧空間最多為100個元素 typedef int ElemType;/假定棧元素的數(shù)據(jù)類型為整型 struct SqStack ElemType elemMAXSIZE; /一維數(shù)組 int top;/變量top指向最

17、后進(jìn)棧元素的位置 SqStack就是棧的順序存儲結(jié)構(gòu)的類型標(biāo)識符。 順序棧中元素用向量存放，即數(shù)組。 棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個端點，一般為向量低端，即數(shù)組首棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當(dāng)前棧頂位置圖2-5 順序(shnx)棧進(jìn)棧例:假設(shè)(jish)MAXSIZE取值為，圖2-5展示(zhnsh)了順序棧S中數(shù)據(jù)元素和棧頂指針的關(guān)系。圖a為空棧，指針top=-1；圖b為元素a1進(jìn)棧，指針top=0；圖c為元素a2、a3、a4依次進(jìn)棧，指針top依次遞增，top=3；圖d為元素a4退棧，指針top減一，top=2。

18、2. 順序棧的基本操作 前提條件：若棧底位置在向量的低端，即S0是棧底元素。（1）進(jìn)棧操作：進(jìn)棧時，需將top加1top=MAXSIZE-1表示棧滿上溢現(xiàn)象-當(dāng)棧滿時，再做進(jìn)棧運算產(chǎn)生空間溢出的現(xiàn)象。上溢是一種出錯狀態(tài)，應(yīng)設(shè)法避免。（2）退棧操作：退棧時，需將top減1top1 時，該結(jié)點的雙親結(jié)點編號為【i/2】； 若 2in ，它有編號為 2i 的左孩子，否則沒有左孩子； 若 2i+1n ，則它有編號為 2i+1 的右孩子，否則沒有右孩子。3.滿二叉樹和完全(wnqun)二叉樹(1)滿二叉樹：一棵深度(shnd)為k且有2k-1個結(jié)點(ji din)的二叉樹稱為滿二叉樹(如圖3-3(a)。

19、滿二叉樹的特點：每一層上的結(jié)點數(shù)都達(dá)到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層上。圖3-3滿二叉樹和完全二叉樹(2)完全二叉樹：若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹(如圖3-3(b)。注：(1) 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。(2) 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。(3) 在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子

20、，即該結(jié)點必是葉結(jié)點。 4.二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個元素可以有兩個后繼結(jié)點，因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子節(jié)點的存儲地址，稱為左指針域；另一個用于指向該結(jié)點的右子節(jié)點的存儲地址，稱為右指針域。5.二叉樹的遍歷所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，并且每個結(jié)點僅被訪問一次。（1）先序遍歷若二叉樹為空，則結(jié)束遍歷操作；否則：訪問根結(jié)點；先序遍歷左子樹；先序遍歷右子樹。（2）中序遍歷若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷

21、左子樹；訪問根結(jié)點；中序遍歷右子樹。（3）后序遍歷若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點?！纠?.1】寫出圖3-4所示的二叉樹的前序、中序和后序遍歷(bin l)的序列。圖3-4例3.1二叉樹前序遍歷(bin l)序列：ABCDEF 中序遍歷序列：CBDAEF 后序遍歷：CDBFEA第四章 查找(ch zho)和排序一、查找查找(Searching)的定義是：給定一個值K，在含有n個結(jié)點的表中找出關(guān)鍵字等于給定值K的結(jié)點。若找到，則查找成功，返回該結(jié)點的信息或該結(jié)點在表中的位置；否則查找失敗，返回相關(guān)的指示信息。通常，不同的數(shù)據(jù)結(jié)構(gòu)，將采用不同的查找方法。

22、1.順序查找 順序查找又稱順序搜索，一般是指在線性表中查找指定的元素，查找方法：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中所有的元素與被查元素進(jìn)行了比較但都不相等，則表示查找失敗。順序查找算法的時間復(fù)雜度如下：對于大的線性表來說，順序查找的效率是很低的，但在如下兩種情況下只能采用順序查找。無序線性表（表中元素的排列是無序的），不管是順序存儲，還是鏈?zhǔn)酱鎯?。鏈?zhǔn)酱鎯Φ挠行蚓€性表。2.二分法查找二分法查找只適用于順序存儲的有序表，所謂有序表是指線性表中的元素按值從小到大排列。設(shè)有序線性表的長度為n，被查元素為x，則二分查找的方法如下：將x與線

23、性表的中間項進(jìn)行比較。若中間項的值等于x，則說明查找成功，查找結(jié)束。若x小于中間項的值，則在線性表的前半部分以相同的方法進(jìn)行查找。若x大于中間項的值，則在線性表的后半部分以相同的方法進(jìn)行查找。重復(fù)如上查找過程，直到查找成功或子表長度為0為止。log2n在最好情況下，二分法查找只需比較一次即查找成功，最壞情況下需要比較log2n次。二、排序 在排序技術(shù)方面，主要考查簡單插入排序、簡單選擇排序、冒泡排序、堆排序等方法。簡單(jindn)插入排序法每次將一個(y )待排序的數(shù)據(jù)元素插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序，直到待排序數(shù)據(jù)元素全部插入完為止?！纠?.1】設(shè)有一組關(guān)鍵字序列

24、55，22，44，11，33，這里 n=5，即有5個記錄。請將其按由小到大的順序排序(pi x)。排序過程如圖4-1所示。圖4-1 插入排序示例 簡單選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完?！纠?.2】圖4-2是使用選擇排序法對序列3,4,1,5,2按照由小到大排序過程的示意圖。圖4-2 選擇排序示例冒泡排序兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。【例4.3】圖4-3是使用冒泡排序?qū)?、4、2、1、5按照從小到大排序過程的示意圖。圖4-3 冒泡排序示例堆

25、排序首先，將一個無序序列建成堆，然后，將堆頂元素與堆中的最后一個元素交換。不考慮已經(jīng)換到最后的那個元素，將剩下的狀個元素重新調(diào)整為堆，重復(fù)執(zhí)行此操作，直到所有元素有序為止。注：冒泡排序、簡單插入排序與簡單選擇排序法在最壞的情況下需要比較n(n-1)/2次，而堆排序在最壞情況下需要比較的次數(shù)是nlog2n。第二部分 軟件工程軟件工程概述1.軟件(run jin)的含義軟件指的是計算機系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)(shj)和相關(guān)文檔的完整集合。其中(qzhng)，程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計語言描述的、適合計算機執(zhí)行的指令序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)

26、結(jié)構(gòu)。文檔是與程序的開發(fā)、維護(hù)和使用有關(guān)的圖文資料。軟件的分類（考點）：軟件按功能可以分為應(yīng)用軟件、系統(tǒng)軟件和工具軟件（或支撐軟件）。應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件；系統(tǒng)軟件是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務(wù)的軟件；工具軟件是介于兩者之間，協(xié)助用戶開發(fā)軟件的工具性軟件2.軟件工程20世紀(jì)60年代計算機領(lǐng)域爆發(fā)“軟件危機”，表現(xiàn)在如下方面：軟件需求的增長得不到滿足，軟件開發(fā)成本和進(jìn)度無法控制，軟件質(zhì)量難以保證，軟件可維護(hù)性差，軟件的成本不斷提高，軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長。（考點）軟件工程的概念主要針對軟件危機提出來的，軟件工

27、程是指，采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開發(fā)與維護(hù)。軟件工程包括3個要素：方法、工具和過程。軟件工程學(xué)是研究軟件開發(fā)和維護(hù)的普遍原理與技術(shù)的一門工程學(xué)科。軟件工程學(xué)的主要研究對象包括軟件開發(fā)與維護(hù)的技術(shù)、方法、工具和管理等方面。3.軟件生命周期（考點）軟件生命周期是指軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的整個過程?？梢詫④浖芷诜譃槿缦?個時期8個階段：（1）軟件定義期：包括問題定義、可行性研究和需求分析3個階段；（2）軟件開發(fā)期：包括概要設(shè)計、詳細(xì)設(shè)計、實現(xiàn)和測試4個階段；（3）運行維護(hù)期：即運行維護(hù)階段。軟件生命周期各階段的主要任務(wù)如下： 問題定義：確定要求解決的問題

28、是什么可行性研究與計劃制定：決定該問題是否存在一個可行的解決辦法，確定待開發(fā)的軟件系統(tǒng)的開發(fā)目標(biāo)和總體要求，給出它的功能、性能、可靠性及接口等方面的方案，制訂完成開發(fā)任務(wù)的實施計劃。需求分析：對待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義，編寫軟件需求規(guī)格說明書、初步的用戶手冊和系統(tǒng)測試計劃提交評審。軟件設(shè)計：通常又分為概要設(shè)計和詳細(xì)設(shè)計兩個階段，在本環(huán)節(jié)，程序設(shè)計人員給出軟件的結(jié)構(gòu)、模塊的劃分、功能的分配以及處理流程。需要編寫概要設(shè)計說明書、詳細(xì)設(shè)計說明書和測試計劃初稿（集成測試計劃和單元測試計劃），提交評審。軟件實現(xiàn)：在軟件設(shè)計的基礎(chǔ)上編寫程序。同時需完成用戶手冊、操作手冊等面向用戶的文檔。

29、軟件測試：在設(shè)計測試用例的基礎(chǔ)上，檢驗軟件的各個組成部分。編寫測試分析報告。運行維護(hù)：將已交付的軟件投入運行，同時不斷的維護(hù)，進(jìn)行必要而且可行的擴充和刪改。軟件需求分析（考點）需求分析所要做的工作就是深入描述軟件的功能和性能，確定軟件設(shè)計的限制和軟件同其他系統(tǒng)元素的接口細(xì)節(jié)。結(jié)構(gòu)化分析法結(jié)構(gòu)化分析法是需求分析中使用最多的一種方法，它分析的對象是數(shù)據(jù)流，采用自頂向下、逐層分解、建立系統(tǒng)的處理流程，強調(diào)開發(fā)方法的結(jié)構(gòu)合理性及所開發(fā)軟件的結(jié)構(gòu)合理性的軟件開發(fā)方法。結(jié)構(gòu)化分析法的工具（考點）：數(shù)據(jù)流圖（Data Flow Diagram，DFD）（如表1）、數(shù)據(jù)字典（Data Dictionary，D

30、D）、結(jié)構(gòu)化語言、判定表和判定樹等。表1 數(shù)據(jù)流圖中主要圖形元素及說明軟件(run jin)需求規(guī)格說明書（以下(yxi)簡稱“需求(xqi)說明書”）軟件需求規(guī)格說明書是需求分析階段的最終成果，是軟件開發(fā)中的重要文檔之一。需求說明書的作用：便于用戶、開發(fā)人員進(jìn)行理解和交流；反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)，作為確認(rèn)測試和驗收的依據(jù)。需求說明書的內(nèi)容：把在軟件計劃中確定的軟件范圍加以展開，制定出完整的信息描述、詳細(xì)的功能說明、恰當(dāng)?shù)臋z驗標(biāo)準(zhǔn)以及其他與要求有關(guān)的數(shù)據(jù)。具體包括系統(tǒng)概述、數(shù)據(jù)描述、功能描述、性能描述、參考文獻(xiàn)、附錄等部分。需求說明書的特點：正確性、無歧義性、完

31、整性、可驗證性、一致性、可理解性、可修改性、可追蹤性。軟件設(shè)計軟件設(shè)計就是把軟件的需求分析變成軟件表示的過程，設(shè)計方法為結(jié)構(gòu)化設(shè)計法，按自頂向下，對各個層次的過程細(xì)節(jié)和數(shù)據(jù)細(xì)節(jié)逐層細(xì)化，直到用程序設(shè)計語言能夠?qū)崿F(xiàn)為止，從而最后確定整個體系結(jié)構(gòu)。注：面向?qū)ο缶哂蟹庋b性、繼承性和多態(tài)性三個特點，設(shè)計工具為UML語言。模塊模塊是指把一個待開發(fā)的軟件分解成若干個小的簡單的部分，解決一個復(fù)雜問題時自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。模塊獨立性是指，每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。模塊的獨立程度是評價設(shè)計好壞的重要度量標(biāo)準(zhǔn)，衡量指標(biāo)為內(nèi)聚性和耦合性。內(nèi)聚性

32、。一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度。包括偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚七種。內(nèi)聚性越強，模塊獨立性越強。耦合性。模塊間互相連接的緊密程度的設(shè)置。包括內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合七種。耦合性越弱，模塊獨立性越強?？傊瑑?yōu)秀軟件設(shè)計的原則為：高內(nèi)聚、低耦合。（重要考點）概要設(shè)計概要設(shè)計的主要任務(wù)是把 HYPERLINK /view/111493.htm t _blank 需求分析得到的DFD轉(zhuǎn)換為 HYPERLINK /view/600142.htm t _blank 軟件結(jié)構(gòu)和 HYPERLINK /view

33、/9900.htm t _blank 數(shù)據(jù)結(jié)構(gòu)。設(shè)計軟件結(jié)構(gòu)的具體任務(wù)是：將一個復(fù)雜系統(tǒng)按功能進(jìn)行模塊劃分、建立模塊的 HYPERLINK /view/420833.htm t _blank 層次結(jié)構(gòu)及調(diào)用關(guān)系、確定模塊間的接口及人機界面等。數(shù)據(jù) HYPERLINK /view/411272.htm t _blank 結(jié)構(gòu)設(shè)計包括數(shù)據(jù)特征的描述、確定數(shù)據(jù)的結(jié)構(gòu)特性、以及 HYPERLINK /view/1088.htm t _blank 數(shù)據(jù)庫的設(shè)計。顯然，概要設(shè)計建立的是目標(biāo)系統(tǒng)的邏輯模型，與計算機無關(guān)。典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)性面向數(shù)據(jù)流的設(shè)計方法：變換型系統(tǒng)結(jié)構(gòu)圖和事務(wù)性數(shù)據(jù)

34、流面向數(shù)據(jù)流設(shè)計方法的過程：（1）精化DFD。（2）確定DFD類型。（3）分解上層模塊、設(shè)計中、下層模塊結(jié)構(gòu)。（4）根據(jù)優(yōu)化準(zhǔn)則對軟件結(jié)構(gòu)求精。（5）描述模塊功能、接口及全局?jǐn)?shù)據(jù)結(jié)構(gòu)。（6）復(fù)查，進(jìn)入詳細(xì)設(shè)計。詳細(xì)設(shè)計詳細(xì) HYPERLINK /view/14417.htm t _blank 設(shè)計的主要 HYPERLINK /view/135914.htm t _blank 任務(wù)是設(shè)計每個模塊的實現(xiàn)算法、所需的局部 HYPERLINK /view/9900.htm t _blank 數(shù)據(jù)結(jié)構(gòu)。詳細(xì) HYPERLINK /view/14417.htm t _blank 設(shè)計的目標(biāo)有兩個：實現(xiàn)模塊

35、功能的算法要邏輯上正確和算法描述要簡明易懂。詳細(xì)設(shè)計的基本(jbn)任務(wù)：（1）為每個模塊確定采用的算法，選擇某種適當(dāng)?shù)墓ぞ弑磉_(dá)(biod)算法的過程，寫出模塊的詳細(xì)過程性描述。（2）確定每一模塊(m kui)使用的數(shù)據(jù)結(jié)構(gòu)。（3）確定模塊接口的細(xì)節(jié)，包括對系統(tǒng)外部的接口和用戶界面、對系統(tǒng)內(nèi)部吉他模塊的接口，以及模塊輸入、輸出數(shù)據(jù)及局部數(shù)據(jù)的全部細(xì)節(jié)。（4）為每一個模塊設(shè)計出一組測試用例。詳細(xì)設(shè)計的工具：圖形工具程序流程圖(PDF)、N-S圖、問題分析圖(PAD)和HIPO圖表格工具判定表語言工具PDL（偽碼）軟件測試軟件測試就是利用測試工具按照測試方案和流程對產(chǎn)品進(jìn)行功能和性能測試，甚至根據(jù)

36、需要編寫不同的測試工具，設(shè)計和維護(hù)測試系統(tǒng)，對測試方案可能出現(xiàn)的問題進(jìn)行分析和評估。執(zhí)行測試用例后，需要跟蹤故障，以確保開發(fā)的產(chǎn)品適合需求。軟件測試概述軟件測試的分類：從軟件的內(nèi)部結(jié)構(gòu)和具體的實現(xiàn)角度劃分，分為白盒測試、黑盒測試。從執(zhí)行程序的角度劃分，分為靜態(tài)測試和動態(tài)測試。按軟件開發(fā)過程階段劃分，分為單元測試、集成測試、確認(rèn)測試(驗收測試)和系統(tǒng)測試。軟件測試的步驟：(1) 單元測試 （2）集成測試 （3）確認(rèn)測試 （4）系統(tǒng)測試。軟件測試技術(shù)靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等?？梢杂扇斯みM(jìn)行，也可以借助軟件工具自動進(jìn)行。動態(tài)測試：是基于計算機的測試，目的是為了發(fā)現(xiàn)錯誤而執(zhí)

37、行程序的過程。白盒測試：也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試，它是按照程序內(nèi)部結(jié)構(gòu)進(jìn)行測試的程序，通過測試來檢測產(chǎn)品內(nèi)部是夠按照設(shè)計規(guī)格說明書的規(guī)定正常進(jìn)行。白盒測試的主要方法有邏輯覆蓋測試、基本路徑測試。黑盒測試：也稱功能測試，設(shè)計測試用例著眼于程序外部結(jié)構(gòu)，不考慮內(nèi)部邏輯結(jié)構(gòu)，主要針對軟件界面和軟件功能測試，在測試中，把程序看成一個不能打開的黑盒子，在完全不考慮程序內(nèi)部結(jié)構(gòu)和內(nèi)部特性的情況下，在程序接口進(jìn)行測試。主要測試方法有等價類劃分法、邊界值分析法、錯誤推測法、因果法等。程序的調(diào)試程序調(diào)試，是將編制的程序投入實際運行前，用手工或 HYPERLINK /view/454895.htm t _bla

38、nk 編譯程序等方法進(jìn)行測試，修正語法錯誤和邏輯錯誤的過程。這是保證計算機信息系統(tǒng)正確性的必不可少的步驟。程序調(diào)試的方法：靜態(tài)調(diào)試和動態(tài)調(diào)試程序經(jīng)常出現(xiàn)的錯誤類型：編輯錯誤、編譯錯誤、運行錯誤和邏輯錯誤。第三部分 數(shù)據(jù)庫設(shè)計基礎(chǔ)第一章 數(shù)據(jù)庫的基本概念一、數(shù)據(jù)庫相關(guān)概念數(shù)據(jù)處理包括對數(shù)據(jù)進(jìn)行收集、存儲、傳送、整理、檢索、計算、輸出等各種加工和管理。數(shù)據(jù)庫(DataBase,DB)是數(shù)據(jù)的集合，它有統(tǒng)一的結(jié)構(gòu)系統(tǒng)，存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各種應(yīng)用程序所共享。1.數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)(Database System,DBS)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平

39、臺、軟件平臺五部分(b fen)組成。硬件平臺包括計算機和網(wǎng)絡(luò)，軟件平臺包括操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)開發(fā)工具。2.數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)(Database Management System,DBS)是數(shù)據(jù)庫的機構(gòu)，用來幫助用戶建立、使用、管理、加工和維護(hù)數(shù)據(jù)庫而配置的專用系統(tǒng)軟件，它在操作系統(tǒng)的支持下對數(shù)據(jù)庫進(jìn)行統(tǒng)一(tngy)的管理和控制，并且其結(jié)構(gòu)復(fù)雜。它的具體功能如下：（1）數(shù)據(jù)(shj)模式定義 （2）數(shù)據(jù)存取的物理構(gòu)建 （3）數(shù)據(jù)操作（4）數(shù)據(jù)的完整性、安全性定義與檢查 （5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù) （6）數(shù)據(jù)的服務(wù)為完成以上六個功能，數(shù)據(jù)庫管理系統(tǒng)一般提供相應(yīng)的數(shù)據(jù)語言，包

40、括數(shù)據(jù)定義語言（Data Definition Language，DDL）、數(shù)據(jù)操縱語言（Data Manipulation Language，DML）、數(shù)據(jù)控制語言（Data Control Language，DCL）。3.數(shù)據(jù)庫應(yīng)用系統(tǒng)數(shù)據(jù)庫應(yīng)用系統(tǒng)（Database Application System，DBAS）是程序員根據(jù)用戶的需要在數(shù)據(jù)庫管理系統(tǒng)的支持下，用數(shù)據(jù)庫管理系統(tǒng)提供的命令編寫、開發(fā)并能夠在數(shù)據(jù)庫管理系統(tǒng)的支持下運行的程序和數(shù)據(jù)庫的總稱，如人事管理系統(tǒng)、物質(zhì)管理系統(tǒng)，包括硬件、操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用開發(fā)工具、應(yīng)用系統(tǒng)五個方面。二、數(shù)據(jù)庫系統(tǒng)的發(fā)展1.數(shù)據(jù)管理發(fā)展至今

41、經(jīng)歷了3個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。目前，根據(jù)數(shù)據(jù)之間的聯(lián)系方式劃分，數(shù)據(jù)庫系統(tǒng)先后經(jīng)歷層次數(shù)據(jù)庫、網(wǎng)狀數(shù)據(jù)庫和關(guān)系數(shù)據(jù)庫三種類型。2.數(shù)據(jù)庫系統(tǒng)具有如下特點：(1)數(shù)據(jù)的集成性 (2)數(shù)據(jù)高共享性與低冗余性 (3)數(shù)據(jù)獨立性 (4)數(shù)據(jù)的統(tǒng)一管理與控制3.關(guān)于數(shù)據(jù)庫的新技術(shù)，下面三種比較重要：（1）面向?qū)ο髷?shù)據(jù)庫系統(tǒng) （2）知識庫系統(tǒng) （3）關(guān)系數(shù)據(jù)庫系統(tǒng)的擴充三、數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu)數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)主要體現(xiàn)在三級模式和兩級映射上。1.數(shù)據(jù)庫系統(tǒng)的三級模式（考點） 數(shù)據(jù)模式是數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式，包括概念模式（又稱模式或邏輯模式）、外模式、內(nèi)模式

42、三個層次結(jié)構(gòu)，如圖1-1.圖1-1 三級模式圖模式的3個級別層次反映了模式的3個不同環(huán)境及它們的不同要求，其中內(nèi)模式處于底層，它是數(shù)據(jù)物理結(jié)構(gòu)和存儲方式的描述，是數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式，概念模式處于中層，它反映了設(shè)計者的數(shù)據(jù)全局邏輯要求，而外模式處于最外層，它反映了用戶對數(shù)據(jù)的要求。一個數(shù)據(jù)庫只有一個概念模式和內(nèi)模式，可以有多個外模式。概念模式是數(shù)據(jù)庫的中心和關(guān)鍵(gunjin)。內(nèi)模式依賴于概念模式，獨立于外模式和存儲設(shè)備；外模式面向(min xin)具體的應(yīng)用，獨立于內(nèi)模式和存儲設(shè)備；應(yīng)用程序依賴于外模式，獨立于概念模式和內(nèi)模式。2.數(shù)據(jù)庫系統(tǒng)的兩級映射(yngsh)外模式/模式映射：

43、把基于外模式的用戶操作轉(zhuǎn)換成對模式中數(shù)據(jù)的訪問。模式/內(nèi)模式映射：把模式中數(shù)據(jù)的邏輯定位映射成內(nèi)模式中數(shù)據(jù)的物理存儲位置。第二章 數(shù)據(jù)模型一、數(shù)據(jù)模型概述 1.數(shù)據(jù)模型是現(xiàn)實世界中數(shù)據(jù)特征的抽象，為數(shù)據(jù)庫系統(tǒng)的信息表達(dá)與操作提供一個抽象的框架。數(shù)據(jù)模型所描述的內(nèi)容包括3個部分：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。 2.數(shù)據(jù)模型分類：概念模型、邏輯數(shù)據(jù)模型（又稱數(shù)據(jù)模型）和物理模型。 3.數(shù)據(jù)庫領(lǐng)域中最常用的四種數(shù)據(jù)模型：層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ汀６?、E-R模型 概念模型中被廣泛使用的模型是E-R模型，該模型將現(xiàn)實世界的要求轉(zhuǎn)化成實體、聯(lián)系、屬性等幾個基本概念，以及它們間的兩種基本連

44、接關(guān)系，并且可以用一種圖非常直觀地表示出來。 1.E-R模型的基本概念 （1）實體。現(xiàn)實世界中的事物都可以抽象成實體，實體是概念世界中的基本單位，它們是客觀存在的且又能相互區(qū)別的事物。凡是有共性的實體可組成一個集合稱為實體集。 （2）屬性?，F(xiàn)實世界中事物的特性。 （3）聯(lián)系?，F(xiàn)實世界中事物間的關(guān)聯(lián)稱為聯(lián)系。兩個實體集間的聯(lián)系實際上是實體集間的函數(shù)關(guān)系，這種函數(shù)關(guān)系有三種：一對一的聯(lián)系、一對多或多對一聯(lián)系、多對多聯(lián)系。(如圖1-2)圖1-2聯(lián)系的三種類型2.E-R模型的圖示法 E-R模型可以用一種非常直觀的圖的形式表示，這種圖稱為E-R圖。 （1）實體集表示法。在E-R圖中用矩形表示實體集，如圖

45、1-3。 （2）屬性表示法。在E-R圖中用橢圓形表示屬性，如圖1-4。 （3）聯(lián)系表示法。在E-R圖中用菱形表示聯(lián)系，如圖1-5。 圖1-3 實體集表示法 圖1-4 屬性表示法 圖1-5聯(lián)系表示法三、關(guān)系模型關(guān)系模型采用二維表來表示，簡稱表（如圖1-6）。二維表由表框架及表的元組組成。表框架由n個命名的屬性組成，n稱為屬性元數(shù)。每個屬性有一個取值范圍稱為值域。表框架對應(yīng)了關(guān)系的模式，即類型的概念。1. 關(guān)系模型的主要特點：一個表中不允許出現(xiàn)相同的兩個字段名。一個表中不允許出現(xiàn)完全相同的兩行一個表中同一列的數(shù)據(jù)項必須是類型相同數(shù)據(jù)一個表中每一行中與每一列中的數(shù)據(jù)項都是不可拆分的基本數(shù)據(jù)項一個表中

46、行或列的順序改變都不影響表格所描述(mio sh)的內(nèi)容。圖1-6 表2.關(guān)系模型的重要(zhngyo)概念(1)關(guān)系(gun x)：一個關(guān)系就是一張二維表，通常將一個沒有重復(fù)行，重復(fù)列的二維表看成一個關(guān)系，每個關(guān)系都有一個關(guān)系名。(2)元組：二維表的每一行在關(guān)系中稱為元組。(3)屬性：二維表的每一列在關(guān)系中稱為屬性，每個屬性都有一個屬性名，屬性值則是各元組屬性的取值。(4)域：屬性的取值范圍稱為域。域作為屬性值的集合，其類型與范圍由屬性的性質(zhì)及其所表示的意義具體確定。同一屬性只能在相同域中取值。 (5)關(guān)鍵字：關(guān)系中能惟一區(qū)分、確定不同元組的屬性或?qū)傩越M合，稱為該關(guān)系的一個關(guān)鍵字。單個屬性組

47、成的關(guān)鍵字稱為單關(guān)鍵字。需要強調(diào)的是，關(guān)鍵字的屬性值不能取“空值。所謂空值就是“不知道或“不確定的值，因而空值無法惟一地區(qū)分、確定元組。 (6)候選關(guān)鍵字：關(guān)系中能夠成為關(guān)鍵字的屬性或?qū)傩越M合可能不是惟一的。凡在關(guān)系中能夠惟一區(qū)分確定不同元組的屬性或?qū)傩越M合，稱為候選關(guān)鍵字。(7)主關(guān)鍵字：在候選關(guān)鍵字中選定一個作為關(guān)鍵字，稱為該關(guān)系的主關(guān)鍵字。關(guān)系中主關(guān)鍵字是惟一的。(8)外部關(guān)鍵字：關(guān)系中某個屬性或?qū)傩越M合并非關(guān)鍵字，但卻是另一個關(guān)系的主關(guān)鍵字，稱此屬性或?qū)傩越M合為本關(guān)系的外部關(guān)鍵字。關(guān)系之間的聯(lián)系是通過外部關(guān)鍵字實現(xiàn)的。3.關(guān)系模型的操作：增加、刪除、修改、查詢。4. 數(shù)據(jù)約束數(shù)據(jù)庫完整

48、性是指數(shù)據(jù)庫中數(shù)據(jù)的正確性、有效性和相容性。數(shù)據(jù)庫完整性由各種各樣的完整性約束來保證，關(guān)系模型允許定義3類數(shù)據(jù)約束：實體完整性約束：一個關(guān)系應(yīng)該有一個或多個候選關(guān)鍵字參照完整性約束：參照完整性屬于表間規(guī)則，目的是保證數(shù)據(jù)的一致性。對于永久關(guān)系的相關(guān)表，在更新、插入或刪除記錄時，如果只改其一不改其二，就會影響數(shù)據(jù)的完整性：例如修改父表中關(guān)鍵字值后，子表關(guān)鍵字值未做相應(yīng)改變；刪除父表的某記錄后，子表的相應(yīng)記錄未刪除，致使這些記錄成為孤立記錄；對于子表插入的記錄，父表中沒有相應(yīng)關(guān)鍵字值的記錄；等等。對于這些設(shè)計表間數(shù)據(jù)的完整性，統(tǒng)稱為參照完整性。用戶定義的完整性約束：就是指明關(guān)系中屬性的取值范圍，也

49、就是屬性的域，即限制關(guān)系中的屬性的取值類型及取值范圍。如學(xué)生成績?nèi)≈捣秶?-100。四、關(guān)系代數(shù)（考點） 運算對象：一個或多個二維表 運算結(jié)果：一個新的二維表 運算種類：傳統(tǒng)運算并 、交 、差-（相減）、笛卡爾積 (運算從關(guān)系的水平（行）的角度來進(jìn)行）；專門運算選擇 、投影 、連接、除（運算不僅涉及行而且涉及列）1.并：由屬于進(jìn)行運算的兩個關(guān)系的全部元組組成的集合。 關(guān)系(gun x)stu1 關(guān)系(gun x)stu2 stu1stu22.交：由屬于(shy)進(jìn)行運算的兩個關(guān)系所共有的元組組成的集合。 關(guān)系stu1 關(guān)系stu2 stu1 stu23.差：由屬于前一個關(guān)系的元組但不屬于后一個關(guān)系的元組組成的集合。 關(guān)系stu1 關(guān)系stu2 stu1-stu24.笛卡爾積 關(guān)系R 關(guān)系S R x S5.選擇：根據(jù)選擇條件調(diào)取表中某行的運算 表stu 性別 = 男（s