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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、值是可以修改的。在程序大部分數(shù)據(jù)的值是可以修改的。在程序中，中，變量變量是指代表某個具體數(shù)值，并且是指代表某個具體數(shù)值，并且所代表的數(shù)值可改變的一個符號名字。所代表的數(shù)值可改變的一個符號名字。 變量必須先定義，然后才能使用，這是變量必須先定義，然后才能使用，這是條基條基本原則。本原則。 變量實質(zhì)上代表了一個特定大小的內(nèi)存單元空變量實質(zhì)上代表了一個特定大小的內(nèi)存單元空間。間。 定義變量的實質(zhì)就是讓程序為該變量分配一個定義變量的實質(zhì)就是讓程序為該變量分配一個特定的內(nèi)存空間。特定的內(nèi)存空間。 變量的類型實質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間變量的類型實質(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ù)高級語言都支持的型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級語言都支持的兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。 (1) 數(shù)組類型數(shù)組類型 數(shù)組是若干個相同類型的數(shù)據(jù)的集合。數(shù)組是若干個相同類型的數(shù)據(jù)的集合。 (2) 用戶自定義的結(jié)構(gòu)體類型用戶自定義的結(jié)構(gòu)體類型 結(jié)構(gòu)體是隸屬于同一個事物的多個不同類型的結(jié)構(gòu)體是隸屬于同一個事物的多個不同類型的數(shù)據(jù)的集合，用來表示具有若干

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

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

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

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

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

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

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

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

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

30、問題 三級子問題 三級子問題 . . . . . . . . . 最小問題 最小問題 最小問題 結(jié)構(gòu)化程序設(shè)計的結(jié)構(gòu)化程序設(shè)計的原則原則是：是： (1) 使用順序、選擇、循環(huán)使用順序、選擇、循環(huán)3種基本控制種基本控制結(jié)構(gòu)表示程序邏輯。結(jié)構(gòu)表示程序邏輯。 (2)程序語句組織成容易識別的語句模塊，程序語句組織成容易識別的語句模塊，每個模塊都是單入口、單出口。每個模塊都是單入口、單出口。 (3)嚴格控制嚴格控制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模塊模塊 一個復(fù)雜的問題可以劃分為多個簡單問題的組一個復(fù)雜的問題可以劃分為多個簡單問題的組合。合。 在自頂向下、逐步細化的過程中，把復(fù)雜問題在自頂向下、逐步細化的過程中，把復(fù)雜問題分解成一個個簡單問題的最基本方法就是模塊分解成一個個簡單問題的最基本方法就是模塊化?；?模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實現(xiàn)。的概念。模塊常用子程序加以實現(xiàn)。1 1面向?qū)ο蟮乃枷朊嫦驅(qū)ο蟮乃枷?.2.2 6.2.2 面向?qū)ο蟮某绦蛟O(shè)計方法面向?qū)ο蟮某绦蛟O(shè)計方法 OO(Object Oriented，面向?qū)ο?，面向?qū)ο?/p>

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

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

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

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

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

37、算機中并被計算機進行處理的符號的集合。算機進行處理的符號的集合。 數(shù)據(jù)類型數(shù)據(jù)類型 是指具有相同取值范圍和可以實施同種操是指具有相同取值范圍和可以實施同種操作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計中，作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計中，通常會有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。通常會有字符型、整型、數(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ù)項、數(shù)據(jù)對象數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象 能夠獨立并完整地描述客觀世界實體的基本數(shù)能夠獨立并完整地描述客觀世界實體的基本數(shù)據(jù)單元稱為據(jù)單元稱為數(shù)據(jù)元素數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單，它是

38、組成數(shù)據(jù)的基本單位。位。 數(shù)據(jù)項數(shù)據(jù)項是組成數(shù)據(jù)元素的不可分割的最小單位。是組成數(shù)據(jù)元素的不可分割的最小單位。最簡單的數(shù)據(jù)元素就是由一個數(shù)據(jù)項構(gòu)成的。最簡單的數(shù)據(jù)元素就是由一個數(shù)據(jù)項構(gòu)成的。 同類數(shù)據(jù)元素的集合稱為同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象數(shù)據(jù)對象。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ù)的運算。以及數(shù)據(jù)的運算。 數(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)系，即除了第一個數(shù)據(jù)元素和最后一個元素外，其關(guān)系，即除了第一個數(shù)據(jù)元素和最后一個元素外，其他每個元素都有惟一的一個前驅(qū)和一個后繼元素，這他每個元素都有惟一的一個前驅(qū)和一個后繼元素，這樣的數(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)系，且除了一個被稱為根節(jié)點的元素外，每個元素都有一個除了一個被稱為根節(jié)點的元素外，每個元素都

40、有一個前驅(qū)節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯結(jié)構(gòu)前驅(qū)節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。稱為樹形結(jié)構(gòu)。 圖形結(jié)構(gòu)圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果任何一個數(shù)據(jù)元素都可以有多個數(shù)據(jù)結(jié)構(gòu)中，如果任何一個數(shù)據(jù)元素都可以有多個前驅(qū)節(jié)點和多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為圖形結(jié)前驅(qū)節(jié)點和多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。構(gòu)。 (2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計算機存儲器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)算機存儲器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)不僅要存儲數(shù)據(jù)本身，還要存儲表示數(shù)不僅要存儲數(shù)據(jù)本身，還要存儲表示數(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ù)的存儲單元中，把所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存儲在物理位置相鄰的存儲邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結(jié)單元中，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。構(gòu)。 順序存儲結(jié)構(gòu)常借助于程序設(shè)計語言中順序存儲結(jié)構(gòu)常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。優(yōu)點是使用方法簡單，缺點是的數(shù)組來實現(xiàn)。優(yōu)點是使用方法簡單，缺點是必須預(yù)先分析出所需定義數(shù)組的大小。必須預(yù)先分析出所需

42、定義數(shù)組的大小。 鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 對邏輯上相鄰的元素不要求其物理對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來實現(xiàn)，由此得到的存儲表示的指針域來實現(xiàn)，由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。稱為鏈式存儲結(jié)構(gòu)。 鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針來實現(xiàn)。語言中的指針來實現(xiàn)。 索引結(jié)構(gòu)索引結(jié)構(gòu) 針對每個數(shù)據(jù)結(jié)構(gòu)建立一張所謂的針對每個數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個數(shù)據(jù)元素占用表中的一項，索引表，每個數(shù)據(jù)元素占用表中的一項，每個表項包含一個能夠惟一識別一個元每個表項包含一個能夠惟一識別一個元素的關(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ù)運算數(shù)據(jù)運算 數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計算機程序加以實數(shù)據(jù)操作通常由計算機程序加以實現(xiàn)，通常也叫現(xiàn)，通常也叫算法實現(xiàn)算法實現(xiàn)。6.3.2 6.3.2 線性表線性表 1定義定義 線性表線性表是由有限個相同的數(shù)據(jù)元素構(gòu)成的序列，是由有限個相同的數(shù)據(jù)元素構(gòu)成的序列，

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

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

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

47、列，如果只允許在其固定的一端位置插入和刪除一如果只允許在其固定的一端位置插入和刪除一個數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱個數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為為堆?；驐６褩；驐?stack)。 允許插入或刪除的這一端稱為允許插入或刪除的這一端稱為棧項棧項，另一，另一個固定端稱為個固定端稱為棧底棧底。當(dāng)表中沒有元素時稱為。當(dāng)表中沒有元素時稱為空空棧棧。2 2運算和實現(xiàn)運算和實現(xià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é)果是一個邏輯值：真或假?？?，返回結(jié)果是一個邏輯值：真或假。如果棧頂和棧底重合，說明堆棧為空。如果棧頂和棧底重合，說明堆棧為空。6.3.4 6.3.4 隊列隊列 1定義定義 對于由對于由N個數(shù)據(jù)元素構(gòu)成的一個線個數(shù)據(jù)元素構(gòu)成的一個線性序列，如果在其固定的一端只允

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)稱為為隊列隊列(queue)。 把允許插入的一端叫把允許插入的一端叫隊尾隊尾(rear)，把，把只允許刪除的一端叫只允許刪除的一端叫隊首隊首(front)。2 2運算運算 隊列的基本運算主要有：入隊、出隊和判斷。隊列的基本運算主要有：入隊、出隊和判斷。 入隊入隊 入隊是在隊列中插入一個新數(shù)據(jù)元素的過入隊是在隊列中插入一個新數(shù)據(jù)元素的過程，插入在隊尾進行，新的元素成為隊尾，。程，插入在隊尾進行，新的元素成為隊尾，。 出隊出隊

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

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

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

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

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

55、圖中的每個數(shù)據(jù)頂點逐一進行訪問。據(jù)頂點逐一進行訪問。3 3實現(xiàn)實現(xiàn) 圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實現(xiàn)。圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實現(xiàn)。對于各個頂點和頂點之間的關(guān)系分別采對于各個頂點和頂點之間的關(guā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算法的定義算法的定義 準確地說，準確地

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

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

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

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