計(jì)算機(jī)科學(xué)導(dǎo)論(第2版)第6章 程序設(shè)計(jì)與算法分析

計(jì)算機(jī)科學(xué)導(dǎo)論 學(xué)習(xí)計(jì)算機(jī)專業(yè)的第一門(mén)基礎(chǔ)課程 第六章 程序設(shè)計(jì)與算法分析 本章要點(diǎn) 初步了解程序設(shè)計(jì)的基礎(chǔ)知識(shí) 掌握結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)的基本方法 掌握數(shù)據(jù)結(jié)構(gòu)中的基本數(shù)據(jù)類型及其實(shí)現(xiàn) 掌握程序設(shè)計(jì)算法的基本思想及幾種經(jīng)典的算法 了解編譯原理的基本知識(shí) 程序的概念 程序 就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合。 程序設(shè)計(jì) 是程序員編寫(xiě)一系列可存儲(chǔ)的指令以指示計(jì)算機(jī)完成某些工作的過(guò)程。這些指令用程序設(shè)計(jì)語(yǔ)言寫(xiě)成。 程序設(shè)計(jì)語(yǔ)言 是一組專門(mén)設(shè)計(jì)的用來(lái)生成一系列可被計(jì)算機(jī)處理和執(zhí)行的指令的符號(hào)集合。 程序設(shè)計(jì)人員用程序設(shè)計(jì)語(yǔ)言寫(xiě)成的指令稱作 代碼 。 程序設(shè)計(jì)基礎(chǔ) 計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言 分類： 低級(jí)語(yǔ)言、高級(jí)語(yǔ)言。 1）低級(jí)語(yǔ)言包括兩種類型：機(jī)器語(yǔ)言和匯編語(yǔ)言。 2） 機(jī)器語(yǔ)言 機(jī)器語(yǔ)言面向機(jī)器，可以由 不同的機(jī)器能夠識(shí)別的機(jī)器語(yǔ)言是不相同的。 機(jī)器語(yǔ)言指令都是用一串 0、 1構(gòu)成的二進(jìn)制位串來(lái)表示的。 指令系統(tǒng)是機(jī)器提供的機(jī)器指令的集合。 用二進(jìn)制編碼表示的指令，稱為機(jī)器指令，或稱為機(jī)器碼。 用機(jī)器指令編寫(xiě)的程序稱為機(jī)器語(yǔ)言程序，或稱為目標(biāo)程序，這是計(jì)算機(jī)能夠直接執(zhí)行的程序。 機(jī)器語(yǔ)言難以閱讀和理解，編寫(xiě)和修改都比較困難，而且通用性較差。 匯編語(yǔ)言 匯編語(yǔ)言也稱符號(hào)語(yǔ)言。 指令助記符是指令英文名稱的縮寫(xiě)，容易記憶。 所謂匯編語(yǔ)言，就是采用字母、數(shù)字和符號(hào)來(lái)代替由一個(gè)個(gè) 0和 1構(gòu)成的指令操作碼、寄存器、數(shù)據(jù)和存儲(chǔ)地址等，并在程序中用它們代替二進(jìn)制編碼數(shù)，這樣編寫(xiě)出來(lái)的程序就稱為符號(hào)語(yǔ)言程序或匯編語(yǔ)言程序。 大多數(shù)情況下，一條匯編指令直接對(duì)應(yīng)一條機(jī)器指令，少數(shù)對(duì)應(yīng)幾條機(jī)器指令。 匯編語(yǔ)言具有一個(gè)本質(zhì)上與機(jī)器語(yǔ)言一一對(duì)應(yīng)的指令系統(tǒng)。匯編語(yǔ)言的實(shí)質(zhì)和機(jī)器語(yǔ)言是相同的。 低級(jí)語(yǔ)言的特點(diǎn) 都與特定的計(jì)算機(jī)硬件系統(tǒng)緊密相關(guān)，來(lái)自于特定系統(tǒng)的指令系統(tǒng)，可移植性差； 專業(yè)知識(shí)要求高，要求對(duì)計(jì)算機(jī)硬件的結(jié)構(gòu)和工作原理非常熟悉； 每條指令的功能很單一，程序員編制源程序時(shí)指令比較繁瑣； 由于直接針對(duì)特定硬件編程，所以，最終的可執(zhí)行程序代碼精煉，而且執(zhí)行效率非常高。 兩者主要的區(qū)別在于：機(jī)器語(yǔ)言無(wú)需翻譯或編譯， 匯編語(yǔ)言必須經(jīng)過(guò)匯編才能得到目標(biāo)程序。 匯編 雖然匯編語(yǔ)言比機(jī)器語(yǔ)言容易閱讀理解和便于檢查，所以仍然需要一種特殊的程序，該程序能夠?qū)⒂脜R編語(yǔ)言編寫(xiě)的程序“翻譯”成 實(shí)現(xiàn)這種翻譯功能的特殊程序稱為 匯編語(yǔ)言翻譯程序、匯編程序或匯編器 。程序員手工編寫(xiě)的程序統(tǒng)稱為源程序，用匯編語(yǔ)言編寫(xiě)的源程序稱為匯編語(yǔ)言源程序，匯編程序?qū)⒃闯绦蚍g得到的機(jī)器語(yǔ)言程序稱為目標(biāo)程序，翻譯的過(guò)程稱為 匯編 。 反匯編程序 用于將目標(biāo)代碼程序轉(zhuǎn)換成相應(yīng)的匯編語(yǔ)言源程序，這一過(guò)程稱為反匯編。反匯編主要用于識(shí)別源程序代碼，常用的調(diào)試工具程序 高級(jí)語(yǔ)言的產(chǎn)生 一個(gè)問(wèn)題：如何解決程序的可移植性，即：程序員編寫(xiě)的源程序如何可以從一臺(tái)計(jì)算機(jī)很容易地轉(zhuǎn)到另一臺(tái)計(jì)算機(jī)上工作。為了解決這些問(wèn)題，人們引入了高級(jí)語(yǔ)言來(lái)編寫(xiě)程序。 所謂高級(jí)語(yǔ)言是一種由表達(dá)各種意義的“詞”和“公式”，按照一定的“語(yǔ)法規(guī)則”來(lái)編寫(xiě)程序的語(yǔ)言，又稱為程序設(shè)計(jì)語(yǔ)言或算法語(yǔ)言。 高級(jí)語(yǔ)言之所以“高級(jí)”，就是因?yàn)樗钩绦騿T可以完全不用與計(jì)算機(jī)的硬件打交道，可以不必了解機(jī)器的指令系統(tǒng)。 程序員可以把硬件上復(fù)雜的概念比如存儲(chǔ)空間抽象成一個(gè)所謂的變量之類的概念，因而程序員就可以繞開(kāi)硬件問(wèn)題而集中精力解決問(wèn)題本身，編程效率大大提高。 由于高級(jí)語(yǔ)言與具體機(jī)器無(wú)關(guān)，那么在一種機(jī)器上運(yùn)行的高級(jí)語(yǔ)言程序可以幾乎不經(jīng)改動(dòng)地移植到另一種機(jī)器上運(yùn)行，大大提高了程序的通用性。 此外，由于高級(jí)語(yǔ)言與自然語(yǔ)言 (尤其是英語(yǔ) )很相似，因此易學(xué)、易懂，也易編寫(xiě)。 高級(jí)語(yǔ)言的常見(jiàn)類型 目前已經(jīng)有許多高級(jí)語(yǔ)言在流行，并且新的類型還在不斷出現(xiàn)和升級(jí)。 用戶在實(shí)際應(yīng)用中進(jìn)行程序設(shè)計(jì)時(shí)，可根據(jù)情況選擇適合的高級(jí)語(yǔ)言。 (1) (2) (3) (4) (5) (6) C+語(yǔ)言 (7) 其他高級(jí)語(yǔ)言 基于視窗類操作系統(tǒng)的，如 +、 高級(jí)語(yǔ)言的優(yōu)點(diǎn)是語(yǔ)句的功能強(qiáng)，源程序比較短，容易學(xué)習(xí)，使用方便，通用性較強(qiáng)，便于推廣和交流。 其缺點(diǎn)是編譯程序比匯編程序復(fù)雜，而且編譯出來(lái)的目標(biāo)程序往往效率不高，目標(biāo)程序的長(zhǎng)度比有經(jīng)驗(yàn)的程序員所編的同樣功能的匯編語(yǔ)言程序要長(zhǎng) 半以上，運(yùn)行時(shí)間也要長(zhǎng)一些。 因此，在很多對(duì)時(shí)間要求比較高的系統(tǒng)，如某些實(shí)時(shí)控制系統(tǒng)或者大型計(jì)算機(jī)控制系統(tǒng)中，低級(jí)語(yǔ)言，主要是匯編語(yǔ)言，仍然得到了一定的應(yīng)用。 高級(jí)語(yǔ)言的基本內(nèi)容 高級(jí)程序設(shè)計(jì)語(yǔ)言依賴于各自特定的語(yǔ)句和語(yǔ)法。一條一條的語(yǔ)句是構(gòu)成源程序的基本單位。高級(jí)語(yǔ)言的一條語(yǔ)句被編譯或解釋時(shí)往往會(huì)對(duì)應(yīng)多條機(jī)器指令。 每一種編程語(yǔ)言都包含一組語(yǔ)句和語(yǔ)法。所謂語(yǔ)法，是指管理語(yǔ)言結(jié)構(gòu)和語(yǔ)句的一組規(guī)則。不論使用何種設(shè)計(jì)語(yǔ)言，都必須遵循其語(yǔ)法規(guī)則。 以下內(nèi)容主要描述了大多數(shù)高級(jí)語(yǔ)言都共同具備的特性，但不一定是所有高級(jí)語(yǔ)言都有的。 1高級(jí)語(yǔ)言的基本符號(hào) 高級(jí)語(yǔ)言都是由所謂的基本符號(hào)組成的?；痉?hào)可以分為單字符和多字符兩種情況。單字符基本符號(hào)由單個(gè)字符組成，在高級(jí)語(yǔ)言中通常都有下列幾種單字符基本符號(hào)： (1) 字母 大寫(xiě)英文字母 A Z，小寫(xiě)英文字母 a z，共 52個(gè)符號(hào)。 (2) 數(shù)字 0 9，共 10個(gè)數(shù)字符號(hào)。 (3)特殊字符 (加 )， (減 )， *(乘 )， /(除 )， (乘方 )，(等號(hào) )， (左括號(hào) )， )(右括號(hào) )， (大于 )，(小于 )， (逗號(hào) )， (空格 )等。 在高級(jí)語(yǔ)言中的多字符基本符號(hào)由兩個(gè)或兩個(gè)以上的字符組成，例如 移 )、 (小于或等于 )、 )等等。 2高級(jí)語(yǔ)言的基本元素 基本元素由基本符號(hào)組成，可分為數(shù)、邏輯值、名字、標(biāo)號(hào)和字符串等五大類。 (1) 數(shù) 它由 0 9共 10個(gè)基本數(shù)字和其他一些符號(hào) (如小數(shù)點(diǎn)“ .”、正負(fù)號(hào)“、”及指數(shù)符號(hào)“ E”等所構(gòu)成。 (2) 邏輯值 由真 (假 (個(gè)值表示。 (3) 名字 由字符組成，一般約定名字的開(kāi)頭是字母或者下劃線，其后可為字母或數(shù)字，如 _字可用來(lái)定義常量、變量、函數(shù)、過(guò)程或子程序的，也被用來(lái)定義成某些東西，故也稱為標(biāo)識(shí)符。在高級(jí)語(yǔ)言中，一般還規(guī)定了組成名字的字符的長(zhǎng)度，即字符個(gè)數(shù)。 (4) 標(biāo)號(hào) 是在高級(jí)語(yǔ)言中的程序語(yǔ)句前所加的一個(gè)名字，主要用來(lái)指示程序可能的轉(zhuǎn)移方向。 (5) 字符串 由一串字符所組成。在不同的高級(jí)語(yǔ)言中，字符串中的多個(gè)字符放在一對(duì)單引號(hào)或雙引號(hào)中。 3基本的數(shù)據(jù)類型 任何一種高級(jí)語(yǔ)言都會(huì)定義一些基本的數(shù)據(jù)類型?；镜臄?shù)據(jù)類型通常包括整數(shù)數(shù)據(jù)類型、實(shí)數(shù)數(shù)據(jù)類型和字符數(shù)據(jù)類型等。 在程序中，除了值無(wú)需改變的常數(shù)外，大部分?jǐn)?shù)據(jù)的值是可以修改的。在程序中，變量是指代表某個(gè)具體數(shù)值，并且所代表的數(shù)值可改變的一個(gè)符號(hào)名字。 變量必須先定義，然后才能使用，這是 條基本原則。 變量實(shí)質(zhì)上代表了一個(gè)特定大小的內(nèi)存單元空間。 定義變量的實(shí)質(zhì)就是讓程序?yàn)樵撟兞糠峙湟粋€(gè)特定的內(nèi)存空間。 變量的類型實(shí)質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間的大小，即分配給該變量代表的數(shù)據(jù)的所占據(jù)的內(nèi)存單元的字節(jié)數(shù)目。 4結(jié)構(gòu)數(shù)據(jù)類型 是在基本數(shù)據(jù)類型的基礎(chǔ)上構(gòu)造出來(lái)的數(shù)據(jù)類型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級(jí)語(yǔ)言都支持的兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。 (1) 數(shù)組類型 數(shù)組是若干個(gè)相同類型的數(shù)據(jù)的集合。 (2) 用戶自定義的結(jié)構(gòu)體類型 結(jié)構(gòu)體是隸屬于同一個(gè)事物的多個(gè)不同類型的數(shù)據(jù)的集合，用來(lái)表示具有若干個(gè)屬性的一個(gè)事物。 除了以上兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型外，許多高級(jí)語(yǔ)言還有比如枚舉、集合，以及更復(fù)雜的隊(duì)列、堆棧等多種數(shù)據(jù)類型。 結(jié)構(gòu)數(shù)據(jù)類型在使用時(shí)也必須定義相應(yīng)類型的“變量”名字。 5運(yùn)算符與表達(dá)式 表達(dá)式是由基本符號(hào)、基本元素和各種數(shù)據(jù)通過(guò)各種運(yùn)算符連接而成的。按表達(dá)式的運(yùn)算結(jié)果可以分為算術(shù)表達(dá)式、邏輯表達(dá)式和字符串表達(dá)式等幾種情況。 高級(jí)語(yǔ)言中的運(yùn)算符大致包括以下幾個(gè)方面： (1) 邏輯運(yùn)算： 與、或、非、異或。 (2) 算術(shù)運(yùn)算： 加、減、乘、除、取模。 (3) 數(shù)據(jù)比較： 大于、小于、等于、不等于。 (4) 數(shù)據(jù)傳送； 輸入、輸出、賦值。 (5) 算術(shù)表達(dá)式： 該表達(dá)式的運(yùn)算結(jié)果是數(shù)，它非常近似于日常的數(shù)學(xué)公式。 (6) 關(guān)系運(yùn)算表達(dá)式： 該表達(dá)式的運(yùn)算結(jié)果是邏輯值，常用的運(yùn)算符包含 (大于 )、 (小于 )、 (等于 )、 (小于等于 )、 (大于等于 )、不等于。 (7) 字符串表達(dá)式： 該表達(dá)式的運(yùn)算結(jié)果是字符串。 6語(yǔ)句 語(yǔ)句是構(gòu)成高級(jí)語(yǔ)言源程序的基本單位，是由基本元素、運(yùn)算符、表達(dá)式等組成。任何一種高級(jí)語(yǔ)言往往都支持賦值、條件判斷、循環(huán)、輸入輸出等語(yǔ)句。程序員利用這些語(yǔ)句的結(jié)合，能夠很方便地編制出功能強(qiáng)大的程序。 7庫(kù)函數(shù)和用戶自定義的函數(shù) 為了支持用戶編寫(xiě)出功能強(qiáng)大的源程序，幾乎所有的高級(jí)語(yǔ)言都為用戶提供了豐富的庫(kù)函數(shù)，這些庫(kù)函數(shù)能夠?qū)崿F(xiàn)某些特定的功能，比如計(jì)算一個(gè)比較復(fù)雜的數(shù)學(xué)函數(shù)。 在源程序中，用戶也可以自己定義自己的函數(shù) (子程序或過(guò)程 )，以便以后可以反復(fù)調(diào)用這些代碼集合。 8注釋 任何一種程序設(shè)計(jì)語(yǔ)言都強(qiáng)調(diào)注釋的重要性。源程序所包含的代碼往往比較冗長(zhǎng)，添加必要的注釋不僅有助于閱讀程序，更重要的是，在需要對(duì)程序功能進(jìn)行擴(kuò)充時(shí)，注釋可以極大地幫助程序員對(duì)原始程序的理解。 經(jīng)常會(huì)出現(xiàn)這樣一種情況，程序員自己編寫(xiě)的程序，經(jīng)過(guò)一段時(shí)間后，可能就是半年或者幾個(gè)月以后，程序員自己也讀不懂自己的程序了。況且，程序不僅要自己看得懂，更重要的是也要讓別人能夠看懂。 9程序設(shè)計(jì)風(fēng)格 (1) 編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。 (2) 程序中應(yīng)給出必要的注釋，尤其在變量定義、調(diào)用接口、參數(shù)傳遞處，在修改程序時(shí)應(yīng)注明修改人、時(shí)間、簡(jiǎn)要的修改原因。 (3) 對(duì)變量、函數(shù)標(biāo)識(shí)等的命名，采用規(guī)范的命名方法，避免含義不明確的縮寫(xiě)，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含義和數(shù)據(jù)類型。 (4) 采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。 (5) 每一行只寫(xiě)一條語(yǔ)句，使用括號(hào)間隔表達(dá)式或語(yǔ)句的組成部分，使組成部分清晰； (6) 使用結(jié)構(gòu)化、面向?qū)ο蟮木幊碳夹g(shù)，提高程序可重用性、可擴(kuò)充性。 (7) 除非完全必要，應(yīng)盡量避免多任務(wù)和多重處理。 (8) 盡量避免使用復(fù)雜的算術(shù)和邏輯表達(dá)式。 (9) 提高程序健壯性，預(yù)防用戶的操作錯(cuò)誤，做到廢進(jìn)廢出。 10高級(jí)語(yǔ)言程序的運(yùn)行 使用高級(jí)語(yǔ)言編制程序的一般過(guò)程可以歸納為以下幾個(gè)步驟： (1) 使用文本編輯工具，逐條編寫(xiě)源程序的語(yǔ)句。存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的高級(jí)語(yǔ)言有關(guān)。 (2) 編譯源程序文件，生成目標(biāo)文件，文件后綴名通常為 (3) 鏈接目標(biāo)文件，生成可執(zhí)行文件，文件后綴名通常為 (4) 在計(jì)算機(jī)上執(zhí)行可執(zhí)行程序文件，進(jìn) 步調(diào)試和維護(hù)。 結(jié)構(gòu)化程序設(shè)計(jì)方法 采用 自頂向下、逐步求精 的設(shè)計(jì)方法和單入口單出口的控制結(jié)構(gòu)。 1. 結(jié)構(gòu)化程序設(shè)計(jì)思想 . . . . . . 二級(jí)子問(wèn)題 二級(jí)子問(wèn)題 二級(jí)子問(wèn)題 需要解決的復(fù)雜問(wèn)題 三級(jí)子問(wèn)題 三級(jí)子問(wèn)題 三級(jí)子問(wèn)題 . . . . . . . . . 最小問(wèn)題 最小問(wèn)題 最小問(wèn)題 結(jié)構(gòu)化程序設(shè)計(jì)的 原則 是： (1) 使用順序、選擇、循環(huán) 3種基本控制結(jié)構(gòu)表示程序邏輯。 (2)程序語(yǔ)句組織成容易識(shí)別的語(yǔ)句模塊，每個(gè)模塊都是單入口、單出口。 (3)嚴(yán)格控制 (a) 順序結(jié)構(gòu) (b) 選擇結(jié)構(gòu) (c) (d) A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假 真 入口 A S 2模塊 一個(gè)復(fù)雜的問(wèn)題可以劃分為多個(gè)簡(jiǎn)單問(wèn)題的組合。 在自頂向下、逐步細(xì)化的過(guò)程中，把復(fù)雜問(wèn)題分解成一個(gè)個(gè)簡(jiǎn)單問(wèn)題的最基本方法就是模塊化。 模塊化便于問(wèn)題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實(shí)現(xiàn)。 1面向?qū)ο蟮乃枷?向?qū)ο蟮某绦蛟O(shè)計(jì)方法 向?qū)ο?)的程序設(shè)計(jì)把客觀事物看作具有屬性和行為的對(duì)象，通過(guò)抽象找出同一類對(duì)象的共同屬性 (靜態(tài)特征 )和行為 (動(dòng)態(tài)特征 )，形成類。 2對(duì)象和類 對(duì)象 是對(duì)現(xiàn)實(shí)問(wèn)題的高度概括、分類和抽象。每個(gè)對(duì)象都只有自己的數(shù)據(jù)和相應(yīng)的處理函數(shù)，整個(gè)程序是由一系列相互作用的對(duì)象來(lái)構(gòu)成，不同對(duì)象之間是通過(guò)發(fā)送消息來(lái)實(shí)現(xiàn)相互聯(lián)系、相互作用。 方法 在對(duì)象內(nèi)的操作通常叫做方法。 類 定義了一組大體上相似的對(duì)象。一個(gè)類所包含的方法和數(shù)據(jù)描述一組對(duì)象的共同行為和屬性。 對(duì)象則是類的具體化，是類的實(shí)例。 類通過(guò)派生可以有子類，同樣也可以有父類，形成層次結(jié)構(gòu)。 3抽象 抽象 是對(duì)具體事物 (即對(duì)象 )進(jìn)行概括，即忽略事物的非本質(zhì)特征，只注意那些與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而抽象出一類對(duì)象的共性并加以描述。 對(duì)一個(gè)問(wèn)題的抽象一般來(lái)講應(yīng)該包括兩個(gè)方面：數(shù)據(jù)抽象和代碼抽象 (或稱為行為抽象 )。 4封裝性 封裝的兩個(gè)含義 ： 第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結(jié)合，形成一個(gè)不可分割的整體，即對(duì)象，這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。 第二個(gè)含義稱為信息隱蔽，即盡可能隱蔽對(duì)象的內(nèi)部細(xì)節(jié)。在隱蔽對(duì)象內(nèi)部細(xì)節(jié)的同時(shí)，對(duì)象需要提供與外部世界進(jìn)行交流的接口，并實(shí)現(xiàn)對(duì)數(shù)據(jù)訪問(wèn)權(quán)限的合理控制，把整個(gè)程序中不同部分的相互影響減少到最低限度。 5繼承性 繼承性 是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制。在定義一個(gè)類的時(shí)候，可以以一個(gè)已經(jīng)存在的類為基礎(chǔ)，并把這個(gè)已經(jīng)存在的類所包含的屬性和方法作為自身的一部分，然后加入新的屬性和方法以區(qū)別于原來(lái)的類。 原有的類稱為 基類或父類 ，產(chǎn)生的新類稱為 派生類 。 6多態(tài)性 多態(tài)性 在收到外部消息時(shí)，對(duì)象通常要予以響應(yīng)。不同的對(duì)象收到同一消息可能產(chǎn)生完全不同的結(jié)果。 1數(shù)據(jù)、數(shù)據(jù)類型 數(shù)據(jù) 是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)系統(tǒng)內(nèi)，數(shù)據(jù)通常是指能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)進(jìn)行處理的符號(hào)的集合。 數(shù)據(jù)類型 是指具有相同取值范圍和可以實(shí)施同種操作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計(jì)中，通常會(huì)有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。 基本概念 數(shù)據(jù)結(jié)構(gòu) 2數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象 能夠獨(dú)立并完整地描述客觀世界實(shí)體的基本數(shù)據(jù)單元稱為 數(shù)據(jù)元素 ，它是組成數(shù)據(jù)的基本單位。 數(shù)據(jù)項(xiàng) 是組成數(shù)據(jù)元素的不可分割的最小單位。最簡(jiǎn)單的數(shù)據(jù)元素就是由一個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的。 同類數(shù)據(jù)元素的集合稱為 數(shù)據(jù)對(duì)象 。 3數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的關(guān)系組成不同的數(shù)據(jù)結(jié)構(gòu)。 線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間存在著前后順序的關(guān)系，即除了第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素外，其他每個(gè)元素都有惟一的一個(gè)前驅(qū)和一個(gè)后繼元素，這樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。 樹(shù)形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且除了一個(gè)被稱為根節(jié)點(diǎn)的元素外，每個(gè)元素都有一個(gè)前驅(qū)節(jié)點(diǎn)，并且可以有多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為樹(shù)形結(jié)構(gòu)。 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果任何一個(gè)數(shù)據(jù)元素都可以有多個(gè)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。 (2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)不僅要存儲(chǔ)數(shù)據(jù)本身，還要存儲(chǔ)表示數(shù)據(jù)間的邏輯關(guān)系。 數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。 順序結(jié)構(gòu) 把所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是必須預(yù)先分析出所需定義數(shù)組的大小。 鏈表結(jié)構(gòu) 對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針域來(lái)實(shí)現(xiàn)，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針來(lái)實(shí)現(xiàn)。 索引結(jié)構(gòu) 針對(duì)每個(gè)數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，每個(gè)表項(xiàng)包含一個(gè)能夠惟一識(shí)別一個(gè)元素的關(guān)鍵字和用以指示該元素的地址指針。 散列結(jié)構(gòu) 通過(guò)構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來(lái)確定元素存放的地址。 (3) 數(shù)據(jù)運(yùn)算 數(shù)據(jù)操作的集合。常見(jiàn)的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計(jì)算機(jī)程序加以實(shí)現(xiàn)，通常也叫 算法實(shí)現(xiàn) 。 線性表 1定義 線性表 是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，元素之間是一對(duì)一的線性關(guān)系，除了第一個(gè)元素只有直接后繼、最后一個(gè)元素只有直接前驅(qū)外，其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖。 元素 1 u a n s u 元素 2 1 元素 3 1 元素 n 1 2運(yùn)算和實(shí)現(xiàn) 線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：插入、刪除、查詢和遍歷。 插入 在保持原有的存儲(chǔ)結(jié)構(gòu)的前提下，根據(jù)插入要求，在適當(dāng)?shù)奈恢貌迦胍粋€(gè)元素。插入操作要求線性表要有足夠的存放新元素的空間，如果空間不足，插入操作無(wú)法進(jìn)行，線性表會(huì)溢出。 刪除 在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會(huì)失敗。 查詢 在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過(guò)程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)元素中的關(guān)鍵字進(jìn)行。實(shí)際上，數(shù)據(jù)的插入和刪除都需要首先定位數(shù)據(jù)元素。對(duì)于空的線性表是無(wú)法查詢的。 遍歷 是指按照某種方式，逐一訪問(wèn)線性表中的每一個(gè)數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫(xiě)、或查詢等。 棧 1定義 對(duì)于由 果只允許在其固定的一端位置插入和刪除一個(gè)數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為 堆?；驐?( 允許插入或刪除的這一端稱為 棧項(xiàng) ，另一個(gè)固定端稱為 棧底 。當(dāng)表中沒(méi)有元素時(shí)稱為 空棧 。 2運(yùn)算和實(shí)現(xiàn) 棧的基本運(yùn)算主要有：入棧、出棧和判斷。 入棧 入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。 出棧 出棧也叫退?；驈棗?，是將棧頂元素從棧中退出并傳遞給用戶程序的操作 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ù)是否為空，返回結(jié)果是一個(gè)邏輯值：真或假。如果棧頂和棧底重合，說(shuō)明堆棧為空。 隊(duì)列 1定義 對(duì)于由 果在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為 隊(duì)列 ( 把允許插入的一端叫 隊(duì)尾 (把只允許刪除的一端叫 隊(duì)首 ( 2運(yùn)算 隊(duì)列的基本運(yùn)算主要有：入隊(duì)、出隊(duì)和判斷。 入隊(duì) 入隊(duì)是在隊(duì)列中插入一個(gè)新數(shù)據(jù)元素的過(guò)程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾，。 出隊(duì) 出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過(guò)程，刪除在隊(duì)首進(jìn)行并把出來(lái)的數(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ì) 判斷： 判斷操作用來(lái)檢查隊(duì)列是否為空，返回結(jié)果是一個(gè)邏輯值：真或假，如圖。 頭指針 尾指針 3循環(huán)隊(duì)列的實(shí)現(xiàn) F G A B C D E 頭指針 尾指針 內(nèi)存塊第一個(gè)存儲(chǔ)單元 內(nèi)存塊最后一個(gè)存儲(chǔ)單元 隊(duì)列移動(dòng) 樹(shù) 1定義 樹(shù)形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為是一個(gè)節(jié)點(diǎn)，除了一個(gè)惟一的所謂 根節(jié)點(diǎn) 外，其他每個(gè)節(jié)點(diǎn)都有且只有一個(gè)父節(jié)點(diǎn)，每個(gè)元素可以有多個(gè)子節(jié)點(diǎn)。 樹(shù)主要用在大型、動(dòng)態(tài)列表的搜索，人工智能系統(tǒng)和編碼算法等問(wèn)題中。 2運(yùn)算 樹(shù)常見(jiàn)的基本運(yùn)算有：插入、刪除和遍歷。 插入 在樹(shù)中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹(shù)本身所具有的性質(zhì)。 刪除 在樹(shù)中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)點(diǎn)后，也要保持該樹(shù)本身所具有的性質(zhì)。 遍歷 按照某種順序或規(guī)則，對(duì)樹(shù)中的每個(gè)節(jié)點(diǎn)逐一進(jìn)行訪問(wèn)的過(guò)程。 3實(shí)現(xiàn) A B C D E F 圖 1定義 在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來(lái)表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。 圖可以用來(lái)描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中獲得最小生成樹(shù)。除此以外，圖在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。 2運(yùn)算 常見(jiàn)的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添加邊、刪除邊和遍歷圖。 添加頂點(diǎn) 在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常是孤立的節(jié)點(diǎn)，還沒(méi)有邊連接。 刪除頂點(diǎn) 在圖中去掉一個(gè)頂點(diǎn)，顯然，在去掉一個(gè)頂點(diǎn)的同時(shí)還應(yīng)該刪除與該頂點(diǎn)所連接的邊。 添加邊 根據(jù)指定的頂點(diǎn)，添加相應(yīng)的邊。 刪除邊 根據(jù)指定的頂點(diǎn)，刪除相應(yīng)的邊。 遍歷圖 按照一定的規(guī)則，對(duì)圖中的每個(gè)數(shù)據(jù)頂點(diǎn)逐一進(jìn)行訪問(wèn)。 3實(shí)現(xiàn) 圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實(shí)現(xiàn)。對(duì)于各個(gè)頂點(diǎn)和頂點(diǎn)之間的關(guā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 ) 概述 1算法的定義 準(zhǔn)確地說(shuō)，“ 算法 (一組明確的、可以執(zhí)行的步驟的有序集合，它在有限的時(shí)間內(nèi)終止并產(chǎn)生結(jié)果”。 算法和數(shù)據(jù)結(jié)構(gòu)之間存在密切聯(lián)系。數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)的不同，通常的采用的算法也會(huì)不同；當(dāng)問(wèn)題的求解算法一旦確定，也可以選擇合適的數(shù)據(jù)結(jié)構(gòu)加以實(shí)現(xiàn)，合理的數(shù)據(jù)結(jié)構(gòu)能夠簡(jiǎn)化算法。 算法分析基礎(chǔ) (1) 有窮性 (可終止性 ) 一個(gè)算法必須在有限個(gè)操作步驟內(nèi)以及合理的時(shí)間內(nèi)執(zhí)行完成。 (2) 確定性 算法中的每一個(gè)操作步驟都必須有明確的含義，不允許存在二義性。 (3) 有效性 (可執(zhí)行性 ) 算法中描述的操作步驟都是可執(zhí)行的，并能最終得到確定的結(jié)果。 (4) 輸入及輸出 一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入數(shù)據(jù)、有 1個(gè)或多個(gè)輸出數(shù)據(jù)。 2算法的特性 3算法的描述 (1) 自然語(yǔ)言表示 自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是中文、英文等。 例如，求三個(gè)數(shù)中最大值的問(wèn)題，可以描述為： 比較前兩個(gè)數(shù)； 將中較大的數(shù)與第三個(gè)數(shù)進(jìn)行比較； 步驟中較大的數(shù)即為所求。 (2) 流程圖表示 流程圖是用規(guī)定的一組圖形符號(hào)、流程線和文字說(shuō)明來(lái)表示算法的一種表示方法。 (3) 偽碼 偽碼用一種介于自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。比計(jì)算機(jī)語(yǔ)言形式靈活，格式緊湊，沒(méi)有嚴(yán)格的語(yǔ)法。 (4) 程序設(shè)計(jì)語(yǔ)言形式 算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)表示，如， C、 C+、 例如，求兩個(gè)數(shù)的較大者。用偽代碼描述算法如下： s:a,b 1. a is or to b) a b 常用算法介紹 1遞歸算法 如果一個(gè)過(guò)程直接或間接地調(diào)用它本身，則稱該過(guò)程是遞歸的。 例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法定義函數(shù) f (n)如下： 1!( 1 ) ! 遞歸的情況包括所謂的遞推法和分治法。 遞推 是從已知的初始條件出發(fā)，逐次推導(dǎo)出最后所求的值。遞推是利用問(wèn)題本身所具有的一種遞推關(guān)系求解問(wèn)題的一種方法。 分治法 也是一種廣泛使用的算法設(shè)計(jì)方法。其基本思想是把大問(wèn)題分解成一些較小的問(wèn)題。然后由小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解。 2迭代算法 所謂迭代是指重復(fù)執(zhí)行一組指令或操作步驟，在每次執(zhí)行這組指令時(shí)，都從原來(lái)的解值的基礎(chǔ)上推出一個(gè)新的解值。新的解值比原來(lái)的解值更加接近真實(shí)的解。這個(gè)過(guò)程不斷重復(fù)，直到計(jì)算得到的解與真實(shí)解的誤差滿足實(shí)際要求。 迭代常常用于科學(xué)計(jì)算領(lǐng)域?qū)δ承o(wú)法直接求解的數(shù)值問(wèn)題。 例如：現(xiàn)欲求解方程 f(x)=0的解。首先用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式 x=g(x)，然后按以下步驟執(zhí)行： (1)選一個(gè)方程的近似根，賦給變量 (2)將 后計(jì)算 g(并將結(jié)果存于變量 (3)若 復(fù)步驟 (2)的計(jì)算。 如果方程有解，并且按照上述方法計(jì)算出來(lái)的近似根序列數(shù)學(xué)上收斂，則按上述方法求得的 3窮舉算法 亦稱枚舉法，該算法首先根據(jù)問(wèn)題的部分條件確定問(wèn)題解的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況逐一進(jìn)行驗(yàn)證，直到全部情況驗(yàn)證完畢。 4貪婪算法 貪婪算法通常具有 貪婪選擇性 和 最優(yōu)子結(jié)構(gòu)性 。 貪婪選擇性 指的是所求解問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪婪選擇來(lái)達(dá)到。 最優(yōu)子結(jié)構(gòu)性 指的是一個(gè)問(wèn)題的最優(yōu)解往往包含著它的子問(wèn)題的最優(yōu)解。 現(xiàn)在我們假設(shè)顧客同樣希望找回總額為 16的硬幣。但是銀行發(fā)行的硬幣面額是分別變成了 1、5和 12單位的硬幣。按照上述的貪婪法，應(yīng)該選擇 1枚面額 12的硬幣，然后選擇 4枚面額為 1的硬幣，硬幣總數(shù)為 5。而最優(yōu)解應(yīng)該是選擇 3枚面額為 5的硬幣，然后選擇 1枚面額為 1的硬幣，總數(shù)為 4。此時(shí)，貪婪法的結(jié)果就不等于最優(yōu)解了。 算法的評(píng)價(jià) 對(duì)于一個(gè)算法的評(píng)價(jià)，通常要從 正確性、可理解性、健壯性、時(shí)間復(fù)雜性及空間復(fù)雜性 等多個(gè)方面加以衡量。相比而言，人們更關(guān)心的是與計(jì)算機(jī)系統(tǒng)資源密切相關(guān)的時(shí)間復(fù)雜性和空間復(fù)雜性。 在計(jì)算機(jī)系統(tǒng)內(nèi)，求解問(wèn)題的算法耗費(fèi)的資源主要包括時(shí)間和空間，可以從分析算法的時(shí)間開(kāi)銷和空間開(kāi)銷入手，來(lái)分析算法的時(shí)間復(fù)雜性及空間復(fù)雜性。 1算法的時(shí)間復(fù)雜度 時(shí)間復(fù)雜度 (度量時(shí)間復(fù)雜性、即算法的時(shí)間效率的指標(biāo)。時(shí)間復(fù)雜度是與求解問(wèn)題規(guī)模、算法輸入相關(guān)的函數(shù)，該函數(shù)表示算法運(yùn)行所花費(fèi)的時(shí)間。 為了簡(jiǎn)化問(wèn)題，通常，用算法運(yùn)行某段核心代碼的 次數(shù) 來(lái)代替準(zhǔn)確的執(zhí)行時(shí)間，記為 T(n)，其中， 般是指待處理的數(shù)據(jù)量的大小。 引入符號(hào)“ O”，以此簡(jiǎn)化時(shí)間復(fù)雜度 T(n)與求解問(wèn)題規(guī)模 化后的關(guān)系是一種數(shù)量級(jí)關(guān)系。 時(shí)間復(fù)雜度最好的算法是常數(shù)數(shù)量級(jí)的算法。常數(shù)數(shù)量級(jí)的算法表示為 O (c)，其中 例如，如果某個(gè)算法的時(shí)間復(fù)雜度為 T(n)=n，那么，當(dāng)求解規(guī)模趨于 T(n)/ ，表示算法的時(shí)間復(fù)雜度與 為T(mén)(n)=O( 多項(xiàng)式函數(shù)的時(shí)間復(fù)雜度有 O (n)， O ( O ( O (等，以及數(shù)量級(jí)介于上述數(shù)量級(jí)之間的 O ( O (n* O (n2*等。 2算法的空間復(fù)雜度 算法的 空間復(fù)雜度 (用來(lái)度量算法的空間復(fù)雜性、即執(zhí)行算法的程序在計(jì)算機(jī)中運(yùn)行時(shí)所占用空間的大小。 簡(jiǎn)單講，空間復(fù)雜度也是與求解問(wèn)題規(guī)模、算法輸入相關(guān)的函數(shù)。記為 S(n)，其中 符號(hào)“ O”同樣被用來(lái)表示空間復(fù)雜度 S(n)與求解問(wèn)題規(guī)模 例如，如果 S(n)= O(表示算法的空間復(fù)雜度與 為 S(n)=O( 空間復(fù)雜度的分析方法與時(shí)間復(fù)雜度的分析也是類似的，往往希望算法有常數(shù)數(shù)量級(jí)或多項(xiàng)式數(shù)量級(jí)的空間復(fù)雜度。 題，是非確定型多項(xiàng)式問(wèn)題。所謂的非確定型，簡(jiǎn)單講就是指算法無(wú)法直接計(jì)算出結(jié)果，只能通過(guò)進(jìn)行一些有選擇的“猜算”來(lái)得到結(jié)果。 對(duì)于這類問(wèn)題給出的算法并不能直接計(jì)算出結(jié)果，但可以檢驗(yàn)?zāi)硞€(gè)可能的結(jié)果是正確的還是錯(cuò)誤的。這個(gè)可以檢驗(yàn)“猜算”的答案正確與否的算法，如果可以在多項(xiàng)式時(shí)間內(nèi)解出，就是非確定型多項(xiàng)式 (題。 例如，找一個(gè)大的質(zhì)數(shù)的問(wèn)題。并不存在一個(gè)公式可以用來(lái)推算并找到這個(gè)大的質(zhì)數(shù)，但是，如果事先給定一個(gè)數(shù)，程序卻可以在多項(xiàng)式時(shí)間內(nèi)判斷出它是否滿足要求。 檢驗(yàn)一個(gè)問(wèn)題是否屬于 果在多項(xiàng)式時(shí)間內(nèi)能夠證明該問(wèn)題的任意“是”的實(shí)例是正確的，則該問(wèn)題即為 目前關(guān)于 為典型的有裝箱問(wèn)題、背包問(wèn)題、著色問(wèn)題等等。 這些問(wèn)題的研究結(jié)果有兩種可能，一種是找到了求解問(wèn)題的算法；另外一種就是求解問(wèn)題的算法是不存在的，那么就要從數(shù)學(xué)理論上證明它為什么不存在。 編譯程序概述 語(yǔ)言處理的過(guò)程如圖所示。 編譯原理 匯編器 絕對(duì)機(jī)器碼 裝配連接編輯 編譯器 目標(biāo)匯編程序 可重定位機(jī)器代碼 預(yù)處理器 骨架程序 源程序 可重定位目標(biāo)文件庫(kù) 編譯程序的功能如圖所示。 編譯程序 低級(jí)語(yǔ)言程序 高級(jí)語(yǔ)言程序 解釋程序在處理源程序時(shí)，執(zhí)行方式類似于日常生活中的“同聲翻譯”。 解釋一句、執(zhí)行一句，立即產(chǎn)生運(yùn)行結(jié)果。解釋程序不產(chǎn)生目標(biāo)代碼，不能脫離其語(yǔ)言環(huán)境獨(dú)立執(zhí)行。 解釋程序?qū)υ闯绦虻慕忉寛?zhí)行比編譯程序產(chǎn)生的目標(biāo)代碼程序的執(zhí)行速度要慢。 編譯程序是把高級(jí)語(yǔ)言程序 (源程序 )作為一個(gè)整體來(lái)處理，首先將程序源代碼“翻譯”成目標(biāo)代碼 (機(jī)器語(yǔ)言 )，編譯后與系統(tǒng)提供的代碼庫(kù)鏈接，形成 個(gè)完整的可執(zhí)行的機(jī)器語(yǔ)言程序 (目標(biāo)程序代碼 )。 目標(biāo)程序可以脫離其語(yǔ)言環(huán)境獨(dú)立執(zhí)行，使用比較方便、效率較高。相應(yīng)地，由于每次執(zhí)行之前必須通過(guò)編譯得到可執(zhí)行程序，所以，可執(zhí)行程序一旦需要修改，必須先修改源代碼，再重新編譯生成新的目標(biāo)文件 (*能執(zhí)行。 詞法分析器語(yǔ)法分析器語(yǔ)義分析器中間代碼生成優(yōu)化目標(biāo)代碼生成源程序 目標(biāo)代碼 表格管理 出錯(cuò)處理 詞法分析 其任務(wù)是從左到右一個(gè)字符、一個(gè)字符地對(duì)源程序進(jìn)行掃描，讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，通過(guò)詞法分析從而識(shí)別出一個(gè)個(gè)單詞 (也稱單詞符號(hào)或符號(hào) )。 例 對(duì)表達(dá)式： = 100；進(jìn)行詞法分析。 對(duì)其進(jìn)行詞法分析后得到以下結(jié)果： 單詞類型 單詞值 標(biāo)識(shí)符 1( 算符 (賦值 ) := 標(biāo)識(shí)符 2( 算符 (加 ) + 標(biāo)識(shí)符 3( 算符 (乘 ) * 整數(shù) 100 分號(hào) ； 語(yǔ)法分析 語(yǔ)法分析是編譯過(guò)程的第二個(gè)階段，任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語(yǔ)法短語(yǔ)，如“程序”、“語(yǔ)句”、“表達(dá)式”等等。一般這種語(yǔ)法短語(yǔ)也稱為語(yǔ)法單位。 例 按照例 表達(dá)式： = 100；進(jìn)行語(yǔ)法分析。 語(yǔ)法規(guī)則： :=“:=” :=“+” :=“*” :=“(”