全國計算機(jī)二級之公共基礎(chǔ)

1、第一章數(shù)據(jù)結(jié)構(gòu)與算法算法定義：指階梯方案的準(zhǔn)確而完整的描述（算法*程序）特征：可行性，在設(shè)計一個算法時，必須考慮它的可行性。 確定性，算法中的每個步驟必須是明確定義的，不允許 模棱兩可。 有窮性，算法必須在有限的時間內(nèi)做完，必須在執(zhí)行有 限個步驟之后終止。 足夠的情報，是指算法要有一定的輸入數(shù)據(jù)和必須要有 輸出結(jié)果基本要素： 對數(shù)據(jù)對象的運(yùn)算和操作：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 算法的控制結(jié)構(gòu)：算法中各操作之間的執(zhí)行順序描述算法的工具：傳統(tǒng)流程圖、ns結(jié)構(gòu)化流程圖、算法描述語言等一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成時間復(fù)雜度：是指執(zhí)行算法所需要的計算工作量，可以用算

2、法所執(zhí)行的基本運(yùn)算次數(shù)度量空間復(fù)雜度：是指執(zhí)行算法所需要的內(nèi)存空間。包括算法程序、 輸入的初始數(shù)據(jù)以及算法所執(zhí)行過程需要的額外空間。時間復(fù)雜度和空間復(fù)雜度相互獨(dú)立的丄eax x算法"本“也1 |j?;叫時間刺*和空間1 麗rmha” arnhnr數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)：需要處理的數(shù)據(jù)元素的集合，一般來說，這些數(shù)據(jù)元素， 具有某個共同特征。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中個的個體。有時一個數(shù)據(jù)元素可有若干數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位結(jié)構(gòu)：是集合中個數(shù)據(jù)元素之間存在的某種關(guān)系（聯(lián)系）數(shù)據(jù)結(jié)構(gòu)：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合分類：邏輯結(jié)構(gòu)：（1）線性結(jié)構(gòu)：線性表、棧、隊列；非線

3、性結(jié)構(gòu)：樹、圖 存儲結(jié)構(gòu)：（1）順序存儲；鏈?zhǔn)酱鎯?運(yùn)算：插入；刪除；查找；排序邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)：有且只有一個根結(jié)點(diǎn)，它無前件 每一個節(jié)點(diǎn)最多有一個前件，也最多只有一個后件例如：春t夏t秋t冬：春即為根節(jié)點(diǎn)，秋即為夏的后 件，春為夏的前件非線性結(jié)構(gòu)：不滿足以上兩個條件的數(shù)據(jù)結(jié)構(gòu)存儲結(jié)構(gòu)：是數(shù)據(jù)邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放方式順序存儲結(jié)構(gòu)：主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯相 鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里鏈?zhǔn)酱鎯Y(jié)構(gòu)：每一個節(jié)點(diǎn)至少包含一個指針域，用指針的指向來體現(xiàn)數(shù)據(jù)元素之間在邏輯上的聯(lián)系12 3 4順序存儲結(jié)構(gòu)12 3 4鏈?zhǔn)酱鎯Y(jié)構(gòu)132

4、4特點(diǎn)：一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)不同的存儲結(jié)構(gòu)其數(shù)據(jù)處理的效率不同線性表及其順序存儲結(jié)構(gòu)線性表：n ( n>0 )個數(shù)據(jù)構(gòu)成的有限序列，表中除第一個元素外 的每個元素，有且只有一個前件，除最后一個元素外，有且只有 一個后件。(線性結(jié)構(gòu)習(xí)慣稱為線性表)例如，春>夏-秋-冬；英 文字母表；地理學(xué)中的四向；表格線性表的順序存儲結(jié)構(gòu)：通常，線性表可以用順序存儲和鏈?zhǔn)酱?儲，但一般使用順序存儲結(jié)構(gòu)。線性表的順序存儲又叫順序表。特點(diǎn)：線性表中所有元素所占的存儲空間是連續(xù)的 線性表中數(shù)據(jù)元素所在的存儲空間中是按邏輯順序依次存放的 可以隨機(jī)訪問數(shù)據(jù)元素 做插入、刪除時需移動大量的元素，因此線

5、性表不便于插入和刪除元素線性表箔構(gòu)牙時力cfmfz洛線性表及其順序存儲結(jié)構(gòu)又棧頂棧和隊列3棧：是限定在一 2除的線性表1端進(jìn)行插入和刪棧底特點(diǎn)：棧是只能在棧頂進(jìn)行插入和刪除 棧的修改原則是“先進(jìn)后岀”或“后進(jìn)先岀” 棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化(1展底指針bottom ( 2展頂指針top ( 3 )入棧 (4棧滿(5 )出棧43top 21 bottom西瓜蘋果棧頂棧底 棧具有記憶功能 棧支持子程序的調(diào)用枝的悸改3測是先送后ar £ 后進(jìn)先ar特點(diǎn)g悅田itt不變.棧中元素的交化幣動歩飆«uwr記也磴怪支獰子程厚的調(diào)用長晦在一*2行!入如金帕誡性寰定義

6、隊列：是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。原則是：先進(jìn)先出（或后進(jìn)后出） 隊頭指針front54321乎賽西瓜rearfront 隊尾指針rear 入隊 出隊特點(diǎn)：隊列只允許在隊尾進(jìn)行插入，而在對頭進(jìn)行刪除 隊列的修改原則是“先進(jìn)先出”或“后進(jìn)后出” 隊列中的元素隨隊頭指針和隊尾指針的變化而動態(tài)變化循環(huán)隊列：將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。 rear < front ,貝u s = rear-front rear=front ,貝ij s二容量+rearfront rear > front ,則s = 1或0（ s = 1是隊列中元

7、素已滿元素個數(shù)等于容量，s二0時，元素全部出隊）隊列原則©e8ht 雷的原則 餾6岀 /f lj待原陽eg廳而左對疋行夠走峽tr « 爲(wèi)遲爲(wèi)土定義允許&tm廳a .靜"tta行他&住« :先isw歲（同證£出）rear > front c$«fnr.from t«wb*rear-front計it元*fmf < frontrmfsfrontf«lks«0循環(huán)隊列線性鏈表線性表可以采用順序存儲和鏈?zhǔn)酱鎯樞虮恚壕€性表的順序存儲線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：各數(shù)據(jù)結(jié)點(diǎn)的存儲空間

8、可以不連續(xù) 各數(shù)據(jù)元素的存儲順序與邏輯順序可以不一致 線性表的鏈?zhǔn)酱鎯臻g所占存儲空間大于順序存儲結(jié)構(gòu)（由于每個結(jié)點(diǎn)之間都有一個指針域） 查找結(jié)點(diǎn)時鏈?zhǔn)酱鎯σ软樞虼鎯βㄒ驗椴檎业臅r候還需要看指針的指向，而順序存儲結(jié)構(gòu)一目了然） 鏈?zhǔn)酱鎯Σ迦雱h除元素比順序存儲要靈活（在線性鏈表中進(jìn)行插入和刪除，不需要移動鏈表中的元素）線性表：線性表順序存儲結(jié)構(gòu) 線性表鏈?zhǔn)酱鎯Y(jié)構(gòu) 雙向鏈表 循環(huán)鏈表線性鏈表換序存?zhèn)?幀序表各數(shù)曙結(jié)點(diǎn)的存借空間可以不連續(xù)定義各數(shù)據(jù)元素的存?zhèn)鶐蚺c邏輯換序可以不一董特點(diǎn)線性表的旳t存儲空間所占曲空間大于頓序存儲結(jié)構(gòu)查紹點(diǎn)時占曲晏比額序存儲慢查找技術(shù)順序查找：從第一個元素開始，

9、逐個將線性表中的元素與被查找 元素進(jìn)行比較，如果相等則查找成功。對于長度為n的線性表， 平均要進(jìn)行n/2次比較，在最壞情況下要進(jìn)行n次查找順序查找適用于無序表和線性鏈表（不管是有序還是無序）二分查找：適用于順序存儲的有序表，對長度為n的線性表，在 最壞的情況下進(jìn)行l(wèi)ogn次比較順序查找從始按顧序匹配査戔適用于無打（不置有序還是無序）查找技術(shù)二分查找適用于m曲有序套排序技術(shù)排序平均時間 最壞情況交換類冒泡排序n(n-1)/2n(n-1)/2快速排序n(n-1)/2n(n-1)/2插入類插入排序n(n-1)/2n(n-1)/2希爾排序nl og2nn1 5選擇類選擇排序n (n-1)/2n(n-1

10、)/2堆排序nlog2nnlog2n快速排序：基本思想：在要排序的序列找一個數(shù)作為基準(zhǔn)數(shù)（通常為第一 個） 通過交換將這個序列中所有比基準(zhǔn)數(shù)大的數(shù)放在右 邊，比基準(zhǔn)數(shù)小的放在左邊 以基準(zhǔn)數(shù)作為分割線分為兩個子表，對兩個子表重復(fù)上述步驟包排序交換類e找yr作為快速排序片m e交換.離比ix大的放右邊.比致j曲放左邊以基換作為分割線分為兩個子表扌非序插入類7 z序i序選擇類彌排序| m序第二章程序設(shè)計基礎(chǔ)程序設(shè)計風(fēng)格程序設(shè)計的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”應(yīng)當(dāng)注重和考慮下述一些因素： 源程序文檔化 數(shù)據(jù)說明 語句的結(jié)構(gòu) 輸入和輸出結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為： 自頂向

11、下：程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。（即總體-細(xì)節(jié)；全局-局部） 逐步求精：對于復(fù)雜的問題，應(yīng)設(shè)計一些子目標(biāo)作過渡，逐步細(xì)化 模塊化：一個復(fù)雜問題，肯定是由若干個稍簡單的問題構(gòu) 成。模塊化是把程序要解決的總目標(biāo)分解成分目標(biāo)，再進(jìn)一步分 解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊 限制使用goto語句基本結(jié)構(gòu)：順序結(jié)構(gòu)：一種簡單的程序設(shè)計，即按照程序語句 的自然順序，一條語句一條語句地執(zhí)行程序，它是 最基本、最常用的結(jié)構(gòu) 選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選 擇結(jié)構(gòu)，可根據(jù)條件

12、，判斷應(yīng)該選擇哪一條分支來 執(zhí)行相應(yīng)的語句序列 重復(fù)結(jié)構(gòu)：又稱為循環(huán)結(jié)構(gòu)，可根據(jù)是否需要重復(fù)執(zhí) 行某一相同或類似的程序段面向?qū)ο蟮某绦蛟O(shè)計（如java ）面向?qū)ο蟮姆椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實生活中常用的思維來認(rèn)識、理解和描述 客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠反映問題域。也就是說，系統(tǒng)中的對象及對象之間的關(guān)系能夠如實地反映問題域中有的事物及其關(guān)系 面向?qū)ο蟮闹饕獌?yōu)點(diǎn)：與人類習(xí)慣的思維方法一致穩(wěn)定性好 可重用性好 易于開發(fā)大型軟件產(chǎn)品 可維護(hù)性好對象是面對對象方法中最基本的概念，可以用來表示客觀世界的 任何實體，對象是實體的抽象。面對對象的程序設(shè)計方法中的

13、對 象是系統(tǒng)中用來客觀描述事物的一個實體，是構(gòu)成系統(tǒng)的一個基 本單位，由一組表示靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 對象是屬性和方法的封裝體。類比“找對象”，對對象的要求從以下兩個角度出發(fā)：(1 )外表：身高，胖瘦等屬性(2 )內(nèi)在：責(zé)任心、愛心等操作屬性：即對象所包含的信息，它在設(shè)計對象時確定，一般只能通 過執(zhí)行對象的操作來改變。操作：描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。操作是 對象的動態(tài)屬性。一個對象由對象名、屬性和操作三部分組成對象的基本特點(diǎn)：標(biāo)識唯一性：指對象是可區(qū)分的，并且由對 象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū) 分 分類性：指可以將具有相同屬性的操作的對象 抽象成

14、類多態(tài)性：指同一個操作可以是不同對象的行為 封裝性：從外面看只能看到對象的外部特性， 即只需知道數(shù)據(jù)的取值范圍和就可以對該數(shù) 據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié) 構(gòu)以及實現(xiàn)操作的算法。對象的內(nèi)部，即處 理能力的實行和內(nèi)部狀態(tài)，對外是不可見的。 從外面不能直接使用對象的處理能力，也不 能直接修改其內(nèi)部狀態(tài)（簡而言之，就是從 外面看只能看到對象的外部特性）信息隱蔽是通過對象的封裝性來實現(xiàn)的 模塊獨(dú)立性好：對象是面對對象的軟件的基本模塊，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的 操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為 中心的，操作圍繞對其數(shù)據(jù)所需做的處理來 設(shè)置，沒有無關(guān)的操作。從模塊的獨(dú)立性考 慮，對

15、象內(nèi)部各種元素彼此結(jié)合得很緊密， 內(nèi)聚性強(qiáng)（簡而言之，對象作為基本模塊， 相互之間沒有很多聯(lián)系的）類：指具有共同屬性、共同方法的對象的集合消息：一個實例與另一個實例之間傳遞的信息 繼承：指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們 多態(tài)性：指同樣的消息被不同的對象接受時可導(dǎo)致完全不同行動的現(xiàn)象在面對對象方法中，一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送消息類的繼承性是類之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性用序設(shè)計風(fēng)格王”審tx<tmmteeathmimbir結(jié)悔化程序設(shè)計htflgooc*swkttftc owex，fawwmai林程序設(shè)計基礎(chǔ)a»f從蘇珂

16、幟*入口/it岀的fi序烏于幵面向?qū)κ车臋?quán)序設(shè)計bwsmw-個*9s-fi性 totnas&r«-«w»tt*w« ; >e«aimm i4>t2ob<ms第三章軟件工程基礎(chǔ)軟件工程基本概念軟件的相關(guān)概念：計算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完集合軟件的特點(diǎn)：是一種邏輯實體，而不是物理實體，具有抽象性軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程軟件在運(yùn)行、使用期間不存在磨損、老化的問題 軟件的開發(fā)、運(yùn)行對計算機(jī)系統(tǒng)具有依賴性，受計算機(jī)系統(tǒng)的限制 軟件復(fù)雜性高，成本昂貴計btfis件 e fty d kffl完"

17、;合 軟件開發(fā)設(shè)計諸多的社會因素軟件的相關(guān)概念軟件工程基本概念沒u明是的*1件12程特點(diǎn)不存左嗣老化*對計機(jī)i毓貝窮依耐夏5®、涉及多des*軟件危機(jī)與軟件工程軟件工程源自軟件危機(jī)軟件危機(jī)：泛指在計算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系 列的嚴(yán)重問題。具體的說，在軟件開發(fā)過程中，軟件危機(jī)主要體 現(xiàn)在：軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況 經(jīng)常發(fā)生 軟件開發(fā)成本和進(jìn)度無法控制。開發(fā)成本超出預(yù)算，開發(fā)周 期大大超過規(guī)定日期的情況經(jīng)常發(fā)生 軟件質(zhì)量難以保證 軟件不可維護(hù)或維護(hù)程度非常低總之，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題軟件工程：應(yīng)用于計算機(jī)軟件的定義、開發(fā)和維護(hù)

18、的一整套的方目的：法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。建造一個優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩占八、 軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境 軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)主要思想：將工程化原則運(yùn)用到軟件開發(fā)過程，它包括三個要素： 方法，是完成軟件工程項目的技術(shù)手段 工具，支持軟件的開發(fā)、管理、文檔生成 過程，支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理強(qiáng)為成&匪新皆問越軟件工程源自欣件危機(jī)beg軟件工程三 rw 1 m軟件危機(jī)與軟件工程i：件的才軟件危t住雯表現(xiàn)i心如3斑r件5軟件生命周期軟件生命周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護(hù)到停止使用退役的過程分

19、為三個階段：軟件定義階段：包括制定計劃和需求分析制定計劃：確定總計劃、可行性研究、探討解決方案、制定開發(fā)計劃需求分析：對待開發(fā)軟件提岀的需求進(jìn)行分析并給出詳細(xì)的定義 軟件開發(fā)階段：軟件設(shè)計：分為概要設(shè)計和詳細(xì)設(shè)計兩個部分軟件實現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機(jī)可以接受的程序代碼軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗軟件的各個組成部分 軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷維護(hù)，進(jìn)行必要的擴(kuò)充和刪改軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段定義軟件生命周期軟件趙 -需采分析較件蹄角三個階段詳細(xì)設(shè)計軟件開發(fā)g軟件實現(xiàn)軟件運(yùn)行維護(hù)較件產(chǎn)品從提出、實觀、使用堆護(hù)到停止便用退檢的過思屈走計劉軟件工程

20、的目標(biāo)與原則軟件工程的目標(biāo)（可以不用看）軟件工程的原則：抽象、信息隱蔽、模塊化、局部化確定性、一致性、完備性和可驗證性 抽象：是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化的辦法控制軟件開發(fā)過程的復(fù)雜性 信息隱蔽：采用封裝技術(shù)，將程序模塊的實現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡單 模塊化：模塊是程序中相對獨(dú)立的一部分，一個獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過大會使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修 改，也不利于模塊的調(diào)試和重用；模塊太小會導(dǎo)致整個系 統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性 局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有

21、較強(qiáng)的內(nèi)聚性 確定性：軟件開發(fā)的過程中所有的概念的表達(dá)應(yīng)是正確、無歧義且規(guī)范的 一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致 完備性：軟件系統(tǒng)不丟失任何重要成分，完全實現(xiàn)系統(tǒng)所需的功能 可驗證性：應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性fbtw仝用対費(fèi)技術(shù)j8hk匕性原則 |義定住wtfiwissjwts.無15義且觀危的衲內(nèi)外疙口阿一欣一僉?。ǘS軟件工程的原則事和8幡說鈞屠原侯行力&陽一叔可空證性帕易鈕.辭.t?aoj對比一下對象的待點(diǎn)m-®軟杵開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具：軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法 的進(jìn)步和完善，

22、促進(jìn)軟件開發(fā)的高速度和高質(zhì)量。軟件開發(fā)工具 的發(fā)展從單項工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)工具 為軟件工程方法提供了自動的或半自動的軟件支撐環(huán)境。同時， 軟件開發(fā)的方法的有效應(yīng)用也必須得到相應(yīng)工具的支持，否則方 法將難以有效的實施軟件開發(fā)環(huán)境：（或稱為軟件工程環(huán)境）是全面支持軟件開發(fā)全過 程的軟件工具的集合軟件開發(fā)工具. java軟件的開發(fā)工具及環(huán)境軟件開發(fā)環(huán)境定義全奩支拎軟件開發(fā)全12程的馱件hmm合結(jié)構(gòu)化分析方法結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論需求分析：需求分析方法有：結(jié)構(gòu)化需求分析方法 面向?qū)ο?的分析方法需求分析的任務(wù)：就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題需

23、求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個步驟進(jìn)行結(jié)構(gòu)化分析方法：是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用結(jié)構(gòu)化分析方法的實質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要 工具，建立系統(tǒng)的邏輯模型結(jié)構(gòu)化分析的常用工具： 數(shù)據(jù)流圖（dfd ）:以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流 動和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能， 是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工源、潭加工數(shù)據(jù)流存儲文件上圖是數(shù)據(jù)流圖的基本圖形元素：加工（轉(zhuǎn)換）:輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出 數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名存儲文件:（

24、數(shù)據(jù)源）表示處理過程中存放各種數(shù)據(jù)的文件源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體畫數(shù)據(jù)流圖基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求 精 數(shù)據(jù)字典（dd）:對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶 和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算 結(jié)果有共同的理解數(shù)據(jù)字典的作用：對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切 解釋數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心 判斷樹 判斷表需求分析輸化不分，方怎ksxk(dfd) 護(hù)i交件惟用rnaas刻eq出詼令名ssflsm嘶切第h構(gòu)化分僑方2ss卻結(jié)構(gòu)化分析方法軟件需求規(guī)格說明書（srs ）a i軟件需求規(guī)格說明

25、書：需求分析階段的最后成果，通過建立完的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計約束的說合適的驗收標(biāo)準(zhǔn)，給出對目標(biāo)惡如阿1的各種需求需求分析階段的最后結(jié)果軟件需求規(guī)格說明書結(jié)構(gòu)化設(shè)計方法軟件設(shè)計的基礎(chǔ)需求分析主要解決“做什么”的問題，而軟件設(shè)計主要解決“怎么做”的問題從技術(shù)觀點(diǎn)看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計 結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系 數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義 接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人 之間如何通信 過程設(shè)計：把系統(tǒng)結(jié)構(gòu)不見轉(zhuǎn)換成軟件的過程性描述從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計

26、和詳細(xì)設(shè)計概要設(shè)計：又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式詳細(xì)設(shè)計：確定每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié) 軟件設(shè)計的原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性 抽象：是一種思維工具，就是把事物本質(zhì)的共同特性提取岀來而不考慮其他細(xì)節(jié) 模塊化：解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對獨(dú)立但又不互相關(guān)聯(lián)的模塊的過程 信息隱蔽：每個模塊的實施細(xì)節(jié)對于其他模塊來說是隱蔽的 模塊獨(dú)立性：軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能，而和系統(tǒng)軟件中其他的接口是簡單的 模塊分解的主要指導(dǎo)思想是信息隱蔽

27、和模塊獨(dú)立性 模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個定性指標(biāo)內(nèi)聚性：一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量 按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、 邏輯內(nèi)聚、時間內(nèi)聚、過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚耦合性：是模塊之間互相連接的緊密程度的度量按耦合性由高到低排列，耦合性可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合 一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度解決怎么做”的問題軟件設(shè)計的基礎(chǔ)從技術(shù)觀點(diǎn)看 rnoattgwiht從工程角度wia

28、tu性內(nèi)援性內(nèi)smp后索總體設(shè)計（概要設(shè)計）和詳細(xì)設(shè)計總體設(shè)計（概要設(shè)計）軟件概要設(shè)計的基本任務(wù)：設(shè)計軟件系統(tǒng)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計 編寫概要文檔設(shè)計文檔 概要設(shè)計文檔評審常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：模塊用一個矩形表示，箭頭表示模塊間 的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過 程中傳遞的信息。還可用實心圓的箭頭表示傳遞的是控制信息， 空心圓箭頭表示傳遞的是數(shù)據(jù)信息o一般模塊o 數(shù)據(jù)信息控制信息據(jù)流的類型：變換型：變換型數(shù)據(jù)處理問題的工作過程大致 分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和輸岀數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部 分

29、組成事務(wù)型：事務(wù)型數(shù)據(jù)處理問題的工作機(jī)理是接受 一樣事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)，選擇分派 一個適當(dāng)?shù)奶幚韱卧缓蠼o出結(jié)果設(shè)計軟件系統(tǒng)結(jié)構(gòu)基本任務(wù)換結(jié)構(gòu)及數(shù)58庫設(shè)計砂設(shè)計文檔評京總體設(shè)計數(shù)據(jù)流89類型>51 1煩 o軟件結(jié)構(gòu)設(shè)計工具程序結(jié)構(gòu)85-空心國陸頭o 政釦b患實心05筆頭©控制佰患詳細(xì)設(shè)計詳細(xì)設(shè)計是為了軟件結(jié)構(gòu)圖中的每一個模塊確定實現(xiàn)算法和局部數(shù)據(jù)的結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法的數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)詳細(xì)設(shè)計的任務(wù)是確定實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不用于編碼或 編程常用的過程設(shè)計（即詳細(xì)設(shè)計）工具有以下幾種：圖形工具：程序流程圖、ns （方盒圖）、pad （問題分

30、析圖）和hipo （層次圖+輸入/處理/輸岀圖）表格工具：判定表語言工具：pdl （偽碼）仟務(wù) ehr確科現(xiàn)k法和局宓腐的ta恂詳細(xì)設(shè)計嚴(yán)砂一bb形工具e4ns（方食s3）pad （問去分忻83）常用工具扌| hlpo（jg次bs+給入/處理/焉出s3）1表格工鼻©ismtm ©pdl （陰）軟件測試定義：使用人工或自動手段來運(yùn)行或測定某個系統(tǒng)的過程，其目 的是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實際結(jié)果間的差 別目的：盡可能地發(fā)現(xiàn)程序中的錯誤，不能也不可能證明程序中沒 有錯誤關(guān)鍵：設(shè)計測試用例，一個好的測試用例能找到迄今為止尚未發(fā) 現(xiàn)的錯誤方法：靜態(tài)測試和動態(tài)測試 靜態(tài)測試

31、：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運(yùn)行軟件，主要通過人工進(jìn)行on 動態(tài)測試：是基于計算機(jī)的測試，主要包括白盒測試方法和盒測試方法(1)白盒測試也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試，它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計規(guī)格要求基本原則：保證所測模塊中每一獨(dú)立路徑至少執(zhí)行一次； 保證所測模塊所有判斷的每一分支至少執(zhí)行一次；保證所 測模塊每一循環(huán)都在邊界條件和一般條件下各執(zhí)行一次； 驗證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。白盒測試法的測試用例是根據(jù)程序內(nèi)部邏輯來設(shè)計的，主要用軟件的單元測試，主要方法有邏輯涵蓋、基本徑測試等黑盒測試也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測

32、試是對軟件已經(jīng) 實現(xiàn)的功能是否滿足需求進(jìn)行測試和驗證方法：等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟件的確認(rèn)測試軟件測試過程一般按4個步驟進(jìn)行：單元測試、集成測試、確認(rèn) 測試和系統(tǒng)測試 單元測試：是對軟件設(shè)計的最小單位模塊(程序單元)進(jìn)行正確性檢測的測試，目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯誤 集成測試：測試和組裝軟件的過程，它是把模塊在按照設(shè)計要 求組裝起來的同時進(jìn)行測試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤 確認(rèn)測試：驗證軟件的有效性，基金驗證軟件的功能和性能及 其他特性是否與用戶的要求一致 系統(tǒng)測試：通過系統(tǒng)的需求定義進(jìn)行比較，發(fā)現(xiàn)軟件與系統(tǒng)定 義不符合或與之矛盾的地方方法定義軟件測試

33、程序調(diào)試任務(wù)：診斷和更改程序中的錯誤，主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)該由編制源程序的程序員完成基本步驟：（1）錯誤定位 糾正錯誤 回歸測試調(diào)試方法：強(qiáng)行排錯法：主要方法有：通過內(nèi)存全部打印來排錯；在程序特定部位設(shè)置打印語句；自動調(diào)試工具 回溯法：發(fā)現(xiàn)了錯誤，分析錯誤征兆，確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程序原因排除法：通過演繹、歸納和二分法來實現(xiàn)任務(wù)診斷和更改程序中的flt涙程序調(diào)試調(diào)試方法3基本步驟糾正帕回歸清試位歸排怖去回洌法原因排除法第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)：實際上就是描述事物的符號記錄 特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如整型、實型、

34、字符型等。而數(shù)據(jù)的值給出了符合給定的值，如整型(int )值 15據(jù)庫(db ):數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共 享。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集 成與共享的特點(diǎn)，亦即是數(shù)據(jù)庫集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng) 一的構(gòu)造和存儲，而使它們可被不同的應(yīng)用程序所使用數(shù)據(jù)庫管理系統(tǒng)(dbms ): 一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù) 庫的核心數(shù)據(jù)庫管理員（dba ）:對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護(hù)、監(jiān)視等的專業(yè)管理人員數(shù)據(jù)庫系統(tǒng)（dbs ）:由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)

35、庫管理系統(tǒng)（軟件）、 數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五 個部分構(gòu)成的運(yùn)行實體數(shù)據(jù)庫應(yīng)用系統(tǒng)（dbas ）:由據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成dbs 包含 db、dbms數(shù)ib庫應(yīng)用系統(tǒng)（dbas ）數(shù)據(jù)庫系統(tǒng)（dbs ）數(shù)據(jù)庫系統(tǒng)的基本概念數(shù)據(jù)庫管理員（dba ）數(shù)嘩(db )sy mm 倉數(shù)據(jù)庫系統(tǒng)的發(fā)展數(shù)據(jù)庫管理發(fā)展至今經(jīng)歷了三個階段：人工管理階段、文件系統(tǒng) 階段和數(shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)的基本的特點(diǎn)： 數(shù)據(jù)的高集成性 數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余，但無法避免一起冗余 數(shù)據(jù)的獨(dú)立性：是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中 數(shù)據(jù)獨(dú)立與應(yīng)用程

36、序而不依賴于應(yīng)用程序。也就是說，數(shù)據(jù)的邏 輯結(jié)構(gòu)、存儲結(jié)構(gòu)與存取方式的改變不會影響應(yīng)用程序數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性兩級數(shù)據(jù)庫系統(tǒng)的發(fā)展三個階段文件s3渥系翊段特痊的如性數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系數(shù)據(jù)庫系統(tǒng)的三級模式： 概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用 戶（應(yīng)用）公共數(shù)據(jù)視圖 外模式：也稱子模式或用戶模式，它是用戶的所見到的數(shù)據(jù)模 式，它由概念模式推導(dǎo)而出 內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理 存取方法。內(nèi)模式的物理性主要體現(xiàn)在操作系統(tǒng)及文件級上，它 還未深入到設(shè)備級上（如磁盤及磁盤操作）o內(nèi)模式對用戶一般是 透明的，但它的設(shè)計直接影響數(shù)據(jù)庫

37、的性能數(shù)據(jù)模型數(shù)據(jù)模型分為概念模型、邏輯模型和物理模型三類 概念數(shù)據(jù)模型：簡稱概念模型，對客觀世界復(fù)雜事物的結(jié)構(gòu)描 述及它們之間的內(nèi)在聯(lián)系的刻畫。概念模型主要有：er模型（實 體聯(lián)系模型）、擴(kuò)充的er模型、面向?qū)ο竽Ｐ图爸^詞模型等 邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫系統(tǒng)的模型， 該模型著重在于數(shù)據(jù)庫系統(tǒng)一級的實現(xiàn)。邏輯數(shù)據(jù)模型主要有： 層狀模型、面向?qū)ο竽Ｐ偷?物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計算機(jī)物理表示 的模型，此模型給出了數(shù)據(jù)模型在計算機(jī)物理結(jié)構(gòu)上的表示 實體聯(lián)系模型及e-r圖 er模型的基本概念實體：現(xiàn)實世界中的事物（不可區(qū)分）屬性：事物的特性（外在特征）聯(lián)系：現(xiàn)實世

38、界中事物間的關(guān)系 實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系一對一一對多多對多eg :班級和班長班級和學(xué)生學(xué)生和老師er模型的三個基本概念之間的聯(lián)接關(guān)系：（1 ）實體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系（2 ）實體（集）與聯(lián)系 er模型的基本成分是實體和聯(lián)系er模型的圖示法實體集：用矩形表示屬性：用橢形表示 聯(lián)系：用菱形表示 實體集與屬性間的聯(lián)接關(guān)系：用無向線段表示 實體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示 數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型：層次模型、網(wǎng)狀模型、關(guān)系模層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn)：(1)每棵樹有且只有一個無雙親結(jié)點(diǎn)，稱為根；樹中除根外所有結(jié)點(diǎn)有且只有一個雙親 網(wǎng)狀模型是層次模型的一個特例，從圖論上看