第3章計(jì)算機(jī)軟件基礎(chǔ)

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

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

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

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

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

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

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

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

例3-1給定兩個(gè)正整數(shù)m和n，試寫出求它們的最大公因子的算法。解：歐幾里德算法用自然語言表述如下： 第1步：讀入兩個(gè)正整數(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計(jì)算機(jī)軟件基礎(chǔ)

開始

輸入m，n

r←mod(m,n)

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

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

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

Intm,n,r；

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

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

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

C++成為當(dāng)今最受歡迎的面向?qū)ο蟪绦蛟O(shè)計(jì)語言之一，因?yàn)樗热诤狭嗣嫦驅(qū)ο蟮哪芰?，又與C語言兼容，保留了C語言的許多重要特性。這就維護(hù)了大量開發(fā)的C庫(kù)、C工具以及C源程序的完整性，使C程序員不必放棄自己已經(jīng)十分熟悉的C語言，只要補(bǔ)充學(xué)習(xí)C++提供的那些面向?qū)ο蟮男赂拍罴纯?。目前常用的有BorlandC++版和VisualC++版。2/6/202327計(jì)算機(jī)軟件基礎(chǔ)2）面向?qū)ο笳Z言

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

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

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是教學(xué)計(jì)劃中的核心課程之一。它不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。2/6/202343計(jì)算機(jī)軟件基礎(chǔ)主要內(nèi)容3.3.1 什么是數(shù)據(jù)結(jié)構(gòu)3.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)線性表?xiàng)：完?duì)列樹圖2/6/202344計(jì)算機(jī)軟件基礎(chǔ)3.3.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：一切可輸入計(jì)算機(jī)并能為計(jì)算機(jī)所處理的描述客觀事物的符號(hào)的集合。例如數(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計(jì)算機(jī)軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)課程主要研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)課程主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)運(yùn)算。 數(shù)據(jù)的邏輯結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)（線性表、棧、隊(duì)列、串、數(shù)組和文件）和非線性數(shù)據(jù)結(jié)構(gòu)（樹、圖）。 數(shù)據(jù)的物理結(jié)構(gòu)指數(shù)據(jù)元素在主存中存放形式。數(shù)據(jù)運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。常用的運(yùn)算有：檢索、插入、刪除、更新、排序等。2/6/202346計(jì)算機(jī)軟件基礎(chǔ)3.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)1．線性表線性表是n個(gè)數(shù)據(jù)元素的有限序列，可表示為(a1,a2,…,an)。例如：全班學(xué)生名單；計(jì)算機(jī)導(dǎo)論成績(jī)等都可以用線性表表示。當(dāng)n=0時(shí)，定義線性表為空表。同一線性表中的元素屬于同一類數(shù)據(jù)對(duì)象。線性表的操作有置空表，求表的長(zhǎng)度，取表中元素，在表中查找某元素，插入或刪除一個(gè)元素等。2/6/202347計(jì)算機(jī)軟件基礎(chǔ)線性表的存儲(chǔ)結(jié)構(gòu)線性表的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的元素。線性表的第ｉ個(gè)元素ai的存儲(chǔ)位置為：

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

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

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

棧是限定在表尾進(jìn)行插入和刪除運(yùn)算的線性表，其表尾稱為棧頂（top），表頭稱為棧底（bottom)。當(dāng)表中沒有元素時(shí)，稱為空棧。

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

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

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

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

(a)一棵滿二叉樹

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

(a)一棵完全二叉樹

(b)一棵非完全二叉樹

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

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

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

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

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

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

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

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

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

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

軟件計(jì)劃時(shí)期分為問題定義、可行性研究?jī)蓚€(gè)階段。

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

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

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

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

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

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

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