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

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

算法分析

本章要點

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

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

法

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

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

?了解編譯原理的基本知識

6.1程序設(shè)計基石

6.1.1程序的概念

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

集合。

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

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

程序設(shè)計語言寫成。

?程序設(shè)計語言是一組專門設(shè)計的用來生成一系

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

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

代碼。

?分類：

低級語言、高級語言。.

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

編語言O(shè)

機(jī)器語言

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

別和執(zhí)行。

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

同的。

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

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

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

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

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

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

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

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

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

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

匯編語言

?匯編語言也稱符號語言。

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

易記憶。

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

符號來代替由一個個0和I構(gòu)成的指令操

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

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

樣編寫出來的程序就稱為符號語言程序

或匯編語言程序。

?大多數(shù)情況下，一條匯編指令直接對應(yīng)

一條機(jī)器指令，少數(shù)對應(yīng)幾條機(jī)器指令。

?匯編語言具有一個本質(zhì)上與機(jī)器語言一

一對應(yīng)的指令系統(tǒng)。匯編語言的實質(zhì)和

機(jī)器語言是相同的。

低級語言的特點

?①都與特定的計算機(jī)硬件系統(tǒng)緊密相關(guān)，來自

于特定系統(tǒng)的指令系統(tǒng)，可移植性差；

-②專業(yè)知識要求高，要求對計算機(jī)硬件的結(jié)構(gòu)

和工作原理非常熟悉；

?③每條指令的功能很單一，程序員編制源程序

時指令比較繁瑣；

?④由于直接針對特定硬件編程，所以，最終的

可執(zhí)行程序代碼精煉，而且執(zhí)行效率非常高。

?兩者主要的區(qū)別在于：機(jī)器語言無需翻

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

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

程序。

匯編

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

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

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

能夠識別的機(jī)器語言。

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

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

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

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

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

過程稱為匯編。

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

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

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

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

匯編功能。

高級語言^產(chǎn)±

?一個問題：如何解決程序的可移植性，即：程

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

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

問題，人們引入了高級語言來編寫程序。

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

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

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

?高級語言之所以“高級”，就是因為它使程序

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

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

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

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

員就可以繞開硬件問題而集中精力解決問題本

身，編程效萃大大提高。

?由于高級語言與具體機(jī)器無關(guān)，那么在一種機(jī)

器上運(yùn)行的高級語言程序可以幾乎不經(jīng)改動地

移植到另一種機(jī)器上運(yùn)行，大大提高了程序的

通用性。

?此外，由于高級語言與自然語言（尤其是英語）

很相似，因此易學(xué)、易懂，也易編寫。

_____高級措言的賞見類型

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

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

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

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

?⑴BASIC語言

?(2)FORTRAN語言

?(3)COBOL語言

?(4)PASCAL語言

?(5)C語言

?(6)C++語言

?(7)其他高級語言

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

VisualC++>Delphi、PowerBuilder>Java等

空

寸O

?高級語言的優(yōu)點是語句的功能強(qiáng)，源程序比較

短，容易學(xué)習(xí)，使用方便，通用性較強(qiáng)，便于

推廣和交流。

?其缺點是編譯程序比匯編程序復(fù)雜，而且編譯

出來的目標(biāo)程序往往效率不高，目標(biāo)程序的長

度比有經(jīng)驗的程序員所編的同樣功能的匯編語

言程序要長一半以上，運(yùn)行時間也要長一些。

-因此，在很多對時間要求比較高的系統(tǒng)，如某

些實時控制系統(tǒng)或者大型計算機(jī)控制系統(tǒng)中，

低級語言，主要是匯編語言，仍然得到了一定

的應(yīng)用。

內(nèi)容

?高級程序設(shè)計語言依賴于各自特定的語句和語

法。一條一條的語句是構(gòu)成源程序的基本單位。

高級語言的一條語句被編譯或解釋時往往會對

應(yīng)多條機(jī)器指令。

?每一種編程語言都包含一組語句和語法。所謂

語法，是指管理語言結(jié)構(gòu)和語句的一組規(guī)則。

不論使用何種設(shè)計語言，都必須遵循其語法規(guī)

則。

?以下內(nèi)容主要描述了大多數(shù)高級語言都共同具

備的特性，但不一定是所有高級語言都有的。

1.高級語言的基本符號

?高級語言都是由所謂的基本符號組成的。基本

符號可以分為單字符和多字符兩種情況。單字

符基本符號由單個字符組成，在高級語言中通

常都有下列幾種單字符基本符號：

■(1)字母

?大寫英文字母A?Z,小寫英文字母a?z,共

52個符號。

?(2)數(shù)字

?0?9,共10個數(shù)字符號。

?（3）特殊字符

?十（加），一（減），*（乘），/（除），八（乘方）,

=（等號），（（左括號），）（右括號），＞（大

于），＜（小于），，（逗號），（空格）等。

?在高級語言中的多字符基本符號由兩個

或兩個以上的字符組成，例如GoTo（轉(zhuǎn)

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

2.高級語言的基本元素

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

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

?⑴數(shù)

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

號(如小數(shù)點正負(fù)號“十、一”及

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

?⑵邏輯值一

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

?(3)名字

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

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

A123、_C等。名字可用來定義常量、變量、

函數(shù)、過程或子程序的，也被用來定義成某些

東西，故也稱為標(biāo)識符。在高級語言中，一般

還規(guī)定了組成名字的字符的長度，即字符個數(shù)。

?(4)標(biāo)號

-是在高級語言中的程序語句前所加的一個名字,

主要用來指示程序可能的轉(zhuǎn)移方向。

?(5)字符串

?由一串字符所組成。在不同的高級語言

中，字符串中的多個字符放在一對單引

號或雙引號中。

3.基本的數(shù)據(jù)類型

?任何一種高級語言都會定義一些基本的

數(shù)據(jù)類型?；镜臄?shù)據(jù)類型通常包括整

數(shù)數(shù)據(jù)類型、實數(shù)數(shù)據(jù)類型和字符數(shù)據(jù)

類型等。

-在程序中，除了值無需改變的常數(shù)外，

大部分?jǐn)?shù)據(jù)的值是可以修改的。在程序

中，變量是指代表某個具體數(shù)值，并且

所代表的數(shù)值可改變的一個符號名字。

-變量必須先定義，然后才能使用，這是一條基

本原則。

-變量實質(zhì)上代表了一個特定大小的內(nèi)存單元空

間。

?定義變量的實質(zhì)就是讓程序為該變量分配一個

特定的內(nèi)存空間。

-變量的類型實質(zhì)上反映了該數(shù)據(jù)占用內(nèi)存空間

的大小，即分配給該變量代表的數(shù)據(jù)的所占據(jù)

的內(nèi)存單元的字節(jié)數(shù)目。

4.結(jié)構(gòu)數(shù)據(jù)類型

-是在基本數(shù)據(jù)類型的基礎(chǔ)上構(gòu)造出來的數(shù)據(jù)類

型。數(shù)組和結(jié)構(gòu)體是大多數(shù)高級語言都支持的

兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型。

?(1)數(shù)組類型

?數(shù)組是若干個相同類型的數(shù)據(jù)的集合。

?(2)用戶自定義的結(jié)構(gòu)體類型

?結(jié)構(gòu)體是隸屬于同一個事物的多個不同類型的

數(shù)據(jù)的集合，用來表示具有若干個屬性的一個

事物。

?除了以上兩種最基本的結(jié)構(gòu)數(shù)據(jù)類型外，許多

高級語言還有比如枚舉、集合，以及更復(fù)雜的

隊列、堆棧等多種數(shù)據(jù)類型。

?結(jié)構(gòu)數(shù)據(jù)類型在使用時也必須定義相應(yīng)類型的

“變量”名字。

5.運(yùn)算符與表達(dá)式

?表達(dá)式是由基本符號、基本元素和各種數(shù)據(jù)通

過各種運(yùn)算符連接而成的。按表達(dá)式的運(yùn)算結(jié)

果可以分為算術(shù)表達(dá)式、邏輯表達(dá)式和字符串

表達(dá)式等幾種情況。

?高級語言中的運(yùn)算符大致包括以下幾個方面：

?(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.語句

?語句是構(gòu)成高級語言源程序的基本單位,

是由基本元素、運(yùn)算符、表達(dá)式等組成。

任何一種高級語言往往都支持賦值、條

件判斷、循環(huán)、輸入輸出等語句。程序

員利用這些語句的結(jié)合，能夠很方便地

編制出功能強(qiáng)大的程序。

7.庫函數(shù)和用戶自定義的函數(shù)

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

幾乎所有的高級語言都為用戶提供了豐

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

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

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

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

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

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

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

源程序所包含的代碼往往比較冗長，添加必要

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

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

幫助程序員對原始程序的理解。

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

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

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

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

要讓別人能夠看懂。

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

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

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

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

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

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

義和藪據(jù)類型。

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

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

分，使組成部分清晰；

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

獷充性。

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

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

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

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

?使用高級語言編制程序的一般過程可以歸納為

以下幾個步驟：

1,逐條編寫源程序的語

口O存儲源程序文件時文件的后綴名與所用的

高級語言有關(guān)。

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

鬃名通常為obj。

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

鬃它通常為exe。

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

痼試和維護(hù)。

6.方場

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

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

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

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

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

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

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

每個模塊都是單入口、單出口。

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

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

2.模塊

?一個復(fù)雜的問題可以劃分為多個簡單問題的組

合。

-在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題

分解成一個個簡單問題的最基本方法就是模塊

化。

?模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏

的概念。模塊常用子程序加以實現(xiàn)。

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

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

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

設(shè)計把客觀事物看作具有屬性和行為的

對象，通過抽象找出同一類對象的共同

屬性（靜態(tài)特征）和行為（動態(tài)特征），形成

類。

2.對象和類

?對象

是對現(xiàn)實問題的高度概括、分類和

抽象。每個對象都只有自己的數(shù)據(jù)和相

應(yīng)的處理函數(shù)，整個程序是由一系列相

互作用的對象來構(gòu)成，不同對象之間是

通過發(fā)送消息來實現(xiàn)相互聯(lián)系、相互作

用。

?方法

在對象內(nèi)的操作通常叫做方法。

?類

定義了一組大體上相似的對象。一個類

所包含的方法和數(shù)據(jù)描述一組對象的共同行

為和屬性。

對象則是類的具體化，是類的實例。

?類通過派生可以有子類，同樣也可以有父類,

形成層次結(jié)構(gòu)。

3.抽象

?抽象

是對具體事物（即對象）進(jìn)行概括，

即忽略事物的非本質(zhì)特征，只注意那些

與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而抽象

出一類對象的共性并加以描述。

對一個問題的抽象一般來講應(yīng)該包

括兩個方面：數(shù)據(jù)抽象和代碼抽象（或稱

為行為抽象）。

4.封裝性

?封裝的兩個含義：

第一是，將抽象得到的數(shù)據(jù)成員和代碼成

員相結(jié)合，形成一個不可分割的整體，即對象,

這種數(shù)據(jù)及行為的有機(jī)結(jié)合也就是封裝。

第二個含義稱為信息隱蔽，即盡可能隱蔽

對象的內(nèi)部細(xì)節(jié)。在隱蔽對象內(nèi)部細(xì)節(jié)的同時,

對象需要提供與外部世界進(jìn)行交流的接口，并

實現(xiàn)對數(shù)據(jù)訪問權(quán)限的合理控制，把整個程序

中不同部分的相互影響減少到最低限度。

5.繼承性

?繼承性

是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制。

在定義一個類的時候，可以以一個已經(jīng)存在的

類為基礎(chǔ)，并把這個已經(jīng)存在的類所包含的屬

性和方法作為自身的一部分，然后加入新的屬

性和方法以區(qū)別于原來的類。

原有的類稱為基類或父類，產(chǎn)生的新類稱

為派生類。

6.多態(tài)性

?多態(tài)性

在收到外部消息時，對象通常要予

以響應(yīng)。不同的對象收到同一消息可能

產(chǎn)生完全不同的結(jié)果。

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

6.3.1基本概念

1.數(shù)據(jù)、數(shù)據(jù)類型

■數(shù)據(jù)

是對客觀事物的符號表示。在計算機(jī)系統(tǒng)

內(nèi)，數(shù)據(jù)通常是指能夠輸入到計算機(jī)中并被計

算機(jī)進(jìn)行處理的符號的集合。

?數(shù)據(jù)類型

是指具有相同取值范圍和可以實施同種操

作的數(shù)據(jù)的集合的總稱。例如，在程序設(shè)計中,

通常會有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。

2.數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對

?能夠獨立并完整地描述客觀世界實體的基本數(shù)

據(jù)單元稱為數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單

彳立。

?數(shù)據(jù)項是組成數(shù)據(jù)元素的不可分割的最小單位。

最簡單的數(shù)據(jù)元素就是由一個數(shù)據(jù)項構(gòu)成的。

?同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。

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)系，即除了第一個數(shù)據(jù)元素和最后一個元素外，其

，也每個元素軟有惟一的一個前驅(qū)和一個后繼元素，這

樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。

?樹形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且

除了一個被稱為根節(jié)點的元素外，每個元素都有一個

前驅(qū)節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯結(jié)構(gòu)

稱為樹形結(jié)構(gòu)。

■圖形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，如果任何一個數(shù)據(jù)元素都可以有多個

前驅(qū)節(jié)點和多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為圖形結(jié)

構(gòu)。

?(2)數(shù)據(jù)的物理結(jié)構(gòu)

數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計

算機(jī)存儲器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)

不僅要存儲數(shù)據(jù)本身，還要存儲表示數(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ù)的存儲單元中,

邏輯上相鄰的元素存儲在物理位置相鄰的存儲

單元中，由此得到的存儲表示稱為順序存儲結(jié)

構(gòu)。

順序存儲結(jié)構(gòu)常借助于程序設(shè)計語言中的

數(shù)組來實現(xiàn)。優(yōu)點是使用方法簡單，缺點是必

須預(yù)先分析出所需定義數(shù)組的大小。

?②鏈表結(jié)構(gòu)

對邏輯上相鄰的元素不要求其物理

位置相鄰，元素間的邏輯關(guān)系通過附設(shè)

的指針域來實現(xiàn)，由此得到的存儲表示

稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。

鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計

語言中的指針來實現(xiàn)。

-③索引結(jié)構(gòu)

針對每個數(shù)據(jù)結(jié)構(gòu)建立一張所謂的

索引表，每個數(shù)據(jù)元素占用表中的一項,

每個表項包含一個能夠惟一識別一個元

素的關(guān)鍵字和用以指示該元素的地址指

車K

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

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

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

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

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

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

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

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

6.3.2線性表

?i.定義

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

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

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

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

如圖。

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

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

線性表通常采用順序和鏈表兩種物

理實現(xiàn)。對于經(jīng)常變化的表，通常采取

鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：

插入、刪除、查詢和遍歷。

?①插入

在保持原有的存儲結(jié)構(gòu)的前提下，根據(jù)插

入要求，在適當(dāng)?shù)奈恢貌迦胍粋€元素。插入操

作要求線性表要有足夠的存放新元素的空間，

如果空間不足，插入操作無法進(jìn)行，線性表會

溢出O

?②刪除

在線性表中，找到滿足條件的數(shù)據(jù)元素，

并刪除。如果線性表為空，刪除就會失敗。

?③查詢

在線性表中，按照查詢條件，定位數(shù)據(jù)元

素的過程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)

元素中的關(guān)鍵字進(jìn)行。實際上，數(shù)據(jù)的插入利

刪除都需要首先定位數(shù)據(jù)元素。對于空的線性

表是無法查詢的。

?④遍歷

是指按照某種方式，逐一訪問線性表中的

每一個數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這

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

6.3.3棧

?i.定義

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

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

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

%堆?；虺?stack)o

允許插入或刪除的這一端稱為棧項，另一

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

在。

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

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

?①入棧

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

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

?②出棧

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

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

E

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

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

CL)CCc

B

BBB

A

AAA

?③判斷

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

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

如果棧頂和棧底重合，說明堆棧為空。

6.3.4隊列

?1.定義

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

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

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

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

為隊列(queue)。

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

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

—2.運(yùn)算一二.

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

?①入隊

入隊是在隊列中插入一個新數(shù)據(jù)元素的過

程，插入在隊尾進(jìn)行，新的元素成為隊尾，。

■②出隊、

出隊是在隊列中刪除一個數(shù)據(jù)元素的過程,

刪除在隊首進(jìn)行并把出來的數(shù)據(jù)傳遞給用戶程

序。

A,B,C出隊

?③判斷：

判斷操作用來檢查隊列是否為空，返

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

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

6.3.5樹

?1.定義

樹形數(shù)據(jù)結(jié)構(gòu)中，每個數(shù)據(jù)元素稱

為是一個節(jié)點，除了一個惟一的所謂根

節(jié)點外，其他每個節(jié)點都有且只有一個

父節(jié)點，每個元素可以有多個子節(jié)點。

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

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

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

?①插入

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

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

?②刪除

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

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

?③遍歷

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

行訪問的過程。

3.實現(xiàn)

[6.35圖

?1.定義

在圖形結(jié)構(gòu)中，每個數(shù)據(jù)元素稱為一個頂

點，任意兩個頂點之間都可能相關(guān)，這種相關(guān)

性用一條邊來表示，頂點之間的鄰接關(guān)系可以

是任意的。

圖可以用來描述計算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，

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

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

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

2.運(yùn)算

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

加邊、刪除邊和遍歷圖。

?①添加頂點

在圖中添加新的頂點，新添加的頂點通常

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

?②刪除頂點

在圖中去掉一個頂點，顯然，在去掉一個

頂點的同時還應(yīng)該刪除與該頂點所連接的邊。

?③添加邊

根據(jù)指定的頂點，添加相應(yīng)的邊。

?④刪除邊

根據(jù)指定的頂點，刪除相應(yīng)的邊。

?⑤遍歷圖

按照一定的規(guī)則，對圖中的每個數(shù)

據(jù)頂點逐一進(jìn)行訪問。

3.實現(xiàn)

?圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實現(xiàn)。

對于各個頂點和頂點之間的關(guān)系分別采

用鄰接矩陣和鄰接列表來進(jìn)行描述。

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

6.4.1概述

?1.算法的定義

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

的、可以執(zhí)行的步驟的有序集合，它在有限的

時間內(nèi)終止并產(chǎn)生結(jié)果”。

?算法和數(shù)據(jù)結(jié)構(gòu)之間存在密切聯(lián)系。數(shù)據(jù)結(jié)構(gòu)

是算法的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)的不同，通常的采用

的算法也會不同；當(dāng)問題的求解算法一旦確定,

也可以選擇合適的數(shù)據(jù)結(jié)構(gòu)加以實現(xiàn)，合理的

數(shù)據(jù)結(jié)構(gòu)能夠簡化算法。

2.算法的特性

?1()有窮性(可終止性)

一個算法必須在有限個操作步驟內(nèi)以及合

理的時間內(nèi)執(zhí)行完成。

?(2)確定性

算法中的每一個操作步驟都必須有明確的

含義，不允許存在二義性。

?(3)有效性(可執(zhí)行性)

算法中描述的操作步驟都是可執(zhí)行的，并

能最終得到確定的結(jié)果。

?(4)輸入及輸出

一個算法應(yīng)該有零個或多個輸入數(shù)據(jù)、有1

個或多個輸出數(shù)據(jù)。

3.算法的描述一

⑴自然語言表示

自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以

是中文、英文等。

?例如，求三個數(shù)中最大值的問題，可以描述為:

?①比較前兩個數(shù)；

?②將①中較大的數(shù)與第三個數(shù)進(jìn)行比較；

?③步驟②中較大的數(shù)即為所求。

?(2)流程圖表示

流程圖是用規(guī)定的一組圖形符號、流程線

和文字說明來表示算法的一種表示方法。

?(3)偽碼

偽碼用一種介于自然語言與計算機(jī)語言之

間的文字和符號來描述算法。比計算機(jī)語言形

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

?(4)程序設(shè)計語言形式

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

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

來描述算法。

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

如下：

Input:twonumbers:a,b

1.if(thefirstnumberaisgreaterthanor

equaltothesecondnumberb)

then

1.1returna

else

1.2returnb

endif

end

6.4.2常用算法介紹

?1.遞歸算法

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

本身，則稱該過程是遞歸的。

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

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

1

n\-<

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

?遞推是從已知的初始條件出發(fā)，逐次推導(dǎo)出最

后所求的值。遞推是利用問題本身所具有的一

種遞推關(guān)系求解問題的一種方法。

-分治法也是一種廣泛使用的算法設(shè)計方法。其

基本思想是把大問題分解成一些較小的問題。

然后由小問題的解方便地構(gòu)造出大問題的解。

?2.迭代算法

所謂迭代是指重復(fù)執(zhí)行一組指令或操作步

驟，在每次執(zhí)行這組指令時，都從原來的解值

的基礎(chǔ)上推出一個新的解值。新的解值比原來

的解值更加接近真實的解。這個過程不斷重復(fù),

直到計算得到的解與真實解的誤差滿足實際要

求。

?迭代常常用于科學(xué)計算領(lǐng)域?qū)δ承o法直接求

解的數(shù)值問題。

?例如：現(xiàn)欲求解方程f(x)=O的解。首先用某種

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

步驟執(zhí)行：

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

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

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

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

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

?如果方程有解，并且按照上述方法計算出來的

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

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

?3.窮舉算法

亦稱枚舉法，該算法首先根據(jù)問題

的部分條件確定問題解的大致范圍，然

后在此范圍內(nèi)對所有可能的情況逐一進(jìn)

行驗證，直到全部情況驗證完畢。

4.貪婪算法

貪婪算法通常具有貪婪選擇性和最

優(yōu)子結(jié)構(gòu)性。貪婪選擇性指的是所求解

問題的整體最優(yōu)解可以通過一系列局部

最優(yōu)的選擇，即貪婪選擇來達(dá)到。最優(yōu)

子結(jié)構(gòu)性指的是一個問題的最優(yōu)解往往

包含著它的子問題的最優(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。此時，貪婪法的結(jié)果就不等于

最優(yōu)解了。

L6.4.k算法的評價

?對于一個算法的評價，通常要從正確性、可理

解性、健壯性、時間復(fù)雜性及空間復(fù)雜性等多

個方面加以衡量。相比而言，人們更關(guān)心的是

與計算機(jī)系統(tǒng)資源密切相關(guān)的時間復(fù)雜性和空

間復(fù)雜性。

?在計算機(jī)系統(tǒng)內(nèi)，求解問題的算法耗費(fèi)的資源

主要包括時間和空間，可以從分析算法的時間

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

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

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

?時間復(fù)雜度(Timecomplexity)是度量時間復(fù)雜

性、即算法的時間效率的指標(biāo)。時間復(fù)雜度是

與求解問題規(guī)模、算法輸入相關(guān)的函數(shù)，該函

數(shù)表示算法運(yùn)行所花費(fèi)的時間。

?為了簡化問題，通常，用算法運(yùn)行某段核心代

碼的次數(shù)來代替準(zhǔn)確的執(zhí)行時間，記為T(n),

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

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

?引入符號“O”，以此簡化時間復(fù)雜度T(n)

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

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

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

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

任意常數(shù)。

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

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

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

2

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

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

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

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

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

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

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

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

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

大小。

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

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

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

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

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

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

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

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

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

級或多項式數(shù)量級的空間復(fù)雜度。

6.4.4NP問題

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

確定型多項式問題。所謂的非確定型，簡單講

就是指算法無法直接計算出結(jié)果，只能通過進(jìn)

行一些有選擇的“猜算”來得到結(jié)果。

?對于這類問題給出的算法并不能直接計算出結(jié)

果，但可以檢驗?zāi)硞€可能的結(jié)果是正確的還是

錯誤的。這個可以檢驗“猜算”的答案正確與

否的算法，如果可以在多項式時間內(nèi)解出，就

是非確定型多項式(NP)問題。

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

在一個公式可以用來推算并找到這個大

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

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

否滿足要求。

■檢驗一個問題是否屬于NP問題，如果在

多項式時間內(nèi)能夠證明該問題的任意

“是”的實例是正確的，則該問題即為

NP問題。

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

題的研究上，較為典型的有裝箱問題、背包問

題、著色問題等等。

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

了求解問題的算法；另外一種就是求解問題的

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

它為什么不存在。

6.5編譯原理

6.5.1編譯程序概述

?語言處理的過程如圖所示。

骨期程序

絕對機(jī)器碼

?編譯程序的功能如圖所不。

語?編譯程序一（

?解釋程序在處理源程序時，執(zhí)行方式類

似于日常生活中的“同聲翻譯”。

?解釋一句、執(zhí)行一句，立即產(chǎn)生運(yùn)行結(jié)

果。解釋程序不產(chǎn)生目標(biāo)代碼，不能脫

離其語言環(huán)境獨立執(zhí)行。

?解釋程序?qū)υ闯绦虻慕忉寛?zhí)行比編譯程

序產(chǎn)生的目標(biāo)代碼程序的執(zhí)行速度要慢。

?編譯程序是把高級語言程序（源程序）作為一個

整體來處理，首先將程序源代碼“翻譯”成目

標(biāo)代碼（機(jī)器語言），編譯后與系統(tǒng)提供的代碼

庫鏈接，形成一個完整的可執(zhí)行的機(jī)器語言程

序（目標(biāo)程序代碼）。

?目標(biāo)程序可以脫離其語言環(huán)境獨立執(zhí)行，使用

比較方便、效率較高。相應(yīng)地，由于每次執(zhí)行

之前必須通過編譯得到可執(zhí)行程序，所以，可

執(zhí)行程序一旦需要修改，必須先修改源代碼，

再重新編譯生成新的目標(biāo)文件（*.obj）才能執(zhí)行。

表格管理

目

詞

標(biāo)

法

序

程

源

代

分目標(biāo)代碼

碼

析

生

器

成

出錯處理

6.5.2詞法分析

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

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

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

通過詞法分析從而識別出一個個單詞（也

稱單詞符號或符號）。

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

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

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

?單詞類型單詞值

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

?算符(賦值)：=

?標(biāo)識符2(