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

計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章軟件工程第二章數(shù)據(jù)結(jié)構(gòu)第三章操作系統(tǒng)第四章數(shù)據(jù)庫技術(shù)第五章面向?qū)ο蟪绦蛟O(shè)計(jì)第六章計(jì)算機(jī)網(wǎng)絡(luò)第七章網(wǎng)頁設(shè)計(jì)綜合練習(xí)題計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

第一章軟件工程

本章簡單介紹軟件工程的形成和發(fā)展，重點(diǎn)介紹軟件開發(fā)的不同方法和軟件測試策略與方法，最后就軟件開發(fā)環(huán)境和軟件重用技術(shù)作一簡要介紹。1.1概述軟件工程的提出源于20世記60年代末期出現(xiàn)的“軟件危機(jī)”，并在較短的時(shí)間內(nèi)發(fā)展成一個(gè)完整的學(xué)科方向，30多年來，在理論研究和工程實(shí)踐兩個(gè)方面作了大量的工作。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.1軟件工程的形成與發(fā)展1.軟件發(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è)研討會，提出了“軟件工程”這一述語，根本目的在于克服“軟件危機(jī)”中所遇到的困難問題，從此進(jìn)入軟件工程時(shí)代。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.軟件危機(jī)(1)軟件危機(jī)的主要表現(xiàn)：軟件開發(fā)成本和進(jìn)度的估計(jì)常常很不準(zhǔn)確。用戶往往對已完成的軟件不滿意。3)軟件的質(zhì)量常被懷疑。4)軟件極難維護(hù)。5)缺乏良好的軟件文檔。6)軟件開發(fā)生產(chǎn)率提高的速度遠(yuǎn)遠(yuǎn)跟不上計(jì)算機(jī)應(yīng)用迅速普及深入的趨勢。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)軟件危機(jī)的產(chǎn)生原因一般以為,軟件危機(jī)的發(fā)生與軟件產(chǎn)品的特征和軟件產(chǎn)品開發(fā)與維護(hù)的方法不正確有關(guān)。其一：軟件是邏輯的系統(tǒng)部件而不是物理的系統(tǒng)部件，以程序和文檔形式存在，具有無形性。其二：軟件規(guī)模越來越大，功能越來越強(qiáng)，導(dǎo)致軟件結(jié)構(gòu)非常復(fù)雜。(3)解決軟件危機(jī)的途徑方法是要充分吸取和借鑒人類長期以來從事各種工程項(xiàng)目所積累的行之有效的原理、概念、技術(shù)和方法，并應(yīng)用于軟件開發(fā)的實(shí)踐中，將軟件開發(fā)變成一種組織良好、管理嚴(yán)密、各類人員協(xié)同完成的工程項(xiàng)目計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3、軟件工程

1983年IEEE定義為：“軟件工程是開發(fā)、運(yùn)行、維護(hù)和修復(fù)軟件的系統(tǒng)方法”。軟件工程學(xué)的多個(gè)分支

(1)軟件工程方法學(xué)方法學(xué)是研究軟件構(gòu)造技術(shù)的學(xué)問。一個(gè)軟件從定義、開發(fā)到維護(hù)，都需要有適當(dāng)?shù)姆椒ā?/p>

(2)軟件工程環(huán)境對最終用戶而言，環(huán)境就是他們運(yùn)行程序所使用的計(jì)算機(jī)系統(tǒng)。對于應(yīng)用軟件開發(fā)人員，環(huán)境是開發(fā)活動(dòng)的舞臺。軟件工具是環(huán)境中最活躍的成分。所謂工具，在這里泛指一切幫助開發(fā)軟件的軟件。在軟件開發(fā)的各個(gè)方面都研制了許多有效的工具。集成化工具的自動(dòng)切換，可以明顯提高軟件的生產(chǎn)率。

(3)軟件工程管理軟件工程管理的目的，是為了按照軟件的預(yù)算和進(jìn)度完成項(xiàng)目計(jì)劃，實(shí)現(xiàn)預(yù)期的經(jīng)濟(jì)和社會效益。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.1.2軟件工程范型

1、傳統(tǒng)的軟件工程范型――瀑布模型瀑布模型是1976年由B·W·Boehm提出的，是基于軟件生存周期的一種范型。它將軟件生存周期分為定義、開發(fā)、維護(hù)三個(gè)階段，每個(gè)階段又分為若干個(gè)子階段，各子階段的工作順序展開，如自上而下的瀑布。(見后圖)定義階段：分析用戶需求。問題定義：收集、分析、理解、確定用戶的要求。可行性研究：確定對問題是否有可行的解決辦法。需求分析：確定用戶對軟件系統(tǒng)的全部需求。開發(fā)階段：設(shè)計(jì)：設(shè)計(jì)軟件系統(tǒng)的模塊層次結(jié)構(gòu)、數(shù)據(jù)庫結(jié)構(gòu)、模塊控制流程等。編程：將每個(gè)模塊的控制流程紡出相應(yīng)的程序。測試：檢查并排除軟件中的錯(cuò)誤，提高軟件的可靠性。維護(hù)階段：運(yùn)行與維護(hù)：維護(hù)軟件系統(tǒng)的正常運(yùn)行。各個(gè)階段確均有相應(yīng)的文檔。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)問題定義或行性研究需求分析設(shè)計(jì)編程測試運(yùn)行與維護(hù)（目標(biāo)與范圍說明）（可行性論證報(bào)告）（需求說明書）（設(shè)計(jì)文檔）（程序）（測試報(bào)告）（維護(hù)報(bào)告）定義階段開發(fā)階段維護(hù)階段傳統(tǒng)的軟件工程范型――瀑布模型計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.2軟件開發(fā)方法兩種不同的開發(fā)方法：結(jié)構(gòu)化開發(fā)方法和面向?qū)ο蟮拈_發(fā)方法。1.2.1結(jié)構(gòu)化開發(fā)方法一、結(jié)構(gòu)化分析

1.結(jié)構(gòu)化分析方法，亦稱SA（StructuredAnalysis）方法。

(1)SA方法的特點(diǎn)：①核心思想：自頂向下和逐步求精。②基本手段：分解和抽象。分解：把大問題分割成若干小問題，然后分別解決。抽象：略去細(xì)節(jié)，先考慮問題最本質(zhì)的屬性。③使用了描述需求說明書的幾個(gè)規(guī)范工具。即數(shù)據(jù)流圖、數(shù)據(jù)詞典、小說明（加工邏輯的描述）等，使文檔規(guī)范化。

(2)數(shù)據(jù)流圖（DataFlowDiagram，簡稱DFD圖）

SA方法采用“分解”的方法來描述一個(gè)復(fù)雜的系統(tǒng)，數(shù)據(jù)流圖是描述系統(tǒng)中數(shù)據(jù)流程的圖形工具，它標(biāo)識了一個(gè)系統(tǒng)的邏輯輸入和邏輯輸出以及把邏輯輸入轉(zhuǎn)換為邏輯輸出所需要的加工處理。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1

數(shù)據(jù)流圖的基本符號：(1)數(shù)據(jù)流(2)加工(3)數(shù)據(jù)存儲(4)數(shù)據(jù)源點(diǎn)或終點(diǎn)。畫各層數(shù)據(jù)流圖應(yīng)注意的問題：(1)父圖和子圖平衡(2)子圖的編號(3)數(shù)據(jù)守恒計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)數(shù)據(jù)詞典（DataDictionary，簡稱DD）對數(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è)文件的定義。訂單文件=訂單編號+顧客名稱+產(chǎn)品名稱+訂貨數(shù)量+交貨日期（3）數(shù)據(jù)項(xiàng)條目數(shù)據(jù)項(xiàng)條目給出某個(gè)數(shù)據(jù)單項(xiàng)的定義。學(xué)號編號=1～9999（4）加工條目加工條目又稱小說明。小說明中應(yīng)精確地描述用戶要求某個(gè)加工做什么。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)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ì)出模塊相對獨(dú)立的，模塊結(jié)構(gòu)圖深度、寬度都適當(dāng)?shù)模瑔稳肟趩纬隹诘?，單一功能的模塊結(jié)構(gòu)的軟件結(jié)構(gòu)圖或軟件層次方框圖。此方法提供了描述軟件系統(tǒng)的工具，提出了評價(jià)模塊結(jié)構(gòu)圖質(zhì)量的標(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è)模塊有多個(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è)；③降低模塊接口的復(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ù)流圖都可看成是對輸入數(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ì)算機(jī)軟件技術(shù)基礎(chǔ)事務(wù)處理型:

另一類數(shù)據(jù)流圖可看成是對一個(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ù)流圖，從軟件的需求說明書弄清楚數(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ù)雜的程序流程圖都可以由以下不同類型的基本結(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)化編碼方法①對源程序的編碼要求:最基本要求是源程序的正確性，同時(shí)還要考慮其可讀性、可理解性、可測試性和可維護(hù)性。②寫程序的風(fēng)格:一個(gè)好的源程序意味著源程序代碼邏輯簡明清晰，易讀易懂。編碼原則：程序內(nèi)部文檔應(yīng)選取含義鮮明的名字，注解正確，程序清單層次清晰，布局合理。數(shù)據(jù)說明和次序應(yīng)該標(biāo)準(zhǔn)化，個(gè)別復(fù)雜的數(shù)據(jù)結(jié)構(gòu)應(yīng)加注釋。每個(gè)語句應(yīng)該簡單直接，不能為提高效率而使程序變得過份復(fù)雜。對輸入數(shù)據(jù)應(yīng)進(jìn)行合法性檢查；對輸出數(shù)據(jù)要加輸出數(shù)據(jù)的標(biāo)志。在程序編碼階段以不影響程序的清晰度和可讀性為前提，盡可能提高效率。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.2.2面向?qū)ο箝_發(fā)方法面向?qū)ο蠹夹g(shù)是一種非常實(shí)用而強(qiáng)有力的軟件開發(fā)方法。面向?qū)ο筌浖_發(fā)方法又稱OOSD（Object-OrientedSoftwareDevelopment）。OOSD包括面向?qū)ο蠓治觯∣OA）、面向?qū)ο笤O(shè)計(jì)（OOD）和面向?qū)ο蟪绦蛟O(shè)計(jì)（OOP）三個(gè)方面。其中OOP是基礎(chǔ)，OOA和OOD是應(yīng)用OOP的機(jī)制。面向?qū)ο蠓椒ê图夹g(shù)是自80年代以來逐漸形成的一種分析問題和解決問題的新方法，其基本出發(fā)點(diǎn)就是盡可能按照人類認(rèn)識世界的方法和思維方式來分析和解決問題?？陀^世界是由許多具體的事物或事件、抽象的概念和規(guī)則等組成的，因此，我們將要加以研究的事、物、概念都稱為對象。面向?qū)ο蟮姆椒ㄕ且詫ο笞鳛樽罨镜脑?，以對象作為分析問題，解決問題的核心。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1、面向?qū)ο蠓治觯∣OA）把對象作為現(xiàn)實(shí)世界的抽象表示，然后定義對象的屬性和專門操縱那些屬性的服務(wù)，屬性和服務(wù)被看成對象的特征。具有相同的屬性和服務(wù)抽象的一系列對象組成類。因此在面向?qū)ο竽Ｐ椭?，它可以包含若干類，并且它對?yīng)于模型的不同層次，因此這些類有一定的層次關(guān)系和屬性繼承關(guān)系。面向?qū)ο蠓治鲇晌鍌€(gè)主要步驟構(gòu)成：(1)標(biāo)識對象(2)標(biāo)識對象屬性(3)定義對象的服務(wù)(4)識別對象所屬的類(5)定義主題計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2、面向?qū)ο蟮脑O(shè)計(jì)（OOD）OOA是一個(gè)分類活動(dòng)，而OOD模型由主體部件、用戶界面部件、任務(wù)管理部件和數(shù)據(jù)管理部件四部分構(gòu)成。每個(gè)部件又由主題詞、對象及類、結(jié)構(gòu)、屬性和外部服務(wù)五層組成，它們分別對應(yīng)OOA中的五個(gè)活動(dòng)：定義主題詞、標(biāo)識對象、標(biāo)識類、標(biāo)識對象的屬性和標(biāo)識對象的服務(wù)。其中主體部件是整個(gè)設(shè)計(jì)的主體，它包括完成目標(biāo)軟件系統(tǒng)主要功能的所有對象，用戶界面部件給出人機(jī)交互需要的對象，任務(wù)管理部件提供協(xié)調(diào)和管理目標(biāo)軟件各個(gè)任務(wù)的對象，數(shù)據(jù)管理部件定義專用對象。要將目標(biāo)軟件系統(tǒng)中依賴于開發(fā)平臺的數(shù)據(jù)存取操作與其他功能分開，以提高對象獨(dú)立性。概括地說，OOD方法是以O(shè)OA模型為基礎(chǔ)，不斷填入和擴(kuò)展有關(guān)軟件設(shè)計(jì)的信息。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3、面向?qū)ο缶幊掏瓿蒓OD以后，將開始進(jìn)入編程階段。目前主要選取面向?qū)ο笳Z言(如C++)、基于對象的語言(如Ada)、過程式語言(如C語言)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3軟件測試與質(zhì)量保證1.3.1軟件測試原則1、基本概念軟件測試定義:軟件測試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。軟件測試分為：單元測試和綜合測試。軟件測試在軟件生存周期中橫跨了兩個(gè)階段：通常在編寫出第一個(gè)模塊之后就對它做必要的測試（稱作單元測試）。編碼與單元測試屬于軟件生存周期中的同一階段。在結(jié)束這個(gè)階段之后，對軟件系統(tǒng)還要進(jìn)行各種綜合測試，這是軟件生存周期的另一個(gè)獨(dú)立的階段，即測試階段。2、目標(biāo)和原則軟件測試的目標(biāo)可以歸納為以下幾點(diǎn)：

1.測試是為了發(fā)現(xiàn)軟件中的錯(cuò)誤而去運(yùn)行軟件的過程。

2.好的測試方案是盡可能地發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯(cuò)誤的測試方案。

3.成功的測試則是發(fā)現(xiàn)出至今未發(fā)現(xiàn)的錯(cuò)誤的測試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3.2軟件測試策略與技術(shù)1、軟件測試策略測試過程是按單元測試、組裝測試、確認(rèn)測試和系統(tǒng)測試四個(gè)步驟進(jìn)行的。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.單元測試（模塊測試）目的是發(fā)現(xiàn)模塊的子程序或過程的實(shí)際功能與該模塊的功能和接口描述是否相符，以及是否有編碼錯(cuò)誤存在。單元測試的主要內(nèi)容有:模塊接口測試；局部數(shù)據(jù)結(jié)構(gòu)測試；重要路徑測試；出錯(cuò)處理能力測試；邊界條件測試.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.組裝測試（集成測試或聯(lián)合測試）它的測試目的是為了發(fā)現(xiàn)程序結(jié)構(gòu)的錯(cuò)誤。組裝測試過程中的模塊組織方式有非漸增式和漸增式兩種。①非漸增式組裝測試：又稱一次性組裝方式或整體拼裝。測試方式是先對每個(gè)模塊分別進(jìn)行測試。然后再把所以模塊組裝在一起整體測試。其優(yōu)點(diǎn)是對各模塊的測試可以并行進(jìn)行，有利于充分利用人力，加快測試速度。其缺點(diǎn)是由于程序中不可避免的地存在涉及模塊間接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)等方面的問題，所以一次試運(yùn)行成功的可能性不大，結(jié)果是發(fā)現(xiàn)有錯(cuò)誤，但卻找不到錯(cuò)誤的產(chǎn)生原因。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)②漸增式組裝測試這種方式是對一個(gè)個(gè)模塊進(jìn)行模塊調(diào)試，然后將這些模塊逐步組裝成較大的系統(tǒng)。在組裝過程中，每連接一個(gè)模塊便進(jìn)行一次測試，直到把所有模塊集成為一個(gè)整體并進(jìn)行測試，則軟件的組裝測試完成。在漸增測試過程中，將模塊結(jié)合起來的策略有兩種：自底向上測試和自頂向下測試。自底向上測試：從程序模塊結(jié)構(gòu)的最低層模塊進(jìn)行組裝和測試。因?yàn)槟K是自底向上進(jìn)行組裝的，對給定層次的模塊的下層模塊處理功能總可以得到，所以這種測試策略不必設(shè)計(jì)樁模塊（存根模塊），但要設(shè)計(jì)驅(qū)動(dòng)模塊。

自頂向下測試：將模塊按系統(tǒng)程序結(jié)構(gòu)，沿控制層次自頂向下進(jìn)行組裝。由主控模塊開始，按照程序的層次結(jié)構(gòu)向下移動(dòng)。逐漸把各個(gè)模塊組裝起來。

計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(3)確認(rèn)測試(有效性測試)又稱有效性測試。組裝測試結(jié)束后，得到的是一個(gè)完整的軟件系統(tǒng)。這時(shí)需要進(jìn)行最后的測試，即有效性測試。有效性測試階段主要進(jìn)行的測試有：有效性測試（黑盒測試）、軟件配置復(fù)查、α測試和β測試以及驗(yàn)收測試。(4)系統(tǒng)測試系統(tǒng)測試是指將經(jīng)過測試后的軟件系統(tǒng)與計(jì)算機(jī)硬件、外設(shè)、其他支持軟件以及其他系統(tǒng)元素一起進(jìn)行測試。測試內(nèi)容主要有：功能測試、吞吐量測試、可用性測試、保密性測試、安裝測試、可恢復(fù)性測試、資料測試和程序測試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2、常用的測試方法常用的測試方法有黑盒測試和白盒測試兩種。(1)白盒測試白盒測試又稱結(jié)構(gòu)測試或邏輯驅(qū)動(dòng)測試。所謂“白盒”是指將對象看作一個(gè)打開的盒子，測試人員可利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)的信息來設(shè)計(jì)或選擇測試用例。

白盒測試主要考慮的是測試用例對程序內(nèi)部邏輯的覆蓋程度，而不考慮程序的功能。測試用例對程序的覆蓋程序從低到高分別為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋。需要說明的是，上述各種覆蓋準(zhǔn)則的側(cè)重點(diǎn)不同，覆蓋程度也不同。但它們共同的是：任何一種覆蓋都不能做到完全測試。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(2)黑盒測試黑盒測試又稱功能測試或數(shù)據(jù)驅(qū)動(dòng)測試。在這種測試方法中，程序?qū)y試者是完全透明的。測試者不考慮程序的內(nèi)部結(jié)構(gòu)和特性，就好像把程序看作一個(gè)不能打開的盒子，只根據(jù)程序的需求規(guī)格說明中的程序功能或程序的外部特性來設(shè)計(jì)測試用例。黑盒測試的方法包括：等價(jià)分類法、邊緣值分析法、因果圖法和錯(cuò)誤推測法。測試方法還有回歸測試、強(qiáng)度測試等等。每一種測試方法都各有所長，在實(shí)際測試中應(yīng)綜合使用。一般來講，通常用黑盒法設(shè)計(jì)基本的測試方案，再利用白盒法做必要的補(bǔ)充。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.3.3軟件質(zhì)量保證1、評審與測試評審和測試都是質(zhì)量保證的重要活動(dòng)。驗(yàn)證：我們制造產(chǎn)品的步驟正確嗎？確認(rèn)：我們制造的是正確的產(chǎn)品嗎？2、程序正確性證明程序正確性證明就是要通過數(shù)學(xué)的方法，證明程序具有某些需要的性質(zhì)。通過多年的研究，現(xiàn)已提出了一些有用的方法和技術(shù)，其中包括輸入——輸出斷言法、最弱前置條件法、結(jié)構(gòu)歸納法紀(jì)等幾種常用的方法。如果說程序測試是為了證明程序有錯(cuò)，則程序正確性的證明正好相反，是為了證明程序能夠完成某些預(yù)定的功能?，F(xiàn)有的證明程序正確性的技術(shù)與工具包括已研制出來的程序正確性自動(dòng)證明器，僅適用于很小的程序。要解決大程序的正確性證明，還需要進(jìn)行大量的工作。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.4軟件重用重用（Reuse）是軟件過程的一部分。為了快速做出復(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ú)立的可重用對象），這樣可以大幅度提高開發(fā)效率。

重用的真正價(jià)值在于方案、決策的重用。利用集成技術(shù)將構(gòu)件按可重用模式裝入可重用框架（相當(dāng)于建筑中的梁、柱組成的房梁）構(gòu)成一組裝式軟件過程。從代碼重用到構(gòu)件重用到設(shè)計(jì)重用到過程重用（域工程）、從初創(chuàng)到成長到成就到實(shí)用?，F(xiàn)代的軟件平臺，或多或少都提供了重用機(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ī)界面⑨測試用例⑩數(shù)據(jù)這些產(chǎn)物作為重用件要作分類、標(biāo)記，作為對象構(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)構(gòu)件都有被定義好的接口，只巴能通過這些接口來操縱構(gòu)件。(4)構(gòu)件之間可以交互。(5)構(gòu)件可以被擴(kuò)展。構(gòu)件的可繼承性使構(gòu)件能夠被擴(kuò)充和修改。目前有兩個(gè)方面的技術(shù)，一種是可視化構(gòu)件，另一種是分布式對象構(gòu)件。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.5軟件開發(fā)環(huán)境軟件開發(fā)由來已久。一臺宿主機(jī)，一個(gè)編譯（或匯編）程序，加上編輯、鏈接、裝入等少量實(shí)用程序，就構(gòu)成了早期軟件開發(fā)的舞臺。從這個(gè)意義上講，在軟件工程興起之前就有了軟件開發(fā)環(huán)境。在70年代和80年代初期，開發(fā)環(huán)境常被稱為“軟件工程環(huán)境”（簡稱SEE或SE2）或“程序設(shè)計(jì)支撐環(huán)境”?！坝?jì)算機(jī)輔助軟件工程”（簡稱CASE），是今天對開發(fā)環(huán)境最流行的稱呼。成為描述軟件開發(fā)環(huán)境與工具的最通用的名稱。另一個(gè)常見的名稱——“工作臺”（workshop）。1976年，ICSE第二屆會議在一篇文章中發(fā)表了一個(gè)基于UNIX操作系統(tǒng)的程序設(shè)計(jì)支撐環(huán)境，稱之為“UNIX程序員工作臺”（UNIXprogrammer’sworkbench，簡寫為UNIX/PWB）。這是國際上出現(xiàn)的第一個(gè)有影響的軟件開發(fā)環(huán)境。自此之后，工作臺也常被用作開發(fā)環(huán)境的同義詞。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2．集成化工具開發(fā)軟件用到兩類工具。一類工具是畫或?qū)懺诩埳系模ㄔ诓煌A段使用的各種圖形與語言；另一類則是用來“開發(fā)軟件的軟件”，又稱為“軟件工具”或CASE工具。這里討論的是后一類工具。早期的環(huán)境只配置用于編碼階段的工具，也稱為“低層”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)工具切換的“集成工具”，對軟件開發(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)境的軟、硬件平臺適應(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ì)、編程、測試、運(yùn)行維護(hù)等），每個(gè)階段有相對獨(dú)立的任務(wù)。

需求分析最常用的方法是結(jié)構(gòu)化分析方法（SA方法），SA方法適于分析大型數(shù)據(jù)處理系統(tǒng)，使用的主要工具有數(shù)據(jù)流圖和數(shù)據(jù)詞典。數(shù)據(jù)流圖以圖形形式表示軟件信息流向和信息加工，而數(shù)據(jù)詞典對這些信息和加工進(jìn)行更詳細(xì)的描述。SA方法簡單實(shí)用、易于理解、使用廣泛。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)軟件設(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)來設(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ù)的一組基本操作或過程封裝在一起，用“對象”這個(gè)概念來完整地反映客觀事物的靜態(tài)屬性和動(dòng)態(tài)屬性?！懊嫦?qū)ο蟆钡幕舅枷刖褪前岩獦?gòu)造的系統(tǒng)表示為對象的集合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

軟件測試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。軟件測試的目的是要暴露軟件系統(tǒng)中的隱含錯(cuò)誤，然后通過軟件測試找出錯(cuò)誤的原因和位置并加以改正。在軟件開發(fā)中，測試是保證軟件正確性的最后一個(gè)階段，測試需要制定測試計(jì)劃，設(shè)計(jì)測試用例，然后實(shí)施測試，測試后進(jìn)行分析評價(jià)，測試結(jié)束后，要給出測試報(bào)告。軟件測試方式分為：人工測試、動(dòng)態(tài)測試和自動(dòng)測試三種。測試過程按單元測試、組裝測試、確認(rèn)測試和系統(tǒng)測試四個(gè)步驟。

常用的測試方法有黑盒測試和白盒測試兩種。對于不同的測試方法，需要設(shè)計(jì)不同的測試用例。階段評審與測試，軟件配置管理是保證軟件質(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ù)在對象包裝下，當(dāng)今分布式應(yīng)用系統(tǒng)上已可實(shí)現(xiàn)數(shù)據(jù)集成、控制集成、表示集成。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第二章數(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ī)中的存儲方式及在數(shù)據(jù)元素集合上設(shè)立的運(yùn)算如何實(shí)現(xiàn)，這是研究數(shù)據(jù)處理的基礎(chǔ)。本章在介紹數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念后，著重討論線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖形結(jié)構(gòu)等三類數(shù)據(jù)結(jié)構(gòu)，最后介紹數(shù)據(jù)結(jié)構(gòu)中兩種特別重要的運(yùn)算-查找和排序。對數(shù)據(jù)結(jié)構(gòu)的基本操作，本章采用C語言描述。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1概述2.2線性表2.3樹型結(jié)構(gòu)2.4圖2.5查找2.6排序小結(jié)計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1概述計(jì)算機(jī)早期運(yùn)算:原始數(shù)據(jù)和結(jié)果數(shù)據(jù)不多,重點(diǎn)在于算法。計(jì)算機(jī)應(yīng)用的發(fā)展:逐漸變成對數(shù)據(jù)進(jìn)行非數(shù)值型的加工處理為主。特點(diǎn)是數(shù)據(jù)量大，而計(jì)算的工作量可能很小。數(shù)據(jù)結(jié)構(gòu)的提出：數(shù)據(jù)結(jié)構(gòu)是為研究和解決諸如數(shù)據(jù)的分類與查找、情報(bào)檢索、數(shù)據(jù)庫、企業(yè)管理、系統(tǒng)工程、圖形識別、人工智能以及日常生活等各領(lǐng)域的非數(shù)值問題而提出的理論與方法，即如何合理的組織數(shù)據(jù)，以提高算法的效率。重要性：對實(shí)現(xiàn)系統(tǒng)軟件，如操作系統(tǒng)、編譯程序和數(shù)據(jù)庫管理系統(tǒng)等均有十分重要的意義。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.1數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)：描述客觀事物的的信息（數(shù)，字符，符號等）的集合，是程序處理的對象。

數(shù)據(jù)元素：是數(shù)據(jù)集合中的個(gè)體，是構(gòu)成數(shù)據(jù)對象的基本單位，可由若干個(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ī)中的存儲方式以及在這些數(shù)據(jù)元素上定義的運(yùn)算的集合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)有時(shí)可直接稱為數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)的三種基本類型：線性表、樹和圖。分別屬于兩大類：

(一)線性結(jié)構(gòu)（線性表）各數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡單地表示出來。線性表是典型的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只按先后次序聯(lián)接。有棧、隊(duì)列、字串、數(shù)組和文件。(二）非線性結(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)在計(jì)算機(jī)存儲設(shè)備中的映象稱為數(shù)據(jù)的存儲結(jié)構(gòu)(亦稱為物理結(jié)構(gòu))。同一個(gè)邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)。最常用的二種方式是：

順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。大多數(shù)據(jù)結(jié)構(gòu)的存儲表示都采用其中的一種方式或兩種方式的結(jié)合。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.順序存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素按某種順序存放在存儲器的連續(xù)單元中。即將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，而數(shù)據(jù)元素之間的關(guān)系由存儲單元的鄰接關(guān)系唯一確定。若數(shù)據(jù)元素存放在以起始地址S開始的連續(xù)存儲單元中。則第i個(gè)元素的存儲地址：LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l假定每個(gè)元素所占的存儲空間是相同的,長度均為l。數(shù)據(jù)的這種順序存儲結(jié)構(gòu)叫做向量，以V表示，向量V的分量V[i]是數(shù)據(jù)結(jié)構(gòu)的第i個(gè)元素在存儲器中的映像。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)順序存儲的主要特點(diǎn)是：

1.結(jié)點(diǎn)中只有自身信息域，沒有連接信息域。因此存儲密度大，存儲空間利用率高；

2.可以通過計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)點(diǎn)的存儲地址L。即可以對記錄直接進(jìn)行存取；

3.插入、刪除運(yùn)算會引起大量結(jié)點(diǎn)的移動(dòng)；

4.要求存儲在一片連續(xù)的地址中。這種存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.鏈接存儲結(jié)構(gòu)

存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(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數(shù)據(jù)結(jié)構(gòu)的運(yùn)算

對一些典型數(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)來，條件可以是某個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值；5.排序:根據(jù)某一給定的條件，將數(shù)據(jù)結(jié)構(gòu)中所有的結(jié)點(diǎn)重新排列順序等。從操作的特性來看，所有這些運(yùn)算的操作可以分為二類:

一類是加工型操作：操作改變了存儲結(jié)構(gòu)的值（如插入、刪除、更新等）；

另一類是引用操作：操作只是查詢或求得結(jié)點(diǎn)的值（如檢索等）。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2線性表——最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)2.2.1線性表線性是指表中的每個(gè)元素呈線性關(guān)系，即除第一個(gè)外，都有一個(gè)直接前趨(predecessor)，同時(shí)除最后一個(gè)元素外，都僅有一個(gè)直接后繼(successor)。1.線性表的邏輯結(jié)構(gòu)線性表L用符號表示為：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,ai>|ai-1，ai∈D，2≤i≤n}。關(guān)系<ai-1,ai>給出了元素的一種先后次序。a1稱為表的線性起始結(jié)點(diǎn)，an為表的終結(jié)點(diǎn)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.線性表的存儲結(jié)構(gòu)存儲結(jié)構(gòu):順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。具有順序存儲結(jié)構(gòu)的線性表稱為順序表，即用一組地址連續(xù)的存儲單元依次存儲線性表中的每個(gè)數(shù)據(jù)元素。具有鏈接存儲結(jié)構(gòu)的線性表稱為線性鏈表。鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。通常亦稱為鏈表。常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。3.線性表的基本運(yùn)算常用的操作有:插入、刪除、修改、讀值、檢索和排序等。線性表還可以進(jìn)行一些更為復(fù)雜的操作。如將兩個(gè)或兩個(gè)以上的具有相同數(shù)據(jù)對象的線性表合并成一個(gè)線性表，將一個(gè)線性表拆成若干個(gè)線性表，復(fù)制一個(gè)線性表等等。這些較為復(fù)雜的操作都可以利用上述幾種常用的操作來實(shí)現(xiàn)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(1)順序表的操作順序表在各種高級語言里經(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è)存儲位置讓出來，存儲新元素X。

假定已有一個(gè)數(shù)組,其值是由小到大排列的,現(xiàn)插入一個(gè)新的結(jié)點(diǎn)p0,要求插入后仍能保持由小到大的順序。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)#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;}}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

當(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ù)為：計(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è)位置即可。

設(shè)線性表用一維數(shù)組a(N)存放，則在長度為n的線性表中刪除值為data元素.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)函數(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);}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)head..............an0a0a1a2(2)線性鏈表的操作單鏈表結(jié)點(diǎn)一般用結(jié)構(gòu)體說明如下：structnode{intdata;structnode*next;};

①單鏈表的插入假定已有一個(gè)鏈表的表頭為h,其data域的值是由小到大排列的,現(xiàn)插入一個(gè)新的結(jié)點(diǎn)p0,要求插入后仍能保持由小到大的順序.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)考慮:1.鏈表h若為空，則將p0的next值為NULL，并將h指向p0。2.鏈表h不是空表，則首先確定p0的插入位置。則分三種情況:①p0插在第一個(gè)結(jié)點(diǎn)之前：將p0的next指向h的第一個(gè)結(jié)點(diǎn)，然后將h指向p0。②p0插在鏈表中間：若在ai-1和ai之間插入,可將p0的next指向ai;ai-1的next指向p0.③p0插在鏈表的末尾：將最后一個(gè)結(jié)點(diǎn)的next指向p0，而使p0的next置為NULL。......p2p1p0計(jì)算機(jī)軟件技術(shù)基礎(chǔ)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);}計(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ǔ)structnode*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);}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)例：單鏈表的建立、打印和插入：#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;}}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)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);}計(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.

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計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(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計(jì)算機(jī)軟件技術(shù)基礎(chǔ)三.多項(xiàng)式相加

A(x)=3x14+2x8+1B(x)=8x14-3x10+10x6C(x)=A(x)+B(x)

設(shè)pa,pb指針（1）若指針相等，則系數(shù)相加，c(x)中建項(xiàng)（系數(shù)為0，不建）（2）若pa->exp>pb->exp復(fù)抄pa所指項(xiàng)，反之，復(fù)抄pb所指項(xiàng)。-13142810ah-1814-310106bhcofexpch-11411-3102810610papbpc計(jì)算機(jī)軟件技術(shù)基礎(chǔ)structnode1*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；/*修改指針*/}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)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);}計(jì)算機(jī)軟件技術(shù)基礎(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)鏈表計(jì)算機(jī)軟件技術(shù)基礎(chǔ)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);}p0p1h計(jì)算機(jī)軟件技術(shù)基礎(chǔ)b.刪除操作在已給定的頭結(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);}hmp1計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.2棧棧是限定在一端進(jìn)行插入與刪除的線性表。允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。例如，給定棧(a0,a1,…,an-1

）稱a0為棧底元素，an-1為棧頂元素。棧是一種后進(jìn)先出(LIFO--LastInFirstOut)或先進(jìn)后出（FILO)的線性表。在棧中，元素的插入稱為進(jìn)棧，元素的刪除稱為出棧。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.順序存儲的棧

順序棧：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?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);}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)圖2-2-8數(shù)據(jù)元素和棧頂指針之間的對應(yīng)關(guān)系計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

假設(shè)有兩個(gè)棧，我們讓它們共享一數(shù)組s[m]，因?yàn)闂５孜恢檬遣蛔儎?dòng)的，所以可將兩個(gè)棧底分別設(shè)在數(shù)組空間的兩端，然后各自向中間伸展(如下圖所示)，顯然，僅當(dāng)兩個(gè)棧頂相遇時(shí)才可能發(fā)生上溢。由于兩個(gè)棧之間可以做到互補(bǔ)余缺，使得每個(gè)棧實(shí)際可利用的最大空間大于m/2。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.鏈存儲的棧當(dāng)棧的最大容量事先不能估計(jì)時(shí)，也可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，稱為鏈棧。一個(gè)鏈棧由它的棧頂指針top唯一確定。如圖2.11所示。這里棧空的判別條件是top是否為NULL，而棧滿將不會發(fā)生,除非計(jì)算機(jī)的全部可利用空間都被占滿。對一個(gè)元素多變的棧來說，鏈?zhǔn)酱鎯Y(jié)構(gòu)似乎更適宜。棧鏈的運(yùn)算實(shí)現(xiàn)也比較簡單。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3.棧的應(yīng)用(1)子程序的調(diào)用和返回當(dāng)多個(gè)過程構(gòu)成嵌套調(diào)用時(shí)，按照后調(diào)用先返回的原則，通過棧來實(shí)現(xiàn)。(2)表達(dá)式求值棧的另一個(gè)重要的應(yīng)用是在編譯中用來求表達(dá)式的值。任何一個(gè)表達(dá)式由三部分組成：操作數(shù)、運(yùn)算符和界限符。其中，操作數(shù)可以是常量或標(biāo)識符（表示常量或變量）；運(yùn)算符有算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符等，在這里，我們只討論算術(shù)運(yùn)算符。算術(shù)運(yùn)算符的規(guī)則：界限運(yùn)算符有左，右括號(左括號運(yùn)算級最高，右括號運(yùn)算級最低)及表達(dá)式結(jié)束符#(#號的運(yùn)算級最低)。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)要正確解釋表達(dá)式，必須先了解算術(shù)四則運(yùn)算的規(guī)則。即：①先乘除,后加減；②從左計(jì)算到右；③先括號內(nèi),后括號外為實(shí)現(xiàn)算符優(yōu)先法必須使用兩個(gè)工作棧.

一個(gè)數(shù)棧（opnd），一個(gè)運(yùn)算符棧(optr)，系統(tǒng)自左至右掃描表達(dá)式，遇到操作數(shù)，則送入數(shù)棧，遇到運(yùn)算符，則把它的優(yōu)先度與當(dāng)前運(yùn)算符棧頂運(yùn)算符的優(yōu)先度比較，若大于棧頂優(yōu)先符的優(yōu)先度，則入棧，否則退棧，并以這個(gè)退棧運(yùn)算符和從數(shù)棧頂上退出的兩個(gè)操作數(shù)形成一條機(jī)器指令。這樣，一邊形成相應(yīng)的機(jī)器指令，直到掃描到結(jié)束符，所有的?？諡橹褂?jì)算機(jī)軟件技術(shù)基礎(chǔ)

計(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)彈出左括號T3(e)T3=A*T2T3EFG_***(f)進(jìn)棧后T3ET4_*(g)T4=F**GT3T5_(h)T5=E*T4T6(i)T6=T3_T5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)求表達(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)&&一對（）出棧9#*35#operate(’3’,’*’,’5’)10#15#return計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.3隊(duì)列隊(duì)列（Queue）也是操作受限的線性表.

隊(duì)列是一種先進(jìn)先出(FIFO)的線性表.(a1,a2,…,an)

允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端則稱隊(duì)頭（front）。若限制插入和刪除能在表的兩端進(jìn)行，稱此隊(duì)列為“雙向隊(duì)”。若限制插入在表的一端進(jìn)行，而限制刪除在表的另一端進(jìn)行,稱此隊(duì)列為“單向隊(duì)”。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列是一種先進(jìn)先出（FIFO)的線性表。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)隊(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)；計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.順序存儲的隊(duì)設(shè)置二個(gè)指針front(隊(duì)頭)和rear(隊(duì)尾).

存在“假溢出”現(xiàn)象，解決方法：采用循環(huán)隊(duì)列（反轉(zhuǎn)技術(shù)）計(jì)算機(jī)軟件技術(shù)基礎(chǔ)假設(shè)存儲空間為數(shù)組q[m]，把隊(duì)列數(shù)組的元素q[0]和q[m-1]連接起來，形成一個(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

專門設(shè)立一個(gè)標(biāo)志符少用一個(gè)元素空間，用(rear+1)/m==front作為隊(duì)滿的判別條件計(jì)算機(jī)軟件技術(shù)基礎(chǔ)循環(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);}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2．鏈接存儲的隊(duì)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)列。一個(gè)鏈隊(duì)列需要隊(duì)頭和隊(duì)尾的兩個(gè)指針才能唯一確定。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)b.鏈?zhǔn)酱鎯Φ年?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;}}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(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);}計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3．隊(duì)列的應(yīng)用分時(shí)操作系統(tǒng)中，多個(gè)用戶程序排成隊(duì)列，分時(shí)地循環(huán)使用CPU和主存。

緩沖技術(shù)——系統(tǒng)為了解決高速的主機(jī)和低速的輸入輸出設(shè)備之間的矛盾，在主存中開辟緩沖區(qū)，主機(jī)將要輸入或輸出的信息先送至緩沖區(qū)，然后輸入或輸出設(shè)備從緩沖區(qū)中按隊(duì)列的先進(jìn)先出原則依次取出數(shù)據(jù)，在這種情況下，主機(jī)不必等待外部設(shè)備操作完就可以繼續(xù)做其它的工作。通常，緩沖區(qū)的結(jié)構(gòu)為一個(gè)循環(huán)隊(duì)列。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2.2.4串串(String)也是一種特殊的線性表，即當(dāng)線性表中的元素為字符時(shí)的情形。串定義：由零個(gè)或多個(gè)字符組成的有限序列，稱為串。一般記為：s=’a1a2…an’(n>=0)

線性表上的操作通常是對其中的單個(gè)元素進(jìn)行的，如插入一個(gè)元素，刪除一個(gè)元素等。對于串，經(jīng)常要對其連續(xù)的字符組進(jìn)行操作，如從正文中取一個(gè)單詞，替換一個(gè)單詞等。串的基本運(yùn)算有：求串s的長度的函數(shù)len(s)；求串s的第m位置開始且長度為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)等。計(jì)算機(jī)軟件技術(shù)基礎(chǔ)1.串的順序存儲用一組地址連續(xù)的存儲單元來存放字符串的值。為了唯一確定串，需要設(shè)置兩個(gè)變量，一個(gè)是指向串第一個(gè)字符位置的指針sp，一個(gè)是指示串長度