【學(xué)習(xí)】第五章計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

1、計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt 硬件是計(jì)算機(jī)系統(tǒng)的基礎(chǔ)，但沒有軟件的計(jì)算機(jī)硬件是計(jì)算機(jī)系統(tǒng)的基礎(chǔ)，但沒有軟件的計(jì)算機(jī)是無(wú)法工作的。計(jì)算機(jī)能廣泛地應(yīng)用于各個(gè)領(lǐng)域完全是無(wú)法工作的。計(jì)算機(jī)能廣泛地應(yīng)用于各個(gè)領(lǐng)域完全是因?yàn)橛辛素S富的計(jì)算機(jī)軟件。是因?yàn)橛辛素S富的計(jì)算機(jī)軟件。 本章將學(xué)習(xí)計(jì)算機(jī)軟件和計(jì)算機(jī)軟件開發(fā)的相關(guān)本章將學(xué)習(xí)計(jì)算機(jī)軟件和計(jì)算機(jī)軟件開發(fā)的相關(guān)知識(shí)，如什么是軟件，程序設(shè)計(jì)語(yǔ)言的分類及構(gòu)成、知識(shí)，如什么是軟件，程序設(shè)計(jì)語(yǔ)言的分類及構(gòu)成、數(shù)據(jù)結(jié)構(gòu)與算法、軟件開發(fā)過(guò)程等。數(shù)據(jù)結(jié)構(gòu)與算法、軟件開發(fā)過(guò)程等。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.1.1 軟件的概念與特點(diǎn)軟

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

3、軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與維護(hù)的軟件。維護(hù)的軟件。 應(yīng)用軟件：針對(duì)特定領(lǐng)域開發(fā)，為特定目的服務(wù)的應(yīng)用軟件：針對(duì)特定領(lǐng)域開發(fā)，為特定目的服務(wù)的軟件。軟件。 系統(tǒng)軟件：能與計(jì)算機(jī)硬件緊密配合，使計(jì)算機(jī)系系統(tǒng)軟件：能與計(jì)算機(jī)硬件緊密配合，使計(jì)算機(jī)系統(tǒng)的各個(gè)部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效工作。統(tǒng)的各個(gè)部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效工作。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt 計(jì)算機(jī)軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是計(jì)算機(jī)軟件系

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

5、言三種。三種。對(duì)數(shù)據(jù)操作的步驟如何表示、組織和存儲(chǔ)數(shù)據(jù)計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.2.1 機(jī)器語(yǔ)言機(jī)器語(yǔ)言 機(jī)器語(yǔ)言是唯一能被計(jì)算機(jī)直接理解和執(zhí)行的程序設(shè)計(jì)機(jī)器語(yǔ)言是唯一能被計(jì)算機(jī)直接理解和執(zhí)行的程序設(shè)計(jì)語(yǔ)言，屬低級(jí)語(yǔ)言。機(jī)器語(yǔ)言的一條語(yǔ)句就是一條指令，機(jī)語(yǔ)言，屬低級(jí)語(yǔ)言。機(jī)器語(yǔ)言的一條語(yǔ)句就是一條指令，機(jī)器指令的格式如下：器指令的格式如下： 操作碼操作碼操作數(shù)操作數(shù)例如：計(jì)算例如：計(jì)算256+16結(jié)果的機(jī)器代碼如下結(jié)果的機(jī)器代碼如下(以十六進(jìn)制表示以十六進(jìn)制表示)： B8 0001；把；把256放入累加器放入累加器AX05 1000；把；把16與與AX中值相加，結(jié)果存入

6、中值相加，結(jié)果存入AX10111000 0000000100000101 00001000計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.2.2 匯編語(yǔ)言匯編語(yǔ)言 為了解決機(jī)器語(yǔ)言難記憶、可讀性差的缺點(diǎn)，人們把機(jī)為了解決機(jī)器語(yǔ)言難記憶、可讀性差的缺點(diǎn)，人們把機(jī)器指令中的操作碼和操作數(shù)用英文助記符來(lái)表示，這種助記器指令中的操作碼和操作數(shù)用英文助記符來(lái)表示，這種助記符語(yǔ)言稱為匯編語(yǔ)言，也屬于低級(jí)語(yǔ)言。符語(yǔ)言稱為匯編語(yǔ)言，也屬于低級(jí)語(yǔ)言。 MOV AX， 256；把；把256放入累加器放入累加器AXADD AX， 16；把；把16與與AX中值相加，結(jié)果存入中值相加，結(jié)果存入AX 匯編語(yǔ)言編寫的程序

7、屬于符號(hào)程序，計(jì)算機(jī)不能直接識(shí)匯編語(yǔ)言編寫的程序?qū)儆诜?hào)程序，計(jì)算機(jī)不能直接識(shí)別和執(zhí)行，必須翻譯成計(jì)算機(jī)能識(shí)別的機(jī)器指令后才能在計(jì)別和執(zhí)行，必須翻譯成計(jì)算機(jī)能識(shí)別的機(jī)器指令后才能在計(jì)算機(jī)上執(zhí)行，其翻譯過(guò)程如下：算機(jī)上執(zhí)行，其翻譯過(guò)程如下： 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.2.3 高級(jí)語(yǔ)言高級(jí)語(yǔ)言 高級(jí)語(yǔ)言是一類程序設(shè)計(jì)語(yǔ)言的統(tǒng)稱，它采用接近人類高級(jí)語(yǔ)言是一類程序設(shè)計(jì)語(yǔ)言的統(tǒng)稱，它采用接近人類自然語(yǔ)言的表示方法，并遵循一定的語(yǔ)法規(guī)則來(lái)編寫程序。自然語(yǔ)言的表示方法，并遵循一定的語(yǔ)法規(guī)則來(lái)編寫程序。 實(shí)現(xiàn)求整數(shù)的絕對(duì)值的程序段：實(shí)現(xiàn)求整數(shù)的絕對(duì)值的程序段：int intVar, r

8、esult;scanf(“%d”, &intVar);if(intVar = 0) result = intVar;else result = -1*intVar;printf(“%d的絕對(duì)值是：的絕對(duì)值是：%d”, intVar, result);計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt高級(jí)語(yǔ)言程序的翻譯和執(zhí)行過(guò)程如下：高級(jí)語(yǔ)言程序的翻譯和執(zhí)行過(guò)程如下： 高級(jí)語(yǔ)言編寫的程序也屬于符號(hào)程序，不能直接在計(jì)算高級(jí)語(yǔ)言編寫的程序也屬于符號(hào)程序，不能直接在計(jì)算機(jī)上執(zhí)行，必須通過(guò)程序的翻譯才能執(zhí)行，其翻譯成指令代機(jī)上執(zhí)行，必須通過(guò)程序的翻譯才能執(zhí)行，其翻譯成指令代碼的方法主要有編譯和解釋兩

9、種。碼的方法主要有編譯和解釋兩種。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.2.4 程序設(shè)計(jì)語(yǔ)言的構(gòu)成程序設(shè)計(jì)語(yǔ)言的構(gòu)成 程序設(shè)計(jì)語(yǔ)言的構(gòu)成主要包括以下幾個(gè)方面：程序設(shè)計(jì)語(yǔ)言的構(gòu)成主要包括以下幾個(gè)方面： (1) 數(shù)據(jù)類型數(shù)據(jù)類型 基本數(shù)據(jù)類型：是由程序設(shè)計(jì)語(yǔ)言內(nèi)置的，其特點(diǎn)是不基本數(shù)據(jù)類型：是由程序設(shè)計(jì)語(yǔ)言內(nèi)置的，其特點(diǎn)是不能再分解為其它的類型。在主流的程序設(shè)計(jì)語(yǔ)言中一般包括：能再分解為其它的類型。在主流的程序設(shè)計(jì)語(yǔ)言中一般包括：整數(shù)類型、實(shí)數(shù)類型、字符類型、布爾類型等。整數(shù)類型、實(shí)數(shù)類型、字符類型、布爾類型等。 構(gòu)造數(shù)據(jù)類型：是由基本數(shù)

10、據(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) 運(yùn)算符和表達(dá)式運(yùn)算符和表達(dá)式 在程序設(shè)計(jì)中使用表達(dá)式可完成各種各樣的運(yùn)算。表達(dá)在程序設(shè)計(jì)中使用表達(dá)式可完成各種各樣的運(yùn)算。表達(dá)式通常包括：常量、變量、運(yùn)算符和函數(shù)調(diào)用等。式通常包括：常量、變量、運(yùn)算符和函數(shù)調(diào)用等。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt (3) 語(yǔ)句語(yǔ)句 程序是對(duì)計(jì)算機(jī)要執(zhí)行的操作的描述，高級(jí)語(yǔ)言源程序的程序是對(duì)計(jì)算機(jī)要執(zhí)行的操作的描述，高級(jí)語(yǔ)言源程序的基本組成

11、單位就是語(yǔ)句?；窘M成單位就是語(yǔ)句。 語(yǔ)句按功能可以分為兩類：語(yǔ)句按功能可以分為兩類： 用于描述操作運(yùn)算的語(yǔ)句，如賦值語(yǔ)句；用于描述操作運(yùn)算的語(yǔ)句，如賦值語(yǔ)句； 用于控制操作運(yùn)算流程的語(yǔ)句，如分支控制語(yǔ)句。用于控制操作運(yùn)算流程的語(yǔ)句，如分支控制語(yǔ)句。 (4) 控制結(jié)構(gòu)控制結(jié)構(gòu) 順序結(jié)構(gòu)，按照語(yǔ)句出現(xiàn)的先后順序依次執(zhí)行。順序結(jié)構(gòu)，按照語(yǔ)句出現(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ù)) )是計(jì)算機(jī)解題的一個(gè)重要特征。是計(jì)算機(jī)解題的一個(gè)重要特征。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程

12、系編輯ppt (5) 輸入輸入/輸出輸出 高級(jí)程序設(shè)計(jì)語(yǔ)言中通常以函數(shù)或語(yǔ)句的形式提供輸入高級(jí)程序設(shè)計(jì)語(yǔ)言中通常以函數(shù)或語(yǔ)句的形式提供輸入輸出操作?，F(xiàn)代高級(jí)程序設(shè)計(jì)語(yǔ)言通常都提供通過(guò)窗口、文輸出操作?，F(xiàn)代高級(jí)程序設(shè)計(jì)語(yǔ)言通常都提供通過(guò)窗口、文本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。 (6) 子程序子程序 子程序就是將需要重復(fù)使用的程序段或分解的子問(wèn)題編子程序就是將需要重復(fù)使用的程序段或分解的子問(wèn)題編寫成一個(gè)獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對(duì)寫成一個(gè)獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對(duì)其進(jìn)行調(diào)用。其進(jìn)行調(diào)用。 子程序有兩種

13、：函數(shù)子程序有兩種：函數(shù)(Function)和過(guò)程和過(guò)程(Procedure)，它，它們的主要區(qū)別是函數(shù)有返回值，而過(guò)程不能有返回值。們的主要區(qū)別是函數(shù)有返回值，而過(guò)程不能有返回值。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.3.1 什么是數(shù)據(jù)什么是數(shù)據(jù) 數(shù)據(jù)是對(duì)客觀事物的描述，對(duì)計(jì)算機(jī)來(lái)說(shuō)，數(shù)字、字符、數(shù)據(jù)是對(duì)客觀事物的描述，對(duì)計(jì)算機(jī)來(lái)說(shuō)，數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。圖形、色彩、聲音等都是數(shù)據(jù)。 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以是一數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以是一個(gè)單個(gè)數(shù)據(jù)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分個(gè)單個(gè)數(shù)據(jù)也可以由若干個(gè)

14、數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。割的最小單位。 例：公司員工數(shù)據(jù)的存儲(chǔ)例：公司員工數(shù)據(jù)的存儲(chǔ)( (一個(gè)員工信息可以構(gòu)造一個(gè)一一個(gè)員工信息可以構(gòu)造一個(gè)一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)維數(shù)組的數(shù)據(jù)結(jié)構(gòu)) ) 姓名姓名性別性別出生日期出生日期職位職位工資工資張軍張軍男男1975.5.6總經(jīng)理總經(jīng)理2080.00李芳李芳女女1980.12.12項(xiàng)目經(jīng)理項(xiàng)目經(jīng)理1800.00王明王明男男1979.4.19程序員程序員1500.00劉杰劉杰男男1974.6.23系統(tǒng)分析員系統(tǒng)分析員1750.00數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)數(shù)據(jù)元素?cái)?shù)據(jù)元素計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.3.2 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容數(shù)據(jù)結(jié)構(gòu)研

15、究的內(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)運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)運(yùn)算。 (1)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。它描述數(shù)據(jù)的組織形式。元素之間是一對(duì)一關(guān)系元素之間是一對(duì)一關(guān)系例如例如:公司員工數(shù)據(jù)表中公司員工數(shù)據(jù)表中每個(gè)成員關(guān)系每個(gè)成員關(guān)系元素之間是多對(duì)多關(guān)系元素之間是多對(duì)多關(guān)系例如例如:華農(nóng)與周邊地區(qū)的華農(nóng)與周邊地區(qū)的位置關(guān)系位置關(guān)系元素之間是

16、一對(duì)多關(guān)系元素之間是一對(duì)多關(guān)系例如例如:一對(duì)夫婦和他們的一對(duì)夫婦和他們的全部子孫全部子孫元素之間是松散關(guān)系元素之間是松散關(guān)系例如例如:自然數(shù)的全體自然數(shù)的全體計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(2) 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，稱為數(shù)據(jù)的物理結(jié)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)。它包括：構(gòu)或存儲(chǔ)結(jié)構(gòu)。它包括： 順序存儲(chǔ)方式，把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理順序存儲(chǔ)方式，把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中。上相鄰的存儲(chǔ)單元中。 鏈?zhǔn)酱鎯?chǔ)方式，每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域兩部分，鏈?zhǔn)酱鎯?chǔ)方式，每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和

17、指針域兩部分，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)與該結(jié)點(diǎn)具有邏輯關(guān)系的數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)與該結(jié)點(diǎn)具有邏輯關(guān)系的結(jié)點(diǎn)的地址。結(jié)點(diǎn)的地址。 索引存儲(chǔ)方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲(chǔ)區(qū)域索引存儲(chǔ)方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲(chǔ)區(qū)域里。再建一個(gè)附加的索引表，索引表中的第里。再建一個(gè)附加的索引表，索引表中的第i項(xiàng)表示第項(xiàng)表示第i個(gè)元個(gè)元素的存儲(chǔ)地址。素的存儲(chǔ)地址。 散列存儲(chǔ)方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲(chǔ)區(qū)散列存儲(chǔ)方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲(chǔ)區(qū)域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲(chǔ)地址。域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲(chǔ)地址。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt 例如例如:線性

18、表是一種邏輯結(jié)構(gòu)線性表是一種邏輯結(jié)構(gòu),若采用順序存儲(chǔ)方式，可稱若采用順序存儲(chǔ)方式，可稱其為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法，可稱其為鏈表；若采用散其為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法，可稱其為鏈表；若采用散列存儲(chǔ)方法，可稱其為散列表。列存儲(chǔ)方法，可稱其為散列表。 右圖為某學(xué)生各右圖為某學(xué)生各科成績(jī)表分別采用順科成績(jī)表分別采用順序和鏈?zhǔn)酱鎯?chǔ)的情形。序和鏈?zhǔn)酱鎯?chǔ)的情形。前者存儲(chǔ)在一片連續(xù)前者存儲(chǔ)在一片連續(xù)空間，后者則存儲(chǔ)在空間，后者則存儲(chǔ)在非連續(xù)空間。非連續(xù)空間。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(3) 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、數(shù)據(jù)結(jié)構(gòu)的運(yùn)

19、算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、刪除、查找、排序等。刪除、查找、排序等。 比如一張表格，可能需要進(jìn)行查找、增加、修改、刪除記比如一張表格，可能需要進(jìn)行查找、增加、修改、刪除記錄等，進(jìn)行這樣的操作已不是加減乘除這樣一些算術(shù)運(yùn)算，在錄等，進(jìn)行這樣的操作已不是加減乘除這樣一些算術(shù)運(yùn)算，在數(shù)據(jù)結(jié)構(gòu)中，運(yùn)算常常涉及算法的問(wèn)題。數(shù)據(jù)結(jié)構(gòu)中，運(yùn)算常常涉及算法的問(wèn)題。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.3.3 常見數(shù)據(jù)結(jié)構(gòu)介紹常見數(shù)據(jù)結(jié)構(gòu)介紹 (了解了解)(1) 數(shù)組數(shù)組 數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計(jì)算機(jī)內(nèi)存中使用一組連數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計(jì)算機(jī)內(nèi)存中使用一組連續(xù)的存儲(chǔ)單元保存數(shù)

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

21、：二叉二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個(gè)結(jié)點(diǎn)的集合，該集合或者為空，或者滿足下面兩個(gè)樹是一個(gè)結(jié)點(diǎn)的集合，該集合或者為空，或者滿足下面兩個(gè)條件：條件： 有且僅有一個(gè)稱為根的結(jié)點(diǎn)。有且僅有一個(gè)稱為根的結(jié)點(diǎn)。 其它結(jié)點(diǎn)分為兩個(gè)互不相交的集合其它結(jié)點(diǎn)分為兩個(gè)互不相交的集合T1、T2。T1和和T2均為二叉樹，并且在均為二叉樹，并且在T1和和T2之間存在順序關(guān)系之間存在順序關(guān)系(T1在在T2之之前前)，分別稱為根的左子樹和右子樹。，分別稱為根的左子樹和右子樹。 二叉樹的二叉樹的5 5種基本形態(tài)種基本形態(tài) 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt二叉樹的存儲(chǔ)結(jié)構(gòu) 計(jì)算機(jī)科學(xué)與工程

22、系計(jì)算機(jī)科學(xué)與工程系編輯ppt遍歷二叉樹遍歷二叉樹 遍歷二叉樹是非常重要的一種運(yùn)算。遍歷二叉樹是非常重要的一種運(yùn)算。“遍歷遍歷”的含義是的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)都訪問(wèn)一次且僅訪問(wèn)一次?？梢杂腥N對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)都訪問(wèn)一次且僅訪問(wèn)一次?？梢杂腥N訪問(wèn)路徑：訪問(wèn)路徑： 前序遍歷前序遍歷: :訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn); ;前序遍歷左子樹前序遍歷左子樹; ;前序遍歷右子樹前序遍歷右子樹 中序遍歷中序遍歷: :中序遍歷左子樹中序遍歷左子樹; ;訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn); ;中序遍歷右子樹中序遍歷右子樹 后序遍歷后序遍歷: :后序遍歷左子樹后序遍歷左子樹; ;后序遍歷右子樹后序遍歷右子樹; ;訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根

23、結(jié)點(diǎn) 前序遍歷：前序遍歷：A B D E F G CA B D E F G C 中序遍歷：中序遍歷：D B F E G A CD B F E G A C 后序遍歷：后序遍歷：D F G E B C AD F G E B C A計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.4.1 算法的基本概念算法的基本概念 算法是指為解決給定問(wèn)題而需實(shí)施的有窮操作算法是指為解決給定問(wèn)題而需實(shí)施的有窮操作步驟的描述。步驟的描述。 5.4.2 算法的描述方法算法的描述方法 (1) 用自然語(yǔ)言描述算法用自然語(yǔ)言描述算法(2) 用流程圖描述算法用流程圖描述算法(3) 使用偽代碼描述算法使用偽代碼描述算法(4) 用

24、程序設(shè)計(jì)語(yǔ)言描述算法用程序設(shè)計(jì)語(yǔ)言描述算法 算法的描述方法有以下四種：算法的描述方法有以下四種： 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.4.3 查找算法查找算法(了解了解) 查找查找(Searching)也稱檢索，設(shè)表也稱檢索，設(shè)表F中有中有n個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，Ki是記是記錄錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在，在F中尋找關(guān)鍵字與中尋找關(guān)鍵字與K相同相同的結(jié)點(diǎn)的結(jié)點(diǎn)R的過(guò)程，叫做查找。的過(guò)程，叫做查找。 (1) 順序查找順序查找 順序查找是線性表的最簡(jiǎn)單的查找算法。它是用給定的順序查找是線性表的最簡(jiǎn)單的查找算法。它是用給定的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)

25、算，若找到相值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。等的關(guān)鍵字則查找成功，否則查找失敗。 順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對(duì)線性表中結(jié)點(diǎn)邏順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對(duì)線性表中結(jié)點(diǎn)邏輯次序無(wú)關(guān)，即不要求按關(guān)鍵字排序。對(duì)線性表的物理存儲(chǔ)輯次序無(wú)關(guān)，即不要求按關(guān)鍵字排序。對(duì)線性表的物理存儲(chǔ)結(jié)構(gòu)也沒有要求，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)均可。結(jié)構(gòu)也沒有要求，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)均可。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(2) 折半查找折半查找 折半查找的基本思想是：折半查找的基本思想是： 先取表的中間位置的結(jié)點(diǎn)關(guān)鍵字與所給定的關(guān)鍵字進(jìn)行比先取表的中間位

26、置的結(jié)點(diǎn)關(guān)鍵字與所給定的關(guān)鍵字進(jìn)行比較，如果相等，則查找成功。如果給定值比該結(jié)點(diǎn)的關(guān)鍵字大，較，如果相等，則查找成功。如果給定值比該結(jié)點(diǎn)的關(guān)鍵字大，則所找結(jié)點(diǎn)在表的后半部分；否則所找結(jié)點(diǎn)在表的前半部分，則所找結(jié)點(diǎn)在表的后半部分；否則所找結(jié)點(diǎn)在表的前半部分，然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字進(jìn)行然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字進(jìn)行比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失敗為止。比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失敗為止。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt例: 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.4.4 排序算法排序算法(了解了解

27、) 排序排序(Sort)是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是將是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是將一組數(shù)據(jù)元素一組數(shù)據(jù)元素(或記錄或記錄)從任意序列排列成一個(gè)按關(guān)鍵字排序的從任意序列排列成一個(gè)按關(guān)鍵字排序的序列。序列。 按照排序過(guò)程中涉及的存儲(chǔ)器的不同將排序分為內(nèi)部排序按照排序過(guò)程中涉及的存儲(chǔ)器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過(guò)程都在內(nèi)存和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過(guò)程都在內(nèi)存中進(jìn)行的排序。中進(jìn)行的排序。 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(1) 直接插入排序直接插入排序 算法的基本思想如下：算法的基本思想如下： 開始時(shí)，把第一個(gè)記

28、錄看成是已經(jīng)排好序的子序列，開始時(shí)，把第一個(gè)記錄看成是已經(jīng)排好序的子序列，這時(shí)子序列中只有一個(gè)記錄；這時(shí)子序列中只有一個(gè)記錄； 從第二個(gè)記錄起到最后一個(gè)記錄，依次將每個(gè)記錄從第二個(gè)記錄起到最后一個(gè)記錄，依次將每個(gè)記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置；與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置； 將記錄插入到子序列中，子序列記錄個(gè)數(shù)加將記錄插入到子序列中，子序列記錄個(gè)數(shù)加1，直至，直至子序列長(zhǎng)度與待排序列長(zhǎng)度相等時(shí)結(jié)束。子序列長(zhǎng)度與待排序列長(zhǎng)度相等時(shí)結(jié)束。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(1) 直接插入排序 計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5

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

30、換過(guò)程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第記錄被交換到了第1個(gè)記錄的位置，完成一趟排序；個(gè)記錄的位置，完成一趟排序； 第二趟排序從第第二趟排序從第n個(gè)記錄到第個(gè)記錄到第2個(gè)記錄進(jìn)行同樣的操作，結(jié)果是使關(guān)個(gè)記錄進(jìn)行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第鍵字次小的記錄被交換到了第2個(gè)記錄的位置；個(gè)記錄的位置；依次類推，第依次類推，第i趟排序是從第趟排序是從第n個(gè)記錄到第個(gè)記錄到第i個(gè)記錄依次比較交換。個(gè)記錄依次比較交換。計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt(2) 冒泡排序計(jì)算機(jī)科學(xué)與工程系計(jì)算機(jī)科學(xué)與工程系編輯ppt5.5.1 軟件工程提出軟件工程提出 早期早

31、期, ,在軟件開發(fā)過(guò)程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展的在軟件開發(fā)過(guò)程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展的問(wèn)題，主要表現(xiàn)在以下幾個(gè)方面：?jiǎn)栴}，主要表現(xiàn)在以下幾個(gè)方面： 軟件開發(fā)無(wú)計(jì)劃性。軟件開發(fā)無(wú)計(jì)劃性。 軟件開發(fā)過(guò)程無(wú)規(guī)范。軟件開發(fā)過(guò)程無(wú)規(guī)范。 軟件產(chǎn)品無(wú)評(píng)測(cè)手段。軟件產(chǎn)品無(wú)評(píng)測(cè)手段。 1990年電氣電子工程師協(xié)會(huì)年電氣電子工程師協(xié)會(huì)(IEEE)給出了軟件工程的一給出了軟件工程的一個(gè)定義：個(gè)定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過(guò)程，也就是把工程化運(yùn)用應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過(guò)程，也就是把工程化運(yùn)用于軟件工程，并對(duì)這

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