經(jīng)濟(jì)數(shù)學(xué)：第五章 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(1)

1、教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系第五章第五章 計(jì)算機(jī)軟件技術(shù)基礎(chǔ)計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 計(jì)算機(jī)硬件(Hardware)是計(jì)算機(jī)系統(tǒng)的基礎(chǔ)，但是沒有軟件(Software)的計(jì)算機(jī)是無法工作的。事實(shí)上，現(xiàn)在計(jì)算機(jī)能廣泛地應(yīng)用于各個(gè)領(lǐng)域，完全是由于有了豐富的計(jì)算機(jī)軟件，人們?yōu)榱擞糜?jì)算機(jī)解決各類問題，針對性地開發(fā)了各種各樣的軟件。 本章將討論關(guān)于計(jì)算機(jī)軟件和計(jì)算機(jī)軟件開發(fā)的一些基本問題，從而對計(jì)算機(jī)軟件開發(fā)有一個(gè)總體的認(rèn)識(shí)，掌握一些重要的基本概念，如什么是軟件，什么是軟件開發(fā)過程等。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工

2、程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.1 計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)軟件系統(tǒng) 5.1.1 軟件的概念與特點(diǎn)軟件的概念與特點(diǎn) 軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)及其相關(guān)文檔的完整集合。軟件通常是為某個(gè)特定目的而開發(fā)的產(chǎn)品。 程序：按照事先設(shè)計(jì)的功能和性能要求執(zhí)行的計(jì)算機(jī)指令序列。 數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。 文檔：與程序開發(fā)、維護(hù)和使用有關(guān)的資料。 軟件的特點(diǎn): 抽象性 復(fù)雜性 維護(hù)長期性 高成本性教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.1 計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)軟件系統(tǒng)5.1

3、.2 軟件的分類軟件的分類(1) 按軟件功能劃分 系統(tǒng)軟件：能與計(jì)算機(jī)硬件緊密配合在一起，使計(jì)算機(jī)系統(tǒng)的各個(gè)部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效地工作。 支撐軟件：協(xié)助用戶開發(fā)軟件的工具性軟件，其中包括幫助軟件人員開發(fā)軟件產(chǎn)品的工具，也包括幫助管理人員控制開發(fā)進(jìn)程的工具。 應(yīng)用軟件：針對特定領(lǐng)域應(yīng)用開發(fā)，為特定目的服務(wù)的軟件。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.1 計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)軟件系統(tǒng) (2) 按軟件工作方式劃分 實(shí)時(shí)處理軟件：對實(shí)時(shí)過程進(jìn)行監(jiān)控的軟件。 分時(shí)軟件：允許多個(gè)聯(lián)機(jī)用戶同時(shí)使用計(jì)算機(jī)。 交互式軟件：能實(shí)現(xiàn)人

4、機(jī)通信的軟件。 批處理軟件：把一組輸入作業(yè)或大量數(shù)據(jù)以成批處理的方式一次運(yùn)行，按順序逐個(gè)處理的軟件。 (3) 按軟件服務(wù)對象劃分 項(xiàng)目軟件：也稱定制軟件，是受某個(gè)特定客戶(或少數(shù)客戶)委托，由一個(gè)或多個(gè)軟件開發(fā)機(jī)構(gòu)在合同的約束下開發(fā)出來的軟件。 產(chǎn)品軟件：由軟件開發(fā)機(jī)構(gòu)開發(fā)出來投入市場或用戶群體龐大的軟件。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.1 計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)軟件系統(tǒng) 計(jì)算機(jī)軟件系統(tǒng)包括各種各樣的軟件，這些軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。 5.1.3 計(jì)算機(jī)軟件的層次結(jié)構(gòu)計(jì)算機(jī)軟件的層次結(jié)構(gòu)教學(xué)進(jìn)度教

5、學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言 簡單來講，程序設(shè)計(jì)就是：用計(jì)算機(jī)語言編寫程序。 程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 編寫計(jì)算機(jī)程序時(shí)使用的語言稱為程序設(shè)計(jì)語言(Programming Language)，使用它把人類解決問題的方法用計(jì)算機(jī)可以識(shí)別的形式表示出來。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.1 機(jī)器語言機(jī)器語言 機(jī)器語言是指由二進(jìn)制代碼按照一定規(guī)則組成的命令集合，也稱為機(jī)器指令集合。機(jī)器指令

6、的格式如下： 操作碼操作數(shù)例如：計(jì)算256+16結(jié)果的機(jī)器代碼如下(以十六進(jìn)制表示)： B8 0001；把；把256放入累加器放入累加器AX05 1000；把；把16與與AX中值相加，結(jié)果存入中值相加，結(jié)果存入AX教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.2 匯編語言匯編語言 為了解決機(jī)器語言難記憶、可讀性差的缺點(diǎn)，人們把機(jī)器指令中的操作碼和操作數(shù)用英文助記符和符號地址來表示，這種助記符語言稱為匯編語言。 MOV AX， 256；把；把256放入累加器放入累加器AXADD AX， 16；把；把

7、16與與AX中值相加，結(jié)果存入中值相加，結(jié)果存入AX匯編和連接過程 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.3 高級語言高級語言 高級語言是一類程序設(shè)計(jì)語言的統(tǒng)稱，它采用接近人類自然語言和數(shù)學(xué)表達(dá)式的表示方法，并遵循一定的語法規(guī)則來編寫程序。 實(shí)現(xiàn)求整數(shù)的絕對值的程序段：int intVar, result;scanf(“%d”, &intVar);if(intVar = 0) result = intVar;else result = -1*intVar;printf(“%d的絕對值是：的

8、絕對值是：%d”, intVar, result);教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言高級語言程序的翻譯和執(zhí)行 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.4 程序設(shè)計(jì)語言的構(gòu)成程序設(shè)計(jì)語言的構(gòu)成 數(shù)據(jù)和操作是構(gòu)成程序的兩個(gè)基本要素，任何一種程序設(shè)計(jì)語言都必須提供表示數(shù)據(jù)和操作的語法、語義元素。 (1) 數(shù)據(jù)類型 程序設(shè)計(jì)語言中一般分為基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型兩大類。 基本數(shù)據(jù)類型是由程序設(shè)計(jì)

9、語言內(nèi)置的，其特點(diǎn)是不能再分解為其它的類型。在主流的程序設(shè)計(jì)語言中一般包括：整數(shù)類型、實(shí)數(shù)類型、字符類型、布爾類型等。 構(gòu)造數(shù)據(jù)類型是由基本數(shù)據(jù)類型按照某種方式組合構(gòu)成的。常見的構(gòu)造數(shù)據(jù)類型有：數(shù)組類型、記錄類型(結(jié)構(gòu)體)、枚舉類型、字符串類型、文件類型等。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言(2) 運(yùn)算符和表達(dá)式 運(yùn)算是程序?qū)?shù)據(jù)進(jìn)行的最基本也是最重要的處理，程序設(shè)計(jì)中使用表達(dá)式完成各種各樣的運(yùn)算。表達(dá)式通常包括：常量、變量、運(yùn)算符和函數(shù)調(diào)用等構(gòu)成。例如：給定圓的半徑r，求其面積的Java語言

10、表達(dá)式是： s = 3.14 * r * r(3) 語句 程序是對計(jì)算機(jī)要執(zhí)行的操作的描述。高級語言源程序的基本組成單位是語句。 語句按功能可以分為兩類： 1.用于描述操作運(yùn)算，如賦值語句，稱為操作運(yùn)算語句； 2.用于控制操作運(yùn)算的執(zhí)行順序，如分支控制語句，稱為流程控制語句。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言(4) 控制結(jié)構(gòu) 順序結(jié)構(gòu)，按照語句出現(xiàn)的先后順序依次執(zhí)行。 分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。 循環(huán)結(jié)構(gòu)，循環(huán)(重復(fù))是計(jì)算機(jī)解題的一個(gè)重要特征。(5) 輸入/輸出 程序

11、的輸入是指用戶將數(shù)據(jù)通過輸入設(shè)備(如鍵盤等)輸入到程序中。 程序的輸出是指程序把運(yùn)算結(jié)果以用戶可以理解的形式輸出到輸出設(shè)備(如顯示器、打印機(jī)等)。 高級程序設(shè)計(jì)語言中通常以函數(shù)或語句的形式提供輸入輸出操作。 現(xiàn)代高級程序設(shè)計(jì)語言通常都提供通過窗口、文本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言(6) 子程序 子程序就是將需要重復(fù)使用的程序段或分解的子問題編寫為一個(gè)邏輯上獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對其進(jìn)行調(diào)用。 使用子程序的好處是降低了程序

12、的復(fù)雜度，使程序的結(jié)構(gòu)清晰，提高了程序設(shè)計(jì)的效率。 一般程序設(shè)計(jì)語言中有兩種子程序：函數(shù)(Function)和過程(Procedure)，它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.1 什么是數(shù)據(jù)什么是數(shù)據(jù) 數(shù)據(jù)是對客觀事物的描述，對計(jì)算機(jī)來說，數(shù)據(jù)的含義非常廣泛，如數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。數(shù)據(jù)元素(Data Element)是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。 例：公司員工數(shù)據(jù)的存

13、儲(chǔ) 姓名姓名性別性別出生日期出生日期職位職位工資工資張軍男1975.5.6總經(jīng)理2080.00李芳女1980.12.12項(xiàng)目經(jīng)理1800.00王明男1979.4.19程序員1500.00劉杰男1974.6.23系統(tǒng)分析員1750.00趙麗女1977.11.9測試員1900.00教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.2 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)研究的不是幾個(gè)孤立的數(shù)據(jù)，而是大量的相互關(guān)聯(lián)的數(shù)據(jù)。 數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)。簡單來說，數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括三個(gè)方面： (1)數(shù)據(jù)的邏

14、輯結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)方式，把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中。 鏈?zhǔn)酱鎯?chǔ)方式，每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)與該結(jié)點(diǎn)具有邏輯關(guān)系的結(jié)點(diǎn)的地址。 索引存儲(chǔ)方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲(chǔ)區(qū)域里。選取一個(gè)結(jié)點(diǎn)作為索引表，索引表中的第i項(xiàng)表示第i個(gè)元素的存儲(chǔ)地址。 散列

15、存儲(chǔ)方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲(chǔ)區(qū)域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲(chǔ)地址。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(3) 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、刪除、查找、排序、遍歷等。 每一種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算及其規(guī)則的集合。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.3 常見數(shù)據(jù)結(jié)構(gòu)介紹常見數(shù)據(jù)結(jié)構(gòu)介紹 (了解了解)(1) 數(shù)組 數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計(jì)算機(jī)內(nèi)存中使用一組連

16、續(xù)的存儲(chǔ)單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有相同的變量名，稱為數(shù)組名。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(2) 鏈表 鏈表(Linked List)是采用鏈?zhǔn)酱鎯?chǔ)的線性表。線性鏈表的結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩個(gè)部分組成，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)一個(gè)指向直接后繼結(jié)點(diǎn)的指針。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(3) 二叉樹 二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個(gè)結(jié)點(diǎn)的集合，該集合或者

17、為空，或者滿足下面兩個(gè)條件： 有且僅有一個(gè)稱為根的結(jié)點(diǎn)。 其它結(jié)點(diǎn)分為兩個(gè)互不相交的集合T1、T2。T1和T2均為二叉樹，并且在T1和T2之間存在順序關(guān)系(T1在T2之前)，分別稱為根的左子樹和右子樹。 二叉樹的5種基本形態(tài) 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu) 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹 前序遍歷:訪問根結(jié)點(diǎn);前序遍歷左子樹;前序遍歷右子樹 中序遍歷:中序遍歷左子樹;訪問根結(jié)

18、點(diǎn);中序遍歷右子樹 后序遍歷:后序遍歷左子樹;后序遍歷右子樹;訪問根結(jié)點(diǎn) 前序遍歷：A B D E F G C 中序遍歷：D B F E G A C 后序遍歷：D F G E B C A教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法5.4.1 算法的基本概念算法的基本概念 算法(Algorithm)是指為解決給定問題而需實(shí)施的有窮操作步驟的描述。 5.4.2 算法的描述方法算法的描述方法 (1) 用自然語言描述算法(2) 用流程圖描述算法(3) 使用偽代碼描述算法(4) 用程序設(shè)計(jì)語言描述算法教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與

19、工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法5.4.3 查找算法查找算法(了解了解) 查找(Searching)也稱檢索，設(shè)表F中有n個(gè)結(jié)點(diǎn)，Ki是記錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在F中尋找關(guān)鍵字與K相同的結(jié)點(diǎn)R的過程，叫做查找。 (1) 順序查找 順序查找是線性表的最簡單的查找算法。它是用給定的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。 順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對線性表中結(jié)點(diǎn)邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理存儲(chǔ)結(jié)構(gòu)也沒有要求，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)均可。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)

20、科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法(2) 折半查找 折半查找的基本思想是： 先取表的中間位置的結(jié)點(diǎn)關(guān)鍵字與所給定的關(guān)鍵字進(jìn)行比較，如果相等，則查找成功。如果給定值比該結(jié)點(diǎn)的關(guān)鍵字大，則所找結(jié)點(diǎn)在表的后半部分；否則所找結(jié)點(diǎn)在表的前半部分，然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字進(jìn)行比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失敗為止。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法例: 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)

21、算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法5.4.4 排序算法排序算法(了解了解) 排序(Sort)是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是將一組數(shù)據(jù)元素(或記錄)從任意序列排列成一個(gè)按關(guān)鍵字排序的序列。 按照排序過程中涉及的存儲(chǔ)器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過程都在內(nèi)存中進(jìn)行的排序。 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法(1) 直接插入排序 算法的基本思想如下： 開始時(shí)，把第一個(gè)記錄看成是已經(jīng)排好序的子序列，這時(shí)子序列中只有一個(gè)記錄； 從第二個(gè)記錄起到最后一個(gè)記錄，依

22、次將每個(gè)記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置； 將記錄插入到子序列中，子序列記錄個(gè)數(shù)加1，直至子序列長度與待排序列長度相等時(shí)結(jié)束。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法(1) 直接插入排序 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法5.4.4 排序算法排序算法(了解了解) (2) 冒泡排序冒泡排序的算法思想是： 將第n個(gè)記錄的關(guān)鍵字與將第n-1個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄進(jìn)行位置的交換，否則保持原來順序

23、； 將第n-1個(gè)記錄的關(guān)鍵字與將第n-2個(gè)記錄的關(guān)鍵字進(jìn)行比較； 重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍； 上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第1個(gè)記錄的位置，完成一趟排序； 第二趟排序從第n個(gè)記錄到第2個(gè)記錄進(jìn)行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第2個(gè)記錄的位置；依次類推，第i趟排序是從第n個(gè)記錄到第i個(gè)記錄依次比較交換。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.4 算法算法(2) 冒泡排序教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工

24、程系計(jì)算機(jī)科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.1 軟件危機(jī)與軟件工程軟件危機(jī)與軟件工程 在軟件開發(fā)、維護(hù)過程中出現(xiàn)了一系列嚴(yán)重的問題，造成軟件需求與軟件生產(chǎn)之間的尖銳的矛盾，稱為軟件危機(jī)。 1990年電氣電子工程師協(xié)會(huì)(IEEE)給出了軟件工程的一個(gè)定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過程，也就是把工程化運(yùn)用于軟件工程，并對這樣的方法進(jìn)行研究”。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系 軟件生存周期：軟件生存周期：從用戶需求開始，經(jīng)過開發(fā)、交付使用，在使用中 不斷地增補(bǔ)修訂

25、，直至讓位于新的軟件的全過程。 過程：過程： a . 概念階段 b . 需求階段 c . 設(shè)計(jì)階段 d . 實(shí)現(xiàn)階段 e .測試階段 f . 安裝階段 g . 交付使用階段 h . 運(yùn)行階段 i . 維護(hù)階段 需求管理 5.5 軟件工程簡介軟件工程簡介教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系 需求分析的成本需求分析的成本 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系 需求管理的過程需求管理的過程 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科

26、學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.3 軟件開發(fā)模型軟件開發(fā)模型 軟件開發(fā)模型也叫軟件過程模型，是軟件系統(tǒng)開發(fā)項(xiàng)目總貌的一種描述，它是從軟件項(xiàng)目計(jì)劃的制定到軟件最后停止使用的整個(gè)過程的結(jié)構(gòu)框架。 到目前為止，已經(jīng)提出了多種軟件生命周期模型，如：瀑布模型、螺旋模型、演化模型、噴泉模型等。 5.5.4 軟件開發(fā)方法軟件開發(fā)方法 軟件開發(fā)方法是關(guān)于如何組織軟件開發(fā)過程的方法，是從宏觀上來把握開發(fā)全過程，其方法一般描述為一系列的步驟，每個(gè)步驟都會(huì)有相應(yīng)的技術(shù)來支持，有相應(yīng)的符號工具來描述。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工

27、程系計(jì)算機(jī)科學(xué)與工程系1 瀑布模型(Waterfall) 思想：將軟件開發(fā)過程中的各項(xiàng)活動(dòng)規(guī)定為依固定順序連接的若干 階段工 作，行如瀑布流水，最終得到軟件系統(tǒng)或軟件產(chǎn)品 本質(zhì)：一次通過，每個(gè)活動(dòng)做一次 過程： 計(jì)劃計(jì)劃 需求分析 設(shè)計(jì) 編碼 測試 運(yùn)行維護(hù) 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系3 演化模型(Eolutionary Model) 主要針對事先不能完整定義需求的軟件項(xiàng)目開發(fā) 形式： 丟棄型 樣品型 漸增式演化型 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程

28、系4 螺旋模型(Spiral Model) 思想: 將瀑布模型和演化模型結(jié)合起來，并強(qiáng)調(diào)其他模型均忽略的風(fēng)險(xiǎn)分析 過程：將開發(fā)劃分為制定計(jì)劃、風(fēng)險(xiǎn)分析、實(shí)施開發(fā)和客戶評估4類活動(dòng)，沿螺旋 線每轉(zhuǎn)一圈，表示開發(fā)出一個(gè)更完善的新的軟件版本。 應(yīng)用：適合大型軟件的開發(fā)教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系 螺旋模型過程螺旋模型過程 建立開發(fā)者和用戶之間有效溝通 定義資源,進(jìn)度和 其他項(xiàng)目相關(guān)信息 建立項(xiàng)目的軟件模型編碼、測試、安裝、對用戶提供支持性培訓(xùn)等基于當(dāng)前階段所產(chǎn)生的軟件、原形或產(chǎn)出物的評估基于當(dāng)前階段所產(chǎn)生的軟件、原形或產(chǎn)出物

29、的評估 教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.4 軟件開發(fā)方法軟件開發(fā)方法 (1) 結(jié)構(gòu)化開發(fā)方法 結(jié)構(gòu)化方法是一種傳統(tǒng)的系統(tǒng)開發(fā)方法，它采用了系統(tǒng)科學(xué)的思想方法，從層次的角度，自頂向下地分析和設(shè)計(jì)系統(tǒng)。 (2) 面向?qū)ο筌浖_發(fā)方法 面向?qū)ο筌浖_發(fā)方法是一種以面向?qū)ο笏枷霝橹笇?dǎo)進(jìn)行系統(tǒng)開發(fā)的一類方法的總稱，這種方法以對象為中心，以類和繼承為構(gòu)造機(jī)制來抽象現(xiàn)實(shí)世界，通過建立模型，最終構(gòu)建相應(yīng)的軟件系統(tǒng)。教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系教學(xué)進(jìn)度教學(xué)進(jìn)度計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.5 軟件測試技術(shù)軟件測試技術(shù) 軟件測試(Tes