計算機軟件技術基礎課件

計算機軟件技術基礎第一章軟件工程第二章數據結構第三章操作系統(tǒng)第四章數據庫技術第五章面向對象程序設計第六章計算機網絡第七章網頁設計綜合練習題計算機軟件技術基礎

第一章軟件工程

本章簡單介紹軟件工程的形成和發(fā)展，重點介紹軟件開發(fā)的不同方法和軟件測試策略與方法，最后就軟件開發(fā)環(huán)境和軟件重用技術作一簡要介紹。1.1概述軟件工程的提出源于20世記60年代末期出現的“軟件危機”，并在較短的時間內發(fā)展成一個完整的學科方向，30多年來，在理論研究和工程實踐兩個方面作了大量的工作。計算機軟件技術基礎1.1.1軟件工程的形成與發(fā)展1.軟件發(fā)展的三個階段軟件開發(fā)方法從機器語言編程到軟件工程方法，經歷了三個階段。

1.程序設計時期（1946年到60年代中期）生產方式是手工生產、個體勞動。只有程序，無軟件的概念。

2.軟件時期（60年代中期至70年代中期）程序不再是硬件的附屬，有軟件的概念。作坊式的生產方式已難滿足軟件生產的質量和數量上的要求。出現了“軟件危機”。3.軟件工程時期（70年代至今）

1968年、1969年北大西洋公約組織成員國的軟件工件者召開了兩個研討會，提出了“軟件工程”這一述語，根本目的在于克服“軟件危機”中所遇到的困難問題，從此進入軟件工程時代。計算機軟件技術基礎2.軟件危機(1)軟件危機的主要表現：軟件開發(fā)成本和進度的估計常常很不準確。用戶往往對已完成的軟件不滿意。3)軟件的質量常被懷疑。4)軟件極難維護。5)缺乏良好的軟件文檔。6)軟件開發(fā)生產率提高的速度遠遠跟不上計算機應用迅速普及深入的趨勢。計算機軟件技術基礎(2)軟件危機的產生原因一般以為,軟件危機的發(fā)生與軟件產品的特征和軟件產品開發(fā)與維護的方法不正確有關。其一：軟件是邏輯的系統(tǒng)部件而不是物理的系統(tǒng)部件，以程序和文檔形式存在，具有無形性。其二：軟件規(guī)模越來越大，功能越來越強，導致軟件結構非常復雜。(3)解決軟件危機的途徑方法是要充分吸取和借鑒人類長期以來從事各種工程項目所積累的行之有效的原理、概念、技術和方法，并應用于軟件開發(fā)的實踐中，將軟件開發(fā)變成一種組織良好、管理嚴密、各類人員協(xié)同完成的工程項目計算機軟件技術基礎3、軟件工程

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

(1)軟件工程方法學方法學是研究軟件構造技術的學問。一個軟件從定義、開發(fā)到維護，都需要有適當的方法。

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

(3)軟件工程管理軟件工程管理的目的，是為了按照軟件的預算和進度完成項目計劃，實現預期的經濟和社會效益。計算機軟件技術基礎1.1.2軟件工程范型

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

1.結構化分析方法，亦稱SA（StructuredAnalysis）方法。

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

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

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

數據流圖的基本符號：(1)數據流(2)加工(3)數據存儲(4)數據源點或終點。畫各層數據流圖應注意的問題：(1)父圖和子圖平衡(2)子圖的編號(3)數據守恒計算機軟件技術基礎(3)數據詞典（DataDictionary，簡稱DD）對數據流圖中包含的所有元素的定義的集合構成了數據字典。數據詞典中有四種類型的條目：數據流、文件、數據項和加工。（1）數據流條目數據流條目給出某個數據流的定義，它通常是列出該數據流的各組成數據項。如：課程=課程名+教員+教材+課程表課程表={星期幾+第幾節(jié)+教室}（2）文件條目文件條目給出某個文件的定義。訂單文件=訂單編號+顧客名稱+產品名稱+訂貨數量+交貨日期（3）數據項條目數據項條目給出某個數據單項的定義。學號編號=1～9999（4）加工條目加工條目又稱小說明。小說明中應精確地描述用戶要求某個加工做什么。計算機軟件技術基礎2、結構化設計結構化設計方法，亦稱SD（StructuredDesign）方法。是一種面向數據流的設計方法，目的在于確定軟件的結構。(1)SD方法的基本思想其基本思想是：根據SA方法中的數據流圖建立一個良好的模塊結構圖（例如SC圖或軟件層次方框圖）；運用模塊化的設計原理控制系統(tǒng)的復雜性，即設計出模塊相對獨立的，模塊結構圖深度、寬度都適當的，單入口單出口的，單一功能的模塊結構的軟件結構圖或軟件層次方框圖。此方法提供了描述軟件系統(tǒng)的工具，提出了評價模塊結構圖質量的標準，即模塊之間的聯(lián)系越松散越好，而模塊內各成分之間的聯(lián)系越緊湊越好。計算機軟件技術基礎(2)SD方法的設計原理1）模塊化:

模塊化就是把系統(tǒng)劃分為若干個模塊，從而獲得滿足問題需要的一個解的過程。2）模塊的獨立性:

模塊獨立性有兩個定性的度量標準，即內聚和耦合。耦合有六種，從小到大如下：①兩個模塊完全獨立（沒有任何聯(lián)系）；②數據耦合:即兩個模塊只通過數據進行交換；③狀態(tài)耦合:即兩個模塊之間通過控制狀態(tài)進行傳遞；④環(huán)境耦合:即兩個模塊之間通過公共環(huán)境進行數據存?。虎莨矇K耦合:即多個模塊引用一個全程數據區(qū)；⑥內容耦合:即一個模塊使用保存在另一模塊內部的數據或控制信息，或轉移進入另一個模塊中間時，或一個模塊有多個入口時。由此看出模塊間耦合性越小越好。計算機軟件技術基礎內聚有六種，從小到大如下：①偶然內聚，即一個模塊由多任務組成，這些任務之間關系松散或根本沒聯(lián)系；②邏輯內聚:即一個模塊完成的任務在邏輯上相同或相似；③時間內聚:即一個模塊所包含的任務必須在同一時間內執(zhí)行；④通信內聚:即一個模塊內所有處理元素集中于相同的數據結構；⑤順序內聚:即一個模塊中所有處理元素都是為完成同一功能而且必須順序執(zhí)行；⑥功能內聚:一個模塊所有處理都完成一個而且僅完成一個功能。內聚性給出模塊的內在聯(lián)系，因此內聚性越大越好。計算機軟件技術基礎3）模塊的設計準則

①通過模塊的分解和合并，提高模塊的獨立性；②模塊調用個數最好不要超過五個；③降低模塊接口的復雜性；④一個模塊的所有下屬模塊應該包括該模塊受某一判定影響的所有模塊的集合；⑤模塊應設計成單入口和單出口；⑥模塊的大小要適中，一般在50句左右。計算機軟件技術基礎(3)數據流圖的類型數據流圖通常分為兩大類型:轉換處理型和事務處理型.

轉換處理型:

由于大多數數據流圖都可看成是對輸入數據進行轉換而得到輸出數據的處理，因此可把這類處理抽象為轉換處理型。轉換處理過程大致分為輸入數據，變換數據和輸出數據三步；它包含的數據流有輸入流、轉換流、輸出流三個部分。在輸入流中，信息由外部形式轉換為內部形式的結果；在輸出流中，信息由內部形式的結果轉換為外部形式數據流出系統(tǒng)。轉換處理型的數據流圖。計算機軟件技術基礎事務處理型:

另一類數據流圖可看成是對一個數據流經過某種加工后，按加工的結果選擇一個輸出數據流繼續(xù)執(zhí)行的處理。這種類型的處理可以抽象為事務處理型。在事務處理中，輸入數據流稱為事務流，加工稱為事務中心，若干平行數據流稱為事務路徑。當事務流中的事務送到事務中心后，事務中心分析每一事務，根據事務處理的特點和性質選擇一個事務路徑繼續(xù)進行處理。計算機軟件技術基礎(4)SD方法的設計過程使用SD方法的基礎是數據流圖。正如前面所述，幾乎所有軟件在分析階段都可以表示為數據流圖，所以SD方法基本上可適用于任何軟件的開發(fā)工作。

用SD方法進行總體設計的過程大致如下：（1）研究、分析和審查數據流圖，從軟件的需求說明書弄清楚數據流加工的過程；（2）根據數據流圖確定數據流圖的類型；（3）從數據流圖導出系統(tǒng)的初始軟件結構圖；（4）改進初始軟件結構圖，直到符合要求為止；（5）復查。(5)軟件結構的描述方式在SD方法中，軟件結構用一種結構圖來描述，它是設計說明書的一部分。結構圖描述了軟件模塊結構，并反映了模塊和模塊間聯(lián)系等特性。計算機軟件技術基礎3、詳細設計和編碼(1)詳細設計的任務為軟件結構圖中的每一個模塊確定采用的算法和塊內數據結構，用某種選定的表達工具給出清晰的描述。(2)詳細設計的描述工具①程序流程圖也稱為程序框圖，獨立于任何一種程序設計語言，比較直觀、清晰、易于掌握。任何復雜的程序流程圖都可以由以下不同類型的基本結構組合或嵌套而成：順序結構選擇結構(IF-THEN-ELSE)

多分支選擇結構(CASE)

先判定循環(huán)結構(WHILE)

后判定循環(huán)結構(UNTIL)計算機軟件技術基礎(2)方框圖（N-S圖）：圖形描述工具。限制了隨意的控制轉移。順序結構選擇結構多分支選擇結構先判定型循環(huán)結構后判定型循環(huán)結構計算機軟件技術基礎(3)結構化編碼方法①對源程序的編碼要求:最基本要求是源程序的正確性，同時還要考慮其可讀性、可理解性、可測試性和可維護性。②寫程序的風格:一個好的源程序意味著源程序代碼邏輯簡明清晰，易讀易懂。編碼原則：程序內部文檔應選取含義鮮明的名字，注解正確，程序清單層次清晰，布局合理。數據說明和次序應該標準化，個別復雜的數據結構應加注釋。每個語句應該簡單直接，不能為提高效率而使程序變得過份復雜。對輸入數據應進行合法性檢查；對輸出數據要加輸出數據的標志。在程序編碼階段以不影響程序的清晰度和可讀性為前提，盡可能提高效率。計算機軟件技術基礎1.2.2面向對象開發(fā)方法面向對象技術是一種非常實用而強有力的軟件開發(fā)方法。面向對象軟件開發(fā)方法又稱OOSD（Object-OrientedSoftwareDevelopment）。OOSD包括面向對象分析（OOA）、面向對象設計（OOD）和面向對象程序設計（OOP）三個方面。其中OOP是基礎，OOA和OOD是應用OOP的機制。面向對象方法和技術是自80年代以來逐漸形成的一種分析問題和解決問題的新方法，其基本出發(fā)點就是盡可能按照人類認識世界的方法和思維方式來分析和解決問題?？陀^世界是由許多具體的事物或事件、抽象的概念和規(guī)則等組成的，因此，我們將要加以研究的事、物、概念都稱為對象。面向對象的方法正是以對象作為最基本的元素，以對象作為分析問題，解決問題的核心。計算機軟件技術基礎1、面向對象分析（OOA）把對象作為現實世界的抽象表示，然后定義對象的屬性和專門操縱那些屬性的服務，屬性和服務被看成對象的特征。具有相同的屬性和服務抽象的一系列對象組成類。因此在面向對象模型中，它可以包含若干類，并且它對應于模型的不同層次，因此這些類有一定的層次關系和屬性繼承關系。面向對象分析由五個主要步驟構成：(1)標識對象(2)標識對象屬性(3)定義對象的服務(4)識別對象所屬的類(5)定義主題計算機軟件技術基礎2、面向對象的設計（OOD）OOA是一個分類活動，而OOD模型由主體部件、用戶界面部件、任務管理部件和數據管理部件四部分構成。每個部件又由主題詞、對象及類、結構、屬性和外部服務五層組成，它們分別對應OOA中的五個活動：定義主題詞、標識對象、標識類、標識對象的屬性和標識對象的服務。其中主體部件是整個設計的主體，它包括完成目標軟件系統(tǒng)主要功能的所有對象，用戶界面部件給出人機交互需要的對象，任務管理部件提供協(xié)調和管理目標軟件各個任務的對象，數據管理部件定義專用對象。要將目標軟件系統(tǒng)中依賴于開發(fā)平臺的數據存取操作與其他功能分開，以提高對象獨立性。概括地說，OOD方法是以OOA模型為基礎，不斷填入和擴展有關軟件設計的信息。計算機軟件技術基礎3、面向對象編程完成OOD以后，將開始進入編程階段。目前主要選取面向對象語言(如C++)、基于對象的語言(如Ada)、過程式語言(如C語言)。計算機軟件技術基礎1.3軟件測試與質量保證1.3.1軟件測試原則1、基本概念軟件測試定義:軟件測試是為了發(fā)現錯誤而執(zhí)行程序的過程。軟件測試分為：單元測試和綜合測試。軟件測試在軟件生存周期中橫跨了兩個階段：通常在編寫出第一個模塊之后就對它做必要的測試（稱作單元測試）。編碼與單元測試屬于軟件生存周期中的同一階段。在結束這個階段之后，對軟件系統(tǒng)還要進行各種綜合測試，這是軟件生存周期的另一個獨立的階段，即測試階段。2、目標和原則軟件測試的目標可以歸納為以下幾點：

1.測試是為了發(fā)現軟件中的錯誤而去運行軟件的過程。

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

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

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

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

白盒測試主要考慮的是測試用例對程序內部邏輯的覆蓋程度，而不考慮程序的功能。測試用例對程序的覆蓋程序從低到高分別為：語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋。需要說明的是，上述各種覆蓋準則的側重點不同，覆蓋程度也不同。但它們共同的是：任何一種覆蓋都不能做到完全測試。計算機軟件技術基礎(2)黑盒測試黑盒測試又稱功能測試或數據驅動測試。在這種測試方法中，程序對測試者是完全透明的。測試者不考慮程序的內部結構和特性，就好像把程序看作一個不能打開的盒子，只根據程序的需求規(guī)格說明中的程序功能或程序的外部特性來設計測試用例。黑盒測試的方法包括：等價分類法、邊緣值分析法、因果圖法和錯誤推測法。測試方法還有回歸測試、強度測試等等。每一種測試方法都各有所長，在實際測試中應綜合使用。一般來講，通常用黑盒法設計基本的測試方案，再利用白盒法做必要的補充。計算機軟件技術基礎1.3.3軟件質量保證1、評審與測試評審和測試都是質量保證的重要活動。驗證：我們制造產品的步驟正確嗎？確認：我們制造的是正確的產品嗎？2、程序正確性證明程序正確性證明就是要通過數學的方法，證明程序具有某些需要的性質。通過多年的研究，現已提出了一些有用的方法和技術，其中包括輸入——輸出斷言法、最弱前置條件法、結構歸納法紀等幾種常用的方法。如果說程序測試是為了證明程序有錯，則程序正確性的證明正好相反，是為了證明程序能夠完成某些預定的功能?，F有的證明程序正確性的技術與工具包括已研制出來的程序正確性自動證明器，僅適用于很小的程序。要解決大程序的正確性證明，還需要進行大量的工作。計算機軟件技術基礎1.4軟件重用重用（Reuse）是軟件過程的一部分。為了快速做出復雜的應用，重用是一條捷徑。此外，重用也是當今軟件系統(tǒng)的重要特征。重用指在一個軟件項目中直接使用以前項目中的產物，而非重用某些工具，也就是把以前做過的東西納入到新項目中。1．重用過程面向對象的語言本身就提供了重用機制，如封裝、繼承、模板等。技術上可以制成可重用構件（不僅封裝數據還封裝行為，成為獨立的可重用對象），這樣可以大幅度提高開發(fā)效率。

重用的真正價值在于方案、決策的重用。利用集成技術將構件按可重用模式裝入可重用框架（相當于建筑中的梁、柱組成的房梁）構成一組裝式軟件過程。從代碼重用到構件重用到設計重用到過程重用（域工程）、從初創(chuàng)到成長到成就到實用。現代的軟件平臺，或多或少都提供了重用機制。計算機軟件技術基礎2．支持重用的環(huán)境從過程重用的觀點，以下10種軟件過程產物均可以重用：①項目計劃②費用估算③體系結構④需求模型和規(guī)格說明⑤設計⑥源代碼⑦各種文檔⑧人機界面⑨測試用例⑩數據這些產物作為重用件要作分類、標記，作為對象構件放入構件庫。在當今CIS分布系統(tǒng)上，構件庫是一個數據庫服務器，它提供訪問服務。重用環(huán)境還必須提供集成工具，使重用的構件能集成到新項目中。計算機軟件技術基礎3．構件與構件重用構件：是可重用的、具有獨立性的軟件單元，是用來構造其他軟件的部件。構件具有以下特點：(1)構件是具有獨立性的、被封裝好的、具有描述能力的軟件單元。(2)構件本身不是一個完整的應用程序。(3)構件都有被定義好的接口，只巴能通過這些接口來操縱構件。(4)構件之間可以交互。(5)構件可以被擴展。構件的可繼承性使構件能夠被擴充和修改。目前有兩個方面的技術，一種是可視化構件，另一種是分布式對象構件。計算機軟件技術基礎1.5軟件開發(fā)環(huán)境軟件開發(fā)由來已久。一臺宿主機，一個編譯（或匯編）程序，加上編輯、鏈接、裝入等少量實用程序，就構成了早期軟件開發(fā)的舞臺。從這個意義上講，在軟件工程興起之前就有了軟件開發(fā)環(huán)境。在70年代和80年代初期，開發(fā)環(huán)境常被稱為“軟件工程環(huán)境”（簡稱SEE或SE2）或“程序設計支撐環(huán)境”。“計算機輔助軟件工程”（簡稱CASE），是今天對開發(fā)環(huán)境最流行的稱呼。成為描述軟件開發(fā)環(huán)境與工具的最通用的名稱。另一個常見的名稱——“工作臺”（workshop）。1976年，ICSE第二屆會議在一篇文章中發(fā)表了一個基于UNIX操作系統(tǒng)的程序設計支撐環(huán)境，稱之為“UNIX程序員工作臺”（UNIXprogrammer’sworkbench，簡寫為UNIX/PWB）。這是國際上出現的第一個有影響的軟件開發(fā)環(huán)境。自此之后，工作臺也常被用作開發(fā)環(huán)境的同義詞。計算機軟件技術基礎2．集成化工具開發(fā)軟件用到兩類工具。一類工具是畫或寫在紙上的，包括在不同階段使用的各種圖形與語言；另一類則是用來“開發(fā)軟件的軟件”，又稱為“軟件工具”或CASE工具。這里討論的是后一類工具。早期的環(huán)境只配置用于編碼階段的工具，也稱為“低層”CASE工具。今天在軟件分析和總體設計等階段也有了許多支持開發(fā)的工具，即“高層”CASE工具。70年代出現了“工具箱”能部分地實現從一個工具到另一個工具的切換。今天，高、低層CASE工具由一組專用程序和一個用來支持工具間數據交換的環(huán)境信息庫構成的支持下，共同構成了具有統(tǒng)一的用戶界面、并能自動實現工具切換的“集成工具”，對軟件開發(fā)的自動化提供了有力的支持。CASE環(huán)境還可能包括另兩個層次。一個是環(huán)境體系結構，用于區(qū)分開發(fā)環(huán)境為單機環(huán)境或網絡環(huán)境；另一個是可移植性服務程序，它介于集成工具與宿主機之間，使集成后的CASE工具不需要作重大的修改即可與環(huán)境的軟、硬件平臺適應。計算機軟件技術基礎小結軟件工程是從工程角度來研究軟件開發(fā)的方法和技術，它是在克服軟件危機的過程中產生而發(fā)展起來的。軟件工程學是自軟件工程出現以后形成的一門新興學科。它包括的主要內容有：軟件工程方法學、軟件工程環(huán)境和軟件工程管理等多個分支。一個軟件從用戶提出開發(fā)要求，到廢棄不用為止的全過程，稱為軟件的生存周期。軟件的生存周期劃分為若干個階段（如：需求定義、軟件設計、編程、測試、運行維護等），每個階段有相對獨立的任務。

需求分析最常用的方法是結構化分析方法（SA方法），SA方法適于分析大型數據處理系統(tǒng)，使用的主要工具有數據流圖和數據詞典。數據流圖以圖形形式表示軟件信息流向和信息加工，而數據詞典對這些信息和加工進行更詳細的描述。SA方法簡單實用、易于理解、使用廣泛。計算機軟件技術基礎軟件設計可分為總體設計和詳細設計?？傮w設計通常使用結構化設計方法。詳細設計是根據結構化程序設計原則進行的，只使用順序、分支、重復三種結構來設計模塊的控制流程，使用的表示工具有程序流程圖、方框圖、PAD圖、偽碼（PDL語言）等。

軟件編程的任務是將軟件詳細設計的結果轉換成某種程序設計語言編寫的源程序。面向對象的方法是在結構化程序設計的基礎上，進一步力圖用更自然的方法反映客觀世界。在面向對象的系統(tǒng)中，將數據和使用該數據的一組基本操作或過程封裝在一起，用“對象”這個概念來完整地反映客觀事物的靜態(tài)屬性和動態(tài)屬性?！懊嫦驅ο蟆钡幕舅枷刖褪前岩獦嬙斓南到y(tǒng)表示為對象的集合。計算機軟件技術基礎

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

常用的測試方法有黑盒測試和白盒測試兩種。對于不同的測試方法，需要設計不同的測試用例。階段評審與測試，軟件配置管理是保證軟件質量的重要環(huán)節(jié)，軟件質量保證計劃是確保上述環(huán)節(jié)實施的關鍵。軟件重用和CASE集成環(huán)境是當今軟件工程技術重要的兩個方面，重用技術已從代碼重用發(fā)展到域工程，是大規(guī)模生產軟件的希望。集成技術在對象包裝下，當今分布式應用系統(tǒng)上已可實現數據集成、控制集成、表示集成。計算機軟件技術基礎第二章數據結構概述

隨著計算機應用領域的不斷擴大，非數值數據的處理變得尤為重要，這些數據的元素之間在多是相互有關的。因此，討論數據元素之間的邏輯關系、數據元素在計算機中的存儲方式及在數據元素集合上設立的運算如何實現，這是研究數據處理的基礎。本章在介紹數據結構的有關概念后，著重討論線性結構、樹型結構和圖形結構等三類數據結構，最后介紹數據結構中兩種特別重要的運算-查找和排序。對數據結構的基本操作，本章采用C語言描述。計算機軟件技術基礎2.1概述2.2線性表2.3樹型結構2.4圖2.5查找2.6排序小結計算機軟件技術基礎2.1概述計算機早期運算:原始數據和結果數據不多,重點在于算法。計算機應用的發(fā)展:逐漸變成對數據進行非數值型的加工處理為主。特點是數據量大，而計算的工作量可能很小。數據結構的提出：數據結構是為研究和解決諸如數據的分類與查找、情報檢索、數據庫、企業(yè)管理、系統(tǒng)工程、圖形識別、人工智能以及日常生活等各領域的非數值問題而提出的理論與方法，即如何合理的組織數據，以提高算法的效率。重要性：對實現系統(tǒng)軟件，如操作系統(tǒng)、編譯程序和數據庫管理系統(tǒng)等均有十分重要的意義。計算機軟件技術基礎2.1.1數據結構的概念

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

數據元素：是數據集合中的個體，是構成數據對象的基本單位，可由若干個數據項組成。

數據項：是數據的最小單位。一組數據元素具有某種結構形式。

數據結構：就是描述一組數據元素及元素間的相互關系的。數據結構描述了一組性質相同的數據元素及元素間的相互關系。用集合論給出的數據結構的定義為:

數據結構S是一個二元組：S=(D,R)。其中:D是一個數據元素的非空的有限集合。

R是定義在D上的關系的非空的有限集合數據結構概念一般包括三個方面的內容：數據元素之間的邏輯關系、數據元素在計算機中的存儲方式以及在這些數據元素上定義的運算的集合。計算機軟件技術基礎2.1.2數據的邏輯結構

數據的邏輯結構有時可直接稱為數據結構。

數據的邏輯結構的三種基本類型：線性表、樹和圖。分別屬于兩大類：

(一)線性結構（線性表）各數據元素之間的邏輯關系可以用一個線性序列簡單地表示出來。線性表是典型的線性結構，它的數據元素只按先后次序聯(lián)接。有棧、隊列、字串、數組和文件。(二）非線性結構（樹，圖）不滿足線性結構特點的數據結構稱為非線性結構。樹、圖等是非線性結構。樹中的數據元素是分層次的縱向聯(lián)接。圖中的數據元素則有各種各樣復雜聯(lián)接。其它種類的數據結構由這三種基本結構派生的。計算機軟件技術基礎2.1.3數據的物理結構數據的邏輯結構在計算機存儲設備中的映象稱為數據的存儲結構(亦稱為物理結構)。同一個邏輯結構可以有不同的存儲結構。最常用的二種方式是：

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

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

2.可以通過計算直接確定數據結構中第i個結點的存儲地址L。即可以對記錄直接進行存?。?/p>

3.插入、刪除運算會引起大量結點的移動；

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

存儲數據結構的存儲空間可以不連續(xù)，而數據元素之間的關系是由指針來確定的。主要特點是：（1）結點由兩類域組成：數據域和指針域。（2）邏輯上相鄰的結點物理上不必鄰接，既可實現線性數據結構，又可用于表示非線性數據結構。（3）插入，刪除操作靈活方便，不必移動結點，只要改變結點中的指針值即可。計算機軟件技術基礎2.1.4數據結構的運算

對一些典型數據結構中的結點進行操作處理。1.插入:在數據結構中的指定位置上插入新的數據元素；2.刪除:根據一定的條件,將某個結點從數據結構中刪除；3.更新:更新數據結構中某個指定結點的值；4.檢索:在給定的數據結構中,找出滿足一定條件的結點來，條件可以是某個或幾個數據項的值；5.排序:根據某一給定的條件，將數據結構中所有的結點重新排列順序等。從操作的特性來看，所有這些運算的操作可以分為二類:

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

另一類是引用操作：操作只是查詢或求得結點的值（如檢索等）。計算機軟件技術基礎2.2線性表——最簡單，最常用的一種數據結構2.2.1線性表線性是指表中的每個元素呈線性關系，即除第一個外，都有一個直接前趨(predecessor)，同時除最后一個元素外，都僅有一個直接后繼(successor)。1.線性表的邏輯結構線性表L用符號表示為：L=(a1，a2，a3，..ai...，an)

線性表也可以正式定義為：若數據結構L=（D，R）是一個線性表，則：D是包括a1,a2,a3.....an等元素的集合。R中只包含一個關系，即R={<ai-1,ai>|ai-1，ai∈D，2≤i≤n}。關系<ai-1,ai>給出了元素的一種先后次序。a1稱為表的線性起始結點，an為表的終結點。計算機軟件技術基礎2.線性表的存儲結構存儲結構:順序存儲結構和鏈接存儲結構。具有順序存儲結構的線性表稱為順序表，即用一組地址連續(xù)的存儲單元依次存儲線性表中的每個數據元素。具有鏈接存儲結構的線性表稱為線性鏈表。鏈式存儲結構是用一組任意的存儲單元來存儲線性表中數據元素的，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。通常亦稱為鏈表。常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。3.線性表的基本運算常用的操作有:插入、刪除、修改、讀值、檢索和排序等。線性表還可以進行一些更為復雜的操作。如將兩個或兩個以上的具有相同數據對象的線性表合并成一個線性表，將一個線性表拆成若干個線性表，復制一個線性表等等。這些較為復雜的操作都可以利用上述幾種常用的操作來實現。計算機軟件技術基礎(1)順序表的操作順序表在各種高級語言里經常用一維數組實現。#defineMAXSIZE100//數組中元素個數的最大值intlist[MAXSIZE],n;//n為線性表中當前的結點數①插入運算插入運算是在線性表的第i個元素和第i+1個元素之間插入一個一個新元素x。

為了實現這個操作，必須把第i+1個元素到第n個元素依次向后移位一個位置，以便把第i+1個存儲位置讓出來，存儲新元素X。

假定已有一個數組,其值是由小到大排列的,現插入一個新的結點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;}}計算機軟件技術基礎

當i=0時,新結點x插在a1之前,這時需移動線性表中的所有元素。

當i=n-1時,新結點x插入在an-1之后,這時不需移動線性表中的元素。

在具有n個結點的線性表中，插入一個新結點時，其執(zhí)行時間主要化費在移動結點的循環(huán)上。移動結點的平均次數為：計算機軟件技術基礎②

刪除運算線性表的刪除運算是指將線性表中第i個數據元素除掉，即把長度為n的線性表（a1,a2,...ai-1,ai,ai+1,...an)中的ai除去,變成長度為n-1的線性表（a1,a2,...ai-1,ai+1,...an)。這只需將第i+1數據元素到n數據元素依次向前移動一個位置即可。

設線性表用一維數組a(N)存放，則在長度為n的線性表中刪除值為data元素.計算機軟件技術基礎函數如下：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];/*數據元素依次向前移動*/a[n-1]=0;n--;k=1;break;}if(k==0)printf("Nothiselement!");return(n);}計算機軟件技術基礎head..............an0a0a1a2(2)線性鏈表的操作單鏈表結點一般用結構體說明如下：structnode{intdata;structnode*next;};

①單鏈表的插入假定已有一個鏈表的表頭為h,其data域的值是由小到大排列的,現插入一個新的結點p0,要求插入后仍能保持由小到大的順序.計算機軟件技術基礎考慮:1.鏈表h若為空，則將p0的next值為NULL，并將h指向p0。2.鏈表h不是空表，則首先確定p0的插入位置。則分三種情況:①p0插在第一個結點之前：將p0的next指向h的第一個結點，然后將h指向p0。②p0插在鏈表中間：若在ai-1和ai之間插入,可將p0的next指向ai;ai-1的next指向p0.③p0插在鏈表的末尾：將最后一個結點的next指向p0，而使p0的next置為NULL。......p2p1p0計算機軟件技術基礎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);}計算機軟件技術基礎②單鏈表的刪除在已給定的鏈表h中,刪除data值為m的結點。

1.鏈表h是否指向空表,如果是空表,則報告空表信息。2.若h不為空:①一直查到表尾還找不到該結點,則在此鏈表中無此結點。②查找到該結點:

若該結點在頭部,則h指向該結點的下一個結點。若該結點在中部,則前趨結點的指針指向后趨結點。若該結點在尾部,則前趨結點的指針為NULL。p2p1計算機軟件技術基礎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);}計算機軟件技術基礎實例：單鏈表的建立、打印和插入：#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)鏈表的最后一個結點的指針域不為NULL，而是指向頭結點，整個鏈表形成一個環(huán)。（2）在循環(huán)鏈表中設置一個表頭結點，使空表與非空表的運算統(tǒng)一起來。(a)非空表(b)空表圖2-2-5帶表頭結點的循環(huán)鏈表計算機軟件技術基礎（1）插入算法：在頭指針為h的循環(huán)鏈表中元素b的結點前插入新元素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;/*尋找指定元素的前一結點*/q->next=p->next;p->next=q;return(h);}hpqba計算機軟件技術基礎(2)刪除算法：在頭指針為h的循環(huán)鏈表中刪除元素為b的結點

delcst(structnode*h,intb){structnode*p,*q;p=h;while((p->next!=h)&&((p->next)->data!=b))p=p->next;/*尋找指定元素的前一結點*/if(p->next==h){printf(“Nothisnodeinthelist\n”);return(h);}q=p->next;p->next=q->next;free(q);return(h);}bpq計算機軟件技術基礎三.多項式相加

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

設pa,pb指針（1）若指針相等，則系數相加，c(x)中建項（系數為0，不建）（2）若pa->exp>pb->exp復抄pa所指項，反之，復抄pb所指項。-13142810ah-1814-310106bhcofexpch-11411-3102810610papbpc計算機軟件技術基礎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;/*建立新表頭結點*/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;/*系數相加*/pa=pa->next;pb=pb->next；/*修改指針*/}計算機軟件技術基礎elseif(pa->exp>pb->exp){x=pa->cof;e=pa->exp;/*復抄A(x)*/pa=pa->next;}else{x=pb->cof;e=pb->exp;/*復抄B(x)*/pb=pb->next;}if(x!=0)/*形成新結點鏈入C(x)*/{pp=(structnode1*)malloc(LEN);pp->cof=x;pp->exp=e;pp->next=ch;pc->next=pp;pc=pp;}}return(ch);}計算機軟件技術基礎

多重鏈表:每個結點均有兩個或兩個以上指針的鏈表。雙重鏈表設兩個指針域：一個指向后繼結點，另一個指向前趨結點。 structnode{intdata;structnode*prio;structnode*next;}

圖2-2-6帶表頭結點的雙向循環(huán)鏈表計算機軟件技術基礎a.插入運算在已由小到大排列的帶表頭結點的雙向循環(huán)鏈表h中，插入一個新的結點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計算機軟件技術基礎b.刪除操作在已給定的頭結點h的雙向鏈表中，刪除一個data值為m的結點。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計算機軟件技術基礎2.2.2棧棧是限定在一端進行插入與刪除的線性表。允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。例如，給定棧(a0,a1,…,an-1

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

順序棧：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂的數據元素,同時設指針top指示棧頂元素的當前位置。

假設用一維數組s[max]表示棧，指針top指向棧頂元素.s[0]為最早進入棧的元素，s[top]為最遲進入棧的元素。當top=max-1時，為滿棧.

初始化top=-1注：top,max為全局變量（1）進棧

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數據元素和棧頂指針之間的對應關系計算機軟件技術基礎

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

一個數棧（opnd），一個運算符棧(optr)，系統(tǒng)自左至右掃描表達式，遇到操作數，則送入數棧，遇到運算符，則把它的優(yōu)先度與當前運算符棧頂運算符的優(yōu)先度比較，若大于棧頂優(yōu)先符的優(yōu)先度，則入棧，否則退棧，并以這個退棧運算符和從數棧頂上退出的兩個操作數形成一條機器指令。這樣，一邊形成相應的機器指令，直到掃描到結束符，所有的棧空為止計算機軟件技術基礎

計算表達式運算符:**/*+-X=A*(B+C/D)-E*F**G

優(yōu)先數:43322ABCDOptrOpnd(a)進棧后*（+/ABT1*(+(b)T1=C/DAT2*((c)T2=B+T1AT2*(d)彈出左括號T3(e)T3=A*T2T3EFG_***(f)進棧后T3ET4_*(g)T4=F**GT3T5_(h)T5=E*T4T6(i)T6=T3_T5計算機軟件技術基礎求表達式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計算機軟件技術基礎2.2.3隊列隊列（Queue）也是操作受限的線性表.

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

允許在表的一端進行插入，而在表的另一端進行刪除，允許插入的一端叫做隊尾（rear），允許刪除的一端則稱隊頭（front）。若限制插入和刪除能在表的兩端進行，稱此隊列為“雙向隊”。若限制插入在表的一端進行，而限制刪除在表的另一端進行,稱此隊列為“單向隊”。允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。隊列是一種先進先出（FIFO)的線性表。計算機軟件技術基礎隊列的基本運算有以下四種:①獲得隊列的隊首結點之值：

gethead(q,x)；讀取q隊列的隊頭元素于變量x中,隊列不變。②隊列q中插入一個結點：(進隊)

add(q,x)；在隊尾插入一個元素x。③隊列q中刪除一個結點：（出隊）

del(q)；刪除隊頭元素。④判隊列q是否為空：

empty(q)；計算機軟件技術基礎1.順序存儲的隊設置二個指針front(隊頭)和rear(隊尾).

存在“假溢出”現象，解決方法：采用循環(huán)隊列（反轉技術）計算機軟件技術基礎假設存儲空間為數組q[m]，把隊列數組的元素q[0]和q[m-1]連接起來，形成一個環(huán)形的表。初始值front=rear=0（1）進隊

rear=(rear+1)%m;q[rear]=x;

出隊

front=(front+1)%m;y=q[front];01m-1frontreara1a2a3a4(2)環(huán)形隊列的隊空和隊滿都有rear==front

專門設立一個標志符少用一個元素空間，用(rear+1)/m==front作為隊滿的判別條件計算機軟件技術基礎循環(huán)隊列中入隊和出隊操作的具體算法intfront,rear,m;/*全局變量*/addque(intq[],intx)/*進隊算法*/{rear=(rear+1)%m;if(rear==front)printf("Queenoverflow!\n");elseq[rear]=x;}delque(intq[])/*出隊算法*/{inty=-1;if(front==rear)printf("Queenundelflow!\n");else{front=(front+1)%m;y=q[front];}return(y);}計算機軟件技術基礎2．鏈接存儲的隊采用鏈式存儲結構的隊列稱為鏈隊列。一個鏈隊列需要隊頭和隊尾的兩個指針才能唯一確定。計算機軟件技術基礎b.鏈式存儲的隊列

(1)進隊算法注：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)出隊算法注：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);}計算機軟件技術基礎3．隊列的應用分時操作系統(tǒng)中，多個用戶程序排成隊列，分時地循環(huán)使用CPU和主存。

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

線性表上的操作通常是對其中的單個元素進行的，如插入一個元素，刪除一個元素等。對于串，經常要對其連續(xù)的字符組進行操作，如從正文中取一個單詞，替換一個單詞等。串的基本運算有：求串s的長度的函數len(s)；求串s的第m位置開始且長度為n的子串的函數sub(s,m,n)；求子串t在主串s中的位置的函數index(s,t)；串v的值替換所有在串s中出現的子串t的值的函數rep(s,t,v)及將串s2的值緊接著放在串s1的值的末尾，聯(lián)接成一個新串的函數concat(s1,s2)等。計算機軟件技術基礎1.串的順序存儲用一組地址連續(xù)的存儲單元來存放字符串的值。為了唯一確定串，需要設置兩個變量，一個是指向串第一個字符位置的指針sp，一個是指示串長度