二級公共基礎(chǔ)知識總結(jié)

下個學期就要開始我的計算機雙學位就讀了,。在此之前，我打算先考幾個證來過渡一下,，像二級的C,、C++、VB,、Java,、Python、Office都考一下,。其中我比較熟悉的只有C和Python,，其他的編程語言就要自己突擊一下了。3月我報的是C,、C++和VB,。為此還買了幾本書。這里總結(jié)一下考點,，做一下筆記,。之后書就不重要了，可以丟了,。再刷一些題目,，做一些記錄就可以了。開始筆記吧,。

第一部分 數(shù)據(jù)結(jié)構(gòu)和算法

1.1 算法

• 定義：對解決方案的操作步驟的準確而完整的描述,。(是數(shù)學計算方法和程序間的一個過渡)

• 基本特征：可行性(可以在實際計算工具上執(zhí)行)；確定性(算法每一步的表述沒有歧義),；有窮性(操作步驟有限,，在有限時間內(nèi)完成)；有足夠的輸入,。
  總之,，算法是指一組嚴謹?shù)囟x操作步驟的可以在有限的次數(shù)中終止的規(guī)則，每一個規(guī)則都是可行的,、明確的,。

• 基本要素：
  (1). 對數(shù)據(jù)對象的運算和操作(由不同計算機系統(tǒng)的指令集規(guī)定其基本運算和操作)；
  (2). 控制結(jié)構(gòu)(就是順序,、選擇,、循環(huán)三種)；

• 算法基本設(shè)計方法：列舉法,、歸納法,、遞推法,、遞歸法、減半遞推法,、回溯法

• 算法復雜度：體現(xiàn)在運行該算法所需的計算機的時間和空間資源上,，越多則算法復雜度越高。
  (1). 時間復雜度：執(zhí)行算法所需的計算工作量,，用算法所執(zhí)行的基本運算次數(shù)來度量(注意: 不是具體的執(zhí)行時間)。常用大O表示法表示,。我們經(jīng)常用平均復雜度和最壞情況復雜度來分析算法的工作量,。
  (2). 空間復雜度：執(zhí)行這個算法所需的內(nèi)存空間。包括3個部分,。為降低空間復雜度,，主要應(yīng)減少輸入數(shù)據(jù)所占的空間和額外空間。如果額外空間不隨問題規(guī)模變化,，稱該算法in place原地工作,。

     a. 輸入數(shù)據(jù)所占的存儲空間
     b. 程序本身所占的存儲空間
     c. 算法執(zhí)行過程中所需要的額外空間,，包括算法執(zhí)行過程中的工作單元和某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間
  

1.2 數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)結(jié)構(gòu)：是數(shù)據(jù)+結(jié)構(gòu)(即有關(guān)聯(lián)的數(shù)據(jù)元素集合),。數(shù)據(jù)是需要處理的數(shù)據(jù)元素(數(shù)據(jù)的基本單位)的集合，具有共同特征,。結(jié)構(gòu)就是關(guān)系,，是數(shù)據(jù)集合中各個數(shù)據(jù)元素之間存在的某種關(guān)系,。
  結(jié)構(gòu)又可以分為邏輯結(jié)構(gòu)——數(shù)據(jù)集合中各數(shù)據(jù)元素之間固有的邏輯關(guān)系；存儲結(jié)構(gòu)——各數(shù)據(jù)元素在計算機中的存儲關(guān)系,。此外,，數(shù)據(jù)結(jié)構(gòu)還研究對各種數(shù)據(jù)結(jié)構(gòu)的運算。
  所以,，數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)+邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+運算,。
• 數(shù)據(jù)元素間的結(jié)構(gòu)根據(jù)不同的特性，分為線性結(jié)構(gòu),、樹形結(jié)構(gòu),、網(wǎng)狀結(jié)構(gòu)(圖形結(jié)構(gòu))、集合,。
• 兩兩數(shù)據(jù)元素的關(guān)系常常用前后件(前驅(qū)后繼關(guān)系)描述,。B=(D+R)，D={數(shù)據(jù)元素集合},，R={前后件關(guān)系的集合},。 如：B=D+R，D={早餐,，中餐,，晚餐},，R={(早餐，午餐),，(午餐,，晚餐)}。
• 節(jié)點：數(shù)據(jù)結(jié)構(gòu)的圖形表示中引出的概念,，根節(jié)點——沒有前驅(qū)的節(jié)點,，葉子節(jié)點——沒有后繼的節(jié)點，內(nèi)部節(jié)點——除了根節(jié)點和葉子節(jié)點之外的節(jié)點的統(tǒng)稱,。
• 存儲結(jié)構(gòu)：包括順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu),。
• 邏輯結(jié)構(gòu)：包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)。如果數(shù)據(jù)結(jié)構(gòu)沒有數(shù)據(jù)元素,，稱其為空的數(shù)據(jù)結(jié)構(gòu),。

1.3 線性表

• 定義：表中除第一個元素外的每一個元素，有且只有一個前件,，除最后一個元素外,，有且只有一個后件。
• 結(jié)構(gòu)特征：只有一個根節(jié)點,，它無前件,；有且只有一個終端節(jié)點，它無后件,；除根節(jié)點與終端節(jié)點外,，其他所有節(jié)點有且只有一個前件，有且只有一個后件,。節(jié)點個數(shù)n就是線性表的長度,，n=0時稱為空表。
• 順序表：線性表的順序存儲結(jié)構(gòu),，所有元素所占的存儲空間是連續(xù)的,，按邏輯順序依次存放。此時邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一致的,。順序表中前后件兩個元素在存儲空間中緊鄰,，前件元素一定存儲在后件元素的前面。只要確定了首地址，順序表中任意元素的地址都可以方便地計算出來,。
• 線性表的插入運算：在第i個元素之前插入一個新元素,，需要把原來的第i個節(jié)點至第n個節(jié)點依次往后移一個元素位置，把新節(jié)點放在第i個節(jié)點位置上,。其時間耗費在節(jié)點的移動上,，所需移動節(jié)點的次數(shù)不僅與表的長度有關(guān)，還與插入的位置有關(guān),。
• 線性表的刪除運算：將表的第i個節(jié)點刪除,，應(yīng)將第i+1個元素至第n個元素依次向前移一個元素位置，共移動n-i個元素,。所需移動節(jié)點的次數(shù)不僅與表的長度有關(guān),，還與刪除的節(jié)點位置有關(guān)。
• 綜上所述,，線性表的順序存儲結(jié)構(gòu)適用于建立之后其中元素不經(jīng)常變動的情況，而不適用于經(jīng)常需要進行插入和刪除的線性表,。

1.4 棧和隊列

1.4.1 棧

• 定義：特殊的線性表,，所有的插入和刪除操作限定在表的同一端(棧頂top)進行，另一端(棧底bottom)是封閉的,，既不允許插入元素,，也不運行刪除元素。棧中沒有元素時稱為空棧,。
• 設(shè)有棧S=(a1, a2, a3, a4),，則a1為棧底元素，a4為棧底元素,。按照a1,a2,a3,a4的順序入棧,，a4,a3,a2,a1的順序出棧。
• 特點：Last In First Out,，后進先出,。即棧頂元素總是最后被插入的元素，也是最早被刪除的元素,，棧底元素總是最早被插入的元素,，也是最晚被刪除的元素。在順序存儲結(jié)構(gòu)中,，棧的插入和刪除不需要移動表中的其他元素,。
• 棧的運算之入棧：在棧頂插入一個新元素。
• 棧的運算之出棧：取出棧頂元素并賦予指定變量,。
• 棧底運算之讀取棧頂元素：讀取棧頂指針所指向的元素并賦予指定變量,。

1.4.2 隊列

• 定義：特殊的線性表，允許在一段(隊尾rear)進行插入，而在另一端(隊頭front)進行刪除的線性表,。與生活中的排隊現(xiàn)象是一樣的,。
• 設(shè)有隊列Q=(q1,q2,q3,q4)，則q1為隊頭元素,，q4為隊尾元素,。按照q1,q2,q3,q4的順序進入，也按照這個順序退出,。
• 隊列運算之入隊：隊頭指針front指示當前執(zhí)行退隊運算的隊頭位置(即當前隊頭元素的前一個位置),，隊尾指針rear指向當前執(zhí)行入隊運算的隊尾位置，往隊列的隊尾插入一個元素稱為入隊,，首先隊尾指針進1,，然后在rear指針指向的位置插入新元素。
• 隊列運算之出隊：從隊列的排頭刪除一個元素稱為退隊運算,。排頭指針front+1,，然后刪除front指針指向的位置上的元素。隊頭指針始終指向當前執(zhí)行退隊操作的隊頭位置,。
• 循環(huán)隊列及其運算：為充分地利用數(shù)組的存儲空間而把數(shù)組的前端和后端連接起來,，形成一個環(huán)形的表，就是循環(huán)隊列,，是隊列的一種順序存儲結(jié)構(gòu),。常用取余運算來實現(xiàn)循環(huán)順序隊列的“循環(huán)”。為區(qū)分隊空和隊滿的情況可以設(shè)置標志,。

1.5 線性鏈表(線性表的鏈式存儲)

1.5.1 線性鏈表的概念及基本運算

• 概念：用一組不連續(xù)的存儲單元存儲線性表中的各個元素,，數(shù)據(jù)元素間的邏輯關(guān)系不能依靠數(shù)據(jù)元素的存儲單元之間的物理關(guān)系來表達，因此每個元素除了存儲自身的信息外,，還要存儲一個指示其后件的信息,。
• 存儲節(jié)點：線性表鏈式結(jié)構(gòu)的基本單位成為存儲節(jié)點，包括數(shù)據(jù)域(存儲數(shù)據(jù)元素本身的信息)和指針域(存儲一個指向后繼的指針,，即存放下一個數(shù)據(jù)元素的存儲地址)
• 單鏈表：這種鏈表中,，每一個節(jié)點只有一個指針域。是最基本的鏈表,。其中第一個元素沒有前驅(qū),，可以是一個指向鏈表中第一個節(jié)點的特殊指針，即頭指針HEAD,，最后一個元素沒有后繼,，其指針域為空，用NULL表示,。更加直觀的表示是用箭頭相鏈接的節(jié)點序列,。在單鏈表中，只能順時針向鏈尾方向進行掃描。
• 雙向鏈表：在實際應(yīng)用中有時還會用到每個存儲節(jié)點有兩個指針域的鏈表,，一個存放前驅(qū)的地址,，稱為左指針(Llink)，一個指針域存放后繼的地址,，稱為右指針(Rlink),。雙向鏈表的第一個元素左指針為空，最后一個元素的右指針為空,。由于有兩個指針,，可以從任一節(jié)點出發(fā)找到其他節(jié)點。
• 鏈棧：使用鏈式存儲結(jié)構(gòu)表示棧,，組織成一個單鏈表,。
• 鏈隊列：使用鏈式存儲結(jié)構(gòu)表示隊列，組織成一個單鏈表,。
• 順序表和鏈表的優(yōu)缺點比較：

• 線性鏈表的基本運算：
  (1). 查找指定元素：必須從隊頭指針出發(fā),，沿著指針域Next逐個節(jié)點搜索,，直到找到指定元素或鏈表尾部返回NULL為止。
  (2). 可利用棧(線性鏈表的存儲單元是不連續(xù)的,，就存在離散的空閑節(jié)點,，將計算機存儲空間中空閑的存儲節(jié)點利用起來，把其組織成一個帶鏈的棧,，就是可利用棧)的插入和刪除：線性鏈表執(zhí)行刪除時,，被刪除節(jié)點回收到可利用棧，即把該空閑節(jié)點放到可利用棧棧頂,，執(zhí)行入棧操作,；線性鏈表執(zhí)行插入運算時，
  需要一個空閑節(jié)點,，就在可利用棧中取棧頂節(jié)點,，執(zhí)行退棧操作。
  (3). 插入運算：在鏈式存儲結(jié)構(gòu)下的線性表中插入一個新元素,。由于新節(jié)點的存儲單元取自可利用棧,，只要可利用棧非空，線性鏈表就總能找到存儲新元素的節(jié)點，因而不需要規(guī)定最大存儲空間,，不會發(fā)生上溢錯誤,。
  (4). 刪除運算。

1.5.2 循環(huán)鏈表

• 概念：在單鏈表第一個節(jié)點之前增加一個沒有元素的表頭節(jié)點,，HEAD指針指向表頭節(jié)點,，最后一個節(jié)點的指針域指向表頭節(jié)點。在循環(huán)鏈表中,，所有節(jié)點的指針構(gòu)成了一個環(huán)狀鏈,。
• 與單鏈表的比較：
  (1). 對單鏈表的訪問是一種順序訪問，從其中一個節(jié)點出發(fā),，只能找到它的后繼,；在循環(huán)鏈表中，可以通過一個節(jié)點訪問到表中的所有節(jié)點,。
  (2). 在單鏈表中空表和第一個節(jié)點的處理必須單獨考慮,；在循環(huán)鏈表中，表頭節(jié)點是循環(huán)鏈表所固有的節(jié)點,，因此即使在表中沒有數(shù)據(jù)元素的情況下,，表中也至少有一個節(jié)點，從而使空表與非空表的處理統(tǒng)一,。

1.6 樹與二叉樹

1.6.1 樹的基本概念

• 樹：一種簡單的非線性結(jié)構(gòu),，是以分支關(guān)系定義的層次結(jié)構(gòu)。在使用圖形表示數(shù)據(jù)結(jié)構(gòu)中元素的前后件關(guān)系時通常使用有序箭頭,，但是樹形結(jié)構(gòu)中使用無向箭頭也可以,，因為前后件關(guān)系很明確。

1.6.2 二叉樹及其性質(zhì)

• 二叉樹(Binary Tree)定義：是一個有限的節(jié)點集合,，該集合或為空，或由一個根節(jié)點及其左右不相交的左,、右二叉子樹所構(gòu)成,。與樹是相似的，但又有不同,。二叉樹不是樹的特殊情況,，二者是不同的概念。

• 二叉樹的特點：
  (1). 二叉樹可以為空,，空的二叉樹沒有節(jié)點,，非空二叉樹只有一個根節(jié)點；
  (2). 每個節(jié)點最多只有兩棵子樹,，即二叉樹中不存在度大于2的節(jié)點,，二叉樹中的節(jié)點可能沒有子節(jié)點，可能只有一個左子節(jié)點或只有一個右子節(jié)點,；
  (3). 二叉樹的子樹有左右之分,，不能任意顛倒次序。

• 二叉樹的基本形態(tài)：5種,；空,，僅有根節(jié)點，左右子樹均非空,，左子樹非空右子樹為空,，左子樹為空右子樹非空。

• 滿二叉樹：除最后一層,，每一層上的所有節(jié)點都有兩個子節(jié)點的二叉樹,，一棵平衡的二叉樹。
  (1). 其在第i層有2^(i-1)個節(jié)點,，相當于每一層的節(jié)點數(shù)都滿了；
  (2). 一棵深度為K的滿二叉樹共有2^k-1個節(jié)點;
  (3). 滿二叉樹中只有度為2和0的節(jié)點,，沒有度為1的節(jié)點,。所有度為0的葉子節(jié)點都在最后同一層。

• 完全二叉樹：除最后一層,，每一層上的節(jié)點數(shù)均達到最大,，在最后一層上只缺少右邊的若干節(jié)點。
  (1). 葉子節(jié)點只在最后兩層出現(xiàn),；
  (2). 對于任一節(jié)點,，若其右子樹的深度為m，則左子樹的深度為m或m+1,。

• 二叉樹的基本性質(zhì)：
  (1). 二叉樹的第K層上面,，最多只有2^k-1個節(jié)點,；
  (2). 深度為K的二叉樹，最多有2^k-1個節(jié)點(等比數(shù)列求和),；
  (3). 對任何一棵二叉樹,，度為0的節(jié)點(葉子節(jié)點)總是比度為2的節(jié)點多一個；
  (4). 具有n個節(jié)點的二叉樹,，其深度至少為[log₂n]+1,；
  (5). 具有n個節(jié)點的完全二叉樹，其深度為[log₂n]+1,。
  (6). 較復雜,。

1.6.3 二叉樹存儲結(jié)構(gòu)及其遍歷

• 二叉鏈表：二叉樹常采用鏈式結(jié)構(gòu)。由于每個元素可以有兩個后件,，因此每個節(jié)點有兩個指針：左指針域執(zhí)行左子節(jié)點,，右指針域執(zhí)行右子節(jié)點。因此,，二叉樹的鏈式存儲結(jié)構(gòu)也稱為二叉鏈表(非線性結(jié)構(gòu),，不同于雙向鏈表)。
• 二叉樹的遍歷：不重復的訪問二叉樹中的所有節(jié)點,。一般先訪問左子樹,，在訪問右子樹，在先左后右的原則下,，根據(jù)訪問根節(jié)點的次序不同,，二叉樹的遍歷分為前序遍歷(DLR)、中序遍歷(LDR),、后序遍歷(LRD)三種,。
  (1). 前序遍歷：先訪問根節(jié)點——> 前序遍歷左子樹——> 前序遍歷右子樹(DLR)
  (2). 中序遍歷：先中序遍歷左子樹——> 訪問根節(jié)點——> 中序遍歷右子樹(LDR)
  (3). 后序遍歷：先后序遍歷左子樹——> 后序遍歷右子樹——> 訪問根節(jié)點 (LRD)

  已知中序遍歷序列和前序遍歷序列(或后序遍歷序列)可以唯一確認一棵二叉樹，但是知道前序和后序則無法唯一確定這棵二叉樹,。

1.7 查找技術(shù)

查找是插入和刪除等運算的基礎(chǔ),，是數(shù)據(jù)處理的重要內(nèi)容。

• 順序查找：最好情況：1次找到,；最壞情況：n次比較后找到,；平均：n/2次，即O(n)的時間復雜度,。特點在于：雖然效率很低,，但是在線性表無序(不管使用順序存儲還是鏈式存儲)的時候，或者在采用鏈式存儲結(jié)構(gòu)時,，只能用順序查找,。
• 二分查找：條件：使用順序存儲結(jié)構(gòu)；線性表是有序表,。對于長度為n的有序線性表,，在最壞情況下二分查找只需比較log₂n次,。即O(logn)的時間復雜度。
• 哈希查找：時間復雜度O(1),。

1.8 排序技術(shù)

排序是指將一個無序序列整理成按值非遞減順序排列的有序序列,。

• 交換類排序法(借助數(shù)據(jù)元素的交換來排序的方法)：冒泡排序: 最壞的情況下，對長度為n的線性表排列需要比較n(n-1)/2次,?？焖倥判騽t是對冒泡排序的一種本質(zhì)改進，其平均時間最佳O(nlog₂n) ,，最壞O(n²),。如初始序列基本有序，則蛻化為冒泡排序,。

• 插入類排序法(每次將一個待排序元素按其大小插入到前面的有序子表中)：簡單插入排序：持續(xù)不斷的清空無序表,，插入有序表中，其效率與冒泡排序法基本相同,。希爾排序法則有較大改進,。

• 選擇類排序法(每趟從待排序的序列中選擇最小的元素，順序放在有序子表中的后面,，直到全部序列滿足排序要求為止)：簡單選擇排序,，最壞的情況下要比較n(n-1)/2次。對于大量數(shù)據(jù)元素,，堆排序則是很有效的,。

• 排序方法比較：

  方法	平均時間	最壞情況時間	輔助存儲
  冒泡排序	O(n2)	O(n2)	O(1)
  快速排序	O(nlog2n)	O(n2)	O(log2n)
  簡單插入排序	O(n2)	O(n2)	O(1)
  簡單選擇排序	O(n2)	O(n2)	O(1)
  堆排序	O(nlog2n)	O(nlog2n)	O(1)

第二部分 程序設(shè)計基礎(chǔ)

2.1 程序設(shè)計方法與風格

• 程序設(shè)計：指設(shè)計、編制,、調(diào)試程序的方法與過程,。不等同于編程。程序設(shè)計的方法和風格顯著影響程序的質(zhì)量,。良好的程序設(shè)計風格可以使程序結(jié)構(gòu)清晰,，便于維護。
• 程序設(shè)計規(guī)范：
  (1). 源程序文檔化：在源程序中包含一些內(nèi)部文檔,，以幫助人們理解和閱讀源程序,。考慮符號名的命名,、程序注釋(包括序言性注釋和功能性注釋)、視覺組織(空行,、空格和縮進),。
  (2). 數(shù)據(jù)說明的方法：詞序規(guī)范化、變量安排有序化,、使用注釋,。
  (3). 語句結(jié)構(gòu)：簡單直接,，模塊化……
  (4). 輸入輸出：方式和格式盡量方便用戶使用；對所有的輸入數(shù)據(jù)都要進行檢驗,，確保輸入數(shù)據(jù)的合法性,；輸入數(shù)據(jù)時，應(yīng)允許使用自由格式,，允許默認值,；輸入一批數(shù)據(jù)后，最好使用輸入結(jié)束標志,；給所有的輸出加注釋,，并設(shè)計良好的輸出報表格式……

2.2 結(jié)構(gòu)化程序設(shè)計

• 原則：自頂向下； 逐步求精,；模塊化,；限制使用goto語句。
• 基本結(jié)構(gòu)：順序結(jié)構(gòu),、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu),。3種基本結(jié)構(gòu)就足以表達各種其他形式的結(jié)構(gòu)。共同特征是嚴格的只有一個入口和出口,。
• 注意事項：使用順序,、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯,；選用的控制結(jié)構(gòu)只允許有一個入口和出口,；程序語句組成容易識別的功能模塊，每個模塊只有一個入口和一個出口,；復雜結(jié)構(gòu)應(yīng)該用基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn),；語言中沒有的控制結(jié)構(gòu)，應(yīng)采用前后一致的方法模擬,；嚴格控制goto語句的使用,。
• 總之，按結(jié)構(gòu)化程序設(shè)計出的程序具有明顯的優(yōu)點：程序易于理解,、使用和維護,；提高呢編程工作的效率，降低了軟件開發(fā)成本,。

2.3 面向?qū)ο蟮某绦蛟O(shè)計

基本概念：

• 對象(Object)：系統(tǒng)中用于描述客觀事物的一個實體,，是構(gòu)成系統(tǒng)的一個基本單位，由一組靜態(tài)特征(屬性)和它可執(zhí)行的一系列方法(行為)組成,。其中的屬性即對象包含的信息,，一般只能通過執(zhí)行對象的操作來改變。方法則是對象的動態(tài)行為,。
  對象的基本特點：標識唯一性,；分類性(可以將具有相同屬性和操作的對象抽象成類),；多態(tài)性(同一個操作可以是不同對象的行為)；封裝性(對象內(nèi)部對外是不可見的),；模塊獨立性好(完成對象功能所需的元素都被封裝在對象內(nèi)部),。
• 類(Class)：具有共同屬性和方法的對象的集合，是關(guān)于對象的抽象描述,，反映屬于該對象類型的所有對象的性質(zhì),。
• 實例(Instance)：一個具體對象則是其對應(yīng)類的一個實例。
• 消息(Message)：消息傳遞是對象間通信的手段,，一個對象通過向另一個對象發(fā)送對象來請求其服務(wù),。一個消息由接受消息的對象名稱、消息選擇符,、零或多個參數(shù)組成,。消息只告知接受對象需要完成什么操作，而不指示怎樣完成操作,。
• 繼承：直接獲得已有的性質(zhì)和特征,，而不必重復定義它們。一個子類可以直接繼承父類的全部描述,，而且可以定義自己的屬性和方法,。其中，繼承又分成單繼承和多繼承,。
• 多態(tài)：同樣的消息可以被不同的對象接受而產(chǎn)生不同的行為,。即子類對象可以像父類對象那樣使用，同樣的消息既可以發(fā)給父類也可以發(fā)給子類對象,。
• 優(yōu)點：與人類習慣的思維方法一致,；穩(wěn)定性好；可重用性好,；容易開發(fā)大型軟件產(chǎn)品,；可維護性好。

第三部分 軟件工程基礎(chǔ)

3.1 軟件工程基本概念

3.1.1 軟件

• 定義：是由(機器可執(zhí)行的)程序,、數(shù)據(jù)和(不可執(zhí)行的)相關(guān)文檔組成的完整集合,。
  (1). 程序：軟件開發(fā)人員依據(jù)用戶需求開發(fā)的、用某種程序設(shè)計語言描述的,、能夠在計算機中執(zhí)行的語句序列,。
  (2). 數(shù)據(jù)：使程序能夠正常操作信息的數(shù)據(jù)結(jié)構(gòu)。
  (3). 文檔：與程序開發(fā)維護使用相關(guān)的文件資料,。
• 特點：(1). 是一種邏輯實體,；(2). 沒有明顯的制作過程；(3). 在使用期間不存在磨損老化問題，損失方式特殊,；(4). 對硬件和環(huán)境具有依賴性，給軟件的移植帶來問題,；(5). 軟件復雜性高,，成本昂貴；(6). 軟件開發(fā)涉及諸多社會因素,。
• 分類：(1). 系統(tǒng)軟件：管理計算機資源,，提高使用效率，為用戶提供各種服務(wù)的軟件,。(2). 支撐軟件：介于系統(tǒng)軟件和應(yīng)用軟件之間,，輔助用戶開發(fā)軟件的工具型軟件。 (3). 應(yīng)用軟件：為了應(yīng)用于特定軟件而開發(fā)的軟件,。
• 軟件危機：泛指在計算機軟件的開發(fā)和維護中所遇到的一系列嚴重問題,，幾乎所有軟件都不同程度存在這些問題(軟件開發(fā)生產(chǎn)率低；軟件質(zhì)量難以保證,；軟件開發(fā)進度無法控制,；軟件成本不斷提高；軟件維護程度低下,；軟件需求的增長得不到滿足),。主要原因在于：軟件本身的特點，如復雜度高,，規(guī)模龐大,；人們對軟件開發(fā)維護有許多錯誤認識和做法，對軟件的特性認識不足,。為此,，誕生了軟件工程的概念。

3.1.2 軟件工程

• 軟件工程：應(yīng)用于計算機軟件的定義,、開發(fā)和維護的一整套方法,、工具、文檔,、實踐標準,、工序。重要三要素是方法(技術(shù)手段),、工具,、過程。
• 軟件工程目標和研究內(nèi)容(軟件開發(fā)技術(shù)和軟件工程管理)
• 軟件工程的原則：

• 軟件工程過程：是使用適當?shù)馁Y源為開發(fā)軟件進行的一組開發(fā)活動,，在過程結(jié)束時將輸入(用戶要求)轉(zhuǎn)化為輸出(軟件產(chǎn)品),。
  基礎(chǔ)活動如下：

• 軟件生命周期：一個軟件從提出,、實現(xiàn),、使用、維護和停止使用與廢棄的過程稱為軟件生命周期,。分為3個時期和8個階段,。

• 軟件開發(fā)工具：從單項工具逐步向集成工具發(fā)展,；軟件開發(fā)環(huán)境：是全面支持軟件開發(fā)全過程的軟件工具的集合。

3.2 結(jié)構(gòu)化分析方法

也稱傳統(tǒng)方法學,，使用結(jié)構(gòu)化方法完成軟件開發(fā)的各項任務(wù),。

3.2.1 需求分析

• 軟件需求是用戶對目標軟件系統(tǒng)在功能、性能和設(shè)計約束上的期望,。需求分析的任務(wù)是發(fā)現(xiàn)需求,、定義需求的過程，將創(chuàng)建所需的數(shù)據(jù)模型,、功能模型和控制模型,。
• 需求分析階段的工作：
  (1). 需求獲?。毫私庥脩羟闆r，發(fā)現(xiàn)用戶問題和對目標系統(tǒng)的完整,、準確和具體的需求,。
  (2). 需求分析：整合獲得的需求，得出系統(tǒng)的解決方案和目標系統(tǒng)的邏輯模型,。
  (3). 編寫需求規(guī)格說明書：這是需求分析的階段性成果,。
  (4). 需求評審：從一致性、完整性,、現(xiàn)實性、有效性復審軟件需求規(guī)格說明書,。

3.2.2 需求分析方法

• 結(jié)構(gòu)化分析方法：面向數(shù)據(jù)流的結(jié)構(gòu)化分析(SA),；面向數(shù)據(jù)結(jié)構(gòu)的Jackson系統(tǒng)開發(fā)；面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法,。面向?qū)ο蠓治龇椒ǎ好嫦驅(qū)ο蠓治鍪敲嫦驅(qū)ο筌浖こ谭椒ǖ牡谝粋€環(huán)節(jié),。
• 結(jié)構(gòu)化分析方法：使用數(shù)據(jù)流圖、數(shù)據(jù)字典,、結(jié)構(gòu)化英語,、判定表和判定樹等工具來建立一種新的稱為結(jié)構(gòu)化規(guī)格說明的目標文檔。

3.2.3 結(jié)構(gòu)化分析方法的常用工具

• 數(shù)據(jù)流圖：分析員和用戶間極好的通訊工具,。

• 數(shù)據(jù)字典：對數(shù)據(jù)流圖中所有元素的定義的集合，是結(jié)構(gòu)化分析的核心,，與數(shù)據(jù)流圖共同構(gòu)成系統(tǒng)的邏輯模型,。其中共有4種類型的條目，數(shù)據(jù)流,、數(shù)據(jù)項,、數(shù)據(jù)存儲和加工。
• 判定表：如果一個加工邏輯有多個條件,、多個操作并且在不同場合下執(zhí)行不同的操作,，可以使用判定表來描述。一個十字分成四個區(qū)域,，左上部是基本條件項,，列出各種可能的條件；右上部成為條件項,，列出各種可能的條件組合,；左下部是基本動作項，列出所有的操作；右下部是動作項,，列出在對應(yīng)的條件組合下所選的操作,。
• 判定樹：可以用判定表表示的加工邏輯都可以用判定樹表示。

3.2.4 軟件需求規(guī)格說明書

這是需求分析階段的最后成果,，是軟件開發(fā)過程中的重要文檔之一,，衡量它的標準如下：

3.3 結(jié)構(gòu)化設(shè)計方法

在需求分析階段已經(jīng)使用數(shù)據(jù)流圖和數(shù)據(jù)字典等工具建立了系統(tǒng)的邏輯模型,，即做什么,，接下來解決怎么做的問題。

3.3.1 軟件設(shè)計概述

• 軟件設(shè)計基礎(chǔ)：基本目標是用抽象概括的方式確定目標系統(tǒng)如何完成預定的任務(wù),，確定系統(tǒng)的物理模型,，是開發(fā)階段最重要的步驟。

• 軟件設(shè)計基本原理與原則：
  (1). 模塊化,，但要避免模塊的數(shù)目過多或過少,；(2). 抽象；(3). 信息隱藏——指出設(shè)計和確定模塊時應(yīng)使得一個模塊中包含的信息對不需要這些信息的模塊來說是不能訪問的,；(4).模塊獨立性——每個模塊完成一個相對獨立的特定子功能,，并且和其他模塊間的關(guān)系很簡單。模塊的獨立性是設(shè)計好壞的關(guān)鍵,，可以用耦合和內(nèi)聚兩個定性指標來衡量,，一般來說，要求模塊之間的耦合盡可能弱,，即模塊盡可能獨立,，且模塊的內(nèi)聚程度盡可能高。實踐表明,，內(nèi)聚更加重要,，應(yīng)把更多精力放到提高模塊的內(nèi)聚程度上,。

3.3.2 概要設(shè)計(總體設(shè)計)

• 基本任務(wù)：
  (1). 設(shè)計軟件系統(tǒng)結(jié)構(gòu)：過程如下： (2). 設(shè)計數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫：實現(xiàn)需求定義和規(guī)格說明中提出的數(shù)據(jù)對象的邏輯表示,。
  (3). 編寫概要設(shè)計文檔：概要階段的文檔有概要設(shè)計說明書,、數(shù)據(jù)庫設(shè)計說明書,、集成測試計劃,。
  (4). 概要設(shè)計文檔評審：對其進行評審。
• (程序)結(jié)構(gòu)圖：構(gòu)成的基本形式有順序形式,、選擇形式和重復形式,。4種經(jīng)常使用的模塊類型：傳入模塊、傳出模塊,、變換模塊和協(xié)調(diào)模塊,。軟件的結(jié)構(gòu)是一種層次化的關(guān)系,，支持了軟件的各個模塊之間的關(guān)系。

• 面向數(shù)據(jù)流的設(shè)計方法：在需求分析階段產(chǎn)生了數(shù)據(jù)流圖,，而面向數(shù)據(jù)流的結(jié)構(gòu)化設(shè)計能夠很輕易的將數(shù)據(jù)流圖轉(zhuǎn)換成程序結(jié)構(gòu)圖,。
  (1). 數(shù)據(jù)流圖的類型：數(shù)據(jù)流圖的信息流可分為兩種類型：變換流和事務(wù)流。相應(yīng)地,，數(shù)據(jù)流圖可分為變換型和結(jié)構(gòu)型兩種類型,。
  (2). 變換型：信息沿著輸入通路進入系統(tǒng)，從外部形式變成內(nèi)部形式,；然后經(jīng)過變換中心(主加工),；再沿著輸出通路變換成外部形式離開軟件系統(tǒng)。這種信息流就是變換流,，這種數(shù)據(jù)流圖就是變換流圖,。
  (3). 事務(wù)型：信息沿著輸入通路到達一個事務(wù)中心，事務(wù)中心根據(jù)輸入信息的類型在若干個處理序列中選擇一個來執(zhí)行,。這就是事務(wù)流,，有明顯的事務(wù)中心，各活動流以事務(wù)為起點成輻射狀流出,。
  (4). 面向數(shù)據(jù)流的結(jié)構(gòu)化設(shè)計過程：確認數(shù)據(jù)流圖的類型,；說明數(shù)據(jù)流的邊界,；把數(shù)據(jù)流圖映射為結(jié)構(gòu)圖，根據(jù)數(shù)據(jù)流圖的類型進行事務(wù)分析或變換分析,；根據(jù)設(shè)計原則進行結(jié)構(gòu)優(yōu)化,。
  (5). 結(jié)構(gòu)化設(shè)計的原則：提高模塊獨立性；模塊規(guī)模應(yīng)適中,；深度,、寬度、扇入和扇出都適當,；模塊的作用域應(yīng)位于控制域之內(nèi),；降低模塊之間接口的復雜程度；設(shè)計單入口單出口的模塊,；模塊功能可以預測,。

3.3.3 詳細設(shè)計

• 任務(wù)：為軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)。
• 過程設(shè)計工具：
  (1). 程序流程圖：方框表示加工步驟,；菱形表示邏輯條件,；箭頭表示控制流。程序流程圖不便于表示數(shù)據(jù)結(jié)構(gòu),。
  (2). N-S圖：用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖,。
  (3). PAD圖：問題分析圖，用二維樹形結(jié)構(gòu)表示程序的控制流,，將這種圖翻譯成程序代碼較容易,。
  (4). PDL：過程設(shè)計語言，也稱為偽碼,。

3.4 軟件測試

在軟件投入使用之前盡可能多的發(fā)現(xiàn)軟件中的錯誤,，是保證軟件質(zhì)量、可靠性的關(guān)鍵步驟,，是對軟件規(guī)格說明,、設(shè)計和編碼的最后復審。

• 軟件測試目的：根本目的在于盡可能多的發(fā)現(xiàn)并排除軟件中隱藏的錯誤,。
• 軟件測試準則：
  (1). 所有測試都應(yīng)追溯到用戶需求,；
  (2). 在測試之前制定測試計劃，并嚴格執(zhí)行,；
  (3). 充分注意測試中的群集現(xiàn)象,；
  (4). 避免由程序的編寫者測試自己的程序；
  (5). 不可能進行窮舉測試,；
  (6). 妥善保存測試計劃,、用例、出錯統(tǒng)計和分析報告,，為維護提供方便,。
• 軟件測試方法：根據(jù)軟件是否被執(zhí)行,，分為靜態(tài)和動態(tài)測試。按照功能分,，可以分為白盒測試和黑盒測試,。
  (1). 靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析,、代碼質(zhì)量度量等,；不實際運行軟件，而是通過人工進行分析,。
  (2). 動態(tài)測試：上機測試,，關(guān)鍵在于設(shè)計合理、高效的測試用例,。測試用例的設(shè)計方法分為白盒測試方法和黑盒測試方法,。
  (3). 白盒測試：(又稱結(jié)構(gòu)測試或邏輯驅(qū)動測試)把程序看成裝在一只透明的白盒子里，測試者必須完全了解程序的結(jié)構(gòu)和處理過程,。根據(jù)程序的內(nèi)部邏輯來設(shè)計測試用例,。其主要是在程序內(nèi)部進行，完成軟件內(nèi)部操作的驗證,。主要技術(shù)有邏輯覆蓋測試和基本路徑測試等,。
  邏輯覆蓋測試：語句覆蓋(選擇足夠多的測試用例，使被測程序中的每個語句至少執(zhí)行一次,，是邏輯覆蓋中的基本覆蓋，但是沒有關(guān)注判斷的條件中隱含的錯誤)和路徑覆蓋(執(zhí)行足夠的測試用例,，使程序中所有可能的路徑至少經(jīng)歷一次),、判定覆蓋(對每個判斷條件的取值分支T或F都要測試一次)、條件覆蓋(設(shè)計測試用例保證程序中的每個判斷的每個條件的可能取值至少執(zhí)行一次,，但可能忽略全面的判斷覆蓋的要求),、判斷-條件覆蓋(使判斷中每個條件的所有可能取值至少執(zhí)行一次，同時每個判斷的所有取值分支至少執(zhí)行一次),。
  基本路徑測試：根據(jù)控制流程確定程序的基本環(huán)路集合,，由此導出一組測試用例對每一組獨立執(zhí)行路徑進行測試。環(huán)路復雜度=程序流程圖中的判斷框個數(shù)+1就是要設(shè)計測試用例的基本路徑數(shù),。
  (4). 黑盒測試：把程序看成一只黑盒子,，完全不考慮程序的結(jié)構(gòu)和處理過程，根據(jù)規(guī)格說明書的程序外部功能來設(shè)計測試用例,，檢查是否符合規(guī)格說明的要求,。常見測試法有：等價類劃分法、邊界值分析法(設(shè)計測試用例使之剛好運行在邊界情況附近,，揭露錯誤),、錯誤推測法(列出所有的錯誤和易錯情況表,，基于此設(shè)計測試用例；針對性強,，非常實用,，但是需要豐富經(jīng)驗)等。
• 軟件測試的實施：過程：單元測試,、集成測試,、確認測試(驗收測試)、系統(tǒng)測試,。
  (1). 單元測試：針對單個模塊(軟件設(shè)計的最小單位)測試,，對軟件進行正確性的檢驗，以盡早發(fā)現(xiàn)模塊內(nèi)部可能存在的各種錯誤,。它在編碼階段進行,，依據(jù)是源程序和詳細設(shè)計說明書。采用靜態(tài)或動態(tài)測試,，動態(tài)以白盒測試法為主,，測試其結(jié)構(gòu)，黑盒測試法為輔,，測試其功能,。因為測試的是單模塊，需要一些輔助模塊去模擬與被測模塊相聯(lián)系的其他模塊,，即為測試模塊設(shè)計驅(qū)動模塊(相當于主程序,，接收測試數(shù)據(jù)，傳給被測模塊,，輸出結(jié)果)和樁模塊(虛擬子程序,，代替被測模塊調(diào)用的模塊，接受被測模塊的調(diào)用,，默認被調(diào)用的子模塊的功能,，將結(jié)果返回被測模塊)，構(gòu)成其測試環(huán)境,。
  (2). 集成測試：組裝測試,，對各模塊按照設(shè)計要求組裝成的程序進行調(diào)試，主要目的是發(fā)現(xiàn)與接口有關(guān)的,、設(shè)計階段產(chǎn)生的錯誤,。依據(jù)是概要設(shè)計說明書，通常采用黑盒測試,。內(nèi)容主要是軟件單元的接口測試,、全局數(shù)據(jù)結(jié)構(gòu)測試、邊界條件測試,、非法輸入測試,。方式可分為非增量方式集成(先分別測試每個模塊,，再按設(shè)計要求組裝在一起進行整體測試)和增量方式集成(把要測試的模塊和已經(jīng)測試的模塊連接起來測試，測試完把下一個模塊連接進來測試),。
  (3). 確認測試：檢查軟件的功能,、性能是否與用戶需求一致，依據(jù)是需求規(guī)格說明書,，常采用黑盒測試,。首先測試程序是否滿足規(guī)格說明書上的各種要求，然后進行軟件配置復審,，保證軟件配置齊全,、分類有序。
  (4). 系統(tǒng)測試：在實際運行環(huán)境中進行的一系列集成測試和確認測試,，目的是在真實的系統(tǒng)工作環(huán)境檢驗軟件是否能與系統(tǒng)正確連接,，發(fā)現(xiàn)軟件與系統(tǒng)需求不一致的地方。

3.5 程序調(diào)試

在對軟件進行成功的測試之后進行程序的調(diào)試,，診斷和改正程序中的錯誤,。

• 程序調(diào)試基本概念：測試發(fā)現(xiàn)錯誤，調(diào)試是在成功測試(發(fā)現(xiàn)了錯誤的測試)之后排除錯誤的過程,。軟件測試貫穿整個軟件生命期,，調(diào)試主要在開發(fā)階段。

• 程序調(diào)試的基本步驟：
  (1). 錯誤定位,；(2). 修改設(shè)計和代碼,，排除錯誤；(3). 進行回歸測試,，防止引進新的錯誤,。

• 程序調(diào)試的原則：
  (1). 錯誤定性和定位的原則： 集中思考分析與錯誤現(xiàn)象有關(guān)的信息；不鉆死胡同,；不要過分依賴調(diào)試工具,；避免用試探法,；
  (2). 修改錯誤的原則：錯誤可能群集,；要修改錯誤本身；必須進行回歸測試,；修改源代碼程序,，不要改變目標代碼。

• 軟件調(diào)試方法：從是否追蹤和執(zhí)行程序的角度,，分為靜態(tài)(主要調(diào)試手段)和動態(tài)調(diào)試(通過人的思維分析代碼調(diào)錯,，輔助手段)。
  (1). 強行排錯法：傳統(tǒng)方法,，很低效,；設(shè)置斷點,，程序暫停，觀察程序狀態(tài)和繼續(xù)運行程序,。
  (2). 回溯法：相當常用,，適合小程序；大程序回溯可能性很低,。
  (3). 原因排除法：二分法,，歸納法，演繹法,。都可以使用調(diào)試工具來輔助完成,，但是工具不能完全替代。

第四部分 數(shù)據(jù)庫設(shè)計基礎(chǔ)

4.1 數(shù)據(jù)庫系統(tǒng)的基本概念

• 數(shù)據(jù)：描述事物的符號記錄,。數(shù)據(jù)庫中的數(shù)據(jù)被稱為持久性數(shù)據(jù),，而存放在內(nèi)存的數(shù)據(jù)稱為臨時性數(shù)據(jù)。
• 數(shù)據(jù)庫：長期存儲在計算機內(nèi),、有組織的,、集成的、可共享的數(shù)據(jù)集合,，冗余度小,，數(shù)據(jù)獨立性和擴展性高。
• 數(shù)據(jù)庫管理系統(tǒng)：系統(tǒng)軟件,，負責數(shù)據(jù)庫中的數(shù)據(jù)組織,、數(shù)據(jù)操縱、數(shù)據(jù)維護,、控制,、保護和數(shù)據(jù)服務(wù)。
• 數(shù)據(jù)語言：包括交互式命令語言和宿主型語言,，用于定義,、操縱和控制數(shù)據(jù)。
• 數(shù)據(jù)庫管理員：管理數(shù)據(jù)庫的規(guī)劃,、設(shè)計,、維護、監(jiān)視的專人,。
• 數(shù)據(jù)庫系統(tǒng)：由以上的幾個部分組成,。
• 數(shù)據(jù)庫應(yīng)用系統(tǒng)：在數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)上，使用數(shù)據(jù)庫管理系統(tǒng)軟件和數(shù)據(jù)庫開發(fā)工具書寫出應(yīng)用程序,，開發(fā)出應(yīng)用界面,，就構(gòu)成了數(shù)據(jù)庫應(yīng)用系統(tǒng)。由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件,、應(yīng)用界面組成,。
• 數(shù)據(jù)庫技術(shù)的發(fā)展階段：

• 未來的數(shù)據(jù)庫系統(tǒng)應(yīng)支持數(shù)據(jù)管理、對象管理,、知識管理,，應(yīng)具有面向?qū)ο蟮幕咎卣鳌?/li>
• 數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)集成性、數(shù)據(jù)共享性高,，冗余性低(保證系統(tǒng)一致性的基礎(chǔ)),、數(shù)據(jù)獨立性高、數(shù)據(jù)統(tǒng)一管理與控制,。
• 數(shù)據(jù)庫系統(tǒng)體系結(jié)構(gòu)：(應(yīng)用——>外模式——>外模式/概念模式映射——>概念模式——>概念模式/內(nèi)模式的映射——>內(nèi)模式——>數(shù)據(jù)庫) 三級模式和兩級映射,。
  (1). 數(shù)據(jù)庫系統(tǒng)的三級模式結(jié)構(gòu)：
  a. 外模式：也稱子模式或用戶模式，是用戶的數(shù)據(jù)視圖,，是用戶所能夠看見和使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述,，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的邏輯表示。外模式通常是模式的子集,，它反映了用戶對數(shù)據(jù)的要求,。
  b. 概念模式：模式，是數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯結(jié)構(gòu)的描述,，全體用戶的公共數(shù)據(jù)視圖,。概念模式處于中層，反映了設(shè)計者的數(shù)據(jù)全局邏輯要求,。
  c. 內(nèi)模式：又稱物理模式,，是數(shù)據(jù)物理結(jié)構(gòu)和存儲方式的描述,，是數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式,。內(nèi)模式處于最底層，反映了數(shù)據(jù)在計算機物理結(jié)構(gòu)中的實際存儲方式。
  三個級別的模式層次反映了它們的不同環(huán)境和要求,，其中內(nèi)模式處于底層,，概念模式處于中層，外模式處于最外層,。一個數(shù)據(jù)庫只有一個內(nèi)模式和概念模式,，可以有多個外模式。
  (2). 數(shù)據(jù)庫系統(tǒng)的二級映射：
  這是在三級模式之間提供的兩級映射：外模式/概念模式的映射(使數(shù)據(jù)庫中的數(shù)據(jù)具有較高的邏輯獨立性),，概念模式/內(nèi)模式的映射(使數(shù)據(jù)庫中的數(shù)據(jù)具有較高的物理獨立性),。

4.2 數(shù)據(jù)模型

現(xiàn)有的數(shù)據(jù)庫系統(tǒng)都是基于某種數(shù)據(jù)模型而建立的，數(shù)據(jù)模型是數(shù)據(jù)庫系統(tǒng)的基礎(chǔ),。

• 數(shù)據(jù)模型三要素：
  (1). 數(shù)據(jù)結(jié)構(gòu)：對系統(tǒng)靜態(tài)特征的描述,，是數(shù)據(jù)模型的核心。
  (2). 數(shù)據(jù)操作：對系統(tǒng)動態(tài)特征的描述,，是允許的操作的集合,。
  (3). 數(shù)據(jù)約束：特定的語義約束條件，保證數(shù)據(jù)的正確,、有效,、相容。

• 數(shù)據(jù)模型的類型(按不同的應(yīng)用層次分成三種)：
  (1). 概念數(shù)據(jù)模型(概念模型)：一種面向客觀世界,、面向用戶的模型,，與具體的平臺和系統(tǒng)無關(guān)。
  (2). 邏輯數(shù)據(jù)模型(數(shù)據(jù)模型)：面向數(shù)據(jù)庫系統(tǒng)的模型,，著重與數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn),。
  (3). 物理數(shù)據(jù)模型(物理模型)：面向計算機物理實現(xiàn)的模型。

• E-R模型：實體聯(lián)系模型,。有1:1,、1:n、n:m三種聯(lián)系,?？梢灾庇^的用E-R圖表示。屬于概念模型,。

• 層次模型：用樹形結(jié)構(gòu)表示實體及其聯(lián)系,，節(jié)點是實體，樹枝是聯(lián)系,，從上到下是一對多的聯(lián)系,，有且只有一個根節(jié)點。

• 網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實體及其聯(lián)系,，是層次模型的擴展,，允許一個或多個節(jié)點無父節(jié)點,，一個節(jié)點可以有多于一個的父節(jié)點。

• 關(guān)系模型：用二維表來表示關(guān)系,，以其為基本結(jié)構(gòu)建立的模型稱為關(guān)系模型,。

4.3 關(guān)系代數(shù)

表示關(guān)系模型的數(shù)據(jù)操作的相關(guān)理論——關(guān)系代數(shù)和關(guān)系演算。

• 關(guān)系代數(shù)的基本運算：
  (1). 投影運算：從關(guān)系模式中指定若干屬性組成新的關(guān)系,。是對列屬性的去重復,。
  (2). 選擇運算：從關(guān)系模式中找出滿足指定條件的數(shù)據(jù)項的操作稱為選擇。
  (3). 笛卡爾積：設(shè)有n元關(guān)系R和m元關(guān)系S,，它們分別有p和q個記錄,，則笛卡爾積為RxS，是一個m+n元關(guān)系,，記錄有pxq個,。
• 關(guān)系代數(shù)的擴充運算：
  (1). 交。集合運算之一,，是兩個關(guān)系的交集,。
  (2). 連接和自然連接。連接是從兩個關(guān)系的笛卡爾積中選擇滿足給定屬性間的一定條件的那些元組,。其中的一個特例是自然連接,，要求兩個關(guān)系中進行比較的是相同的屬性，并且進行等值連接,，還有去掉重復的屬性列,。
  (3). 除。近似于笛卡爾積的逆運算,。
  (4). 并,。集合運算之一，是兩個關(guān)系的并集,。
• 關(guān)系代數(shù)的應(yīng)用實例：關(guān)系代數(shù)雖然形式簡單,，但它足以滿足對表的查詢、插入,、刪除和修改操作,。

4.4 數(shù)據(jù)庫設(shè)計與管理

數(shù)據(jù)庫設(shè)計是數(shù)據(jù)應(yīng)用的核心，根本目標是要解決數(shù)據(jù)共享問題,。

• 數(shù)據(jù)庫設(shè)計：是對于一個給定的應(yīng)用環(huán)境,，構(gòu)造最優(yōu)的數(shù)據(jù)庫模式，建立性能良好的數(shù)據(jù)庫,，滿足用戶的信息需求(靜態(tài)要求)和處理需求(動態(tài)要求),。
• 數(shù)據(jù)庫設(shè)計方法：面向數(shù)據(jù)的方法：以信息需求為主，兼顧處理需求,；面向過程的方法：以處理需求為主,，兼顧信息需求,。面向數(shù)據(jù)的方法是主流。
• 數(shù)據(jù)庫設(shè)計的步驟：
  生命周期法：
  (1). 需求分析階段：成果：需求說明書,。設(shè)計數(shù)據(jù)庫的起點，收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流程圖是下一步設(shè)計概念結(jié)構(gòu)的基礎(chǔ),。方法主要有兩種：結(jié)構(gòu)化分析(SA,，自頂向下，逐步分解,；使用數(shù)據(jù)流程圖和數(shù)據(jù)字典,，數(shù)據(jù)字典包含數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu),、數(shù)據(jù)流,、數(shù)據(jù)存儲和處理過程)和面向?qū)ο蠓治觥?br> (2). 概念設(shè)計階段：成果：概念數(shù)據(jù)模型。分析數(shù)據(jù)間的語義關(guān)聯(lián),，在此基礎(chǔ)上建立一個數(shù)據(jù)的概念模型,。方法有集中式模式設(shè)計法(設(shè)計簡單方便，強調(diào)統(tǒng)一一致,，適合小型單位)和視圖集成設(shè)計法(先做局部在合并,；選擇局部應(yīng)用，視圖設(shè)計——逐一設(shè)計分E-R圖,，視圖集成——合并E-R圖,，得到概念模式，常見的沖突有命名,、概念,、域、約束沖突,；策略：自頂向下,，自底向上，自內(nèi)向外),。
  (3). 邏輯設(shè)計階段：成果：邏輯數(shù)據(jù)模型,。將E-R圖轉(zhuǎn)換為關(guān)系模式(即關(guān)系數(shù)據(jù)模型)，這就是邏輯設(shè)計的主要內(nèi)容,。在關(guān)系模式的基礎(chǔ)上進行關(guān)系視圖設(shè)計(外模式設(shè)計,，用戶子模式設(shè)計)，關(guān)系視圖具有優(yōu)點(提供數(shù)據(jù)邏輯獨立性,；能夠適應(yīng)用戶對數(shù)據(jù)的不同需求,；有一定的數(shù)據(jù)保密功能)。其后還要進行規(guī)范化,。
  (4). 物理設(shè)計階段：成果：數(shù)據(jù)庫內(nèi)模型,。是為一個給定的邏輯模型選取一個最適合應(yīng)用要求的物理結(jié)構(gòu)的過程,。一般留給用戶的內(nèi)容有索引設(shè)計、集簇設(shè)計,、分區(qū)設(shè)計,。
• 數(shù)據(jù)庫管理：對數(shù)據(jù)庫中的共享資源進行維護和管理，這是數(shù)據(jù)庫管理員的責任,。包含數(shù)據(jù)庫的建立,、調(diào)整、重組,、安全性和完整性控制,、故障恢復、數(shù)據(jù)庫監(jiān)控6大功能,。