程序設(shè)計(jì)與算法分析

1、第六章第六章 程序設(shè)計(jì)與程序設(shè)計(jì)與算法分析算法分析本章要點(diǎn)本章要點(diǎn)初步了解程序設(shè)計(jì)的基礎(chǔ)知識(shí)初步了解程序設(shè)計(jì)的基礎(chǔ)知識(shí)掌握結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)的基本方掌握結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)的基本方法法掌握數(shù)據(jù)結(jié)構(gòu)中的基本數(shù)據(jù)類型及其實(shí)現(xiàn)掌握數(shù)據(jù)結(jié)構(gòu)中的基本數(shù)據(jù)類型及其實(shí)現(xiàn)掌握程序設(shè)計(jì)算法的基本思想及幾種經(jīng)典的算法掌握程序設(shè)計(jì)算法的基本思想及幾種經(jīng)典的算法了解編譯原理的基本知識(shí)了解編譯原理的基本知識(shí)6.1.1 6.1.1 程序的概念程序的概念 程序程序就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合。集合。 程序設(shè)計(jì)程序設(shè)計(jì)是程序員編寫一系列可存儲(chǔ)的指令以是

2、程序員編寫一系列可存儲(chǔ)的指令以指示計(jì)算機(jī)完成某些工作的過程。這些指令用指示計(jì)算機(jī)完成某些工作的過程。這些指令用程序設(shè)計(jì)語言寫成。程序設(shè)計(jì)語言寫成。 程序設(shè)計(jì)語言程序設(shè)計(jì)語言是一組專門設(shè)計(jì)的用來生成一系是一組專門設(shè)計(jì)的用來生成一系列可被計(jì)算機(jī)處理和執(zhí)行的指令的符號(hào)集合。列可被計(jì)算機(jī)處理和執(zhí)行的指令的符號(hào)集合。 程序設(shè)計(jì)人員用程序設(shè)計(jì)語言寫成的指令稱作程序設(shè)計(jì)人員用程序設(shè)計(jì)語言寫成的指令稱作代碼代碼。6.1 6.1 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)6.1.2 6.1.2 計(jì)算機(jī)程序設(shè)計(jì)語言計(jì)算機(jī)程序設(shè)計(jì)語言 分類：分類： 低級(jí)語言、高級(jí)語言。低級(jí)語言、高級(jí)語言。1）低級(jí)語言包括兩種類型：機(jī)器語言和匯）低級(jí)

3、語言包括兩種類型：機(jī)器語言和匯編語言。編語言。機(jī)器語言機(jī)器語言 機(jī)器語言面向機(jī)器，可以由機(jī)器語言面向機(jī)器，可以由CPU直接識(shí)直接識(shí)別和執(zhí)行。別和執(zhí)行。 不同的機(jī)器能夠識(shí)別的機(jī)器語言是不相不同的機(jī)器能夠識(shí)別的機(jī)器語言是不相同的。同的。 機(jī)器語言指令都是用一串機(jī)器語言指令都是用一串0、1構(gòu)成的二構(gòu)成的二進(jìn)制位串來表示的。進(jìn)制位串來表示的。 指令系統(tǒng)是機(jī)器提供的機(jī)器指令的集合。指令系統(tǒng)是機(jī)器提供的機(jī)器指令的集合。 用二進(jìn)制編碼表示的指令，稱為機(jī)器指用二進(jìn)制編碼表示的指令，稱為機(jī)器指令，或稱為機(jī)器碼。令，或稱為機(jī)器碼。 用機(jī)器指令編寫的程序稱為機(jī)器語言程用機(jī)器指令編寫的程序稱為機(jī)器語言程序，或稱為目標(biāo)

4、程序，這是計(jì)算機(jī)能夠序，或稱為目標(biāo)程序，這是計(jì)算機(jī)能夠直接執(zhí)行的程序。直接執(zhí)行的程序。 機(jī)器語言難以閱讀和理解，編寫和修改機(jī)器語言難以閱讀和理解，編寫和修改都比較困難，而且通用性較差。都比較困難，而且通用性較差。匯編語言匯編語言 匯編語言也稱符號(hào)語言。匯編語言也稱符號(hào)語言。 指令助記符是指令英文名稱的縮寫，容指令助記符是指令英文名稱的縮寫，容易記憶。易記憶。 所謂匯編語言，就是采用字母、數(shù)字和所謂匯編語言，就是采用字母、數(shù)字和符號(hào)來代替由一個(gè)個(gè)符號(hào)來代替由一個(gè)個(gè)0和和1構(gòu)成的指令操構(gòu)成的指令操作碼、寄存器、數(shù)據(jù)和存儲(chǔ)地址等，并作碼、寄存器、數(shù)據(jù)和存儲(chǔ)地址等，并在程序中用它們代替二進(jìn)制編碼數(shù)，這

5、在程序中用它們代替二進(jìn)制編碼數(shù)，這樣編寫出來的程序就稱為符號(hào)語言程序樣編寫出來的程序就稱為符號(hào)語言程序或匯編語言程序。或匯編語言程序。 大多數(shù)情況下，一條匯編指令直接對(duì)應(yīng)大多數(shù)情況下，一條匯編指令直接對(duì)應(yīng)一條機(jī)器指令，少數(shù)對(duì)應(yīng)幾條機(jī)器指令。一條機(jī)器指令，少數(shù)對(duì)應(yīng)幾條機(jī)器指令。 匯編語言具有一個(gè)本質(zhì)上與機(jī)器語言一匯編語言具有一個(gè)本質(zhì)上與機(jī)器語言一一對(duì)應(yīng)的指令系統(tǒng)。匯編語言的實(shí)質(zhì)和一對(duì)應(yīng)的指令系統(tǒng)。匯編語言的實(shí)質(zhì)和機(jī)器語言是相同的。機(jī)器語言是相同的。低級(jí)語言的特點(diǎn)低級(jí)語言的特點(diǎn) 都與特定的計(jì)算機(jī)硬件系統(tǒng)緊密相關(guān)，來自都與特定的計(jì)算機(jī)硬件系統(tǒng)緊密相關(guān)，來自于特定系統(tǒng)的指令系統(tǒng)，可移植性差；于特定系統(tǒng)

6、的指令系統(tǒng)，可移植性差； 專業(yè)知識(shí)要求高，要求對(duì)計(jì)算機(jī)硬件的結(jié)構(gòu)專業(yè)知識(shí)要求高，要求對(duì)計(jì)算機(jī)硬件的結(jié)構(gòu)和工作原理非常熟悉；和工作原理非常熟悉； 每條指令的功能很單一，程序員編制源程序每條指令的功能很單一，程序員編制源程序時(shí)指令比較繁瑣；時(shí)指令比較繁瑣； 由于直接針對(duì)特定硬件編程，所以，最終的由于直接針對(duì)特定硬件編程，所以，最終的可執(zhí)行程序代碼精煉，而且執(zhí)行效率非常高。可執(zhí)行程序代碼精煉，而且執(zhí)行效率非常高。 兩者主要的區(qū)別在于：機(jī)器語言無需翻兩者主要的區(qū)別在于：機(jī)器語言無需翻譯或編譯，譯或編譯，CPU能夠直接識(shí)別和執(zhí)行。能夠直接識(shí)別和執(zhí)行。而匯編語言必須經(jīng)過匯編才能得到目標(biāo)而匯編語言必須經(jīng)過匯

7、編才能得到目標(biāo)程序。程序。匯編匯編 雖然匯編語言比機(jī)器語言容易閱讀理解和便于雖然匯編語言比機(jī)器語言容易閱讀理解和便于檢查，所以仍然需要一種特殊的程序，該程序檢查，所以仍然需要一種特殊的程序，該程序能夠?qū)⒂脜R編語言編寫的程序能夠?qū)⒂脜R編語言編寫的程序“翻譯翻譯”成成CPU能夠識(shí)別的機(jī)器語言。能夠識(shí)別的機(jī)器語言。 實(shí)現(xiàn)這種翻譯功能的特殊程序稱為實(shí)現(xiàn)這種翻譯功能的特殊程序稱為匯編語言翻匯編語言翻譯程序、匯編程序或匯編器譯程序、匯編程序或匯編器。程序員手工編寫。程序員手工編寫的程序統(tǒng)稱為源程序，用匯編語言編寫的源程的程序統(tǒng)稱為源程序，用匯編語言編寫的源程序稱為匯編語言源程序，匯編程序?qū)⒃闯绦蚍蚍Q為匯

8、編語言源程序，匯編程序?qū)⒃闯绦蚍g得到的機(jī)器語言程序稱為目標(biāo)程序，翻譯的譯得到的機(jī)器語言程序稱為目標(biāo)程序，翻譯的過程稱為過程稱為匯編匯編。反匯編程序反匯編程序用于將目標(biāo)代碼程序轉(zhuǎn)換成相用于將目標(biāo)代碼程序轉(zhuǎn)換成相應(yīng)的匯編語言源程序，這一過程稱為反應(yīng)的匯編語言源程序，這一過程稱為反匯編。反匯編主要用于識(shí)別源程序代碼，匯編。反匯編主要用于識(shí)別源程序代碼，常用的調(diào)試工具程序常用的調(diào)試工具程序DEBUG就提供了反就提供了反匯編功能。匯編功能。高級(jí)語言的產(chǎn)生高級(jí)語言的產(chǎn)生 一個(gè)問題：如何解決程序的可移植性，即：程一個(gè)問題：如何解決程序的可移植性，即：程序員編寫的源程序如何可以從一臺(tái)計(jì)算機(jī)很容序員編寫的源程

9、序如何可以從一臺(tái)計(jì)算機(jī)很容易地轉(zhuǎn)到另一臺(tái)計(jì)算機(jī)上工作。為了解決這些易地轉(zhuǎn)到另一臺(tái)計(jì)算機(jī)上工作。為了解決這些問題，人們引入了高級(jí)語言來編寫程序。問題，人們引入了高級(jí)語言來編寫程序。 所謂高級(jí)語言是一種由表達(dá)各種意義的所謂高級(jí)語言是一種由表達(dá)各種意義的“詞詞”和和“公式公式”，按照一定的，按照一定的“語法規(guī)則語法規(guī)則”來編寫來編寫程序的語言，又稱為程序設(shè)計(jì)語言或算法語言。程序的語言，又稱為程序設(shè)計(jì)語言或算法語言。 高級(jí)語言之所以高級(jí)語言之所以“高級(jí)高級(jí)”，就是因?yàn)樗钩绦颍褪且驗(yàn)樗钩绦騿T可以完全不用與計(jì)算機(jī)的硬件打交道，可以員可以完全不用與計(jì)算機(jī)的硬件打交道，可以不必了解機(jī)器的指令系統(tǒng)。不必了

10、解機(jī)器的指令系統(tǒng)。 程序員可以把硬件上復(fù)雜的概念比如存儲(chǔ)空間程序員可以把硬件上復(fù)雜的概念比如存儲(chǔ)空間抽象成一個(gè)所謂的變量之類的概念，因而程序抽象成一個(gè)所謂的變量之類的概念，因而程序員就可以繞開硬件問題而集中精力解決問題本員就可以繞開硬件問題而集中精力解決問題本身，編程效率大大提高。身，編程效率大大提高。 由于高級(jí)語言與具體機(jī)器無關(guān)，那么在一種機(jī)由于高級(jí)語言與具體機(jī)器無關(guān)，那么在一種機(jī)器上運(yùn)行的高級(jí)語言程序可以幾乎不經(jīng)改動(dòng)地器上運(yùn)行的高級(jí)語言程序可以幾乎不經(jīng)改動(dòng)地移植到另一種機(jī)器上運(yùn)行，大大提高了程序的移植到另一種機(jī)器上運(yùn)行，大大提高了程序的通用性。通用性。 此外，由于高級(jí)語言與自然語言此外，由

11、于高級(jí)語言與自然語言(尤其是英語尤其是英語)很相似，因此易學(xué)、易懂，也易編寫。很相似，因此易學(xué)、易懂，也易編寫。高級(jí)語言的常見類型高級(jí)語言的常見類型 目前已經(jīng)有許多高級(jí)語言在流行，并且目前已經(jīng)有許多高級(jí)語言在流行，并且新的類型還在不斷出現(xiàn)和升級(jí)。新的類型還在不斷出現(xiàn)和升級(jí)。 用戶在實(shí)際應(yīng)用中進(jìn)行程序設(shè)計(jì)時(shí)，可用戶在實(shí)際應(yīng)用中進(jìn)行程序設(shè)計(jì)時(shí)，可根據(jù)情況選擇適合的高級(jí)語言。根據(jù)情況選擇適合的高級(jí)語言。 (1) BASIC語言語言 (2) FORTRAN語言語言 (3) COBOL語言語言 (4) PASCAL語言語言 (5) C語言語言 (6) C+語言語言 (7) 其他高級(jí)語言其他高級(jí)語言 基于

12、視窗類操作系統(tǒng)的，如基于視窗類操作系統(tǒng)的，如Visual Basic、Visual C+、Delphi、Power Builder、Java等等等。等。 高級(jí)語言的優(yōu)點(diǎn)是語句的功能強(qiáng)，源程序比較高級(jí)語言的優(yōu)點(diǎn)是語句的功能強(qiáng)，源程序比較短，容易學(xué)習(xí)，使用方便，通用性較強(qiáng)，便于短，容易學(xué)習(xí)，使用方便，通用性較強(qiáng)，便于推廣和交流。推廣和交流。 其缺點(diǎn)是編譯程序比匯編程序復(fù)雜，而且編譯其缺點(diǎn)是編譯程序比匯編程序復(fù)雜，而且編譯出來的目標(biāo)程序往往效率不高，目標(biāo)程序的長出來的目標(biāo)程序往往效率不高，目標(biāo)程序的長度比有經(jīng)驗(yàn)的程序員所編的同樣功能的匯編語度比有經(jīng)驗(yàn)的程序員所編的同樣功能的匯編語言程序要長言程序要長

13、半以上，運(yùn)行時(shí)間也要長一些。半以上，運(yùn)行時(shí)間也要長一些。 因此，在很多對(duì)時(shí)間要求比較高的系統(tǒng)，如某因此，在很多對(duì)時(shí)間要求比較高的系統(tǒng)，如某些實(shí)時(shí)控制系統(tǒng)或者大型計(jì)算機(jī)控制系統(tǒng)中，些實(shí)時(shí)控制系統(tǒng)或者大型計(jì)算機(jī)控制系統(tǒng)中，低級(jí)語言，主要是匯編語言，仍然得到了一定低級(jí)語言，主要是匯編語言，仍然得到了一定的應(yīng)用。的應(yīng)用。6.1.3 6.1.3 高級(jí)語言的基本內(nèi)容高級(jí)語言的基本內(nèi)容 高級(jí)程序設(shè)計(jì)語言依賴于各自特定的語句和語高級(jí)程序設(shè)計(jì)語言依賴于各自特定的語句和語法。一條一條的語句是構(gòu)成源程序的基本單位。法。一條一條的語句是構(gòu)成源程序的基本單位。高級(jí)語言的一條語句被編譯或解釋時(shí)往往會(huì)對(duì)高級(jí)語言的一條語句被

14、編譯或解釋時(shí)往往會(huì)對(duì)應(yīng)多條機(jī)器指令。應(yīng)多條機(jī)器指令。 每一種編程語言都包含一組語句和語法。所謂每一種編程語言都包含一組語句和語法。所謂語法，是指管理語言結(jié)構(gòu)和語句的一組規(guī)則。語法，是指管理語言結(jié)構(gòu)和語句的一組規(guī)則。不論使用何種設(shè)計(jì)語言，都必須遵循其語法規(guī)不論使用何種設(shè)計(jì)語言，都必須遵循其語法規(guī)則。則。 以下內(nèi)容主要描述了大多數(shù)高級(jí)語言都共同具以下內(nèi)容主要描述了大多數(shù)高級(jí)語言都共同具備的特性，但不一定是所有高級(jí)語言都有的。備的特性，但不一定是所有高級(jí)語言都有的。1 1高級(jí)語言的基本符號(hào)高級(jí)語言的基本符號(hào) 高級(jí)語言都是由所謂的基本符號(hào)組成的。基本高級(jí)語言都是由所謂的基本符號(hào)組成的。基本符號(hào)可以分為

15、單字符和多字符兩種情況。單字符號(hào)可以分為單字符和多字符兩種情況。單字符基本符號(hào)由單個(gè)字符組成，在高級(jí)語言中通符基本符號(hào)由單個(gè)字符組成，在高級(jí)語言中通常都有下列幾種單字符基本符號(hào)：常都有下列幾種單字符基本符號(hào)： (1) 字母字母 大寫英文字母大寫英文字母AZ，小寫英文字母，小寫英文字母az，共，共52個(gè)符號(hào)。個(gè)符號(hào)。 (2) 數(shù)字?jǐn)?shù)字 09，共，共10個(gè)數(shù)字符號(hào)。個(gè)數(shù)字符號(hào)。 (3)特殊字符特殊字符 (加加)，(減減)，*(乘乘)，/(除除)，(乘方乘方)，(等號(hào)等號(hào))，(左括號(hào)左括號(hào))，)(右括號(hào)右括號(hào))，(大大于于)，(小于小于)，(逗號(hào)逗號(hào))，(空格空格)等。等。 在高級(jí)語言中的多字符基本

16、符號(hào)由兩個(gè)在高級(jí)語言中的多字符基本符號(hào)由兩個(gè)或兩個(gè)以上的字符組成，例如或兩個(gè)以上的字符組成，例如GoTo(轉(zhuǎn)轉(zhuǎn)移移)、(小于或等于小于或等于)、AND(與與)等等。等等。2 2高級(jí)語言的基本元素高級(jí)語言的基本元素 基本元素由基本符號(hào)組成，可分為數(shù)、基本元素由基本符號(hào)組成，可分為數(shù)、邏輯值、名字、標(biāo)號(hào)和字符串等五大類。邏輯值、名字、標(biāo)號(hào)和字符串等五大類。 (1) 數(shù)數(shù) 它由它由09共共10個(gè)基本數(shù)字和其他一些符個(gè)基本數(shù)字和其他一些符號(hào)號(hào)(如小數(shù)點(diǎn)如小數(shù)點(diǎn)“.”、正負(fù)號(hào)、正負(fù)號(hào)“、”及及指數(shù)符號(hào)指數(shù)符號(hào)“E”等所構(gòu)成。等所構(gòu)成。 (2) 邏輯值邏輯值 由真由真(True)和假和假(False)兩個(gè)

17、值表示。兩個(gè)值表示。 (3) 名字名字 由字符組成，一般約定名字的開頭是字母或者由字符組成，一般約定名字的開頭是字母或者下劃線，其后可為字母或數(shù)字，如下劃線，其后可為字母或數(shù)字，如XYZ、A123、_C等。名字可用來定義常量、變量、等。名字可用來定義常量、變量、函數(shù)、過程或子程序的，也被用來定義成某些函數(shù)、過程或子程序的，也被用來定義成某些東西，故也稱為標(biāo)識(shí)符。在高級(jí)語言中，一般東西，故也稱為標(biāo)識(shí)符。在高級(jí)語言中，一般還規(guī)定了組成名字的字符的長度，即字符個(gè)數(shù)。還規(guī)定了組成名字的字符的長度，即字符個(gè)數(shù)。 (4) 標(biāo)號(hào)標(biāo)號(hào) 是在高級(jí)語言中的程序語句前所加的一個(gè)名字，是在高級(jí)語言中的程序語句前所加的

18、一個(gè)名字，主要用來指示程序可能的轉(zhuǎn)移方向。主要用來指示程序可能的轉(zhuǎn)移方向。 (5) 字符串字符串 由一串字符所組成。在不同的高級(jí)語言由一串字符所組成。在不同的高級(jí)語言中，字符串中的多個(gè)字符放在一對(duì)單引中，字符串中的多個(gè)字符放在一對(duì)單引號(hào)或雙引號(hào)中。號(hào)或雙引號(hào)中。3 3基本的數(shù)據(jù)類型基本的數(shù)據(jù)類型 任何一種高級(jí)語言都會(huì)定義一些基本的任何一種高級(jí)語言都會(huì)定義一些基本的數(shù)據(jù)類型。基本的數(shù)據(jù)類型通常包括整數(shù)據(jù)類型。基本的數(shù)據(jù)類型通常包括整數(shù)數(shù)據(jù)類型、實(shí)數(shù)數(shù)據(jù)類型和字符數(shù)據(jù)數(shù)數(shù)據(jù)類型、實(shí)數(shù)數(shù)據(jù)類型和字符數(shù)據(jù)類型等。類型等。 在程序中，除了值無需改變的常數(shù)外，在程序中，除了值無需改變的常數(shù)外，大部分?jǐn)?shù)據(jù)的

19、值是可以修改的。在程序大部分?jǐn)?shù)據(jù)的值是可以修改的。在程序中，中，變量變量是指代表某個(gè)具體數(shù)值，并且是指代表某個(gè)具體數(shù)值，并且所代表的數(shù)值可改變的一個(gè)符號(hào)名字。所代表的數(shù)值可改變的一個(gè)符號(hào)名字。 變量必須先定義，然后才能使用，這是變量必須先定義，然后才能使用，這是條基條基本原則。本原則。 變量實(shí)質(zhì)上代表了一個(gè)特定大小的內(nèi)存單元空變量實(shí)質(zhì)上代表了一個(gè)特定大小的內(nèi)存單元空間。間。 定義變量的實(shí)質(zhì)就是讓程序?yàn)樵撟兞糠峙湟粋€(gè)定義變量的實(shí)質(zhì)就是讓程序?yàn)樵撟兞糠峙湟粋€(gè)特定的內(nèi)存空間。特定的內(nèi)存空間。 變量的類型實(shí)質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間變量的類型實(shí)質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間的大小，即分配給該變量代表的

20、數(shù)據(jù)的所占據(jù)的大小，即分配給該變量代表的數(shù)據(jù)的所占據(jù)的內(nèi)存單元的字節(jié)數(shù)目。的內(nèi)存單元的字節(jié)數(shù)目。4 4結(jié)構(gòu)數(shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型 是在基本數(shù)據(jù)類型的基礎(chǔ)上構(gòu)造出來的數(shù)據(jù)類是在基本數(shù)據(jù)類型的基礎(chǔ)上構(gòu)造出來的數(shù)據(jù)類型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級(jí)語言都支持的型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級(jí)語言都支持的兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。 (1) 數(shù)組類型數(shù)組類型 數(shù)組是若干個(gè)相同類型的數(shù)據(jù)的集合。數(shù)組是若干個(gè)相同類型的數(shù)據(jù)的集合。 (2) 用戶自定義的結(jié)構(gòu)體類型用戶自定義的結(jié)構(gòu)體類型 結(jié)構(gòu)體是隸屬于同一個(gè)事物的多個(gè)不同類型的結(jié)構(gòu)體是隸屬于同一個(gè)事物的多個(gè)不同類型的數(shù)據(jù)的集合，用來表示具有若干

21、個(gè)屬性的一個(gè)數(shù)據(jù)的集合，用來表示具有若干個(gè)屬性的一個(gè)事物。事物。 除了以上兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型外，許多除了以上兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型外，許多高級(jí)語言還有比如枚舉、集合，以及更復(fù)雜的高級(jí)語言還有比如枚舉、集合，以及更復(fù)雜的隊(duì)列、堆棧等多種數(shù)據(jù)類型。隊(duì)列、堆棧等多種數(shù)據(jù)類型。 結(jié)構(gòu)數(shù)據(jù)類型在使用時(shí)也必須定義相應(yīng)類型的結(jié)構(gòu)數(shù)據(jù)類型在使用時(shí)也必須定義相應(yīng)類型的“變量變量”名字。名字。5 5運(yùn)算符與表達(dá)式運(yùn)算符與表達(dá)式 表達(dá)式是由基本符號(hào)、基本元素和各種數(shù)據(jù)通表達(dá)式是由基本符號(hào)、基本元素和各種數(shù)據(jù)通過各種運(yùn)算符連接而成的。按表達(dá)式的運(yùn)算結(jié)過各種運(yùn)算符連接而成的。按表達(dá)式的運(yùn)算結(jié)果可以分為果可以分為

22、算術(shù)表達(dá)式、邏輯表達(dá)式和字符串算術(shù)表達(dá)式、邏輯表達(dá)式和字符串表達(dá)式表達(dá)式等幾種情況。等幾種情況。 高級(jí)語言中的運(yùn)算符大致包括以下幾個(gè)方面：高級(jí)語言中的運(yùn)算符大致包括以下幾個(gè)方面： (1) 邏輯運(yùn)算：邏輯運(yùn)算：與、或、非、異或。與、或、非、異或。 (2) 算術(shù)運(yùn)算：算術(shù)運(yùn)算：加、減、乘、除、取模。加、減、乘、除、取模。 (3) 數(shù)據(jù)比較：數(shù)據(jù)比較：大于、小于、等于、不等于。大于、小于、等于、不等于。 (4) 數(shù)據(jù)傳送；數(shù)據(jù)傳送；輸入、輸出、賦值。輸入、輸出、賦值。 (5) 算術(shù)表達(dá)式：算術(shù)表達(dá)式：該表達(dá)式的運(yùn)算結(jié)果是數(shù)，該表達(dá)式的運(yùn)算結(jié)果是數(shù)，它非常近似于日常的數(shù)學(xué)公式。它非常近似于日常的數(shù)學(xué)公

23、式。 (6) 關(guān)系運(yùn)算表達(dá)式：關(guān)系運(yùn)算表達(dá)式：該表達(dá)式的運(yùn)算結(jié)果是該表達(dá)式的運(yùn)算結(jié)果是邏輯值，常用的運(yùn)算符包含邏輯值，常用的運(yùn)算符包含(大于大于)、(小小于于)、(等于等于)、(小于等于小于等于)、(大于等大于等于于)、不等于。、不等于。 (7) 字符串表達(dá)式：字符串表達(dá)式：該表達(dá)式的運(yùn)算結(jié)果是字該表達(dá)式的運(yùn)算結(jié)果是字符串。符串。6 6語句語句 語句是構(gòu)成高級(jí)語言源程序的基本單位，語句是構(gòu)成高級(jí)語言源程序的基本單位，是由基本元素、運(yùn)算符、表達(dá)式等組成。是由基本元素、運(yùn)算符、表達(dá)式等組成。任何一種高級(jí)語言往往都支持賦值、條任何一種高級(jí)語言往往都支持賦值、條件判斷、循環(huán)、輸入輸出等語句。程序件判斷

24、、循環(huán)、輸入輸出等語句。程序員利用這些語句的結(jié)合，能夠很方便地員利用這些語句的結(jié)合，能夠很方便地編制出功能強(qiáng)大的程序。編制出功能強(qiáng)大的程序。7 7庫函數(shù)和用戶自定義的函數(shù)庫函數(shù)和用戶自定義的函數(shù) 為了支持用戶編寫出功能強(qiáng)大的源程序，為了支持用戶編寫出功能強(qiáng)大的源程序，幾乎所有的高級(jí)語言都為用戶提供了豐幾乎所有的高級(jí)語言都為用戶提供了豐富的庫函數(shù)，這些庫函數(shù)能夠?qū)崿F(xiàn)某些富的庫函數(shù)，這些庫函數(shù)能夠?qū)崿F(xiàn)某些特定的功能，比如計(jì)算一個(gè)比較復(fù)雜的特定的功能，比如計(jì)算一個(gè)比較復(fù)雜的數(shù)學(xué)函數(shù)。數(shù)學(xué)函數(shù)。 在源程序中，用戶也可以自己定義自己在源程序中，用戶也可以自己定義自己的函數(shù)的函數(shù) (子程序或過程子程序或過

25、程)，以便以后可以，以便以后可以反復(fù)調(diào)用這些代碼集合。反復(fù)調(diào)用這些代碼集合。8 8注釋注釋 任何一種程序設(shè)計(jì)語言都強(qiáng)調(diào)注釋的重要性。任何一種程序設(shè)計(jì)語言都強(qiáng)調(diào)注釋的重要性。源程序所包含的代碼往往比較冗長，添加必要源程序所包含的代碼往往比較冗長，添加必要的注釋不僅有助于閱讀程序，更重要的是，在的注釋不僅有助于閱讀程序，更重要的是，在需要對(duì)程序功能進(jìn)行擴(kuò)充時(shí)，注釋可以極大地需要對(duì)程序功能進(jìn)行擴(kuò)充時(shí)，注釋可以極大地幫助程序員對(duì)原始程序的理解。幫助程序員對(duì)原始程序的理解。 經(jīng)常會(huì)出現(xiàn)這樣一種情況，程序員自己編寫的經(jīng)常會(huì)出現(xiàn)這樣一種情況，程序員自己編寫的程序，經(jīng)過一段時(shí)間后，可能就是半年或者幾程序，經(jīng)過

26、一段時(shí)間后，可能就是半年或者幾個(gè)月以后，程序員自己也讀不懂自己的程序了。個(gè)月以后，程序員自己也讀不懂自己的程序了。況且，程序不僅要自己看得懂，更重要的是也況且，程序不僅要自己看得懂，更重要的是也要讓別人能夠看懂。要讓別人能夠看懂。9 9程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格(1) 編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。(2) 程序中應(yīng)給出必要的注釋，尤其在變量定義、調(diào)用接口、參程序中應(yīng)給出必要的注釋，尤其在變量定義、調(diào)用接口、參數(shù)傳遞處，在修改程序時(shí)應(yīng)注明修改人、時(shí)間、簡(jiǎn)要的修改原因。數(shù)傳遞處，在修改程序時(shí)應(yīng)注明修改人、時(shí)間、簡(jiǎn)要的修改原因。(3) 對(duì)變量、函數(shù)

27、標(biāo)識(shí)等的命名，采用規(guī)范的命名方法，避免含對(duì)變量、函數(shù)標(biāo)識(shí)等的命名，采用規(guī)范的命名方法，避免含義不明確的縮寫，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含義不明確的縮寫，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含義和數(shù)據(jù)類型。義和數(shù)據(jù)類型。(4) 采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。(5) 每一行只寫一條語句，使用括號(hào)間隔表達(dá)式或語句的組成部每一行只寫一條語句，使用括號(hào)間隔表達(dá)式或語句的組成部分，使組成部分清晰；分，使組成部分清晰；(6) 使用結(jié)構(gòu)化、面向?qū)ο蟮木幊碳夹g(shù)，提高程序可重用性、可使用結(jié)構(gòu)化、面向?qū)ο蟮木幊碳夹g(shù)，提高程序可重用性、可擴(kuò)充性。擴(kuò)充性。(7

28、) 除非完全必要，應(yīng)盡量避免多任務(wù)和多重處理。除非完全必要，應(yīng)盡量避免多任務(wù)和多重處理。(8) 盡量避免使用復(fù)雜的算術(shù)和邏輯表達(dá)式。盡量避免使用復(fù)雜的算術(shù)和邏輯表達(dá)式。(9) 提高程序健壯性，預(yù)防用戶的操作錯(cuò)誤，做到廢進(jìn)廢出。提高程序健壯性，預(yù)防用戶的操作錯(cuò)誤，做到廢進(jìn)廢出。 1010高級(jí)語言程序的運(yùn)行高級(jí)語言程序的運(yùn)行 使用高級(jí)語言編制程序的一般過程可以歸納為使用高級(jí)語言編制程序的一般過程可以歸納為以下幾個(gè)步驟：以下幾個(gè)步驟： (1) 使用文本編輯工具，逐條編寫源程序的語使用文本編輯工具，逐條編寫源程序的語句。存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的句。存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的高級(jí)語

29、言有關(guān)。高級(jí)語言有關(guān)。 (2) 編譯源程序文件，生成目標(biāo)文件，文件后編譯源程序文件，生成目標(biāo)文件，文件后綴名通常為綴名通常為obj。 (3) 鏈接目標(biāo)文件，生成可執(zhí)行文件，文件后鏈接目標(biāo)文件，生成可執(zhí)行文件，文件后綴名通常為綴名通常為exe。 (4) 在計(jì)算機(jī)上執(zhí)行可執(zhí)行程序文件，進(jìn)在計(jì)算機(jī)上執(zhí)行可執(zhí)行程序文件，進(jìn)步步調(diào)試和維護(hù)。調(diào)試和維護(hù)。6.2.1 6.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 采用自頂向下、逐步求精的設(shè)計(jì)方法和單入口單出口的控制結(jié)構(gòu)。1. 1. 結(jié)構(gòu)化程序設(shè)計(jì)思想結(jié)構(gòu)化程序設(shè)計(jì)思想 . . . . . . 二級(jí)子問題 二級(jí)子問題 二級(jí)子問題 需要解決的復(fù)雜問題 三級(jí)子

30、問題 三級(jí)子問題 三級(jí)子問題 . . . . . . . . . 最小問題 最小問題 最小問題 結(jié)構(gòu)化程序設(shè)計(jì)的結(jié)構(gòu)化程序設(shè)計(jì)的原則原則是：是： (1) 使用順序、選擇、循環(huán)使用順序、選擇、循環(huán)3種基本控制種基本控制結(jié)構(gòu)表示程序邏輯。結(jié)構(gòu)表示程序邏輯。 (2)程序語句組織成容易識(shí)別的語句模塊，程序語句組織成容易識(shí)別的語句模塊，每個(gè)模塊都是單入口、單出口。每個(gè)模塊都是單入口、單出口。 (3)嚴(yán)格控制嚴(yán)格控制GOTO語句的使用。語句的使用。(a) 順序結(jié)構(gòu) (b) 選擇結(jié)構(gòu) (c) while循環(huán) (d) do-while循環(huán) A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假

31、 真 入口 A S 2 2模塊模塊 一個(gè)復(fù)雜的問題可以劃分為多個(gè)簡(jiǎn)單問題的組一個(gè)復(fù)雜的問題可以劃分為多個(gè)簡(jiǎn)單問題的組合。合。 在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題分解成一個(gè)個(gè)簡(jiǎn)單問題的最基本方法就是模塊分解成一個(gè)個(gè)簡(jiǎn)單問題的最基本方法就是模塊化?；?。 模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實(shí)現(xiàn)。的概念。模塊常用子程序加以實(shí)現(xiàn)。1 1面向?qū)ο蟮乃枷朊嫦驅(qū)ο蟮乃枷?.2.2 6.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 OO(Object Oriented，面向?qū)ο?，面向?qū)ο?/p>

32、)的程序的程序設(shè)計(jì)把客觀事物看作具有屬性和行為的設(shè)計(jì)把客觀事物看作具有屬性和行為的對(duì)象，通過抽象找出同一類對(duì)象的共同對(duì)象，通過抽象找出同一類對(duì)象的共同屬性屬性(靜態(tài)特征靜態(tài)特征)和行為和行為(動(dòng)態(tài)特征動(dòng)態(tài)特征)，形成，形成類。類。2 2對(duì)象和類對(duì)象和類 對(duì)象對(duì)象 是對(duì)現(xiàn)實(shí)問題的高度概括、分類和是對(duì)現(xiàn)實(shí)問題的高度概括、分類和抽象。每個(gè)對(duì)象都只有自己的數(shù)據(jù)和相抽象。每個(gè)對(duì)象都只有自己的數(shù)據(jù)和相應(yīng)的處理函數(shù)，整個(gè)程序是由一系列相應(yīng)的處理函數(shù)，整個(gè)程序是由一系列相互作用的對(duì)象來構(gòu)成，不同對(duì)象之間是互作用的對(duì)象來構(gòu)成，不同對(duì)象之間是通過發(fā)送消息來實(shí)現(xiàn)相互聯(lián)系、相互作通過發(fā)送消息來實(shí)現(xiàn)相互聯(lián)系、相互作用。

33、用。 方法方法 在對(duì)象內(nèi)的操作通常叫做方法。在對(duì)象內(nèi)的操作通常叫做方法。 類 定義了一組大體上相似的對(duì)象。一個(gè)類定義了一組大體上相似的對(duì)象。一個(gè)類所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行為和屬性。為和屬性。 對(duì)象則是類的具體化，是類的實(shí)例。對(duì)象則是類的具體化，是類的實(shí)例。 類通過派生可以有子類，同樣也可以有父類，類通過派生可以有子類，同樣也可以有父類，形成層次結(jié)構(gòu)。形成層次結(jié)構(gòu)。3 3抽象抽象 抽象 是對(duì)具體事物是對(duì)具體事物(即對(duì)象即對(duì)象)進(jìn)行概括，進(jìn)行概括，即忽略事物的非本質(zhì)特征，只注意那些即忽略事物的非本質(zhì)特征，只注意那些與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而抽

34、象與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而抽象出一類對(duì)象的共性并加以描述。出一類對(duì)象的共性并加以描述。 對(duì)一個(gè)問題的抽象一般來講應(yīng)該包對(duì)一個(gè)問題的抽象一般來講應(yīng)該包括兩個(gè)方面：數(shù)據(jù)抽象和代碼抽象括兩個(gè)方面：數(shù)據(jù)抽象和代碼抽象(或稱或稱為行為抽象為行為抽象)。4 4封裝性封裝性 封裝的兩個(gè)含義封裝的兩個(gè)含義： 第一是，將抽象得到的數(shù)據(jù)成員和代碼成第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結(jié)合，形成一個(gè)不可分割的整體，即對(duì)象，員相結(jié)合，形成一個(gè)不可分割的整體，即對(duì)象，這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。 第二個(gè)含義稱為信息隱蔽，即盡可能隱蔽第二個(gè)含義稱為信息隱蔽，即盡可能隱

35、蔽對(duì)象的內(nèi)部細(xì)節(jié)。在隱蔽對(duì)象內(nèi)部細(xì)節(jié)的同時(shí)，對(duì)象的內(nèi)部細(xì)節(jié)。在隱蔽對(duì)象內(nèi)部細(xì)節(jié)的同時(shí)，對(duì)象需要提供與外部世界進(jìn)行交流的接口，并對(duì)象需要提供與外部世界進(jìn)行交流的接口，并實(shí)現(xiàn)對(duì)數(shù)據(jù)訪問權(quán)限的合理控制，把整個(gè)程序?qū)崿F(xiàn)對(duì)數(shù)據(jù)訪問權(quán)限的合理控制，把整個(gè)程序中不同部分的相互影響減少到最低限度。中不同部分的相互影響減少到最低限度。5 5繼承性繼承性 繼承性繼承性 是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制。是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制。在定義一個(gè)類的時(shí)候，可以以一個(gè)已經(jīng)存在的在定義一個(gè)類的時(shí)候，可以以一個(gè)已經(jīng)存在的類為基礎(chǔ)，并把這個(gè)已經(jīng)存在的類所包含的屬類為基礎(chǔ)，并把這個(gè)已經(jīng)存在的類所包含的屬性和方法作為

36、自身的一部分，然后加入新的屬性和方法作為自身的一部分，然后加入新的屬性和方法以區(qū)別于原來的類。性和方法以區(qū)別于原來的類。 原有的類稱為原有的類稱為基類或父類基類或父類，產(chǎn)生的新類，產(chǎn)生的新類稱為稱為派生類派生類。6 6多態(tài)性多態(tài)性 多態(tài)性多態(tài)性 在收到外部消息時(shí)，對(duì)象通常要予在收到外部消息時(shí)，對(duì)象通常要予以響應(yīng)。不同的對(duì)象收到同一消息可能以響應(yīng)。不同的對(duì)象收到同一消息可能產(chǎn)生完全不同的結(jié)果。產(chǎn)生完全不同的結(jié)果。1 1數(shù)據(jù)、數(shù)據(jù)類型數(shù)據(jù)、數(shù)據(jù)類型 數(shù)據(jù)數(shù)據(jù) 是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)系統(tǒng)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)系統(tǒng)內(nèi)，數(shù)據(jù)通常是指能夠輸入到計(jì)算機(jī)中并被計(jì)內(nèi)，數(shù)據(jù)通常是指能夠輸入到計(jì)

37、算機(jī)中并被計(jì)算機(jī)進(jìn)行處理的符號(hào)的集合。算機(jī)進(jìn)行處理的符號(hào)的集合。 數(shù)據(jù)類型數(shù)據(jù)類型 是指具有相同取值范圍和可以實(shí)施同種操是指具有相同取值范圍和可以實(shí)施同種操作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計(jì)中，作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計(jì)中，通常會(huì)有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。通常會(huì)有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。6.3.1 6.3.1 基本概念基本概念6.3 6.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2 2數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象 能夠獨(dú)立并完整地描述客觀世界實(shí)體的基本數(shù)能夠獨(dú)立并完整地描述客觀世界實(shí)體的基本數(shù)據(jù)單元稱為據(jù)單元稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素，它是組成數(shù)據(jù)的基本單，它是

38、組成數(shù)據(jù)的基本單位。位。 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是組成數(shù)據(jù)元素的不可分割的最小單位。是組成數(shù)據(jù)元素的不可分割的最小單位。最簡(jiǎn)單的數(shù)據(jù)元素就是由一個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的。最簡(jiǎn)單的數(shù)據(jù)元素就是由一個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的。 同類數(shù)據(jù)元素的集合稱為同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象。3 3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 是指數(shù)據(jù)元素之間的相互關(guān)系的集是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。以及數(shù)據(jù)的運(yùn)算。 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的關(guān)系組

39、成不同的數(shù)據(jù)結(jié)構(gòu)。關(guān)系組成不同的數(shù)據(jù)結(jié)構(gòu)。 線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間存在著前后順序的數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間存在著前后順序的關(guān)系，即除了第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素外，其關(guān)系，即除了第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素外，其他每個(gè)元素都有惟一的一個(gè)前驅(qū)和一個(gè)后繼元素，這他每個(gè)元素都有惟一的一個(gè)前驅(qū)和一個(gè)后繼元素，這樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。 樹形結(jié)構(gòu)樹形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且除了一個(gè)被稱為根節(jié)點(diǎn)的元素外，每個(gè)元素都有一個(gè)除了一個(gè)被稱為根節(jié)點(diǎn)的元素外，每個(gè)元素都

40、有一個(gè)前驅(qū)節(jié)點(diǎn)，并且可以有多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)前驅(qū)節(jié)點(diǎn)，并且可以有多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。稱為樹形結(jié)構(gòu)。 圖形結(jié)構(gòu)圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果任何一個(gè)數(shù)據(jù)元素都可以有多個(gè)數(shù)據(jù)結(jié)構(gòu)中，如果任何一個(gè)數(shù)據(jù)元素都可以有多個(gè)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。構(gòu)。 (2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)算機(jī)存儲(chǔ)器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)不僅要存儲(chǔ)數(shù)據(jù)本身，還要存儲(chǔ)表示數(shù)不僅要存儲(chǔ)數(shù)據(jù)本身，還要存儲(chǔ)表示數(shù)據(jù)間的邏輯關(guān)系。據(jù)間的邏輯關(guān)系。 數(shù)據(jù)的物理

41、結(jié)構(gòu)主要有四種，分別數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。列結(jié)構(gòu)。 順序結(jié)構(gòu)順序結(jié)構(gòu) 把所有元素存放在一片連續(xù)的存儲(chǔ)單元中，把所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語言中順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是的數(shù)組來實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是必須預(yù)先分析出所需定義數(shù)組的大小。必須預(yù)先分析出所需

42、定義數(shù)組的大小。 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 對(duì)邏輯上相鄰的元素不要求其物理對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來實(shí)現(xiàn)，由此得到的存儲(chǔ)表示的指針域來實(shí)現(xiàn)，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針來實(shí)現(xiàn)。語言中的指針來實(shí)現(xiàn)。 索引結(jié)構(gòu)索引結(jié)構(gòu) 針對(duì)每個(gè)數(shù)據(jù)結(jié)構(gòu)建立一張所謂的針對(duì)每個(gè)數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，每個(gè)表項(xiàng)包含一個(gè)能夠惟一識(shí)別一個(gè)元每個(gè)表項(xiàng)包含一個(gè)能夠惟一識(shí)別一個(gè)元素的關(guān)鍵字

43、和用以指示該元素的地址指素的關(guān)鍵字和用以指示該元素的地址指針。針。 散列結(jié)構(gòu)散列結(jié)構(gòu) 通過構(gòu)造相應(yīng)的散列函數(shù)，由散列通過構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。函數(shù)的值來確定元素存放的地址。 (3) 數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算 數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計(jì)算機(jī)程序加以實(shí)數(shù)據(jù)操作通常由計(jì)算機(jī)程序加以實(shí)現(xiàn)，通常也叫現(xiàn)，通常也叫算法實(shí)現(xiàn)算法實(shí)現(xiàn)。6.3.2 6.3.2 線性表線性表 1定義定義 線性表線性表是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，

44、元素之間是一對(duì)一的線性關(guān)系，除了第一個(gè)元素元素之間是一對(duì)一的線性關(guān)系，除了第一個(gè)元素只有直接后繼、最后一個(gè)元素只有直接前驅(qū)外，只有直接后繼、最后一個(gè)元素只有直接前驅(qū)外，其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼，其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖。如圖。 元素 1 uansu 元素 2 1 元素 3 1 元素 n 1 ua 2運(yùn)算和實(shí)現(xiàn)運(yùn)算和實(shí)現(xiàn) 線性表通常采用順序和鏈表兩種物線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：插入、刪除、查詢和遍歷。插入、刪除、查詢

45、和遍歷。 插入插入 在保持原有的存儲(chǔ)結(jié)構(gòu)的前提下，根據(jù)插在保持原有的存儲(chǔ)結(jié)構(gòu)的前提下，根據(jù)插入要求，在適當(dāng)?shù)奈恢貌迦胍粋€(gè)元素。插入操入要求，在適當(dāng)?shù)奈恢貌迦胍粋€(gè)元素。插入操作要求線性表要有足夠的存放新元素的空間，作要求線性表要有足夠的存放新元素的空間，如果空間不足，插入操作無法進(jìn)行，線性表會(huì)如果空間不足，插入操作無法進(jìn)行，線性表會(huì)溢出。溢出。 刪除刪除 在線性表中，找到滿足條件的數(shù)據(jù)元素，在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會(huì)失敗。并刪除。如果線性表為空，刪除就會(huì)失敗。 查詢查詢 在線性表中，按照查詢條件，定位數(shù)據(jù)在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過程就是查

46、詢。查詢的條件一般根據(jù)數(shù)元素的過程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)元素中的關(guān)鍵字進(jìn)行。實(shí)際上，數(shù)據(jù)的插入據(jù)元素中的關(guān)鍵字進(jìn)行。實(shí)際上，數(shù)據(jù)的插入和刪除都需要首先定位數(shù)據(jù)元素。對(duì)于空的線和刪除都需要首先定位數(shù)據(jù)元素。對(duì)于空的線性表是無法查詢的。性表是無法查詢的。 遍歷遍歷 是指按照某種方式，逐一訪問線性表中是指按照某種方式，逐一訪問線性表中的每一個(gè)數(shù)據(jù)元素，并執(zhí)行相同處理的操作。的每一個(gè)數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫、或查詢等。這里的處理可以是讀、寫、或查詢等。6.3.3 6.3.3 棧棧 1定義定義 對(duì)于由對(duì)于由N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序列，個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序

47、列，如果只允許在其固定的一端位置插入和刪除一如果只允許在其固定的一端位置插入和刪除一個(gè)數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱個(gè)數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為為堆棧或棧堆?；驐?stack)。 允許插入或刪除的這一端稱為允許插入或刪除的這一端稱為棧項(xiàng)棧項(xiàng)，另一，另一個(gè)固定端稱為個(gè)固定端稱為棧底棧底。當(dāng)表中沒有元素時(shí)稱為。當(dāng)表中沒有元素時(shí)稱為空空棧棧。2 2運(yùn)算和實(shí)現(xiàn)運(yùn)算和實(shí)現(xiàn) 棧的基本運(yùn)算主要有：入棧、出棧和判斷。棧的基本運(yùn)算主要有：入棧、出棧和判斷。 入棧入棧 入棧也叫壓棧，是在棧頂添加新元素的操入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。作，新的元素入棧

48、后成為新的棧頂元素。 出棧出棧 出棧也叫退?；驈棗?，是將棧頂元素從棧出棧也叫退?；驈棗?，是將棧頂元素從棧中退出并傳遞給用戶程序的操作中退出并傳遞給用戶程序的操作 D C B A 入棧數(shù)據(jù)元素 E E D C B A D C B A 出棧數(shù)據(jù)元素D C B A 判斷判斷 判斷操作用來檢查棧內(nèi)數(shù)據(jù)是否為判斷操作用來檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個(gè)邏輯值：真或假。空，返回結(jié)果是一個(gè)邏輯值：真或假。如果棧頂和棧底重合，說明堆棧為空。如果棧頂和棧底重合，說明堆棧為空。6.3.4 6.3.4 隊(duì)列隊(duì)列 1定義定義 對(duì)于由對(duì)于由N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序列，如果在其固定的一端只允

49、許插性序列，如果在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為為隊(duì)列隊(duì)列(queue)。 把允許插入的一端叫把允許插入的一端叫隊(duì)尾隊(duì)尾(rear)，把，把只允許刪除的一端叫只允許刪除的一端叫隊(duì)首隊(duì)首(front)。2 2運(yùn)算運(yùn)算 隊(duì)列的基本運(yùn)算主要有：入隊(duì)、出隊(duì)和判斷。隊(duì)列的基本運(yùn)算主要有：入隊(duì)、出隊(duì)和判斷。 入隊(duì)入隊(duì) 入隊(duì)是在隊(duì)列中插入一個(gè)新數(shù)據(jù)元素的過入隊(duì)是在隊(duì)列中插入一個(gè)新數(shù)據(jù)元素的過程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾，。程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾，。 出隊(duì)出隊(duì)

50、出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過程，出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過程，刪除在隊(duì)首進(jìn)行并把出來的數(shù)據(jù)傳遞給用戶程刪除在隊(duì)首進(jìn)行并把出來的數(shù)據(jù)傳遞給用戶程序。序。 A B C D E 頭指針 尾指針 A B C D E F G 頭指針 尾指針 F，G入隊(duì) A B C D E 頭指針 尾指針 D E F G 頭指針 尾指針 A，B，C 出隊(duì) 判斷：判斷： 判斷操作用來檢查隊(duì)列是否為空，返判斷操作用來檢查隊(duì)列是否為空，返回結(jié)果是一個(gè)邏輯值：真或假，如圖?；亟Y(jié)果是一個(gè)邏輯值：真或假，如圖。 頭 指 針 尾 指 針 3 3循環(huán)隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列的實(shí)現(xiàn) F G A B C D E 頭指針 尾指針 內(nèi)存

51、塊第一個(gè)存儲(chǔ)單元 內(nèi)存塊最后一個(gè)存儲(chǔ)單元 隊(duì)列移動(dòng) 6.3.5 6.3.5 樹樹 1定義定義 樹形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱樹形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為是一個(gè)節(jié)點(diǎn)，除了一個(gè)惟一的所謂為是一個(gè)節(jié)點(diǎn)，除了一個(gè)惟一的所謂根根節(jié)點(diǎn)節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)都有且只有一個(gè)外，其他每個(gè)節(jié)點(diǎn)都有且只有一個(gè)父節(jié)點(diǎn)，每個(gè)元素可以有多個(gè)子節(jié)點(diǎn)。父節(jié)點(diǎn)，每個(gè)元素可以有多個(gè)子節(jié)點(diǎn)。 樹主要用在大型、動(dòng)態(tài)列表的搜索，樹主要用在大型、動(dòng)態(tài)列表的搜索，人工智能系統(tǒng)和編碼算法等問題中。人工智能系統(tǒng)和編碼算法等問題中。2 2運(yùn)算運(yùn)算 樹常見的基本運(yùn)算有：插入、刪除和遍歷。樹常見的基本運(yùn)算有：插入、刪除和遍歷。 插入插入 在樹中合

52、適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新在樹中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。 刪除刪除 在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。 遍歷遍歷 按照某種順序或規(guī)則，對(duì)樹中的每個(gè)節(jié)點(diǎn)逐一進(jìn)按照某種順序或規(guī)則，對(duì)樹中的每個(gè)節(jié)點(diǎn)逐一進(jìn)行訪問的過程。行訪問的過程。3 3實(shí)現(xiàn)實(shí)現(xiàn) Left A Right Left B Right C Right D E F 6.3.6 6.3.6 圖圖 1定義定義 在圖形

53、結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來表示，頂點(diǎn)之間的鄰接關(guān)系可以性用一條邊來表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。是任意的。 圖可以用來描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，圖可以用來描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中獲得最小生成樹。除此以外，圖在以及圖論中獲得最小生成樹。除此以外，圖在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。都有著非常廣泛的應(yīng)用。2 2運(yùn)算運(yùn)算 常見的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添常見的基本運(yùn)算有：添

54、加頂點(diǎn)、刪除頂點(diǎn)、添加邊、刪除邊和遍歷圖。加邊、刪除邊和遍歷圖。 添加頂點(diǎn)添加頂點(diǎn) 在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常是孤立的節(jié)點(diǎn)，還沒有邊連接。是孤立的節(jié)點(diǎn)，還沒有邊連接。 刪除頂點(diǎn)刪除頂點(diǎn) 在圖中去掉一個(gè)頂點(diǎn)，顯然，在去掉一個(gè)在圖中去掉一個(gè)頂點(diǎn)，顯然，在去掉一個(gè)頂點(diǎn)的同時(shí)還應(yīng)該刪除與該頂點(diǎn)所連接的邊。頂點(diǎn)的同時(shí)還應(yīng)該刪除與該頂點(diǎn)所連接的邊。 添加邊添加邊 根據(jù)指定的頂點(diǎn)，添加相應(yīng)的邊。根據(jù)指定的頂點(diǎn)，添加相應(yīng)的邊。 刪除邊刪除邊 根據(jù)指定的頂點(diǎn)，刪除相應(yīng)的邊。根據(jù)指定的頂點(diǎn)，刪除相應(yīng)的邊。 遍歷圖遍歷圖 按照一定的規(guī)則，對(duì)圖中的每個(gè)數(shù)按照一定的規(guī)則，對(duì)

55、圖中的每個(gè)數(shù)據(jù)頂點(diǎn)逐一進(jìn)行訪問。據(jù)頂點(diǎn)逐一進(jìn)行訪問。3 3實(shí)現(xiàn)實(shí)現(xiàn) 圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實(shí)現(xiàn)。圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實(shí)現(xiàn)。對(duì)于各個(gè)頂點(diǎn)和頂點(diǎn)之間的關(guān)系分別采對(duì)于各個(gè)頂點(diǎn)和頂點(diǎn)之間的關(guān)系分別采用鄰接矩陣和鄰接列表來進(jìn)行描述。用鄰接矩陣和鄰接列表來進(jìn)行描述。 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E (a) (b) (c) 6.4.1 6.4.1 概述概述 1算法的定義算法的定義 準(zhǔn)確地說，準(zhǔn)確地

56、說，“算法算法(Algorithm)是一組明確是一組明確的、可以執(zhí)行的步驟的有序集合，它在有限的的、可以執(zhí)行的步驟的有序集合，它在有限的時(shí)間內(nèi)終止并產(chǎn)生結(jié)果時(shí)間內(nèi)終止并產(chǎn)生結(jié)果”。 算法和數(shù)據(jù)結(jié)構(gòu)之間存在密切聯(lián)系。數(shù)據(jù)結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)之間存在密切聯(lián)系。數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)的不同，通常的采用是算法的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)的不同，通常的采用的算法也會(huì)不同；當(dāng)問題的求解算法一旦確定，的算法也會(huì)不同；當(dāng)問題的求解算法一旦確定，也可以選擇合適的數(shù)據(jù)結(jié)構(gòu)加以實(shí)現(xiàn)，合理的也可以選擇合適的數(shù)據(jù)結(jié)構(gòu)加以實(shí)現(xiàn)，合理的數(shù)據(jù)結(jié)構(gòu)能夠簡(jiǎn)化算法。數(shù)據(jù)結(jié)構(gòu)能夠簡(jiǎn)化算法。6.4 6.4 算法分析基礎(chǔ)算法分析基礎(chǔ) (1)

57、有窮性有窮性(可終止性可終止性) 一個(gè)算法必須在有限個(gè)操作步驟內(nèi)以及合一個(gè)算法必須在有限個(gè)操作步驟內(nèi)以及合理的時(shí)間內(nèi)執(zhí)行完成。理的時(shí)間內(nèi)執(zhí)行完成。 (2) 確定性確定性 算法中的每一個(gè)操作步驟都必須有明確的算法中的每一個(gè)操作步驟都必須有明確的含義，不允許存在二義性。含義，不允許存在二義性。 (3) 有效性有效性(可執(zhí)行性可執(zhí)行性) 算法中描述的操作步驟都是可執(zhí)行的，并算法中描述的操作步驟都是可執(zhí)行的，并能最終得到確定的結(jié)果。能最終得到確定的結(jié)果。 (4) 輸入及輸出輸入及輸出 一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入數(shù)據(jù)、有一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入數(shù)據(jù)、有1個(gè)或多個(gè)輸出數(shù)據(jù)。個(gè)或多個(gè)輸出數(shù)據(jù)。2算法的

58、特性算法的特性3 3算法的描述算法的描述(1) 自然語言表示自然語言表示 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是中文、英文等。是中文、英文等。 例如，求三個(gè)數(shù)中最大值的問題，可以描述為：例如，求三個(gè)數(shù)中最大值的問題，可以描述為： 比較前兩個(gè)數(shù)；比較前兩個(gè)數(shù)； 將將中較大的數(shù)與第三個(gè)數(shù)進(jìn)行比較；中較大的數(shù)與第三個(gè)數(shù)進(jìn)行比較； 步驟步驟中較大的數(shù)即為所求。中較大的數(shù)即為所求。 (2) 流程圖表示流程圖表示 流程圖是用規(guī)定的一組圖形符號(hào)、流程線流程圖是用規(guī)定的一組圖形符號(hào)、流程線和文字說明來表示算法的一種表示方法。和文字說明來表示算法的一種表示方法。 (3) 偽碼

59、偽碼 偽碼用一種介于自然語言與計(jì)算機(jī)語言之偽碼用一種介于自然語言與計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。比計(jì)算機(jī)語言形間的文字和符號(hào)來描述算法。比計(jì)算機(jī)語言形式靈活，格式緊湊，沒有嚴(yán)格的語法。式靈活，格式緊湊，沒有嚴(yán)格的語法。 (4) 程序設(shè)計(jì)語言形式程序設(shè)計(jì)語言形式 算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)語言來表示，如，語言來表示，如，C、C+、Java等都可以用等都可以用來描述算法。來描述算法。 例如，求兩個(gè)數(shù)的較大者。用偽代碼描述算法例如，求兩個(gè)數(shù)的較大者。用偽代碼描述算法如下：如下： Input: two number s:a,b 1.if (the

60、first number a is greater than or equal to the second number b) then 1.1 return a else 1.2 return b end if end6.4.2 6.4.2 常用算法介紹常用算法介紹 1遞歸算法遞歸算法 如果一個(gè)過程直接或間接地調(diào)用它如果一個(gè)過程直接或間接地調(diào)用它本身，則稱該過程是遞歸的。本身，則稱該過程是遞歸的。 例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法定義函數(shù)定義函數(shù)f (n)如下：如下：1!(1)!nn n 遞歸的情況包括所謂的遞推法和分治法。遞歸的情況包括所謂的遞推法和分治