陽光計算機學校教學公共基礎課件

二級公共基礎知識1二級公共基礎知識第一章算法與數(shù)據(jù)結構第二章程序設計基礎第三章軟件工程基礎第四章數(shù)據(jù)庫設計基礎第一章算法與數(shù)據(jù)結構第二章程序設計基礎第三章軟件工程基礎第四章數(shù)據(jù)庫設計基礎2第一章算法與數(shù)據(jù)結構一、算法二、數(shù)據(jù)結構三、線性表四、棧五、隊列六、線性鏈表七、樹與二叉樹八、查找技術九、排序技術一、算法二、數(shù)據(jù)結構三、線性表四、棧五、隊列六、線性鏈表七、樹與二叉樹八、查找技術九、排序技術3一、算法1.算法的基本概念算法是指解題方案準確而完整的描述。（1）算法的特征：

可行性、確定性、有窮性、擁有足夠的情報。（2）算法的兩個基本要素：

一是對數(shù)據(jù)對象的運算和操作，具體包括算術運算、邏輯運算、關系運算和數(shù)據(jù)傳輸?shù)龋?/p>

二是算法的控制結構，具體包括順序結構、選擇結構和循環(huán)結構。42.算法的復雜度算法的復雜度：是衡量算法好壞的量度，具體可分為兩種:時間復雜度和空間復雜度。（1）時間復雜度是指執(zhí)行算法所需要的計算工作量，即算法執(zhí)行過程中所需要的基本運算次數(shù)。

（2）空間復雜度是指執(zhí)行該算法所需要的內(nèi)存空間。具體包括（1）算法程序所占的空間；（2）輸入的初始數(shù)據(jù)所占的存儲空間；（3）算法執(zhí)行過程中的額外空間5二、數(shù)據(jù)結構1.數(shù)據(jù)結構的基本概念數(shù)據(jù)結構就是相互有關聯(lián)的數(shù)據(jù)元素的集合。一年四季：春、夏、秋、冬家庭成員：父親、兒子、女兒6春夏秋冬父親兒子女兒一個數(shù)據(jù)結構應包含兩方面信息：1、表示數(shù)據(jù)元素的信息；2、表示各數(shù)據(jù)元素之間的前后件關系。7數(shù)據(jù)結構有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構、數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系，從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。數(shù)據(jù)的存儲結構是指數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式；存儲結構的存儲方式有：順序存儲和鏈式存儲。數(shù)據(jù)的運算即算法。8在數(shù)據(jù)結構中，沒有前件的節(jié)點稱為根節(jié)點；沒有后件的節(jié)點稱為終端節(jié)點（也稱為葉子節(jié)點）；除了根節(jié)點與終端節(jié)點外的其他節(jié)點稱為內(nèi)部節(jié)點。d1d3d7d6d2d4d59數(shù)據(jù)的邏輯結構分為兩種:線性結構和非線性結構。

線性結構：有且只有一個根結點；每一個結點最多有一個前件，也最多有一個后件。如：一年四季。

非線性結構：如果一個數(shù)據(jù)結構不是線性結構，則稱之為存儲結構。如：反映家庭成員間輩分關系的數(shù)據(jù)結構。10A.線性結構

①線性表

②棧——先進后出的線性表③隊列——先進先出的線性表如下“學生成績表”就是線性表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號11B.非線性結構

①樹型結構（樹、二叉樹）

例:全校學生檔案管理的組織方式12三、線性表線性表是最簡單的、最常用的一種線性結構。線性表（非空線性表）必須同時滿足以下3個條件：

（1）有且只有一個根結點a1，它無前件。

（2）有且只有一個終端結點an，它無后件。

（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號131.線性表的順序存儲結構

特點：

（1）線性表中所有元素所占的存儲空間是連續(xù)的;

（2）線性表中各數(shù)據(jù)元素在存儲空間中的存放順序是按邏輯順序依次存放的。如圖所示

A1A2A3A4計算機的內(nèi)存空間102104106108110112114A1A2A3A4線性表14例：正確表示線性表(A1，A2，A3，A4)的順序結構是( )

A)

B)

C)

A1A2A3A4分析：選C，選項C中線性表各元素的存儲空間是連續(xù)的，而且元素的存儲順序與邏輯順序一致。選項A中各元素的物理順序與邏輯順序不同。選項B中各元素所占的存儲空間并不連續(xù)。15六、線性鏈表1.鏈式存儲結構

對于大的線性表或者變動頻繁的線性表不宜用順序存儲，應該采用鏈式存儲。16鏈式存儲的過程如圖所示。A1A2A3A4線性表A4A1A3A2計算機的內(nèi)存空間102104106108110112114A1114A2110A3104A4…108114110104鏈式存儲每個存儲空間都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素值，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。數(shù)據(jù)域指針域17四、棧1.棧的定義：

棧是一種特殊的線性表，特殊在其數(shù)據(jù)操作上，即限定在一端進行插入與刪除的線性表。在棧中，允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。往棧中插入一個元素叫入棧運算從棧中刪除一個元素稱為退棧運算棧的數(shù)據(jù)操作原則是先進后出或后進先出。18

棧的示意圖：192.棧的基本運算

有三種:入棧、退棧和讀棧頂元素。

(1)入棧運算：

值得注意的是，在入棧運算中應避免上溢錯誤的出現(xiàn)。上溢錯誤是指當棧頂指針己經(jīng)指向存儲空間的最后一個位置時，說明棧的空間己滿，不能再進行入棧操作，這種情況稱為?！吧弦纭卞e誤。(2)退棧運算：

值得注意的是，退棧運算中應避免“下溢”錯誤的出現(xiàn)。下溢錯誤是指當棧頂指針為0時，說明棧空，不可能在進行退棧操作，這種情況稱為?！跋乱纭卞e誤。20(3)讀棧頂元素：

讀棧頂元素是指將棧頂元素賦值給一個指定的變量21五、隊列1.隊列的基本概念：隊列是一種只允許在一端進行插入，而在另一端進行刪除的線性表，它也是一種特殊的線性表。允許插入的一端叫隊尾(尾指針，Rear，指向隊尾元素)，允許刪除的一端叫隊頭(頭指針，F(xiàn)ront，指向隊頭元素的前一個位置)。

隊列的數(shù)據(jù)操作方法:先進先出。退隊入隊ACBDEfrontrear22Q(1:8)8rear→7F6E5D4C3B2Afront→1一個隊列Q(1:8)87F6E5D4C3B21front→rear→刪除一個元素后的隊列Q(1:8)8X7F6E5D4C3Bfront→

2rear→插入一個元素X后的隊列232.循環(huán)隊列

在實際應用中，隊列的順序存儲結構一般采用循環(huán)隊列的形式。原理:循環(huán)隊列是指當隊列存儲空

間的最后一個位置己被使用而仍

要進行入隊運算，這時只要存儲

空間的第一個位置空閑，便可以

將元素加入到這個位置，即將存

儲空間的第一個位置作為隊尾，

如圖所示。24例：圖（a）是一個容量為8的循環(huán)隊列存儲空間，且其中已有6個元素。圖（b）是在圖（a）的循環(huán)隊列中又加入了兩個元素后的狀態(tài)。圖（c）是在圖（b）的循環(huán)隊列中退出了1個元素后的狀態(tài)。Q(1:8)8rear→7F6E5D4C3B2Afront→1Q(1:8)8X7F6E5D4C3B2Afront→rear→1YQ(1:8)8X7F6E5D4C3Bfront→

2rear→1Y（a）具有6個元素的循環(huán)隊列（b）加入X、Y后的循環(huán)隊列（c）退出一個元素后的循環(huán)隊列25七、樹與二叉樹1.樹樹是一種非線性結構。ABDCEFGHIJKLM26在樹結構中，每個結點只有一

個前件，稱為父結點，沒有前

件的結點只有一個，稱為樹的

根結點，簡稱為樹的根。如圖

所示的結點A就是樹的根。在樹結構中，每個結點可以有

多個后件，它們都稱為該結點的子結點。沒有后件的結點稱為葉子結點。如圖所示的結點K,L,F,G,M,I,J都是葉子結點。在樹結構中，每個結點所擁有的后件個數(shù)稱為該結點的度。例如圖中結點D的度為3。ABDCEFGHIJKLM27在樹中，所有結點中的最大的度稱為

樹的度。如圖示的樹的度為3。樹結構具有明顯的層次關系，即樹

是一種層次結構。在樹結構中，一

般有如下分層:根結點在第一層，

依次類推。樹的最大層次稱為樹的深度。如圖所示的樹的深度為4。ABDCEFGHIJKLM282.二叉樹（1）二叉樹的定義

二叉樹是一種特殊的樹，非空二叉樹只有一個根結點。如圖所示，每個根結點最多有兩棵子樹，分別稱為該結點的左子樹和右子樹。ABDEJKH左子樹右子樹根2930（2）二叉樹的性質(zhì)：性質(zhì)1:

在二叉樹的第k層上，最多有2k-1（k>1）個結點。423167531性質(zhì)2：深度為m的二叉樹最多有2m-1個結點。423167532性質(zhì)3：在任意一棵二叉樹中，度為0的結點(葉子結點)總比度為2的結點多一個。4231675n0=n2+1n2=n0-133性質(zhì)4：具有n個結點的二叉樹，其深度至少為[log2n]+1。其中，[log2n]表示取log2n的整數(shù)部分423167534（3）滿二叉樹

滿二叉樹是特殊的二叉樹。滿二叉樹是指除最后一層之外，每一層上的所有結點都有兩個子結點。結構如圖所示：35（4）完全二叉樹

完全二叉樹也是一種特殊的二叉樹。特殊在:除最后一層之外，每一層上的結點數(shù)均達到了最大值，在最后一層上只缺少右邊的若干個結點。36（6）二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。37（1）前序遍歷（根、左、右）

訪問根結點；前序遍歷左子樹；前序遍歷右子樹。ABEFCDABC前序遍歷結果：ABC前序遍歷結果：ABDECF38（2）中序遍歷（左、根、右）

中序遍歷左子樹；訪問根結點；中序遍歷右子樹。ABEFCDABC中序遍歷結果：BAC中序遍歷結果：DBEAFC39（3）后序遍歷（左、右、根）

后序遍歷左子樹；后序遍歷右子樹；訪問根結點。ABEFCDABC后序遍歷結果：BCA后序遍歷結果：DEBFCA40八、查找技術查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素。通常，根據(jù)不同的數(shù)據(jù)結構，應采用不同的查找方法。常見的查找方法有兩種：順序查找、二分法查找。查找是數(shù)據(jù)處理中的重要環(huán)節(jié)，一般認為查找的效率將直接影響到數(shù)據(jù)處理的效率。41（1）順序查找

順序查找是指從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示查找成功；若找不到相等的元素則查找失敗。1235634196712345678長度為7的線性表1719222427315012345678長度為7的有序線性表42（2）二分法查找

二分法查找只適用于順序存儲的有序表。其中，“有序表”是指已對線性表排序。設有序列表的長度為n，被查找的元素為x，則二分法查找的方法如下：

將x與線性表中的中間項進行比較：

若中間項的值等于x，則說明查到，查找結束；

若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；

若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。43二分法查找的優(yōu)點主要有兩個:

（1）二分法查找的效率比順序查找高得多；

（2）對于長度為n的有序線性表，在最壞的情況下，二分法查找只需要比較log2n次,而順序查找需要比較n次。44九、排序技術排序是指將一個無序的列表整理成按值遞減（或遞增）順序排列的有序序列。常見的排序方法有:交換類排序、插入類排序和選擇類排序。45一、交換類排序1、冒泡排序最壞情況比較次數(shù)：n(n-1)/22、快速排序最壞情況比較次數(shù)：n(n-1)/2二、插入類排序1、簡單插入排序最壞情況比較次數(shù)：n(n-1)/22、希爾排序最壞情況比較次數(shù)：n1.5三、選擇類排序1、簡單選擇排序最壞情況比較次數(shù)：n(n-1)/22、堆排序最壞情況比較次數(shù)：nlog2n46第二章程序設計基礎本章要求程序設計方法與風格。結構化程序設計。面向?qū)ο蟮某绦蛟O計方法，對象、方法、屬性及繼承與多態(tài)性。47第二章程序設計基礎一、程序設計方法和風格二、結構化程序設計三、面向?qū)ο蟮某绦蛟O計48一、程序設計方法和風格良好的程序設計風格

良好的程序設計風格應遵循一個總體原則，即“清晰第一、效率第二”。具體應注意以下幾個問題。

（1）源程序文檔化。

①符號命名的技巧。

應具有一定的實際含義，以便于對程序功能的理解。

②程序注釋。

注釋一般分為序言性注釋和功能型注釋兩種。

序言性注釋通常位于程序的開頭部分，它是對程序進行整體說明。

功能性注釋的位置一般嵌在源程序之中，主要描述其后的語句或程序做什么。49③視覺組織。

為了使程序的結構一目了然，可以在程序中利用空格、空行、縮進等技巧使程序?qū)哟吻逦?/p>

(2)數(shù)據(jù)說明的方法。

設計原則:易于理解和維護。

(3)語句的結構。

設計原則:清晰第一、效率第二、簡單易懂。

(4)程序的輸入輸出。

設計原則:方便用戶的使用。50二、結構化程序設計1.結構化程序設計的原則

結構化程序設計的基本原則是:自頂向下、逐步求精、模塊化、限制使用goto語句。2.結構化程序設計的基本結構

有3種:順序結構、選擇結構和重復結構

51三、面向?qū)ο蟮某绦蛟O計面向?qū)ο蠓椒ǖ闹饕獌?yōu)點如下：

（1）與人類思維習慣的思維方法一致:主要強調(diào)模擬現(xiàn)實世界中的概念而不強調(diào)算法。

（2）穩(wěn)定性好:當對系統(tǒng)功能的需求發(fā)生變化時并不會引起軟件結構的整體變化，往往僅需要作一些局部性的修改即可。

（3）可重用性好

（4）易于開發(fā)大型軟件產(chǎn)品。

（5）可維護性好（最重要的優(yōu)點）。521.對象

對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢ο罂梢杂脕肀硎究陀^世界存在的任何實體。2.類、實例

將屬性操作相似的對象歸為類，也就是說類是具有共同屬性、共同方法的對象的集合。一個具體的對象則是其對應類的一個實例。533.消息

面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相互合作來推動的，對象間的這種相互合作需要一個機制協(xié)助進行，這樣的機制稱為“消息”。通常，消息由三部分組成：1、接收消息的對象名稱；2、消息標識符（消息名）3、零個或多個參數(shù)。544.繼承繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復的定義它們。繼承是一種在多個類之間共享屬性和操作的機制。繼承分為兩種：單繼承和多繼承555.多態(tài)性對象根據(jù)所接受的消息而做出動作，多態(tài)性是指同樣的消息被不同的對象接收時可導致完全不同的行動，該現(xiàn)象就稱為多態(tài)性。56第三章軟件工程基礎本章要求軟件工程基本概念、軟件生命周期概念、軟件工具與軟件開發(fā)環(huán)境。結構化分析方法、數(shù)據(jù)流圖、數(shù)據(jù)字典、軟件需求規(guī)格說明書。結構化設計方法、總體設計與詳細設計。軟件測試的方法、白盒測試與黑盒測試、測試用例設計、軟件測試的實施、單元測試、集成測試和系統(tǒng)測試。程序的調(diào)試、靜態(tài)調(diào)試與動態(tài)調(diào)試。57第三章軟件工程基礎一、軟件工程基本概念二、結構化分析方法三、結構化設計方法四、軟件測試五、程序調(diào)試58一、軟件工程基本概念1.軟件的定義軟件是包括程序、數(shù)據(jù)及相關文檔的完整集合，軟件和硬件是相互依存的。592.軟件的特點①軟件是一種邏輯實體，而不是物理實體，具有抽象性②軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程。一旦研制開發(fā)成功，可以大量拷貝。③軟件在運行、使用期間不存在磨損、老化問題。④軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性。⑤軟件復雜性高，成本昂貴。⑥軟件開發(fā)涉及諸多社會因素。603.軟件危機

20世紀60年代末以后出現(xiàn)了軟件危機。

軟件危機主要表現(xiàn)在成本、質(zhì)量和生產(chǎn)率等3個方面問題。

產(chǎn)生的主要原因是軟件開發(fā)和維護方法不正確。

為了解決這種軟件危機，出現(xiàn)了軟件工程的概念。4.軟件工程

軟件工程概念的出現(xiàn)源自軟件危機。

軟件工程就是試圖用工程、科學和數(shù)學的原理與方法研制、維護計算機軟件的有關技術及管理方法。61軟件工程有3個要素：方法、工具和過程。

其中，方法是完成軟件工程項目的技術手段；工具用于支持軟件的開發(fā)、管理、文檔生成；過程用于支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。625.軟件生命周期

軟件的生命周期是指將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程，分為3個階段?？尚行匝芯砍醪巾椖坑媱澬枨蠓治龆x階段開發(fā)階段概要設計詳細設計軟件實現(xiàn)軟件測試程序調(diào)試維護階段使用維護退役軟件生命周期過程示意圖63二、結構化分析方法（定義階段）1.需求分析目的：確定軟件系統(tǒng)做什么，實現(xiàn)哪些功能。需求分析階段的工作有四個方面：①需求獲取②需求分析③編寫需求規(guī)格說明書④需求評審642.需求分析的常用工具：①數(shù)據(jù)流圖（DFD）

功能：描述數(shù)據(jù)處理過程，也是需求理解的邏輯模型的圖形表示，直接支持系統(tǒng)的功能建模。65數(shù)據(jù)流圖中的主要圖形元素如下表所示

66例：下圖是銀行取款業(yè)務的數(shù)據(jù)流圖儲戶檢驗登錄賬卡存折付款67②數(shù)據(jù)字典（DD）

作用：數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖（DFD）中出現(xiàn)的被命名的圖形元素的確切解釋。③判定樹④判定表判定樹和判定表主要用在條件判斷中。68三、結構化設計方法（開發(fā)階段）軟件設計的基本原理有以下4種。

（1）抽象:抽象是思維工具，抽象的層次從概要設計到詳細設計逐步降低。

（2）模塊化：把一個待開發(fā)的軟件分解成若干個小的、簡單的部分。

（3）信息隱蔽:主要通過封裝來實現(xiàn)。

（4）模塊獨立性:每個模塊只完成系統(tǒng)要求的獨立的子功能，與其他模塊的聯(lián)系少且接口簡單。69模塊獨立性

模塊的獨立性是評價設計好壞的重要標準。

衡量軟件的模塊獨立性的方法有兩種，即耦合性和內(nèi)聚性。

內(nèi)聚性是指從功能角度分析模塊內(nèi)部的聯(lián)系；

耦合性是模塊之間的相互聯(lián)系的緊密程度的度量。軟件設計應盡量做到：高內(nèi)聚，低耦合。703.概要設計

概要設計主要包括以下幾個方面:

①設計軟件系統(tǒng)結構;

②設計數(shù)據(jù)結構及數(shù)據(jù)庫;

③編寫概要設計文檔;

④概要設計文擋的審評。714.詳細設計

詳細設計的任務是為軟件結構圖中的每個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結構，用某種選定的表達工具表示算法和數(shù)據(jù)結構的細節(jié)。常見的詳細設計工具有以下3種。

（1）圖形工具:程序流程圖、N-S、PAD、HIPO。

（2）表格工具:判定表。

（3）語言工具:PDL(偽碼)72程序流程圖用于詳細設計階段，它獨立于任何一種程序設計語言，其基本圖符如下表所示。73四、軟件測試做好軟件設計和實現(xiàn)后，接著可以進行軟件測試了。軟件測試是軟件生命周期中的重要組成部分，可占總成本40%以上。軟件測試的目的是:注意測試的目的是查找錯誤，而不是演示軟件的正確功能。軟件測試有多種分類方法。

第一種分類方法:從是否需要執(zhí)行被測試軟件的角度可分為靜態(tài)測試和動態(tài)測試。

第二種分類方法:從功能劃分則可以分為白盒測試和黑盒測試。 741.靜態(tài)測試與動態(tài)測試

靜態(tài)測試是不執(zhí)行程序，主要通過人工進行，具體包括代碼檢查、靜態(tài)結構分析與代碼質(zhì)量度量等。

動態(tài)測試是指基于計算機的測試，為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。752.白盒測試與黑盒測試黑盒測試，又稱為功能測試或數(shù)據(jù)驅(qū)動測試，是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試和驗證。它只測試功能，將其看作是一個黑盒子，不考慮程序內(nèi)部的邏輯結構和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說明書進行測試。白盒測試法，又稱為結構設計或邏輯驅(qū)動測試，主要用于測試結構。這種方法將被測試對象看作是一個打開的盒子，允許測試人員利用程序內(nèi)部的邏輯結構及有關信息來設計或選擇用例。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設計規(guī)格要求。763.軟件測試的具體實施步驟

軟件測試的具體實施步驟依次為單元測試、集成測試、驗收測試和系統(tǒng)測試。（1）單元測試是對軟件設計的最小單位——模塊(程序單元)進行正確性檢驗的測試。測試的依據(jù)是詳細設計說明書和源程序。（2）集成測試是測試和組裝的過程。它是把模塊在按照設計要求組裝的同時進行測試，主要目的是發(fā)現(xiàn)與接口有關的錯誤。測試的依據(jù)是概要設計說明書。77（3）驗收測試（確認測試）是驗證軟件的功能和性能及其他特征是否滿足需求規(guī)格說明中確定的各種需求，以及軟件配置是否完善、正確。確認測試的依據(jù)是需求規(guī)格說明書。（4）系統(tǒng)測試是將通過確認的軟件作為整個基于計算機系統(tǒng)的一個元素，與計算機硬件、外設、支持軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實際運行環(huán)境下對計算機系統(tǒng)進行一系列的集成測試和驗收測試。78五、程序調(diào)試程序調(diào)試是在測試成功后開始，程序調(diào)試的任務是診斷和改正程序中的錯誤。79第四章數(shù)據(jù)庫設計基礎本章要求數(shù)據(jù)庫的基本概念:數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)與數(shù)據(jù)庫系統(tǒng)。數(shù)據(jù)模型、實體聯(lián)系模型及E-R圖、從E-R圖導出的關系數(shù)據(jù)模型。關系代數(shù)運算，包括集合運算及選擇、投影、連接運算，數(shù)據(jù)庫規(guī)范化理論。數(shù)據(jù)庫設計方法和步驟:需求分析、概念設計、邏輯設計和物理設計的相關策略。80第四章數(shù)據(jù)庫設計基礎一、數(shù)據(jù)庫系統(tǒng)的基本概念二、數(shù)據(jù)模型三、關系代數(shù)四、數(shù)據(jù)庫設計與管理81一、數(shù)據(jù)庫系統(tǒng)的基本概念1.數(shù)據(jù)

數(shù)據(jù)（data)是指描述事務的符號記錄。例如，描述一名學生的方法是(張三，男，1981，北京，黨員)。

數(shù)據(jù)是數(shù)據(jù)庫中存儲的基本對象。2.數(shù)據(jù)庫

數(shù)據(jù)庫(database)是數(shù)據(jù)的集合，它具有統(tǒng)一的結構形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應用數(shù)據(jù)的集成，并可被各個應用程序所共享。823.數(shù)據(jù)庫管理系統(tǒng)

數(shù)據(jù)庫管理系統(tǒng)（DBMS）是指幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應用程序的集合(軟件)。

DBMS是數(shù)據(jù)庫系統(tǒng)的核心。4.數(shù)據(jù)庫管理員

由于數(shù)據(jù)庫的共享性，因此對數(shù)據(jù)庫的規(guī)劃、設計、維護、監(jiān)視等需要專人管理，稱他們?yōu)閿?shù)據(jù)庫管理員（DataBaseAdministrator，DBA）。DBA的主要工作是數(shù)據(jù)庫設計、數(shù)據(jù)庫維護、改善系統(tǒng)性能。835.數(shù)據(jù)庫系統(tǒng)

數(shù)據(jù)庫系統(tǒng)（DatabaseSystem，DBS）由如下幾部分組成：數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、系統(tǒng)平臺之一——硬件平臺（硬件）、系統(tǒng)平臺之二——軟件平臺（軟件）。這五部分組成了一個完整的數(shù)據(jù)庫系統(tǒng)。84數(shù)據(jù)庫系統(tǒng)的發(fā)展有以下3個階段：第一階段:20世紀50年代中期以前為人工管理階段，主要特點是數(shù)據(jù)不能保存、應用程序管理數(shù)據(jù)、數(shù)據(jù)不共享、不具有數(shù)據(jù)獨立性。第二階段:20世紀50年代后期到60年代中期的文件系統(tǒng)階段，主要特點是能長期保存數(shù)據(jù)，應用文件系統(tǒng)管理數(shù)據(jù)、數(shù)據(jù)共享性差、數(shù)據(jù)獨立性差。第三階段:20世紀60年代后期開始的數(shù)據(jù)庫系統(tǒng)階段。這時期的數(shù)據(jù)庫系統(tǒng)的特點如下所述：

①數(shù)據(jù)的集成性。

②數(shù)據(jù)的高共享性、低冗余性。

③數(shù)據(jù)獨立性高。

④數(shù)據(jù)的統(tǒng)一管理和控制。85二、數(shù)據(jù)模型數(shù)據(jù)模型的基本概念數(shù)據(jù)模型是指模擬現(xiàn)實世界中的實物及其之間聯(lián)系的方法。數(shù)據(jù)模型按不同的應用層次可分為3種:

概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。

（1）概念模型:面向現(xiàn)實世界，與計算機平臺無關，著名的概念模型是E-R模型。86

（2）邏輯模型:又稱數(shù)據(jù)模型，是面向數(shù)據(jù)庫系統(tǒng)的模型。該模型著重于在數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn)。著名的邏輯模型有層次模型、網(wǎng)狀模型、關系模型、面向?qū)ο竽Ｐ?種。（3）物理數(shù)據(jù)模型:又稱物理模型，是面向計算機物理表示的模型。此模型給出了數(shù)據(jù)模型在計算機上物理結構的表示。871.概念模型（E-R模型）概念模型是面向現(xiàn)實世界的，它的出發(fā)點是有效自然的模擬現(xiàn)實世界。

E-R模型中常見的概念如下：

（1）實體和實體集現(xiàn)實世界中，客觀存在并可以相互區(qū)別的事物稱為實體。實體可以是人、事、物，也可以是抽象的概念或聯(lián)系。凡是有共性的實體可以組成一個集合，稱為實體集例如:小趙，小李是實體，他們又具有學生的共性，所以可以組成一個實體集。88（2）屬性和域現(xiàn)實世界中事物均有一些特性，這些特性可以用屬性來表示。

屬性刻畫了實體的特征。一個實體往往可以有若干個屬性。每個屬性可以有值，一個屬性的取值范圍稱為該屬性的域。

例如:小趙的年齡屬性取值為16。89（3）聯(lián)系

現(xiàn)實世界中事物之間的關聯(lián)稱為聯(lián)系。在概念世界中聯(lián)系反映了實體集間的一定關系，如人工與設備之間的操作關系，上、下級之間的領導關系，生產(chǎn)者與消費者之間的供求關系等。

實體之間聯(lián)系可以有以下3種:

一對一、一對多和多對多。90（4）E-R圖

它是指實體-聯(lián)系圖，用來描述現(xiàn)實世界中的概念模型。在該圖中，用矩形來表示實體集、用橢圓表示屬性、用菱形表示聯(lián)系。學生選課實體集表示法學號姓名年齡屬性表示法選學聯(lián)系表示法91學生選課E-R圖學號姓名性別年齡籍貫選課學生學號課程號成績m1選學922.邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）①層次模型

（1）層次模型是發(fā)展最早的數(shù)據(jù)模型。

（2）層次模型中用樹形結構來表示。②網(wǎng)狀模型

（1）網(wǎng)狀模型出現(xiàn)晚于層次模型。

（3）網(wǎng)狀模型實際上是不加任何條件限制的無向圖。93③關系模型

（1）數(shù)據(jù)結構。關系模型采用二維表來表示數(shù)據(jù)，例如下表表示一種關系。學號姓名性別專業(yè)號年齡80