第3章 計算機軟件基礎(chǔ)曲阜師范大學計算機科學學院2/6/20231計算機軟件基礎(chǔ)內(nèi)容摘要

計算機系統(tǒng)由硬件與軟件組成，硬件是基礎(chǔ)，軟件是靈魂。軟件是指為運行、維護、管理及應(yīng)用計算機所編制的所有程序和程序運行所需要的數(shù)據(jù)及其文檔資料的總稱，簡而言之，軟件=程序+數(shù)據(jù)+文檔。 本章主要介紹軟件基礎(chǔ)知識：算法基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，程序設(shè)計基礎(chǔ)和軟件工程基礎(chǔ)等。2/6/20232計算機軟件基礎(chǔ)學習目標

理解算法、算法的設(shè)計以及評價算法優(yōu)劣的概念；了解程序設(shè)計語言的概念和程序設(shè)計的過程；理解數(shù)據(jù)結(jié)構(gòu)的基本概念和幾種典型的數(shù)據(jù)結(jié)構(gòu)；了解軟件工程中有關(guān)概念，熟悉軟件生存周期、軟件開發(fā)模型和軟件開發(fā)方法的內(nèi)容。為進一步學習本書以下各章內(nèi)容和以后的各門專業(yè)課程學習打好基礎(chǔ)。

2/6/20233計算機軟件基礎(chǔ)主要內(nèi)容3.1算法基礎(chǔ)3.2程序設(shè)計基礎(chǔ)3.3數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)3.4軟件工程基礎(chǔ)2/6/20234計算機軟件基礎(chǔ)3.1 算法基礎(chǔ) 算法是計算機科學中最重要的核心概念，算法設(shè)計的好壞直接影響軟件的性能。

數(shù)值計算算法:“計算方法”課程是研究求線性代數(shù)方程組、高次代數(shù)方程、常微分方程數(shù)值解以及計算數(shù)值微分、數(shù)值積分算法的課程。

非數(shù)值計算算法:“算法設(shè)計與分析”課程研究解決線性規(guī)劃、動態(tài)規(guī)劃等典型問題的算法設(shè)計問題；“數(shù)據(jù)結(jié)構(gòu)”課程研究了各種排序與查找算法等。2/6/20235計算機軟件基礎(chǔ)3.1.1算法及其性質(zhì)算法：為解決一個問題而采取的方法和步驟。算法的特性：

（1）有窮性：有窮步驟；（2）確定性：無歧義性；（3）輸入：0或多個；（4）輸出：1或多個；（5）可行性：在有限時間內(nèi)完成。 綜上可知，算法是精確定義的一系列規(guī)則，這些規(guī)則指出如何經(jīng)過有限步驟在有限的時間內(nèi)產(chǎn)生出所求問題的解。2/6/20236計算機軟件基礎(chǔ)3.1.2算法的描述算法是對解決問題方法的精確描述，常用的描述工具有:自然語言流程圖算法描述語言計算機程序設(shè)計語言

2/6/20237計算機軟件基礎(chǔ)3.1.3算法設(shè)計舉例

例3-1給定兩個正整數(shù)m和n，試寫出求它們的最大公因子的算法。解：歐幾里德算法用自然語言表述如下： 第1步：讀入兩個正整數(shù)m和n（設(shè)m>n）。 第2步：求m除以n的余數(shù)r＝mod（m,n）。 第3步：用n的值取代m，用r的值取代n。 第4步：判別r的值是否為零，如果r＝0，則m為最大公因子；否則返回第2步。 第5步：輸出m的值，即為最大公因子。2/6/20238計算機軟件基礎(chǔ)

開始

輸入m，n

r←mod(m,n)

m←nn←rr≠0結(jié)束Y

輸出mN歐幾里算法流程圖：2/6/20239計算機軟件基礎(chǔ)歐幾里德算法用算法描述語言表示PROCEDUREEuclid BEGINREAD（m,n）;REPEATr:=求m除以n的余數(shù);m:=n;n:=r;UNTILr＝0; WRITE(m)；

END2/6/202310計算機軟件基礎(chǔ)歐幾里德算法用C語言表示main（）{

Intm,n,r；

printf(“請輸入兩個正整數(shù)m和n:”);

scanf(“%d%d”,&m,&n);/*讀入正整數(shù)m和n*/ while（n!=0）

{r=m%n；/*求m除以n的余數(shù)*/m=n；/*用n的值取代m*/n=r；/*用r的值取代n*/}

printf(“最大公因子是:%d\n”,m)；}2/6/202311計算機軟件基礎(chǔ)3.1.4怎樣衡量算法的優(yōu)劣 正確性是對算法的基本要求。除此之外，一般衡量算法的優(yōu)劣以下3個方面來考慮。（1）算法的時間特性（2）算法的空間特性（3）算法的易理解性2/6/202312計算機軟件基礎(chǔ)3.1.4怎樣衡量算法的優(yōu)劣 設(shè)計算法時，還要注意以下幾點：（1）通用性。一個算法總是針對某類問題設(shè)計的，所以對于求解某類問題中的任何一個問題應(yīng)該是有效的。（2）確定性。算法中的每個步驟都是確定的，在什么情況下做什么都非常明確，沒有含糊不清的地方。（3）有限性。一個算法在執(zhí)行時，必須經(jīng)過有限步后停下來，結(jié)束算法執(zhí)行，給出結(jié)果，而不能無限地執(zhí)行下去。2/6/202313計算機軟件基礎(chǔ)3.2 程序設(shè)計基礎(chǔ) 程序由計算機基本的操作指令組成，計算機所有的指令稱為機器的指令系統(tǒng)。程序中的每一步都由程序員用計算機能夠理解的計算機語言編寫而成。2/6/202314計算機軟件基礎(chǔ)主要內(nèi)容3.2.1 程序設(shè)計語言3.2.2 結(jié)構(gòu)化程序設(shè)計3.2.3 程序設(shè)計步驟2/6/202315計算機軟件基礎(chǔ)3.2.1程序設(shè)計語言 人們針對不同的應(yīng)用領(lǐng)域開發(fā)出了幾百種編程語言，隨著計算機技術(shù)的發(fā)展，程序設(shè)計語言也不斷地變化、發(fā)展，新的語言不斷涌現(xiàn)，老的語言不斷發(fā)展、改進，當然有些語言也逐步被淘汰。程序設(shè)計語言向著易學、易用、描述問題的能力越來越強的方向發(fā)展。

2/6/202316計算機軟件基礎(chǔ)1．程序設(shè)計語言的特點和分類（1）機器語言——第一代語言 機器語言是二進制形式的計算機能直接執(zhí)行的低級語言。它是由機器指令組成的語言，對應(yīng)不同的機器就有不同的機器語言。機器語言對人來說既難理解又難掌握，編出的程序不易查錯糾錯。計算機剛出現(xiàn)時用的是機器語言。2/6/202317計算機軟件基礎(chǔ)（2）匯編語言—第二代語言 匯編語言比機器語言直觀，它的每一條符號指令與相應(yīng)的機器指令有對應(yīng)關(guān)系，同時又增加了一些宏、符號地址等功能。 使用匯編語言編寫的程序稱為匯編語言程序，它要經(jīng)過匯編系統(tǒng)翻譯成機器語言后才能執(zhí)行。例如，微機上常用的Microsoft的宏匯編語言MASM。2/6/202318計算機軟件基礎(chǔ)（3）高級程序設(shè)計語言—第三代語言 高級程序設(shè)計語言種類很多，依據(jù)語言的性質(zhì)它們可以分為過程性語言、面向?qū)ο笳Z言和專用語言三類。2/6/202319計算機軟件基礎(chǔ)1) 過程性語言 過程性的編程語言適合于那些順序執(zhí)行的算法。用過程性語言編寫的程序有一個起點和一個終點，程序從起點到終點執(zhí)行的流程是直線型的。2/6/202320計算機軟件基礎(chǔ)1）過程性語言BASIC是為初級編程者設(shè)計的，自從1964年問世以來，已經(jīng)出現(xiàn)了幾種流行的版本，包括GW-BASIC，QBASIC，TurboBASIC等，它在PC機上得到廣泛應(yīng)用。它以簡單易學為主要特點。COBOL是發(fā)展于20世紀60年代的一種語言，適合于大型計算機系統(tǒng)上的事務(wù)處理。COBOL是編譯執(zhí)行的過程性高級語言，主要被一些專業(yè)程序員用來開發(fā)和維護大型商業(yè)集團的復雜程序。2/6/202321計算機軟件基礎(chǔ)1）過程性語言FORTRAN語言它出現(xiàn)于1954年，是出現(xiàn)最早的高級編程語言之一，有著非常廣泛的用戶群，對于數(shù)值計算的應(yīng)用，至今仍然是一種可選的語言。2/6/202322計算機軟件基礎(chǔ)1）過程性語言Pascal語言開發(fā)于1971年，主要用于結(jié)構(gòu)化程序設(shè)計的教學，現(xiàn)在在科學、工程計算領(lǐng)域和系統(tǒng)程序設(shè)計方面得到廣泛使用，各種計算機系統(tǒng)中都已配置了Pascal語言。在微機上用的TurboPascal語言就是一種開發(fā)能力很強的語言。2/6/202323計算機軟件基礎(chǔ)1）過程性語言C語言是20世紀70年代初作為設(shè)計UNIX操作系統(tǒng)的語言而研制的。C語言具有很強的功能而且十分靈活，以其高效、簡潔、可移植性強等特點受到計算機用戶的青睞。它還具有類似匯編語言的特性，使程序員能“最接近機器”。目前流行的TurboC語言是在微機上運行的，它的集成環(huán)境包含有編輯、編譯、連接、運行和調(diào)試程序所需的一切工具。2/6/202324計算機軟件基礎(chǔ)2）面向?qū)ο笳Z言 面向?qū)ο蟮某绦蛟O(shè)計語言是建立在用對象編程方法的基礎(chǔ)上的。程序被看成是正在進行通信的若干對象的集合。程序設(shè)計就是定義對象、建立對象間的通信關(guān)系。程序運行的結(jié)果就是將對象集的初始狀態(tài)變成終結(jié)狀態(tài)（目標狀態(tài)），程序中的輸入即是對象間發(fā)消息（通信），而輸出則是程序中的對象向顯示器（或打印機）發(fā)消息（通信）的結(jié)果。2/6/202325計算機軟件基礎(chǔ)2）面向?qū)ο笳Z言

20世紀70年代以來，盡管出現(xiàn)了十多種面向?qū)ο蟮某绦蛟O(shè)計語言，但最有生命力的當屬VisualBasic、C++、Java等。 微軟的VisualBasic（VB）是綜合性的且功能強大的編程語言，具有圖形設(shè)計工具、結(jié)構(gòu)化的事件驅(qū)動編程模式，使用戶可以既快又簡便地編制出Windows下的各種應(yīng)用程序。2/6/202326計算機軟件基礎(chǔ)2）面向?qū)ο笳Z言

C++成為當今最受歡迎的面向?qū)ο蟪绦蛟O(shè)計語言之一，因為它既融合了面向?qū)ο蟮哪芰Γ峙cC語言兼容，保留了C語言的許多重要特性。這就維護了大量開發(fā)的C庫、C工具以及C源程序的完整性，使C程序員不必放棄自己已經(jīng)十分熟悉的C語言，只要補充學習C++提供的那些面向?qū)ο蟮男赂拍罴纯?。目前常用的有BorlandC++版和VisualC++版。2/6/202327計算機軟件基礎(chǔ)2）面向?qū)ο笳Z言

Java語言是20世紀90年代新出現(xiàn)的面向?qū)ο蟮恼Z言，它與C++很相似，但更適用于網(wǎng)絡(luò)應(yīng)用。Java是一種獨立于平臺的語言，Java程序不但能在微機的Windows環(huán)境下運行，還同樣能運行在其他機器的Macintosh和UNIX環(huán)境下，對于Java程序可以說“一次編寫，多次使用”。近幾年廣泛而成功的應(yīng)用，證明它將推動Internet和網(wǎng)絡(luò)的發(fā)展。2/6/202328計算機軟件基礎(chǔ)3）專用語言 專用語言是為特殊的應(yīng)用而設(shè)計的語言。今天仍有數(shù)百種專用語言在流通，最有代表性的包括LISP、Prolog、APL和Forth。LISP和Prolog適用于人工智能領(lǐng)域，特別是關(guān)于知識表示和專家系統(tǒng)構(gòu)造；APL是為數(shù)組和向量運算設(shè)計的簡潔而強有力的語言；Forth是為開發(fā)微處理機軟件設(shè)計的語言，它支持用戶自定義函數(shù)并以面向堆棧方式執(zhí)行，以提高速度和節(jié)省內(nèi)存。2/6/202329計算機軟件基礎(chǔ)（4）第四代語言 第四代語言（4GL）上升到更高的一個抽象層次，盡管還用不同的語法表示程序結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)，但已不再涉及太多的算法性細節(jié)。迄今，使用最廣的第四代語言是數(shù)據(jù)庫查詢語言，它支持用戶以復雜的方式操作數(shù)據(jù)庫。最流行的SQL（StructuredQueryLanguage）結(jié)構(gòu)化查詢語言，支持數(shù)據(jù)庫的定義和操作。它功能強大，簡單易學。2/6/202330計算機軟件基礎(chǔ)（4）第四代語言 程序生成器（ProgramGenerators）代表更為復雜的一類4GL，它只需要很少的語句就可生成完整的第三代語言程序，它不必依賴預(yù)先定義的數(shù)據(jù)庫作為它的著手點。 此外，一些決策支持語言（DecisionSupportLanguage）、原型語言（PrototypingLanguage）、形式化規(guī)格說明語言（FormalSpecificationLanguage）也被認為屬于4GL的范疇。2/6/202331計算機軟件基礎(chǔ)2．程序設(shè)計語言的選擇 一項任務(wù)可以用多種編程語言來實現(xiàn),當你為一項工程選擇程序設(shè)計語言時，主要考慮以下幾個因素：（1）應(yīng)用領(lǐng)域；（2）算法和計算復雜性；（3）數(shù)據(jù)結(jié)構(gòu)復雜性；（4）軟件運行環(huán)境；（5）性能方面的需要與實現(xiàn)的條件；（6）軟件開發(fā)組成員是否都精通這門語言。2/6/202332計算機軟件基礎(chǔ)2．程序設(shè)計語言的選擇 項目所屬的應(yīng)用領(lǐng)域常常作為首要考慮的因素，例如，C語言經(jīng)常用于系統(tǒng)軟件的開發(fā)，F(xiàn)ORTRAN在工程及科學計算領(lǐng)域占主導地位（當然Pascal、BASIC、C也廣為使用），數(shù)據(jù)庫管理系統(tǒng)在信息處理領(lǐng)域廣泛使用（其中SQL使用較廣），匯編語言在工業(yè)控制領(lǐng)域被廣泛使用，面向?qū)ο蟮恼Z言C++正被用來開發(fā)大型的軟件系統(tǒng)，Java語言正在網(wǎng)絡(luò)應(yīng)用方面發(fā)揮作用等。2/6/202333計算機軟件基礎(chǔ)3.2.2結(jié)構(gòu)化程序設(shè)計 程序的編寫就是用程序設(shè)計語言把算法程序化。程序員應(yīng)該根據(jù)算法的要求，選擇一種程序設(shè)計語言，對算法進行編碼。對該程序設(shè)計語言，必須要深刻地理解、熟練地掌握、正確地運用，以便能編出高質(zhì)量的程序代碼。2/6/202334計算機軟件基礎(chǔ)編寫程序的基本要求語法上的正確性語義的正確性2/6/202335計算機軟件基礎(chǔ)高質(zhì)量程序的特點運行速度快占用存儲空間小可靠性高易懂性2/6/202336計算機軟件基礎(chǔ)1．三種基本的控制結(jié)構(gòu)（1）順序控制結(jié)構(gòu)（2）選擇控制結(jié)構(gòu)（3）重復控制結(jié)構(gòu)2/6/202337計算機軟件基礎(chǔ)三種基本控制結(jié)構(gòu)共同點（1）只有一個入口（2）只有一個出口（3）結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行（4）結(jié)構(gòu)內(nèi)沒有死循環(huán)（無終止的循環(huán)）2/6/202338計算機軟件基礎(chǔ)2．程序設(shè)計風格（1）文檔化（documentation）要有效、適當?shù)厥褂米⑨尅Ｒ褂煤x鮮明的符號名。（2）格式化（layout）：盡量使程序布局合理、清晰、明了。恰當?shù)乩每崭?、空行和縮進。自然的程序段之間用空行分開。2/6/202339計算機軟件基礎(chǔ)2．程序設(shè)計風格（3）模塊化 把復雜的程序分解為功能單一的程序模塊，每一個程序模塊只完成一個獨立的功能，模塊之間盡量減少聯(lián)系，即高內(nèi)聚、低耦合。2/6/202340計算機軟件基礎(chǔ)3.2.3程序設(shè)計步驟 設(shè)計一個能解決實際問題的計算機程序需要經(jīng)過以下幾個過程：（1）建立模型：由實際問題的描述抽象出數(shù)學模型，即由物理模型到抽象模型，用形式化方法描述現(xiàn)實世界。（

2）算法設(shè)計：給出解決問題的步驟，即算法。同一個問題可以有各種不同的解決辦法，可以從中選取一種最合適的算法。2/6/202341計算機軟件基礎(chǔ)3.2.3程序設(shè)計步驟（3）算法表達：選擇一種表達算法的工具，對算法進行清晰的表達。（4）編寫程序：選擇一種程序設(shè)計語言，把以上算法程序化，這稱為編寫程序。（5）程序測試：對編寫好的程序進行測試，查找并修改程序中的錯誤。（6）程序文檔編寫與程序維護：整理和編寫程序文檔，以便更好地維護程序。對程序員有用的文檔為程序手冊，對用戶有用的文檔為用戶參考手冊。2/6/202342計算機軟件基礎(chǔ)3.3數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

《數(shù)據(jù)結(jié)構(gòu)》是計算機科學技術(shù)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是教學計劃中的核心課程之一。它不僅是一般程序設(shè)計（特別是非數(shù)值性程序設(shè)計）的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。2/6/202343計算機軟件基礎(chǔ)主要內(nèi)容3.3.1 什么是數(shù)據(jù)結(jié)構(gòu)3.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)線性表棧和隊列樹圖2/6/202344計算機軟件基礎(chǔ)3.3.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：一切可輸入計算機并能為計算機所處理的描述客觀事物的符號的集合。例如數(shù)、字符、圖形、圖像、聲音等都可以視為數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，結(jié)構(gòu)反映了數(shù)據(jù)元素之間存在的某種關(guān)系，但不涉及數(shù)據(jù)的具體內(nèi)容。

2/6/202345計算機軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)課程主要研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)運算。 數(shù)據(jù)的邏輯結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)（線性表、棧、隊列、串、數(shù)組和文件）和非線性數(shù)據(jù)結(jié)構(gòu)（樹、圖）。 數(shù)據(jù)的物理結(jié)構(gòu)指數(shù)據(jù)元素在主存中存放形式。數(shù)據(jù)運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，但運算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進行。常用的運算有：檢索、插入、刪除、更新、排序等。2/6/202346計算機軟件基礎(chǔ)3.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)1．線性表線性表是n個數(shù)據(jù)元素的有限序列，可表示為(a1,a2,…,an)。例如：全班學生名單；計算機導論成績等都可以用線性表表示。當n=0時，定義線性表為空表。同一線性表中的元素屬于同一類數(shù)據(jù)對象。線性表的操作有置空表，求表的長度，取表中元素，在表中查找某元素，插入或刪除一個元素等。2/6/202347計算機軟件基礎(chǔ)線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)通常采用順序存儲和鏈式存儲兩種存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元依次存放線性表的元素。線性表的第ｉ個元素ai的存儲位置為：

LOC(ai)=LOC(a)+(i-1)*C

式中LOC(a)是線性表的第一個數(shù)據(jù)元ａ的存儲位置，通常稱為線形表的基地址。2/6/202348計算機軟件基礎(chǔ)線性表的順序存儲結(jié)構(gòu)圖3-9線性表的順序存儲結(jié)構(gòu)1000H1004H1000H+4（i-1）a1元素ai元素存儲地址存儲單元2/6/202349計算機軟件基礎(chǔ)順序存儲結(jié)構(gòu)的缺點①在進行插入或刪除運算時，需要移動大量元素。②在為長度變化較大的線性表預(yù)先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用。③表的容量難以擴充。2/6/202350計算機軟件基礎(chǔ)線性表的鏈式存儲結(jié)構(gòu) 鏈式存儲結(jié)構(gòu)用一組任意存儲單元（可以是連續(xù)的或不連續(xù)的存儲單元）來存儲線性表的元素。 在這種存儲結(jié)構(gòu)中，每個元素需存儲兩個部分信息：一部分就是元素本身的信息，稱之“數(shù)據(jù)域”；另一部分則是該元素的直接后繼元素的存儲位置,稱之“指針域”（或“鏈”）。2/6/202351計算機軟件基礎(chǔ)線性表的鏈式存儲結(jié)構(gòu)

(c)刪除一個元素a32/6/202352計算機軟件基礎(chǔ)2．棧和隊列棧和隊列是各種程序設(shè)計中廣泛應(yīng)用的兩種數(shù)據(jù)結(jié)構(gòu)。從邏輯結(jié)構(gòu)上看，它們是一種運算受限制的線性表，也稱為限定性數(shù)據(jù)結(jié)構(gòu)。2/6/202353計算機軟件基礎(chǔ)（1）棧(stack）

棧是限定在表尾進行插入和刪除運算的線性表，其表尾稱為棧頂（top），表頭稱為棧底（bottom)。當表中沒有元素時，稱為空棧。

若給定棧S=(a1,a2,…,an),則稱a1是棧底元素,an是棧頂元素。棧的操作是按“先進后出”（LIOF:LastInFirstOut）的原則進行的。2/6/202354計算機軟件基礎(chǔ)棧的邏輯結(jié)構(gòu)圖3-11進棧和出棧示意圖2/6/202355計算機軟件基礎(chǔ)棧的基本操作與存儲結(jié)構(gòu) 棧的基本操作除入棧和出棧外，還有取棧頂位置上的元素、置Ｓ為一個空棧、判定Ｓ是否為空棧等操作。 在計算機中，棧的存儲結(jié)構(gòu)與線性表的相似，可以分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種。2/6/202356計算機軟件基礎(chǔ)（2）隊列隊列的邏輯結(jié)構(gòu)與棧相反,隊列（queue）是一種“先進先出”（FIFO:FirstInFirstOut）的線性表。只允許在隊列一端插入,并在另一端進行刪除。2/6/202357計算機軟件基礎(chǔ)（2）隊列 隊列的基本運算與棧的運算類似，主要包括下列五種：入隊列(在隊列Q的隊尾插入元素Ｘ），出隊列（刪除隊列Ｑ的隊頭元素），取出隊列Q的隊頭元素，置隊列Q為一個空隊列，判別Q是否為一個空隊列。 隊列的存儲結(jié)構(gòu)也與棧的存儲結(jié)構(gòu)相類似，可分為隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩類。2/6/202358計算機軟件基礎(chǔ)3．樹 樹結(jié)構(gòu)是非線性結(jié)構(gòu)，可以用來描述客觀世界中廣泛存在的層次結(jié)構(gòu)的關(guān)系。例如人類社會的族譜、各種社會組織機構(gòu)等都可以表示為樹型結(jié)構(gòu)。

樹形的存儲結(jié)構(gòu)也可分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩類。 下面我們介紹的二叉樹和樹其結(jié)構(gòu)都是樹形的結(jié)構(gòu)。2/6/202359計算機軟件基礎(chǔ)（1）二叉樹 二叉樹是有限個元素的集合，該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結(jié)點。Ф左子樹右子樹左子樹右子樹

(a)(b)(c)(d)(e)

圖3-13二叉樹的五種基本形態(tài)2/6/202360計算機軟件基礎(chǔ)BCDEFGHIJKLMNO123456789101112131415ABCDEFGHI123456789

(a)一棵滿二叉樹

(b)一棵非滿二叉樹A2/6/202361計算機軟件基礎(chǔ)ABDCEFGHIJ12345678910ABDCGEF1234567

(a)一棵完全二叉樹

(b)一棵非完全二叉樹

2/6/202362計算機軟件基礎(chǔ)（2）樹

樹是n個有限數(shù)據(jù)元素的集合。當n＝0時，稱這棵樹為空樹。在一棵非空樹T中：1)有一個特殊的數(shù)據(jù)元素稱為樹的根結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點。2)若n>1，除根結(jié)點之外的其余數(shù)據(jù)元素被分成m（m>0）個互不相交的集合T1，T2，…，Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹。樹T1，T2，…，Tm稱為這個根結(jié)點的子樹。2/6/202363計算機軟件基礎(chǔ)ABCDEFGIH圖3-16樹結(jié)構(gòu)示意圖2/6/202364計算機軟件基礎(chǔ)（2）樹

如果一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。零棵或有限棵不相交的樹的集合稱為森林。任何一棵樹，刪去根結(jié)點就變成了森林。2/6/202365計算機軟件基礎(chǔ)4．圖 圖結(jié)構(gòu)是一種比樹結(jié)構(gòu)更復雜的非線性結(jié)構(gòu)。任意兩個結(jié)點之間都可能相關(guān)，即結(jié)點之間的鄰接關(guān)系可以是任意的。圖結(jié)構(gòu)被用于描述各種復雜的數(shù)據(jù)對象，在自然科學、社會科學和人文科學等許多領(lǐng)域有著非常廣泛的應(yīng)用。圖的存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)以及順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的結(jié)合，例如鄰接矩陣、鄰接表等。

2/6/202366計算機軟件基礎(chǔ)4．圖圖是由非空的頂點集合和描述頂點之間關(guān)系的邊（或者?。┘辖M成，其形式化定義為：G＝（V，E）; G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點vi和頂點vj之間有一條直接連線，即偶對(vi,vj)表示一條邊。2/6/202367計算機軟件基礎(chǔ)v1v4v3v2v5圖3-17無向圖

v4v3v2v1圖3-18有向圖2/6/202368計算機軟件基礎(chǔ)3.4軟件工程基礎(chǔ)軟件工程自1968年提出以來，近40年中，已發(fā)展成為用于指導軟件生產(chǎn)工程化，覆蓋軟件開發(fā)方法學、軟件工具與環(huán)境、軟件工程管理等內(nèi)容的一門新學科。隨著程序設(shè)計從結(jié)構(gòu)化程序設(shè)計發(fā)展到面向?qū)ο蟪绦蛟O(shè)計，軟件工程也由傳統(tǒng)的軟件工程演變?yōu)槊嫦驅(qū)ο蟮能浖こ?，現(xiàn)在正向更新一代的基于構(gòu)件的軟件工程邁進。2/6/202369計算機軟件基礎(chǔ)主要內(nèi)容3.4.1 軟件工程概述3.4.2 軟件生存周期3.4.3 軟件開發(fā)模型3.4.4 軟件開發(fā)方法2/6/202370計算機軟件基礎(chǔ)3.4.1軟件工程概述1．軟件的發(fā)展與軟件危機

20世紀60年代末期所發(fā)生的軟件危機，體現(xiàn)在軟件可靠性沒有保障、軟件維護費用不斷上升、進度無法預(yù)測、成本增長無法控制、程序人員無限度地增加等各個方面，以致形成人們難以控制軟件開發(fā)的局面。計算機領(lǐng)域把大型軟件開發(fā)和維護過程中遇到的一系列嚴重問題稱為“軟件危機”（SoftwareCrisis）。2/6/202371計算機軟件基礎(chǔ)2．軟件工程學的主要內(nèi)容

(1)軟件工程的定義 軟件工程是以系統(tǒng)的、規(guī)范的、定量的過程化方法應(yīng)用于軟件的開發(fā)、運行和維護，以及對這些方法的研究。 軟件工程的目標就是在要求的時間內(nèi)研制開發(fā)出具有良好的軟件質(zhì)量和費用合理的產(chǎn)品。2/6/202372計算機軟件基礎(chǔ)(2)軟件工程學的主要內(nèi)容軟件工程學的主要內(nèi)容是軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)技術(shù)包含了軟件開發(fā)方法、軟件工具和軟件工程環(huán)境；軟件工程管理包含了軟件工程經(jīng)濟學和軟件管理學。2/6/202373計算機軟件基礎(chǔ)軟件開發(fā)方法常用的軟件開發(fā)方法:結(jié)構(gòu)化方法是采用結(jié)構(gòu)化的技術(shù)來完成軟件開發(fā)的各項任務(wù)；面向?qū)ο蠓椒ㄊ敲嫦驅(qū)ο蠓椒ㄔ谲浖こ填I(lǐng)域的全面運用；面向構(gòu)件的方法是創(chuàng)建和利用可復用的軟件構(gòu)件來解決軟件開發(fā)問題。2/6/202374計算機軟件基礎(chǔ)軟件工具

軟件工具（SoftwareTools）是指幫助開發(fā)和維護軟件的軟件。 利用軟件工具可提高軟件設(shè)計的質(zhì)量和生產(chǎn)效率。例如，編程時用的編輯程序，測試用的跟蹤程序、靜態(tài)分析工具等。眾多的軟件工具組成“工具箱”，供開發(fā)人員選用。2/6/202375計算機軟件基礎(chǔ)軟件工程環(huán)境 軟件工程環(huán)境正是軟件方法和工具的結(jié)合，它是相關(guān)的一組軟件工具集合，它支持一定的軟件開發(fā)方法或按照一定的軟件開發(fā)模型組織而成。軟件開發(fā)環(huán)境的設(shè)計目標是提高軟件生產(chǎn)率和改善軟件的質(zhì)量。2/6/202376計算機軟件基礎(chǔ)軟件工程管理學 軟件工程管理就是對軟件工程生存期內(nèi)的各階段的活動進行管理，實現(xiàn)按預(yù)定的時間和費用成功地完成軟件的開發(fā)和維護。 軟件工程管理學的內(nèi)容包括軟件費用管理、人員組織、工程計劃管理和軟件配置管理等。

2/6/202377計算機軟件基礎(chǔ)軟件工程經(jīng)濟學 軟件工程經(jīng)濟學借鑒經(jīng)濟學的成熟經(jīng)驗、技術(shù)和方法為軟件工程決策服務(wù)。

包括軟件成本估算模型分析，軟件生命周期成本估算，以成本效益分析、邊際分析、風險分析為基礎(chǔ)的決策方法以及軟件成本估算技術(shù)等。2/6/202378計算機軟件基礎(chǔ)3.4.2軟件生存周期 軟件生存周期是軟件工程的一個重要概念，是一個從用戶需求開始，經(jīng)過開發(fā)、交付使用，在使用中不斷地增補修訂，直至讓位于新的軟件的全過程，是指軟件產(chǎn)品從考慮其概念開始，到該軟件產(chǎn)品不再能使用為止的整個時期。2/6/202379計算機軟件基礎(chǔ)3.4.2軟件生存周期 軟件生存周期一般劃分為軟件計劃、軟件開發(fā)和軟件運行維護三個時期組成。

軟件計劃時期分為問題定義、可行性研究兩個階段。

軟件開發(fā)時期可分為需求分析、軟件設(shè)計、程序編寫、軟件測試等階段。

軟件運行維護時期是指軟件交付使用后在運行過程中需要不斷地維護，使軟件能持久地滿足用戶的需要。2/6/202380計算機軟件基礎(chǔ)3.4.2軟件生存周期1．問題定義：系統(tǒng)要解決的問題是什么？2．可行性研究：問題是否有可行性方案？3．需求分析：目標系統(tǒng)必須做什么？4．軟件設(shè)計：怎樣實現(xiàn)(劃分及模塊具體描述) 目標系統(tǒng)?5．程序編寫6．軟件測試：單元、集成及驗收測試；7．軟件運行維護：改正性、適應(yīng)性及完善性維 護。2/6/202381計算機軟件基礎(chǔ)3.4.3 軟件開發(fā)模型 軟件開發(fā)模型是軟件開發(fā)全部過程、活動和任務(wù)的結(jié)構(gòu)框架。 軟件開發(fā)模型能清晰、直觀地表達軟件開發(fā)全過程，明確規(guī)定了要完成的主要活動和任務(wù)，用來作為軟件項目開發(fā)工作的基礎(chǔ)。 常用的有瀑布模型，快速原型模型，演化模型，螺旋模型，噴泉模型，構(gòu)件組裝模型，轉(zhuǎn)換模型和智能模型等。2/6/202382計算機軟件基礎(chǔ)（1）瀑布模型 瀑布模型（WaterfallModel）是1970年WinstonRoyce提出的最早出現(xiàn)的軟件開發(fā)模型。 瀑布模型遵循軟件生存期的劃分，明確規(guī)定每個階段的任務(wù)，各個階段的工作按順序展開，形如瀑布流水，最終得到軟件系統(tǒng)或軟件產(chǎn)品。2/6/202383計算機軟件基礎(chǔ)（1）瀑布模型圖3-19瀑布模型2/6/202384計算機軟件基礎(chǔ)（2）快速原型 快速原型（RapidPrototypeModel）模型是把用戶最初的需求快速建立一個只包括核心功能并可在計算機上運行的程序（原型）讓用戶使用。用戶通過使用這個原型，以便能準確地認識到他們的實際需要是什么，提出進一步的需求，開發(fā)人員按照用戶意見快速修改原型，直到得到明確完整的需求，按照這個最后的需求開發(fā)出系統(tǒng)。2/6/202385計算機軟件基礎(chǔ)（2）快速原型

圖3-20快速原型模型快速分析形成最終系統(tǒng)快速構(gòu)造原型運行原型評價原型快速修改系統(tǒng)不滿意滿意2/6/202386計算機軟件基礎(chǔ)（3）演化模型 演化模型（evolutionarymodel）結(jié)合了瀑布模型的線性順序的特點和快速原型模型的迭代思想。 演化模型與快速原型的相同之處是迭代的特征，不同之處是演化模型的每一輪都得到一個用戶真正使用的完整版本，而快速原型每一輪得到的是在功能和性能上大大簡化了的版本。2/6/202387計算機軟件基礎(chǔ)（3）演化模型

需求分析設(shè)計編碼測試運行需求分析設(shè)計編碼測試運行需求分析設(shè)計編碼測試運行工作版本n工作版本2工作版本12/6/202388計算機軟件基礎(chǔ)（4）螺旋模型 螺旋模型是由TRW公司的B.Boehm于1988年提出的，它將瀑布模型和演化模型等結(jié)合起來，并且強調(diào)了其他模型均忽略了的風險分析。螺旋模型更適合于大型軟件的開發(fā)，應(yīng)該說它對于具有高度風險的大型復雜軟件系統(tǒng)的開發(fā)是較為實際的方法。2/6/202389計算機軟件基礎(chǔ)圖3-22螺旋模型2/6/202390計算機軟件基礎(chǔ)（5）噴泉模型 噴泉模型（FountainModel)主要用于采用對象技術(shù)的軟件開發(fā)項目。軟件的某個部分常常被重復工作多次，相關(guān)對象在每次迭代中隨之加入漸進的軟件成分。由于對象概念的引入，表達分析、設(shè)計、實現(xiàn)等活動只用對象類和關(guān)系，從而可以較為容易地實現(xiàn)活動的迭代和無間隙，使其開發(fā)自然地包括復用。2/6/202391計算機軟件基礎(chǔ)圖3-23噴泉模型2/6/202392計算機軟件基礎(chǔ)（6）構(gòu)件組裝模型

構(gòu)件組裝模型（SoftwareReuseModel）旨在開發(fā)具有各種一般性功能的軟件模塊—構(gòu)件，一般這些構(gòu)件適用于某個領(lǐng)域（例如建筑、電子、機械、財經(jīng)等），這些構(gòu)件設(shè)計時考慮其適應(yīng)各種界面的接口規(guī)格，將它們規(guī)范化后放入構(gòu)件庫，供軟件開發(fā)時利用。

構(gòu)件組裝模型利用已有的軟件構(gòu)件來構(gòu)造應(yīng)用軟件系統(tǒng)，軟件開發(fā)過程也用螺旋模型，支持軟件開發(fā)的迭代方法。2/6/202393計算機軟件基礎(chǔ)（6）構(gòu)件組裝模型

構(gòu)件組裝模型在實施開發(fā)活動時，要描述項目需要什么構(gòu)件，然后在構(gòu)件庫中查找構(gòu)件，如果有構(gòu)件可用就直接使用；否則如果有相似的構(gòu)件就進行修改，修改后的構(gòu)件用于構(gòu)造系統(tǒng)并且追加到構(gòu)件庫中；若沒有需要的構(gòu)件，就要進行開發(fā)，再將開發(fā)的新構(gòu)件用于構(gòu)造系統(tǒng)并且追加到構(gòu)件庫中。 建立一個豐富的構(gòu)件庫，充分復用已有構(gòu)件，可以減少軟件生產(chǎn)中的重復開發(fā)，避免開發(fā)人員的重復勞動，提高開發(fā)效率，縮短開發(fā)周期，降低開發(fā)成本。2/6/202394計算機軟件基礎(chǔ)3.4.4軟件開發(fā)方法 軟件工程研究的范圍非常廣泛，包括技術(shù)方法、工具和管理等許多方面。其中軟件開發(fā)的技術(shù)方法是軟件工程研究的重點。 當前軟件開發(fā)方法主要有結(jié)構(gòu)化軟件開發(fā)方法、面向?qū)ο箝_發(fā)方法和基于構(gòu)件的軟件開發(fā)方法。2/6/202395計算機軟件基礎(chǔ)1.結(jié)構(gòu)化軟件開發(fā)方法 結(jié)構(gòu)化方法是通過按功能將問題分解抽象成模塊，建立模塊和模塊之間的調(diào)用關(guān)系來進行軟件開發(fā)的。針對軟件開發(fā)的不同階段和活動，該方法又可以劃分為結(jié)構(gòu)化分析(structuredanalysis,SA)、結(jié)構(gòu)化設(shè)計(structureddesign,SD)和結(jié)構(gòu)化程序設(shè)計(structuredprogramdesign,SP)3個階段和方法。2/6/202396計算機軟件基礎(chǔ)（1）結(jié)構(gòu)化方法的基本原則 采用結(jié)構(gòu)化方法來分析和解決問題應(yīng)遵循3個基本原則：1)分解原則2）模塊化原則3）抽象原則2/6/202397計算機軟件基礎(chǔ)（2）結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法給出一組幫助系統(tǒng)分析人員產(chǎn)生功能規(guī)約的原理和技術(shù)。一般利用圖形表示用戶需求，以數(shù)據(jù)流圖為基礎(chǔ)，伴以數(shù)據(jù)詞典，并配上結(jié)構(gòu)化語言、判定表和判定樹等手段，從而達到為解決問題建立模型。2/6/202398計算機軟件基礎(chǔ)（3）結(jié)構(gòu)化設(shè)計方法 結(jié)構(gòu)化設(shè)計方法給出一組幫助設(shè)計人員在模塊層次上區(qū)分設(shè)計質(zhì)量的原理與技術(shù)，它通常與結(jié)構(gòu)化分析街接起來使用，以數(shù)據(jù)流圖為基礎(chǔ)得到軟件模塊結(jié)構(gòu)。 第一階段是概要設(shè)計，又稱總體設(shè)計或初步設(shè)計，從整體上回答系統(tǒng)應(yīng)該如何實現(xiàn)的問題，即確定軟件結(jié)構(gòu)。 第二階段是詳細設(shè)計階段，確定每個模塊具體的執(zhí)行過程，故又稱“過程設(shè)計”。2/6/202399計算機軟件基礎(chǔ)（4）結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計是把軟件結(jié)構(gòu)化設(shè)計的結(jié)果翻譯成用某種結(jié)構(gòu)化程序設(shè)計語言書寫的程序。 雖然程序設(shè)計的質(zhì)量取決于軟件設(shè)計的質(zhì)量，但是選用的程序設(shè)計語言和編碼的風格對軟件的可靠性、可讀性、可測試性和可維護性產(chǎn)生深遠影響。2/6/2023100計算機軟件基礎(chǔ)2.面向?qū)ο蟮能浖_發(fā)方法 面向?qū)ο蟮能浖_發(fā)技術(shù)(object-orienteddevelopmenttechnology,OOT)以客觀世界中的對象為中心，以類和繼承為構(gòu)造機制來抽象現(xiàn)實世界。這種技術(shù)起源于面向?qū)ο蟮某绦蛟O(shè)計語言。自20世紀80年代中期到90年代，面向?qū)ο蟮难芯恐攸c已從編程語言轉(zhuǎn)移到設(shè)計方法學。面向?qū)ο蟮能浖_發(fā)方法包