計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)筆記

計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)筆記

?算法

?解決方案的準(zhǔn)確而完整的描述

算法不等于程序

?可行性

?字面意思，即算法可行

?確定性

?每個(gè)步驟需要明確定義，不能出現(xiàn)模棱兩可，可A可B。指該步驟每次執(zhí)行都是相同的。

?有窮性

?必須在有限的時(shí)間內(nèi)做完

?執(zhí)行有限個(gè)步驟后終止

?足夠的情報(bào)

?算法要有一定的輸入數(shù)據(jù)和必要的輸出數(shù)據(jù)

?eg.出錯(cuò)時(shí)的處理和調(diào)試

?算法的基本要素

?對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作

?算木運(yùn)算

?邏輯運(yùn)算

?關(guān)系運(yùn)算

?數(shù)揶專(zhuān)輸

?算法的控制結(jié)構(gòu)

?算法中各操作之間的執(zhí)行順序

?通常描述算法的工具

?傳統(tǒng)流程圖

?N-S結(jié)構(gòu)化流程圖

?算法描述語(yǔ)言

?算法的基本結(jié)構(gòu)

?順序

?選擇（分支）

?循環(huán)（重復(fù)）

?算法的時(shí)間復(fù)雜度

?執(zhí)行算法所需要的計(jì)算工作量

?可以用算法所執(zhí)行的基本運(yùn)算次數(shù)度量

?不是指算法所需時(shí)間，而是指算法所需的計(jì)算工作量

?算法的空間復(fù)雜度

?執(zhí)行算法所需要的內(nèi)存空間

?包括

?算法程序

?輸入的初始數(shù)據(jù)

?算法執(zhí)行過(guò)程中所需要的額外空間

?算法的時(shí)間復(fù)雜度和空間復(fù)雜度相互獨(dú)立

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

?數(shù)據(jù)

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

?這些數(shù)據(jù)元素具有某個(gè)共同的特征

?數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體

?有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)（dataitem）組成

?數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位

?結(jié)構(gòu)

?集合中各個(gè)數(shù)據(jù)元素之間存在的某種關(guān)系（或聯(lián)系）

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

?相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合

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

?邏輯結(jié)構(gòu)

?反映數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系）的數(shù)據(jù)結(jié)構(gòu)

?有且只有一個(gè)根結(jié)點(diǎn)，它無(wú)前件

?每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件

?線性結(jié)構(gòu)

?線性表

線性表

?線性表順序存儲(chǔ)結(jié)構(gòu)

9線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十日小04?巨［.Z：

head

雙向鏈表q”|Z30dlz3^■囚

head

3日2巨［?曰■二＞■?

V循環(huán)鏈表

f

head

?n(n>0)個(gè)數(shù)據(jù)元素構(gòu)成的有限序列，表中除第一個(gè)元素外的每一個(gè)元素，有且

只有一個(gè)

?線性表的存儲(chǔ)結(jié)構(gòu)

?可以采用順序也可以鏈?zhǔn)?，但大多選順序存儲(chǔ)結(jié)構(gòu)

?線性表的順序存儲(chǔ)結(jié)構(gòu)又叫做順序表

?特點(diǎn)

?線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的

?線性表中數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的

?可以隨機(jī)訪問(wèn)數(shù)據(jù)元素

?做插入、刪除時(shí)需移動(dòng)大量元素，因此線性表不便于插入和刪除元素

?線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又叫線性鏈表

?特點(diǎn)

?各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)

?各數(shù)據(jù)元素的存儲(chǔ)順序和邏輯循序可以不一致

?線性表的鏈?zhǔn)酱鎯?chǔ)所占存儲(chǔ)空間大于順序存儲(chǔ)結(jié)構(gòu)

?查找結(jié)點(diǎn)時(shí)鏈?zhǔn)絻?chǔ)存要比順序存儲(chǔ)慢

?鏈?zhǔn)酱鎯?chǔ)插入刪除元素比順序存儲(chǔ)靈活

?線性鏈表的操作

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

?兩個(gè)特殊存儲(chǔ)結(jié)構(gòu)

?雙向鏈表

?循環(huán)鏈表

?是限定在一端進(jìn)行插入和刪除的線性表

?特點(diǎn)

?棧是只能在棧頂進(jìn)行插入和刪除

?棧的修改原則是“先進(jìn)后出"或"后進(jìn)先出"

?棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化

?棧底指針bottom、棧頂指針top、入棧、棧滿、出棧

?棧具有記憶功能

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

?棧的運(yùn)算

?隊(duì)歹U

?允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。原則是：先進(jìn)先出或（后進(jìn)

后出）

?隊(duì)頭指針front（在第一個(gè)數(shù)據(jù)元素前一格）、隊(duì)尾指針rear、入隊(duì)、出隊(duì)

?特點(diǎn)：

?隊(duì)列只允許在隊(duì)尾進(jìn)行插入，而在隊(duì)頭進(jìn)行刪除

?隊(duì)列的修改原則是“先進(jìn)先出"或"后進(jìn)后出"

?隊(duì)列中元素隨隊(duì)頭指針和隊(duì)尾指針的變化而動(dòng)態(tài)變化

?循環(huán)隊(duì)列

?循環(huán)隊(duì)列就是講隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞道第一個(gè)位置，形成邏輯上的

環(huán)狀空間

?rear>front

?s=rear-front

?rear<front

?s=（容量-front）+rear

?rear=front

?s=l或者s=0

?非線性結(jié)構(gòu)

?非以上類(lèi)型結(jié)構(gòu)

?樹(shù)形結(jié)構(gòu)

?樹(shù)是n（n>0）個(gè)元素的有限集合。他有且僅有一個(gè)稱(chēng)為根的元素；其余元素是互

不相交的子樹(shù)。

?常用術(shù)語(yǔ)：

?父結(jié)點(diǎn)、子結(jié)點(diǎn)

?父結(jié)點(diǎn)即前件

?子節(jié)點(diǎn)即后件

?根結(jié)點(diǎn)、葉子結(jié)點(diǎn)

?根結(jié)點(diǎn)即沒(méi)有前件的結(jié)點(diǎn)

?葉子結(jié)點(diǎn)即沒(méi)有后件的結(jié)點(diǎn)

?結(jié)點(diǎn)的度.樹(shù)的度

?結(jié)點(diǎn)的度即一個(gè)結(jié)點(diǎn)所擁有的后件的數(shù)

?樹(shù)的度即所有結(jié)點(diǎn)中最大的度稱(chēng)為樹(shù)的度

?樹(shù)的深度

?從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的層數(shù)

?子樹(shù)

?以某個(gè)結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的數(shù)稱(chēng)為該結(jié)點(diǎn)的一顆子樹(shù)

?二叉樹(shù)

?二叉樹(shù)是一個(gè)有限的結(jié)點(diǎn)集合，該集合或者為空，或者有一個(gè)根結(jié)點(diǎn)及其兩顆

互不相交的左右二叉子樹(shù)所組成

?二叉樹(shù)的特點(diǎn)：

?非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)

?每一個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)

?二叉樹(shù)有五種基本形態(tài)：

?空二叉樹(shù)

?什么都沒(méi)有

?只有T結(jié)點(diǎn)的二叉樹(shù)

?只有左子樹(shù)的二叉樹(shù)

?只有右子樹(shù)的二叉樹(shù)

?左右子樹(shù)雙全的二叉樹(shù)

?特殊二叉樹(shù)

?滿二叉樹(shù)

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

?即最后一層無(wú)子節(jié)點(diǎn)

?完全二叉樹(shù)

?除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺右

邊的若干結(jié)點(diǎn)

?滿二叉樹(shù)是完全二叉樹(shù)，但是完全二叉樹(shù)不一定是滿二叉樹(shù)

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

?非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)，分別稱(chēng)為左子樹(shù)

和右子樹(shù)

?在二叉樹(shù)的第K層上，最多有2A（K-1）個(gè)結(jié)點(diǎn)

深度為的二叉樹(shù)最多有個(gè)結(jié)點(diǎn)

?m2Am-l

?度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)

?有n個(gè)結(jié)點(diǎn)的二叉樹(shù)深度至少為【log_2口n]+1

?二叉樹(shù)的遍歷

?按照一定的順序訪問(wèn)二叉樹(shù)中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次

?前序遍歷：

?訪問(wèn)根結(jié)點(diǎn)-前序遍歷左子樹(shù)一前序遍歷右子樹(shù)（根左右）

?首先訪問(wèn)根結(jié)點(diǎn)，然后左子樹(shù),又左子樹(shù)有子樹(shù)則左子樹(shù)又可視為根結(jié)

點(diǎn)，直到?jīng)]有子樹(shù)為止，再右子樹(shù)，再上一層右子樹(shù)，直到所有結(jié)點(diǎn)被

訪問(wèn)

?中序遍歷：

?中序遍歷左子樹(shù)—訪問(wèn)根結(jié)點(diǎn)一中序遍歷右子樹(shù)（左根右）

?先訪問(wèn)最左子樹(shù)，然后該子樹(shù)的根，然后訪問(wèn)右子樹(shù)，然后上一層的根,

然后上一層右子樹(shù)中最左的子樹(shù)，直到所有結(jié)點(diǎn)被訪問(wèn)

?后序遍歷：

?后序遍歷左子樹(shù)一后序遍歷右子樹(shù)一訪問(wèn)根結(jié)點(diǎn)（左右根）

?先訪問(wèn)最左子樹(shù)，然后最左子樹(shù)的右子樹(shù)，然后該子樹(shù)的根，然后因?yàn)?/p>

該根是上一層的左子樹(shù)，訪問(wèn)上一層的右子樹(shù)中最左的子樹(shù)，循環(huán)，直

到所有結(jié)點(diǎn)被訪問(wèn)

?圖狀結(jié)構(gòu)

?存儲(chǔ)結(jié)構(gòu)

?又稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放方式

?一個(gè)邏輯結(jié)構(gòu)可以有多種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

?不同的存儲(chǔ)結(jié)構(gòu)其數(shù)據(jù)處理的效率不同

?順序存儲(chǔ)

?主要用于線性的數(shù)據(jù)結(jié)構(gòu)

?把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里

?犍式存儲(chǔ)

?每一個(gè)結(jié)點(diǎn)至少包含一個(gè)指針域

?用指針的指向來(lái)體現(xiàn)數(shù)據(jù)元素之間在邏輯上的聯(lián)系

?1EW

?插入

?刪除

?查找

?順序查找

?對(duì)于長(zhǎng)度為n的線性表，平均要進(jìn)行n/2次比較，在最壞的情況下進(jìn)行n次比較。

?以下兩種情況只能使用順序查找

?無(wú)序表

?鏈?zhǔn)骄€性表（不管無(wú)序還是有序）

?（適用于所有的線性表）

?二分直找

?適用于順序存儲(chǔ)的有序表

?對(duì)長(zhǎng)度為n的線性表，在最壞的情況下進(jìn)行l(wèi)og_2Dn次匕俄。

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

?排序

?排序（重點(diǎn)記憶最壞情況，和希爾排序與堆排序）

排序

排序平均時(shí)間最壞情況

冒泡排序n(n-1)/2n(n-1)/2

交換類(lèi)

快速排序n(n-1)/2n(n-1)/2

插入AE序n(n-1)/2n(n-1)/2

插入類(lèi)

希爾排序nlog2nn15

選擇排序n(n-1)/2n(n-1)/2

選擇類(lèi)

堆排序nlog2nnlog2n

?快速排序基本思想：

?在要排序的序列中找一個(gè)數(shù)作為基準(zhǔn)數(shù)（通常為第一個(gè)數(shù)）

?找匕瞰數(shù)的時(shí)候

?從后往前開(kāi)始找比基準(zhǔn)數(shù)小的數(shù)

?從前往后開(kāi)始找比基準(zhǔn)數(shù)大的數(shù)

?通過(guò)交換將這個(gè)序列中所有比基準(zhǔn)數(shù)大的數(shù)放在右邊，比基準(zhǔn)數(shù)小的數(shù)放在左邊

?即交換基準(zhǔn)數(shù)和被比較數(shù)

?以基準(zhǔn)數(shù)為分割線分為兩個(gè)子表，對(duì)兩個(gè)子表重復(fù)上述步驟

?eg.

?4530618274122649

?2630124574826149

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

?良好的程序設(shè)計(jì)風(fēng)格

?清晰第一，效率第二

?如何形成良好的程序設(shè)計(jì)風(fēng)格：

?源程序內(nèi)部文檔化

?選擇標(biāo)識(shí)符的名字

?注釋?zhuān)ㄐ蜓孕院凸δ苄宰⑨專(zhuān)?/p>

?序言性注釋一般位于模塊的首部，用于說(shuō)明模塊的相關(guān)信息（標(biāo)題、功能的說(shuō)明、主要

的算法、模塊接口、開(kāi)發(fā)歷史、開(kāi)發(fā)者、復(fù)審者和復(fù)審日期）

?功能性注釋位于源程序模塊內(nèi)部

?程序的視覺(jué)組織

?數(shù)據(jù)說(shuō)明

?語(yǔ)句的結(jié)構(gòu)

?輸入和輸出

?結(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è)T的模塊

?限用goto:

?限制使用goto語(yǔ)句，程序的質(zhì)量與goto語(yǔ)句數(shù)量成反比

?結(jié)構(gòu)化程序的基本結(jié)構(gòu)

?結(jié)構(gòu)化程序設(shè)計(jì)常采用順序、選擇（分支）和循環(huán)三種基本結(jié)構(gòu)

?程序設(shè)計(jì)語(yǔ)言的基本成分是

?數(shù)據(jù)成分、運(yùn)算成分、控制成分和傳輸成分

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

?幾個(gè)術(shù)語(yǔ)

?對(duì)象：

?在現(xiàn)實(shí)世界中，每個(gè)實(shí)體都是對(duì)象，例如，大學(xué)生、汽車(chē)、電視機(jī)、空調(diào)等都是現(xiàn)實(shí)世界

中的對(duì)象

?屬性：

?用于描述對(duì)象的狀態(tài)

?方法：

?用于描述對(duì)象的行為

?類(lèi)：

?類(lèi)是一組具有相同屬性和相同操作的對(duì)象的集合

?基于同一類(lèi)產(chǎn)生的對(duì)象可以分別設(shè)置各自的屬性

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

.標(biāo)識(shí)唯一性：

?對(duì)象可由內(nèi)在本質(zhì)來(lái)區(qū)分。而不是通過(guò)描述來(lái)區(qū)分

?分類(lèi)性：

?可以將具有相同屬性和操作的對(duì)象抽象成類(lèi)

?多態(tài)性：

?同一操作可以是不同對(duì)象的行為

?封裝性：

?從外面看不到對(duì)象的內(nèi)部，只能看到對(duì)象的外部特征

?模塊獨(dú)立性好：

?對(duì)象是面向?qū)ο蟮能浖幕灸K，內(nèi)聚性強(qiáng)

?繼承

?使用已有的類(lèi)建立新類(lèi)的定義技術(shù)。能直接獲得已有的性質(zhì),而不必重復(fù)定義他們

?類(lèi)直接共享屬性和操作的機(jī)制

?消息

?是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。對(duì)象間的通信靠消息傳遞

?消息的組成包括:

?接收消息的對(duì)象的名稱(chēng)

?消息標(biāo)識(shí)符，也成消息名

?零個(gè)或多個(gè)參數(shù)

?多態(tài)性

?是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象軟件軟件（程序、數(shù)據(jù)、文

檔）

?軟件

?包含程序、數(shù)據(jù)、文檔

?軟件的分類(lèi)

?系統(tǒng)軟件：

?操作系統(tǒng)、編譯程序、匯編程序、網(wǎng)絡(luò)軟件、數(shù)據(jù)庫(kù)管理系統(tǒng)

?應(yīng)用軟件：

?事務(wù)處理軟件、工程與科學(xué)計(jì)算軟件、實(shí)時(shí)處理軟件、人工智能軟件

?eg.QQ,游戲，教務(wù)管理系統(tǒng)

?支撐軟件（工具軟件）：

?需求分析工具、編譯工具軟件、測(cè)試工具軟件、維護(hù)工具軟件

?軟件危機(jī)

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

?軟件工程

?軟件工程：應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工

序

?其目的是提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低軟件成本

?其核心思想是把軟件當(dāng)做一個(gè)工程產(chǎn)品來(lái)處理

?軟件工程三要素

?方法

?是完成軟件工程項(xiàng)目的技術(shù)手段

?工具

?支持軟件的開(kāi)發(fā)、管理和文檔生成

?過(guò)程

?支持軟件發(fā)開(kāi)的各環(huán)節(jié)的控制和管理

?軟件生命周期

?將軟件產(chǎn)品產(chǎn)品能夠提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱(chēng)為軟件生命周期

?分為

?軟件定義

?問(wèn)題定義可行性研究

?可行性分析報(bào)告

?需求分析

?需求分析

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

?其工作：

?需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)、需求評(píng)審

?產(chǎn)生文檔：

?需求規(guī)格說(shuō)明書(shū)

?需求規(guī)格說(shuō)明書(shū)的作用：

?便于用戶、開(kāi)發(fā)人員進(jìn)行理解交流

?反映用戶問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的繼承和依據(jù)

?作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)

?需求規(guī)格說(shuō)明書(shū)（SRS）

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

?正確性：體現(xiàn)待開(kāi)發(fā)系統(tǒng)的真是要求

?無(wú)歧義性：對(duì)每個(gè)需求只有一種解釋

?完整性：包括全部有意義的需求

?可驗(yàn)證性：每個(gè)需求都是可驗(yàn)證的

?一致性：各個(gè)需求的描述不矛盾

?可理解性：需求說(shuō)明書(shū)必須簡(jiǎn)明易懂

?可修改性：結(jié)構(gòu)風(fēng)格在改變時(shí)，是易于實(shí)現(xiàn)的

?可追蹤性：每個(gè)需求的來(lái)源和流向是清晰的

?需求分析方法有：

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

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

?使用數(shù)據(jù)流圖（DFD）

?數(shù)據(jù)流圖的圖形元素

?。加工：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出

?一數(shù)據(jù)流：沿箭頭方向傳遞數(shù)據(jù)的通道

?=存儲(chǔ)文件（數(shù)據(jù)源）：存放各種數(shù)據(jù)的文件

?口源（潭）：系統(tǒng)和環(huán)境的接口

?數(shù)據(jù)字典（DD）

?結(jié)構(gòu)化分析的核心

?對(duì)數(shù)據(jù)流圖中所有元素的定義的集合

?判定表

?判定樹(shù)

?等（結(jié)構(gòu)化語(yǔ)言）工具，來(lái)建立系統(tǒng)的邏輯模型

?面向?qū)ο蟮男枨蠓椒?/p>

?軟件開(kāi)發(fā)

?概要設(shè)計(jì)

?概要設(shè)計(jì)說(shuō)明書(shū)

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

?詳細(xì)設(shè)計(jì)說(shuō)明書(shū)

?實(shí)現(xiàn)

?用戶操作手冊(cè)

?測(cè)試

?測(cè)試分析報(bào)告

?軟件運(yùn)行維護(hù)

?使用

?維護(hù)

?3個(gè)時(shí)期8個(gè)階段。維護(hù)是持續(xù)時(shí)間最長(zhǎng),花費(fèi)代價(jià)最大的一個(gè)時(shí)期

?軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)代價(jià)

?軟件設(shè)計(jì)

軟件設(shè)計(jì)確定程序的物理模型，軟件分析確定程序的邏輯模型

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

?從工程管理角度劃分：

?概要設(shè)計(jì)

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

?設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)

?數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)

?編寫(xiě)概要設(shè)計(jì)文檔

?概要設(shè)計(jì)文檔評(píng)審

?概要設(shè)計(jì)的工具是程序結(jié)構(gòu)圖（SC）

?程序結(jié)構(gòu)圖（SC）

程序結(jié)構(gòu)圖（SC）

出1序結(jié)構(gòu)圖的基本圖符：

一I一

一般橫塊數(shù)據(jù)信息控制信息

31序結(jié)構(gòu)圖的基本形式:

基本順序重復(fù)選擇

?程序結(jié)構(gòu)圖的基本圖符：

?一般模塊、數(shù)據(jù)信息、控制信息

?程序結(jié)構(gòu)圖的基本形式：

?基本、順序、重復(fù)、選擇

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

?詳細(xì)設(shè)計(jì)的任務(wù)：

?確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法標(biāo)識(shí)算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)

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

?圖形工具：

?程序流程圖、N-S圖、PAD、HIPO

?表格工具：

?判定表

?語(yǔ)言工具：

?PDL（偽碼）

?程序流程圖

程序流程圖

?程序流程圖的基本圖符：

?①控制流表示為：或

?②加工步驟表示為：□

<O>

?③邏輯條件表示為：

ra.WK]

「?也」9

?程序流程圖的基本圖符：

?控制流TI

?加工步驟口

?邏輯條件

?按技術(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)。（高內(nèi)聚低耦合）

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

?內(nèi)聚性：指一個(gè)模塊臉各個(gè)元素件彼此結(jié)合的緊密程度（高內(nèi)聚）

?耦合性：指模塊間相互連接的緊密程度（低耦合）

?非直接耦合、數(shù)據(jù)耦合、標(biāo)記耦合、控制耦合.外部耦合、公共耦合.內(nèi)容耦合

（由弱到強(qiáng)）

?軟件測(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ù)提供方便

?靜態(tài)和動(dòng)態(tài)測(cè)試

?靜態(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è)試

?白盒測(cè)試

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

試

?程序的內(nèi)部邏輯結(jié)構(gòu)

?邏輯覆蓋測(cè)試

?基本路徑測(cè)試

?黑盒測(cè)試

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

?程序的外部功能

?等價(jià)類(lèi)劃分法

?邊界值分析法

?錯(cuò)誤推測(cè)法

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

?單元測(cè)試

?是對(duì)軟件設(shè)計(jì)的最小單元一模塊進(jìn)行測(cè)試，目的是發(fā)現(xiàn)各模塊內(nèi)部的錯(cuò)誤

?集成測(cè)試

?是把模塊按照設(shè)計(jì)要求組裝起來(lái)的同時(shí)進(jìn)行測(cè)試，目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤

?確認(rèn)測(cè)試

?是驗(yàn)證軟件的功能和性能是否滿足各種需求，以及軟件配置是否完全、正確

?系統(tǒng)測(cè)試

?是將軟件作為一個(gè)元素，與計(jì)算機(jī)系統(tǒng)其他元素組合在一起，進(jìn)行集成測(cè)試

?程序調(diào)試

?對(duì)程序進(jìn)行了成功的測(cè)試之后將進(jìn)入程序調(diào)試，通常稱(chēng)為Debug（排錯(cuò)），主要在開(kāi)發(fā)階段進(jìn)行

?程序調(diào)試的任務(wù)是診斷和改正程序迪錯(cuò)誤

?基本步驟

?錯(cuò)誤定位

?修改設(shè)計(jì)和代碼，以排除錯(cuò)誤

?進(jìn)行回歸測(cè)試，防止引進(jìn)新的錯(cuò)誤

?軟件調(diào)試方法

?強(qiáng)行排除法

?回溯法

?原因排除法

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

?數(shù)據(jù)：（Data）

?描述事物的符號(hào)記錄稱(chēng)為數(shù)據(jù)

?實(shí)際上就是描述事物的符號(hào)記錄

?軟件中的數(shù)據(jù)一定是有結(jié)構(gòu)的，有型與值兩個(gè)概念

?數(shù)據(jù)庫(kù)：（DB）

?是指長(zhǎng)期儲(chǔ)存在計(jì)算機(jī)內(nèi)的，有組織的，可共享的數(shù)據(jù)集合

?數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有兩大特點(diǎn)：

?"集成"，"共享"

?數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS（系統(tǒng)軟件）

?數(shù)據(jù)庫(kù)管理系統(tǒng)是數(shù)據(jù)庫(kù)系統(tǒng)的核心

?數(shù)據(jù)庫(kù)語(yǔ)言

?數(shù)據(jù)定義語(yǔ)言DDL

?數(shù)據(jù)模式定義

?數(shù)據(jù)存儲(chǔ)的物理構(gòu)建

?數(shù)據(jù)操縱語(yǔ)言DML

?數(shù)據(jù)操縱

?包括查詢與增、刪、改等操作

?數(shù)據(jù)控制語(yǔ)言DCL

?數(shù)據(jù)的安全性的定義與檢查

?并發(fā)控制與故障恢復(fù)

?數(shù)據(jù)的完整性

?數(shù)據(jù)庫(kù)管理員DBA（人員）

?主要工作包括：

?數(shù)據(jù)庫(kù)設(shè)計(jì)

?數(shù)據(jù)庫(kù)維護(hù)

?改善系統(tǒng)性能，提高系統(tǒng)效率

?數(shù)據(jù)庫(kù)系統(tǒng)（DBS）

?數(shù)據(jù)庫(kù)（數(shù)據(jù)）

?集成，共享

?數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS（系統(tǒng)軟件）

?定義，構(gòu)建，操縱，檢查，控制，服務(wù)。DDL,DML,DCL

?數(shù)據(jù)庫(kù)管理員DBA（人員）

?設(shè)計(jì)，維護(hù)，改善性能，提高效率

?軟件平臺(tái)

?操作系統(tǒng)，開(kāi)發(fā)工具，接口軟件

?硬件平臺(tái)

?計(jì)算機(jī)，網(wǎng)絡(luò)

?數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)（DBAS）

?數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)包括：

?數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件以及應(yīng)用界面

?數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)>數(shù)據(jù)庫(kù)系統(tǒng)>數(shù)據(jù)庫(kù)管理系統(tǒng)>操作系統(tǒng)>硬件

?數(shù)據(jù)管理三個(gè)階段

?人工管理（早期）

?文件系統(tǒng)（發(fā)展）

?數(shù)據(jù)庫(kù)系統(tǒng)（現(xiàn)在）

?數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是：

?解決數(shù)據(jù)共享問(wèn)題

?數(shù)據(jù)庫(kù)系統(tǒng)特點(diǎn)：

?集成性

?高共享低冗余

?獨(dú)立性

?統(tǒng)一管理控制

?三級(jí)模式和兩級(jí)映射

?外模式（用戶數(shù)據(jù)庫(kù)）：

?又稱(chēng)子模式或用戶模式，是用戶的數(shù)據(jù)視圖

?最外層

?概念模式（概念數(shù)據(jù)庫(kù)）：

?是全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶的公共數(shù)據(jù)視圖

?中層

?內(nèi)模式（物理數(shù)據(jù)庫(kù)）：

?給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與存取方法。

?最底層

?外模式f念模式映射

?概念模式一內(nèi)模式映射

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

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

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

?數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束

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

?概念數(shù)據(jù)模型：E-R模型

?簡(jiǎn)稱(chēng)概念模型

?是一種面向客觀世界，面向用戶的模型，它與具體的數(shù)據(jù)庫(kù)管理系統(tǒng)、與具體的計(jì)算機(jī)平

臺(tái)無(wú)關(guān)

?著重于對(duì)客觀世界復(fù)雜事物的描述以及對(duì)它們內(nèi)在聯(lián)系的刻畫(huà)

?實(shí)體（矩形）

?客觀存在并且可以相互區(qū)別的事物

?屬性（橢圓形）

?描述實(shí)體的特征

?聯(lián)系（菱形）

?實(shí)體間對(duì)應(yīng)的關(guān)系，反映了世間事物的相互聯(lián)系

?一對(duì)一的關(guān)系

?一對(duì)多的關(guān)系

?多對(duì)多的關(guān)系

?聯(lián)系關(guān)系

?邏輯數(shù)據(jù)模型：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ?/p>

?簡(jiǎn)稱(chēng)數(shù)據(jù)模型

?面向數(shù)據(jù)庫(kù)系統(tǒng)的模型，它著重于數(shù)據(jù)庫(kù)的一級(jí)實(shí)現(xiàn)

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

?層次模型：

?樹(shù)

?網(wǎng)狀模型：

?無(wú)向圖

?關(guān)系模型：

?二維表

?采用二維表來(lái)表示，簡(jiǎn)稱(chēng)表，每一個(gè)二維表稱(chēng)為一個(gè)關(guān)系

?屬性

?二維表中的一列稱(chēng)為屬性

?元組

?二維表中的一行稱(chēng)為元組

?一個(gè)元組可以由若干元組分量組成,元組分量的個(gè)數(shù)等于屬性的個(gè)數(shù)

?（分量不可再分）

?關(guān)系操縱

?查詢、增加、刪除和修改

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

?實(shí)體完整性約束

?主關(guān)鍵字不能為空

?參照完整性約束

?用戶定義的完整性約束

?物理數(shù)據(jù)模型

?簡(jiǎn)稱(chēng)物理模型

?面向計(jì)算機(jī)物理實(shí)現(xiàn)的模型，該模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上的物理結(jié)構(gòu)的表示

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

?關(guān)系模型的基本操作

?插入、刪除、修改、查詢

?查詢運(yùn)算

?投影運(yùn)算

投影

R

姓名

姓名

a

花道

櫻木

花道

櫻木

10

r

11

7

楓

流川

洞II楓

c

田

宮城良

田

宮城良豆

剛憲

赤木

剛憲

赤木目

壽

三井

三井壽

性

影屬

?投

擇列

?選

算

擇運(yùn)

?選

選擇

T

R

照片

姓名

球衣

照片

姓名

球衣

4

以

剛憲

赤木

10

□

花道

櫻木胸

14

3

壽

三井

11

7

田

宮城良

4

憲

赤木剛

14

三井壽

組

擇元

?選

擇行

?選

算）

接運(yùn)

算（連

積運(yùn)

卡爾

?笛

S

=Rx

爾根T

笛卡

RDS

?T=

算

充運(yùn)

的擴(kuò)

數(shù)中

系代

?關(guān)

?并運(yùn)算

并T=R+S

RST

姓名姓名