第一章數(shù)據(jù)構(gòu)造與算法

L1算法

算法：是指解題方案的精確而完整的）描述。

算法不等于程序，也不等計算機措施，程序的編制不也許優(yōu)于

算法的設計。

算法的基本特性：是一組嚴謹?shù)囟x運算次序的規(guī)則，每一種規(guī)

則都是有效的，是明確的，此次序?qū)⒃谟邢薜拇螖?shù)下終止。

特性包括：

（1）可行性；

（2）確定性，算法中每一環(huán)節(jié)都必須有明確定義，不容許有模

棱兩可的解釋，不容許有多義性；

（3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有

限個環(huán)節(jié)后終止，包括合理的執(zhí)行時間時含義；

（4）擁有足夠的情報。

算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控

制構(gòu)造。

基本運算和操作包括：算術(shù)運算、邏輯運算、關系運算、數(shù)據(jù)傳

播。

算法的控制構(gòu)造：次序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造。

算法基本設計措施：列舉法、歸納法、遞推、遞歸、減半遞推技

術(shù)、回溯法。

算法復雜度：算法時間復雜度和算法空間復雜度。

算法時間復雜度是指執(zhí)行算法所需要的計算工作量。

一般來說，算法的工作量用其執(zhí)行的基本運算次數(shù)來度量，而

算法執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)。在同一種問題規(guī)模下,

用平均性態(tài)和最壞狀況復雜性來分析。一般狀況下，用最壞狀況復雜

性來分析算法的時間復雜度。

算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。

1.2數(shù)據(jù)構(gòu)造的基本概念

數(shù)據(jù)構(gòu)造研究的三個方面：

(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的

邏輯構(gòu)造；

(2)在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系,

即數(shù)據(jù)的存儲構(gòu)造；

(3)對多種數(shù)據(jù)構(gòu)造進行的運算。

數(shù)據(jù)構(gòu)造是指互相有關聯(lián)的數(shù)據(jù)元素的集合。

數(shù)據(jù)構(gòu)造是反應數(shù)據(jù)元素之間關系的數(shù)據(jù)元素集合的表達。

數(shù)據(jù)的邏輯構(gòu)造包括：

(1)表達數(shù)據(jù)元素的信息；

(2)表達各數(shù)據(jù)元素之間的前后件關系。(邏輯關系，與在計算

機內(nèi)的存儲位置無關)

一種數(shù)據(jù)構(gòu)造中的各數(shù)據(jù)元素在計算機存儲空間中的位置關系與

邏輯關系有也許不一樣。

數(shù)據(jù)的存儲構(gòu)造是數(shù)據(jù)的邏輯構(gòu)造在計算機存儲空間中的寄存形

式。

常用的存儲構(gòu)造有次序、鏈接、索引等。

根據(jù)數(shù)據(jù)構(gòu)造中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般

將數(shù)據(jù)構(gòu)造分為線性構(gòu)造和非線性構(gòu)造。

線性構(gòu)造條件：

(1)有且只有一種根結(jié)點；

(2)每一種結(jié)點最多有一種前件，也最多有一種后件。

非線性構(gòu)造：不滿足線性構(gòu)造條件的數(shù)據(jù)構(gòu)造。

1.3線性表及其次序存儲構(gòu)造

線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的

序號，元素之間的相對位置是線性的。

如：一種N維向量、矩陣

在復雜線性表中，由若干項數(shù)據(jù)元素構(gòu)成的J數(shù)據(jù)元素稱為記錄,

而由多種記錄構(gòu)成的線性表又稱為文獻。

非空線性表的構(gòu)造特性：

(1)有且只有一種根結(jié)點al,它無前件；

(2)有且只有一種終端結(jié)點an,它無后件；

(3)除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一種前件,

也有且只有一種后件。結(jié)點個數(shù)n稱為線性表的長度，當n=0時，稱

為空表。

線性表的次序存儲構(gòu)造具有如下兩個基本特點：

(1)線性表中所有元素的所占的存儲空間是持續(xù)的；

(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯次序依次寄存

的。

ai的存儲地址為：ADR(ai)=ADR(al)+(i-l)k,,ADR(al)為第一種

元素的地址，k代表每個元素占的字節(jié)數(shù)。

次序表的運算：插入、刪除。

1.4棧和隊列

棧是限定在一端進行插入與刪除的線性表，容許插入與刪除時

一端稱為棧頂，不容許插入與刪除的另一端稱為棧底。

棧按照“先進后出"(FILO)或“后進先出"(LIFO)組織數(shù)據(jù)，棧

具有記憶作用。用top表達棧頂位置，用bottom表達棧底。

棧的次序存儲

用一維數(shù)組S(l:m)作為棧的次序存儲空間，M為棧的最大容

量。S(bottom)表達棧底元素，s(top)為棧頂元素，top=0表達?？?

top=m表達棧滿。

棧的基本運算:

（1）插入元素稱為入棧運算；（top=top+1;將新元素插入到棧頂

指針指向的位置）.上溢

（2）刪除元素稱為退棧運算；（將棧頂指針指向的元素賦給指定

的變量，top=top-l）下溢

（3）讀棧頂元素是將棧頂元素賦給一種指定的變量，此時指針

無變化。

隊列

隊列是指容許在一端（隊尾）進入插入，而在另一端（隊頭）進

行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。

隊列是“先進先出"（FIFO）或“后進后出”（LIL0）的線性表。

隊列的次序存儲

與棧類似，用一維數(shù)組Q（1：m）作為隊列的次序存儲空間

隊列運算

（1）入隊運算：從隊尾插入一種元素；

（2）退隊運算：從隊頭刪除一種元素。

循環(huán)隊列：

在循環(huán)隊列構(gòu)造中，當存儲空間的最終一種位置已被使用而要

進行入隊運算時，只要存儲空間的第一種位置空閑，就可將元素加

入到第一種位置，即將存儲空間的第一種位置作為隊尾。

MAXSIZE-1

從Front指針指向的后一種位置直到隊尾指針rear指向的位置

之間所有的元素均為隊列中的元素。

循環(huán)隊列的J初始狀態(tài)為空：rear=front=m

當循環(huán)隊列滿時，rear=Front

為區(qū)別隊滿還是隊空，增長標志S。

s=0表達隊列空，s=l且front=rear表達隊列滿

1.5線性鏈表

對于元素變動頻繁的大線性表不適宜采用次序存儲構(gòu)造，而應

采用鏈式存儲構(gòu)造。

在鏈式存儲構(gòu)造中，數(shù)據(jù)構(gòu)造中的每一種結(jié)點對應于一種存儲

單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。

結(jié)點由兩部分構(gòu)成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域：（2）

用于寄存指針，稱為指針域，用于指向前一種或后一種結(jié)點。

在鏈式存儲構(gòu)造中，存儲數(shù)據(jù)構(gòu)造的存儲空間可以不持續(xù)，各

數(shù)據(jù)結(jié)點的存儲次序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)

據(jù)元素之間的邏輯關系是由指針域來確定的o

鏈式存儲方式既可用于表達線性構(gòu)造，也可用于表達非線性構(gòu)

造。

線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，假

如是兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向

后件結(jié)點。

線性鏈表的基本運算：查找、插入、刪除。

1.6樹與二叉樹

樹是一種簡樸的非線性構(gòu)造，所有元素之間具有明顯的層次特

在樹構(gòu)造中，每一種結(jié)點只有一種前件，稱為父結(jié)點，沒有前

件的結(jié)點只有一種，稱為樹的根結(jié)點，簡稱樹的根。每一種結(jié)點可以

有多種后件，稱為該結(jié)點的子結(jié)點。沒有后件時結(jié)點稱為葉子結(jié)點。

在樹構(gòu)造中，一種結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度,

所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

度為2的樹稱為二叉樹。

A)1

二叉樹的特點:

(1)非空二叉樹只有一種根結(jié)點；

(2)每一種結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹

與右子樹。

二叉樹的基本性質(zhì)：

(1)在二叉樹的第k層上，最多有2k-l(k，l)個結(jié)點；

(2)深度為m時二叉樹最多有才-1個結(jié)點；

(3)度為0時結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一種;

(4)具有n個結(jié)點的二叉樹，其深度至少為[log2n]+l,其中

[log2n]表達取log2n的整數(shù)部分；

滿二叉樹是指除最終一層外，每一層上的所有結(jié)點有兩個子結(jié)

點，

滿二叉樹的性質(zhì)：

第k層上有2k-1個結(jié)點，深度為m的滿二叉樹有2m-l個結(jié)點。

完全二叉樹是指除最終一層外，每一層上的結(jié)點數(shù)均到達最大

值，在最終一層上只缺乏右邊的若干結(jié)點。

由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是完全

二叉樹，完全二叉樹一般不是滿二叉樹。

完全二叉樹的I性質(zhì)：

(1)具有n個結(jié)點時完全二叉樹的深度為［log/l+l；

(2)設完全二叉樹共有n個結(jié)點。假如從根結(jié)點開始，按層序

(每一層從左到右)用自然數(shù)1,2,n給結(jié)點進行編號

(k=l,2-.n),有如下結(jié)論：

①若k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>l,則該結(jié)

點區(qū)I父結(jié)點編號為INT(k/2)；

②若2kWn,則編號為k的結(jié)點時左子結(jié)點編號為2k；否則該結(jié)

點無左子結(jié)點(也無右子結(jié)點)；

③若2k+l〈n,則編號為k的結(jié)點的右子結(jié)點編號為2k+l；否則

該結(jié)點無右子結(jié)點。

二叉樹存儲構(gòu)造

采用鏈式存儲構(gòu)造，對于滿二叉樹與完全二叉樹可以按層序進

行次序存儲。

二叉樹的遍歷：

（1）前序遍歷（DLR）,首先訪問根結(jié)點，然后遍歷左子樹，最

終遍歷右子樹；ABDEHICFG

（2）中序遍歷（LDR）,首先遍歷左子樹，然后訪問根結(jié)點，最

終遍歷右子樹；DBHEIAFCG

（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最

終訪問根結(jié)點。DHIEBFGCA

例：設有如下的二叉樹

其前序遍歷（DLR）的成果為：ABDEHICFG

其中序遍歷（LDR）的成果為：DBHEIAFCG

其后序遍歷（LRD）的成果為：DHIEBFGCA

1.7查找技術(shù)

次序查找的使用狀況：

(1)線性表為無序表；(不管是次序存儲構(gòu)造還是鏈式存儲構(gòu)造)

(2)表采用鏈式存儲構(gòu)造。(雖然是有序線性表)

二分法查找只合用于次序存儲時有序表，

對于長度為n的有序線性表，二分查找最壞狀況只需比較log2n

次，次序查找需要比較n次。

1.8排序技術(shù)

排序是指將一種無序序列整頓成按值非遞減次序排列的有序序

列。

互換類排序法：

假設線性表的長度為n

(1)冒泡排序法

在最壞狀況下，需要比較的次數(shù)為n(n-1)/2；

(2)迅速排序法

在最壞狀況下，需要比較的J次數(shù)為n(n-l)/2

插入類排序法：

(1)簡樸插入排序法，最壞狀況需要n(nT)/2次比較；

(2)希爾排序法，最壞狀況需要0(nL5)次比較。

選擇類排序法：

(1)簡樸選擇排序法,最壞狀況需要n(n-1)/2次比較；

(2)堆排序法，最壞狀況需要0(nlog2n)次比較。

第二章程序設計基礎

2.1程序設計設計措施和風格

怎樣形成良好的程序設計風格

L源程序文檔化；2.數(shù)聽闡明的措施；

3.語句的構(gòu)造；4.輸入和輸出。

注釋分序言性注釋和功能性注釋，語句構(gòu)造清晰第一、效率第

二。

2.2構(gòu)造化程序設計

構(gòu)造化程序設計措施的四條原則是：1.自頂向下；2.逐漸求精；

3.模塊化；4.限制使用goto語句。

構(gòu)造化程序的基本構(gòu)造和特點：

(1)次序構(gòu)造：一種簡樸的程序設計，最基本、最常用的構(gòu)造;

(2)選擇構(gòu)造：又稱分支構(gòu)造，包括簡樸選擇和多分支選擇構(gòu)

造，可根據(jù)條件，判斷應當選擇哪一條分支來執(zhí)行對應的語句序列；

(3)反復構(gòu)造：又稱循環(huán)構(gòu)造，可根據(jù)給定條件，判斷與否需

要反復執(zhí)行某一相似程序段。

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

面向?qū)ο蟮某绦蛟O計：以60年代末挪威奧斯陸大學和挪威計算

機中心研制的SIMULA語言為標志。

面向?qū)ο蟠胧┑拈L處：

(1)與人類習慣的思維措施一致；

(2)穩(wěn)定性好；

(3)可重用性好；

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

(5)可維護性好。

對象是面向?qū)ο蟠胧┲凶罨镜母拍?，可以用來表達客觀世界

中的任何實體，對象是實體的抽象。

面向?qū)ο蟮某绦蛟O計措施中的對象是系統(tǒng)中用來描述客觀事物的

一種實體，是構(gòu)成系統(tǒng)的一種基本單位，由一組表達其靜態(tài)特性的

屬性和它可執(zhí)行的一組操作構(gòu)成。

屬性即對象所包括的信息，操作描述了對象執(zhí)行的功能，操作

也稱為措施或服務。

對象的基本特點：

(1)標識惟一性；

(2)分類性；

(3)多態(tài)性；

(4)封裝性；

(5)模塊獨立性好。

類是指具有共同屬性、共同措施的對象的集合。因此類是對象的

抽象，對象是對應類的一種實例。

消息是一種實例與另一種實例之間傳遞的信息。

消息時構(gòu)成包括(1)接受消息的對象的名稱；(2)消息標識符,

也稱消息名；（3）零個或多種參數(shù)。

繼承是指可以直接獲得已經(jīng)有的性質(zhì)和特性，而不必反復定義

他們。

繼承分單繼承和多重繼承。單繼承指一種類只容許有一種父類,

多重繼承指一種類容許有多種父類。

多態(tài)性是指同樣的消息被不一樣的對象接受時可導致完全不一樣

的行動的J現(xiàn)象。

第三章軟件工程基礎

3.1軟件工程基本概念

計算機軟件是包括程序、數(shù)據(jù)及有關文檔的完整集合。

軟件的特點包括：

（1）軟件是一種邏輯實體；

（2）軟件的生產(chǎn)與硬件不一樣，它沒有明顯的制作過程；

（3）軟件在運行、有效期間不存在磨損、老化問題；

（4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系

統(tǒng)的限制，這導致了軟件移植的問題；

（5）軟件復雜性高，成本昂貴；

（6）軟件開發(fā)波及諸多的社會原因。

軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。

軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所碰到的一系

列嚴重問題（軟件開發(fā)成本和進度無法控制；質(zhì)量難以保證；軟件維

護程度低）

軟件危機重要表目前成本、質(zhì)量、生產(chǎn)率等問題。

軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套措施、

工具、文檔、實踐原則和工序。

軟件工程包括3個要素：措施、工具和過程。

措施是完畢軟件工程項目的技術(shù)手段；

工具支持軟件的開發(fā)、管理、文檔生成；

過程支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。

軟件工程的關鍵思想是把軟件產(chǎn)品看作是一種工程產(chǎn)品來處理。

軟件工程過程：是把輸入轉(zhuǎn)化為輸出的一組彼此有關的資源和

活動，包括4種基本活動：

(1)P(Plan)一一軟件規(guī)格闡明；(功能及其運行時的限制)

(2)D(Do)一一軟件開發(fā)；(產(chǎn)生滿足規(guī)格闡明的軟件)

(3)C(Check)一一軟件確認；(確認軟件可以滿足客戶提出的規(guī)

定)

(4)A(Action)---軟件演進。

軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退伍時

過程。

軟件生命周期三個階段：

軟件定義、軟件開發(fā)、運行維護

軟件定義階段：

(1)可行性研究與計劃制定；

(2)需求分析；

軟件開發(fā)階段：

(3)軟件設計；(概要設計和詳細設計)

(4)軟件實現(xiàn)；

(5)軟件測試；

軟件維護階段：

(6)運行和維護。

(7)退伍

軟件工程的目的與原則：

目的：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、

可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和

可互操作性且滿足顧客需求的產(chǎn)品。

基本目的：付出較低的開發(fā)成本；到達規(guī)定的軟件功能；獲得

很好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能準時完畢

開發(fā)，及時交付使用。.

基本原則：

抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性

和可驗證性。

軟件工程的理論和技術(shù)性研究的內(nèi)容重要包括：軟件開發(fā)技術(shù)

和軟件工程管理。

軟件開發(fā)技術(shù)包括：軟件開發(fā)措施學、開發(fā)過程、開發(fā)工具和軟

件工程環(huán)境。

軟件工程管理包括：軟件管理學、軟件工程經(jīng)濟學、軟件心理學

等內(nèi)容。

軟件管理學包括人員組織、進度安排、質(zhì)量保證、配置管理、項

目計劃等。

軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、

一致性、完備性和可驗證性。

現(xiàn)代軟件工程措施之因此得以實行，其重要的保證是軟件

開發(fā)工具和環(huán)境的保證。

軟件開發(fā)工具

軟件開發(fā)環(huán)境（全面支持軟件開發(fā)全過程的軟件工具的集合）

3.2構(gòu)造化分析措施

軟件開發(fā)措施是軟件開發(fā)過程所遵照的措施和環(huán)節(jié)，包括分析

措施、設計措施和程序設計措施。

構(gòu)造化措施的關鍵和基礎是構(gòu)造化程序設計理論。

（1）需求分析階段的工作：

（2）需求獲取：確定對目的I系統(tǒng)的各方面需求

（3）需求分析：確定給出系統(tǒng)的處理方案和目的系統(tǒng)的邏輯模型

（4）編寫需求規(guī)格闡明書

（5）需求評審

需求分析措施有（1）構(gòu)造化需求分析措施；（2）面向?qū)ο蟮姆?/p>

析的措施。

構(gòu)造化分析措施

構(gòu)造化分析措施的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解,

建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為重要工具，建立系統(tǒng)

的邏輯模型。

構(gòu)造化分析的常用工具

(1)數(shù)據(jù)流圖；(2)數(shù)據(jù)字典；(3)鑒定樹；(4)鑒定表。

數(shù)據(jù)流圖：描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型

的圖形表達，它直接支持系統(tǒng)功能建模。

數(shù)據(jù)字典：對所有與系統(tǒng)有關的數(shù)據(jù)元素的一種有組織的列表,

以及精確的、嚴格的定義，使得顧客和系統(tǒng)分析員對于輸入、輸出、

存儲成分和中間計算成果有共同的理解。

鑒定樹：從問題定義的文字描述中分清哪些是鑒定的條件，哪些

是鑒定的結(jié)論，根據(jù)描述材料中的連接詞找出鑒定條件之間的附屬

關系、并列關系、選擇關系，根據(jù)它們構(gòu)造鑒定樹。

鑒定表：與鑒定樹相似，當數(shù)據(jù)流圖中的加工要依賴于多種邏輯

條件的取值，即完畢該加工的一組動作是由于某一組條件取值的組

合而引起的I,使用鑒定表描述比較合適。

數(shù)據(jù)字典是構(gòu)造化分析的關鍵。

軟件需求規(guī)格闡明書的特點：

(1)對時性；

(2)無岐義性；

(3)完整性；

(4)可驗證性；

(5)一致性；

(6)可理解性；

(7)可追蹤性。

3.3構(gòu)造化設計措施

軟件設計的基本目的是用比較抽象概括的方式確定目的系統(tǒng)怎樣

完畢預定的任務，軟件設計是確定系統(tǒng)的物理模型。

軟件設計是開發(fā)階段最重要的環(huán)節(jié)，是將需求精確地轉(zhuǎn)化為完

整的軟件產(chǎn)品或系統(tǒng)的唯一途徑。

從技術(shù)觀點來看，軟件設計包括軟件構(gòu)造設計、數(shù)據(jù)設計、接口

設計、過程設計。

構(gòu)造設計：定義軟件系統(tǒng)各重要部件之間的關系。

數(shù)據(jù)設計：將分析時創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)構(gòu)造的定義。

接口設計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之

間怎樣通信。

過程設計：把系統(tǒng)構(gòu)造部件轉(zhuǎn)換成軟件的過程描述。

從工程管理角度來看：概要設計和詳細設計。

軟件設計的一般過程：軟件設計是一種迭代的過程；先進行高層

次的構(gòu)造設計；后進行低層次的過程設計；穿插進行數(shù)據(jù)設計和接口

設計。

軟件設計的基本原理：

(1)抽象(2)模塊化(3)信息屏蔽

(4)模塊獨立性

衡量軟件模塊獨立性使用耦合性和內(nèi)聚性兩個定性的度量原則。

在程序構(gòu)造中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應

高內(nèi)聚，低耦合。

軟件概要設計的基本任務是：

(1)設計軟件系統(tǒng)構(gòu)造；

(2)數(shù)據(jù)構(gòu)造及數(shù)據(jù)庫設計；

(3)編寫概要設計文檔；

(4)概要設計文檔評審。

常用的軟件構(gòu)造設計工具是程序構(gòu)造圖(SC),使用它描述軟件

系統(tǒng)的層次和構(gòu)造關系。

模塊用一種矩形表達，箭頭表達模塊間的調(diào)用關系。

在構(gòu)造圖中還可以用帶注釋的箭頭表達模塊調(diào)用過程中來回傳遞

的信息。還可用帶實心圓的箭頭表達傳遞的是控制信息，帶空心圓的

箭心表達傳遞的是數(shù)據(jù)。

構(gòu)造圖的基本形式：基本形式、次序形式、反復形式、選擇形式。

構(gòu)造圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)

模塊。

面向數(shù)據(jù)流的設計措施

在需求分析階段，重要分析信息在系統(tǒng)中加工和流動的狀況。

面向數(shù)據(jù)流的設計措施定義某些映射措施，把數(shù)據(jù)流圖變換成

構(gòu)造圖表達的軟件構(gòu)造。

經(jīng)典的數(shù)據(jù)流類型有兩種：變換型和事務型。

變換型系統(tǒng)構(gòu)造圖由輸入、中心變換、輸出三部分構(gòu)成。

事務型數(shù)據(jù)流的特點是：接受一項事務，根據(jù)事務處理的特點

和性質(zhì)，選擇分派一種合適的處理單元，然后給出成果。

詳細設計

詳細設計是為軟件構(gòu)造圖中的每一種模塊確定實現(xiàn)算法和局部數(shù)

據(jù)構(gòu)造，用某種選定的體現(xiàn)工具表達算法和數(shù)據(jù)構(gòu)造的細節(jié)。

常見的過程設計工具有：

圖形工具：程序流程圖、N-S（方框圖）、PAD（問題分析圖）、HIPO

表格工具：鑒定表

語言工具：PDL

3.4軟件測試

軟件測試是保證軟件質(zhì)量的重要手段，其重要過程涵蓋了整個

軟件生命周期的過程，包括需求定義階段的需求測試、編碼階段的單

元測試、集成測試以及后期確實認測試、系統(tǒng)測試。

軟件測試定義：使用人工或自動手段來運行或測定某個系統(tǒng)的過

程，其目的在于檢查它與否滿足規(guī)定的需求或是弄清預期成果與實

際成果之間的差異。

軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。

一種好的測試用例是指很也許找到迄今為止尚未發(fā)現(xiàn)的錯誤時用

例。

一種成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。

測試要以查找錯誤為中心，測試只能證明程序中有錯誤，不能

證明程序中沒有錯誤。

軟件測試措施

從與否需要執(zhí)行被測軟件的角度，分為靜態(tài)測試和動態(tài)測試。

按照功能劃分可以分為白盒測試和黑盒測試。

（1）靜態(tài)測試和動態(tài)測試

靜態(tài)測試包括代碼檢查、靜態(tài)構(gòu)造分析、代碼質(zhì)量度量。不實際

運行軟件，重要通過人工進行。

動態(tài)測試：是基本計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的I

過程。（運用測試用例去運行程序，以發(fā)現(xiàn)程序錯誤的過程）

測試用例是為測試設計的I數(shù)據(jù)。

動態(tài)測試重要包括白盒測試措施和黑盒測試措施。

白盒測試也稱構(gòu)造測試，根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查

內(nèi)部成分，以確認每種內(nèi)部操作符合設計規(guī)格規(guī)定。

白盒測試：在程序內(nèi)部進行，重要用于完畢軟件內(nèi)部操作的驗

證。重要措施有邏輯覆蓋、基本途徑測試。

黑盒測試也稱功能測試，是對軟件已經(jīng)實現(xiàn)的功能與否滿足需

求進行測試和驗證。（不考慮內(nèi)部的邏輯構(gòu)造和內(nèi)部特性，只根據(jù)程

序的需求和功能規(guī)格闡明，檢查程序的功能與否滿足功能闡明）

黑盒測試是在軟件接口處進行，完畢功能驗證。

黑盒測試：重要診斷功能不對或遺漏、界面錯誤、數(shù)據(jù)構(gòu)造或

外部數(shù)據(jù)庫訪問錯誤、性能錯誤、初始化和終止條件錯，重要用于軟

件確認測試。重要措施有等價類劃分法、邊界值分析法、錯誤推測法

等。

軟件測試過程一般按4個環(huán)節(jié)進行：

單元測試、集成測試、驗收測試（確認測試）和系統(tǒng)測試。

3.5程序的調(diào)試

注意程序測試與調(diào)試的區(qū)別：

測試是盡量多地發(fā)現(xiàn)軟件中的錯誤，軟件測試貫穿整個軟件生

命期

調(diào)試是診斷和改正程序中的錯誤，重要在開發(fā)階段進行

程序調(diào)試的基本環(huán)節(jié)：

（1）錯誤定位；

（2）修改設計和代碼，以排除錯誤；

（3）進行回歸測試，防止引進新的錯誤。

軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試重要是指通過人

的思維來分析源程序代碼和排錯，是重要的設計手段，而動態(tài)調(diào)試

是輔助靜態(tài)調(diào)試。重要調(diào)試措施有：

（1）強行排錯法；（設置斷點、程序暫停、監(jiān)視體現(xiàn)式等）

(2)回溯法；

(3)原因排除法。

第四章數(shù)據(jù)庫設計基礎

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

數(shù)據(jù)：實際上就是描述事物的符號記錄。

數(shù)據(jù)的特點：有一定的構(gòu)造，有型與值之分，如整型、實型、字

符型等。而數(shù)據(jù)時值給出了符合定型時值，如整型值15。

數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的構(gòu)造形式并寄存于統(tǒng)一的

存儲介質(zhì)內(nèi)，是多種應用數(shù)據(jù)的I集成，并可被各個應用程序共享。

數(shù)據(jù)庫寄存數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式寄存的，具有集成

與共享的特點。

數(shù)據(jù)庫管理系統(tǒng)：一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)

據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務等，是數(shù)據(jù)庫的關鍵。

數(shù)據(jù)庫管理系統(tǒng)功能：

(1)數(shù)據(jù)模式定義：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架；

(2)數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供

有效的存取措施與手段；

(3)數(shù)據(jù)操縱：為顧客使用數(shù)據(jù)庫的數(shù)據(jù)提供以便，如查詢、

插入、修改、刪除等以及簡樸的算術(shù)運算及記錄；

(4)數(shù)據(jù)的完整性、安生性定義與檢查；

(5)數(shù)據(jù)庫的并發(fā)控制與故障恢復；

(6)數(shù)據(jù)的服務：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測、分析等。

為完畢以上六個功能，數(shù)據(jù)庫管理系統(tǒng)提供如下的數(shù)據(jù)語言：

（1）數(shù)據(jù)定義語言（DDL）:負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理

存取構(gòu)建；

（2）數(shù)據(jù)操縱語言（DML）：負責數(shù)據(jù)的操縱，如查詢與增、刪、

改等；

（3）數(shù)據(jù)控制語言（DCL）:負責數(shù)據(jù)完整性、安全性的定義與

檢查以及并發(fā)控制、故障恢復等。

數(shù)據(jù)語言按其使用方式具有兩種構(gòu)造形式：交互式命令（又稱自

含型或自主型語言）宿主型語言（一般可嵌入某些宿主語言中）。

目前流行的數(shù)據(jù)庫管理系統(tǒng)都是關系數(shù)據(jù)庫系統(tǒng)，如ORACLE、

PowerBuider^SqlServer>VisualFoxpro和Access等。

數(shù)據(jù)庫管理員：對數(shù)據(jù)庫進行規(guī)劃、設計、維護、監(jiān)視等的專業(yè)

管理人員。

數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)

庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)

成的運行實體。

數(shù)據(jù)庫應用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應用軟件及應用界面三者構(gòu)

成。

文獻系統(tǒng)階段：提供了簡樸的數(shù)據(jù)共享與數(shù)據(jù)管理能力，不過它

無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。

層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提供了

有力支撐。

關系數(shù)據(jù)庫系統(tǒng)階段

數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗

余性、數(shù)據(jù)獨立性(物理獨立性與邏輯獨立性)、數(shù)據(jù)統(tǒng)一管理與控制。

數(shù)據(jù)庫系統(tǒng)的三級模式：

(1)概念模式：數(shù)據(jù)庫系統(tǒng)中全局數(shù)據(jù)邏輯構(gòu)造的描述，全體

顧客公共數(shù)據(jù)視圖；

(2)外模式：也稱子模式與顧客模式。是顧客的數(shù)據(jù)視圖，也

就是顧客所見到的數(shù)據(jù)模式；

(3)內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲構(gòu)造與

物理存取措施。

數(shù)據(jù)庫系統(tǒng)的兩級映射：

(1)概念模式到內(nèi)模式的映射；

(2)外模式到概念模式的映射。

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

數(shù)據(jù)模型的概念：是數(shù)據(jù)特性的抽象，從抽象層次上描述了系

統(tǒng)的靜態(tài)特性、動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表與操作

提供一種抽象的框架。描述了數(shù)據(jù)構(gòu)造、數(shù)據(jù)操作及數(shù)據(jù)約束。

E-R模型的基本概念

(1)實體：現(xiàn)實世界中的I事物；

(2)屬性：事物的特性；

(3)聯(lián)絡：現(xiàn)實世界中事物間的關系。實體集的關系有一對一、

一對多、多對多的聯(lián)絡。

E-R模型三個基本概念之間的聯(lián)接關系：實體是概念世界中的基

本單位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。一種實體的所

有屬性值叫元組。

E-R模型的圖示法：（1）實體集表達法；（2）屬性表法；（3）聯(lián)

絡表達法。

層次模型的基本構(gòu)造是樹形構(gòu)造，具有如下特點：

（1）每棵樹有且僅有一種無雙親結(jié)點，稱為根；