第五章 計算機軟件技術(shù)基礎(chǔ)

1、計算機科學(xué)與工程系計算機科學(xué)與工程系第五章第五章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 硬件是計算機系統(tǒng)的基礎(chǔ)，但沒有軟件的計算機硬件是計算機系統(tǒng)的基礎(chǔ)，但沒有軟件的計算機是無法工作的。計算機能廣泛地應(yīng)用于各個領(lǐng)域完全是無法工作的。計算機能廣泛地應(yīng)用于各個領(lǐng)域完全是因為有了豐富的計算機軟件。是因為有了豐富的計算機軟件。 本章將學(xué)習(xí)計算機軟件和計算機軟件開發(fā)的相關(guān)本章將學(xué)習(xí)計算機軟件和計算機軟件開發(fā)的相關(guān)知識，如什么是軟件，程序設(shè)計語言的分類及構(gòu)成、知識，如什么是軟件，程序設(shè)計語言的分類及構(gòu)成、數(shù)據(jù)結(jié)構(gòu)與算法、軟件開發(fā)過程等。數(shù)據(jù)結(jié)構(gòu)與算法、軟件開發(fā)過程等。 計算機科學(xué)與工程系計算機科學(xué)與工程系

2、5.1 計算機軟件系統(tǒng)計算機軟件系統(tǒng) 5.1.1 軟件的概念與特點軟件的概念與特點 軟件是由程序、數(shù)據(jù)及其相關(guān)文檔三部分組成。軟件是由程序、數(shù)據(jù)及其相關(guān)文檔三部分組成。 程序：按照事先設(shè)計的功能和性能要求執(zhí)行的程序：按照事先設(shè)計的功能和性能要求執(zhí)行的計算機指令序列。計算機指令序列。 數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。 文檔：與程序開發(fā)、維護和使用有關(guān)的資料。文檔：與程序開發(fā)、維護和使用有關(guān)的資料。計算機科學(xué)與工程系計算機科學(xué)與工程系5.1 計算機軟件系統(tǒng)計算機軟件系統(tǒng)5.1.2 軟件的分類軟件的分類 軟件可以按功能、工作方式、服務(wù)對象進行劃分，其軟

3、件可以按功能、工作方式、服務(wù)對象進行劃分，其中按軟件功能可劃分為：中按軟件功能可劃分為： 支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與維護的軟件。維護的軟件。 應(yīng)用軟件：針對特定領(lǐng)域開發(fā)，為特定目的服務(wù)的應(yīng)用軟件：針對特定領(lǐng)域開發(fā)，為特定目的服務(wù)的軟件。軟件。 系統(tǒng)軟件：能與計算機硬件緊密配合，使計算機系系統(tǒng)軟件：能與計算機硬件緊密配合，使計算機系統(tǒng)的各個部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效工作。統(tǒng)的各個部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效工作。 計算機科學(xué)與

4、工程系計算機科學(xué)與工程系5.1 計算機軟件系統(tǒng)計算機軟件系統(tǒng) 計算機軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是計算機軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。并列的，而是有一定的層次關(guān)系。 5.1.3 計算機軟件的層次結(jié)構(gòu)計算機軟件的層次結(jié)構(gòu)系統(tǒng)系統(tǒng)軟件軟件支撐支撐軟件軟件應(yīng)用應(yīng)用軟件軟件計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言 簡單講，程序設(shè)計就是用計算機語言編寫程序。簡單講，程序設(shè)計就是用計算機語言編寫程序。 程序程序 = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 編寫計算機程序時使用的語言稱為程序設(shè)計語編寫計算機程序時使用的語言稱為程序

5、設(shè)計語言言(Programming Language)，程序設(shè)計語言分為，程序設(shè)計語言分為機機器語言、匯編語言和高級語言器語言、匯編語言和高級語言三種。三種。對數(shù)據(jù)操作的步驟如何表示、組織和存儲數(shù)據(jù)計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言5.2.1 機器語言機器語言 機器語言是唯一能被計算機直接理解和執(zhí)行的程序設(shè)計機器語言是唯一能被計算機直接理解和執(zhí)行的程序設(shè)計語言，屬低級語言。機器語言的一條語句就是一條指令，機語言，屬低級語言。機器語言的一條語句就是一條指令，機器指令的格式如下：器指令的格式如下： 操作碼操作碼操作數(shù)操作數(shù)例如：計算例如：計算256+16結(jié)果的機器

6、代碼如下結(jié)果的機器代碼如下(以十六進制表示以十六進制表示)： B8 0001；把；把256放入累加器放入累加器AX05 1000；把；把16與與AX中值相加，結(jié)果存入中值相加，結(jié)果存入AX10111000 0000000100000101 00001000計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言5.2.2 匯編語言匯編語言 為了解決機器語言難記憶、可讀性差的缺點，人們把機為了解決機器語言難記憶、可讀性差的缺點，人們把機器指令中的操作碼和操作數(shù)用英文助記符來表示，這種助記器指令中的操作碼和操作數(shù)用英文助記符來表示，這種助記符語言稱為匯編語言，也屬于低級語言。符語言稱為

7、匯編語言，也屬于低級語言。 MOV AX， 256；把；把256放入累加器放入累加器AXADD AX， 16；把；把16與與AX中值相加，結(jié)果存入中值相加，結(jié)果存入AX 匯編語言編寫的程序?qū)儆诜柍绦?，計算機不能直接識匯編語言編寫的程序?qū)儆诜柍绦?，計算機不能直接識別和執(zhí)行，必須翻譯成計算機能識別的機器指令后才能在計別和執(zhí)行，必須翻譯成計算機能識別的機器指令后才能在計算機上執(zhí)行，其翻譯過程如下：算機上執(zhí)行，其翻譯過程如下： 計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言5.2.3 高級語言高級語言 高級語言是一類程序設(shè)計語言的統(tǒng)稱，它采用接近人類高級語言是一類程序設(shè)計語言

8、的統(tǒng)稱，它采用接近人類自然語言的表示方法，并遵循一定的語法規(guī)則來編寫程序。自然語言的表示方法，并遵循一定的語法規(guī)則來編寫程序。 實現(xiàn)求整數(shù)的絕對值的程序段：實現(xiàn)求整數(shù)的絕對值的程序段：int intVar, result;scanf(“%d”, &intVar);if(intVar = 0) result = intVar;else result = -1*intVar;printf(“%d的絕對值是：的絕對值是：%d”, intVar, result);計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言高級語言程序的翻譯和執(zhí)行過程如下：高級語言程序的翻譯和執(zhí)行過程如

9、下： 高級語言編寫的程序也屬于符號程序，不能直接在計算高級語言編寫的程序也屬于符號程序，不能直接在計算機上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代機上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代碼的方法主要有編譯和解釋兩種。碼的方法主要有編譯和解釋兩種。 計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言5.2.4 程序設(shè)計語言的構(gòu)成程序設(shè)計語言的構(gòu)成 程序設(shè)計語言的構(gòu)成主要包括以下幾個方面：程序設(shè)計語言的構(gòu)成主要包括以下幾個方面： (1) 數(shù)據(jù)類型數(shù)據(jù)類型 基本數(shù)據(jù)類型：是由程序設(shè)計語言內(nèi)置的，

10、其特點是不基本數(shù)據(jù)類型：是由程序設(shè)計語言內(nèi)置的，其特點是不能再分解為其它的類型。在主流的程序設(shè)計語言中一般包括：能再分解為其它的類型。在主流的程序設(shè)計語言中一般包括：整數(shù)類型、實數(shù)類型、字符類型、布爾類型等。整數(shù)類型、實數(shù)類型、字符類型、布爾類型等。 構(gòu)造數(shù)據(jù)類型：是由基本數(shù)據(jù)類型按照某種方式組合構(gòu)構(gòu)造數(shù)據(jù)類型：是由基本數(shù)據(jù)類型按照某種方式組合構(gòu)成的。常見的構(gòu)造數(shù)據(jù)類型有：數(shù)組類型、記錄類型成的。常見的構(gòu)造數(shù)據(jù)類型有：數(shù)組類型、記錄類型( (結(jié)構(gòu)結(jié)構(gòu)體體) ) 等等。等等。 (2) 運算符和表達式運算符和表達式 在程序設(shè)計中使用表達式可完成各種各樣的運算。表達在程序設(shè)計中使用表達式可完成各種各

11、樣的運算。表達式通常包括：常量、變量、運算符和函數(shù)調(diào)用等。式通常包括：常量、變量、運算符和函數(shù)調(diào)用等。計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言 (3) 語句語句 程序是對計算機要執(zhí)行的操作的描述，高級語言源程序的程序是對計算機要執(zhí)行的操作的描述，高級語言源程序的基本組成單位就是語句。基本組成單位就是語句。 語句按功能可以分為兩類：語句按功能可以分為兩類： 用于描述操作運算的語句，如賦值語句；用于描述操作運算的語句，如賦值語句； 用于控制操作運算流程的語句，如分支控制語句。用于控制操作運算流程的語句，如分支控制語句。 (4) 控制結(jié)構(gòu)控制結(jié)構(gòu) 順序結(jié)構(gòu)，按照語句出現(xiàn)的

12、先后順序依次執(zhí)行。順序結(jié)構(gòu)，按照語句出現(xiàn)的先后順序依次執(zhí)行。 分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。 循環(huán)結(jié)構(gòu)，循環(huán)循環(huán)結(jié)構(gòu)，循環(huán)( (重復(fù)重復(fù)) )是計算機解題的一個重要特征。是計算機解題的一個重要特征。計算機科學(xué)與工程系計算機科學(xué)與工程系5.2 程序設(shè)計語言程序設(shè)計語言 (5) 輸入輸入/輸出輸出 高級程序設(shè)計語言中通常以函數(shù)或語句的形式提供輸入高級程序設(shè)計語言中通常以函數(shù)或語句的形式提供輸入輸出操作?，F(xiàn)代高級程序設(shè)計語言通常都提供通過窗口、文輸出操作?，F(xiàn)代高級程序設(shè)計語言通常都提供通過窗口、文本框、按鈕、組合框、圖表等圖形組件進行

13、輸入輸出。本框、按鈕、組合框、圖表等圖形組件進行輸入輸出。 (6) 子程序子程序 子程序就是將需要重復(fù)使用的程序段或分解的子問題子程序就是將需要重復(fù)使用的程序段或分解的子問題編寫成一個獨立的子程序，當(dāng)程序中需要使用子程序時，編寫成一個獨立的子程序，當(dāng)程序中需要使用子程序時，再對其進行調(diào)用。再對其進行調(diào)用。 子程序有兩種：函數(shù)子程序有兩種：函數(shù)(Function)和過程和過程(Procedure)，它，它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。 計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.1 什么是數(shù)據(jù)什么是數(shù)據(jù) 數(shù)

14、據(jù)是對客觀事物的描述，對計算機來說，數(shù)字、字符、數(shù)據(jù)是對客觀事物的描述，對計算機來說，數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。圖形、色彩、聲音等都是數(shù)據(jù)。 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可以是一數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可以是一個單個數(shù)據(jù)也可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)不可分個單個數(shù)據(jù)也可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。割的最小單位。 例：公司員工數(shù)據(jù)的存儲例：公司員工數(shù)據(jù)的存儲( (一個員工信息可以構(gòu)造一個一個員工信息可以構(gòu)造一個一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)) ) 姓名姓名性別性別出生日期出生日期職位職位工資工資張軍張軍男男19

15、75.5.6總經(jīng)理總經(jīng)理2080.00李芳李芳女女1980.12.12項目經(jīng)理項目經(jīng)理1800.00王明王明男男1979.4.19程序員程序員1500.00劉杰劉杰男男1974.6.23系統(tǒng)分析員系統(tǒng)分析員1750.00數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)元素計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.2 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容 數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括容包括: :數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)運算。數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)運算。 (1)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素之

16、間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。構(gòu)，它描述數(shù)據(jù)的組織形式。元素之間是一對一關(guān)系元素之間是一對一關(guān)系例如例如:公司員工數(shù)據(jù)表中公司員工數(shù)據(jù)表中每個成員關(guān)系每個成員關(guān)系元素之間是多對多關(guān)系元素之間是多對多關(guān)系例如例如:華農(nóng)與周邊地區(qū)的華農(nóng)與周邊地區(qū)的位置關(guān)系位置關(guān)系元素之間是一對多關(guān)系元素之間是一對多關(guān)系例如例如:一對夫婦和他們的一對夫婦和他們的全部子孫全部子孫元素之間是松散關(guān)系元素之間是松散關(guān)系例如例如:自然數(shù)的全體自然數(shù)的全體計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(2) 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)

17、構(gòu) 數(shù)據(jù)在計算機存儲器中的存儲方式，稱為數(shù)據(jù)的物理結(jié)數(shù)據(jù)在計算機存儲器中的存儲方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)。它包括：構(gòu)或存儲結(jié)構(gòu)。它包括： 順序存儲方式，把邏輯上相鄰的數(shù)據(jù)元素存儲在物理順序存儲方式，把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中。上相鄰的存儲單元中。 鏈?zhǔn)酱鎯Ψ绞?，每個結(jié)點分為數(shù)據(jù)域和指針域兩部分，鏈?zhǔn)酱鎯Ψ绞?，每個結(jié)點分為數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲與該結(jié)點具有邏輯關(guān)系的數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲與該結(jié)點具有邏輯關(guān)系的結(jié)點的地址。結(jié)點的地址。 索引存儲方式，數(shù)據(jù)元素存放在一個不連續(xù)存儲區(qū)域索引存儲方式，數(shù)據(jù)元素存放在一個不連續(xù)存儲區(qū)域里

18、。再建一個附加的索引表，索引表中的第里。再建一個附加的索引表，索引表中的第i項表示第項表示第i個元個元素的存儲地址。素的存儲地址。 散列存儲方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲區(qū)散列存儲方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲區(qū)域里，用散列函數(shù)計算各結(jié)點的存儲地址。域里，用散列函數(shù)計算各結(jié)點的存儲地址。計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 例如例如:線性表是一種邏輯結(jié)構(gòu)線性表是一種邏輯結(jié)構(gòu),若采用順序存儲方式，可稱若采用順序存儲方式，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，可稱其為鏈表；若采用其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，可稱其為鏈表；若采用散列存儲方法，可稱其為散列表。散列

19、存儲方法，可稱其為散列表。 右圖為某學(xué)生各右圖為某學(xué)生各科成績表分別采用順科成績表分別采用順序和鏈?zhǔn)酱鎯Φ那樾?。序和鏈?zhǔn)酱鎯Φ那樾?。前者存儲在一片連續(xù)前者存儲在一片連續(xù)空間，后者則存儲在空間，后者則存儲在非連續(xù)空間。非連續(xù)空間。計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(3) 數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)的運算 數(shù)據(jù)結(jié)構(gòu)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插數(shù)據(jù)結(jié)構(gòu)的運算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、刪除、查找、排序等。入、刪除、查找、排序等。 比如一張表格，可能需要進行查找、增加、修改、刪除比如一張表格，可能需要進行查找、增加、修改、刪除記錄等，進行這樣的操作已不是加減

20、乘除這樣一些算術(shù)運算，記錄等，進行這樣的操作已不是加減乘除這樣一些算術(shù)運算，在數(shù)據(jù)結(jié)構(gòu)中，運算常常涉及算法的問題。在數(shù)據(jù)結(jié)構(gòu)中，運算常常涉及算法的問題。 計算機科學(xué)與工程系計算機科學(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ù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計算機內(nèi)存中使用一組連數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計算機內(nèi)存中使用一組連續(xù)的存儲單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有續(xù)的存儲單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有相同的變量名，稱為數(shù)組名。相同的變量名，稱為數(shù)組名。計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)

21、構(gòu)(2) 鏈表鏈表 鏈表鏈表(Linked List)是采用鏈?zhǔn)酱鎯Φ木€性表。線性鏈表的是采用鏈?zhǔn)酱鎯Φ木€性表。線性鏈表的結(jié)點由數(shù)據(jù)域和指針域兩個部分組成，數(shù)據(jù)域存儲數(shù)據(jù)元素，結(jié)點由數(shù)據(jù)域和指針域兩個部分組成，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲一個指向直接后繼結(jié)點的指針。指針域存儲一個指向直接后繼結(jié)點的指針。 計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(3) 二叉樹二叉樹 二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個結(jié)點的集合，該集合或者為空，或者滿足下面兩個樹是一個結(jié)點的集合，該集合或者為空，或者滿足下面兩個條件：條件

22、： 有且僅有一個稱為根的結(jié)點。有且僅有一個稱為根的結(jié)點。 其它結(jié)點分為兩個互不相交的集合其它結(jié)點分為兩個互不相交的集合T1、T2。T1和和T2均為二叉樹，并且在均為二叉樹，并且在T1和和T2之間存在順序關(guān)系之間存在順序關(guān)系(T1在在T2之之前前)，分別稱為根的左子樹和右子樹。，分別稱為根的左子樹和右子樹。 二叉樹的二叉樹的5 5種基本形態(tài)種基本形態(tài) 計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 計算機科學(xué)與工程系計算機科學(xué)與工程系5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹遍歷二叉樹 遍歷二叉樹是非常重要的一種運算。遍歷二叉樹是非常重要的一種運算?！氨闅v遍歷”的含義是的含

23、義是對結(jié)構(gòu)中的每個數(shù)據(jù)都訪問一次且僅訪問一次?？梢杂腥N對結(jié)構(gòu)中的每個數(shù)據(jù)都訪問一次且僅訪問一次?？梢杂腥N訪問路徑：訪問路徑： 前序遍歷前序遍歷: :訪問根結(jié)點訪問根結(jié)點; ;前序遍歷左子樹前序遍歷左子樹; ;前序遍歷右子樹前序遍歷右子樹 中序遍歷中序遍歷: :中序遍歷左子樹中序遍歷左子樹; ;訪問根結(jié)點訪問根結(jié)點; ;中序遍歷右子樹中序遍歷右子樹 后序遍歷后序遍歷: :后序遍歷左子樹后序遍歷左子樹; ;后序遍歷右子樹后序遍歷右子樹; ;訪問根結(jié)點訪問根結(jié)點 前序遍歷：前序遍歷：A B D E F G CA B D E F G C 中序遍歷：中序遍歷：D B F E G A CD B F E

24、 G A C 后序遍歷：后序遍歷：D F G E B C AD F G E B C A計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法5.4.1 算法的基本概念算法的基本概念 算法是指為解決給定問題而需實施的有窮操作算法是指為解決給定問題而需實施的有窮操作步驟的描述。步驟的描述。 5.4.2 算法的描述方法算法的描述方法 (1) 用自然語言描述算法用自然語言描述算法(2) 用流程圖描述算法用流程圖描述算法(3) 使用偽代碼描述算法使用偽代碼描述算法(4) 用程序設(shè)計語言描述算法用程序設(shè)計語言描述算法 算法的描述方法有以下四種：算法的描述方法有以下四種： 計算機科學(xué)與工程系計算機科學(xué)與工程系

25、5.4 算法算法5.4.3 查找算法查找算法(了解了解) 查找查找(Searching)也稱檢索，設(shè)表也稱檢索，設(shè)表F中有中有n個結(jié)點，個結(jié)點，Ki是記是記錄錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在，在F中尋找關(guān)鍵字與中尋找關(guān)鍵字與K相同相同的結(jié)點的結(jié)點R的過程，叫做查找。的過程，叫做查找。 (1) 順序查找順序查找 順序查找是線性表的最簡單的查找算法。它是用給定順序查找是線性表的最簡單的查找算法。它是用給定的值與表中的每個結(jié)點的關(guān)鍵字逐個進行比較運算，若找的值與表中的每個結(jié)點的關(guān)鍵字逐個進行比較運算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。到相等的關(guān)鍵字則查找成功，否則查

26、找失敗。 順序查找算法的優(yōu)點是適用范圍廣，對線性表中結(jié)點順序查找算法的優(yōu)點是適用范圍廣，對線性表中結(jié)點邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理存儲結(jié)構(gòu)也沒有要求，順序存儲與鏈?zhǔn)酱鎯?。存儲結(jié)構(gòu)也沒有要求，順序存儲與鏈?zhǔn)酱鎯?。計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法(2) 折半查找折半查找 折半查找的基本思想是：折半查找的基本思想是： 先取表的中間位置的結(jié)點關(guān)鍵字與所給定的關(guān)鍵字進行比先取表的中間位置的結(jié)點關(guān)鍵字與所給定的關(guān)鍵字進行比較，如果相等，則查找成功。如果給定值比該結(jié)點的關(guān)鍵字較，如果相等，則查找成功。如果給定

27、值比該結(jié)點的關(guān)鍵字大，則所找結(jié)點在表的后半部分；否則所找結(jié)點在表的前半大，則所找結(jié)點在表的后半部分；否則所找結(jié)點在表的前半部分，然后再把選定的部分表的中間結(jié)點的關(guān)鍵字與給定關(guān)部分，然后再把選定的部分表的中間結(jié)點的關(guān)鍵字與給定關(guān)鍵字進行比較。如此反復(fù)進行，直到查找成功或者查找失敗鍵字進行比較。如此反復(fù)進行，直到查找成功或者查找失敗為止。為止。計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法例: 計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法5.4.4 排序算法排序算法(了解了解) 排序排序(Sort)是數(shù)據(jù)處理中的一種重要運算，它的功能是將是數(shù)據(jù)處理中的一種重要運算，它的功能是將一組數(shù)

28、據(jù)元素一組數(shù)據(jù)元素(或記錄或記錄)從任意序列排列成一個按關(guān)鍵字排序的從任意序列排列成一個按關(guān)鍵字排序的序列。序列。 按照排序過程中涉及的存儲器的不同將排序分為內(nèi)部排按照排序過程中涉及的存儲器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個排序過程都在內(nèi)序和外部排序兩類，其中內(nèi)部排序是指整個排序過程都在內(nèi)存中進行的排序。存中進行的排序。 計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法(1) 直接插入排序直接插入排序 算法的基本思想如下：算法的基本思想如下： 開始時，把第一個記錄看成是已經(jīng)排好序的子序列，開始時，把第一個記錄看成是已經(jīng)排好序的子序列，這時子序列中只有一個記錄；這時

29、子序列中只有一個記錄； 從第二個記錄起到最后一個記錄，依次將每個記錄從第二個記錄起到最后一個記錄，依次將每個記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置；與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置； 將記錄插入到子序列中，子序列記錄個數(shù)加將記錄插入到子序列中，子序列記錄個數(shù)加1，直至，直至子序列長度與待排序列長度相等時結(jié)束。子序列長度與待排序列長度相等時結(jié)束。計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法(1) 直接插入排序 計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法5.4.4 排序算法排序算法(了解了解) (2) 冒泡排序冒泡排序冒泡排序的算法思想是：冒泡排

30、序的算法思想是： 將第將第n個記錄的關(guān)鍵字與將第個記錄的關(guān)鍵字與將第n-1個記錄的關(guān)鍵字進行比較，若為逆?zhèn)€記錄的關(guān)鍵字進行比較，若為逆序則將兩個記錄進行位置的交換，否則保持原來順序；序則將兩個記錄進行位置的交換，否則保持原來順序； 將第將第n-1個記錄的關(guān)鍵字與將第個記錄的關(guān)鍵字與將第n-2個記錄的關(guān)鍵字進行比較；個記錄的關(guān)鍵字進行比較； 重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍；重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍； 上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第的記錄被交換到了第1個記錄的位置，

31、完成一趟排序；個記錄的位置，完成一趟排序； 第二趟排序從第第二趟排序從第n個記錄到第個記錄到第2個記錄進行同樣的操作，結(jié)果是使關(guān)個記錄進行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第鍵字次小的記錄被交換到了第2個記錄的位置；個記錄的位置；依次類推，第依次類推，第i趟排序是從第趟排序是從第n個記錄到第個記錄到第i個記錄依次比較交換。個記錄依次比較交換。計算機科學(xué)與工程系計算機科學(xué)與工程系5.4 算法算法(2) 冒泡排序計算機科學(xué)與工程系計算機科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.1 軟件工程提出軟件工程提出 早期早期, ,在軟件開發(fā)過程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展在軟件開發(fā)過程

32、中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展的問題，主要表現(xiàn)在以下幾個方面：的問題，主要表現(xiàn)在以下幾個方面： 軟件開發(fā)無計劃性。軟件開發(fā)無計劃性。 軟件開發(fā)過程無規(guī)范。軟件開發(fā)過程無規(guī)范。 軟件產(chǎn)品無評測手段。軟件產(chǎn)品無評測手段。 1990年電氣電子工程師協(xié)會年電氣電子工程師協(xié)會(IEEE)給出了軟件工程的一給出了軟件工程的一個定義：個定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件開發(fā)、運行和維護的過程，也就是把工程化運用應(yīng)用于軟件開發(fā)、運行和維護的過程，也就是把工程化運用于軟件工程，并對這樣的方法進行研究于軟件工程，并對這樣的方法進行研究”。計算機科學(xué)

33、與工程系計算機科學(xué)與工程系5.5 軟件工程簡介軟件工程簡介5.5.2 軟件生命周期軟件生命周期 制定計劃：確定要開發(fā)軟件系統(tǒng)的總體目標(biāo)。制定計劃：確定要開發(fā)軟件系統(tǒng)的總體目標(biāo)。 需求分析：對要開發(fā)軟件提出的需求進行分析并給出詳細定義。需求分析：對要開發(fā)軟件提出的需求進行分析并給出詳細定義。 軟件設(shè)計：設(shè)計人員首先進行概要設(shè)計，然后進行詳細設(shè)計，為軟件設(shè)計：設(shè)計人員首先進行概要設(shè)計，然后進行詳細設(shè)計，為程序代碼的編寫打下基礎(chǔ)。程序代碼的編寫打下基礎(chǔ)。 程序編碼：使用程序設(shè)計語言把軟件設(shè)計轉(zhuǎn)換成計算機可以接受程序編碼：使用程序設(shè)計語言把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼，也稱為軟件實現(xiàn)。的程序代碼，也稱為軟件實現(xiàn)。 軟件測試：測試是保證軟件質(zhì)量的重要手段。軟件測試：測試是保證軟件質(zhì)量的重要手段。 運行與維護：軟件交付后就進入它的運行時期