算法

算法基本特征

• 算法：指解題方案的準(zhǔn)確而完整的描述（≠程序 ≠計(jì)算方法）
• 算法四個(gè)特點(diǎn)：可行性 確定性 有窮性 足夠的情報(bào)

程序的設(shè)計(jì)不可能優(yōu)于算法的設(shè)計(jì)

有窮性：算法程序的運(yùn)行時(shí)間是有限的

算法的基本要素

• 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸
• 算法的控制結(jié)構(gòu)
  • 算法中各操作之間的執(zhí)行順序
  • 描述算法的工具：傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、自然描述語(yǔ)言、偽代碼描述、程序
  • 一個(gè)算法可以用順序、選擇（分支） 、循環(huán)（重復(fù)）三種基本結(jié)構(gòu)組合而成
• 算法的復(fù)雜度
  • 時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量（基本運(yùn)算次數(shù)），與所用計(jì)算工具無(wú)關(guān)，與采用的算法描述語(yǔ)言無(wú)關(guān)
  • 空間復(fù)雜度：執(zhí)行算法所需要的內(nèi)存空間（計(jì)算機(jī)所需存儲(chǔ)空間）

設(shè)計(jì)算法時(shí)需要考慮算法的的時(shí)間和空間復(fù)雜度，但兩者相互獨(dú)立，毫無(wú)關(guān)聯(lián)

• 算法分析方法：平均性態(tài)、最壞情況復(fù)雜性
• 算法分析目的：降低算法復(fù)雜度，提高算法的執(zhí)行效率，以求改進(jìn)
• 算法設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減半遞推、回溯

算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)

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

image

數(shù)據(jù)

• 數(shù)據(jù)：需要處理的數(shù)據(jù)元素的集合

• 數(shù)據(jù)元素：數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體，也是結(jié)點(diǎn)

  有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(Data Item)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位

• 結(jié)構(gòu)：集合中各數(shù)據(jù)元素之間存在的某種前后件關(guān)系

• 數(shù)據(jù)結(jié)構(gòu)：指帶有結(jié)構(gòu)的相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合

【真題】設(shè)數(shù)據(jù)集合為D={1，2，3，4，5}，則結(jié)構(gòu)B=(D,R)中為非線性結(jié)構(gòu)的是

R={(1,2)，(2,3)，(4,3)，(3,5)} 非線性【1→2→3→5、4→3】（√）

R={(1,2)，(2,3)，(3,4)，(4,5)} 線性【1→2→3→4→5】（×）

數(shù)據(jù)結(jié)構(gòu)的分類(lèi)

數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門(mén)學(xué)科，主要研究三個(gè)方面：數(shù)據(jù)間固有邏輯結(jié)構(gòu)關(guān)系、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)關(guān)系、數(shù)據(jù)結(jié)構(gòu)的運(yùn)算

• 邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的前后件邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)（與所使用的計(jì)算機(jī)無(wú)關(guān)）
• 存儲(chǔ)結(jié)構(gòu)：即物理結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)空間中的存放方式（不同的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)處理的效率不同，與效率有關(guān)）
  • 順序結(jié)構(gòu)：主要用于線性的數(shù)據(jù)結(jié)構(gòu)
  • 鏈?zhǔn)浇Y(jié)構(gòu)：每一個(gè)結(jié)點(diǎn)至少包含一個(gè)指針域，用指針的指向來(lái)體現(xiàn)數(shù)據(jù)元素之間在邏輯上的聯(lián)系 ，優(yōu)點(diǎn)是便于插入和刪除操作
  • 索引結(jié)構(gòu)：帶有目錄與內(nèi)容

image

image

image

線性表

• 線性表：由n(n≥0)個(gè)數(shù)據(jù)元素構(gòu)成的有限序列，表中由且只有一個(gè)根結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，除根元素外的其它元素有且只有一個(gè)前件，除終端元素外的其它元素有且只有一個(gè)后件（如：春→夏→秋→冬）
• 線性表的順序存儲(chǔ)結(jié)構(gòu)叫做順序表（隨機(jī)存?。?，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)叫做線性鏈表（順序存?。?/li>

順序表

1. 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的
2. 線性表中數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的
3. 可以隨機(jī)訪問(wèn)數(shù)據(jù)元素
4. 做插入、刪除時(shí)需移動(dòng)大量元素，因此線性表不便于插入和刪除元素
5. 其存儲(chǔ)空間連續(xù)，各個(gè)元素所占字節(jié)數(shù)相同，元素的存儲(chǔ)順序與邏輯順序一致

image

線性鏈表

1. 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)
2. 各數(shù)據(jù)元素的存儲(chǔ)順序與邏輯順序可以不一致，可任意
3. 所占存儲(chǔ)空間大于順序存儲(chǔ)結(jié)構(gòu)（每節(jié)點(diǎn)多出至少一個(gè)指針域）
4. 查找結(jié)點(diǎn)時(shí)要比順序存儲(chǔ)慢
5. 插入刪除元素比順序存儲(chǔ)靈活

• 線性鏈表的操作：在線性鏈表中進(jìn)行插入與刪除，不需要移動(dòng)鏈表中的元素

  image

棧

1. 棧的入口和出口是同一個(gè)口，只能在棧頂進(jìn)行插入和刪除

2. 棧的修改原則是“先進(jìn)后出”或“后進(jìn)先出”

3. 棧的棧底指針bottom和棧頂指針top，從入棧到棧滿再到退棧，棧低指針bottom不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化（指針存放的是地址而非數(shù)據(jù)）

4. 棧能臨時(shí)保存數(shù)據(jù)，具有記憶功能

5. 棧支持子程序調(diào)用

   image

一個(gè)棧的初始狀態(tài)為空。將元素abcde依次入棧，不可能的出棧順序?yàn)椋‥）

A.edcba B.dcbae C.badce D.cbaed E.eabcd

用一個(gè)長(zhǎng)度為50的數(shù)組(數(shù)組元素的下標(biāo)從0到49)作為棧的存儲(chǔ)空間，如果bottom=49，top=30(數(shù)組下標(biāo))，則棧中具有的元素個(gè)數(shù)為【20】（49-30+1=20）

設(shè)棧的存儲(chǔ)空間為S（1：60），初始狀態(tài)為top=61?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后，top=25，則棧中的元素個(gè)數(shù)為【36】（60-25+1=36）

棧內(nèi)元素個(gè)數(shù)計(jì)算：丨Top－Bottom丨＋1 （其中Bottom≥1），若T＝B＝0說(shuō)明棧空

鏈?zhǔn)綏１容^特殊，當(dāng)中存放元素與地址，但其棧底指針bottom可以改變

隊(duì)列

1. 隊(duì)列中隊(duì)頭指針front指向?qū)︻^元素的前一位置，隊(duì)尾指針rear指向最末元素，從入隊(duì)到出隊(duì)
2. 隊(duì)列的入口和出口非同一個(gè)口，只允許在隊(duì)尾插入，而在隊(duì)頭刪除
3. 隊(duì)列的修改原則是“先進(jìn)先出”或“后進(jìn)后出”（先到先服務(wù)的作業(yè)調(diào)度）
4. 隊(duì)列中元素隨front和rear的變化而動(dòng)態(tài)變化，并非固定

• 循環(huán)隊(duì)列：將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用

  image

  求隊(duì)列中的元素個(gè)數(shù)s（由rear與front共同決定）

  1. rear＞front s=rear-front
     . rear＜front s=rear-front+總?cè)萘?br> . rear＝front s=0或者s=容量(滿)

  設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q（1:40），初始狀態(tài)為front=rear=40。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=15，此后又正常地退出了一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為 【39】 （當(dāng)頭尾指針都是15之后還能退出元素，說(shuō)明初始狀態(tài)為滿，故退出一個(gè)元素，即40-1=3）

樹(shù)

• 樹(shù)：指n(n＞0)個(gè)元素的有限集合，它有且僅有一個(gè)稱為根的元素，其余元素是互不相交的子樹(shù)

image

• 概念術(shù)語(yǔ)：
  • 父結(jié)點(diǎn)（A是BCD的父）、子結(jié)點(diǎn)（BCD是A的子)
  • 根結(jié)點(diǎn)（A）、葉子結(jié)點(diǎn)（KLFMHNJ）
  • 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)（A的度為3、B的度為2）
  • 樹(shù)的度：具有結(jié)點(diǎn)中最大的度（上圖為3）
  • 樹(shù)的深度：整棵樹(shù)的層數(shù)（上圖為4）
  • 子樹(shù)：在一棵樹(shù)中以某個(gè)結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根所構(gòu)成的樹(shù)（如B→EF→KL這一左半部分）

二叉樹(shù)

二叉樹(shù)是一個(gè)有限的結(jié)點(diǎn)集合，該集合或?yàn)榭?，或由一個(gè)根結(jié)點(diǎn)及其兩棵互不相交的左右二叉子樹(shù)所組成

image

• 二又樹(shù)的特點(diǎn)
  1. 非空二又樹(shù)只有一個(gè)根結(jié)點(diǎn)
  2. 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)
• 特殊二叉樹(shù)

image

滿二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值。

完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)

滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不是滿二叉樹(shù)

• 二叉樹(shù)的性質(zhì)：

  1. 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，分別稱為左子樹(shù)和右子樹(shù)
  2. 在二叉樹(shù)的第k層上，最多有2^(k-1)個(gè)結(jié)點(diǎn)
  3. 深度為m的二叉樹(shù)最多有2^(m)-1個(gè)結(jié)點(diǎn)
  4. 度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，度=0的結(jié)點(diǎn)總比度=2的結(jié)點(diǎn)多1個(gè)
  5. 有n個(gè)結(jié)點(diǎn)的二叉樹(shù)深度至少為[log(2)n]+1

• 二叉樹(shù)的遍歷：按照一定的順序不重復(fù)不遺漏地訪問(wèn)二叉樹(shù)中的結(jié)點(diǎn)

  image

  前序遍歷：訪問(wèn)根結(jié)點(diǎn)→前序遍歷左子樹(shù)→前序遍歷右子樹(shù)（ABDGECF）（根左右）
  中序遍歷：中序遍歷左子樹(shù)→訪問(wèn)根結(jié)點(diǎn)→中序遍歷右子樹(shù)（DGBEACF）（左根右）
  后序遍歷：后序遍歷左子樹(shù)→后序遍歷右子樹(shù)→訪問(wèn)根結(jié)點(diǎn)（GDEBFCA）（左右根）

查找技術(shù)

• 順序查找：從第一個(gè)或最后一個(gè)記錄開(kāi)始，一直到查找出給定值，結(jié)束查找

• 二分查找：在有序表中取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等，查找成功；若小于則找左半?yún)^(qū)，若大于則找右半?yún)^(qū)，不斷重復(fù)直到成功

  image

  注意：即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找

排序

• 冒泡排序：從頭到尾重復(fù)比較相鄰的兩元素，如果前比后大，就交換彼此，直到?jīng)]有相鄰元素需要交換則完成排序，越大的元素會(huì)經(jīng)交換慢慢“浮”到數(shù)列的后端
• 快速排序：選第一個(gè)數(shù)作為基準(zhǔn)數(shù)，將之后所有的數(shù)與其做比較，比基大放右區(qū)，比基小放左區(qū)，此時(shí)線性表被分割為兩個(gè)子表，再對(duì)兩個(gè)子表重復(fù)上述步驟，直到各字表的長(zhǎng)度為1則完成排序
• 簡(jiǎn)單插入排序：將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中，像軍訓(xùn)時(shí)按身高逐個(gè)糾正排序
• 希爾排序：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行簡(jiǎn)單插入排序
• 簡(jiǎn)單選擇排序：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，以此類(lèi)推直到所有元素均排序完畢
• 堆排序：選建堆，然后將堆頂元素與堆中最后一個(gè)元素交換，再調(diào)整為堆

image

最壞情況下，比較次數(shù)最少的是堆排序

要求內(nèi)存量最大的是歸并排序

當(dāng)數(shù)據(jù)表中每個(gè)元素距其最終位置不遠(yuǎn)，最節(jié)省時(shí)間的是簡(jiǎn)單插入排序

選擇排序與冒泡排序的區(qū)別：冒泡排序通過(guò)依次交換相鄰兩個(gè)順序不合法的元素位置，從而將當(dāng)前最?。ù螅┰胤诺胶线m的位置；而選擇排序每遍歷一次都記住了當(dāng)前最?。ù螅┰氐奈恢?，最后僅需一次交換操作即可將其放到合適的位置。

程序設(shè)計(jì)基礎(chǔ)

程序設(shè)計(jì)方法與風(fēng)格

• 相關(guān)術(shù)語(yǔ)
  • 程序：將計(jì)算機(jī)語(yǔ)言代碼依據(jù)一定的語(yǔ)法規(guī)則，描述為完成特定任務(wù)的算法的指令序列，程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)
  • 程序設(shè)計(jì)：程序設(shè)計(jì)為完成一項(xiàng)程序工作的過(guò)程
  • 計(jì)算機(jī)語(yǔ)言：計(jì)算機(jī)語(yǔ)言是人與計(jì)算機(jī)交流的工具
  • Wirth公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序
• 良好的程序設(shè)計(jì)風(fēng)格：清晰第一，效率第二
• 良好的程序設(shè)計(jì)風(fēng)格
  1. 源程序內(nèi)部文檔化
     • 選擇標(biāo)識(shí)符的名字
     • 程序的視覺(jué)組織
     • 程序的注釋
       • 功能性注釋：位于模塊內(nèi)部，用于描述其后語(yǔ)句或程序主要功能
       • 序言性注釋：位于模塊首部，用于說(shuō)明模塊的相關(guān)信息（程序的標(biāo)題 功能的說(shuō)明 主要的算法 模塊接口 開(kāi)發(fā)歷史 程序設(shè)計(jì)者 復(fù)審者 復(fù)審日期 修改日期）
  2. 數(shù)據(jù)說(shuō)明
     • 數(shù)據(jù)說(shuō)明的次序規(guī)范化
     • 說(shuō)明語(yǔ)句中變量安排有序化
     • 使用注釋來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)
  3. 語(yǔ)句的結(jié)構(gòu)
     • 在一行內(nèi)只寫(xiě)一條語(yǔ)句
     • 程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性
     • 程序編寫(xiě)要做到清晰第一，效率第二
     • 在保證程序正確的基礎(chǔ)上再要求提高效率
     • 避免使用臨時(shí)變量而使程序的可讀性下降
     • 避免不必要的轉(zhuǎn)移
     • 盡量使用庫(kù)函數(shù)
     • 避免采用復(fù)雜的條件語(yǔ)句
     • 盡量減少使用“否定”條件語(yǔ)句
     • 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化
     • 要模塊化，使模塊功能盡可能單一化
     • 利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性
     • 從數(shù)據(jù)出發(fā)去構(gòu)造程序
     • 不要修補(bǔ)不好的程序，要重新編寫(xiě)
  4. 輸入和輸出
     • 對(duì)輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性
     • 檢查輸入項(xiàng)的各種重要組合的合法性
     • 輸入格式要簡(jiǎn)單，使得輸入的步驟和操作盡可能簡(jiǎn)單
     • 輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式
     • 應(yīng)允許缺省值
     • 輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志
     • 在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過(guò)程中和輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息
     • 當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性，給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式

良好程序設(shè)計(jì)風(fēng)格不僅有助于提高程序的可靠性、可理解性、可測(cè)試性、可維護(hù)性和可重復(fù)性，而且也能夠促進(jìn)技術(shù)的交流，改善軟件的質(zhì)量

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

• 軟件設(shè)計(jì)的基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性、可靠性
• 結(jié)構(gòu)化程序設(shè)計(jì)風(fēng)格：程序結(jié)構(gòu)良好、可讀性好、易測(cè)試、易維護(hù)
• 結(jié)構(gòu)化程序設(shè)計(jì)原則
  • 自頂向下：先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)
  • 逐步求精：對(duì)復(fù)雜問(wèn)題，先設(shè)計(jì)一個(gè)目標(biāo)作為過(guò)渡，然后逐步細(xì)化
  • 模塊化：把程序要解決的總目標(biāo)分解為一個(gè)一個(gè)的模塊
  • 限用goto語(yǔ)句：程序的質(zhì)量與goto語(yǔ)句數(shù)量成反比
• 結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序、選擇（分支）、循環(huán)（重復(fù)）
• 程序設(shè)計(jì)語(yǔ)言的基本成分：數(shù)據(jù)成分、運(yùn)算成分、控制成分、傳輸成分

設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是程序結(jié)構(gòu)應(yīng)有助于讀者理解（強(qiáng)調(diào)程序易讀性）

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

• 面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)
  1. 與人類(lèi)習(xí)慣的思維方法致
  2. 穩(wěn)定性好
  3. 可重用性好
  4. 易于開(kāi)發(fā)大型軟件產(chǎn)品
  5. 可維護(hù)性好

與傳統(tǒng)的的面向過(guò)程的方法不同之處：

面向?qū)ο蟮某绦蛟O(shè)計(jì)主張從客觀世界固有的物質(zhì)出發(fā)來(lái)構(gòu)造系統(tǒng)，使用現(xiàn)實(shí)世界的概念抽象地思考問(wèn)題從而自然地解決問(wèn)題，它提倡用人類(lèi)在現(xiàn)實(shí)生活中常用的思維方式來(lái)認(rèn)識(shí)理解描述客觀事物

• 對(duì)象有關(guān)概念術(shù)語(yǔ)

  • 對(duì)象：在現(xiàn)實(shí)世界中，每個(gè)實(shí)體都是對(duì)象（大學(xué)生、汽車(chē)、電視機(jī)、空調(diào)）
  • 屬性：用于描述對(duì)象的狀態(tài)
  • 方法：用于描述對(duì)象的行為
  • 類(lèi)：一組具有相同屬性和相同操作的對(duì)象的集合
  • 消息：是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，對(duì)象間的通信靠消息傳遞
    1. 接收消息的對(duì)象的名稱
    2. 消息標(biāo)識(shí)符，也稱消息名
    3. 零個(gè)或多個(gè)參數(shù)

  “對(duì)象是屬性和方法的封裝體”、“任何對(duì)象不一定有繼承性”

  “對(duì)象是類(lèi)的具體實(shí)例，類(lèi)是對(duì)象的抽象”、“操作是對(duì)象的動(dòng)態(tài)屬性”

  基于同一類(lèi)產(chǎn)生的對(duì)象可以分別設(shè)置各自的屬性，對(duì)象中的屬性只能通過(guò)該對(duì)象所提供的操作來(lái)存取或修改

• 對(duì)象的基本特點(diǎn)

  1. 標(biāo)識(shí)唯一性：對(duì)象可由內(nèi)在本質(zhì)來(lái)區(qū)分，而不是通過(guò)描述來(lái)區(qū)分
  2. 分類(lèi)性：可以將具有相同屬性和操作的對(duì)象抽象成類(lèi)
  3. 多態(tài)性：同一操作可以是不同對(duì)象的行為，同樣的消息被不同對(duì)象接受時(shí)可導(dǎo)致完全不同的行為
  4. 封裝性：從外面看不到對(duì)象的內(nèi)部，只能看到對(duì)象外部特征，實(shí)現(xiàn)信息隱蔽，是數(shù)據(jù)與操作的結(jié)合，是屬性與方法的封裝
  5. 模塊獨(dú)立性好：對(duì)象是面向?qū)ο蟮能浖幕灸K，高內(nèi)聚低耦合
  6. 繼承性：使用已有的類(lèi)建立新類(lèi)的定義技術(shù)，能直接獲得已有的性質(zhì)，而不必重復(fù)定義他們，是類(lèi)之間共享屬性和操作的機(jī)制
  7. 多態(tài)性：同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象
  8. 依賴性：某個(gè)對(duì)象的功能依賴于另外的某個(gè)對(duì)象，而被依賴的對(duì)象只是作為一種工具在使用，而并不持有對(duì)它的引用

軟件工程基礎(chǔ)

image

軟件工程基本概念

• 軟件分類(lèi)：

  • 系統(tǒng)軟件：操作系統(tǒng)、編譯程序、匯編程序、網(wǎng)絡(luò)軟件、數(shù)據(jù)庫(kù)管理系統(tǒng)
  • 應(yīng)用軟件：事務(wù)處理軟件、工程與科學(xué)計(jì)算軟件、實(shí)時(shí)處理軟件、人工智能軟件、財(cái)務(wù)管理系統(tǒng)
  • 支撐軟件（工具軟件）：需求分析工具軟件、編譯工具軟件、測(cè)試工具軟件、維護(hù)工具軟件、Word編輯軟件

  學(xué)生成績(jī)管理系統(tǒng)、教務(wù)管理系統(tǒng)屬于應(yīng)用軟件

• 軟件危機(jī)：需求增長(zhǎng)、開(kāi)發(fā)難控、質(zhì)量難保、難以維護(hù)、成本提高、生產(chǎn)率低

• 軟件工程：應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序；其目的是<u>提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低軟件成本</u>；其核心思想是<u>把軟件當(dāng)作一個(gè)工程產(chǎn)品來(lái)處理</u>

• 軟件工程三要素

  • 方法是完成軟件工程項(xiàng)目的技術(shù)手段
  • 工具支持軟件的開(kāi)發(fā)、管理和文檔生成
  • 過(guò)程支持軟件開(kāi)發(fā)的各環(huán)節(jié)的控制和管理

• 軟件生命周期：將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程

  • 軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)代價(jià)
  • 分為3個(gè)時(shí)期8個(gè)階段，維護(hù)是持續(xù)時(shí)間最長(zhǎng)，花費(fèi)代價(jià)最大的一個(gè)時(shí)期
    • 軟件定義階段（問(wèn)題定義可行性研究、需求分析）
    • 軟件開(kāi)發(fā)階段（概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試）
    • 軟件運(yùn)行維護(hù)階段（使用、維護(hù)）

• 需求分析：確定系統(tǒng)的邏輯模型。參加人員有用戶、項(xiàng)目負(fù)責(zé)人和系統(tǒng)分析員

  • 需求分析的工作：需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)、需求評(píng)審
  • 需求分析階段產(chǎn)生的主要文檔為需求規(guī)格說(shuō)明書(shū)，其作用為：
    1. 便于用戶、開(kāi)發(fā)人員進(jìn)行理解交流
    2. 反映用戶問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù)
    3. 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)

• 需求規(guī)格說(shuō)明書(shū)（SRS）需求分析階段產(chǎn)生的主要文檔是“軟件需求規(guī)格說(shuō)明書(shū)”，其特點(diǎn)是：

  • 正確性：體現(xiàn)待開(kāi)發(fā)系統(tǒng)的真實(shí)要求·無(wú)歧義性：對(duì)每個(gè)需求只有一種解釋
  • 完整性：包括全部有意義的需求
  • 一致性：各個(gè)需求的描述不矛盾
  • 可驗(yàn)證性：每個(gè)需求都是可驗(yàn)證的
  • 可理解性：需求說(shuō)明書(shū)必須簡(jiǎn)明易懂
  • 可修改性：結(jié)構(gòu)風(fēng)格在改變時(shí)，是易于實(shí)現(xiàn)的
  • 可追蹤性：每個(gè)需求的來(lái)源和流向是清晰的

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

• 需求分析方法包括結(jié)構(gòu)化需求分析方法、面向?qū)ο蟮姆治龇椒?/code>

• 結(jié)構(gòu)化分析方法是一種使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、判定表和判定樹(shù)等工具，來(lái)建立系統(tǒng)的邏輯模型。

• 數(shù)據(jù)流圖（DFD）是結(jié)構(gòu)化方法的需求分析工具，其圖形元素：

  • 〇 加工：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出
  • → 數(shù)據(jù)流：沿箭頭方向傳遞數(shù)據(jù)的通道
  • ＝ 存儲(chǔ)文件（數(shù)據(jù)源）：存放各種數(shù)據(jù)的文件
  • ? 源（潭）：系統(tǒng)和環(huán)境的接口
  image

• 數(shù)據(jù)字典（DD）：對(duì)數(shù)據(jù)流圖中所有元素定義的集合，它是結(jié)構(gòu)化分析的核心。

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

• 軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象、 概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。

• 軟件設(shè)計(jì)的劃分

  • 按工程管理角度劃分：概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)
  • 按技術(shù)觀點(diǎn)劃分：結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)

• 軟件設(shè)計(jì)基本原理

  • 抽象：在軟件設(shè)計(jì)中，可以定出多個(gè)抽象級(jí)別，抽象層次從概要設(shè)計(jì)到詳細(xì)設(shè)計(jì)逐步降低。
  • 模塊化：把一個(gè)待開(kāi)發(fā)的軟件分解成若干小的簡(jiǎn)單的部分，自頂向下逐層把軟件劃分成若干模塊。
  • 信息隱蔽：一個(gè)模塊內(nèi)的信息，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)不能訪問(wèn)。
  • 模塊獨(dú)立性：每個(gè)模塊只完成獨(dú)立的子功能，并且與其他模塊的聯(lián)系少且接口簡(jiǎn)單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。

• 軟件模塊獨(dú)立性

  • 高內(nèi)聚性：指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度
  • 低耦合性：指模塊間互相連接的緊密程度

  耦合包括非直接耦合、數(shù)據(jù)耦合、標(biāo)記耦合、控制耦合、外部耦合、公共耦合、內(nèi)容耦合（耦合度逐漸增強(qiáng)）

• 概要設(shè)計(jì)的任務(wù)：

  1. 設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)
  2. 數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)
  3. 編寫(xiě)概要設(shè)計(jì)文檔
  4. 概要設(shè)計(jì)文檔評(píng)審

• 概要設(shè)計(jì)的常用工具是程序結(jié)構(gòu)圖（SC），其基本圖形：? 一般模塊、〇→ 數(shù)據(jù)信息、●→ 控制信息

  image

• 詳細(xì)設(shè)計(jì)的任務(wù)：確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。

• 詳細(xì)設(shè)計(jì)的常用工具：

  • 圖形工具：程序流程圖、N-S圖、PAD、HIPO
  • 表格工具：判定表
  • 語(yǔ)言工具：PDL（偽碼）

• 程序流程圖的基本圖形：→ 控制流、? 加工步驟、◇ 邏輯條件

  image

軟件測(cè)試

• 軟件測(cè)試的目的：發(fā)現(xiàn)程序中的錯(cuò)誤

• 軟件測(cè)試的準(zhǔn)則

  • 所有測(cè)試都應(yīng)追溯到用戶需求
  • 在測(cè)試之前制定測(cè)試計(jì)劃，并嚴(yán)格執(zhí)行
  • 充分注意測(cè)試中的群集現(xiàn)象
  • 避免由程序的編寫(xiě)者測(cè)試自己的程序
  • 不可能進(jìn)行窮舉測(cè)試
  • 妥善保存測(cè)試分析報(bào)告，為維護(hù)提供方便

• 軟件測(cè)試的類(lèi)型

  • 靜態(tài)測(cè)試：不實(shí)際運(yùn)行軟件，通過(guò)人發(fā)揮思維優(yōu)勢(shì)發(fā)現(xiàn)程序的錯(cuò)誤

  • 動(dòng)態(tài)測(cè)試：基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程

  • 白盒測(cè)試：把測(cè)試對(duì)象看作一個(gè)打開(kāi)的盒子，利用程序內(nèi)部的邏輯結(jié)構(gòu)，對(duì)程序所有邏輯路徑進(jìn)行測(cè)試

    白盒測(cè)試針對(duì)程序的內(nèi)部邏輯結(jié)構(gòu)

    其方法有邏輯覆蓋測(cè)試、基本路徑測(cè)試

  • 黑盒測(cè)試：完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)，只檢查程序是否能接收輸入數(shù)據(jù)而產(chǎn)生正確的輸出信息

    黑盒針對(duì)程序的外部功能

    其方法有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤推測(cè)法

• 軟件測(cè)試的步驟

  1. 單元測(cè)試：對(duì)軟件設(shè)計(jì)的最小單位——模塊進(jìn)行測(cè)試，目的是發(fā)現(xiàn)各模塊內(nèi)部的錯(cuò)誤。
  2. 集成測(cè)試：把模塊按照設(shè)計(jì)要求組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。
  3. 確認(rèn)測(cè)試：驗(yàn)證軟件的功能和性能是否滿足各種需求，以及軟件配置是否完全、正確。
  4. 系統(tǒng)測(cè)試：將軟件作為一個(gè)元素，與計(jì)算機(jī)系統(tǒng)其他元素組合在一起，進(jìn)行集成測(cè)試。

程序調(diào)試

• 程序調(diào)試是對(duì)程序進(jìn)行了成功的測(cè)試之后將進(jìn)入程序調(diào)試，通常稱為Debug（排錯(cuò)），主要在開(kāi)發(fā)階段進(jìn)行。
• 程序調(diào)試的任務(wù)：診斷和改正程序的錯(cuò)誤
• 程序調(diào)試的基本步驟
  1. 錯(cuò)誤定位
  2. 修改設(shè)計(jì)和代碼，以排除錯(cuò)誤
  3. 進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤
• 程序調(diào)試的方法：強(qiáng)行排除法、回溯法、原因排除法

數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)

數(shù)據(jù)庫(kù)基本概念

• 數(shù)據(jù)（data）：描述事物的符號(hào)記錄

• 數(shù)據(jù)庫(kù)（Database）：數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享

  數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有兩大特點(diǎn)：“集成”與“共享”

  數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)：解決數(shù)據(jù)共享問(wèn)題

• 數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：數(shù)據(jù)庫(kù)的機(jī)構(gòu)，一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)，它是數(shù)據(jù)庫(kù)系統(tǒng)的核心

  • 數(shù)據(jù)定義語(yǔ)言（DDL，Definition）：數(shù)據(jù)模式定義、數(shù)據(jù)存取的物理構(gòu)建
  • 數(shù)據(jù)操縱語(yǔ)言（DML，Manipulation）：數(shù)據(jù)操縱（包括查詢與增、刪、改等操作）
  • 數(shù)據(jù)控制語(yǔ)言（DCL，Control）：數(shù)據(jù)的完整性、安全性的定義與檢查、并發(fā)控制、故障恢復(fù)
  • 數(shù)據(jù)查詢語(yǔ)言（DQL，Query）：集數(shù)據(jù)定義、操縱和控制功能于一體的數(shù)據(jù)庫(kù)語(yǔ)言，是數(shù)據(jù)庫(kù)的核心語(yǔ)言， 具有操作所有關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)的能力

• 數(shù)據(jù)庫(kù)管理員（DBA）：主要工作包括數(shù)據(jù)庫(kù)規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視，改善系統(tǒng)性能、提高系統(tǒng)效率

• 數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）：利用數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行應(yīng)用開(kāi)發(fā)可構(gòu)成一個(gè)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)，它是專門(mén)為一類(lèi)用戶設(shè)計(jì)的系統(tǒng)，不具有通用性，由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件以及應(yīng)用界面組成

  image

• 數(shù)據(jù)庫(kù)系統(tǒng)（DBS）的組成

  • 數(shù)據(jù)庫(kù)（數(shù)據(jù)）
  • 數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS（軟件）
  • 數(shù)據(jù)庫(kù)管理員DBA（人員）
  • 軟件平臺(tái)
  • 硬件平臺(tái)

• 數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)：高集成性、高共享低冗余、物理獨(dú)立性與邏輯獨(dú)立性、統(tǒng)一管理與控制

  數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序，==在數(shù)據(jù)系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)并不一定與邏輯結(jié)構(gòu)一致==

  邏輯獨(dú)立性——指用戶的應(yīng)用程序與數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)是相互獨(dú)立的，即當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，用戶程序也可以不變，當(dāng)數(shù)據(jù)庫(kù)中數(shù)據(jù)總體邏輯結(jié)構(gòu)發(fā)生變化，而應(yīng)用程序不受影響

• 數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系

  • 三級(jí)模式
    • 概念模式（概念數(shù)據(jù)庫(kù)）：全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，即全體用戶的公共數(shù)據(jù)視圖
    • 外模式（用戶數(shù)據(jù)庫(kù)）：又稱子模式或用戶模式，即用戶的數(shù)據(jù)視圖，反映用戶對(duì)數(shù)據(jù)的要求
    • 內(nèi)模式（物理數(shù)據(jù)庫(kù)）：給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與存取方法，反映數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)上的實(shí)際存儲(chǔ)形式，如數(shù)據(jù)存儲(chǔ)的文件結(jié)構(gòu)、索引、集簇及hash等存取方式與存取路徑
  • 二級(jí)映射
    • 外模式/概念模式的映射：實(shí)現(xiàn)了外槿式到概念模式之間的相互轉(zhuǎn)換（當(dāng)邏輯模式發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立性）
    • 概念模式/內(nèi)模式的映射：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換（當(dāng)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫(kù)的邏輯模式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨(dú)立性）

  image

  三級(jí)模式反映了模式的三個(gè)不同環(huán)境及其他們的不同要求

  兩級(jí)映射保證了數(shù)據(jù)庫(kù)中數(shù)據(jù)具有較高的邏輯獨(dú)立性和物理獨(dú)立性

• 數(shù)據(jù)管理發(fā)展的三個(gè)階段：人工管理 → 文件系統(tǒng) → 數(shù)據(jù)庫(kù)系統(tǒng)

  在數(shù)據(jù)管理技術(shù)發(fā)展過(guò)程中，文件系統(tǒng)與數(shù)據(jù)庫(kù)系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫(kù)系統(tǒng)具有特定的數(shù)據(jù)模型

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

• 數(shù)據(jù)模型：數(shù)據(jù)庫(kù)設(shè)計(jì)的核心

• 數(shù)據(jù)模型的三要素

  數(shù)據(jù)結(jié)構(gòu)：描述數(shù)據(jù)的類(lèi)型、內(nèi)容、性質(zhì)以及數(shù)據(jù)間的聯(lián)系

  數(shù)據(jù)操作：描述在相應(yīng)數(shù)據(jù)結(jié)構(gòu)上的操作類(lèi)型與操作方式

  數(shù)據(jù)約束：描述數(shù)據(jù)結(jié)構(gòu)內(nèi)數(shù)據(jù)間的語(yǔ)法、語(yǔ)義聯(lián)系，它們之間的制約與依存關(guān)系

  用計(jì)算機(jī)表示每一個(gè)實(shí)體時(shí)，由其所有信息項(xiàng)組成一條記錄，相應(yīng)于屬性的數(shù)據(jù)稱為數(shù)據(jù)項(xiàng)

  實(shí)體內(nèi)部的聯(lián)系反映在數(shù)據(jù)上是數(shù)據(jù)項(xiàng)之間的聯(lián)系，實(shí)體間的聯(lián)系反映在數(shù)據(jù)上是記錄間的聯(lián)系
  實(shí)體與屬性有“型“與“值”之分，型是指結(jié)構(gòu)（對(duì)應(yīng)行），值是指結(jié)構(gòu)約束下的具體取值（對(duì)應(yīng)列）

• 數(shù)據(jù)模型按不同的應(yīng)用層次

  • 概念數(shù)據(jù)模型（概念模型）：E-R模型、謂詞模型
  • 邏輯數(shù)據(jù)模型（數(shù)據(jù)模型）：層次模型、網(wǎng)狀模型、關(guān)系模型
  • 物理數(shù)據(jù)模型（物理模型）：面向計(jì)算機(jī)物理結(jié)構(gòu)的模型

  概念數(shù)據(jù)模型——用于對(duì)客觀世界中復(fù)雜事物的結(jié)構(gòu)及它們之間的聯(lián)系進(jìn)行描述，與具體的數(shù)據(jù)庫(kù)管理系統(tǒng)無(wú)關(guān)，與具體的計(jì)算機(jī)平臺(tái)無(wú)關(guān)

  邏輯數(shù)據(jù)模型——面向數(shù)據(jù)庫(kù)系統(tǒng)、考慮數(shù)據(jù)庫(kù)實(shí)現(xiàn)的模型，著重于在數(shù)據(jù)庫(kù)系統(tǒng)一級(jí)的實(shí)現(xiàn)

數(shù)據(jù)模型實(shí)例

• E-R模型：實(shí)體聯(lián)系模型，由實(shí)體、聯(lián)系、屬性組成

  image

  E-R模型圖形符號(hào)：? 實(shí)體、〇 屬性、◇ 聯(lián)系、— 聯(lián)接關(guān)系

  實(shí)體集間的相互關(guān)系：一對(duì)一、一對(duì)多、多對(duì)一、多對(duì)多

• 層次模型：最早發(fā)展起來(lái)的數(shù)據(jù)庫(kù)模型，如樹(shù)

  image

  層次模型的特點(diǎn)：

  • 每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱為根
  • 樹(shù)中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親

• 網(wǎng)狀模型：一個(gè)不加任何條件限制的無(wú)向圖

image

• 關(guān)系模型：以二維表為基本結(jié)構(gòu)所建立的模型，由表框架及表元組構(gòu)成，表框架由n個(gè)命名的屬性組成，n稱為屬性元數(shù)

層次型、網(wǎng)狀型、關(guān)系型數(shù)據(jù)庫(kù)的劃分原則是數(shù)據(jù)之間的聯(lián)系方式

二維表

image

• 二維表的概念：用來(lái)表示實(shí)體間聯(lián)系，每一個(gè)二維表稱為一個(gè)關(guān)系，為了建立一個(gè)關(guān)系，首先要指定關(guān)系的屬性

  • 屬性：二維表中的一列，每個(gè)屬性的取值范圍稱為值域（一個(gè)關(guān)系的屬性名表稱為該關(guān)系的關(guān)系模式，其記法為<關(guān)系名>(<屬性名1>,<屬性名2>,…,<屬性名n>)）

  • 元組：二維表中的一行（各元組的每一個(gè)分量是表示最小單位的基本數(shù)據(jù)項(xiàng)，分量不可再分）

  • 主鍵：也稱關(guān)鍵字、主碼，其值能唯一標(biāo)識(shí)表中一個(gè)元組，主碼屬性不能取空

  • 外鍵：也稱外部關(guān)鍵字，在一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組，表的外鍵是另一表的主鍵，外鍵可重復(fù)、可空值

    例：在關(guān)系A(chǔ)(S，SN，D)和B(D，CN，NM)中，A的主鍵是S，B的主鍵是D，則D是A的外鍵

• 關(guān)系中的數(shù)據(jù)約束

  • 實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，為主鍵是唯一決定元組的，若屬性為空值則其唯一性就無(wú)意義了，即一個(gè)關(guān)系中應(yīng)有一個(gè)或多個(gè)候選關(guān)鍵字
  • 參照完整性約束：這是關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，即在關(guān)系中的外鍵要么是所關(guān)聯(lián)關(guān)系中實(shí)際存在的元組，要么為空值
  • 用戶定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語(yǔ)義要求，例如某個(gè)屬性的取值范圍在0-100之間

• 關(guān)系的特點(diǎn)

  1. 關(guān)系必須規(guī)范化
  2. 在同一個(gè)關(guān)系中不能出現(xiàn)相同的屬性名
  3. 關(guān)系中不能有相同的元組
  4. 在一個(gè)關(guān)系中元組的次序無(wú)關(guān)緊要，任意交換兩行位置并不影響數(shù)據(jù)的實(shí)際含義
  5. 在一個(gè)關(guān)系中屬性的次序無(wú)關(guān)緊要，任意交換兩列位置也不影響數(shù)據(jù)的實(shí)際含義

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

• 關(guān)系模型的基本操縱：增加、刪除、修改、查詢

  • 并 R∪S：將兩個(gè)以上表的行并到一起，去除相同的行
  • 差 R-S：在關(guān)系R中減去關(guān)系S共有的行，保留的是S中沒(méi)有的行，運(yùn)算時(shí)依次將兩個(gè)表的一行一行相減
  • 笛卡兒積 R×S：行與列重新組合
  • 投影 π：從所有字段中選取一部分字段及其值進(jìn)行縱向操作（選列）
  • 選擇 σ：從二維表的全部記錄中把那些符合指定條件的記錄挑出來(lái)（選行）
  • 連接 R?S(A?B)：將兩個(gè)關(guān)系模式拼接成一個(gè)更寬的關(guān)系模式，在新的關(guān)系上做選擇操作，生成的新關(guān)系中包含滿足聯(lián)接條件的元組
  • 交 R∩S：求兩個(gè)以上表的公共行，前提是參與運(yùn)算的表的結(jié)構(gòu)相同
  • 除 T=R÷S（笛卡兒反運(yùn)算）：行與列重新拆分，剩下的合并相同行
  • 自然連接 R?S：一種特殊的等值鏈接，把對(duì)應(yīng)字段取值相等的元組連接成一個(gè)新的表，剩下的去掉屬性重復(fù)的列，要求R和S含有一個(gè)或多個(gè)共有的屬性

  image

  image

  說(shuō)明：

  笛卡爾積——若R有m個(gè)元組，S有n個(gè)元組，則R×S有m×n個(gè)元組

  投影——C和A為屬性名，說(shuō)明要選擇的列

  選擇——B>'4'是選擇語(yǔ)句的條件，對(duì)關(guān)系做水平分割，選擇符合條件的元組

  image

  image

  image

  image

  image

  交運(yùn)算能不改變關(guān)系表中的屬性個(gè)數(shù)但能減少元組個(gè)數(shù)

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

• 數(shù)據(jù)庫(kù)設(shè)計(jì)：設(shè)計(jì)一個(gè)能滿足用戶要求，性能良好的數(shù)據(jù)庫(kù)，它是數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)中的核心問(wèn)題

  • 基本任務(wù)：根據(jù)用戶對(duì)象的信息需求、處理需求和數(shù)據(jù)庫(kù)的支持環(huán)境設(shè)計(jì)出數(shù)據(jù)模式
  • 兩種方法
    • 面向數(shù)據(jù)的方法：以信息需求為主，兼顧處理需求（主流）
    • 面向過(guò)程的方法：以處理需求為主，兼顧信息需求

• 數(shù)據(jù)庫(kù)設(shè)計(jì)的步驟：（一般采用生命周期法）

  1. 需求分析階段——包括信息/處理/安全性/完整性的需求，建立數(shù)據(jù)字典
  2. 概念設(shè)計(jì)階段——分析數(shù)據(jù)間內(nèi)在語(yǔ)義的關(guān)聯(lián)建立抽象模型，用E-R圖來(lái)描述信息結(jié)構(gòu)但不涉及信息在計(jì)算機(jī)中的表示
  3. 邏輯設(shè)計(jì)階段——把E-R圖轉(zhuǎn)換為關(guān)系模式（實(shí)體與聯(lián)系表示成關(guān)系，屬性轉(zhuǎn)換成關(guān)系中的屬性）
  4. 物理設(shè)計(jì)階段——對(duì)數(shù)據(jù)庫(kù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提數(shù)據(jù)庫(kù)訪問(wèn)速度及有效利用存儲(chǔ)空間，包括優(yōu)化數(shù)據(jù)庫(kù)系統(tǒng)查詢性能的索引設(shè)計(jì)、集簇設(shè)計(jì)和分區(qū)設(shè)計(jì)
  5. 編碼階段
  6. 測(cè)試階段
  7. 運(yùn)行階段
  8. 進(jìn)一步修改階段

  在數(shù)據(jù)庫(kù)設(shè)計(jì)中最多采用前四個(gè)階段，并且重點(diǎn)以數(shù)據(jù)結(jié)構(gòu)與模型的設(shè)計(jì)為主線

• 數(shù)據(jù)庫(kù)管理

  • 數(shù)據(jù)庫(kù)的建立
  • 數(shù)據(jù)庫(kù)的調(diào)整
  • 數(shù)據(jù)庫(kù)的重組
  • 數(shù)據(jù)庫(kù)安全性控制與完整性控制
  • 數(shù)據(jù)庫(kù)的故障恢復(fù)
  • 數(shù)據(jù)庫(kù)監(jiān)控