1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章第一章 軟件工程軟件工程第二章第二章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第三章第三章 操作系統(tǒng)操作系統(tǒng)第四章第四章 數(shù)據(jù)庫技術(shù)數(shù)據(jù)庫技術(shù)第五章第五章 面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)第六章第六章 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)第七章第七章 網(wǎng)頁設(shè)計(jì)網(wǎng)頁設(shè)計(jì)綜合練習(xí)題綜合練習(xí)題計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 第一章第一章 軟件工程軟件工程 本章簡單介紹軟件工程的形成和發(fā)展，重點(diǎn)介紹軟件開發(fā)的不同方法和軟件測(cè)試策略與方法，最后就軟件開發(fā)環(huán)境和軟件重用技術(shù)作一簡要介紹。1.1 1.1 概述概述 軟件工程的提出源于20世記60年代末期出現(xiàn)的“軟件危機(jī)”，并在較短的時(shí)間內(nèi)發(fā)展成一個(gè)完整的學(xué)科方向，30多年來，在理論研究

2、和工程實(shí)踐兩個(gè)方面作了大量的工作。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.1 1.1.1 軟件工程的形成與發(fā)展軟件工程的形成與發(fā)展1.1.軟件發(fā)展的三個(gè)階段軟件發(fā)展的三個(gè)階段 軟件開發(fā)方法從機(jī)器語言編程到軟件工程方法，經(jīng)歷了三個(gè)階段。 1.程序設(shè)計(jì)時(shí)期（1946年到60年代中期） 生產(chǎn)方式是手工生產(chǎn)、個(gè)體勞動(dòng)。只有程序，無軟件的概念。 2.軟件時(shí)期（60年代中期至70年代中期） 程序不再是硬件的附屬，有軟件的概念。 作坊式的生產(chǎn)方式已難滿足軟件生產(chǎn)的質(zhì)量和數(shù)量上的要求。出現(xiàn)了“軟件危機(jī)”。3.軟件工程時(shí)期（70年代至今） 1968年、1969年北大西洋公約組織成員國的軟件工件者召開了兩個(gè)研討會(huì)，提出了“軟件

3、工程”這一述語，根本目的在于克服“軟件危機(jī)”中所遇到的困難問題，從此進(jìn)入軟件工程時(shí)代。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.軟件危機(jī)軟件危機(jī)(1) (1) 軟件危機(jī)的主要表現(xiàn)：軟件危機(jī)的主要表現(xiàn)：（軟件開發(fā)成本和進(jìn)度的估計(jì)常常很不準(zhǔn)確。（用戶往往對(duì)已完成的軟件不滿意。3)軟件的質(zhì)量常被懷疑。4)軟件極難維護(hù)。 5)缺乏良好的軟件文檔。6)軟件開發(fā)生產(chǎn)率提高的速度遠(yuǎn)遠(yuǎn)跟不上計(jì)算機(jī)應(yīng)用迅速普及深入的趨勢(shì)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)(2)軟件危機(jī)的產(chǎn)生原因軟件危機(jī)的產(chǎn)生原因 一般以為,軟件危機(jī)的發(fā)生與軟件產(chǎn)品的特征和軟件產(chǎn)品開發(fā)與維護(hù)的方法不正確有關(guān)。其一：軟件是邏輯的系統(tǒng)部件而不是物理的系統(tǒng)部件，以程序和文檔形

4、式存在，具有無形性。其二：軟件規(guī)模越來越大，功能越來越強(qiáng)，導(dǎo)致軟件結(jié)構(gòu)非常復(fù)雜。(3)(3)解決軟件危機(jī)的途徑解決軟件危機(jī)的途徑 方法是要充分吸取和借鑒人類長期以來從事各種工程項(xiàng)目所積累的行之有效的原理、概念、技術(shù)和方法，并應(yīng)用于軟件開發(fā)的實(shí)踐中，將軟件開發(fā)變成一種組織良好、管理嚴(yán)密、各類人員協(xié)同完成的工程項(xiàng)目計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3 3、軟件工程、軟件工程 1983年IEEE定義為：“軟件工程是開發(fā)、運(yùn)行、維護(hù)和修軟件工程是開發(fā)、運(yùn)行、維護(hù)和修復(fù)軟件的系統(tǒng)方法復(fù)軟件的系統(tǒng)方法”。軟件工程學(xué)的多個(gè)分支 (1)軟件工程方法學(xué) 方法學(xué)是研究軟件構(gòu)造技術(shù)的學(xué)問。一個(gè)軟件從定義、開發(fā)到維護(hù)，都需要有適當(dāng)?shù)?/p>

5、方法。 (2)軟件工程環(huán)境 對(duì)最終用戶而言，環(huán)境就是他們運(yùn)行程序所使用的計(jì)算機(jī)系統(tǒng)。 對(duì)于應(yīng)用軟件開發(fā)人員，環(huán)境是開發(fā)活動(dòng)的舞臺(tái)。 軟件工具是環(huán)境中最活躍的成分。所謂工具，在這里泛指一切幫助開發(fā)軟件的軟件。在軟件開發(fā)的各個(gè)方面都研制了許多有效的工具。集成化工具的自動(dòng)切換，可以明顯提高軟件的生產(chǎn)率。 (3)軟件工程管理 軟件工程管理的目的，是為了按照軟件的預(yù)算和進(jìn)度完成項(xiàng)目計(jì)劃，實(shí)現(xiàn)預(yù)期的經(jīng)濟(jì)和社會(huì)效益。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.2 1.1.2 軟件工程范型軟件工程范型 1、傳統(tǒng)的軟件工程范型、傳統(tǒng)的軟件工程范型瀑布模型瀑布模型 瀑布模型是1976年由BWBoehm提出的，是基于軟件生存周期的一

6、種范型。它將軟件生存周期分為定義、開發(fā)、維護(hù)三個(gè)它將軟件生存周期分為定義、開發(fā)、維護(hù)三個(gè)階段階段，每個(gè)階段又分為若干個(gè)子階段，各子階段的工作順序展開，如自上而下的瀑布。(見后圖)定義階段定義階段：分析用戶需求。問題定義問題定義：收集、分析、理解、確定用戶的要求。可行性研究可行性研究：確定對(duì)問題是否有可行的解決辦法。需求分析需求分析：確定用戶對(duì)軟件系統(tǒng)的全部需求。開發(fā)階段開發(fā)階段：設(shè)計(jì)：設(shè)計(jì)：設(shè)計(jì)軟件系統(tǒng)的模塊層次結(jié)構(gòu)、數(shù)據(jù)庫結(jié)構(gòu)、模塊控制流程等。編程：編程：將每個(gè)模塊的控制流程紡出相應(yīng)的程序。測(cè)試：測(cè)試：檢查并排除軟件中的錯(cuò)誤，提高軟件的可靠性。維護(hù)階段維護(hù)階段：運(yùn)行與維護(hù)運(yùn)行與維護(hù)：維護(hù)軟件

7、系統(tǒng)的正常運(yùn)行。各個(gè)階段確均有相應(yīng)的文檔。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)問題定義或行性研究需求分析設(shè) 計(jì)編 程測(cè) 試運(yùn)行與維護(hù)（目標(biāo)與范圍說明）（可行性論證報(bào)告）（需求說明書）（設(shè)計(jì)文檔）（程序）（測(cè)試報(bào)告）（維護(hù)報(bào)告）定義階段開發(fā)階段維護(hù)階段傳統(tǒng)的軟件工程范型傳統(tǒng)的軟件工程范型瀑布模型瀑布模型計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.2 1.2 軟件開發(fā)方法軟件開發(fā)方法 兩種不同的開發(fā)方法：結(jié)構(gòu)化開發(fā)方法和面向?qū)ο蟮拈_發(fā)方法。1.2.1 1.2.1 結(jié)構(gòu)化開發(fā)方法結(jié)構(gòu)化開發(fā)方法一、結(jié)構(gòu)化分析 1.結(jié)構(gòu)化分析方法，亦稱SA（Structured Analysis）方法。 (1)SA方法的特點(diǎn)： 核心思想：自頂向下和逐步求精。

8、 基本手段：分解和抽象。 分解：把大問題分割成若干小問題，然后分別解決。 抽象： 略去細(xì)節(jié)，先考慮問題最本質(zhì)的屬性。 使用了描述需求說明書的幾個(gè)規(guī)范工具。 即數(shù)據(jù)流圖、數(shù)據(jù)詞典、小說明（加工邏輯的描述）等，使文檔規(guī)范化。 (2)數(shù)據(jù)流圖（Data Flow Diagram，簡稱DFD圖） SA方法采用“分解”的方法來描述一個(gè)復(fù)雜的系統(tǒng)，數(shù)據(jù)流圖是描述系統(tǒng)中數(shù)據(jù)流程的圖形工具，它標(biāo)識(shí)了一個(gè)系統(tǒng)的邏輯輸入和邏輯輸出以及把邏輯輸入轉(zhuǎn)換為邏輯輸出所需要的加工處理。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1 數(shù)據(jù)數(shù)據(jù) 流圖的基本符號(hào)：流圖的基本符號(hào)：(1)數(shù)據(jù)流 (2)加工 (3)數(shù)據(jù)存儲(chǔ) (4)數(shù)據(jù)源點(diǎn)或終點(diǎn)。畫各層數(shù)據(jù)流

9、圖應(yīng)注意的問題：畫各層數(shù)據(jù)流圖應(yīng)注意的問題：(1)父圖和子圖平衡 (2)子圖的編號(hào) (3)數(shù)據(jù)守恒計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)數(shù)據(jù)詞典（Data Dictionary，簡稱DD）對(duì)數(shù)據(jù)流圖中包含的所有元素的定義的集合構(gòu)成了數(shù)據(jù)字典。 數(shù)據(jù)詞典中有四種類型的條目：數(shù)據(jù)流、文件、數(shù)據(jù)項(xiàng)和加工。（1）數(shù)據(jù)流條目 數(shù)據(jù)流條目給出某個(gè)數(shù)據(jù)流的定義，它通常是列出該數(shù)據(jù)流的各組成數(shù)據(jù)項(xiàng)。 如：課程=課程名+教員+教材+課程表 課程表=星期幾+第幾節(jié)+教室（2）文件條目 文件條目給出某個(gè)文件的定義。 訂單文件=訂單編號(hào)+顧客名稱+產(chǎn)品名稱+訂貨數(shù)量+交貨日期（3）數(shù)據(jù)項(xiàng)條目 數(shù)據(jù)項(xiàng)條目給出某個(gè)數(shù)據(jù)單項(xiàng)的定義。 學(xué)

10、號(hào)編號(hào)=19999（4）加工條目 加工條目又稱小說明。小說明中應(yīng)精確地描述用戶要求某個(gè)加工做什么。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2 2、結(jié)構(gòu)化設(shè)計(jì)、結(jié)構(gòu)化設(shè)計(jì) 結(jié)構(gòu)化設(shè)計(jì)方法，亦稱SD（Structured Design）方法。是一種面向數(shù)據(jù)流的設(shè)計(jì)方法，目的在于確定軟件的結(jié)構(gòu)。(1)SD方法的基本思想 其基本思想是：根據(jù)SA方法中的數(shù)據(jù)流圖建立一個(gè)良好的模塊結(jié)構(gòu)圖（例如SC圖或軟件層次方框圖）；運(yùn)用模塊化的設(shè)計(jì)原理控制系統(tǒng)的復(fù)雜性，即設(shè)計(jì)出模塊相對(duì)獨(dú)立的，模塊結(jié)構(gòu)圖深度、寬度都適當(dāng)?shù)模瑔稳肟趩纬隹诘模瑔我还δ艿哪K結(jié)構(gòu)的軟件結(jié)構(gòu)圖或軟件層次方框圖。 此方法提供了描述軟件系統(tǒng)的工具，提出了評(píng)價(jià)模塊結(jié)構(gòu)圖質(zhì)

11、量的標(biāo)準(zhǔn)，即模塊之間的聯(lián)系越松散越好，而模塊內(nèi)各成分之間的聯(lián)系越緊湊越好。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)SD方法的設(shè)計(jì)原理1）模塊化: 模塊化就是把系統(tǒng)劃分為若干個(gè)模塊，從而獲得滿足問題需要的一個(gè)解的過程。2）模塊的獨(dú)立性: 模塊獨(dú)立性有兩個(gè)定性的度量標(biāo)準(zhǔn)，即內(nèi)聚和耦合。耦合有六種，從小到大如下：兩個(gè)模塊完全獨(dú)立（沒有任何聯(lián)系）；數(shù)據(jù)耦合:即兩個(gè)模塊只通過數(shù)據(jù)進(jìn)行交換；狀態(tài)耦合:即兩個(gè)模塊之間通過控制狀態(tài)進(jìn)行傳遞；環(huán)境耦合:即兩個(gè)模塊之間通過公共環(huán)境進(jìn)行數(shù)據(jù)存取；公共塊耦合:即多個(gè)模塊引用一個(gè)全程數(shù)據(jù)區(qū)； 內(nèi)容耦合:即一個(gè)模塊使用保存在另一模塊內(nèi)部的數(shù)據(jù)或控制信息，或轉(zhuǎn)移進(jìn)入另一個(gè)模塊中間時(shí)，或一個(gè)

12、模塊有多個(gè)入口時(shí)。 由此看出模塊間耦合性越小越好。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)內(nèi)聚有六種，從小到大如下：偶然內(nèi)聚，即一個(gè)模塊由多任務(wù)組成，這些任務(wù)之間關(guān)系松散或根本沒聯(lián)系；邏輯內(nèi)聚:即一個(gè)模塊完成的任務(wù)在邏輯上相同或相似；時(shí)間內(nèi)聚:即一個(gè)模塊所包含的任務(wù)必須在同一時(shí)間內(nèi)執(zhí)行；通信內(nèi)聚:即一個(gè)模塊內(nèi)所有處理元素集中于相同的數(shù)據(jù)結(jié)構(gòu)；順序內(nèi)聚:即一個(gè)模塊中所有處理元素都是為完成同一功能而且必須順序執(zhí)行；功能內(nèi)聚:一個(gè)模塊所有處理都完成一個(gè)而且僅完成一個(gè)功能。內(nèi)聚性給出模塊的內(nèi)在聯(lián)系，因此內(nèi)聚性越大越好。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3）模塊的設(shè)計(jì)準(zhǔn)則 通過模塊的分解和合并，提高模塊的獨(dú)立性；模塊調(diào)用個(gè)數(shù)最好不要超過五個(gè)

13、；降低模塊接口的復(fù)雜性；一個(gè)模塊的所有下屬模塊應(yīng)該包括該模塊受某一判定影響的所有模塊的集合；模塊應(yīng)設(shè)計(jì)成單入口和單出口；模塊的大小要適中，一般在50句左右。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)數(shù)據(jù)流圖的類型 數(shù)據(jù)流圖通常分為兩大類型:轉(zhuǎn)換處理型和事務(wù)處理型. 轉(zhuǎn)換處理型: 由于大多數(shù)數(shù)據(jù)流圖都可看成是對(duì)輸入數(shù)據(jù)進(jìn)行轉(zhuǎn)換而得到輸出數(shù)據(jù)的處理，因此可把這類處理抽象為轉(zhuǎn)換處理型。轉(zhuǎn)換處理過程大致分為輸入數(shù)據(jù)，變換數(shù)據(jù)和輸出數(shù)據(jù)三步；它包含的數(shù)據(jù)流有輸入流、轉(zhuǎn)換流、輸出流三個(gè)部分。在輸入流中，信息由外部形式轉(zhuǎn)換為內(nèi)部形式的結(jié)果；在輸出流中，信息由內(nèi)部形式的結(jié)果轉(zhuǎn)換為外部形式數(shù)據(jù)流出系統(tǒng)。轉(zhuǎn)換處理型的數(shù)據(jù)流圖。計(jì)算

14、機(jī)軟件技術(shù)基礎(chǔ)事務(wù)處理型: 另一類數(shù)據(jù)流圖可看成是對(duì)一個(gè)數(shù)據(jù)流經(jīng)過某種加工后，按加工的結(jié)果選擇一個(gè)輸出數(shù)據(jù)流繼續(xù)執(zhí)行的處理。這種類型的處理可以抽象為事務(wù)處理型。在事務(wù)處理中，輸入數(shù)據(jù)流稱為事務(wù)流，加工稱為事務(wù)中心，若干平行數(shù)據(jù)流稱為事務(wù)路徑。當(dāng)事務(wù)流中的事務(wù)送到事務(wù)中心后，事務(wù)中心分析每一事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)選擇一個(gè)事務(wù)路徑繼續(xù)進(jìn)行處理。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(4)SD方法的設(shè)計(jì)過程 使用SD方法的基礎(chǔ)是數(shù)據(jù)流圖。正如前面所述，幾乎所有軟件在分析階段都可以表示為數(shù)據(jù)流圖，所以SD方法基本上可適用于任何軟件的開發(fā)工作。 用SD方法進(jìn)行總體設(shè)計(jì)的過程大致如下：（1）研究、分析和審查數(shù)據(jù)流圖，

15、從軟件的需求說明書弄清楚數(shù)據(jù)流加工的過程；（2）根據(jù)數(shù)據(jù)流圖確定數(shù)據(jù)流圖的類型；（3）從數(shù)據(jù)流圖導(dǎo)出系統(tǒng)的初始軟件結(jié)構(gòu)圖；（4）改進(jìn)初始軟件結(jié)構(gòu)圖，直到符合要求為止；（5）復(fù)查。(5)軟件結(jié)構(gòu)的描述方式 在SD方法中，軟件結(jié)構(gòu)用一種結(jié)構(gòu)圖來描述，它是設(shè)計(jì)說明書的一部分。結(jié)構(gòu)圖描述了軟件模塊結(jié)構(gòu)，并反映了模塊和模塊間聯(lián)系等特性。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3、詳細(xì)設(shè)計(jì)和編碼(1)詳細(xì)設(shè)計(jì)的任務(wù) 為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定采用的算法和塊內(nèi)數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具給出清晰的描述。(2)詳細(xì)設(shè)計(jì)的描述工具程序流程圖 也稱為程序框圖，獨(dú)立于任何一種程序設(shè)計(jì)語言，比較直觀、清晰、易于掌握。 任何復(fù)雜的程序

16、流程圖都可以由以下不同類型的基本結(jié)構(gòu)組合或嵌套而成： 順序結(jié)構(gòu) 選擇結(jié)構(gòu)(IF-THEN-ELSE) 多分支選擇結(jié)構(gòu)(CASE) 先判定循環(huán)結(jié)構(gòu)(WHILE) 后判定循環(huán)結(jié)構(gòu)(UNTIL)計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)方框圖（N-S圖）：圖形描述工具。限制了隨意的控制轉(zhuǎn)移。順序結(jié)構(gòu) 選擇結(jié)構(gòu) 多分支選擇結(jié)構(gòu)先判定型循環(huán)結(jié)構(gòu) 后判定型循環(huán)結(jié)構(gòu) 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)結(jié)構(gòu)化編碼方法結(jié)構(gòu)化編碼方法對(duì)源程序的編碼要求:最基本要求是源程序的正確性，同時(shí)還要考慮其可讀性、可理解性、可測(cè)試性和可維護(hù)性。寫程序的風(fēng)格:一個(gè)好的源程序意味著源程序代碼邏輯簡明清晰，易讀易懂。編碼原則： 程序內(nèi)部文檔應(yīng)選取含義鮮明的名

17、字，注解正確，程序清單層次清晰，布局合理。 數(shù)據(jù)說明和次序應(yīng)該標(biāo)準(zhǔn)化，個(gè)別復(fù)雜的數(shù)據(jù)結(jié)構(gòu)應(yīng)加注釋。 每個(gè)語句應(yīng)該簡單直接，不能為提高效率而使程序變得過份復(fù)雜。 對(duì)輸入數(shù)據(jù)應(yīng)進(jìn)行合法性檢查；對(duì)輸出數(shù)據(jù)要加輸出數(shù)據(jù)的標(biāo)志。 在程序編碼階段以不影響程序的清晰度和可讀性為前提，盡可能提高效率。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.2.2 面向?qū)ο箝_發(fā)方法面向?qū)ο箝_發(fā)方法面向?qū)ο蠹夹g(shù)是一種非常實(shí)用而強(qiáng)有力的軟件開發(fā)方法。面向?qū)ο筌浖_發(fā)方法又稱OOSD（Object-Oriented Software Development）。OOSD包括面向?qū)ο蠓治觯∣OA）、面向?qū)ο笤O(shè)計(jì)（OOD）和面向?qū)ο蟪绦蛟O(shè)計(jì)（OOP）三個(gè)方

18、面 。其中OOP是基礎(chǔ)，OOA和OOD是應(yīng)用OOP的機(jī)制。 面向?qū)ο蠓椒ê图夹g(shù)是自80年代以來逐漸形成的一種分析問題和解決問題的新方法，其基本出發(fā)點(diǎn)就是盡可能按照人類認(rèn)識(shí)世界的方法和思維方式來分析和解決問題。客觀世界是由許多具體的事物或事件、抽象的概念和規(guī)則等組成的，因此，我們將要加以研究的事、物、概念都稱為對(duì)象。面向?qū)ο蟮姆椒ㄕ且詫?duì)象作為最基本的元素，以對(duì)象作為分析問題，解決問題的核心。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1、面向?qū)ο蠓治觯∣OA） 把對(duì)象作為現(xiàn)實(shí)世界的抽象表示，然后定義對(duì)象的屬性和專門操縱那些屬性的服務(wù)，屬性和服務(wù)被看成對(duì)象的特征。具有相同的屬性和服務(wù)抽象的一系列對(duì)象組成類。因此在面向?qū)ο?/p>

19、模型中，它可以包含若干類，并且它對(duì)應(yīng)于模型的不同層次，因此 這些類有一定的層次關(guān)系和屬性繼承關(guān)系。面向?qū)ο蠓治鲇晌鍌€(gè)主要步驟構(gòu)成：(1)標(biāo)識(shí)對(duì)象(2)標(biāo)識(shí)對(duì)象屬性(3)定義對(duì)象的服務(wù)(4)識(shí)別對(duì)象所屬的類(5)定義主題計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2、面向?qū)ο蟮脑O(shè)計(jì)（OOD）OOA是一個(gè)分類活動(dòng)，而OOD模型由主體部件、用戶界面部件、任務(wù)管理部件和數(shù)據(jù)管理部件四部分構(gòu)成。每個(gè)部件又由主題詞、對(duì)象及類、結(jié)構(gòu)、屬性和外部服務(wù)五層組成，它們分別對(duì)應(yīng)OOA中的五個(gè)活動(dòng)：定義主題詞、標(biāo)識(shí)對(duì)象、標(biāo)識(shí)類、標(biāo)識(shí)對(duì)象的屬性和標(biāo)識(shí)對(duì)象的服務(wù)。其中主體部件是整個(gè)設(shè)計(jì)的主體，它包括完成目標(biāo)軟件系統(tǒng)主要功能的所有對(duì)象，用戶界面部件

20、給出人機(jī)交互需要的對(duì)象，任務(wù)管理部件提供協(xié)調(diào)和管理目標(biāo)軟件各個(gè)任務(wù)的對(duì)象，數(shù)據(jù)管理部件定義專用對(duì)象。要將目標(biāo)軟件系統(tǒng)中依賴于開發(fā)平臺(tái)的數(shù)據(jù)存取操作與其他功能分開，以提高對(duì)象獨(dú)立性。概括地說，OOD方法是以O(shè)OA模型為基礎(chǔ)，不斷填入和擴(kuò)展有關(guān)軟件設(shè)計(jì)的信息。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3、面向?qū)ο缶幊?完成OOD以后，將開始進(jìn)入編程階段。目前主要選取面向?qū)ο笳Z言(如C+)、基于對(duì)象的語言(如Ada)、過程式語言(如C語言)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3 1.3 軟件測(cè)試與質(zhì)量保證軟件測(cè)試與質(zhì)量保證1.3.1 軟件測(cè)試原則1、基本概念 軟件測(cè)試定義:軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。 軟件測(cè)試分為：單元測(cè)

21、試和綜合測(cè)試。 軟件測(cè)試在軟件生存周期中橫跨了兩個(gè)階段：通常在編寫出第一個(gè)模塊之后就對(duì)它做必要的測(cè)試（稱作單元測(cè)試）。編碼與單元測(cè)試屬于軟件生存周期中的同一階段。在結(jié)束這個(gè)階段之后，對(duì)軟件系統(tǒng)還要進(jìn)行各種綜合測(cè)試，這是軟件生存周期的另一個(gè)獨(dú)立的階段，即測(cè)試階段。2、目標(biāo)和原則 軟件測(cè)試的目標(biāo)可以歸納為以下幾點(diǎn)： 1.測(cè)試是為了發(fā)現(xiàn)軟件中的錯(cuò)誤而去運(yùn)行軟件的過程。 2.好的測(cè)試方案是盡可能地發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試方案。 3.成功的測(cè)試則是發(fā)現(xiàn)出至今未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3.2 軟件測(cè)試策略與技術(shù)軟件測(cè)試策略與技術(shù)1、軟件測(cè)試策略、軟件測(cè)試策略測(cè)試過程是按單元測(cè)試、組裝測(cè)

22、試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試四個(gè)步驟進(jìn)行的。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.單元測(cè)試（模塊測(cè)試）單元測(cè)試（模塊測(cè)試） 目的是發(fā)現(xiàn)模塊的子程序或過程的實(shí)際功能與該模塊的功能和接口描述是否相符，以及是否有編碼錯(cuò)誤存在。單元測(cè)試的主要內(nèi)容有:模塊接口測(cè)試；局部數(shù)據(jù)結(jié)構(gòu)測(cè)試；重要路徑測(cè)試；出錯(cuò)處理能力測(cè)試；邊界條件測(cè)試.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.組裝測(cè)試（集成測(cè)試或聯(lián)合測(cè)試）組裝測(cè)試（集成測(cè)試或聯(lián)合測(cè)試） 它的測(cè)試目的是為了發(fā)現(xiàn)程序結(jié)構(gòu)的錯(cuò)誤。組裝測(cè)試過程中的模塊組織方式有非漸增式和漸增式兩種。非漸增式組裝測(cè)試：又稱一次性組裝方式或整體拼裝。 測(cè)試方式是先對(duì)每個(gè)模塊分別進(jìn)行測(cè)試。然后再把所以模塊組裝在一起整體測(cè)試

23、。其優(yōu)點(diǎn)是對(duì)各模塊的測(cè)試可以并行進(jìn)行，有利于充分利用人力，加快測(cè)試速度。其缺點(diǎn)是由于程序中不可避免的地存在涉及模塊間接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)等方面的問題，所以一次試運(yùn)行成功的可能性不大，結(jié)果是發(fā)現(xiàn)有錯(cuò)誤，但卻找不到錯(cuò)誤的產(chǎn)生原因。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)漸增式組裝測(cè)試 這種方式是對(duì)一個(gè)個(gè)模塊進(jìn)行模塊調(diào)試，然后將這些模塊逐步組裝成較大的系統(tǒng)。在組裝過程中，每連接一個(gè)模塊便進(jìn)行一次測(cè)試，直到把所有模塊集成為一個(gè)整體并進(jìn)行測(cè)試，則軟件的組裝測(cè)試完成。 在漸增測(cè)試過程中，將模塊結(jié)合起來的策略有兩種：自底向上測(cè)試和自頂向下測(cè)試。自底向上測(cè)試：從程序模塊結(jié)構(gòu)的最低層模塊進(jìn)行組裝和測(cè)試。因?yàn)槟K是自底向上進(jìn)行組裝的，對(duì)

24、給定層次的模塊的下層模塊處理功能總可以得到，所以這種測(cè)試策略不必設(shè)計(jì)樁模塊（存根模塊），但要設(shè)計(jì)驅(qū)動(dòng)模塊。 自頂向下測(cè)試：將模塊按系統(tǒng)程序結(jié)構(gòu)，沿控制層次自頂向下進(jìn)行組裝。由主控模塊開始，按照程序的層次結(jié)構(gòu)向下移動(dòng)。逐漸把各個(gè)模塊組裝起來。 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)確認(rèn)測(cè)試(有效性測(cè)試)又稱有效性測(cè)試。組裝測(cè)試結(jié)束后，得到的是一個(gè)完整的軟件系統(tǒng)。這時(shí)需要進(jìn)行最后的測(cè)試，即有效性測(cè)試。有效性測(cè)試階段主要進(jìn)行的測(cè)試有：有效性測(cè)試（黑盒測(cè)試）、軟件配置復(fù)查、測(cè)試和測(cè)試以及驗(yàn)收測(cè)試。(4)系統(tǒng)測(cè)試 系統(tǒng)測(cè)試是指將經(jīng)過測(cè)試后的軟件系統(tǒng)與計(jì)算機(jī)硬件、外設(shè)、其他支持軟件以及其他系統(tǒng)元素一起進(jìn)行測(cè)試。測(cè)試內(nèi)容

25、主要有：功能測(cè)試、吞吐量測(cè)試、可用性測(cè)試、保密性測(cè)試、安裝測(cè)試、可恢復(fù)性測(cè)試、資料測(cè)試和程序測(cè)試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2、常用的測(cè)試方法常用的測(cè)試方法有黑盒測(cè)試和白盒測(cè)試兩種。(1)白盒測(cè)試 白盒測(cè)試又稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。所謂“白盒”是指將對(duì)象看作一個(gè)打開的盒子，測(cè)試人員可利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)的信息來設(shè)計(jì)或選擇測(cè)試用例。 白盒測(cè)試主要考慮的是測(cè)試用例對(duì)程序內(nèi)部邏輯的覆蓋程度，而不考慮程序的功能。 測(cè)試用例對(duì)程序的覆蓋程序從低到高分別為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋。 需要說明的是，上述各種覆蓋準(zhǔn)則的側(cè)重點(diǎn)不同，覆蓋程度也不同。但它們共同的是：任何一種覆

26、蓋都不能做到完全測(cè)試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)黑盒測(cè)試 黑盒測(cè)試又稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。 在這種測(cè)試方法中，程序?qū)y(cè)試者是完全透明的。測(cè)試者不考慮程序的內(nèi)部結(jié)構(gòu)和特性，就好像把程序看作一個(gè)不能打開的盒子，只根據(jù)程序的需求規(guī)格說明中的程序功能或程序的外部特性來設(shè)計(jì)測(cè)試用例。 黑盒測(cè)試的方法包括：等價(jià)分類法、邊緣值分析法、因果圖法和錯(cuò)誤推測(cè)法。 測(cè)試方法還有回歸測(cè)試、強(qiáng)度測(cè)試等等。每一種測(cè)試方法都各有所長，在實(shí)際測(cè)試中應(yīng)綜合使用。一般來講，通常用黑盒法設(shè)計(jì)基本的測(cè)試方案，再利用白盒法做必要的補(bǔ)充。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3.3 軟件質(zhì)量保證軟件質(zhì)量保證1、評(píng)審與測(cè)試 評(píng)審和測(cè)試都是質(zhì)量保證的重要

27、活動(dòng)。 驗(yàn)證：我們制造產(chǎn)品的步驟正確嗎？ 確認(rèn)：我們制造的是正確的產(chǎn)品嗎？2、程序正確性證明 程序正確性證明就是要通過數(shù)學(xué)的方法，證明程序具有某些需要的性質(zhì)。通過多年的研究，現(xiàn)已提出了一些有用的方法和技術(shù)，其中包括輸入輸出斷言法、最弱前置條件法、結(jié)構(gòu)歸納法紀(jì)等幾種常用的方法。 如果說程序測(cè)試是為了證明程序有錯(cuò)，則程序正確性的證明正好相反，是為了證明程序能夠完成某些預(yù)定的功能。現(xiàn)有的證明程序正確性的技術(shù)與工具包括已研制出來的程序正確性自動(dòng)證明器，僅適用于很小的程序。要解決大程序的正確性證明，還需要進(jìn)行大量的工作。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.4 軟件重用軟件重用重用（Reuse）是軟件過程的一部分。為了

28、快速做出復(fù)雜的應(yīng)用，重用是一條捷徑。此外，重用也是當(dāng)今軟件系統(tǒng)的重要特征。重用指在一個(gè)軟件項(xiàng)目中直接使用以前項(xiàng)目中的產(chǎn)物，而非重用某些工具，也就是把以前做過的東西納入到新項(xiàng)目中。1重用過程 面向?qū)ο蟮恼Z言本身就提供了重用機(jī)制，如封裝、繼承、模板等。技術(shù)上可以制成可重用構(gòu)件（不僅封裝數(shù)據(jù)還封裝行為，成為獨(dú)立的可重用對(duì)象），這樣可以大幅度提高開發(fā)效率。 重用的真正價(jià)值在于方案、決策的重用。利用集成技術(shù)將構(gòu)件按可重用模式裝入可重用框架（相當(dāng)于建筑中的梁、柱組成的房梁）構(gòu)成一組裝式軟件過程。從代碼重用到構(gòu)件重用到設(shè)計(jì)重用到過程重用（域工程）、從初創(chuàng)到成長到成就到實(shí)用。現(xiàn)代的軟件平臺(tái)，或多或少都提供了重

29、用機(jī)制。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2支持重用的環(huán)境從過程重用的觀點(diǎn)，以下10種軟件過程產(chǎn)物均可以重用：項(xiàng)目計(jì)劃 費(fèi)用估算 體系結(jié)構(gòu) 需求模型和規(guī)格說明 設(shè)計(jì) 源代碼 各種文檔 人機(jī)界面 測(cè)試用例 數(shù)據(jù) 這些產(chǎn)物作為重用件要作分類、標(biāo)記，作為對(duì)象構(gòu)件放入構(gòu)件庫。在當(dāng)今CIS分布系統(tǒng)上，構(gòu)件庫是一個(gè)數(shù)據(jù)庫服務(wù)器，它提供訪問服務(wù)。重用環(huán)境還必須提供集成工具，使重用的構(gòu)件能集成到新項(xiàng)目中。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3構(gòu)件與構(gòu)件重用構(gòu)件：是可重用的、具有獨(dú)立性的軟件單元，是用來構(gòu)造其他軟件的部件。構(gòu)件具有以下特點(diǎn)：(1)構(gòu)件是具有獨(dú)立性的、被封裝好的、具有描述能力的軟件單元。(2)構(gòu)件本身不是一個(gè)完整的應(yīng)用程序。(3)

30、構(gòu)件都有被定義好的接口，只巴能通過這些接口來操縱構(gòu)件。 (4)構(gòu)件之間可以交互。(5)構(gòu)件可以被擴(kuò)展。構(gòu)件的可繼承性使構(gòu)件能夠被擴(kuò)充和修改。目前有兩個(gè)方面的技術(shù)，一種是可視化構(gòu)件，另一種是分布式對(duì)象構(gòu)件。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.5 軟件開發(fā)環(huán)境軟件開發(fā)環(huán)境軟件開發(fā)由來已久。一臺(tái)宿主機(jī)，一個(gè)編譯（或匯編）程序，加上編輯、鏈接、裝入等少量實(shí)用程序，就構(gòu)成了早期軟件開發(fā)的舞臺(tái)。從這個(gè)意義上講，在軟件工程興起之前就有了軟件開發(fā)環(huán)境。在70年代和80年代初期，開發(fā)環(huán)境常被稱為“軟件工程環(huán)境”（簡稱SEE或SE2）或“程序設(shè)計(jì)支撐環(huán)境”。“計(jì)算機(jī)輔助軟件工程”（簡稱CASE），是今天對(duì)開發(fā)環(huán)境最流行的稱呼。

31、成為描述軟件開發(fā)環(huán)境與工具的最通用的名稱。另一個(gè)常見的名稱“工作臺(tái)”（workshop）。1976年，ICSE第二屆會(huì)議在一篇文章中發(fā)表了一個(gè)基于UNIX操作系統(tǒng)的程序設(shè)計(jì)支撐環(huán)境，稱之為“UNIX程序員工作臺(tái)”（UNIX programmers workbench，簡寫為UNIX/PWB）。這是國際上出現(xiàn)的第一個(gè)有影響的軟件開發(fā)環(huán)境。自此之后，工作臺(tái)也常被用作開發(fā)環(huán)境的同義詞。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2集成化工具開發(fā)軟件用到兩類工具。一類工具是畫或?qū)懺诩埳系模ㄔ诓煌A段使用的各種圖形與語言；另一類則是用來“開發(fā)軟件的軟件”，又稱為“軟件工具”或CASE工具。這里討論的是后一類工具。早期的環(huán)境只

32、配置用于編碼階段的工具，也稱為“低層”CASE工具。今天在軟件分析和總體設(shè)計(jì)等階段也有了許多支持開發(fā)的工具，即“高層”CASE工具。70年代出現(xiàn)了“工具箱”能部分地實(shí)現(xiàn)從一個(gè)工具到另一個(gè)工具的切換。今天，高、低層CASE工具由一組專用程序和一個(gè)用來支持工具間數(shù)據(jù)交換的環(huán)境信息庫構(gòu)成的支持下，共同構(gòu)成了具有統(tǒng)一的用戶界面、并能自動(dòng)實(shí)現(xiàn)工具切換的“集成工具”，對(duì)軟件開發(fā)的自動(dòng)化提供了有力的支持。CASE環(huán)境還可能包括另兩個(gè)層次。一個(gè)是環(huán)境體系結(jié)構(gòu)，用于區(qū)分開發(fā)環(huán)境為單機(jī)環(huán)境或網(wǎng)絡(luò)環(huán)境；另一個(gè)是可移植性服務(wù)程序，它介于集成工具與宿主機(jī)之間，使集成后的CASE工具不需要作重大的修改即可與環(huán)境的軟、硬件

33、平臺(tái)適應(yīng)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)小 結(jié)軟件工程是從工程角度來研究軟件開發(fā)的方法和技術(shù)，它是在克服軟件危機(jī)的過程中產(chǎn)生而發(fā)展起來的。軟件工程學(xué)是自軟件工程出現(xiàn)以后形成的一門新興學(xué)科。它包括的主要內(nèi)容有：軟件工程方法學(xué)、軟件工程環(huán)境和軟件工程管理等多個(gè)分支。一個(gè)軟件從用戶提出開發(fā)要求，到廢棄不用為止的全過程，稱為軟件的生存周期。軟件的生存周期劃分為若干個(gè)階段（如：需求定義、軟件設(shè)計(jì)、編程、測(cè)試、運(yùn)行維護(hù)等），每個(gè)階段有相對(duì)獨(dú)立的任務(wù)。 需求分析最常用的方法是結(jié)構(gòu)化分析方法（SA方法），SA方法適于分析大型數(shù)據(jù)處理系統(tǒng)，使用的主要工具有數(shù)據(jù)流圖和數(shù)據(jù)詞典。數(shù)據(jù)流圖以圖形形式表示軟件信息流向和信息加工，而

34、數(shù)據(jù)詞典對(duì)這些信息和加工進(jìn)行更詳細(xì)的描述。SA方法簡單實(shí)用、易于理解、使用廣泛。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)軟件設(shè)計(jì)可分為總體設(shè)計(jì)和詳細(xì)設(shè)計(jì)。總體設(shè)計(jì)通常使用結(jié)構(gòu)化設(shè)計(jì)方法。詳細(xì)設(shè)計(jì)是根據(jù)結(jié)構(gòu)化程序設(shè)計(jì)原則進(jìn)行的，只使用順序、分支、重復(fù)三種結(jié)構(gòu)來設(shè)計(jì)模塊的控制流程，使用的表示工具有程序流程圖、方框圖、PAD圖、偽碼（PDL語言）等。 軟件編程的任務(wù)是將軟件詳細(xì)設(shè)計(jì)的結(jié)果轉(zhuǎn)換成某種程序設(shè)計(jì)語言編寫的源程序。面向?qū)ο蟮姆椒ㄊ窃诮Y(jié)構(gòu)化程序設(shè)計(jì)的基礎(chǔ)上，進(jìn)一步力圖用更自然的方法反映客觀世界。在面向?qū)ο蟮南到y(tǒng)中，將數(shù)據(jù)和使用該數(shù)據(jù)的一組基本操作或過程封裝在一起，用“對(duì)象”這個(gè)概念來完整地反映客觀事物的靜態(tài)屬性和動(dòng)

35、態(tài)屬性。“面向?qū)ο蟆钡幕舅枷刖褪前岩獦?gòu)造的系統(tǒng)表示為對(duì)象的集合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。軟件測(cè)試的目的是要暴露軟件系統(tǒng)中的隱含錯(cuò)誤，然后通過軟件測(cè)試找出錯(cuò)誤的原因和位置并加以改正。在軟件開發(fā)中，測(cè)試是保證軟件正確性的最后一個(gè)階段，測(cè)試需要制定測(cè)試計(jì)劃，設(shè)計(jì)測(cè)試用例，然后實(shí)施測(cè)試，測(cè)試后進(jìn)行分析評(píng)價(jià)，測(cè)試結(jié)束后，要給出測(cè)試報(bào)告。 軟件測(cè)試方式分為：人工測(cè)試、動(dòng)態(tài)測(cè)試和自動(dòng)測(cè)試三種。測(cè)試過程按單元測(cè)試、組裝測(cè)試、確認(rèn)測(cè)試和系統(tǒng)測(cè)試四個(gè)步驟。 常用的測(cè)試方法有黑盒測(cè)試和白盒測(cè)試兩種。對(duì)于不同的測(cè)試方法，需要設(shè)計(jì)不同的測(cè)試用例。階段評(píng)審與測(cè)試，軟件配置管理是保證軟

36、件質(zhì)量的重要環(huán)節(jié)，軟件質(zhì)量保證計(jì)劃是確保上述環(huán)節(jié)實(shí)施的關(guān)鍵。軟件重用和CASE集成環(huán)境是當(dāng)今軟件工程技術(shù)重要的兩個(gè)方面，重用技術(shù)已從代碼重用發(fā)展到域工程，是大規(guī)模生產(chǎn)軟件的希望。集成技術(shù)在對(duì)象包裝下，當(dāng)今分布式應(yīng)用系統(tǒng)上已可實(shí)現(xiàn)數(shù)據(jù)集成、控制集成、表示集成。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第二章第二章 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述 隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，非數(shù)值數(shù)據(jù)的處理變得尤為重要，這些數(shù)據(jù)的元素之間在多是相互有關(guān)的。因此，討論數(shù)據(jù)元素之間的邏輯關(guān)系、數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式及在數(shù)據(jù)元素集合上設(shè)立的運(yùn)算如何實(shí)現(xiàn)，這是研究數(shù)據(jù)處理的基礎(chǔ)。本章在介紹數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念后，著重討論線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖形

37、結(jié)構(gòu)等三類數(shù)據(jù)結(jié)構(gòu)，最后介紹數(shù)據(jù)結(jié)構(gòu)中兩種特別重要的運(yùn)算-查找和排序。 對(duì)數(shù)據(jù)結(jié)構(gòu)的基本操作，本章采用C語言描述。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.12.1概述概述2.22.2線性表線性表2.32.3樹型結(jié)構(gòu)樹型結(jié)構(gòu)2.42.4圖圖2.52.5查找查找2.62.6排序排序小結(jié)小結(jié)計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1 概述概述l計(jì)算機(jī)早期運(yùn)算:原始數(shù)據(jù)和結(jié)果數(shù)據(jù)不多,重點(diǎn)在于算法。l計(jì)算機(jī)應(yīng)用的發(fā)展:逐漸變成對(duì)數(shù)據(jù)進(jìn)行非數(shù)值型的加工處理為主。l特點(diǎn)是數(shù)據(jù)量大，而計(jì)算的工作量可能很小。l數(shù)據(jù)結(jié)構(gòu)的提出： 數(shù)據(jù)結(jié)構(gòu)是為研究和解決諸如數(shù)據(jù)的分類與查找、情報(bào)檢索、數(shù)據(jù)庫、企業(yè)管理、系統(tǒng)工程、圖形識(shí)別、人工智能以及日常生活等各領(lǐng)

38、域的非數(shù)值問題而提出的理論與方法，即如何合理的組織數(shù)據(jù)，以提高算法的效率。l 重要性：對(duì)實(shí)現(xiàn)系統(tǒng)軟件，如操作系統(tǒng)、編譯程序和數(shù)據(jù)庫管理系統(tǒng)等均有十分重要的意義。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.1 2.1.1 數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念l 數(shù)據(jù)：描述客觀事物的的信息（數(shù)，字符，符號(hào)等）的集合，是程序處理的對(duì)象。l 數(shù)據(jù)元素：是數(shù)據(jù)集合中的個(gè)體，是構(gòu)成數(shù)據(jù)對(duì)象的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成。l 數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的最小單位。l 一組數(shù)據(jù)元素具有某種結(jié)構(gòu)形式。l 數(shù)據(jù)結(jié)構(gòu)：就是描述一組數(shù)據(jù)元素及元素間的相互關(guān)系的。l 數(shù)據(jù)結(jié)構(gòu)描述了一組性質(zhì)相同的數(shù)據(jù)元素及元素間的相互關(guān)系。 用集合論給出的數(shù)據(jù)結(jié)構(gòu)的定義為

39、: 數(shù)據(jù)結(jié)構(gòu)S是一個(gè)二元組：S=(D,R)。 其中:D是一個(gè)數(shù)據(jù)元素的非空的有限集合。 R是定義在D上的關(guān)系的非空的有限集合 數(shù)據(jù)結(jié)構(gòu)概念一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)元素之間的邏輯關(guān)系、數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式以及在這些數(shù)據(jù)元素上定義的運(yùn)算的集合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.2 2.1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有時(shí)可直接稱為數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)的三種基本類型：線性表、樹和圖。分別屬于兩大類： (一)線性結(jié)構(gòu)（線性表）線性結(jié)構(gòu)（線性表） 各數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡單地表示出來。 線性表是典型的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只按先后次序聯(lián)接。有棧、隊(duì)列、字

40、串、數(shù)組和文件。(二）非線性結(jié)構(gòu)（樹，圖）非線性結(jié)構(gòu)（樹，圖） 不滿足線性結(jié)構(gòu)特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。 樹、圖等是非線性結(jié)構(gòu)。 樹中的數(shù)據(jù)元素是分層次的縱向聯(lián)接。 圖中的數(shù)據(jù)元素則有各種各樣復(fù)雜聯(lián)接。 其它種類的數(shù)據(jù)結(jié)構(gòu)由這三種基本結(jié)構(gòu)派生的。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.3 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)設(shè)備中的映象稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(亦稱為物理結(jié)構(gòu))。 同一個(gè)邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)。 最常用的二種方式是： 順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。 大多數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示都采用其中的一種方式或兩種方式的結(jié)合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.順序存儲(chǔ)結(jié)

41、構(gòu)順序存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素按某種順序存放在存儲(chǔ)器的連續(xù)單元中。即將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中，而數(shù)據(jù)元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系唯一確定。若數(shù)據(jù)元素存放在以起始地址S開始的連續(xù)存儲(chǔ)單元中。則第i個(gè)元素的存儲(chǔ)地址：LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l假定每個(gè)元素所占的存儲(chǔ)空間是相同的,長度均為l。數(shù)據(jù)的這種順序存儲(chǔ)結(jié)構(gòu)叫做向量，以V表示，向量V的分量Vi是數(shù)據(jù)結(jié)構(gòu)的第i個(gè)元素在存儲(chǔ)器中的映像。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)順序存儲(chǔ)的主要特點(diǎn)是： 1.結(jié)點(diǎn)中只有自身信息域，沒有連接信息域。因此存儲(chǔ)密度大，存儲(chǔ)空間利用率高； 2.可以通過計(jì)算直接確定

42、數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址L。即可以對(duì)記錄直接進(jìn)行存取； 3.插入、刪除運(yùn)算會(huì)引起大量結(jié)點(diǎn)的移動(dòng)； 4.要求存儲(chǔ)在一片連續(xù)的地址中。 這種存儲(chǔ)方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.鏈接存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)， 而數(shù)據(jù)元素之間的關(guān)系是由指針來確定的。主要特點(diǎn)是：（1）結(jié)點(diǎn)由兩類域組成：數(shù)據(jù)域和指針域。（2）邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，既可實(shí)現(xiàn)線性數(shù)據(jù)結(jié)構(gòu)，又可用于表示非線性數(shù)據(jù)結(jié)構(gòu)。（3）插入，刪除操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針值即可。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.4 2.1.4 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 對(duì)一些典型數(shù)據(jù)結(jié)

43、構(gòu)中的結(jié)點(diǎn)進(jìn)行操作處理。1.插入:在數(shù)據(jù)結(jié)構(gòu)中的指定位置上插入新的數(shù)據(jù)元素；2.刪除:根據(jù)一定的條件,將某個(gè)結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中刪除；3.更新:更新數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定結(jié)點(diǎn)的值；4.檢索:在給定的數(shù)據(jù)結(jié)構(gòu)中,找出滿足一定條件的結(jié)點(diǎn)來，條件可以是某個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值；5.排序:根據(jù)某一給定的條件，將數(shù)據(jù)結(jié)構(gòu)中所有的結(jié)點(diǎn)重新排列順序等。從操作的特性來看，所有這些運(yùn)算的操作可以分為二類: 一類是加工型操作：操作改變了存儲(chǔ)結(jié)構(gòu)的值（如插入、刪除、更新等）； 另一類是引用操作：操作只是查詢或求得結(jié)點(diǎn)的值（如檢索等）。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2 2.2 線性表線性表最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)2.2.1 2.2.

44、1 線性表線性表 線性是指表中的每個(gè)元素呈線性關(guān)系，即除第一個(gè)外，都有一個(gè)直接前趨(predecessor)，同時(shí)除最后一個(gè)元素外，都僅有一個(gè)直接后繼(successor)。1.1.線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表L用符號(hào)表示為：L=(a1，a2，a3，. ai.，an) 線性表也可以正式定義為： 若數(shù)據(jù)結(jié)構(gòu) L=（D，R）是一個(gè)線性表，則：D是包括a1,a2,a3 .an 等元素的集合。R中只包含一個(gè)關(guān)系，即R= | ai-1，aiD， 2in 。 關(guān)系 給出了元素的一種先后次序。a1 稱為表的線性起始結(jié)點(diǎn)，an 為表的終結(jié)點(diǎn)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.線性表的存儲(chǔ)結(jié)構(gòu)線性表的存儲(chǔ)結(jié)

45、構(gòu)l存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。l具有順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，即用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的每個(gè)數(shù)據(jù)元素。l具有鏈接存儲(chǔ)結(jié)構(gòu)的線性表稱為線性鏈表。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中數(shù)據(jù)元素的，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。通常亦稱為鏈表。 常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。3.3.線性表的基本運(yùn)算線性表的基本運(yùn)算l常用的操作有:插入、刪除、修改、讀值、檢索和排序等。l線性表還可以進(jìn)行一些更為復(fù)雜的操作。如將兩個(gè)或兩個(gè)以上的具有相同數(shù)據(jù)對(duì)象的線性表合并成一個(gè)線性表，將一個(gè)線性表拆成若干個(gè)線性表，復(fù)制一個(gè)線性表等等。這些較為復(fù)雜的

46、操作都可以利用上述幾種常用的操作來實(shí)現(xiàn)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)( (1)1)順序表的操作順序表的操作 順序表在各種高級(jí)語言里經(jīng)常用一維數(shù)組實(shí)現(xiàn)。#define MAXSIZE 100 /數(shù)組中元素個(gè)數(shù)的最大值int listMAXSIZE,n; /n為線性表中當(dāng)前的結(jié)點(diǎn)數(shù) 插入運(yùn)算 插入運(yùn)算是在線性表的第i個(gè)元素和第 i+1個(gè)元素之間插入一個(gè)一個(gè)新元素x。 為了實(shí)現(xiàn)這個(gè)操作，必須把第i+1個(gè)元素到第n個(gè)元素依次向后移位一個(gè)位置，以便把第i+1個(gè)存儲(chǔ)位置讓出來，存儲(chǔ)新元素X。 假定已有一個(gè)數(shù)組,其值是由小到大排列的,現(xiàn)插入一個(gè)新的結(jié)點(diǎn)p0,要求插入后仍能保持由小到大的順序。 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)#de

47、fine N 20#define N 20int aNint aN；main()main() int i, data, n=10; int i, data, n=10; for(i=0; in-1; i+) scanf(“%d”, &ai); for(i=0; in-1; i+) scanf(“%d”, &ai); scanf(“%d”,&data); scanf(“%d”,&data); insert(a,n,data); insert(a,n,data); for(i=0; in; i+) printf(“%3d”,ai); for(i=0; in; i+)

48、 printf(“%3d”,ai); insert(int a, int n, int data)insert(int a, int n, int data) int i; int i; if (an-1data) an=data; if (an-10; i-) for(i=n-1; i0; i-) if (ai-1data) ai=ai-1; if (ai-1data) ai=ai-1; else ai=data; break; else ai=data; break; if(i=0) a0=data; if(i=0) a0=data; 計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 當(dāng)i=0時(shí),新結(jié)點(diǎn)x插在a1之前,

49、這時(shí)需移動(dòng)線性表中的所有元素。 當(dāng)i=n-1時(shí),新結(jié)點(diǎn)x插入在an-1之后,這時(shí)不需移動(dòng)線性表中的元素。 在具有n個(gè)結(jié)點(diǎn)的線性表中，插入一個(gè)新結(jié)點(diǎn)時(shí)，其執(zhí)行時(shí)間主要化費(fèi)在移動(dòng)結(jié)點(diǎn)的循環(huán)上。移動(dòng)結(jié)點(diǎn)的平均次數(shù)為： nii)n(p0122111111110n)n(n.)n(in)in(nnini 計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 刪除運(yùn)算 線性表的刪除運(yùn)算是指將線性表中第i個(gè)數(shù)據(jù)元素除掉，即把長度為n的線性表 （a1,a2,. ai-1,ai,ai+1,.an)中的ai除去,變成長度為n-1的線性表 （a1,a2,. ai-1,ai+1,.an)。 這只需將第i+1數(shù)據(jù)元素到n數(shù)據(jù)元素依次向前移動(dòng)一個(gè)位置即可。

50、 設(shè)線性表用一維數(shù)組a(N)存放，則在長度為n的線性表中刪除值為data元素.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)函數(shù)如下：int delete(int a,int n,int data)int delete(int a,int n,int data) int i,j,k=0; int i,j,k=0; for(i=0;in;i+) for(i=0;in;i+) if(ai=data) if(ai=data) for(j=i;jn-1;j+) aj=aj+1; for(j=i;jnext=NULL; if (h=NULL) h=p0;p0-next=NULL; else else while(p0-datap1

51、-data)&(p1-next!=NULL) while(p0-datap1-data)&(p1-next!=NULL) p2=p1; p1=p1-next; p2=p1; p1=p1-next; if (p0-data data) if (p0-data data) if(h=p1) h=p0; else p2-next=p0; if(h=p1) h=p0; else p2-next=p0; p0-next=p1; p0-next=p1; else else p1-next=p0;p0-next=NULL; p1-next=p0;p0-next=NULL; return (h

52、); return (h); 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)單鏈表的刪除在已給定的鏈表h中,刪除data值為m的結(jié)點(diǎn)。 1.鏈表h是否指向空表,如果是空表,則報(bào)告空表信息。2.若h不為空: 一直查到表尾還找不到該結(jié)點(diǎn),則在此鏈表中無此結(jié)點(diǎn)。 查找到該結(jié)點(diǎn): 若該結(jié)點(diǎn)在頭部,則h指向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。 若該結(jié)點(diǎn)在中部,則前趨結(jié)點(diǎn)的指針指向后趨結(jié)點(diǎn)。 若該結(jié)點(diǎn)在尾部,則前趨結(jié)點(diǎn)的指針為NULL。p2p1計(jì)算機(jī)軟件技術(shù)基礎(chǔ) struct node struct node * *del(struct node del(struct node * *h,int m)h,int m) struct node str

53、uct node * *p1,p1,* *p2;p2; if(h=NULL) if(h=NULL) printf(n This null!n); return(h); printf(n This null!n); return(h); p1=h; p1=h; while (p1-data!=m)&(p1-next!=NULL) while (p1-data!=m)&(p1-next!=NULL) p2=p1;p1=p1-next; p2=p1;p1=p1-next; if(p1-data=m) if(p1-data=m) if(p1=h) h=p1-next; if(p1=h)

54、 h=p1-next; else p2-next=p1-next; else p2-next=p1-next; free(p1); free(p1); else printf(%d nod beed found! n,m); else printf(%d nod beed found! n,m); return(h); return(h); 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)例：單鏈表的建立、打印和插入：實(shí)例：單鏈表的建立、打印和插入：#define NULL 0#define LEN sizeof(struct node)#include stdio.hstruct node int data; stru

55、ct node *next; ;struct node * create() /* 建立鏈表 */ struct node *h=NULL,*p,*q; int x; for(;) printf(Input data:); scanf(%d,&x); if(xdata=x; if(h=NULL) h=p; else q-next=p; q=p; if(h!=NULL) p-next=NULL; return(h); void print(struct node *h) struct node *p=h; while(p!=NULL) printf(%dn,p-data); p=p-ne

56、xt; 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)struct node *insert(struct node *h,struct node *p0) struct node *p1=h ,*p2; if (h=NULL) h=p0;p0-next=NULL; else while(p0-datap1-data)&(p1-next!=NULL) p2=p1; p1=p1-next; if(p0-datadata) if(h=p1) h=p0; else p2-next=p0; p0-next=p1; else p1-next=p0;p0-next=NULL; return (h); main() struc

57、t node *h,*p;int x; h=create(); print(h); p=(struct node *)malloc(LEN); scanf(%d,&x); p-data=x; h=insert(h,p); print(h); 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)二. 循環(huán)鏈表（1）循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針域不為NULL，而是指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。（2）在循環(huán)鏈表中設(shè)置一個(gè)表頭結(jié)點(diǎn)，使空表與非空表的運(yùn)算統(tǒng)一起來。(a) 非空表 (b) 空表圖 2-2-5 帶表頭結(jié)點(diǎn)的循環(huán)鏈表計(jì)算機(jī)軟件技術(shù)基礎(chǔ)（1）插入算法：在頭指針為h的循環(huán)鏈表中元素b的結(jié)點(diǎn)前插入新元素a. struct

58、node struct node * *inscst(struct node inscst(struct node * *h, int b, int a)h, int b, int a) struct node struct node * *q, q, * *p;p; q=(struct node q=(struct node * *)malloc(LEN);)malloc(LEN); q-data=a; q-data=a; p=h; p=h; while (p-next !=h )&(p-next)-data !=b) while (p-next !=h )&(p-next)

59、-data !=b) p=p-next; / p=p-next; /* *尋找指定元素的前一結(jié)點(diǎn)尋找指定元素的前一結(jié)點(diǎn)* */ / q-next=p-next; p-next=q ; q-next=p-next; p-next=q ; return (h); return (h); hpqba計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)刪除算法：在頭指針為h的循環(huán)鏈表中刪除元素為b的結(jié)點(diǎn) delcst(struct node delcst(struct node * *h, int b)h, int b) struct node struct node * *p,p,* *q;q; p=h; p=h; while

60、 (p-next !=h )&(p-next)-data !=b) while (p-next !=h )&(p-next)-data !=b) p=p-next; / p=p-next; /* *尋找指定元素的前一結(jié)點(diǎn)尋找指定元素的前一結(jié)點(diǎn)* */ / if (p-next =h) if (p-next =h) printf(“ No this node in the listn”); printf(“ No this node in the listn”); return(h); return(h); q=p-next ; p -next=q-next; q=p-next ; p -next=q-next; free(q); free(q); return(h); return(h); bpq計(jì)