程序設(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ù)類(lèi)型及其實(shí)現(xiàn)掌握數(shù)據(jù)結(jié)構(gòu)中的基本數(shù)據(jù)類(lèi)型及其實(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ì)是程序員編寫(xiě)一系列可存儲(chǔ)的指令以是

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

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

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

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

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

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

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

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

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

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

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

13、半以上，運(yùn)行時(shí)間也要長(zhǎng)一些。半以上，運(yùn)行時(shí)間也要長(zhǎng)一些。 因此，在很多對(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í)語(yǔ)言，主要是匯編語(yǔ)言，仍然得到了一定低級(jí)語(yǔ)言，主要是匯編語(yǔ)言，仍然得到了一定的應(yīng)用。的應(yīng)用。6.1.3 6.1.3 高級(jí)語(yǔ)言的基本內(nèi)容高級(jí)語(yǔ)言的基本內(nèi)容 高級(jí)程序設(shè)計(jì)語(yǔ)言依賴(lài)于各自特定的語(yǔ)句和語(yǔ)高級(jí)程序設(shè)計(jì)語(yǔ)言依賴(lài)于各自特定的語(yǔ)句和語(yǔ)法。一條一條的語(yǔ)句是構(gòu)成源程序的基本單位。法。一條一條的語(yǔ)句是構(gòu)成源程序的基本單位。高級(jí)語(yǔ)言的一條語(yǔ)句被編譯或解釋時(shí)往往會(huì)對(duì)高級(jí)語(yǔ)言的一條語(yǔ)句被

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

15、單字符和多字符兩種情況。單字符號(hào)可以分為單字符和多字符兩種情況。單字符基本符號(hào)由單個(gè)字符組成，在高級(jí)語(yǔ)言中通符基本符號(hào)由單個(gè)字符組成，在高級(jí)語(yǔ)言中通常都有下列幾種單字符基本符號(hào)：常都有下列幾種單字符基本符號(hào)： (1) 字母字母 大寫(xiě)英文字母大寫(xiě)英文字母AZ，小寫(xiě)英文字母，小寫(xiě)英文字母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í)語(yǔ)言中的多字符基本

16、符號(hào)由兩個(gè)在高級(jí)語(yǔ)言中的多字符基本符號(hào)由兩個(gè)或兩個(gè)以上的字符組成，例如或兩個(gè)以上的字符組成，例如GoTo(轉(zhuǎn)轉(zhuǎn)移移)、(小于或等于小于或等于)、AND(與與)等等。等等。2 2高級(jí)語(yǔ)言的基本元素高級(jí)語(yǔ)言的基本元素 基本元素由基本符號(hào)組成，可分為數(shù)、基本元素由基本符號(hào)組成，可分為數(shù)、邏輯值、名字、標(biāo)號(hào)和字符串等五大類(lèi)。邏輯值、名字、標(biāo)號(hào)和字符串等五大類(lèi)。 (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) 名字名字 由字符組成，一般約定名字的開(kāi)頭是字母或者由字符組成，一般約定名字的開(kāi)頭是字母或者下劃線(xiàn)，其后可為字母或數(shù)字，如下劃線(xiàn)，其后可為字母或數(shù)字，如XYZ、A123、_C等。名字可用來(lái)定義常量、變量、等。名字可用來(lái)定義常量、變量、函數(shù)、過(guò)程或子程序的，也被用來(lái)定義成某些函數(shù)、過(guò)程或子程序的，也被用來(lái)定義成某些東西，故也稱(chēng)為標(biāo)識(shí)符。在高級(jí)語(yǔ)言中，一般東西，故也稱(chēng)為標(biāo)識(shí)符。在高級(jí)語(yǔ)言中，一般還規(guī)定了組成名字的字符的長(zhǎng)度，即字符個(gè)數(shù)。還規(guī)定了組成名字的字符的長(zhǎng)度，即字符個(gè)數(shù)。 (4) 標(biāo)號(hào)標(biāo)號(hào) 是在高級(jí)語(yǔ)言中的程序語(yǔ)句前所加的一個(gè)名字，是在高級(jí)語(yǔ)言中的程序語(yǔ)句前所加的

18、一個(gè)名字，主要用來(lái)指示程序可能的轉(zhuǎn)移方向。主要用來(lái)指示程序可能的轉(zhuǎn)移方向。 (5) 字符串字符串 由一串字符所組成。在不同的高級(jí)語(yǔ)言由一串字符所組成。在不同的高級(jí)語(yǔ)言中，字符串中的多個(gè)字符放在一對(duì)單引中，字符串中的多個(gè)字符放在一對(duì)單引號(hào)或雙引號(hào)中。號(hào)或雙引號(hào)中。3 3基本的數(shù)據(jù)類(lèi)型基本的數(shù)據(jù)類(lèi)型 任何一種高級(jí)語(yǔ)言都會(huì)定義一些基本的任何一種高級(jí)語(yǔ)言都會(huì)定義一些基本的數(shù)據(jù)類(lèi)型?；镜臄?shù)據(jù)類(lèi)型通常包括整數(shù)據(jù)類(lèi)型?；镜臄?shù)據(jù)類(lèi)型通常包括整數(shù)數(shù)據(jù)類(lèi)型、實(shí)數(shù)數(shù)據(jù)類(lèi)型和字符數(shù)據(jù)數(shù)數(shù)據(jù)類(lèi)型、實(shí)數(shù)數(shù)據(jù)類(lèi)型和字符數(shù)據(jù)類(lèi)型等。類(lèi)型等。 在程序中，除了值無(wú)需改變的常數(shù)外，在程序中，除了值無(wú)需改變的常數(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)存空間。 變量的類(lèi)型實(shí)質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間變量的類(lè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ù)類(lèi)型結(jié)構(gòu)數(shù)據(jù)類(lèi)型 是在基本數(shù)據(jù)類(lèi)型的基礎(chǔ)上構(gòu)造出來(lái)的數(shù)據(jù)類(lèi)是在基本數(shù)據(jù)類(lèi)型的基礎(chǔ)上構(gòu)造出來(lái)的數(shù)據(jù)類(lèi)型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級(jí)語(yǔ)言都支持的型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級(jí)語(yǔ)言都支持的兩種最基本的結(jié)構(gòu)數(shù)據(jù)類(lèi)型。兩種最基本的結(jié)構(gòu)數(shù)據(jù)類(lèi)型。 (1) 數(shù)組類(lèi)型數(shù)組類(lèi)型 數(shù)組是若干個(gè)相同類(lèi)型的數(shù)據(jù)的集合。數(shù)組是若干個(gè)相同類(lèi)型的數(shù)據(jù)的集合。 (2) 用戶(hù)自定義的結(jié)構(gòu)體類(lèi)型用戶(hù)自定義的結(jié)構(gòu)體類(lèi)型 結(jié)構(gòu)體是隸屬于同一個(gè)事物的多個(gè)不同類(lèi)型的結(jié)構(gòu)體是隸屬于同一個(gè)事物的多個(gè)不同類(lèi)型的數(shù)據(jù)的集合，用來(lái)表示具有若干

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

22、算術(shù)表達(dá)式、邏輯表達(dá)式和字符串算術(shù)表達(dá)式、邏輯表達(dá)式和字符串表達(dá)式表達(dá)式等幾種情況。等幾種情況。 高級(jí)語(yǔ)言中的運(yùn)算符大致包括以下幾個(gè)方面：高級(jí)語(yǔ)言中的運(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語(yǔ)句語(yǔ)句 語(yǔ)句是構(gòu)成高級(jí)語(yǔ)言源程序的基本單位，語(yǔ)句是構(gòu)成高級(jí)語(yǔ)言源程序的基本單位，是由基本元素、運(yùn)算符、表達(dá)式等組成。是由基本元素、運(yùn)算符、表達(dá)式等組成。任何一種高級(jí)語(yǔ)言往往都支持賦值、條任何一種高級(jí)語(yǔ)言往往都支持賦值、條件判斷、循環(huán)、輸入輸出等語(yǔ)句。程序件判斷

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

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

26、一段時(shí)間后，可能就是半年或者幾個(gè)月以后，程序員自己也讀不懂自己的程序了。個(gè)月以后，程序員自己也讀不懂自己的程序了。況且，程序不僅要自己看得懂，更重要的是也況且，程序不僅要自己看得懂，更重要的是也要讓別人能夠看懂。要讓別人能夠看懂。9 9程序設(shè)計(jì)風(fēng)格程序設(shè)計(jì)風(fēng)格(1) 編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。(2) 程序中應(yīng)給出必要的注釋?zhuān)绕湓谧兞慷x、調(diào)用接口、參程序中應(yīng)給出必要的注釋?zhuān)绕湓谧兞慷x、調(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ī)范的命名方法，避免含義不明確的縮寫(xiě)，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含義不明確的縮寫(xiě)，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含義和數(shù)據(jù)類(lèi)型。義和數(shù)據(jù)類(lèi)型。(4) 采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。(5) 每一行只寫(xiě)一條語(yǔ)句，使用括號(hào)間隔表達(dá)式或語(yǔ)句的組成部每一行只寫(xiě)一條語(yǔ)句，使用括號(hào)間隔表達(dá)式或語(yǔ)句的組成部分，使組成部分清晰；分，使組成部分清晰；(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ù)防用戶(hù)的操作錯(cuò)誤，做到廢進(jìn)廢出。提高程序健壯性，預(yù)防用戶(hù)的操作錯(cuò)誤，做到廢進(jìn)廢出。 1010高級(jí)語(yǔ)言程序的運(yùn)行高級(jí)語(yǔ)言程序的運(yùn)行 使用高級(jí)語(yǔ)言編制程序的一般過(guò)程可以歸納為使用高級(jí)語(yǔ)言編制程序的一般過(guò)程可以歸納為以下幾個(gè)步驟：以下幾個(gè)步驟： (1) 使用文本編輯工具，逐條編寫(xiě)源程序的語(yǔ)使用文本編輯工具，逐條編寫(xiě)源程序的語(yǔ)句。存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的句。存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的高級(jí)語(yǔ)

29、言有關(guān)。高級(jí)語(yǔ)言有關(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í)子問(wèn)題 二級(jí)子問(wèn)題 二級(jí)子問(wèn)題 需要解決的復(fù)雜問(wèn)題 三級(jí)子

30、問(wèn)題 三級(jí)子問(wèn)題 三級(jí)子問(wèn)題 . . . . . . . . . 最小問(wèn)題 最小問(wèn)題 最小問(wèn)題 結(jié)構(gòu)化程序設(shè)計(jì)的結(jié)構(gòu)化程序設(shè)計(jì)的原則原則是：是： (1) 使用順序、選擇、循環(huán)使用順序、選擇、循環(huán)3種基本控制種基本控制結(jié)構(gòu)表示程序邏輯。結(jié)構(gòu)表示程序邏輯。 (2)程序語(yǔ)句組織成容易識(shí)別的語(yǔ)句模塊，程序語(yǔ)句組織成容易識(shí)別的語(yǔ)句模塊，每個(gè)模塊都是單入口、單出口。每個(gè)模塊都是單入口、單出口。 (3)嚴(yán)格控制嚴(yán)格控制GOTO語(yǔ)句的使用。語(yǔ)句的使用。(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ù)雜的問(wèn)題可以劃分為多個(gè)簡(jiǎn)單問(wèn)題的組一個(gè)復(fù)雜的問(wèn)題可以劃分為多個(gè)簡(jiǎn)單問(wèn)題的組合。合。 在自頂向下、逐步細(xì)化的過(guò)程中，把復(fù)雜問(wèn)題在自頂向下、逐步細(xì)化的過(guò)程中，把復(fù)雜問(wèn)題分解成一個(gè)個(gè)簡(jiǎn)單問(wèn)題的最基本方法就是模塊分解成一個(gè)個(gè)簡(jiǎn)單問(wèn)題的最基本方法就是模塊化。化。 模塊化便于問(wèn)題的分析，模塊體現(xiàn)了信息隱藏模塊化便于問(wè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ì)象，通過(guò)抽象找出同一類(lèi)對(duì)象的共同對(duì)象，通過(guò)抽象找出同一類(lèi)對(duì)象的共同屬性屬性(靜態(tài)特征靜態(tài)特征)和行為和行為(動(dòng)態(tài)特征動(dòng)態(tài)特征)，形成，形成類(lèi)。類(lèi)。2 2對(duì)象和類(lèi)對(duì)象和類(lèi) 對(duì)象對(duì)象 是對(duì)現(xiàn)實(shí)問(wèn)題的高度概括、分類(lèi)和是對(duì)現(xiàn)實(shí)問(wèn)題的高度概括、分類(lèi)和抽象。每個(gè)對(duì)象都只有自己的數(shù)據(jù)和相抽象。每個(gè)對(duì)象都只有自己的數(shù)據(jù)和相應(yīng)的處理函數(shù)，整個(gè)程序是由一系列相應(yīng)的處理函數(shù)，整個(gè)程序是由一系列相互作用的對(duì)象來(lái)構(gòu)成，不同對(duì)象之間是互作用的對(duì)象來(lái)構(gòu)成，不同對(duì)象之間是通過(guò)發(fā)送消息來(lái)實(shí)現(xiàn)相互聯(lián)系、相互作通過(guò)發(fā)送消息來(lái)實(shí)現(xiàn)相互聯(lián)系、相互作用。

33、用。 方法方法 在對(duì)象內(nèi)的操作通常叫做方法。在對(duì)象內(nèi)的操作通常叫做方法。 類(lèi) 定義了一組大體上相似的對(duì)象。一個(gè)類(lèi)定義了一組大體上相似的對(duì)象。一個(gè)類(lèi)所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行為和屬性。為和屬性。 對(duì)象則是類(lèi)的具體化，是類(lèi)的實(shí)例。對(duì)象則是類(lèi)的具體化，是類(lèi)的實(shí)例。 類(lèi)通過(guò)派生可以有子類(lèi)，同樣也可以有父類(lèi)，類(lèi)通過(guò)派生可以有子類(lèi)，同樣也可以有父類(lèi)，形成層次結(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ì)特征，從而抽象出一類(lèi)對(duì)象的共性并加以描述。出一類(lèi)對(duì)象的共性并加以描述。 對(duì)一個(gè)問(wèn)題的抽象一般來(lái)講應(yīng)該包對(duì)一個(gè)問(wèn)題的抽象一般來(lái)講應(yīng)該包括兩個(gè)方面：數(shù)據(jù)抽象和代碼抽象括兩個(gè)方面：數(shù)據(jù)抽象和代碼抽象(或稱(chēng)或稱(chēng)為行為抽象為行為抽象)。4 4封裝性封裝性 封裝的兩個(gè)含義封裝的兩個(gè)含義： 第一是，將抽象得到的數(shù)據(jù)成員和代碼成第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結(jié)合，形成一個(gè)不可分割的整體，即對(duì)象，員相結(jié)合，形成一個(gè)不可分割的整體，即對(duì)象，這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。 第二個(gè)含義稱(chēng)為信息隱蔽，即盡可能隱蔽第二個(gè)含義稱(chēng)為信息隱蔽，即盡可能隱

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ù)訪(fǎng)問(wèn)權(quán)限的合理控制，把整個(gè)程序?qū)崿F(xiàn)對(duì)數(shù)據(jù)訪(fǎng)問(wèn)權(quán)限的合理控制，把整個(gè)程序中不同部分的相互影響減少到最低限度。中不同部分的相互影響減少到最低限度。5 5繼承性繼承性 繼承性繼承性 是父類(lèi)和子類(lèi)之間共享數(shù)據(jù)和方法的機(jī)制。是父類(lèi)和子類(lèi)之間共享數(shù)據(jù)和方法的機(jī)制。在定義一個(gè)類(lèi)的時(shí)候，可以以一個(gè)已經(jīng)存在的在定義一個(gè)類(lèi)的時(shí)候，可以以一個(gè)已經(jīng)存在的類(lèi)為基礎(chǔ)，并把這個(gè)已經(jīng)存在的類(lèi)所包含的屬類(lèi)為基礎(chǔ)，并把這個(gè)已經(jīng)存在的類(lèi)所包含的屬性和方法作為

36、自身的一部分，然后加入新的屬性和方法作為自身的一部分，然后加入新的屬性和方法以區(qū)別于原來(lái)的類(lèi)。性和方法以區(qū)別于原來(lái)的類(lèi)。 原有的類(lèi)稱(chēng)為原有的類(lèi)稱(chēng)為基類(lèi)或父類(lèi)基類(lèi)或父類(lèi)，產(chǎn)生的新類(lèi)，產(chǎn)生的新類(lèi)稱(chēng)為稱(chēng)為派生類(lèi)派生類(lèi)。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ù)類(lèi)型數(shù)據(jù)、數(shù)據(jù)類(lèi)型 數(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ù)類(lèi)型數(shù)據(jù)類(lèi)型 是指具有相同取值范圍和可以實(shí)施同種操是指具有相同取值范圍和可以實(shí)施同種操作的數(shù)據(jù)的集合的總稱(chēng)。例如，在程序設(shè)計(jì)中，作的數(shù)據(jù)的集合的總稱(chēng)。例如，在程序設(shè)計(jì)中，通常會(huì)有字符型、整型、數(shù)組等多種數(shù)據(jù)類(lèi)型。通常會(huì)有字符型、整型、數(shù)組等多種數(shù)據(jù)類(lèi)型。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ù)單元稱(chēng)為據(jù)單元稱(chēng)為數(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)成的。 同類(lèi)數(shù)據(jù)元素的集合稱(chēng)為同類(lèi)數(shù)據(jù)元素的集合稱(chēng)為數(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)。 線(xiàn)性結(jié)構(gòu)線(xiàn)性結(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)系被稱(chēng)為線(xiàn)性結(jié)構(gòu)。樣的數(shù)據(jù)元素之間的關(guān)系被稱(chēng)為線(xiàn)性結(jié)構(gòu)。 樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且除了一個(gè)被稱(chēng)為根節(jié)點(diǎn)的元素外，每個(gè)元素都有一個(gè)除了一個(gè)被稱(chēng)為根節(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)稱(chēng)為樹(shù)形結(jié)構(gòu)。稱(chēng)為樹(shù)形結(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)稱(chēng)為圖形結(jié)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱(chēng)為圖形結(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ēng)為順序存儲(chǔ)結(jié)單元中，由此得到的存儲(chǔ)表示稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)。構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語(yǔ)言中順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是的數(shù)組來(lái)實(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)系通過(guò)附設(shè)位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針域來(lái)實(shí)現(xiàn)，由此得到的存儲(chǔ)表示的指針域來(lái)實(shí)現(xiàn)，由此得到的存儲(chǔ)表示稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針來(lái)實(shí)現(xiàn)。語(yǔ)言中的指針來(lái)實(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) 通過(guò)構(gòu)造相應(yīng)的散列函數(shù)，由散列通過(guò)構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來(lái)確定元素存放的地址。函數(shù)的值來(lái)確定元素存放的地址。 (3) 數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算 數(shù)據(jù)操作的集合。常見(jiàn)的數(shù)據(jù)操作數(shù)據(jù)操作的集合。常見(jiàn)的數(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 線(xiàn)性表線(xiàn)性表 1定義定義 線(xiàn)性表線(xiàn)性表是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，

44、元素之間是一對(duì)一的線(xiàn)性關(guān)系，除了第一個(gè)元素元素之間是一對(duì)一的線(xiàn)性關(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) 線(xiàn)性表通常采用順序和鏈表兩種物線(xiàn)性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線(xiàn)性表常用的運(yùn)算主要有：鏈表結(jié)構(gòu)。線(xiàn)性表常用的運(yùn)算主要有：插入、刪除、查詢(xún)和遍歷。插入、刪除、查詢(xún)

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

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

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

48、后成為新的棧頂元素。 出棧出棧 出棧也叫退?；驈棗＃菍ｍ斣貜臈３鰲Ｒ步型藯；驈棗?，是將棧頂元素從棧中退出并傳遞給用戶(hù)程序的操作中退出并傳遞給用戶(hù)程序的操作 D C B A 入棧數(shù)據(jù)元素 E E D C B A D C B A 出棧數(shù)據(jù)元素D C B A 判斷判斷 判斷操作用來(lái)檢查棧內(nèi)數(shù)據(jù)是否為判斷操作用來(lái)檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個(gè)邏輯值：真或假?？眨祷亟Y(jié)果是一個(gè)邏輯值：真或假。如果棧頂和棧底重合，說(shuō)明堆棧為空。如果棧頂和棧底重合，說(shuō)明堆棧為空。6.3.4 6.3.4 隊(duì)列隊(duì)列 1定義定義 對(duì)于由對(duì)于由N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線(xiàn)個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線(xiàn)性序列，如果在其固定的一端只允

49、許插性序列，如果在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱(chēng)據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為為隊(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ù)元素的過(guò)入隊(duì)是在隊(duì)列中插入一個(gè)新數(shù)據(jù)元素的過(guò)程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾，。程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾，。 出隊(duì)出隊(duì)

50、出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過(guò)程，出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過(guò)程，刪除在隊(duì)首進(jìn)行并把出來(lái)的數(shù)據(jù)傳遞給用戶(hù)程刪除在隊(duì)首進(jìn)行并把出來(lái)的數(shù)據(jù)傳遞給用戶(hù)程序。序。 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ì) 判斷：判斷： 判斷操作用來(lái)檢查隊(duì)列是否為空，返判斷操作用來(lái)檢查隊(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 樹(shù)樹(shù) 1定義定義 樹(shù)形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱(chēng)樹(shù)形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱(chēng)為是一個(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)。 樹(shù)主要用在大型、動(dòng)態(tài)列表的搜索，樹(shù)主要用在大型、動(dòng)態(tài)列表的搜索，人工智能系統(tǒng)和編碼算法等問(wèn)題中。人工智能系統(tǒng)和編碼算法等問(wèn)題中。2 2運(yùn)算運(yùn)算 樹(shù)常見(jiàn)的基本運(yùn)算有：插入、刪除和遍歷。樹(shù)常見(jiàn)的基本運(yùn)算有：插入、刪除和遍歷。 插入插入 在樹(shù)中合

52、適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新在樹(shù)中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹(shù)本身所具有的性質(zhì)。的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹(shù)本身所具有的性質(zhì)。 刪除刪除 在樹(shù)中找到滿(mǎn)足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)在樹(shù)中找到滿(mǎn)足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)點(diǎn)后，也要保持該樹(shù)本身所具有的性質(zhì)。點(diǎn)后，也要保持該樹(shù)本身所具有的性質(zhì)。 遍歷遍歷 按照某種順序或規(guī)則，對(duì)樹(shù)中的每個(gè)節(jié)點(diǎn)逐一進(jìn)按照某種順序或規(guī)則，對(duì)樹(shù)中的每個(gè)節(jié)點(diǎn)逐一進(jìn)行訪(fǎng)問(wèn)的過(guò)程。行訪(fǎng)問(wèn)的過(guò)程。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ù)元素稱(chēng)為一個(gè)頂在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱(chēng)為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來(lái)表示，頂點(diǎn)之間的鄰接關(guān)系可以性用一條邊來(lái)表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。是任意的。 圖可以用來(lái)描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，圖可以用來(lái)描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中獲得最小生成樹(shù)。除此以外，圖在以及圖論中獲得最小生成樹(shù)。除此以外，圖在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。都有著非常廣泛的應(yīng)用。2 2運(yùn)算運(yùn)算 常見(jiàn)的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添常見(jiàn)的基本運(yùn)算有：添

54、加頂點(diǎn)、刪除頂點(diǎn)、添加邊、刪除邊和遍歷圖。加邊、刪除邊和遍歷圖。 添加頂點(diǎn)添加頂點(diǎn) 在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常是孤立的節(jié)點(diǎn)，還沒(méi)有邊連接。是孤立的節(jié)點(diǎn)，還沒(méi)有邊連接。 刪除頂點(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)行訪(fǎng)問(wèn)。據(jù)頂點(diǎn)逐一進(jìn)行訪(fǎng)問(wè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)系分別采用鄰接矩陣和鄰接列表來(lái)進(jìn)行描述。用鄰接矩陣和鄰接列表來(lái)進(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)確地說(shuō)，準(zhǔn)確地

56、說(shuō)，“算法算法(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)問(wèn)題的求解算法一旦確定，的算法也會(huì)不同；當(dāng)問(wèn)題的求解算法一旦確定，也可以選擇合適的數(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) 自然語(yǔ)言表示自然語(yǔ)言表示 自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是中文、英文等。是中文、英文等。 例如，求三個(gè)數(shù)中最大值的問(wèn)題，可以描述為：例如，求三個(gè)數(shù)中最大值的問(wèn)題，可以描述為： 比較前兩個(gè)數(shù)；比較前兩個(gè)數(shù)； 將將中較大的數(shù)與第三個(gè)數(shù)進(jìn)行比較；中較大的數(shù)與第三個(gè)數(shù)進(jìn)行比較； 步驟步驟中較大的數(shù)即為所求。中較大的數(shù)即為所求。 (2) 流程圖表示流程圖表示 流程圖是用規(guī)定的一組圖形符號(hào)、流程線(xiàn)流程圖是用規(guī)定的一組圖形符號(hào)、流程線(xiàn)和文字說(shuō)明來(lái)表示算法的一種表示方法。和文字說(shuō)明來(lái)表示算法的一種表示方法。 (3) 偽碼

59、偽碼 偽碼用一種介于自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之偽碼用一種介于自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。比計(jì)算機(jī)語(yǔ)言形間的文字和符號(hào)來(lái)描述算法。比計(jì)算機(jī)語(yǔ)言形式靈活，格式緊湊，沒(méi)有嚴(yán)格的語(yǔ)法。式靈活，格式緊湊，沒(méi)有嚴(yán)格的語(yǔ)法。 (4) 程序設(shè)計(jì)語(yǔ)言形式程序設(shè)計(jì)語(yǔ)言形式 算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)表示，如，語(yǔ)言來(lái)表示，如，C、C+、Java等都可以用等都可以用來(lái)描述算法。來(lái)描述算法。 例如，求兩個(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è)過(guò)程直接或間接地調(diào)用它如果一個(gè)過(guò)程直接或間接地調(diào)用它本身，則稱(chēng)該過(guò)程是遞歸的。本身，則稱(chēng)該過(guò)程是遞歸的。 例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法定義函數(shù)定義函數(shù)f (n)如下：如下：1!(1)!nn n 遞歸的情況包括所謂的遞推法和分治法。遞歸的情況包括所謂的遞推法和分治