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

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

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

3、處理。數(shù)據(jù)元素除了可以是一個(gè)數(shù)字或一個(gè)字符串以外，它也可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng) （數(shù)據(jù)項(xiàng)：有獨(dú)立含義的數(shù)據(jù)的最小單位，有時(shí)也稱為字段） 組成。【例 1.1】如圖1-1中每個(gè)學(xué)生的學(xué)籍信息作為一個(gè)數(shù)據(jù)元素，在表中占一行。每個(gè)數(shù)據(jù)元素由序號(hào)、學(xué)號(hào)、姓名、性別、英語成績(jī)等7個(gè)數(shù)據(jù)項(xiàng)組成。圖1-1學(xué)籍表數(shù)據(jù)(shj)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合(jh)，是數(shù)據(jù)的一個(gè)子集。圖1-1中的整個(gè)學(xué)籍表可以(ky)看成一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯上的聯(lián)系，是對(duì)數(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)：有且只有一個(gè)根結(jié)點(diǎn)、每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，最多只有一個(gè)后件。非線性結(jié)構(gòu)：不是線性結(jié)構(gòu)，即為非線性結(jié)構(gòu)。特點(diǎn)：邏輯結(jié)構(gòu)體現(xiàn)數(shù)據(jù)元素間的抽象化相互聯(lián)系，并不涉及數(shù)據(jù)元素在計(jì)算機(jī)中具體的存儲(chǔ)方式，是獨(dú)立于算機(jī)的。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)，又稱物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用以下四種基本存儲(chǔ)方法得到：(1) 順序存儲(chǔ)法：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。 順

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

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

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

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

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

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

11、 (3)插入步驟： 找到ai-1存儲(chǔ)位置p 生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*s 令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn) 新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。 (4)插入操作代碼實(shí)現(xiàn)在已知P指針?biāo)赶虻慕Y(jié)點(diǎn)后插入一個(gè)元素x。 s=new NodeType; s-data=x; s-next=p-next; p-next=s;在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)元素x。q=head;while(q-next!=p)q=q-next;s=new NodeType;s-data=x;s-next=p-next;q-next=s; 在線性表中值為y的元素插入一個(gè)值為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é)點(diǎn)的后繼結(jié)點(diǎn)（假設(shè)存在）刪除p所指向的結(jié)點(diǎn)。刪除線性表中值為x的數(shù)據(jù)元素。 (2)操作目標(biāo)：刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。(3)操作步驟： 找到ai-1的存儲(chǔ)位置p（因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中） 令p-next指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下） 釋放結(jié)點(diǎn)ai的空間，將其歸還給存儲(chǔ)

13、池。 (4)刪除操作代碼實(shí)現(xiàn)刪除p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)（假設(shè)存在）q=p-next;p-next=q-next;delete q;刪除p所指向的結(jié)點(diǎn)。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個(gè)結(jié)點(diǎn)僅當(dāng)1in時(shí)是合法的。 當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不

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

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

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

17、后進(jìn)棧元素的位置 SqStack就是棧的順序存儲(chǔ)結(jié)構(gòu)的類型標(biāo)識(shí)符。 順序棧中元素用向量存放，即數(shù)組。 棧底位置是固定不變的，可設(shè)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)，一般為向量低端，即數(shù)組首棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量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)棧時(shí)，需將top加1top=MAXSIZE-1表示棧滿上溢現(xiàn)象-當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。（2）退棧操作：退棧時(shí)，需將top減1top1 時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為【i/2】； 若 2in ，它有編號(hào)為 2i 的左孩子，否則沒有左孩子； 若 2i+1n ，則它有編號(hào)為 2i+1 的右孩子，否則沒有右孩子。3.滿二叉樹和完全(wnqun)二叉樹(1)滿二叉樹：一棵深度(shnd)為k且有2k-1個(gè)結(jié)點(diǎn)(ji din)的二叉樹稱為滿二叉樹(如圖3-3(a)。

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

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

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

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

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

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

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

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

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

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

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

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

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

32、。一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度。包括偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚、功能內(nèi)聚七種。內(nèi)聚性越強(qiáng)，模塊獨(dú)立性越強(qiáng)。耦合性。模塊間互相連接的緊密程度的設(shè)置。包括內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非直接耦合七種。耦合性越弱，模塊獨(dú)立性越強(qiáng)?？傊?，優(yōu)秀軟件設(shè)計(jì)的原則為：高內(nèi)聚、低耦合。（重要考點(diǎn)）概要設(shè)計(jì)概要設(shè)計(jì)的主要任務(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è)計(jì)軟件結(jié)構(gòu)的具體任務(wù)是：將一個(gè)復(fù)雜系統(tǒng)按功能進(jìn)行模塊劃分、建立模塊的 HYPERLINK /view/420833.htm t _blank 層次結(jié)構(gòu)及調(diào)用關(guān)系、確定模塊間的接口及人機(jī)界面等。數(shù)據(jù) HYPERLINK /view/411272.htm t _blank 結(jié)構(gòu)設(shè)計(jì)包括數(shù)據(jù)特征的描述、確定數(shù)據(jù)的結(jié)構(gòu)特性、以及 HYPERLINK /view/1088.htm t _blank 數(shù)據(jù)庫的設(shè)計(jì)。顯然，概要設(shè)計(jì)建立的是目標(biāo)系統(tǒng)的邏輯模型，與計(jì)算機(jī)無關(guān)。典型的數(shù)據(jù)流類型有兩種：變換型和事務(wù)性面向數(shù)據(jù)流的設(shè)計(jì)方法：變換型系統(tǒng)結(jié)構(gòu)圖和事務(wù)性數(shù)據(jù)

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

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

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

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

38、nk 編譯程序等方法進(jìn)行測(cè)試，修正語法錯(cuò)誤和邏輯錯(cuò)誤的過程。這是保證計(jì)算機(jī)信息系統(tǒng)正確性的必不可少的步驟。程序調(diào)試的方法：靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試程序經(jīng)常出現(xiàn)的錯(cuò)誤類型：編輯錯(cuò)誤、編譯錯(cuò)誤、運(yùn)行錯(cuò)誤和邏輯錯(cuò)誤。第三部分 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)第一章 數(shù)據(jù)庫的基本概念一、數(shù)據(jù)庫相關(guān)概念數(shù)據(jù)處理包括對(duì)數(shù)據(jù)進(jìn)行收集、存儲(chǔ)、傳送、整理、檢索、計(jì)算、輸出等各種加工和管理。數(shù)據(jù)庫(DataBase,DB)是數(shù)據(jù)的集合，它有統(tǒng)一的結(jié)構(gòu)系統(tǒng)，存放于統(tǒng)一的存儲(chǔ)介質(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、臺(tái)、軟件平臺(tái)五部分(b fen)組成。硬件平臺(tái)包括計(jì)算機(jī)和網(wǎng)絡(luò)，軟件平臺(tái)包括操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)開發(fā)工具。2.數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)(Database Management System,DBS)是數(shù)據(jù)庫的機(jī)構(gòu)，用來幫助用戶建立、使用、管理、加工和維護(hù)數(shù)據(jù)庫而配置的專用系統(tǒng)軟件，它在操作系統(tǒng)的支持下對(duì)數(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ù)為完成以上六個(gè)功能，數(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)的支持下運(yùn)行的程序和數(shù)據(jù)庫的總稱，如人事管理系統(tǒng)、物質(zhì)管理系統(tǒng)，包括硬件、操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、應(yīng)用開發(fā)工具、應(yīng)用系統(tǒng)五個(gè)方面。二、數(shù)據(jù)庫系統(tǒng)的發(fā)展1.數(shù)據(jù)管理發(fā)展至今

41、經(jīng)歷了3個(gè)階段：人工管理階段、文件系統(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)具有如下特點(diǎn)：(1)數(shù)據(jù)的集成性 (2)數(shù)據(jù)高共享性與低冗余性 (3)數(shù)據(jù)獨(dú)立性 (4)數(shù)據(jù)的統(tǒng)一管理與控制3.關(guān)于數(shù)據(jù)庫的新技術(shù)，下面三種比較重要：（1）面向?qū)ο髷?shù)據(jù)庫系統(tǒng) （2）知識(shí)庫系統(tǒng) （3）關(guān)系數(shù)據(jù)庫系統(tǒng)的擴(kuò)充三、數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu)數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)主要體現(xiàn)在三級(jí)模式和兩級(jí)映射上。1.數(shù)據(jù)庫系統(tǒng)的三級(jí)模式（考點(diǎn)） 數(shù)據(jù)模式是數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)的一種表示形式，包括概念模式（又稱模式或邏輯模式）、外模式、內(nèi)模式

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

43、把基于外模式的用戶操作轉(zhuǎn)換成對(duì)模式中數(shù)據(jù)的訪問。模式/內(nèi)模式映射：把模式中數(shù)據(jù)的邏輯定位映射成內(nèi)模式中數(shù)據(jù)的物理存儲(chǔ)位置。第二章 數(shù)據(jù)模型一、數(shù)據(jù)模型概述 1.數(shù)據(jù)模型是現(xiàn)實(shí)世界中數(shù)據(jù)特征的抽象，為數(shù)據(jù)庫系統(tǒng)的信息表達(dá)與操作提供一個(gè)抽象的框架。數(shù)據(jù)模型所描述的內(nèi)容包括3個(gè)部分：數(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)實(shí)世界的要求轉(zhuǎn)化成實(shí)體、聯(lián)系、屬性等幾個(gè)基本概念，以及它們間的兩種基本連

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

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

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

47、成的關(guān)鍵字稱為單關(guān)鍵字。需要強(qiáng)調(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)鍵字中選定一個(gè)作為關(guān)鍵字，稱為該關(guān)系的主關(guān)鍵字。關(guān)系中主關(guān)鍵字是惟一的。(8)外部關(guān)鍵字：關(guān)系中某個(gè)屬性或?qū)傩越M合并非關(guān)鍵字，但卻是另一個(gè)關(guān)系的主關(guān)鍵字，稱此屬性或?qū)傩越M合為本關(guān)系的外部關(guān)鍵字。關(guān)系之間的聯(lián)系是通過外部關(guān)鍵字實(shí)現(xiàn)的。3.關(guān)系模型的操作：增加、刪除、修改、查詢。4. 數(shù)據(jù)約束數(shù)據(jù)庫完整

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

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