全國(guó)計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》講義.doc

《全國(guó)計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》講義.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《全國(guó)計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》講義.doc（86頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

目錄 全國(guó)二級(jí)C語(yǔ)言考試大綱 1 全國(guó)二級(jí)公共基礎(chǔ)知識(shí)考試大綱 3 公共基礎(chǔ)知識(shí)講義 4 第一講 數(shù)據(jù)結(jié)構(gòu)與算法 4 第二講 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 11 第三講 軟件工程基礎(chǔ) 18 第四講 程序設(shè)計(jì)基礎(chǔ) 25 公共基礎(chǔ)知識(shí)習(xí)題 28 數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題 28 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)習(xí)題 33 軟件工程基礎(chǔ)習(xí)題 38 程序設(shè)計(jì)基礎(chǔ)習(xí)題 41 2009年3月二級(jí)C語(yǔ)言筆試真題 43 2009年3月二級(jí)C語(yǔ)言筆試答案 54 2008年9月二級(jí)C語(yǔ)言筆試真題 55 2008年9月二級(jí)C語(yǔ)言筆試答案 64 2008年4月二級(jí)C語(yǔ)言筆試真題 65 2008年4月二級(jí)C語(yǔ)言筆試答案 73 2007年9月二級(jí)C語(yǔ)言筆試真題 74 2007年9月二級(jí)C語(yǔ)言筆試答案 86 全國(guó)二級(jí)C語(yǔ)言考試大綱 ◆ 基本要求 1.熟悉 Visual C++ 6.0 集成開發(fā)環(huán)境。 2.掌握結(jié)構(gòu)化程序設(shè)計(jì)的方法，具有良好的程序設(shè)計(jì)風(fēng)格。 3.掌握程序設(shè)計(jì)中簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)和算法并能閱讀簡(jiǎn)單的程序。 4.在 Visual C++ 6.0 集成環(huán)境下，能夠編寫簡(jiǎn)單的C程序，并具有基本的糾錯(cuò)和調(diào)試程序的能力 ◆ 考試內(nèi)容 一、C語(yǔ)言程序的結(jié)構(gòu) 1.程序的構(gòu)成，main函數(shù)和其他函數(shù)。 2.頭文件，數(shù)據(jù)說(shuō)明，函數(shù)的開始和結(jié)束標(biāo)志以及程序中的注釋。 3.源程序的書寫格式。 4.C語(yǔ)言的風(fēng)格。 二、數(shù)據(jù)類型及其運(yùn)算 1.C的數(shù)據(jù)類型（基本類型，構(gòu)造類型，指針類型，無(wú)值類型）及其定義方法。 2.C運(yùn)算符的種類、運(yùn)算優(yōu)先級(jí)和結(jié)合性。 3.不同類型數(shù)據(jù)間的轉(zhuǎn)換與運(yùn)算。 4.C表達(dá)式類型（賦值表達(dá)式，算術(shù)表達(dá)式，關(guān)系表達(dá)式，邏輯表達(dá)式，條件表達(dá)式，逗號(hào)表達(dá)式）和求值規(guī)則。 三、基本語(yǔ)句 1.表達(dá)式語(yǔ)句，空語(yǔ)句，復(fù)合語(yǔ)句。 2.輸入輸出函數(shù)的調(diào)用，正確輸入數(shù)據(jù)并正確設(shè)計(jì)輸出格式。 四、選擇結(jié)構(gòu)程序設(shè)計(jì) 1.用if語(yǔ)句實(shí)現(xiàn)選擇結(jié)構(gòu)。 2.用switch語(yǔ)句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)。 3.選擇結(jié)構(gòu)的嵌套。 五、循環(huán)結(jié)構(gòu)程序設(shè)計(jì) 1.for循環(huán)結(jié)構(gòu)。 2.while和do-while循環(huán)結(jié)構(gòu)。 3.continue語(yǔ)句和break語(yǔ)句。 4.循環(huán)的嵌套。 六、數(shù)組的定義和引用 1.一維數(shù)組和二維數(shù)組的定義、初始化和數(shù)組元素的引用。 2.字符串與字符數(shù)組。 七、函數(shù) 1.庫(kù)函數(shù)的正確調(diào)用。 2.函數(shù)的定義方法。 3.函數(shù)的類型和返回值。 4.形式參數(shù)與實(shí)在參數(shù)，參數(shù)值傳遞。 5.函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用。 6.局部變量和全局變量。 7.變量的存儲(chǔ)類別（自動(dòng)，靜態(tài)，寄存器，外部），變量的作用域和生存期。 八、編譯預(yù)處理 1.宏定義和調(diào)用（不帶參數(shù)的宏，帶參數(shù)的宏）。 2.“文件包含”處理。 九、指針 1.地址與指針變量的概念，地址運(yùn)算符與間址運(yùn)算符。 2.一維、二維數(shù)組和字符串的地址以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針變量的定義。通過(guò)指針引用以上各類型數(shù)據(jù)。 3.用指針作函數(shù)參數(shù)。 4.返回地址值的函數(shù)。 5.指針數(shù)組，指向指針的指針。 十、結(jié)構(gòu)體（即“結(jié)構(gòu)”）與共同體（即“聯(lián)合”） 1.用typedef說(shuō)明一個(gè)新類型。 2.結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義和成員的引用。 3.通過(guò)結(jié)構(gòu)體構(gòu)成鏈表，單向鏈表的建立，結(jié)點(diǎn)數(shù)據(jù)的輸出、刪除與插入。 十一、位運(yùn)算 1.位運(yùn)算符的含義和使用。 2.簡(jiǎn)單的位運(yùn)算。 十二、文件操作 只要求緩沖文件系統(tǒng)（即高級(jí)磁盤I/O系統(tǒng)），對(duì)非標(biāo)準(zhǔn)緩沖文件系統(tǒng)（即低級(jí)磁盤I/O系統(tǒng)）不要求。 1.文件類型指針（FILE類型指針）。 2.文件的打開與關(guān)閉（fopen，fclose）。 3.文件的讀寫（fputc，fgetc，fputs，fgets，fread，fwrite，fprintf，fscanf函數(shù)的應(yīng)用），文件的定位（rewind，fseek函數(shù)的應(yīng)用）。 ◆ 考試方式 1.筆試：90分鐘，滿分100分，其中含公共基礎(chǔ)知識(shí)部分的30分。 2.上機(jī)：90分鐘，滿分100分 3、上機(jī)操作包括： （1）填空。 （2）改錯(cuò)。 （3）編程。 全國(guó)二級(jí)公共基礎(chǔ)知識(shí)考試大綱 ◆ 基本要求 　　1.掌握算法的基本概念。 　　2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 　　3.掌握基本排序和查找算法。 　　4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。 　　5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。 　　6.掌握數(shù)據(jù)庫(kù)的基本知識(shí)，了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。 ◆ 考試內(nèi)容 一、 基本數(shù)據(jù)結(jié)構(gòu)與算法 1. 算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。 2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3. 線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。 4. 棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 6. 樹的基本概念；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 二、 程序設(shè)計(jì)基礎(chǔ) 1. 程序設(shè)計(jì)方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計(jì)。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。 三、 軟件工程基礎(chǔ) 1. 軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。 2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書。 3. 結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。 4. 軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。 5. 程序的調(diào)試，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。 四、 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 1. 數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。 2. 數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3. 關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。 4. 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。 ◆ 考試方式 公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題共三十分 公共基礎(chǔ)知識(shí)講義 第一講 數(shù)據(jù)結(jié)構(gòu)與算法 1.1 算法 1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述。 *：算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)。 2、算法的基本特征 （1）可行性。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。 （2）確定性。每一條指令的含義明確，無(wú)二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。 （3）有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。 （4）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無(wú)法執(zhí)行或執(zhí)行有錯(cuò)。一般說(shuō)來(lái)，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效。 *：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。 （1）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。 （2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 （2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。 1）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。 2）鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 3）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。 *：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。 （3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 3、數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。 4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 *：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。 （2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 *：常見(jiàn)的非線性結(jié)構(gòu)有樹、二叉樹和圖等。 1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu) 1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度。線性表可以為空表。 *：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順序和鏈?zhǔn)健? 2、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 *：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。 3、順序表的插入、刪除運(yùn)算 （1）順序表的插入運(yùn)算：在一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增加了1。 *：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。 （2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長(zhǎng)度就減小了1。 *：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n-1）/2個(gè)元素。插入、刪除運(yùn)算不方便。 1.4 棧和隊(duì)列 1、棧及其基本運(yùn)算 棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。 棧具有記憶作用。 棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。 棧的存儲(chǔ)方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！? 2、隊(duì)列及其基本運(yùn)算 隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。 隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。 隊(duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。 循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。 *：循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front。 1.5 線性鏈表 1、線性表順序存儲(chǔ)的缺點(diǎn)：（1）插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素；（2）線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充；（3）線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。 2、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所示： 線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。 在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示： 3、線性鏈表的基本運(yùn)算 （1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。 *：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢”現(xiàn)象。 （2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。 *：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。 （3）將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。 （4）將一個(gè)線性鏈表按要求進(jìn)行分解。 （5）逆轉(zhuǎn)線性鏈表。 （6）復(fù)制線性鏈表。 （7）線性鏈表的排序。 （8）線性鏈表的查找。 *：線性鏈表不能隨機(jī)存取。 4、循環(huán)鏈表及其基本運(yùn)算 在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。 與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1）在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)；2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。 下圖a是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表： 循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面：一是在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)；二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。 *：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個(gè)表頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相同。但它可以從任一結(jié)點(diǎn)出發(fā)來(lái)訪問(wèn)表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。 1.6 樹與二叉樹 1、樹的基本概念 樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。 在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。 2、二叉樹及其基本性質(zhì) （1）什么是二叉樹 二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。 *：根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹）或2（有2棵子樹）。 （2）二叉樹的基本性質(zhì) 性質(zhì)1 在二叉樹的第k層上，最多有 個(gè)結(jié)點(diǎn)。 性質(zhì)2 深度為m的二叉樹最多有個(gè) 個(gè)結(jié)點(diǎn)。 性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個(gè)。 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 ，其中 表示取 的整數(shù)部分。 3、滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 *：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。 下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹： 完全二叉樹還具有如下兩個(gè)特性： 性質(zhì)5 具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為 。 性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1，2，…，n）的結(jié)點(diǎn)有以下結(jié)論： ①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。 ②若2k≤n，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。 ③若2k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。 4、二叉樹的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 與線性鏈表類似，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），因此，用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。 *：一般二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹來(lái)說(shuō)，可以按層序進(jìn)行順序存儲(chǔ)。 5、二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問(wèn)二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三種： （1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。 （2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹。 （3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。 1.7 查找技術(shù) 查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 查找結(jié)果：（查找成功：找到；查找不成功：沒(méi)找到。） 平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)。 1、順序查找 基本思想：從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒(méi)有要找的元素，查找不成功。 在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。 順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O（n）。 下列兩種情況下只能采用順序查找： 1）如果線性表是無(wú)序表（即表中的元素是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。 2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。 2、二分法查找 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。 查找過(guò)程： 1）若中間項(xiàng)（中間項(xiàng)mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說(shuō)明已查到； 2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找； 3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。 特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。 *：二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列。對(duì)于無(wú)序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O（log2n）。 1.8 排序技術(shù) 排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列，即是將無(wú)序的記錄序列調(diào)整為有序記錄序列的一種操作。 1、交換類排序法（方法：冒泡排序，快速排序）。 2、插入類排序法（方法：簡(jiǎn)單插入排序，希爾排序）。 3、選擇類排序法（方法：簡(jiǎn)單選擇排序，堆排序）。 總結(jié)：各種排序法比較： 第二講 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 2.1 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 1、數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)管理系統(tǒng) （1）數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。 數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如整型、實(shí)型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。 （2）數(shù)據(jù)庫(kù)（DB）：是數(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ù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)，亦即是數(shù)據(jù)庫(kù)集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一的構(gòu)造和存儲(chǔ)，而使它們可被不同應(yīng)用程序所使用。 （3）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。 數(shù)據(jù)庫(kù)管理系統(tǒng)功能： 1）數(shù)據(jù)模式定義。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫(kù)構(gòu)建模式，也就是為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架。 2）數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫(kù)管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段。 3）數(shù)據(jù)操縱。數(shù)據(jù)庫(kù)管理系統(tǒng)為用戶使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)提供方便，它一般提供如查詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)的能力，而且還可以與某些過(guò)程性語(yǔ)言結(jié)合，使其具有強(qiáng)大的過(guò)程性操作能力。 4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有內(nèi)在語(yǔ)義上的關(guān)聯(lián)性與一致性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫(kù)中數(shù)據(jù)正確的必要條件，因此必須經(jīng)常檢查以維護(hù)數(shù)據(jù)正確。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會(huì)引發(fā)數(shù)據(jù)的非法使用，因此必須要對(duì)數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時(shí)做檢查，這就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性與安全性的維護(hù)是數(shù)據(jù)庫(kù)系統(tǒng)的基本功能。 5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫(kù)是一個(gè)集成、共享的數(shù)據(jù)集合體，它能為多個(gè)應(yīng)用程序服務(wù)，所以就存在著多個(gè)應(yīng)用程序?qū)?shù)據(jù)庫(kù)的并發(fā)操作。在并發(fā)操作中如果不加控制和管理，多個(gè)應(yīng)用程序間就會(huì)相互干擾，從而對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成破壞。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)必須對(duì)多個(gè)應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破壞，這就是數(shù)據(jù)庫(kù)的并發(fā)控制。數(shù)據(jù)庫(kù)中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫(kù)管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢復(fù)，這就是數(shù)據(jù)庫(kù)的故障恢復(fù)。 6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫(kù)管理系統(tǒng)提供對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。 （4）數(shù)據(jù)庫(kù)管理員（DBA）：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專業(yè)管理人員。 （5）數(shù)據(jù)庫(kù)系統(tǒng)（DBS）：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)管理員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。 （6）數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。 *：數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。 2、數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展 數(shù)據(jù)庫(kù)管理發(fā)展至今已經(jīng)歷了三個(gè)階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。 下表是數(shù)據(jù)管理三個(gè)階段的比較： 人工管理階段 文件系統(tǒng)階段 數(shù)據(jù)庫(kù)系統(tǒng)階段 背 景 應(yīng)用背景 科學(xué)計(jì)算 科學(xué)計(jì)算、管理 大規(guī)模管理 硬件背景 無(wú)直接存取存儲(chǔ)設(shè)備 磁盤、磁鼓 大容量磁備盤 軟件背景 沒(méi)有操作系統(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ì)象 某一應(yīng)用程序 某一應(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)用程序自己控制 由數(shù)據(jù)庫(kù)管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)能力 3、數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn) （1）數(shù)據(jù)的高集成性。 （2）數(shù)據(jù)的高共享性與低冗余性。 *：數(shù)據(jù)庫(kù)系統(tǒng)可以減少數(shù)據(jù)冗余，但無(wú)法避免一切冗余。 （3）數(shù)據(jù)獨(dú)立性：數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說(shuō)，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。 數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性兩級(jí)。 1）物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲(chǔ)結(jié)構(gòu)，存取方式等）的改變，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化。 2）邏輯獨(dú)立性：數(shù)據(jù)庫(kù)總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。 （4）數(shù)據(jù)統(tǒng)一管理與控制。 數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個(gè)方面： 1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫(kù)中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。 2）數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫(kù)訪問(wèn)者以防止非法訪問(wèn)。 3）并發(fā)控制：控制多個(gè)應(yīng)用的并發(fā)訪問(wèn)所產(chǎn)生的相互干擾以保證其正確性。 4、數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部結(jié)構(gòu)體系 （1）數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式： 1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)視圖。 2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù)模式，它由概念模式推導(dǎo)而出。 3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級(jí)上，它還未深入到設(shè)備級(jí)上（如磁盤及磁盤操作）。內(nèi)模式對(duì)一般用戶是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能。 （2）數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射： 1）概念模式/內(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ú)立性。 2）外模式/概念模式的映射：實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式發(fā)生變化時(shí)，通過(guò)修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。 2.2 數(shù)據(jù)模型 1、數(shù)據(jù)模型 （1）數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。 （2）數(shù)據(jù)模型所描述的內(nèi)容有三個(gè)部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。 1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是所研究的對(duì)象類型的集合，包括與數(shù)據(jù)類型、內(nèi)容、性質(zhì)有關(guān)的對(duì)象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對(duì)象。它用于描述系統(tǒng)的靜態(tài)特性。 2）數(shù)據(jù)操作：數(shù)據(jù)操作是對(duì)數(shù)據(jù)庫(kù)中各種對(duì)象（型）的實(shí)例（值）允許執(zhí)行的操作的集合，包括操作的含義、符號(hào)、操作規(guī)則及實(shí)現(xiàn)操作的語(yǔ)句等。它用于描述系統(tǒng)的動(dòng)態(tài)特性。 3）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號(hào)數(shù)據(jù)模型的數(shù)據(jù)庫(kù)狀態(tài)及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。 （3）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類： 1）概念數(shù)據(jù)模型：簡(jiǎn)稱概念模型，是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫。概念模型主要有：E-R模型(實(shí)體聯(lián)系模型)、擴(kuò)充的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。 2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫(kù)系統(tǒng)的模型，該模型著重于在數(shù)據(jù)庫(kù)系統(tǒng)一級(jí)的實(shí)現(xiàn)。邏輯數(shù)據(jù)模型主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)ο竽Ｐ偷取? 3）物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計(jì)算機(jī)物理表示的模型，此模型給出了數(shù)據(jù)模型在計(jì)算機(jī)上物理結(jié)構(gòu)的表示。 2、實(shí)體聯(lián)系模型及E-R圖 （1）E-R模型的基本概念： 1）實(shí)體：現(xiàn)實(shí)世界中的事物。 2）屬性：事物的特性。 3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。 E-R模型三個(gè)基本概念之間的聯(lián)接關(guān)系：1）實(shí)體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）實(shí)體（集）與聯(lián)系。 *：E-R模型的基本成分是實(shí)體和聯(lián)系。 （2）E-R模型的圖示法： 1）實(shí)體集：用矩形表示。 2）屬性：用橢圓形表示。 3）聯(lián)系：用菱形表示。 4）實(shí)體集與屬性間的聯(lián)接關(guān)系：用無(wú)向線段表示。 5）實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系：用無(wú)向線段表示。 （3）數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。 1）層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn)：A、每棵樹有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱為根；B、樹中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。 2）網(wǎng)狀模型是層次模型的一個(gè)特例，從圖論上看，網(wǎng)狀模型是一個(gè)不加任何條件限制的無(wú)向圖。 3）關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè)關(guān)系。 二維表的表框架由n個(gè)命名的屬性組成，n稱為屬性元數(shù)。每個(gè)屬性有一個(gè)取值范圍稱為值域。表框架對(duì)應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實(shí)際上，一個(gè)元組是由n個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的 投影值。 學(xué)號(hào) 姓名 性別 出生年月 班級(jí) 籍貫 2007102 張潔然 男 07-07-88 07動(dòng)畫1班 天津 2007203 李一明 男 05-01-87 07播音5班 廣西南寧 2007305 王 麗 女 04-09-88 07管理4班 遼寧沈陽(yáng) 2007406 劉 宏 男 10-11-88 07新聞3班 江蘇南京 *：同一個(gè)關(guān)系模型的任兩個(gè)元組值不能完全相同。 主碼：或稱為關(guān)鍵字、主鍵，簡(jiǎn)稱碼、鍵，表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的，稱為關(guān)系的主碼或關(guān)鍵字。例如，學(xué)生的學(xué)號(hào)。主碼屬性不能取空值。 外部關(guān)鍵字：或稱為外鍵，在一個(gè)關(guān)系中含有與另一個(gè)關(guān)系的關(guān)鍵字相對(duì)應(yīng)的屬性組稱為該關(guān)系的外部關(guān)鍵字。外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?duì)應(yīng)的關(guān)鍵字值。例如，在學(xué)生表中含有的所屬班級(jí)名字，是班級(jí)表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。 （4）關(guān)系中的數(shù)據(jù)約束： 1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯一決定元組的，如為空值則其唯一性就成為不可能的了。 2）參照完整性約束：關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，即在關(guān)系中的外鍵要么是所關(guān)聯(lián)關(guān)系中實(shí)際存在的元組，要么為空值。 3）用戶定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語(yǔ)義要求。例如某個(gè)屬性的取值范圍在0—100之間等。 3、從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型 數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)）中的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實(shí)體與聯(lián)系都可以表示成關(guān)系，E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。 2.3 關(guān)系代數(shù) 1、關(guān)系的數(shù)據(jù)結(jié)構(gòu) 關(guān)系是由若干個(gè)不同的元組所組成，因此關(guān)系可視為元組的集合。n元關(guān)系是一個(gè)n元有序組的集合。 關(guān)系模型的基本運(yùn)算：1）插入；2）刪除；3)修改；4）查詢（包括投影、選擇、笛卡爾積運(yùn)算）。 2、關(guān)系操縱 關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四種操作。 3、集合運(yùn)算及選擇、投影、連接運(yùn)算 （1）并（∪）：關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合。 （2）差（－）：關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合。 （3）交（∩）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S的元組構(gòu)成的集合。 （4）廣義笛卡爾積（）：設(shè)關(guān)系R和S的屬性個(gè)數(shù)分別為n、m，則R和S的廣義笛卡爾 積是一個(gè)有（n+m）列的元組的集合。每個(gè)元組的前n列來(lái)自R的一個(gè)元組，后m列來(lái)自S 的一個(gè)元組，記為RS。 *：根據(jù)笛卡爾積的定義：有n元關(guān)系R及m元關(guān)系S，它們分別有p、q個(gè)元組，則關(guān)系R與S經(jīng)笛卡爾積記為RS，該關(guān)系是一個(gè)n+m元關(guān)系，元組個(gè)數(shù)是pq，由R與S的有序組組合而成。 例：有兩個(gè)關(guān)系R和S，分別進(jìn)行并、差、交和廣義笛卡爾積運(yùn)算。 （5）在關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)中，基本的關(guān)系運(yùn)算有選擇、投影與聯(lián)接三種操作： 1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那些符合指定條件的記錄挑出來(lái)。 2）投影：投影是從所有字段中選取一部分字段及其值進(jìn)行操作，它是一種縱向操作。 3）聯(lián)接：聯(lián)接將兩個(gè)關(guān)系模式拼接成一個(gè)更寬的關(guān)系模式，生成的新關(guān)系中包含滿足聯(lián)接條件的元組。 2.4 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟 （1）數(shù)據(jù)庫(kù)設(shè)計(jì)階段包括：需求分析、概念分析、邏輯設(shè)計(jì)、物理設(shè)計(jì)。 （2）數(shù)據(jù)庫(kù)設(shè)計(jì)的每個(gè)階段都有各自的任務(wù)： 1）需求分析階段：這是數(shù)據(jù)庫(kù)設(shè)計(jì)的第一個(gè)階段，任務(wù)主要是收集和分析數(shù)據(jù)，這一階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計(jì)概念結(jié)構(gòu)的基礎(chǔ)。 2）概念設(shè)計(jì)階段：分析數(shù)據(jù)間內(nèi)在語(yǔ)義關(guān)聯(lián)，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)的抽象模型，即形成E-R圖。 *：數(shù)據(jù)庫(kù)概念設(shè)計(jì)的過(guò)程包括選擇局部應(yīng)用、視圖設(shè)計(jì)和視圖集成。 3）邏輯設(shè)計(jì)階段：將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。 4）物理設(shè)計(jì)階段：對(duì)數(shù)據(jù)庫(kù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫(kù)訪問(wèn)速度及有效利用存儲(chǔ)空間。 第三講 軟件工程基礎(chǔ) 3.1 軟件工程基本概念 1、軟件的相關(guān)概念 計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性；2）軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程；3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題；4）軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問(wèn)題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會(huì)因素。 2、軟件危機(jī)與軟件工程 軟件工程源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。具體的說(shuō)，在軟件開發(fā)和維護(hù)過(guò)程中，軟件危機(jī)主要表現(xiàn)在： 1）軟件需求的增長(zhǎng)得不到滿足。用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生。 2）軟件開發(fā)成本和進(jìn)度無(wú)法控制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過(guò)規(guī)定日期的情況經(jīng)常發(fā)生。 3）軟件質(zhì)量難以保證。 4）軟件不可維護(hù)或維護(hù)程度非常低。 5）軟件的成本不斷提高。 6）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。 總之，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。 軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)： 1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。 2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。 軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過(guò)程，它包括3個(gè)要素：方法、工具和過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過(guò)程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。 軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。 3、軟件生命周期 軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。 軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段： 1）軟件定義階段：包括制定計(jì)劃和需求分析。 制定計(jì)劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計(jì)劃。 需求分析：對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。 2）軟件開發(fā)階段： 軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。 軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。 軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。 3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改。 *：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。 4、軟件工程的目標(biāo)和與原則 （1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、 可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 （2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開發(fā)，及時(shí)交付使用。 （3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。 1)抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化的辦法控制軟件開發(fā)過(guò)程的復(fù)雜性。 2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來(lái)，使模塊接口盡量簡(jiǎn)單。 3）模塊化：模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。 4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性。 5）確定性：軟件開發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定、無(wú)歧義且規(guī)范的。 6）一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說(shuō)明與系統(tǒng)行為應(yīng)保持一致。 7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。 8）可驗(yàn)證性：應(yīng)遵循容易檢查、測(cè)評(píng)、評(píng)審的原則，以確保系統(tǒng)的正確性。 5、軟件開發(fā)工具與軟件開發(fā)環(huán)境 (1)軟件開發(fā)工具 軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項(xiàng)工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境。同時(shí)，軟件開發(fā)方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難以有效的實(shí)施。 （2）軟件開發(fā)環(huán)境 軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過(guò)程的軟件工具集合。 計(jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開發(fā)機(jī)器和一個(gè)存放開發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。 3.2 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。 1、需求分析 需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）面向?qū)ο蟮姆治龇椒ā? *：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問(wèn)題。 *：需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說(shuō)明書和需求評(píng)審四個(gè)步驟進(jìn)行。 2、結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。 結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判定表。 數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過(guò)程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。 上圖是數(shù)據(jù)流圖的基本圖形元素： 加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。 數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。 存儲(chǔ)文件（數(shù)據(jù)源）：表示處理過(guò)程中存放各種數(shù)據(jù)的文件。 源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。 畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。 下圖是一個(gè)數(shù)據(jù)流圖的示例： 數(shù)據(jù)字典：對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。 *：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。 *：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。 3、軟件需求規(guī)格說(shuō)明書（SRS） 軟件需求規(guī)格說(shuō)明書是需求分析階段的最后成果，通過(guò)建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說(shuō)明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。 3.3 結(jié)構(gòu)化設(shè)計(jì)方法 1、軟件設(shè)計(jì)的基礎(chǔ) *：需求分析主要解決“做什么”的問(wèn)題，而軟件設(shè)計(jì)主要解決“怎么做”的問(wèn)題。 從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。 結(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ò)程性描述。 從工程角度來(lái)看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。 概要設(shè)計(jì)：又稱結(jié)構(gòu)設(shè)計(jì)，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式。 詳細(xì)設(shè)計(jì)：確定每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 軟件設(shè)計(jì)的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性。 1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。 2）模塊化。解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐步把軟件系統(tǒng)劃分成一個(gè)個(gè)較小的、相對(duì)獨(dú)立但又不相互關(guān)聯(lián)的模塊的過(guò)程。 3）信息隱蔽。每個(gè)模塊的實(shí)施細(xì)節(jié)對(duì)于其他模塊來(lái)說(shuō)是隱蔽的。 4）模塊獨(dú)立性。軟件系統(tǒng)中每個(gè)模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)中其他的模塊的接口是簡(jiǎn)單的。 *：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。 模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個(gè)定性指標(biāo)。 內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。 *：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。 耦合性：是模塊間互相連接的緊密程度的度量。 *：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。 一個(gè)設(shè)計(jì)良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。 在結(jié)構(gòu)化程序設(shè)計(jì)中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。 2、總體設(shè)計(jì)（概要設(shè)計(jì)）和詳細(xì)設(shè)計(jì) （1）總體設(shè)計(jì)（概要設(shè)計(jì)） 軟件概要設(shè)計(jì)的基本任務(wù)是：1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；3）編寫概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審。 常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符： 模塊用一個(gè)矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過(guò)程中來(lái)回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。 經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表示形式如下圖： 它們的含義分別是： 傳入模塊：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級(jí)模塊。 傳出模塊：從上級(jí)模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。 變換模塊：從上級(jí)模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊。 協(xié)調(diào)模塊：對(duì)所有下屬模塊進(jìn)行協(xié)調(diào)和管理的模塊。 程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語(yǔ)列舉如下： 深度：表示控制的層數(shù)。 上級(jí)模塊、從屬模塊：上、下兩層模塊a和b，且有a調(diào)用b，則a是上級(jí)模塊，b是從屬模塊。 寬度：整體控制跨度（最大模塊數(shù)的層）的表示。 扇入：調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)。 扇出：一個(gè)模塊直接調(diào)用的其他模塊數(shù)。 原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊。 面向數(shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。 數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。 A、變換型：變換型數(shù)據(jù)處理問(wèn)題的工作過(guò)程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。 B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問(wèn)題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)，選擇分派一個(gè)適當(dāng)?shù)奶幚韱卧缓蠼o出結(jié)果。 （2）詳細(xì)設(shè)計(jì) 詳細(xì)設(shè)計(jì)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。 *：詳細(xì)設(shè)計(jì)的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。 常用的過(guò)程設(shè)計(jì)（即詳細(xì)設(shè)計(jì)）工具有以下幾種： 圖形工具：程序流程圖、N-S（方盒圖）、PAD（問(wèn)題分析圖）和HIPO（層次圖+輸入/處理/輸出圖）。 表格工具：判定表。 語(yǔ)言工具：PDL（偽碼） 3.4 軟件測(cè)試 1、軟件測(cè)試定義：使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。 *：軟件測(cè)試的目的：盡可能地多發(fā)現(xiàn)程序中的錯(cuò)誤，不能也不可能證明程序沒(méi)有錯(cuò)誤。軟件測(cè)試的關(guān)鍵是設(shè)計(jì)測(cè)試用例，一個(gè)好的測(cè)試用例能找到迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤。 2、軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試。 靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。 動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，主要包括白盒測(cè)試方法和黑盒測(cè)試方法。 （1）白盒測(cè)試 白盒測(cè)試方法也稱為結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過(guò)程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。 白盒測(cè)試的基本原則：保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次；保證所測(cè)模塊所有判斷的每一分支至少執(zhí)行一次；保證所測(cè)模塊每一循環(huán)都在邊界條件和一般條件