當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

二级公共基础知识总结笔记

發(fā)布時(shí)間：2023/12/18 编程问答 31 豆豆

生活随笔收集整理的這篇文章主要介紹了二级公共基础知识总结笔记小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

文章目錄

二級(jí)公共基礎(chǔ)知識(shí)總結(jié)
- 第一部分數(shù)據(jù)結(jié)構(gòu)和算法
- - 1.1 算法
  - 1.2 數(shù)據(jù)結(jié)構(gòu)
  - 1.3 線性表
  - 1.4 棧和隊(duì)列
  - - 1.4.1 棧
    - 1.4.2 隊(duì)列
  - 1.5 線性鏈表(線性表的鏈?zhǔn)酱鎯?chǔ))
  - - 1.5.1 線性鏈表的概念及基本運(yùn)算
    - 1.5.2 循環(huán)鏈表
  - 1.6 樹(shù)與二叉樹(shù)
  - - 1.6.1 樹(shù)的基本概念
    - 1.6.2 二叉樹(shù)及其性質(zhì)
    - 1.6.3 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)及其遍歷
  - 1.7 查找技術(shù)
  - 1.8 排序技術(shù)
- 第二部分程序設(shè)計(jì)基礎(chǔ)
- - 2.1 程序設(shè)計(jì)方法與風(fēng)格
  - 2.2 結(jié)構(gòu)化程序設(shè)計(jì)
  - 2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)
- 第三部分軟件工程基礎(chǔ)
- - 3.1 軟件工程基本概念
  - - 3.1.1 軟件
    - 3.1.2 軟件工程
  - 3.2 結(jié)構(gòu)化分析方法
  - - 3.2.1 需求分析
    - 3.2.2 需求分析方法
    - 3.2.3 結(jié)構(gòu)化分析方法的常用工具
    - 3.2.4 軟件需求規(guī)格說(shuō)明書
  - 3.3 結(jié)構(gòu)化設(shè)計(jì)方法
  - - 3.3.1 軟件設(shè)計(jì)概述
    - 3.3.2 概要設(shè)計(jì)(總體設(shè)計(jì))
    - 3.3.3 詳細(xì)設(shè)計(jì)
  - 3.4 軟件測(cè)試
  - 3.5 程序調(diào)試
- 第四部分數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)
- - 4.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念
  - - 4.2 數(shù)據(jù)模型
  - 4.3 關(guān)系代數(shù)
  - 4.4 數(shù)據(jù)庫(kù)設(shè)計(jì)與管理

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

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

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

1.1 算法

定義：對(duì)解決方案的操作步驟的準(zhǔn)確而完整的描述。(是數(shù)學(xué)計(jì)算方法和程序間的一個(gè)過(guò)渡)
基本特征：可行性(可以在實(shí)際計(jì)算工具上執(zhí)行)；確定性(算法每一步的表述沒(méi)有歧義)；有窮性(操作步驟有限，在有限時(shí)間內(nèi)完成)；有足夠的輸入。
總之，算法是指一組嚴(yán)謹(jǐn)?shù)囟x操作步驟的可以在有限的次數(shù)中終止的規(guī)則，每一個(gè)規(guī)則都是可行的、明確的。
基本要素：
(1). 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作(由不同計(jì)算機(jī)系統(tǒng)的指令集規(guī)定其基本運(yùn)算和操作)；
(2). 控制結(jié)構(gòu)(就是順序、選擇、循環(huán)三種)；
算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推法、遞歸法、減半遞推法、回溯法
算法復(fù)雜度：體現(xiàn)在運(yùn)行該算法所需的計(jì)算機(jī)的時(shí)間和空間資源上，越多則算法復(fù)雜度越高。
(1). 時(shí)間復(fù)雜度：執(zhí)行算法所需的計(jì)算工作量，用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量(注意: 不是具體的執(zhí)行時(shí)間)。常用大O表示法表示。我們經(jīng)常用平均復(fù)雜度和最壞情況復(fù)雜度來(lái)分析算法的工作量。
(2). 空間復(fù)雜度：執(zhí)行這個(gè)算法所需的內(nèi)存空間。包括3個(gè)部分。為降低空間復(fù)雜度，主要應(yīng)減少輸入數(shù)據(jù)所占的空間和額外空間。如果額外空間不隨問(wèn)題規(guī)模變化，稱該算法in place原地工作。
a. 輸入數(shù)據(jù)所占的存儲(chǔ)空間b. 程序本身所占的存儲(chǔ)空間c. 算法執(zhí)行過(guò)程中所需要的額外空間，包括算法執(zhí)行過(guò)程中的工作單元和某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間

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ù)集合中各個(gè)數(shù)據(jù)元素之間存在的某種關(guān)系。
結(jié)構(gòu)又可以分為邏輯結(jié)構(gòu)——數(shù)據(jù)集合中各數(shù)據(jù)元素之間固有的邏輯關(guān)系；存儲(chǔ)結(jié)構(gòu)——各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系。此外，數(shù)據(jù)結(jié)構(gòu)還研究對(duì)各種數(shù)據(jù)結(jié)構(gòu)的運(yùn)算。
所以，數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)+邏輯結(jié)構(gòu)+存儲(chǔ)結(jié)構(gòu)+運(yùn)算。
數(shù)據(jù)元素間的結(jié)構(gòu)根據(jù)不同的特性，分為線性結(jié)構(gòu)、樹(shù)形結(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é)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的圖形表示中引出的概念，根節(jié)點(diǎn)——沒(méi)有前驅(qū)的節(jié)點(diǎn)，葉子節(jié)點(diǎn)——沒(méi)有后繼的節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)——除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之外的節(jié)點(diǎn)的統(tǒng)稱。
存儲(chǔ)結(jié)構(gòu)：包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
邏輯結(jié)構(gòu)：包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)。如果數(shù)據(jù)結(jié)構(gòu)沒(méi)有數(shù)據(jù)元素，稱其為空的數(shù)據(jù)結(jié)構(gòu)。

基本概念含義例子

線性結(jié)構(gòu)	一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)，滿足一下兩個(gè)條件：有且只有一個(gè)根節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)最多只有一個(gè)前驅(qū)，也最多只有一個(gè)后繼	(早餐，午餐), (午餐，晚餐）
非線性結(jié)構(gòu)	不滿足以上兩個(gè)條件的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)，主要是指樹(shù)和圖形結(jié)構(gòu)

1.3 線性表

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

1.4 棧和隊(duì)列

1.4.1 棧

定義：特殊的線性表，所有的插入和刪除操作限定在表的同一端(棧頂top)進(jìn)行，另一端(棧底bottom)是封閉的，既不允許插入元素，也不運(yùn)行刪除元素。棧中沒(méi)有元素時(shí)稱為空棧。
設(shè)有棧S=(a1, a2, a3, a4)，則a1為棧底元素，a4為棧底元素。按照a1,a2,a3,a4的順序入棧，a4,a3,a2,a1的順序出棧。
特點(diǎn)：Last In First Out，后進(jìn)先出。即棧頂元素總是最后被插入的元素，也是最早被刪除的元素，棧底元素總是最早被插入的元素，也是最晚被刪除的元素。在順序存儲(chǔ)結(jié)構(gòu)中，棧的插入和刪除不需要移動(dòng)表中的其他元素。
棧的運(yùn)算之入棧：在棧頂插入一個(gè)新元素。
棧的運(yùn)算之出棧：取出棧頂元素并賦予指定變量。
棧底運(yùn)算之讀取棧頂元素：讀取棧頂指針?biāo)赶虻脑夭①x予指定變量。

1.4.2 隊(duì)列

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

1.5 線性鏈表(線性表的鏈?zhǔn)酱鎯?chǔ))

1.5.1 線性鏈表的概念及基本運(yùn)算

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

類型優(yōu)點(diǎn)缺點(diǎn)

順序表	(1) 可以隨機(jī)存取表中的任意節(jié)點(diǎn)；(2) 無(wú)需為表示節(jié)點(diǎn)間的邏輯關(guān)系額外增加存儲(chǔ)空間	(1) 其插入和刪除運(yùn)算效率很低；(2) 存儲(chǔ)空間不便于擴(kuò)充，不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配
鏈表	(1) 插入和刪除效率高，只需改變指針即可，不用移動(dòng)元素；(2) 存儲(chǔ)空間易于擴(kuò)充且方便空間的動(dòng)態(tài)分配	(1)需要額外的空間來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系；(2) 數(shù)據(jù)的查詢效率較低

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

1.5.2 循環(huán)鏈表

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

1.6 樹(shù)與二叉樹(shù)

1.6.1 樹(shù)的基本概念

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

相關(guān)術(shù)語(yǔ)含義

父節(jié)點(diǎn)和根節(jié)點(diǎn)	樹(shù)結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)只有一個(gè)直接前驅(qū)，稱為父節(jié)點(diǎn)；沒(méi)有直接前驅(qū)的節(jié)點(diǎn)只有一個(gè)，即樹(shù)的根節(jié)點(diǎn)(樹(shù)的根)
子節(jié)點(diǎn)和葉子節(jié)點(diǎn)	在樹(shù)結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)可以有0、1或多個(gè)直接后繼，稱作該節(jié)點(diǎn)的子節(jié)點(diǎn)。沒(méi)有后繼的節(jié)點(diǎn)是葉子節(jié)點(diǎn)
度	一個(gè)節(jié)點(diǎn)擁有的后件(直接后繼)個(gè)數(shù)就是該節(jié)點(diǎn)的度。所有節(jié)點(diǎn)中最大的度是樹(shù)的度
深度	根節(jié)點(diǎn)所在的層次為1，其他節(jié)點(diǎn)所在的層次等于父節(jié)點(diǎn)的層次+1，樹(shù)的最大層次稱為該樹(shù)的深度。
子樹(shù)	在樹(shù)中，以某節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該節(jié)點(diǎn)的一棵子樹(shù)。

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

二叉樹(shù)(Binary Tree)定義：是一個(gè)有限的節(jié)點(diǎn)集合，該集合或?yàn)榭?#xff0c;或由一個(gè)根節(jié)點(diǎn)及其左右不相交的左、右二叉子樹(shù)所構(gòu)成。與樹(shù)是相似的，但又有不同。二叉樹(shù)不是樹(shù)的特殊情況，二者是不同的概念。
二叉樹(shù)的特點(diǎn)：
(1). 二叉樹(shù)可以為空，空的二叉樹(shù)沒(méi)有節(jié)點(diǎn)，非空二叉樹(shù)只有一個(gè)根節(jié)點(diǎn)；
(2). 每個(gè)節(jié)點(diǎn)最多只有兩棵子樹(shù)，即二叉樹(shù)中不存在度大于2的節(jié)點(diǎn)，二叉樹(shù)中的節(jié)點(diǎn)可能沒(méi)有子節(jié)點(diǎn)，可能只有一個(gè)左子節(jié)點(diǎn)或只有一個(gè)右子節(jié)點(diǎn)；
(3). 二叉樹(shù)的子樹(shù)有左右之分，不能任意顛倒次序。
二叉樹(shù)的基本形態(tài)：5種；空，僅有根節(jié)點(diǎn)，左右子樹(shù)均非空，左子樹(shù)非空右子樹(shù)為空，左子樹(shù)為空右子樹(shù)非空。
滿二叉樹(shù)：除最后一層，每一層上的所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)的二叉樹(shù)，一棵平衡的二叉樹(shù)。
(1). 其在第i層有2^(i-1)個(gè)節(jié)點(diǎn)，相當(dāng)于每一層的節(jié)點(diǎn)數(shù)都滿了；
(2). 一棵深度為K的滿二叉樹(shù)共有2^k-1個(gè)節(jié)點(diǎn);
(3). 滿二叉樹(shù)中只有度為2和0的節(jié)點(diǎn)，沒(méi)有度為1的節(jié)點(diǎn)。所有度為0的葉子節(jié)點(diǎn)都在最后同一層。
完全二叉樹(shù)：除最后一層，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大，在最后一層上只缺少右邊的若干節(jié)點(diǎn)。
(1). 葉子節(jié)點(diǎn)只在最后兩層出現(xiàn)；
(2). 對(duì)于任一節(jié)點(diǎn)，若其右子樹(shù)的深度為m，則左子樹(shù)的深度為m或m+1。
二叉樹(shù)的基本性質(zhì)：
(1). 二叉樹(shù)的第K層上面，最多只有2^k-1個(gè)節(jié)點(diǎn)；
(2). 深度為K的二叉樹(shù)，最多有2^k-1個(gè)節(jié)點(diǎn)(等比數(shù)列求和)；
(3). 對(duì)任何一棵二叉樹(shù)，度為0的節(jié)點(diǎn)(葉子節(jié)點(diǎn))總是比度為2的節(jié)點(diǎn)多一個(gè)；
(4). 具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log₂n]+1；
(5). 具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其深度為[log₂n]+1。
(6). 較復(fù)雜。

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

二叉鏈表：二叉樹(shù)常采用鏈?zhǔn)浇Y(jié)構(gòu)。由于每個(gè)元素可以有兩個(gè)后件，因此每個(gè)節(jié)點(diǎn)有兩個(gè)指針：左指針域執(zhí)行左子節(jié)點(diǎn)，右指針域執(zhí)行右子節(jié)點(diǎn)。因此，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表(非線性結(jié)構(gòu)，不同于雙向鏈表)。
二叉樹(shù)的遍歷：不重復(fù)的訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)。一般先訪問(wèn)左子樹(shù)，在訪問(wèn)右子樹(shù)，在先左后右的原則下，根據(jù)訪問(wèn)根節(jié)點(diǎn)的次序不同，二叉樹(shù)的遍歷分為前序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)三種。
(1). 前序遍歷：先訪問(wèn)根節(jié)點(diǎn)——> 前序遍歷左子樹(shù)——> 前序遍歷右子樹(shù)(DLR)
(2). 中序遍歷：先中序遍歷左子樹(shù)——> 訪問(wèn)根節(jié)點(diǎn)——> 中序遍歷右子樹(shù)(LDR)
(3). 后序遍歷：先后序遍歷左子樹(shù)——> 后序遍歷右子樹(shù)——> 訪問(wèn)根節(jié)點(diǎn) (LRD)
已知中序遍歷序列和前序遍歷序列(或后序遍歷序列)可以唯一確認(rèn)一棵二叉樹(shù)，但是知道前序和后序則無(wú)法唯一確定這棵二叉樹(shù)。

1.7 查找技術(shù)

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

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

1.8 排序技術(shù)

排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。

交換類排序法(借助數(shù)據(jù)元素的交換來(lái)排序的方法)：冒泡排序: 最壞的情況下，對(duì)長(zhǎng)度為n的線性表排列需要比較n(n-1)/2次?？焖倥判騽t是對(duì)冒泡排序的一種本質(zhì)改進(jìn)，其平均時(shí)間最佳O(nlog₂n) ，最壞O(n²)。如初始序列基本有序，則蛻化為冒泡排序。
插入類排序法(每次將一個(gè)待排序元素按其大小插入到前面的有序子表中)：簡(jiǎn)單插入排序：持續(xù)不斷的清空無(wú)序表，插入有序表中，其效率與冒泡排序法基本相同。希爾排序法則有較大改進(jìn)。
選擇類排序法(每趟從待排序的序列中選擇最小的元素，順序放在有序子表中的后面，直到全部序列滿足排序要求為止)：簡(jiǎn)單選擇排序，最壞的情況下要比較n(n-1)/2次。對(duì)于大量數(shù)據(jù)元素，堆排序則是很有效的。
排序方法比較：
方法平均時(shí)間最壞情況時(shí)間輔助存儲(chǔ)
冒泡排序 O(n²) O(n²) O(1)
快速排序 O(nlog₂n) O(n²) O(log₂n)
簡(jiǎn)單插入排序 O(n²) O(n²) O(1)
簡(jiǎn)單選擇排序 O(n²) O(n²) O(1)
堆排序 O(nlog₂n) O(nlog₂n) O(1)

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

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

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

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

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

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

基本概念：

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

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

3.1 軟件工程基本概念

3.1.1 軟件

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

3.1.2 軟件工程

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

原則具體描述

抽象	分層次抽象，自頂向下、逐層細(xì)分控制軟件開(kāi)發(fā)的復(fù)雜性
信息隱蔽	模塊設(shè)計(jì)成黑箱，不讓模塊使用者直接訪問(wèn)
模塊化	模塊化有助于信息隱蔽和抽象，有助于表示復(fù)雜的系統(tǒng)
局部化	模塊間松耦合，模塊內(nèi)部強(qiáng)內(nèi)聚，有助于控制分解的復(fù)雜性
確定性	軟件開(kāi)發(fā)過(guò)程中所有概念的表述是無(wú)歧義的、確定的、規(guī)范的
一致性	各個(gè)模塊使用一致的概念、符號(hào)；程序內(nèi)外部接口一致；系統(tǒng)規(guī)格說(shuō)明書和系統(tǒng)行為一致
完備性	軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所要求的功能
可驗(yàn)證性	開(kāi)發(fā)大型的軟件系統(tǒng)需要對(duì)系統(tǒng)自頂向下、逐層分解，遵循系統(tǒng)易于檢查、測(cè)試、評(píng)審的原則

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

活動(dòng)名稱含義

軟件規(guī)格說(shuō)明	規(guī)定軟件的功能及其運(yùn)行時(shí)的限制
軟件開(kāi)發(fā)	產(chǎn)生滿足規(guī)格說(shuō)明的軟件
軟件確認(rèn)	確認(rèn)能夠滿足用戶提出的要求
軟件演進(jìn)	為滿足用戶要求的變更，軟件必須在使用的過(guò)程中不斷演進(jìn)

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

大時(shí)期小階段主要任務(wù)成果與文檔

軟件定義期	問(wèn)題定義	確定要解決的問(wèn)題是什么
	可行性研究與計(jì)劃制定	決定該問(wèn)題是否存在解決方法可行，指定完成任務(wù)的實(shí)施計(jì)劃	可行性分析報(bào)告
	需求分析	對(duì)于開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義	軟件規(guī)格說(shuō)明書、初步的用戶手冊(cè)
軟件開(kāi)發(fā)期	軟件設(shè)計(jì)	分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)，給出軟件的結(jié)構(gòu)、模塊劃分及設(shè)計(jì)流程	概要和詳細(xì)設(shè)計(jì)說(shuō)明書、測(cè)試計(jì)劃初稿
	軟件實(shí)現(xiàn)	在軟件設(shè)計(jì)的基礎(chǔ)上編寫程序	用戶手冊(cè)、操作手冊(cè)和單元測(cè)試計(jì)劃
	軟件測(cè)試	在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分	測(cè)試分析報(bào)告
運(yùn)行維護(hù)期	運(yùn)行和維護(hù)	將已交付的軟件投入運(yùn)行，同時(shí)不斷地維護(hù)，進(jìn)行必要而且可行的擴(kuò)充和刪改

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

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

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

3.2.1 需求分析

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

3.2.2 需求分析方法

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

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

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

名稱圖形說(shuō)明

數(shù)據(jù)流	有向箭頭	沿箭頭方向傳輸數(shù)據(jù)，在旁邊標(biāo)注數(shù)據(jù)流名
加工過(guò)程	圓形	轉(zhuǎn)換，輸入數(shù)據(jù)經(jīng)過(guò)加工、交換產(chǎn)生輸出
數(shù)據(jù)存儲(chǔ)文件	類長(zhǎng)方形	表示存儲(chǔ)過(guò)程中存放各種數(shù)據(jù)的文件
源/潭	長(zhǎng)方形	表示系統(tǒng)與環(huán)境的接口，屬于系統(tǒng)之外的實(shí)體

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

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

這是需求分析階段的最后成果，是軟件開(kāi)發(fā)過(guò)程中的重要文檔之一，衡量它的標(biāo)準(zhǔn)如下：

標(biāo)準(zhǔn)內(nèi)涵

正確性	首先正確體現(xiàn)系統(tǒng)的真實(shí)需求
無(wú)歧義性	對(duì)每一個(gè)需求沒(méi)有兩種解釋
完整性	涵蓋用戶對(duì)系統(tǒng)的所有需求，包括功能需求、性能需求、接口需求、設(shè)計(jì)約束等
可驗(yàn)證性	每一個(gè)需求都可在有限代價(jià)的有效過(guò)程中驗(yàn)證確認(rèn)
一致性	各個(gè)需求的描述之間不能有邏輯上的沖突
可理解性	應(yīng)盡量少使用計(jì)算機(jī)的概念和術(shù)語(yǔ)
可修改性	結(jié)構(gòu)風(fēng)格在需要的時(shí)候不難改變
可追蹤性	每個(gè)需求的來(lái)源和流向是清晰的

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

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

3.3.1 軟件設(shè)計(jì)概述

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

劃分名稱含義

按工程管理角度劃分	概要設(shè)計(jì)	將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)及接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式
	詳細(xì)設(shè)計(jì)	確認(rèn)每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。
按技術(shù)觀點(diǎn)劃分	結(jié)構(gòu)設(shè)計(jì)	定義軟件系統(tǒng)各主要部件之間的關(guān)系
	數(shù)據(jù)設(shè)計(jì)	將分析時(shí)創(chuàng)建的模型轉(zhuǎn)換成數(shù)據(jù)結(jié)構(gòu)的定義
	接口設(shè)計(jì)	描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信
	過(guò)程設(shè)計(jì)	把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述

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

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

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

概念含義圖符

模塊	一個(gè)矩形代表一個(gè)模塊	矩形
調(diào)用關(guān)系	矩形之間的調(diào)用關(guān)系用矩形之間的箭頭表明	箭頭或直線
信息	用帶注釋的箭頭表名模塊調(diào)用過(guò)程中來(lái)回傳遞的信息	數(shù)據(jù)信息是帶空心圓的箭頭，控制信息則是帶實(shí)心箭頭
協(xié)調(diào)模塊	對(duì)所有下屬模塊進(jìn)行協(xié)調(diào)和管理
傳入模塊	從下級(jí)模塊取得數(shù)據(jù)，經(jīng)處理傳到上級(jí)模塊
變換模塊	從上級(jí)模塊取得數(shù)據(jù)，經(jīng)過(guò)特定的處理轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊
傳出模塊	從上級(jí)模塊取得數(shù)據(jù)，經(jīng)處理傳給下級(jí)模塊
上級(jí)模塊	控制其他模塊的模塊
從屬模塊	被另一個(gè)模塊調(diào)用的模塊
原子模塊	樹(shù)中位于葉子節(jié)點(diǎn)的模塊，沒(méi)有從屬節(jié)點(diǎn)的模塊
深度	表示控制的層數(shù)
寬度	最大模塊數(shù)的層的控制寬度
扇入	調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)
扇出	由一個(gè)模塊直接調(diào)用的其他模塊個(gè)數(shù)

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

3.3.3 詳細(xì)設(shè)計(jì)

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

3.4 軟件測(cè)試

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

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

3.5 程序調(diào)試

在對(duì)軟件進(jìn)行成功的測(cè)試之后進(jìn)行程序的調(diào)試，診斷和改正程序中的錯(cuò)誤。

程序調(diào)試基本概念：測(cè)試發(fā)現(xiàn)錯(cuò)誤，調(diào)試是在成功測(cè)試(發(fā)現(xiàn)了錯(cuò)誤的測(cè)試)之后排除錯(cuò)誤的過(guò)程。軟件測(cè)試貫穿整個(gè)軟件生命期，調(diào)試主要在開(kāi)發(fā)階段。
程序調(diào)試的基本步驟：
(1). 錯(cuò)誤定位；(2). 修改設(shè)計(jì)和代碼，排除錯(cuò)誤；(3). 進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤。
程序調(diào)試的原則：
(1). 錯(cuò)誤定性和定位的原則：集中思考分析與錯(cuò)誤現(xiàn)象有關(guān)的信息；不鉆死胡同；不要過(guò)分依賴調(diào)試工具；避免用試探法；
(2). 修改錯(cuò)誤的原則：錯(cuò)誤可能群集；要修改錯(cuò)誤本身；必須進(jìn)行回歸測(cè)試；修改源代碼程序，不要改變目標(biāo)代碼。
軟件調(diào)試方法：從是否追蹤和執(zhí)行程序的角度，分為靜態(tài)(主要調(diào)試手段)和動(dòng)態(tài)調(diào)試(通過(guò)人的思維分析代碼調(diào)錯(cuò)，輔助手段)。
(1). 強(qiáng)行排錯(cuò)法：傳統(tǒng)方法，很低效；設(shè)置斷點(diǎn)，程序暫停，觀察程序狀態(tài)和繼續(xù)運(yùn)行程序。
(2). 回溯法：相當(dāng)常用，適合小程序；大程序回溯可能性很低。
(3). 原因排除法：二分法，歸納法，演繹法。都可以使用調(diào)試工具來(lái)輔助完成，但是工具不能完全替代。

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

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

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

背景人工管理階段文件管理階段數(shù)據(jù)庫(kù)系統(tǒng)管理階段

應(yīng)用背景	科學(xué)技算	科學(xué)計(jì)算、管理	大規(guī)模管理
硬件背景	無(wú)直接存取設(shè)備	磁盤、磁鼓	大容量磁盤
軟件背景	無(wú)操作系統(tǒng)	有文件系統(tǒng)	數(shù)據(jù)庫(kù)管理系統(tǒng)
處理方式	批處理	聯(lián)機(jī)實(shí)時(shí)處理、批處理	分布處理、聯(lián)機(jī)實(shí)時(shí)處理和批處理
特點(diǎn)
數(shù)據(jù)管理者	人	文件系統(tǒng)	數(shù)據(jù)庫(kù)管理系統(tǒng)
數(shù)據(jù)面向的對(duì)象	某個(gè)應(yīng)用程序	某個(gè)應(yīng)用程序	現(xiàn)實(shí)世界
數(shù)據(jù)共享程度	無(wú)共享，冗余度大	共享性差，冗余度高	共享性大，冗余度小
數(shù)據(jù)獨(dú)立性	不獨(dú)立，完全依賴于程序	獨(dú)立性差	具有高度的物理獨(dú)立性和邏輯獨(dú)立性
數(shù)據(jù)結(jié)構(gòu)化	無(wú)結(jié)構(gòu)	記錄內(nèi)部有結(jié)構(gòu)，整體無(wú)結(jié)構(gòu)	整體結(jié)構(gòu)化，用數(shù)據(jù)模型描述
數(shù)據(jù)控制能力	由應(yīng)用程序控制	由應(yīng)用程序控制	由DBMS提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)

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

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

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

數(shù)據(jù)模型三要素：
(1). 數(shù)據(jù)結(jié)構(gòu)：對(duì)系統(tǒng)靜態(tài)特征的描述，是數(shù)據(jù)模型的核心。
(2). 數(shù)據(jù)操作：對(duì)系統(tǒng)動(dòng)態(tài)特征的描述，是允許的操作的集合。
(3). 數(shù)據(jù)約束：特定的語(yǔ)義約束條件，保證數(shù)據(jù)的正確、有效、相容。
數(shù)據(jù)模型的類型(按不同的應(yīng)用層次分成三種)：
(1). 概念數(shù)據(jù)模型(概念模型)：一種面向客觀世界、面向用戶的模型，與具體的平臺(tái)和系統(tǒng)無(wú)關(guān)。
(2). 邏輯數(shù)據(jù)模型(數(shù)據(jù)模型)：面向數(shù)據(jù)庫(kù)系統(tǒng)的模型，著重與數(shù)據(jù)庫(kù)系統(tǒng)一級(jí)的實(shí)現(xiàn)。
(3). 物理數(shù)據(jù)模型(物理模型)：面向計(jì)算機(jī)物理實(shí)現(xiàn)的模型。
E-R模型：實(shí)體聯(lián)系模型。有1:1、1:n、n:m三種聯(lián)系。可以直觀的用E-R圖表示。屬于概念模型。
層次模型：用樹(shù)形結(jié)構(gòu)表示實(shí)體及其聯(lián)系，節(jié)點(diǎn)是實(shí)體，樹(shù)枝是聯(lián)系，從上到下是一對(duì)多的聯(lián)系，有且只有一個(gè)根節(jié)點(diǎn)。
網(wǎng)狀模型：用網(wǎng)狀結(jié)構(gòu)表示實(shí)體及其聯(lián)系，是層次模型的擴(kuò)展，允許一個(gè)或多個(gè)節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可以有多于一個(gè)的父節(jié)點(diǎn)。
關(guān)系模型：用二維表來(lái)表示關(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ù)的基本運(yùn)算：
(1). 投影運(yùn)算：從關(guān)系模式中指定若干屬性組成新的關(guān)系。是對(duì)列屬性的去重復(fù)。
(2). 選擇運(yùn)算：從關(guān)系模式中找出滿足指定條件的數(shù)據(jù)項(xiàng)的操作稱為選擇。
(3). 笛卡爾積：設(shè)有n元關(guān)系R和m元關(guān)系S，它們分別有p和q個(gè)記錄，則笛卡爾積為RxS，是一個(gè)m+n元關(guān)系，記錄有pxq個(gè)。
關(guān)系代數(shù)的擴(kuò)充運(yùn)算：
(1). 交。集合運(yùn)算之一，是兩個(gè)關(guān)系的交集。
(2). 連接和自然連接。連接是從兩個(gè)關(guān)系的笛卡爾積中選擇滿足給定屬性間的一定條件的那些元組。其中的一個(gè)特例是自然連接，要求兩個(gè)關(guān)系中進(jìn)行比較的是相同的屬性，并且進(jìn)行等值連接，還有去掉重復(fù)的屬性列。
(3). 除。近似于笛卡爾積的逆運(yùn)算。
(4). 并。集合運(yùn)算之一，是兩個(gè)關(guān)系的并集。
關(guān)系代數(shù)的應(yīng)用實(shí)例：關(guān)系代數(shù)雖然形式簡(jiǎn)單，但它足以滿足對(duì)表的查詢、插入、刪除和修改操作。

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

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

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

總結(jié)

以上是生活随笔為你收集整理的二级公共基础知识总结笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。