高校計(jì)算機(jī)教學(xué)第五章計(jì)算機(jī)軟件技術(shù)基礎(chǔ)配套課件

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

2、文檔三部分組成。軟件是由程序、數(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)的資料。5.1 計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)軟件系統(tǒng)5.1.2 軟件的分類軟件的分類 軟件可以按功能、工作方式、服務(wù)對象進(jìn)行劃分，其軟件可以按功能、工作方式、服務(wù)對象進(jìn)行劃分，其中按軟件功能可劃分為：中按軟件功能可劃分為： 支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件支撐軟件：又

3、稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與維護(hù)的軟件。維護(hù)的軟件。 應(yīng)用軟件：針對特定領(lǐng)域開發(fā)，為特定目的服務(wù)的應(yīng)用軟件：針對特定領(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)、高效工作。 5.1 計(jì)算機(jī)軟件系統(tǒng) 計(jì)算機(jī)軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是計(jì)算機(jī)軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。并列的，而是

4、有一定的層次關(guān)系。 5.1.3 計(jì)算機(jī)軟件的層次結(jié)計(jì)算機(jī)軟件的層次結(jié)構(gòu)構(gòu)系統(tǒng)系統(tǒng)軟件軟件支撐支撐軟件軟件應(yīng)用應(yīng)用軟件軟件5.2 程序設(shè)計(jì)語言 計(jì)算機(jī)的本質(zhì)是計(jì)算機(jī)的本質(zhì)是“程序的機(jī)器程序的機(jī)器”，程序和指令的思想是，程序和指令的思想是計(jì)算機(jī)系統(tǒng)中最基本的概念。只有懂得程序設(shè)計(jì)，才能懂得計(jì)算機(jī)系統(tǒng)中最基本的概念。只有懂得程序設(shè)計(jì)，才能懂得計(jì)算機(jī)，真正了解計(jì)算機(jī)是怎樣工作的。計(jì)算機(jī)，真正了解計(jì)算機(jī)是怎樣工作的。什么人需要學(xué)程序設(shè)計(jì)什么人需要學(xué)程序設(shè)計(jì)比爾蓋茨說比爾蓋茨說 最最 終終 用用 戶戶 Office等等 程序開發(fā)人員程序開發(fā)人員-Visual Basic等等 系統(tǒng)開發(fā)人員系統(tǒng)開發(fā)人員-Vi

5、sual C+等等你聽過用過哪些編程語言？你聽過用過哪些編程語言？ BASIC、VB、VB.NET C、VC+、C# FORTRAN PASCAL、Delphi COBOL Java 5.2 程序設(shè)計(jì)語言 簡單講，程序設(shè)計(jì)就是用計(jì)算機(jī)語言編寫程序。簡單講，程序設(shè)計(jì)就是用計(jì)算機(jī)語言編寫程序。 程序程序 = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 編寫計(jì)算機(jī)程序時(shí)使用的語言稱為程序設(shè)計(jì)語編寫計(jì)算機(jī)程序時(shí)使用的語言稱為程序設(shè)計(jì)語言言(Programming Language)，程序設(shè)計(jì)語言分為，程序設(shè)計(jì)語言分為機(jī)機(jī)器語言、匯編語言和高級語言器語言、匯編語言和高級語言三種。三種。對數(shù)據(jù)操作的步驟對數(shù)據(jù)

6、操作的步驟如何表示、組織和存儲數(shù)據(jù)如何表示、組織和存儲數(shù)據(jù)算法是程序的靈魂，不掌握算法就無法編寫出程序。算法是程序的靈魂，不掌握算法就無法編寫出程序。語言是實(shí)現(xiàn)算法的工具，是外殼，是表現(xiàn)形式。語言是實(shí)現(xiàn)算法的工具，是外殼，是表現(xiàn)形式。要做到二者的高度統(tǒng)一。要做到二者的高度統(tǒng)一。5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.1 機(jī)器語言機(jī)器語言 機(jī)器語言是唯一能被計(jì)算機(jī)直接理解和執(zhí)行的程序設(shè)計(jì)機(jī)器語言是唯一能被計(jì)算機(jī)直接理解和執(zhí)行的程序設(shè)計(jì)語言，屬低級語言。機(jī)器語言的一條語句就是一條指令，機(jī)語言，屬低級語言。機(jī)器語言的一條語句就是一條指令，機(jī)器指令的格式如下：器指令的格式如下： 操作碼操作碼操作數(shù)操作

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

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

9、言的表示方法，并遵循一定的語法規(guī)則來編寫程序。自然語言的表示方法，并遵循一定的語法規(guī)則來編寫程序。 實(shí)現(xiàn)求整數(shù)的絕對值的程序段：實(shí)現(xiàn)求整數(shù)的絕對值的程序段：int intVar, result;scanf(“%d”, &intVar);if(intVar = 0) result = intVar;else result = -1*intVar;printf(“%d的絕對值是：的絕對值是：%d”, intVar, result);5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言高級語言程序的翻譯和執(zhí)行過程如下：高級語言程序的翻譯和執(zhí)行過程如下： 高級語言編寫的程序也屬于符號程序，不能直接在計(jì)算高級語言編寫的程序

10、也屬于符號程序，不能直接在計(jì)算機(jī)上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代機(jī)上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代碼的方法主要有編譯和解釋兩種。碼的方法主要有編譯和解釋兩種。 5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言5.2.4 程序設(shè)計(jì)語言的構(gòu)成程序設(shè)計(jì)語言的構(gòu)成 程序設(shè)計(jì)語言的構(gòu)成主要包括以下幾個(gè)方面：程序設(shè)計(jì)語言的構(gòu)成主要包括以下幾個(gè)方面： (1) 數(shù)據(jù)類型數(shù)據(jù)類型 基本數(shù)據(jù)類型：是由程序設(shè)計(jì)語言內(nèi)置的，其特點(diǎn)是不基本數(shù)據(jù)類型：是由程序設(shè)計(jì)語言內(nèi)置的，其特點(diǎn)是不能再分解為其它的類型。在主流的程序設(shè)計(jì)語言中一般包括：能再分解為其它的類型。在主流的程

11、序設(shè)計(jì)語言中一般包括：整數(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) 運(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)用等。5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言 (3)

12、語句語句 程序是對計(jì)算機(jī)要執(zhí)行的操作的描述，高級語言源程序的程序是對計(jì)算機(jī)要執(zhí)行的操作的描述，高級語言源程序的基本組成單位就是語句?；窘M成單位就是語句。 語句按功能可以分為兩類：語句按功能可以分為兩類： 用于描述操作運(yùn)算的語句，如賦值語句；用于描述操作運(yùn)算的語句，如賦值語句； 用于控制操作運(yùn)算流程的語句，如分支控制語句。用于控制操作運(yùn)算流程的語句，如分支控制語句。 (4) 控制結(jié)構(gòu)控制結(jié)構(gòu) 順序結(jié)構(gòu)，按照語句出現(xiàn)的先后順序依次執(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é)

13、構(gòu)，循環(huán)( (重復(fù)重復(fù)) )是計(jì)算機(jī)解題的一個(gè)重要特征。是計(jì)算機(jī)解題的一個(gè)重要特征。5.2 程序設(shè)計(jì)語言程序設(shè)計(jì)語言 (5) 輸入輸入/輸出輸出 高級程序設(shè)計(jì)語言中通常以函數(shù)或語句的形式提供輸入高級程序設(shè)計(jì)語言中通常以函數(shù)或語句的形式提供輸入輸出操作?，F(xiàn)代高級程序設(shè)計(jì)語言通常都提供通過窗口、文輸出操作?，F(xiàn)代高級程序設(shè)計(jì)語言通常都提供通過窗口、文本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。 (6) 子程序子程序 子程序就是將需要重復(fù)使用的程序段或分解的子問題子程序就是將需要重復(fù)使用的程序段或分解的子問題編寫成一個(gè)獨(dú)立的子程序，當(dāng)程序中需要使用子

14、程序時(shí)，編寫成一個(gè)獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對其進(jìn)行調(diào)用。再對其進(jìn)行調(diào)用。 子程序有兩種：函數(shù)子程序有兩種：函數(shù)(Function)和過程和過程(Procedure)，它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。 5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)5.3.1 什么是數(shù)據(jù)什么是數(shù)據(jù) 數(shù)據(jù)是對客觀事物的描述，對計(jì)算機(jī)來說，數(shù)字、字符、數(shù)據(jù)是對客觀事物的描述，對計(jì)算機(jī)來說，數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。圖形、色彩、聲音等都是數(shù)據(jù)。 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以是數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以是一

15、個(gè)單個(gè)數(shù)據(jù)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可一個(gè)單個(gè)數(shù)據(jù)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。分割的最小單位。 例：公司員工數(shù)據(jù)的存儲例：公司員工數(shù)據(jù)的存儲( (一個(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ù)元素5.3

16、 數(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)運(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é)數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。構(gòu)，它描述數(shù)據(jù)的組織形式。元素之間是一對一關(guān)系元素之間是一對一關(guān)系例如例如:公司員工數(shù)據(jù)表中公司員工數(shù)據(jù)表中每個(gè)成員關(guān)系每個(gè)成員關(guān)系元素之間是多對多關(guān)系元素之間是多對多關(guān)系例如例如:

17、華農(nóng)與周邊地區(qū)的華農(nóng)與周邊地區(qū)的位置關(guān)系位置關(guān)系元素之間是一對多關(guān)系元素之間是一對多關(guān)系例如例如:一對夫婦和他們的一對夫婦和他們的全部子孫全部子孫元素之間是松散關(guān)系元素之間是松散關(guān)系例如例如:自然數(shù)的全體自然數(shù)的全體5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(2) 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式，稱為數(shù)據(jù)的物理結(jié)數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)。它包括：構(gòu)或存儲結(jié)構(gòu)。它包括： 順序存儲方式，把邏輯上相鄰的數(shù)據(jù)元素存儲在物順序存儲方式，把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中。理上相鄰的存儲單元中。 鏈?zhǔn)酱鎯Ψ绞剑總€(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域兩部鏈

18、式存儲方式，每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲與該結(jié)點(diǎn)具有邏輯關(guān)分，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲與該結(jié)點(diǎn)具有邏輯關(guān)系的結(jié)點(diǎn)的地址。系的結(jié)點(diǎn)的地址。 索引存儲方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲區(qū)索引存儲方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲區(qū)域里。再建一個(gè)附加的索引表，索引表中的第域里。再建一個(gè)附加的索引表，索引表中的第i項(xiàng)表示第項(xiàng)表示第i個(gè)個(gè)元素的存儲地址。元素的存儲地址。 散列存儲方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲散列存儲方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲區(qū)域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲地址。區(qū)域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲地址。5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

19、例如例如:線性表是一種邏輯結(jié)構(gòu)線性表是一種邏輯結(jié)構(gòu),若采用順序存儲方式，可稱若采用順序存儲方式，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，可稱其為鏈表；若采用其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，可稱其為鏈表；若采用散列存儲方法，可稱其為散列表。散列存儲方法，可稱其為散列表。 右圖為某學(xué)生各右圖為某學(xué)生各科成績表分別采用順科成績表分別采用順序和鏈?zhǔn)酱鎯Φ那樾?。序和鏈?zhǔn)酱鎯Φ那樾?。前者存儲在一片連續(xù)前者存儲在一片連續(xù)空間，后者則存儲在空間，后者則存儲在非連續(xù)空間。非連續(xù)空間。5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(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)算是定義在數(shù)

20、據(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)算常常涉及算法的問題。在數(shù)據(jù)結(jié)構(gòu)中，運(yùn)算常常涉及算法的問題。 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)，是在計(jì)算機(jī)內(nèi)存中使用一組連數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計(jì)算機(jī)內(nèi)存中使用一組連續(xù)的存儲單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)

21、擁有續(xù)的存儲單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有相同的變量名，稱為數(shù)組名。相同的變量名，稱為數(shù)組名。5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(2) 鏈表鏈表 鏈表鏈表(Linked List)是采用鏈?zhǔn)酱鎯Φ木€性表。線性鏈表是采用鏈?zhǔn)酱鎯Φ木€性表。線性鏈表的結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩個(gè)部分組成，數(shù)據(jù)域存儲數(shù)據(jù)元的結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩個(gè)部分組成，數(shù)據(jù)域存儲數(shù)據(jù)元素，指針域存儲一個(gè)指向直接后繼結(jié)點(diǎn)的指針。素，指針域存儲一個(gè)指向直接后繼結(jié)點(diǎn)的指針。 5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(3) 二叉樹二叉樹 二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個(gè)結(jié)點(diǎn)的集合，

22、該集合或者為空，或者滿足下面兩個(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) 5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 5.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹遍歷二叉樹 遍歷二叉樹是非常重要的一種運(yùn)算。遍歷二叉樹是非常重

23、要的一種運(yùn)算?！氨闅v遍歷”的含義是的含義是對結(jié)構(gòu)中的每個(gè)數(shù)據(jù)都訪問一次且僅訪問一次?？梢杂腥N對結(jié)構(gòu)中的每個(gè)數(shù)據(jù)都訪問一次且僅訪問一次?？梢杂腥N訪問路徑：訪問路徑： 前序遍歷前序遍歷: :訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn); ;前序遍歷左子樹前序遍歷左子樹; ;前序遍歷右子樹前序遍歷右子樹 中序遍歷中序遍歷: :中序遍歷左子樹中序遍歷左子樹; ;訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn); ;中序遍歷右子樹中序遍歷右子樹 后序遍歷后序遍歷: :后序遍歷左子樹后序遍歷左子樹; ;后序遍歷右子樹后序遍歷右子樹; ;訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) 前序遍歷：前序遍歷：A B D E F G CA B D E F G C 中序遍歷：中序遍歷：D

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

25、找算法(了解了解) 查找查找(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的過程，叫做查找。的過程，叫做查找。 (1) 順序查找順序查找 順序查找是線性表的最簡單的查找算法。它是用給定順序查找是線性表的最簡單的查找算法。它是用給定的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)算，若找的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。到相等的關(guān)鍵字則查找成功，否則查找失敗。 順序查找算法的優(yōu)點(diǎn)是適用范圍

26、廣，對線性表中結(jié)點(diǎn)順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對線性表中結(jié)點(diǎn)邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對線性表的物理存儲結(jié)構(gòu)也沒有要求，順序存儲與鏈?zhǔn)酱鎯?。存儲結(jié)構(gòu)也沒有要求，順序存儲與鏈?zhǔn)酱鎯伞?.4 算法算法(2) 折半查找折半查找 折半查找的基本思想是：折半查找的基本思想是： 先取表的中間位置的結(jié)點(diǎn)關(guān)鍵字與所給定的關(guān)鍵字進(jìn)行先取表的中間位置的結(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)在表的前字大，則

27、所找結(jié)點(diǎn)在表的后半部分；否則所找結(jié)點(diǎn)在表的前半部分，然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定半部分，然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字進(jìn)行比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失關(guān)鍵字進(jìn)行比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失敗為止。敗為止。5.4 算法算法例例: 5.4 算法算法5.4.4 排序算法排序算法(了解了解) 排序排序(Sort)是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是將一組數(shù)據(jù)元素將一組數(shù)據(jù)元素(或記錄或記錄)從任意序列排列成一個(gè)按關(guān)鍵字排序從任意序列排列成一個(gè)按關(guān)鍵字排序的序列。的序列。 按照排序過程中涉及的存儲器的

28、不同將排序分為內(nèi)部排按照排序過程中涉及的存儲器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過程都在內(nèi)序和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過程都在內(nèi)存中進(jìn)行的排序。存中進(jìn)行的排序。 5.4 算法算法(1) 直接插入排序直接插入排序 算法的基本思想如下：算法的基本思想如下： 開始時(shí)，把第一個(gè)記錄看成是已經(jīng)排好序的子序列，開始時(shí)，把第一個(gè)記錄看成是已經(jīng)排好序的子序列，這時(shí)子序列中只有一個(gè)記錄；這時(shí)子序列中只有一個(gè)記錄； 從第二個(gè)記錄起到最后一個(gè)記錄，依次將每個(gè)記錄從第二個(gè)記錄起到最后一個(gè)記錄，依次將每個(gè)記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置；與前面子序列的記

29、錄按關(guān)鍵字比較，確定記錄插入的位置； 將記錄插入到子序列中，子序列記錄個(gè)數(shù)加將記錄插入到子序列中，子序列記錄個(gè)數(shù)加1，直，直至子序列長度與待排序列長度相等時(shí)結(jié)束。至子序列長度與待排序列長度相等時(shí)結(jié)束。5.4 算法算法(1) 直接插入排序直接插入排序 5.4 算法算法5.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)行位置的交換，否則保持原來順序；若為逆序則將兩個(gè)記錄進(jìn)行位置的交換，否則保持原來順序； 將第將第

30、n-1個(gè)記錄的關(guān)鍵字與將第個(gè)記錄的關(guān)鍵字與將第n-2個(gè)記錄的關(guān)鍵字進(jìn)行比較；個(gè)記錄的關(guān)鍵字進(jìn)行比較； 重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍；重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍； 上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第最小的記錄被交換到了第1個(gè)記錄的位置，完成一趟排序；個(gè)記錄的位置，完成一趟排序； 第二趟排序從第第二趟排序從第n個(gè)記錄到第個(gè)記錄到第2個(gè)記錄進(jìn)行同樣的操作，結(jié)果個(gè)記錄進(jìn)行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第是使關(guān)鍵字次小的記錄被交換到了第2個(gè)記錄的位置；個(gè)記錄的位置

31、；依次類推，第依次類推，第i趟排序是從第趟排序是從第n個(gè)記錄到第個(gè)記錄到第i個(gè)記錄依次比較交換。個(gè)記錄依次比較交換。5.4 算法算法(2) 冒泡排序冒泡排序5.5 軟件工程簡介軟件工程簡介5.5.1 軟件工程提出軟件工程提出 早期早期, ,在軟件開發(fā)過程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展在軟件開發(fā)過程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展的問題，主要表現(xiàn)在以下幾個(gè)方面：的問題，主要表現(xiàn)在以下幾個(gè)方面： 軟件開發(fā)無計(jì)劃性。軟件開發(fā)無計(jì)劃性。 軟件開發(fā)過程無規(guī)范。軟件開發(fā)過程無規(guī)范。 軟件產(chǎn)品無評測手段。軟件產(chǎn)品無評測手段。 1990年電氣電子工程師協(xié)會年電氣電子工程師協(xié)會(IEEE)給出了軟件工程的一給出了軟件

32、工程的一個(gè)定義：個(gè)定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過程，也就是把工程化運(yùn)用應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過程，也就是把工程化運(yùn)用于軟件工程，并對這樣的方法進(jìn)行研究于軟件工程，并對這樣的方法進(jìn)行研究”。5.5 軟件工程簡介軟件工程簡介5.5.2 軟件生命周期軟件生命周期 制定計(jì)劃：確定要開發(fā)軟件系統(tǒng)的總體目標(biāo)。制定計(jì)劃：確定要開發(fā)軟件系統(tǒng)的總體目標(biāo)。 需求分析：對要開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。需求分析：對要開發(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ì)語言把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受程序編碼：使用程序設(shè)計(jì)語言把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼，也稱為軟件實(shí)現(xiàn)。的程序代碼，也稱為軟件實(shí)現(xiàn)。 軟件測試：測試是保證軟件質(zhì)量的重要手段。軟件測試：測試是保證