全國計算機二級《公共基礎知識》講義.doc

《全國計算機二級《公共基礎知識》講義.doc》由會員分享，可在線閱讀，更多相關《全國計算機二級《公共基礎知識》講義.doc（86頁珍藏版）》請在裝配圖網上搜索。

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