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

第六章程序設(shè)計(jì)與

算法分析

本章要點(diǎn)

.初否解麗昌設(shè)計(jì)的而出矢口也

?掌握結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)的基本方

法

?掌握數(shù)據(jù)結(jié)構(gòu)中的基本數(shù)據(jù)類型及其實(shí)現(xiàn)

?掌握程序設(shè)計(jì)算法的基本思想及幾種經(jīng)典的算法J

?了解編譯原理的基本知識(shí)

6.1程序設(shè)計(jì)基石

6.1.1程序的概念

■程序就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的

集合。

?程序設(shè)計(jì)是程序員編寫一系列可存儲(chǔ)的指令以

指示計(jì)算機(jī)完成某些工作的過(guò)程。這些指令用

程序設(shè)計(jì)語(yǔ)言寫成。

?程序設(shè)計(jì)語(yǔ)言是一組專門設(shè)計(jì)的用來(lái)生成一系

列可被計(jì)算機(jī)處理和執(zhí)行的指令的符號(hào)集合。

?程序設(shè)計(jì)人員用程序設(shè)計(jì)語(yǔ)言寫成的指令稱作

代碼。

?分類：

低級(jí)語(yǔ)言、高級(jí)語(yǔ)言。.

1）低級(jí)語(yǔ)言包括兩種類型：機(jī)器語(yǔ)言和匯

編語(yǔ)言O(shè)

機(jī)器語(yǔ)言

?機(jī)器語(yǔ)言面向機(jī)器，可以由CPU直接識(shí)

別和執(zhí)行。

?不同的機(jī)器能夠識(shí)別的機(jī)器語(yǔ)言是不相

同的。

?機(jī)器語(yǔ)言指令都是用一串0、1構(gòu)成的二

進(jìn)制位串來(lái)表示的。

■指令系統(tǒng)是機(jī)器提供的機(jī)器指令的集合。

?用二進(jìn)制編碼表示的指令，稱為機(jī)器指

令，或稱為機(jī)器碼。

?用機(jī)器指令編寫的程序稱為機(jī)器語(yǔ)言程

序，或稱為目標(biāo)程序，這是計(jì)算機(jī)能夠

直接執(zhí)行的程序。

■機(jī)器語(yǔ)言難以閱讀和理解，編寫和修改

都比較困難，而且通用性較差。

匯編語(yǔ)言

?匯編語(yǔ)言也稱符號(hào)語(yǔ)言。

?指令助記符是指令英文名稱的縮寫，容

易記憶。

?所謂匯編語(yǔ)言，就是采用字母、數(shù)字和

符號(hào)來(lái)代替由一個(gè)個(gè)0和I構(gòu)成的指令操

作碼、寄存器、數(shù)據(jù)和存儲(chǔ)地址等，并

在程序中用它們代替二進(jìn)制編碼數(shù)，這

樣編寫出來(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ú)需翻

譯或編譯，CPU能夠直接識(shí)別和執(zhí)行。

而匯編語(yǔ)言必須經(jīng)過(guò)匯編才能得到目標(biāo)

程序。

匯編

?雖然匯編語(yǔ)言比機(jī)器語(yǔ)言容易閱讀理解和便于

檢查，所以仍然需要一種特殊的程序，該程序

能夠?qū)⒂脜R編語(yǔ)言編寫的程序“翻譯”成CPU

能夠識(shí)別的機(jī)器語(yǔ)言。

?實(shí)現(xiàn)這種翻譯功能的特殊程序稱為匯編語(yǔ)言翻

譯程序、匯編程序或匯編器。程序員手工編寫

的程序統(tǒng)稱為源程序，用匯編語(yǔ)言編寫的源程

序稱為匯編語(yǔ)言源程序，匯編程序?qū)⒃闯绦蚍?/p>

譯得到的機(jī)器語(yǔ)言程序稱為目標(biāo)程序，翻譯的

過(guò)程稱為匯編。

反匯編程序用于將目標(biāo)代碼程序轉(zhuǎn)換成相

應(yīng)的匯編語(yǔ)言源程序，這一過(guò)程稱為反

匯編。反匯編主要用于識(shí)別源程序代碼,

常用的調(diào)試工具程序DEBUG就提供了反

匯編功能。

高級(jí)語(yǔ)言^產(chǎn)±

?一個(gè)問(wèn)題：如何解決程序的可移植性，即：程

序員編寫的源程序如何可以從一臺(tái)計(jì)算機(jī)很容

易地轉(zhuǎn)到另一臺(tái)計(jì)算機(jī)上工作。為了解決這些

問(wèn)題，人們引入了高級(jí)語(yǔ)言來(lái)編寫程序。

?所謂高級(jí)語(yǔ)言是一種由表達(dá)各種意義的“詞”

和“公式”，按照一定的“語(yǔ)法規(guī)則”來(lái)編寫

程序的語(yǔ)言，又稱為程序設(shè)計(jì)語(yǔ)言或算法語(yǔ)言。

?高級(jí)語(yǔ)言之所以“高級(jí)”，就是因?yàn)樗钩绦?/p>

員可以完全不用與計(jì)算機(jī)的硬件打交道，可以

不必了解機(jī)器的指令系統(tǒng)。

?程序員可以把硬件上復(fù)雜的概念比如存儲(chǔ)空間

抽象成一個(gè)所謂的變量之類的概念，因而程序

員就可以繞開硬件問(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é)、易懂，也易編寫。

_____高級(jí)措言的賞見類型

?目前已經(jīng)有許多高級(jí)語(yǔ)言在流行，并且

新的類型還在不斷出現(xiàn)和升級(jí)。

?用戶在實(shí)際應(yīng)用中進(jìn)行程序設(shè)計(jì)時(shí)，可

根據(jù)情況選擇適合的高級(jí)語(yǔ)言。

?⑴BASIC語(yǔ)言

?(2)FORTRAN語(yǔ)言

?(3)COBOL語(yǔ)言

?(4)PASCAL語(yǔ)言

?(5)C語(yǔ)言

?(6)C++語(yǔ)言

?(7)其他高級(jí)語(yǔ)言

?基于視窗類操作系統(tǒng)的，如VisualBasic>

VisualC++>Delphi、PowerBuilder>Java等

空

寸O

?高級(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)用。

內(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)字母

?大寫英文字母A?Z,小寫英文字母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è)以上的字符組成，例如GoTo（轉(zhuǎn)

移）、＜=（小于或等于）、AND（與）等等。

2.高級(jí)語(yǔ)言的基本元素

?基本元素由基本符號(hào)組成，可分為數(shù)、

邏輯值、名字、標(biāo)號(hào)和字符串等五大類。

?⑴數(shù)

?它由0?9共10個(gè)基本數(shù)字和其他一些符

號(hào)(如小數(shù)點(diǎn)正負(fù)號(hào)“十、一”及

指數(shù)符號(hào)等所構(gòu)成。

?⑵邏輯值一

?由真(True)和假(Fake)兩個(gè)值表示。

?(3)名字

?由字符組成，一般約定名字的開頭是字母或者

下劃線，其后可為字母或數(shù)字，如XYZ、

A123、_C等。名字可用來(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ù)

?為了支持用戶編寫出功能強(qiáng)大的源程序,

幾乎所有的高級(jí)語(yǔ)言都為用戶提供了豐

富的庫(kù)函數(shù)，這些庫(kù)函數(shù)能夠?qū)崿F(xiàn)某些

特定的功能，比如計(jì)算一個(gè)比較復(fù)雜的

數(shù)學(xué)函數(shù)。

?在源程序中，用戶也可以自己定義自己

的函數(shù)（子程序或過(guò)程），以便以后可以

反復(fù)調(diào)用這些代碼集合。

?任何一種程序設(shè)計(jì)語(yǔ)言都強(qiáng)調(diào)注釋的重要性。

源程序所包含的代碼往往比較冗長(zhǎng)，添加必要

的注釋不僅有助于閱讀程序，更重要的是，在

需要對(duì)程序功能進(jìn)行擴(kuò)充時(shí)，注釋可以極大地

幫助程序員對(duì)原始程序的理解。

?經(jīng)常會(huì)出現(xiàn)這樣一種情況，程序員自己編寫的

程序，經(jīng)過(guò)一段時(shí)間后，可能就是半年或者幾

個(gè)月以后，程序員自己也讀不懂自己的程序了。

況且，程序不僅要自己看得懂，更重要的是也

要讓別人能夠看懂。

9.程序設(shè)計(jì)風(fēng)格

?(1)編碼格式和編碼約定在整個(gè)程序中應(yīng)保持一致。

?(2)程序中應(yīng)給出必要的注釋，尤其在變量定義、調(diào)用接口、參

藪傳遞處，在修改程序時(shí)應(yīng)注明修改人、時(shí)間、簡(jiǎn)要的修改原因。

?(3)對(duì)變量、函數(shù)標(biāo)識(shí)等的命名，采用規(guī)范的命名方法，避免含

義不明確的縮寫，從命名最好就可以一目了然讀出命名標(biāo)識(shí)的含

義和藪據(jù)類型。

?(4)采用縮進(jìn)格式，突出程序的邏輯層次結(jié)構(gòu)。

?(5)每一行只寫一條語(yǔ)句，使用括號(hào)間隔表達(dá)式或語(yǔ)句的組成部

分，使組成部分清晰；

?(6)使用結(jié)構(gòu)化、面向?qū)ο蟮木幊碳夹g(shù)，提高程序可重用性、可

獷充性。

?(7)除非完全必要，應(yīng)盡量避免多任務(wù)和多重處理。

?(8)盡量避免使用復(fù)雜的算術(shù)和邏輯表達(dá)式。

?(9)提高程序健壯性，預(yù)防用戶的操作錯(cuò)誤，做到廢進(jìn)廢出。

10.高級(jí)語(yǔ)言程序的運(yùn)行

?使用高級(jí)語(yǔ)言編制程序的一般過(guò)程可以歸納為

以下幾個(gè)步驟：

1,逐條編寫源程序的語(yǔ)

口O存儲(chǔ)源程序文件時(shí)文件的后綴名與所用的

高級(jí)語(yǔ)言有關(guān)。

?(2)編譯源程序文件，生成目標(biāo)文件,文件后

鬃名通常為obj。

?(3)鏈接目標(biāo)文件，生成可執(zhí)行文件,文件后

鬃它通常為exe。

?今(在計(jì)算機(jī)上執(zhí)行可執(zhí)行程序文件,進(jìn)一步

痼試和維護(hù)。

6.方場(chǎng)

1.結(jié)構(gòu)化程序設(shè)計(jì)思想

采用自頂向下、逐步求精的設(shè)計(jì)方

法和單入口單出口的控制結(jié)構(gòu)。

?結(jié)構(gòu)化程序設(shè)計(jì)的原則是：

?(1)使用順序、選擇、循環(huán)3種基本控制

結(jié)構(gòu)表示程序邏輯。

?(2)程序語(yǔ)句組織成容易識(shí)別的語(yǔ)句模塊,

每個(gè)模塊都是單入口、單出口。

?(3)嚴(yán)格控制GOTO語(yǔ)句的使用。

（a）順序結(jié)構(gòu)（b）選擇結(jié)構(gòu)（c）while循環(huán)（d）do-while循環(huán)

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)。

6.2.Z質(zhì)問(wèn)對(duì)象的程序設(shè)計(jì)方法

1.面向?qū)ο蟮乃枷?/p>

?OO（ObjectOriented,面向?qū)ο螅┑某绦?/p>

設(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é)果。

6.3數(shù)據(jù)結(jié)構(gòu)

6.3.1基本概念

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ù)類型。

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)。

?樹形結(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)

稱為樹形結(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)鍵字和用以指示該元素的地址指

車K

?④散列結(jié)構(gòu)

通過(guò)構(gòu)造相應(yīng)的散列函數(shù)，由散列

函數(shù)的值來(lái)確定元素存放的地址。

?(3)數(shù)據(jù)運(yùn)算

數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作

有數(shù)據(jù)的插入、刪除、查找、遍歷等。

數(shù)據(jù)操作通常由計(jì)算機(jī)程序加以實(shí)

現(xiàn)，通常也叫算法實(shí)現(xiàn)。

6.3.2線性表

?i.定義

-線性表是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，

元素之間是一對(duì)一的線性關(guān)系，除了第一個(gè)元素

只有直接后繼、最后一個(gè)元素只有直接前驅(qū)外，

其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼,

如圖。

元素1元素2元素3元素n

?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ì)

溢出O

?②刪除

在線性表中，找到滿足條件的數(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í)行相同處理的操作。這

里的處理可以是讀、寫、或查詢等。

6.3.3棧

?i.定義

對(duì)于由N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序列,

如果只允許在其固定的一端位置插入和刪除一

個(gè)數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱

%堆?；虺?stack)o

允許插入或刪除的這一端稱為棧項(xiàng)，另一

個(gè)固定端稱為棧底。當(dāng)表中沒有元素時(shí)稱為空

在。

2.運(yùn)算和實(shí)現(xiàn)

?棧的基本運(yùn)算主要有：入棧、出棧和判斷。

?①入棧

入棧也叫壓棧，是在棧頂添加新元素的操

作，新的元素入棧后成為新的棧頂元素。

?②出棧

出棧也叫退?；驈棗?，是將棧頂元素從棧

中退出并傳遞給用戶程序的操作

E

入棧數(shù)據(jù)元素E出棧數(shù)據(jù)元素D—

D?-----------------DD

CL)CCc

B

BBB

A

AAA

?③判斷

判斷操作用來(lái)檢查棧內(nèi)數(shù)據(jù)是否為

空，返回結(jié)果是一個(gè)邏輯值：真或假。

如果棧頂和棧底重合，說(shuō)明堆棧為空。

6.3.4隊(duì)列

?1.定義

對(duì)于由N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線

性序列，如果在其固定的一端只允許插

入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)

據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱

為隊(duì)列(queue)。

把允許插入的一端叫隊(duì)尾(rear),把

只允許刪除的一端叫認(rèn)首(front)o

—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出隊(duì)

?③判斷：

判斷操作用來(lái)檢查隊(duì)列是否為空，返

回結(jié)果是一個(gè)邏輯值：真或假，如圖。

3.循環(huán)隊(duì)列的實(shí)現(xiàn)

6.3.5樹

?1.定義

樹形數(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)。

樹主要用在大型、動(dòng)態(tài)列表的搜索,

人工智能系統(tǒng)和編碼算法等問(wèn)題中。

?樹常見的基本運(yùn)算有：插入、刪除和遍歷。

?①插入

在樹中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新

的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。

?②刪除

在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)

點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。

?③遍歷

按照某種順序或規(guī)則，對(duì)樹中的每個(gè)節(jié)點(diǎn)逐一進(jìn)

行訪問(wèn)的過(guò)程。

3.實(shí)現(xiàn)

[6.35圖

?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)，

以及圖論中獲得最小生成樹。除此以外，圖在

自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也

都有著非常廣泛的應(yīng)用。

2.運(yùn)算

-常見的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添

加邊、刪除邊和遍歷圖。

?①添加頂點(diǎn)

在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常

是孤立的節(jié)點(diǎn)，還沒有邊連接。

?②刪除頂點(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)行描述。

'6.4算法八折一礎(chǔ)彳.

6.4.1概述

?1.算法的定義

準(zhǔn)確地說(shuō)，“算法(Algorithm)是一組明確

的、可以執(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)化算法。

2.算法的特性

?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ù)。

3.算法的描述一

⑴自然語(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ǔ)言形

式靈活，格式緊湊，沒有嚴(yán)格的語(yǔ)法。

?(4)程序設(shè)計(jì)語(yǔ)言形式

算法也可以用某種具體的計(jì)算機(jī)程序設(shè)計(jì)

語(yǔ)百柔表不，如，C>C++、Java第都可以用

來(lái)描述算法。

例如，求兩個(gè)數(shù)的較大者。用偽代碼描述算法

如下：

Input:twonumbers:a,b

1.if(thefirstnumberaisgreaterthanor

equaltothesecondnumberb)

then

1.1returna

else

1.2returnb

endif

end

6.4.2常用算法介紹

?1.遞歸算法

如果一個(gè)過(guò)程直接或間接地調(diào)用它

本身，則稱該過(guò)程是遞歸的。

?例如，數(shù)學(xué)階乘運(yùn)算，可以用遞歸算法

定義函數(shù)f(n)如下：

1

n\-<

?遞歸的情況包括所謂的遞推法和分治法。

?遞推是從已知的初始條件出發(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)=O的解。首先用某種

數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x),然后按以下

步驟執(zhí)行：

?(1)選一個(gè)方程的近似根，賦給變量xO；

?(2)將xO的值保存于變量xl,然后計(jì)算g(xl),

并將結(jié)果存于變量xO；

?(3)若xO與xl差的絕對(duì)值還不小于指定的精度要

求時(shí)，重復(fù)步驟⑵的計(jì)算。

?如果方程有解，并且按照上述方法計(jì)算出來(lái)的

近似根序列數(shù)學(xué)上收斂，則按上述方法求得的

xl就認(rèn)為是方程的根。

?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)解了。

L6.4.k算法的評(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í)間

開銷和空間開銷入手，來(lái)分析算法的時(shí)間復(fù)雜

性及空間復(fù)雜性。

1.算法的時(shí)間復(fù)雜度

?時(shí)間復(fù)雜度(Timecomplexity)是度量時(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),

其中，n代表求解問(wèn)題的規(guī)模，一般是指待處

理的數(shù)據(jù)量的大小。

?引入符號(hào)“O”，以此簡(jiǎn)化時(shí)間復(fù)雜度T(n)

與求解問(wèn)題規(guī)模n之間的函數(shù)關(guān)系，簡(jiǎn)化后

的關(guān)系是一種數(shù)量級(jí)關(guān)系。

?時(shí)間復(fù)雜度最好的算法是常數(shù)數(shù)量級(jí)的算法。

常數(shù)數(shù)量級(jí)的算法表示為O(c),其中c表示

任意常數(shù)。

■例如，如果某個(gè)算法的時(shí)間復(fù)雜度為

T(n)=n2+2n,那么,當(dāng)萊裨規(guī)模趨于n無(wú)窮

大時(shí)，有T(n)/n2-1,表示算法的時(shí)間復(fù)雜

2

度與ip成正4匕，記為T(n)=O(n)o

?多項(xiàng)式函數(shù)的時(shí)間復(fù)雜度有0(11),o

(吟,o(n3),0(114)等等,以及數(shù)量級(jí)介

于上述藪量級(jí)之間的O(1082口)，O

(n^log2n)，O(n2*log2n)等等。

2.算法的空間復(fù)雜度

?算法的空間復(fù)雜度(Spacecomplexity)用

來(lái)度量算法的空間復(fù)雜性、即執(zhí)行算法

的程序在計(jì)算機(jī)中運(yùn)行時(shí)所占用空間的

大小。

?簡(jiǎn)單講，空間復(fù)雜度也是與求解問(wèn)題規(guī)

模、算法輸入相關(guān)的函數(shù)。記為S(n),

其中n代表求解問(wèn)題的規(guī)模。

?符號(hào)“O”同樣被用來(lái)表示空間復(fù)雜度S(n)

與求解問(wèn)題規(guī)模n之間的數(shù)量級(jí)關(guān)系。

例如,如果S(n尸。(小),表示算法的

空間復(fù)雜度與ip成正比，記為S(n尸O(n2)。

?空間復(fù)雜度的分析方法與時(shí)間復(fù)雜度的分

析也是類似的，往往希望算法有常數(shù)數(shù)量

級(jí)或多項(xiàng)式數(shù)量級(jí)的空間復(fù)雜度。

6.4.4NP問(wèn)題

?NP(Non-deterministicPolynomial)問(wèn)題，是非

確定型多項(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)式(NP)問(wèn)題。

?例如，找一個(gè)大的質(zhì)數(shù)的問(wèn)題。并不存

在一個(gè)公式可以用來(lái)推算并找到這個(gè)大

的質(zhì)數(shù)，但是，如果事先給定一個(gè)數(shù)，

程序卻可以在多項(xiàng)式時(shí)間內(nèi)判斷出它是

否滿足要求。

■檢驗(yàn)一個(gè)問(wèn)題是否屬于NP問(wèn)題，如果在

多項(xiàng)式時(shí)間內(nèi)能夠證明該問(wèn)題的任意

“是”的實(shí)例是正確的，則該問(wèn)題即為

NP問(wèn)題。

?目前關(guān)于NP問(wèn)題的研究主要集中在NP-完全問(wèn)

題的研究上，較為典型的有裝箱問(wèn)題、背包問(wèn)

題、著色問(wèn)題等等。

?這些問(wèn)題的研究結(jié)果有兩種可能，一種是找到

了求解問(wèn)題的算法；另外一種就是求解問(wèn)題的

算法是不存在的，那么就要從數(shù)學(xué)理論上證明

它為什么不存在。

6.5編譯原理

6.5.1編譯程序概述

?語(yǔ)言處理的過(guò)程如圖所示。

骨期程序

絕對(duì)機(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)文件（*.obj）才能執(zhí)行。

表格管理

目

詞

標(biāo)

法

序

程

源

代

分目標(biāo)代碼

碼

析

生

器

成

出錯(cuò)處理

6.5.2詞法分析

?其任務(wù)是從左到右一個(gè)字符、一個(gè)字符

地對(duì)源程序進(jìn)行掃描，讀入源程序，對(duì)

構(gòu)成源程序的字符流進(jìn)行掃描和分解，

通過(guò)詞法分析從而識(shí)別出一個(gè)個(gè)單詞（也

稱單詞符號(hào)或符號(hào)）。

?例6.1對(duì)表達(dá)式：position:=initial+

rate*100；進(jìn)行詞法分析。

?對(duì)其進(jìn)行詞法分析后得到以下結(jié)果：

?單詞類型單詞值

?標(biāo)識(shí)符l(idl)position

?算符(賦值)：=

?標(biāo)識(shí)符2(