計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

第一章軟件工程1.1.1軟件工程的形成與開(kāi)展1.軟件開(kāi)展的三個(gè)階段軟件開(kāi)發(fā)方法從機(jī)器語(yǔ)言編程到軟件工程方法，經(jīng)歷了三個(gè)階段。1.程序設(shè)計(jì)時(shí)期〔1946年到60年代中期〕生產(chǎn)方式是手工生產(chǎn)、個(gè)體勞動(dòng)。只有程序，無(wú)軟件的概念。2.軟件時(shí)期〔60年代中期至70年代中期〕程序不再是硬件的附屬，有軟件的概念。作坊式的生產(chǎn)方式已難滿足軟件生產(chǎn)的質(zhì)量和數(shù)量上的要求。出現(xiàn)了“軟件危機(jī)〞。3.軟件工程時(shí)期〔70年代至今〕1968年、1969年北大西洋公約組織成員國(guó)的軟件工件者召開(kāi)了兩個(gè)研討會(huì)，提出了“軟件工程〞這一述語(yǔ)，根本目的在于克服“軟件危機(jī)〞中所遇到的困難問(wèn)題，從此進(jìn)入軟件工程時(shí)代。2.軟件危機(jī)(1)軟件危機(jī)的主要表現(xiàn)：軟件開(kāi)發(fā)本錢(qián)和進(jìn)度的估計(jì)常常很不準(zhǔn)確。用戶往往對(duì)已完成的軟件不滿意。3)軟件的質(zhì)量常被疑心。4)軟件極難維護(hù)。5)缺乏良好的軟件文檔。6)軟件開(kāi)發(fā)生產(chǎn)率提高的速度遠(yuǎn)遠(yuǎn)跟不上計(jì)算機(jī)應(yīng)用迅速普及深入的趨勢(shì)。1.1.2軟件工程范型1、傳統(tǒng)的軟件工程范型――瀑布模型瀑布模型是1976年由B·W·Boehm提出的，是基于軟件生存周期的一種范型。它將軟件生存周期分為定義、開(kāi)發(fā)、維護(hù)三個(gè)階段，每個(gè)階段又分為假設(shè)干個(gè)子階段，各子階段的工作順序展開(kāi)，如自上而下的瀑布。(見(jiàn)后圖)定義階段：分析用戶需求。問(wèn)題定義：收集、分析、理解、確定用戶的要求?？尚行匝芯浚捍_定對(duì)問(wèn)題是否有可行的解決方法。需求分析：確定用戶對(duì)軟件系統(tǒng)的全部需求。開(kāi)發(fā)階段：設(shè)計(jì)：設(shè)計(jì)軟件系統(tǒng)的模塊層次結(jié)構(gòu)、數(shù)據(jù)庫(kù)結(jié)構(gòu)、模塊控制流程等。編程：將每個(gè)模塊的控制流程紡出相應(yīng)的程序。測(cè)試：檢查并排除軟件中的錯(cuò)誤，提高軟件的可靠性。維護(hù)階段：運(yùn)行與維護(hù)：維護(hù)軟件系統(tǒng)的正常運(yùn)行。各個(gè)階段確均有相應(yīng)的文檔。問(wèn)題定義或行性研究需求分析設(shè)計(jì)編程測(cè)試運(yùn)行與維護(hù)〔目標(biāo)與范圍說(shuō)明〕〔可行性論證報(bào)告〕〔需求說(shuō)明書(shū)〕〔設(shè)計(jì)文檔〕〔程序〕〔測(cè)試報(bào)告〕〔維護(hù)報(bào)告〕定義階段開(kāi)發(fā)階段維護(hù)階段傳統(tǒng)的軟件工程范型――瀑布模型1.2軟件開(kāi)發(fā)方法兩種不同的開(kāi)發(fā)方法：結(jié)構(gòu)化開(kāi)發(fā)方法和面向?qū)ο蟮拈_(kāi)發(fā)方法。1.2.1結(jié)構(gòu)化開(kāi)發(fā)方法一、結(jié)構(gòu)化分析1.結(jié)構(gòu)化分析方法，亦稱SA〔StructuredAnalysis〕方法。(1)SA方法的特點(diǎn)：①核心思想：自頂向下和逐步求精。②根本手段：分解和抽象。分解：把大問(wèn)題分割成假設(shè)干小問(wèn)題，然后分別解決。抽象：略去細(xì)節(jié)，先考慮問(wèn)題最本質(zhì)的屬性。③使用了描述需求說(shuō)明書(shū)的幾個(gè)標(biāo)準(zhǔn)工具。即數(shù)據(jù)流圖、數(shù)據(jù)詞典、小說(shuō)明〔加工邏輯的描述〕等，使文檔標(biāo)準(zhǔn)化。(2)數(shù)據(jù)流圖〔DataFlowDiagram，簡(jiǎn)稱DFD圖〕SA方法采用“分解〞的方法來(lái)描述一個(gè)復(fù)雜的系統(tǒng)，數(shù)據(jù)流圖是描述系統(tǒng)中數(shù)據(jù)流程的圖形工具，它標(biāo)識(shí)了一個(gè)系統(tǒng)的邏輯輸入和邏輯輸出以及把邏輯輸入轉(zhuǎn)換為邏輯輸出所需要的加工處理。1

數(shù)據(jù)流圖的根本符號(hào)：(1)數(shù)據(jù)流(2)加工(3)數(shù)據(jù)存儲(chǔ)(4)數(shù)據(jù)源點(diǎn)或終點(diǎn)。畫(huà)各層數(shù)據(jù)流圖應(yīng)注意的問(wèn)題：(1)父圖和子圖平衡(2)子圖的編號(hào)(3)數(shù)據(jù)守恒(3)數(shù)據(jù)詞典〔DataDictionary，簡(jiǎn)稱DD〕對(duì)數(shù)據(jù)流圖中包含的所有元素的定義的集合構(gòu)成了數(shù)據(jù)字典。數(shù)據(jù)詞典中有四種類(lèi)型的條目：數(shù)據(jù)流、文件、數(shù)據(jù)項(xiàng)和加工?！?〕數(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é)號(hào)編號(hào)=1～9999〔4〕加工條目加工條目又稱小說(shuō)明。小說(shuō)明中應(yīng)精確地描述用戶要求某個(gè)加工做什么。2、結(jié)構(gòu)化設(shè)計(jì)結(jié)構(gòu)化設(shè)計(jì)方法，亦稱SD〔StructuredDesign〕方法。是一種面向數(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ù)?，單入口單出口的，單一功能的模塊結(jié)構(gòu)的軟件結(jié)構(gòu)圖或軟件層次方框圖。此方法提供了描述軟件系統(tǒng)的工具，提出了評(píng)價(jià)模塊結(jié)構(gòu)圖質(zhì)量的標(biāo)準(zhǔn)，即模塊之間的聯(lián)系越松散越好，而模塊內(nèi)各成分之間的聯(lián)系越緊湊越好。(2)SD方法的設(shè)計(jì)原理1〕模塊化:模塊化就是把系統(tǒng)劃分為假設(shè)干個(gè)模塊，從而獲得滿足問(wèn)題需要的一個(gè)解的過(guò)程。2〕模塊的獨(dú)立性:模塊獨(dú)立性有兩個(gè)定性的度量標(biāo)準(zhǔn)，即內(nèi)聚和耦合。耦合有六種，從小到大如下：①兩個(gè)模塊完全獨(dú)立〔沒(méi)有任何聯(lián)系〕；②數(shù)據(jù)耦合:即兩個(gè)模塊只通過(guò)數(shù)據(jù)進(jìn)行交換；③狀態(tài)耦合:即兩個(gè)模塊之間通過(guò)控制狀態(tài)進(jìn)行傳遞；④環(huán)境耦合:即兩個(gè)模塊之間通過(guò)公共環(huán)境進(jìn)行數(shù)據(jù)存?。虎莨矇K耦合:即多個(gè)模塊引用一個(gè)全程數(shù)據(jù)區(qū)；⑥內(nèi)容耦合:即一個(gè)模塊使用保存在另一模塊內(nèi)部的數(shù)據(jù)或控制信息，或轉(zhuǎn)移進(jìn)入另一個(gè)模塊中間時(shí)，或一個(gè)模塊有多個(gè)入口時(shí)。由此看出模塊間耦合性越小越好。內(nèi)聚有六種，從小到大如下：①偶然內(nèi)聚，即一個(gè)模塊由多任務(wù)組成，這些任務(wù)之間關(guān)系松散或根本沒(méi)聯(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)聚性越大越好。3〕模塊的設(shè)計(jì)準(zhǔn)那么①通過(guò)模塊的分解和合并，提高模塊的獨(dú)立性；②模塊調(diào)用個(gè)數(shù)最好不要超過(guò)五個(gè)；③降低模塊接口的復(fù)雜性；④一個(gè)模塊的所有下屬模塊應(yīng)該包括該模塊受某一判定影響的所有模塊的集合；⑤模塊應(yīng)設(shè)計(jì)成單入口和單出口；⑥模塊的大小要適中，一般在50句左右。(3)數(shù)據(jù)流圖的類(lèi)型數(shù)據(jù)流圖通常分為兩大類(lèi)型:轉(zhuǎn)換處理型和事務(wù)處理型.轉(zhuǎn)換處理型:由于大多數(shù)數(shù)據(jù)流圖都可看成是對(duì)輸入數(shù)據(jù)進(jìn)行轉(zhuǎn)換而得到輸出數(shù)據(jù)的處理，因此可把這類(lèi)處理抽象為轉(zhuǎn)換處理型。轉(zhuǎn)換處理過(guò)程大致分為輸入數(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ù)流圖。事務(wù)處理型:另一類(lèi)數(shù)據(jù)流圖可看成是對(duì)一個(gè)數(shù)據(jù)流經(jīng)過(guò)某種加工后，按加工的結(jié)果選擇一個(gè)輸出數(shù)據(jù)流繼續(xù)執(zhí)行的處理。這種類(lèi)型的處理可以抽象為事務(wù)處理型。在事務(wù)處理中，輸入數(shù)據(jù)流稱為事務(wù)流，加工稱為事務(wù)中心，假設(shè)干平行數(shù)據(jù)流稱為事務(wù)路徑。當(dāng)事務(wù)流中的事務(wù)送到事務(wù)中心后，事務(wù)中心分析每一事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和性質(zhì)選擇一個(gè)事務(wù)路徑繼續(xù)進(jìn)行處理。(4)SD方法的設(shè)計(jì)過(guò)程使用SD方法的根底是數(shù)據(jù)流圖。正如前面所述，幾乎所有軟件在分析階段都可以表示為數(shù)據(jù)流圖，所以SD方法根本上可適用于任何軟件的開(kāi)發(fā)工作。用SD方法進(jìn)行總體設(shè)計(jì)的過(guò)程大致如下：〔1〕研究、分析和審查數(shù)據(jù)流圖，從軟件的需求說(shuō)明書(shū)弄清楚數(shù)據(jù)流加工的過(guò)程；〔2〕根據(jù)數(shù)據(jù)流圖確定數(shù)據(jù)流圖的類(lèi)型；〔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)圖來(lái)描述，它是設(shè)計(jì)說(shuō)明書(shū)的一局部。結(jié)構(gòu)圖描述了軟件模塊結(jié)構(gòu)，并反映了模塊和模塊間聯(lián)系等特性。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ì)語(yǔ)言，比較直觀、清晰、易于掌握。任何復(fù)雜的程序流程圖都可以由以下不同類(lèi)型的根本結(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)(2)方框圖〔N-S圖〕：圖形描述工具。限制了隨意的控制轉(zhuǎn)移。順序結(jié)構(gòu)選擇結(jié)構(gòu)多分支選擇結(jié)構(gòu)先判定型循環(huán)結(jié)構(gòu)后判定型循環(huán)結(jié)構(gòu)(3)結(jié)構(gòu)化編碼方法①對(duì)源程序的編碼要求:最根本要求是源程序的正確性，同時(shí)還要考慮其可讀性、可理解性、可測(cè)試性和可維護(hù)性。②寫(xiě)程序的風(fēng)格:一個(gè)好的源程序意味著源程序代碼邏輯簡(jiǎn)明清晰，易讀易懂。編碼原那么：程序內(nèi)部文檔應(yīng)選取含義鮮明的名字，注解正確，程序清單層次清晰，布局合理。數(shù)據(jù)說(shuō)明和次序應(yīng)該標(biāo)準(zhǔn)化，個(gè)別復(fù)雜的數(shù)據(jù)結(jié)構(gòu)應(yīng)加注釋。每個(gè)語(yǔ)句應(yīng)該簡(jiǎn)單直接，不能為提高效率而使程序變得過(guò)份復(fù)雜。對(duì)輸入數(shù)據(jù)應(yīng)進(jìn)行合法性檢查；對(duì)輸出數(shù)據(jù)要加輸出數(shù)據(jù)的標(biāo)志。在程序編碼階段以不影響程序的清晰度和可讀性為前提，盡可能提高效率。1、面向?qū)ο蠓治觥睴OA〕把對(duì)象作為現(xiàn)實(shí)世界的抽象表示，然后定義對(duì)象的屬性和專門(mén)操縱那些屬性的效勞，屬性和效勞被看成對(duì)象的特征。具有相同的屬性和效勞抽象的一系列對(duì)象組成類(lèi)。因此在面向?qū)ο竽Ｐ椭校梢园僭O(shè)干類(lèi)，并且它對(duì)應(yīng)于模型的不同層次，因此這些類(lèi)有一定的層次關(guān)系和屬性繼承關(guān)系。面向?qū)ο蠓治鲇晌鍌€(gè)主要步驟構(gòu)成：(1)標(biāo)識(shí)對(duì)象(2)標(biāo)識(shí)對(duì)象屬性(3)定義對(duì)象的效勞(4)識(shí)別對(duì)象所屬的類(lèi)(5)定義主題2、面向?qū)ο蟮脑O(shè)計(jì)〔OOD〕OOA是一個(gè)分類(lèi)活動(dòng)，而OOD模型由主體部件、用戶界面部件、任務(wù)管理部件和數(shù)據(jù)管理部件四局部構(gòu)成。每個(gè)部件又由主題詞、對(duì)象及類(lèi)、結(jié)構(gòu)、屬性和外部效勞五層組成，它們分別對(duì)應(yīng)OOA中的五個(gè)活動(dòng)：定義主題詞、標(biāo)識(shí)對(duì)象、標(biāo)識(shí)類(lèi)、標(biāo)識(shí)對(duì)象的屬性和標(biāo)識(shí)對(duì)象的效勞。其中主體部件是整個(gè)設(shè)計(jì)的主體，它包括完成目標(biāo)軟件系統(tǒng)主要功能的所有對(duì)象，用戶界面部件給出人機(jī)交互需要的對(duì)象，任務(wù)管理部件提供協(xié)調(diào)和管理目標(biāo)軟件各個(gè)任務(wù)的對(duì)象，數(shù)據(jù)管理部件定義專用對(duì)象。要將目標(biāo)軟件系統(tǒng)中依賴于開(kāi)發(fā)平臺(tái)的數(shù)據(jù)存取操作與其他功能分開(kāi)，以提高對(duì)象獨(dú)立性。概括地說(shuō)，OOD方法是以O(shè)OA模型為根底，不斷填入和擴(kuò)展有關(guān)軟件設(shè)計(jì)的信息。3、面向?qū)ο缶幊掏瓿蒓OD以后，將開(kāi)始進(jìn)入編程階段。目前主要選取面向?qū)ο笳Z(yǔ)言(如C++)、基于對(duì)象的語(yǔ)言(如Ada)、過(guò)程式語(yǔ)言(如C語(yǔ)言)。1.3軟件測(cè)試與質(zhì)量保證1.3.1軟件測(cè)試原那么1、根本概念軟件測(cè)試定義:軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。軟件測(cè)試分為：?jiǎn)卧獪y(cè)試和綜合測(cè)試。軟件測(cè)試在軟件生存周期中橫跨了兩個(gè)階段：通常在編寫(xiě)出第一個(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)行軟件的過(guò)程。2.好的測(cè)試方案是盡可能地發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試方案。3.成功的測(cè)試那么是發(fā)現(xiàn)出至今未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。1.單元測(cè)試〔模塊測(cè)試〕目的是發(fā)現(xiàn)模塊的子程序或過(guò)程的實(shí)際功能與該模塊的功能和接口描述是否相符，以及是否有編碼錯(cuò)誤存在。單元測(cè)試的主要內(nèi)容有:模塊接口測(cè)試；局部數(shù)據(jù)結(jié)構(gòu)測(cè)試；重要路徑測(cè)試；出錯(cuò)處理能力測(cè)試；邊界條件測(cè)試.2.組裝測(cè)試〔集成測(cè)試或聯(lián)合測(cè)試〕它的測(cè)試目的是為了發(fā)現(xiàn)程序結(jié)構(gòu)的錯(cuò)誤。組裝測(cè)試過(guò)程中的模塊組織方式有非漸增式和漸增式兩種。①非漸增式組裝測(cè)試：又稱一次性組裝方式或整體拼裝。測(cè)試方式是先對(duì)每個(gè)模塊分別進(jìn)行測(cè)試。然后再把所以模塊組裝在一起整體測(cè)試。其優(yōu)點(diǎn)是對(duì)各模塊的測(cè)試可以并行進(jìn)行，有利于充分利用人力，加快測(cè)試速度。其缺點(diǎn)是由于程序中不可防止的地存在涉及模塊間接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)等方面的問(wèn)題，所以一次試運(yùn)行成功的可能性不大，結(jié)果是發(fā)現(xiàn)有錯(cuò)誤，但卻找不到錯(cuò)誤的產(chǎn)生原因。②漸增式組裝測(cè)試這種方式是對(duì)一個(gè)個(gè)模塊進(jìn)行模塊調(diào)試，然后將這些模塊逐步組裝成較大的系統(tǒng)。在組裝過(guò)程中，每連接一個(gè)模塊便進(jìn)行一次測(cè)試，直到把所有模塊集成為一個(gè)整體并進(jìn)行測(cè)試，那么軟件的組裝測(cè)試完成。在漸增測(cè)試過(guò)程中，將模塊結(jié)合起來(lái)的策略有兩種：自底向上測(cè)試和自頂向下測(cè)試。自底向上測(cè)試：從程序模塊結(jié)構(gòu)的最低層模塊進(jìn)行組裝和測(cè)試。因?yàn)槟K是自底向上進(jìn)行組裝的，對(duì)給定層次的模塊的下層模塊處理功能總可以得到，所以這種測(cè)試策略不必設(shè)計(jì)樁模塊〔存根模塊〕，但要設(shè)計(jì)驅(qū)動(dòng)模塊。自頂向下測(cè)試：將模塊按系統(tǒng)程序結(jié)構(gòu)，沿控制層次自頂向下進(jìn)行組裝。由主控模塊開(kāi)始，按照程序的層次結(jié)構(gòu)向下移動(dòng)。逐漸把各個(gè)模塊組裝起來(lái)。(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)過(guò)測(cè)試后的軟件系統(tǒng)與計(jì)算機(jī)硬件、外設(shè)、其他支持軟件以及其他系統(tǒng)元素一起進(jìn)行測(cè)試。測(cè)試內(nèi)容主要有：功能測(cè)試、吞吐量測(cè)試、可用性測(cè)試、保密性測(cè)試、安裝測(cè)試、可恢復(fù)性測(cè)試、資料測(cè)試和程序測(cè)試。2、常用的測(cè)試方法常用的測(cè)試方法有黑盒測(cè)試和白盒測(cè)試兩種。(1)白盒測(cè)試白盒測(cè)試又稱結(jié)構(gòu)測(cè)試或邏輯驅(qū)動(dòng)測(cè)試。所謂“白盒〞是指將對(duì)象看作一個(gè)翻開(kāi)的盒子，測(cè)試人員可利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)的信息來(lái)設(shè)計(jì)或選擇測(cè)試用例。白盒測(cè)試主要考慮的是測(cè)試用例對(duì)程序內(nèi)部邏輯的覆蓋程度，而不考慮程序的功能。測(cè)試用例對(duì)程序的覆蓋程序從低到高分別為：語(yǔ)句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋。需要說(shuō)明的是，上述各種覆蓋準(zhǔn)那么的側(cè)重點(diǎn)不同，覆蓋程度也不同。但它們共同的是：任何一種覆蓋都不能做到完全測(cè)試。(2)黑盒測(cè)試黑盒測(cè)試又稱功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試。在這種測(cè)試方法中，程序?qū)y(cè)試者是完全透明的。測(cè)試者不考慮程序的內(nèi)部結(jié)構(gòu)和特性，就好似把程序看作一個(gè)不能翻開(kāi)的盒子，只根據(jù)程序的需求規(guī)格說(shuō)明中的程序功能或程序的外部特性來(lái)設(shè)計(jì)測(cè)試用例。黑盒測(cè)試的方法包括：等價(jià)分類(lèi)法、邊緣值分析法、因果圖法和錯(cuò)誤推測(cè)法。測(cè)試方法還有回歸測(cè)試、強(qiáng)度測(cè)試等等。每一種測(cè)試方法都各有所長(zhǎng)，在實(shí)際測(cè)試中應(yīng)綜合使用。一般來(lái)講，通常用黑盒法設(shè)計(jì)根本的測(cè)試方案，再利用白盒法做必要的補(bǔ)充。2．支持重用的環(huán)境從過(guò)程重用的觀點(diǎn)，以下10種軟件過(guò)程產(chǎn)物均可以重用：①工程方案②費(fèi)用估算③體系結(jié)構(gòu)④需求模型和規(guī)格說(shuō)明⑤設(shè)計(jì)⑥源代碼⑦各種文檔⑧人機(jī)界面⑨測(cè)試用例⑩數(shù)據(jù)這些產(chǎn)物作為重用件要作分類(lèi)、標(biāo)記，作為對(duì)象構(gòu)件放入構(gòu)件庫(kù)。在當(dāng)今CIS分布系統(tǒng)上，構(gòu)件庫(kù)是一個(gè)數(shù)據(jù)庫(kù)效勞器，它提供訪問(wèn)效勞。重用環(huán)境還必須提供集成工具，使重用的構(gòu)件能集成到新工程中。1.5軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)由來(lái)已久。一臺(tái)宿主機(jī)，一個(gè)編譯〔或匯編〕程序，加上編輯、鏈接、裝入等少量實(shí)用程序，就構(gòu)成了早期軟件開(kāi)發(fā)的舞臺(tái)。從這個(gè)意義上講，在軟件工程興起之前就有了軟件開(kāi)發(fā)環(huán)境。在70年代和80年代初期，開(kāi)發(fā)環(huán)境常被稱為“軟件工程環(huán)境〞〔簡(jiǎn)稱SEE或SE2〕或“程序設(shè)計(jì)支撐環(huán)境〞。“計(jì)算機(jī)輔助軟件工程〞〔簡(jiǎn)稱CASE〕，是今天對(duì)開(kāi)發(fā)環(huán)境最流行的稱呼。成為描述軟件開(kāi)發(fā)環(huán)境與工具的最通用的名稱。另一個(gè)常見(jiàn)的名稱——“工作臺(tái)〞〔workshop〕。1976年，ICSE第二屆會(huì)議在一篇文章中發(fā)表了一個(gè)基于UNIX操作系統(tǒng)的程序設(shè)計(jì)支撐環(huán)境，稱之為“UNIX程序員工作臺(tái)〞〔UNIXprogrammer’sworkbench，簡(jiǎn)寫(xiě)為UNIX/PWB〕。這是國(guó)際上出現(xiàn)的第一個(gè)有影響的軟件開(kāi)發(fā)環(huán)境。自此之后，工作臺(tái)也常被用作開(kāi)發(fā)環(huán)境的同義詞。2．集成化工具開(kāi)發(fā)軟件用到兩類(lèi)工具。一類(lèi)工具是畫(huà)或?qū)懺诩埳系模ㄔ诓煌A段使用的各種圖形與語(yǔ)言；另一類(lèi)那么是用來(lái)“開(kāi)發(fā)軟件的軟件〞，又稱為“軟件工具〞或CASE工具。這里討論的是后一類(lèi)工具。早期的環(huán)境只配置用于編碼階段的工具，也稱為“低層〞CASE工具。今天在軟件分析和總體設(shè)計(jì)等階段也有了許多支持開(kāi)發(fā)的工具，即“高層〞CASE工具。70年代出現(xiàn)了“工具箱〞能局部地實(shí)現(xiàn)從一個(gè)工具到另一個(gè)工具的切換。今天，高、低層CASE工具由一組專用程序和一個(gè)用來(lái)支持工具間數(shù)據(jù)交換的環(huán)境信息庫(kù)構(gòu)成的支持下，共同構(gòu)成了具有統(tǒng)一的用戶界面、并能自動(dòng)實(shí)現(xiàn)工具切換的“集成工具〞，對(duì)軟件開(kāi)發(fā)的自動(dòng)化提供了有力的支持。CASE環(huán)境還可能包括另兩個(gè)層次。一個(gè)是環(huán)境體系結(jié)構(gòu)，用于區(qū)分開(kāi)發(fā)環(huán)境為單機(jī)環(huán)境或網(wǎng)絡(luò)環(huán)境；另一個(gè)是可移植性效勞程序，它介于集成工具與宿主機(jī)之間，使集成后的CASE工具不需要作重大的修改即可與環(huán)境的軟、硬件平臺(tái)適應(yīng)。軟件設(shè)計(jì)可分為總體設(shè)計(jì)和詳細(xì)設(shè)計(jì)?？傮w設(shè)計(jì)通常使用結(jié)構(gòu)化設(shè)計(jì)方法。詳細(xì)設(shè)計(jì)是根據(jù)結(jié)構(gòu)化程序設(shè)計(jì)原那么進(jìn)行的，只使用順序、分支、重復(fù)三種結(jié)構(gòu)來(lái)設(shè)計(jì)模塊的控制流程，使用的表示工具有程序流程圖、方框圖、PAD圖、偽碼〔PDL語(yǔ)言〕等。軟件編程的任務(wù)是將軟件詳細(xì)設(shè)計(jì)的結(jié)果轉(zhuǎn)換成某種程序設(shè)計(jì)語(yǔ)言編寫(xiě)的源程序。面向?qū)ο蟮姆椒ㄊ窃诮Y(jié)構(gòu)化程序設(shè)計(jì)的根底上，進(jìn)一步力圖用更自然的方法反映客觀世界。在面向?qū)ο蟮南到y(tǒng)中，將數(shù)據(jù)和使用該數(shù)據(jù)的一組根本操作或過(guò)程封裝在一起，用“對(duì)象〞這個(gè)概念來(lái)完整地反映客觀事物的靜態(tài)屬性和動(dòng)態(tài)屬性。“面向?qū)ο蟥暤母舅枷刖褪前岩獦?gòu)造的系統(tǒng)表示為對(duì)象的集合。第二章數(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ù)處理的根底。本章在介紹數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念后，著重討論線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖形結(jié)構(gòu)等三類(lèi)數(shù)據(jù)結(jié)構(gòu)，最后介紹數(shù)據(jù)結(jié)構(gòu)中兩種特別重要的運(yùn)算-查找和排序。對(duì)數(shù)據(jù)結(jié)構(gòu)的根本操作，本章采用C語(yǔ)言描述。2.1概述2.2線性表2.3樹(shù)型結(jié)構(gòu)2.4圖2.5查找2.6排序小結(jié)2.1概述計(jì)算機(jī)早期運(yùn)算:原始數(shù)據(jù)和結(jié)果數(shù)據(jù)不多,重點(diǎn)在于算法。計(jì)算機(jī)應(yīng)用的開(kāi)展:逐漸變成對(duì)數(shù)據(jù)進(jìn)行非數(shù)值型的加工處理為主。特點(diǎn)是數(shù)據(jù)量大，而計(jì)算的工作量可能很小。數(shù)據(jù)結(jié)構(gòu)的提出：數(shù)據(jù)結(jié)構(gòu)是為研究和解決諸如數(shù)據(jù)的分類(lèi)與查找、情報(bào)檢索、數(shù)據(jù)庫(kù)、企業(yè)管理、系統(tǒng)工程、圖形識(shí)別、人工智能以及日常生活等各領(lǐng)域的非數(shù)值問(wèn)題而提出的理論與方法，即如何合理的組織數(shù)據(jù)，以提高算法的效率。重要性：對(duì)實(shí)現(xiàn)系統(tǒng)軟件，如操作系統(tǒng)、編譯程序和數(shù)據(jù)庫(kù)管理系統(tǒng)等均有十分重要的意義。2.1.1數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)：描述客觀事物的的信息〔數(shù)，字符，符號(hào)等〕的集合，是程序處理的對(duì)象。數(shù)據(jù)元素：是數(shù)據(jù)集合中的個(gè)體，是構(gòu)成數(shù)據(jù)對(duì)象的根本單位，可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的最小單位。一組數(shù)據(jù)元素具有某種結(jié)構(gòu)形式。數(shù)據(jù)結(jié)構(gòu)：就是描述一組數(shù)據(jù)元素及元素間的相互關(guān)系的。數(shù)據(jù)結(jié)構(gòu)描述了一組性質(zhì)相同的數(shù)據(jù)元素及元素間的相互關(guān)系。用集合論給出的數(shù)據(jù)結(jié)構(gòu)的定義為:數(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)算的集合。2.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有時(shí)可直接稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)的三種根本類(lèi)型：線性表、樹(shù)和圖。分別屬于兩大類(lèi)：(一)線性結(jié)構(gòu)〔線性表〕各數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡(jiǎn)單地表示出來(lái)。線性表是典型的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只按先后次序聯(lián)接。有棧、隊(duì)列、字串、數(shù)組和文件。(二〕非線性結(jié)構(gòu)〔樹(shù)，圖〕不滿足線性結(jié)構(gòu)特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。樹(shù)、圖等是非線性結(jié)構(gòu)。樹(shù)中的數(shù)據(jù)元素是分層次的縱向聯(lián)接。圖中的數(shù)據(jù)元素那么有各種各樣復(fù)雜聯(lián)接。其它種類(lèi)的數(shù)據(jù)結(jié)構(gòu)由這三種根本結(jié)構(gòu)派生的。2.1.3數(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)。大多數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示都采用其中的一種方式或兩種方式的結(jié)合。1.順序存儲(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è)數(shù)據(jù)元素存放在以起始地址S開(kāi)始的連續(xù)存儲(chǔ)單元中。那么第i個(gè)元素的存儲(chǔ)地址：LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l假定每個(gè)元素所占的存儲(chǔ)空間是相同的,長(zhǎng)度均為l。數(shù)據(jù)的這種順序存儲(chǔ)結(jié)構(gòu)叫做向量，以V表示，向量V的分量V[i]是數(shù)據(jù)結(jié)構(gòu)的第i個(gè)元素在存儲(chǔ)器中的映像。順序存儲(chǔ)的主要特點(diǎn)是：1.結(jié)點(diǎn)中只有自身信息域，沒(méi)有連接信息域。因此存儲(chǔ)密度大，存儲(chǔ)空間利用率高；2.可以通過(guò)計(jì)算直接確定數(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)。2.鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，而數(shù)據(jù)元素之間的關(guān)系是由指針來(lái)確定的。主要特點(diǎn)是：〔1〕結(jié)點(diǎn)由兩類(lèi)域組成：數(shù)據(jù)域和指針域?！?〕邏輯上相鄰的結(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)中的指針值即可。2.1.4數(shù)據(jù)結(jié)構(gòu)的運(yùn)算對(duì)一些典型數(shù)據(jù)結(jié)構(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)來(lái)，條件可以是某個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值；5.排序:根據(jù)某一給定的條件，將數(shù)據(jù)結(jié)構(gòu)中所有的結(jié)點(diǎn)重新排列順序等。從操作的特性來(lái)看，所有這些運(yùn)算的操作可以分為二類(lèi):一類(lèi)是加工型操作：操作改變了存儲(chǔ)結(jié)構(gòu)的值〔如插入、刪除、更新等〕；另一類(lèi)是引用操作：操作只是查詢或求得結(jié)點(diǎn)的值〔如檢索等〕。2.2線性表——最簡(jiǎn)單，最常用的一種數(shù)據(jù)結(jié)構(gòu)2.2.1線性表線性是指表中的每個(gè)元素呈線性關(guān)系，即除第一個(gè)外，都有一個(gè)直接前趨(predecessor)，同時(shí)除最后一個(gè)元素外，都僅有一個(gè)直接后繼(successor)。1.線性表的邏輯結(jié)構(gòu)線性表L用符號(hào)表示為：L=(a1，a2，a3，..ai...，an)線性表也可以正式定義為：假設(shè)數(shù)據(jù)結(jié)構(gòu)L=〔D，R〕是一個(gè)線性表，那么：D是包括a1,a2,a3.....an等元素的集合。R中只包含一個(gè)關(guān)系，即R={<ai-1,ai>|ai-1，ai∈D，2≤i≤n}。關(guān)系<ai-1,ai>給出了元素的一種先后次序。a1稱為表的線性起始結(jié)點(diǎn)，an為表的終結(jié)點(diǎn)。2.線性表的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。具有順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，即用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的每個(gè)數(shù)據(jù)元素。具有鏈接存儲(chǔ)結(jié)構(gòu)的線性表稱為線性鏈表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中數(shù)據(jù)元素的，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。通常亦稱為鏈表。常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。3.線性表的根本運(yùn)算常用的操作有:插入、刪除、修改、讀值、檢索和排序等。線性表還可以進(jìn)行一些更為復(fù)雜的操作。如將兩個(gè)或兩個(gè)以上的具有相同數(shù)據(jù)對(duì)象的線性表合并成一個(gè)線性表，將一個(gè)線性表拆成假設(shè)干個(gè)線性表，復(fù)制一個(gè)線性表等等。這些較為復(fù)雜的操作都可以利用上述幾種常用的操作來(lái)實(shí)現(xiàn)。(1)順序表的操作順序表在各種高級(jí)語(yǔ)言里經(jīng)常用一維數(shù)組實(shí)現(xiàn)。#defineMAXSIZE100//數(shù)組中元素個(gè)數(shù)的最大值intlist[MAXSIZE],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ǔ)位置讓出來(lái)，存儲(chǔ)新元素X。

假定已有一個(gè)數(shù)組,其值是由小到大排列的,現(xiàn)插入一個(gè)新的結(jié)點(diǎn)p0,要求插入后仍能保持由小到大的順序。#defineN20inta[N]；main(){inti,data,n=10;for(i=0;i<n-1;i++)scanf(“%d〞,&a[i]);scanf(“%d〞,&data);insert(a,n,data);for(i=0;i<n;i++)printf(“%3d〞,a[i]);}insert(inta[],intn,intdata){inti;if(a[n-1]<data)a[n]=data;else{a[n]=a[n-1];for(i=n-1;i>0;i--)if(a[i-1]>data)a[i]=a[i-1];else{a[i]=data;break;}if(i==0)a[0]=data;}}

當(dāng)i=0時(shí),新結(jié)點(diǎn)x插在a1之前,這時(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ù)為：②刪除運(yùn)算線性表的刪除運(yùn)算是指將線性表中第i個(gè)數(shù)據(jù)元素除掉，即把長(zhǎng)度為n的線性表〔a1,a2,...ai-1,ai,ai+1,...an)中的ai除去,變成長(zhǎng)度為n-1的線性表〔a1,a2,...ai-1,ai+1,...an)。這只需將第i+1數(shù)據(jù)元素到n數(shù)據(jù)元素依次向前移動(dòng)一個(gè)位置即可。設(shè)線性表用一維數(shù)組a(N)存放，那么在長(zhǎng)度為n的線性表中刪除值為data元素.函數(shù)如下：intdelete(inta[],intn,intdata){inti,j,k=0;for(i=0;i<n;i++)if(a[i]==data){for(j=i;j<n-1;j++)a[j]=a[j+1];/*數(shù)據(jù)元素依次向前移動(dòng)*/a[n-1]=0;n--;k=1;break;}if(k==0)printf("Nothiselement!");return(n);}head..............an0a0a1a2(2)線性鏈表的操作單鏈表結(jié)點(diǎn)一般用結(jié)構(gòu)體說(shuō)明如下：structnode{intdata;structnode*next;};

①單鏈表的插入假定已有一個(gè)鏈表的表頭為h,其data域的值是由小到大排列的,現(xiàn)插入一個(gè)新的結(jié)點(diǎn)p0,要求插入后仍能保持由小到大的順序.考慮:1.鏈表h假設(shè)為空，那么將p0的next值為NULL，并將h指向p0。2.鏈表h不是空表，那么首先確定p0的插入位置。那么分三種情況:①p0插在第一個(gè)結(jié)點(diǎn)之前：將p0的next指向h的第一個(gè)結(jié)點(diǎn)，然后將h指向p0。②p0插在鏈表中間：假設(shè)在ai-1和ai之間插入,可將p0的next指向ai;ai-1的next指向p0.③p0插在鏈表的末尾：將最后一個(gè)結(jié)點(diǎn)的next指向p0，而使p0的next置為NULL。......p2p1p0structnode*insert(structnode*h,structnode*p0){structnode*p1=h,*p2;if(h==NULL){h=p0;p0->next=NULL;}else{while((p0->data>p1->data)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->data<=p1->data){if(h==p1)h=p0;elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}}return(h);}②單鏈表的刪除在已給定的鏈表h中,刪除data值為m的結(jié)點(diǎn)。1.鏈表h是否指向空表,如果是空表,那么報(bào)告空表信息。2.假設(shè)h不為空:①一直查到表尾還找不到該結(jié)點(diǎn),那么在此鏈表中無(wú)此結(jié)點(diǎn)。②查找到該結(jié)點(diǎn):假設(shè)該結(jié)點(diǎn)在頭部,那么h指向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。假設(shè)該結(jié)點(diǎn)在中部,那么前趨結(jié)點(diǎn)的指針指向后趨結(jié)點(diǎn)。假設(shè)該結(jié)點(diǎn)在尾部,那么前趨結(jié)點(diǎn)的指針為NULL。p2p1structnode*del(structnode*h,intm){structnode*p1,*p2;if(h==NULL){printf("\nThisnull!\n");return(h);}p1=h;while((p1->data!=m)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p1->data==m){if(p1==h)h=p1->next;elsep2->next=p1->next;free(p1);}elseprintf("%dnodbeedfound!\n",m);return(h);}實(shí)例：?jiǎn)捂湵淼慕?、打印和插入?defineNULL0#defineLENsizeof(structnode)#include"stdio.h"structnode{intdata;structnode*next;};structnode*create()/*建立鏈表*/{structnode*h=NULL,*p,*q;intx;for(;;){printf("Inputdata:");scanf("%d",&x);if(x<0)break;p=(structnode*)malloc(LEN);p->data=x;if(h==NULL)h=p;elseq->next=p;q=p;}if(h!=NULL)p->next=NULL;return(h);}voidprint(structnode*h){structnode*p=h;while(p!=NULL){printf("%d\n",p->data);p=p->next;}}structnode*insert(structnode*h,structnode*p0){structnode*p1=h,*p2;if(h==NULL){h=p0;p0->next=NULL;}else{while((p0->data>p1->data)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->data<=p1->data){if(h==p1)h=p0;elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}}return(h);}main(){structnode*h,*p;intx;h=create();print(h);p=(structnode*)malloc(LEN);scanf("%d",&x);p->data=x;h=insert(h,p);print(h);}二.循環(huán)鏈表〔1〕循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針域不為NULL，而是指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)?！?〕在循環(huán)鏈表中設(shè)置一個(gè)表頭結(jié)點(diǎn)，使空表與非空表的運(yùn)算統(tǒng)一起來(lái)。(a)非空表(b)空表圖2-2-5帶表頭結(jié)點(diǎn)的循環(huán)鏈表〔1〕插入算法：在頭指針為h的循環(huán)鏈表中元素b的結(jié)點(diǎn)前插入新元素a.structnode*inscst(structnode*h,intb,inta){structnode*q,*p;q=(structnode*)malloc(LEN);q->data=a;p=h;

while((p->next!=h)&&((p->next)->data!=b))p=p->next;/*尋找指定元素的前一結(jié)點(diǎn)*/q->next=p->next;p->next=q;return(h);}hpqba(2)刪除算法：在頭指針為h的循環(huán)鏈表中刪除元素為b的結(jié)點(diǎn)delcst(structnode*h,intb){structnode*p,*q;p=h;while((p->next!=h)&&((p->next)->data!=b))p=p->next;/*尋找指定元素的前一結(jié)點(diǎn)*/if(p->next==h){printf(“Nothisnodeinthelist\n〞);return(h);}q=p->next;p->next=q->next;free(q);return(h);}bpq三.多項(xiàng)式相加A(x)=3x14+2x8+1B(x)=8x14-3x10+10x6C(x)=A(x)+B(x)

設(shè)pa,pb指針〔1〕假設(shè)指針相等，那么系數(shù)相加，c(x)中建項(xiàng)〔系數(shù)為0，不建〕〔2〕假設(shè)pa->exp>pb->exp復(fù)抄pa所指項(xiàng)，反之，復(fù)抄pb所指項(xiàng)。-13142810ah-1814-310106bhcofexpch-11411-3102810610papbpcstructnode1*addpoly(structnode1*ah,structnode1*bh){structnode1*pa,*pb,*pc,*ch,*pp;intx,e;ch=(structnode1*)malloc(LEN);ch->exp=-1;ch->next=ch;pc=ch;/*建立新表頭結(jié)點(diǎn)*/pa=ah->next;pb=bh->next;while((pa->exp!=-1)||(pb->exp!=-1)){if(pa->exp==pb->exp){x=pa->cof+pb->cof;e=pa->exp;/*系數(shù)相加*/pa=pa->next;pb=pb->next；/*修改指針*/}elseif(pa->exp>pb->exp){x=pa->cof;e=pa->exp;/*復(fù)抄A(x)*/pa=pa->next;}else{x=pb->cof;e=pb->exp;/*復(fù)抄B(x)*/pb=pb->next;}if(x!=0)/*形成新結(jié)點(diǎn)鏈入C(x)*/{pp=(structnode1*)malloc(LEN);pp->cof=x;pp->exp=e;pp->next=ch;pc->next=pp;pc=pp;}}return(ch);}

多重鏈表:每個(gè)結(jié)點(diǎn)均有兩個(gè)或兩個(gè)以上指針的鏈表。雙重鏈表設(shè)兩個(gè)指針域：一個(gè)指向后繼結(jié)點(diǎn)，另一個(gè)指向前趨結(jié)點(diǎn)。 structnode{intdata;structnode*prio;structnode*next;}

圖2-2-6帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表a.插入運(yùn)算在已由小到大排列的帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表h中，插入一個(gè)新的結(jié)點(diǎn)p0插入后，要求仍保持由小到大的排列次序。structnode*insert2(structnode*h,structnode*p0){structnode*p1p1=h->next;while((p0->data>p1->data)&&(p1!=h))p1=p1->next;p0->prio=p1->prio;p1->prio->next=p0;p0->next=p1;p1->prio=p0;return(h);}p0p1hb.刪除操作在已給定的頭結(jié)點(diǎn)h的雙向鏈表中，刪除一個(gè)data值為m的結(jié)點(diǎn)。structnode*data(structnode*h,intm){structnode*p1；p1=h->next;while((p1->data!=m)&&(p1!=h))p1=p1->next;if(p1->data==m){p1->prio->next=p1->next;p1->next->prio=p1->prio;free(p1);}elseprintf(“%dnotbeenfound!\n〞,m);return(h);}hmp12.2.2棧棧是限定在一端進(jìn)行插入與刪除的線性表。允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。例如，給定棧(a0,a1,…,an-1〕稱a0為棧底元素，an-1為棧頂元素。棧是一種后進(jìn)先出(LIFO--LastInFirstOut)或先進(jìn)后出〔FILO)的線性表。在棧中，元素的插入稱為進(jìn)棧，元素的刪除稱為出棧。1.順序存儲(chǔ)的棧順序棧：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)設(shè)指針top指示棧頂元素的當(dāng)前位置。假設(shè)用一維數(shù)組s[max]表示棧，指針top指向棧頂元素.s[0]為最早進(jìn)入棧的元素，s[top]為最遲進(jìn)入棧的元素。當(dāng)top=max-1時(shí)，為滿棧.初始化top=-1注：top,max為全局變量〔1〕進(jìn)棧push(ints[],intx){if(top==max-1)printf(“Stackoverflow!\n〞);/*上溢*/elses[++top]=x;}〔2〕出棧intpop(ints[]){inty=-1;if(top==-1)printf(“Stackunderflow!\n〞);/*下溢*/elsey=s[top--];return(y);}圖2-2-8數(shù)據(jù)元素和棧頂指針之間的對(duì)應(yīng)關(guān)系假設(shè)有兩個(gè)棧，我們讓它們共享一數(shù)組s[m]，因?yàn)闂５孜恢檬遣蛔儎?dòng)的，所以可將兩個(gè)棧底分別設(shè)在數(shù)組空間的兩端，然后各自向中間伸展(如以下圖所示)，顯然，僅當(dāng)兩個(gè)棧頂相遇時(shí)才可能發(fā)生上溢。由于兩個(gè)棧之間可以做到互補(bǔ)余缺，使得每個(gè)棧實(shí)際可利用的最大空間大于m/2。2.鏈存儲(chǔ)的棧當(dāng)棧的最大容量事先不能估計(jì)時(shí)，也可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，稱為鏈棧。一個(gè)鏈棧由它的棧頂指針top唯一確定。如圖2.11所示。這里棧空的判別條件是top是否為NULL，而棧滿將不會(huì)發(fā)生,除非計(jì)算機(jī)的全部可利用空間都被占滿。對(duì)一個(gè)元素多變的棧來(lái)說(shuō)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)似乎更適宜。棧鏈的運(yùn)算實(shí)現(xiàn)也比較簡(jiǎn)單。計(jì)算表達(dá)式運(yùn)算符:**/*+-X=A*(B+C/D)-E*F**G優(yōu)先數(shù):43322ABCDOptrOpnd(a)進(jìn)棧后*〔+/ABT1*(+(b)T1=C/DAT2*((c)T2=B+T1AT2*(d)彈出左括號(hào)T3(e)T3=A*T2T3EFG_***(f)進(jìn)棧后T3ET4_*(g)T4=F**GT3T5_(h)T5=E*T4T6(i)T6=T3_T5求表達(dá)式3*〔7-2〕的值。optropnd輸入字符主要操作1#3*〔7-2〕#push(opnd,3)2#3*〔7-2〕#push(optr,’*’)3#*3〔7-2〕#push(optr,’(’)4#*(37-2〕#push(opnd,7)5#*(37-2〕#push(optr,’-’)6#*(-372〕#push(opnd,2)7#*(-372〕#operate(‘7’,’-’,’2’)8#*(35)#pop(optr)&&一對(duì)〔〕出棧9#*35#operate(’3’,’*’,’5’)10#15#return2.2.3隊(duì)列隊(duì)列〔Queue〕也是操作受限的線性表.隊(duì)列是一種先進(jìn)先出(FIFO)的線性表.(a1,a2,…,an)允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，允許插入的一端叫做隊(duì)尾〔rear〕，允許刪除的一端那么稱隊(duì)頭〔front〕。假設(shè)限制插入和刪除能在表的兩端進(jìn)行，稱此隊(duì)列為“雙向隊(duì)〞。假設(shè)限制插入在表的一端進(jìn)行，而限制刪除在表的另一端進(jìn)行,稱此隊(duì)列為“單向隊(duì)〞。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列是一種先進(jìn)先出〔FIFO)的線性表。隊(duì)列的根本運(yùn)算有以下四種:①獲得隊(duì)列的隊(duì)首結(jié)點(diǎn)之值：gethead(q,x)；讀取q隊(duì)列的隊(duì)頭元素于變量x中,隊(duì)列不變。②隊(duì)列q中插入一個(gè)結(jié)點(diǎn)：(進(jìn)隊(duì))add(q,x)；在隊(duì)尾插入一個(gè)元素x。③隊(duì)列q中刪除一個(gè)結(jié)點(diǎn)：〔出隊(duì)〕del(q)；刪除隊(duì)頭元素。④判隊(duì)列q是否為空：empty(q)；假設(shè)存儲(chǔ)空間為數(shù)組q[m]，把隊(duì)列數(shù)組的元素q[0]和q[m-1]連接起來(lái)，形成一個(gè)環(huán)形的表。初始值front=rear=0〔1〕進(jìn)隊(duì)rear=(rear+1)%m;q[rear]=x;出隊(duì)front=(front+1)%m;y=q[front];01m-1frontreara1a2a3a4(2)環(huán)形隊(duì)列的隊(duì)空和隊(duì)滿都有rear==front專門(mén)設(shè)立一個(gè)標(biāo)志符少用一個(gè)元素空間，用(rear+1)/m==front作為隊(duì)滿的判別條件循環(huán)隊(duì)列中入隊(duì)和出隊(duì)操作的具體算法intfront,rear,m;/*全局變量*/addque(intq[],intx)/*進(jìn)隊(duì)算法*/{rear=(rear+1)%m;if(rear==front)printf("Queenoverflow!\n");elseq[rear]=x;}delque(intq[])/*出隊(duì)算法*/{inty=-1;if(front==rear)printf("Queenundelflow!\n");else{front=(front+1)%m;y=q[front];}return(y);}2．鏈接存儲(chǔ)的隊(duì)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)列。一個(gè)鏈隊(duì)列需要隊(duì)頭和隊(duì)尾的兩個(gè)指針才能唯一確定。b.鏈?zhǔn)酱鎯?chǔ)的隊(duì)列(1)進(jìn)隊(duì)算法注：front,rear是全局變量

add(intx){structnode*q;q=(structnode*)malloc(LEN);q->data=x;q->next=NULL;if(front==NULL){front=q;rear=q;}else{rear->next=q;rear=q;}}(2)出隊(duì)算法注：front,rear是全局變量del(){structnode*q;inty=-1;if(front==NULL)printf(“Queennderflow!\n〞);else{q=front;y=q->data;front=q->next;free(q);}return(y);}2.2.4串串(String)也是一種特殊的線性表，即當(dāng)線性表中的元素為字符時(shí)的情形。串定義：由零個(gè)或多個(gè)字符組成的有限序列，稱為串。一般記為：s=’a1a2…an’(n>=0)線性表上的操作通常是對(duì)其中的單個(gè)元素進(jìn)行的，如插入一個(gè)元素，刪除一個(gè)元素等。對(duì)于串，經(jīng)常要對(duì)其連續(xù)的字符組進(jìn)行操作，如從正文中取一個(gè)單詞，替換一個(gè)單詞等。串的根本運(yùn)算有：求串s的長(zhǎng)度的函數(shù)len(s)；求串s的第m位置開(kāi)始且長(zhǎng)度為n的子串的函數(shù)sub(s,m,n)；求子串t在主串s中的位置的函數(shù)index(s,t)；串v的值替換所有在串s中出現(xiàn)的子串t的值的函數(shù)rep(s,t,v)及將串s2的值緊接著放在串s1的值的末尾，聯(lián)接成一個(gè)新串的函數(shù)concat(s1,s2)等。1.串的順序存儲(chǔ)用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放字符串的值。為了唯一確定串，需要設(shè)置兩個(gè)變量，一個(gè)是指向串第一個(gè)字符位置的指針sp，一個(gè)是指示串長(zhǎng)度的整型變量sl?？梢詫⒋拈L(zhǎng)度和串值一起存于內(nèi)存，也可以用一個(gè)特定字符作為串結(jié)束標(biāo)志和串值一起存放，這樣就不需要設(shè)置sl了。C語(yǔ)言就是用NULL(‘\0’)作為串結(jié)束標(biāo)志的。不同的字符所占據(jù)的內(nèi)存空間都是一個(gè)字節(jié)c o m p u t e r \0ll+1l+2……l+8圖2-2-14順序存儲(chǔ)r的串2.串的鏈?zhǔn)酱鎯?chǔ)鏈表存儲(chǔ)串值時(shí),由于串中每個(gè)數(shù)據(jù)元素是一個(gè)字符，因而存在一個(gè)結(jié)點(diǎn)大小的選擇問(wèn)題，即結(jié)點(diǎn)中是存放一個(gè)字符，還是存放多個(gè)字符.結(jié)點(diǎn)大小的選擇直接影響對(duì)串和處理效率。結(jié)點(diǎn)越小，串處理越方便，但所占內(nèi)存也隨之?dāng)U大。反之，結(jié)點(diǎn)越大，串處理越不方便，但可以節(jié)省內(nèi)存。串的根本運(yùn)算一.求串的長(zhǎng)度main(){longle;longlen(char[]);chars[30];scanf("%s",s);le=len(s);printf("len(s)=%d\n",le);}longlen(chars[]){longi=0;while(s[i]!='\0')i++;returni;}二.求子串sub(s,m,n)求串s的第m位置開(kāi)始且長(zhǎng)度為n的子串。三.求子串t在主串s中的位置index(s,t)從主串S的第一個(gè)字符起和模式t的另一個(gè)字符比較，假設(shè)相等，那么繼續(xù)逐個(gè)比較后繼字符，如果全部相等，那么匹配成功，返回子串的位置。否那么從S的第二個(gè)字符起重新開(kāi)始新的比較，直至某一步匹配成功或S結(jié)束，無(wú)法再進(jìn)行比較為止，此時(shí)返回-1作為匹配失敗的標(biāo)志。index(chars[],chart[]){inti=0,j=0;while(s[i]!='\0'&&t[j]!='\0'){if(s[i]==t[j]){i=i+1;j=j+1;}else{i=i-j+1;j=0;}}if(t[j]=='\0')return(i-j);elsereturn(-1);}四.字符串置換rep(s,t,v)以串v的值替換所有在串s中出現(xiàn)的子串t的值。五.字符串連接char*concat(char*s1,char*s2){char*p;p=s1;while(*p++);--p;while(*p++=*s2++);return(s1);}六.字符串比較intcmp(chars1[],chars2[]){inti=0,r;while(s1[i]==s2[i]&&s1[i]!='\0')i++;if(s1[i]=='\0'&&s2[i]=='\0')r=0;elser=s1[i]-s2[i];return(r);}以下是C語(yǔ)言提供的一些有關(guān)字符串的庫(kù)函數(shù)：unsignedstrlen(char*str) /*字符串長(zhǎng)度函數(shù)*/char*strcat(char*str1,char*str2)/*連接函數(shù)*/char*strcpy(char*str1,char*str2)/*拷貝函數(shù)*/

樹(shù)的根本概念樹(shù)的根結(jié)點(diǎn):是樹(shù)中一個(gè)特定的結(jié)點(diǎn)，它是沒(méi)有前趨的結(jié)點(diǎn)。結(jié)點(diǎn)的度:樹(shù)中每個(gè)結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目。度為0的結(jié)點(diǎn)為終端結(jié)點(diǎn)或葉子。度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。樹(shù)中各結(jié)點(diǎn)度的最大值稱為樹(shù)的度。子女與雙親:兄弟:同一雙親的各子女間互稱為兄弟。樹(shù)的高度(或深度):樹(shù)中結(jié)點(diǎn)的最大層次。有序樹(shù)和無(wú)序樹(shù):m(m>0)棵互不相交的樹(shù)的集合，稱為森林。樹(shù)結(jié)構(gòu)有廣泛的應(yīng)用，經(jīng)常被用來(lái)定義層次關(guān)系。/*-*+5ABCD2用樹(shù)表示家庭結(jié)構(gòu)老張張一張二張小一張小二張小三2.3.3二叉樹(shù)1.二叉樹(shù)的概念：二叉樹(shù)定義為：或?yàn)榭?，或由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)不是樹(shù)的特殊情況。它們之間最重要的區(qū)別是：二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分為左子樹(shù)和右子樹(shù)，即使在結(jié)點(diǎn)只有一棵子樹(shù)的情況下，也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。二叉樹(shù)允許空.而一般的樹(shù)至少有一個(gè)結(jié)點(diǎn)。完全二叉樹(shù)(見(jiàn)后圖)一棵二叉樹(shù)，假設(shè)所有的結(jié)點(diǎn)其度數(shù)或者為0，或者為2，那么稱為完全二叉樹(shù)。滿二叉樹(shù)：深度為K且有2K-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。此時(shí)，每一層上的結(jié)點(diǎn)數(shù)都是該層上的最大結(jié)點(diǎn)數(shù)。順序二叉樹(shù)：一棵深度為K的二叉樹(shù)，如果它的葉結(jié)點(diǎn)都在第K層或第K-1層上，且對(duì)任一結(jié)點(diǎn)，假設(shè)其右子樹(shù)中有葉結(jié)點(diǎn)在第K層，那么其左子樹(shù)的葉結(jié)點(diǎn)都應(yīng)在第K層。從上述定義可以看出，如果對(duì)一棵深度為K的滿二叉樹(shù)和一棵深度為K，具有相同個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始，從上到下，從左到右進(jìn)行連續(xù)編號(hào)那么相同位置上結(jié)點(diǎn)的編號(hào)完全相同。完全二叉樹(shù)滿二叉樹(shù)順序二叉樹(shù)2.二叉樹(shù)的性質(zhì)性質(zhì)1在二叉樹(shù)中,第i層最多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2在深度為K的二叉樹(shù)中,結(jié)點(diǎn)總數(shù)最多為2K-1個(gè)，K≥1。性質(zhì)3對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2,那么n0=n2+1。設(shè)n1為二叉樹(shù)T度為1的結(jié)點(diǎn)數(shù)。因?yàn)槎鏄?shù)T中結(jié)點(diǎn)的度數(shù)均小于或等于2，所以其結(jié)點(diǎn)總數(shù)為:n=n0+n1+n2(1)設(shè)m為二叉樹(shù)T中總的分支數(shù)目。因?yàn)槌Y(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，所以m=n-1。但這些分支是由度為1或2的結(jié)點(diǎn)射出的，所以m=n1+2n2,于是得n=n1+2n2+1(2)由(1)式和(2)式得n0=n2+1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的順序二叉樹(shù)的深度為[log2n]+1。假設(shè)樹(shù)的深度為K。那么根據(jù)性質(zhì)2和順序二叉樹(shù)為定義，有2K-1-1<n≤2k-1或2K-1≤n<2k于是K-1≤log2n<K因?yàn)镵是整數(shù)所以K=[log2n]+1性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的順序二叉樹(shù)的結(jié)點(diǎn)自上而下，自左至右連續(xù)地從1開(kāi)始編號(hào)，那么對(duì)任一結(jié)點(diǎn)i(1≤i≤n),有1)如果i=1，那么結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，那么其雙親結(jié)點(diǎn)數(shù)是[i/2]。2)如果2i>n，結(jié)點(diǎn)i無(wú)左孩子(此時(shí)結(jié)點(diǎn)i為葉子)；否那么其左孩子是結(jié)點(diǎn)2i。3)如果2i+1>n,結(jié)點(diǎn)i無(wú)右孩子；否那么其孩子是結(jié)點(diǎn)2i+1。3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)〔1〕二叉樹(shù)的順序存儲(chǔ)用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)順序二叉樹(shù)中的數(shù)據(jù)元素，編號(hào)為i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在相應(yīng)向量中序號(hào)為i的位置上。根據(jù)二叉樹(shù)性質(zhì)5，結(jié)點(diǎn)i的雙親存放在序號(hào)為[i/2]的位置上，結(jié)點(diǎn)i的左、右孩子(如果有的話)將依次存放在序號(hào)為2i和2i+1的位置上。這種方法對(duì)于一般二叉樹(shù)空間浪費(fèi)大，特別是單支樹(shù)?！?〕二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)方式當(dāng)用鏈表表示二叉樹(shù)時(shí)，結(jié)點(diǎn)至少包含數(shù)據(jù)域、左指針域和右指針域，其結(jié)點(diǎn)binode結(jié)構(gòu)如下:structbinode{intdata;structbinode*lchild;structbinode*rchild;}ABDECFGABCDEFG00000000T鏈表中會(huì)有許多空指針。4.二叉樹(shù)的遍歷所謂二叉樹(shù)的遍歷，是指樹(shù)的每個(gè)結(jié)點(diǎn)按某種規(guī)律恰好被處理〔訪問(wèn)〕一次的過(guò)程。二叉樹(shù)的遍歷是一種最根本的算法。其含義是逐一訪問(wèn)樹(shù)中的各結(jié)點(diǎn)，且只訪問(wèn)一次。從二叉樹(shù)的遞歸定義可知，二叉樹(shù)是由三個(gè)根本單元組成，即根結(jié)點(diǎn)(D)，左子樹(shù)(L)，右子樹(shù)(R)。因此，假設(shè)能依次遍歷這三局部，便是遍歷了整個(gè)二叉樹(shù)。根據(jù)排列組合，共有六種方案，即DLR，LDR，LRD，DRL，RDL，RLD。假設(shè)對(duì)左右子樹(shù)的訪問(wèn)次序限定是先左后右，那么只有前三種情況，分別稱為先序遍歷，中序遍歷和后序遍歷?；诙鏄?shù)的遞歸定義，可得下述遍歷二叉樹(shù)的遞歸算法定義。遍歷二叉樹(shù)的遞歸算法：三種方法：先序遍歷：假設(shè)二叉樹(shù)空，那么空操作：否那么：(1)處理根(2)按先序遍歷左子樹(shù)(3)按先序遍歷右子樹(shù)中序遍歷：假設(shè)二叉樹(shù)空，那么空操作：否那么：(1)按中序遍歷左子樹(shù)(2)處理根(3)按中序遍歷右子樹(shù)后序遍歷：假設(shè)二叉樹(shù)空，那么空操作：否那么：(1)按后序遍歷左子樹(shù)(2)按后序遍歷右子樹(shù)(3)處理根ABDEFGCHI對(duì)左圖的三種遍歷：先序：ABDEHICFG中序：DBHEIAFCG后序：DHIEBFGCA先序遍歷:ABDEGCF；中序遍歷:DBGEACF；后序遍歷:DGEBFCA。假設(shè)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，結(jié)點(diǎn)為:structbinode{intdata;structbinode*lchild;structbinode*rchild;}二叉樹(shù)的先序遍歷算法的遞歸過(guò)程描述如下:preorder(structbinode*t)/*先序遍歷*/{while(t!=NULL){printf("%d\n",t->data);/*處理根結(jié)點(diǎn)*/preorder(t->lchild);/*遍歷左子樹(shù)*/preordee(t->rchild);/*遍歷右子樹(shù)*/}}二叉樹(shù)的中序遍歷算法的遞歸過(guò)程描述如下:midorder(structbinode*t)/*中序遍歷*/{while(t!=NULL)

{midorder(t->lchild);/*遍歷左子樹(shù)*/printf("%d\n",t->data);midordee(t->rchild);/*遍歷右子樹(shù)*/

}

}遞歸形式的算法描述過(guò)程精練，算法的正確性也容易得到證明。缺點(diǎn)：一是執(zhí)行效率較低；二是要求編寫(xiě)程序用的高級(jí)語(yǔ)言允許過(guò)程遞歸調(diào)用。二叉樹(shù)先序遍歷的非遞歸的過(guò)程描述如下：〔此時(shí)需要用到棧。用指針數(shù)組a表示棧，記下尚待遍歷的子樹(shù)根結(jié)點(diǎn)指針，這也是棧的一種典型應(yīng)用?！硃preorder(structbinode*t){inti=0;structbinode*a[]，*p;a[0]=t;while(i>=0){p=a[i];printf("%d\n",p->data);/*處理根結(jié)點(diǎn)*/i--;if(p->rchild!=NULL){i++;a[i]=p->rchild;}/*假設(shè)右指針不為空，那么進(jìn)棧*/if(p->lchild!=NULL){i++;a[i]=p->lchild;}/*假設(shè)左指針不為空，那么進(jìn)棧*/}}二叉樹(shù)中序遍歷的非遞歸的過(guò)程描述如下：〔此時(shí)用到棧為鏈接棧。棧用于存放正在遍歷的子樹(shù)根結(jié)點(diǎn)指針?！硈tructsnode{structbinode*addr;structsnode*link;//定義鏈棧};midorder(structbinode*t)//t為樹(shù)根{structsnode*top,*p;//鏈棧指針top=NULL;while(t!=NULL||top!=NULL){while(t!=NULL){p=(structsnode*)malloc(sizeof(structsnode));p->addr=t;p->link=top;top=p;t=t->lchild;}if(top!=NULL){t=top->addr;printf(“%c〞,t->data);p=top;top=top->link;free(p);t=t->rchild;}}}實(shí)例：先建立一