第5章計(jì)算機(jī)軟件開發(fā)

駱耀祖制作

本章學(xué)習(xí)目標(biāo)

本章介紹了程序設(shè)計(jì)的一些基本術(shù)語和

原理。通過本章的學(xué)習(xí)，讀者應(yīng)該掌握

計(jì)算機(jī)的程序設(shè)計(jì)基礎(chǔ)、程序語言的數(shù)

據(jù)類型、基本控制結(jié)構(gòu)，算法與數(shù)據(jù)結(jié)

構(gòu)、程序設(shè)計(jì)語言與翻譯系統(tǒng)、知道軟

件工程方法。本章重點(diǎn)是結(jié)構(gòu)化程序設(shè)

計(jì)，理解面向?qū)ο蠹捌鋺?yīng)用場合；理解

軟件開發(fā)和軟件工程的概念。

5.7程序設(shè)計(jì)基本概念

黎人們用以同計(jì)算機(jī)“交談”的語言，稱之計(jì)算

機(jī)語言O(shè)

器計(jì)算機(jī)每做的一次動作，一個步驟，都是按照

已經(jīng)用計(jì)算機(jī)語言編好的程序來執(zhí)行的，程序

是計(jì)算機(jī)要執(zhí)行的有序指令的集合，而程序全

部都是用我們所掌握的語言來編寫的。所以人

們要控制計(jì)算機(jī)一定要通過計(jì)算機(jī)語言向計(jì)算

機(jī)發(fā)出命令。

?計(jì)算機(jī)所能識別的語言只有機(jī)器語言。

5.7.7程序設(shè)計(jì)語言概述

般人們把需要計(jì)算機(jī)做的工作寫成一定形式的指

令，并把它們存儲在計(jì)算機(jī)內(nèi)存中，讓計(jì)算機(jī)

按順序自動執(zhí)行。這種可以連續(xù)執(zhí)行的計(jì)算機(jī)

指令的集合被稱為“程序”。程序?qū)嶋H上是用

計(jì)算機(jī)語言描述的對某一問題的解決步驟，而

編制程序就是為計(jì)算機(jī)安排指令序列。

齡人與計(jì)算機(jī)之間交流信息必須使用人和計(jì)算機(jī)

都能理解的程序設(shè)計(jì)語言。計(jì)算機(jī)程序設(shè)計(jì)人

員可以選擇各種各樣的程序設(shè)計(jì)語言或程序開

發(fā)工具來開發(fā)軟件。

直

接

機(jī)器語言（由和構(gòu)成的代碼）〕對

01硬

件

計(jì)算機(jī)語言<匯編語言（英文縮寫的助記符）操

作

高級語言

1、采用比較接近人們習(xí)慣的自然語言

2、具有很大的通用性（即不受具體機(jī)器指令的約束）

3、面向算法編寫程序

5.7.7程序設(shè)計(jì)語言概述

耶迄今為止，程序設(shè)計(jì)語言有超過幾百種之多，程序設(shè)

計(jì)語言可以分為五大類：機(jī)器語言、匯編語言、第三

代語言3GL(ThirdGenerationLanguage)>第四代語言

(4GL)和第五代語言(5GL)。而這些語言又可以分為低

級語言和高級語言。

?低級語言是一種面向機(jī)器的語言，它們對計(jì)算機(jī)硬件

的依賴程度很高。一種面向機(jī)器的語言只能運(yùn)行在某

種專門的計(jì)算機(jī)上。用機(jī)器語言編制的程序不能被移

植到其它計(jì)算機(jī)上。機(jī)器語言和匯編語言都是低級語

R。

?高級語言是一種非面向機(jī)器的語言。用高級語言編制

的程序可以運(yùn)行于多種不同類型的計(jì)算機(jī)和操作系統(tǒng)

之上。第三代、第四代和第五代語言都是高級語言。

1.機(jī)器語言

?每個計(jì)算機(jī)系統(tǒng)都有一套自己的指令系統(tǒng)，指

令系統(tǒng)中的每一條指令就稱為機(jī)器指令，而機(jī)

器指令的集合就稱為機(jī)器語言。機(jī)器語言由二

進(jìn)制代碼。和1組成，二進(jìn)制代碼。和1對應(yīng)于計(jì)

算機(jī)中電信號的兩種狀態(tài)，如電位的高和低、

電流的有或無、電容的充電或放電等。因此，

計(jì)算機(jī)能識別二進(jìn)制表示的機(jī)器指令，并能直

接執(zhí)行機(jī)器指令。

器一般來說，機(jī)器指令由操作碼和操作數(shù)兩部分

組成。操作碼告訴計(jì)算機(jī)進(jìn)行什么樣的操作，

操作數(shù)是將要被操作的對象。有時，操作數(shù)也

可以用地址碼來表示，地址碼告訴計(jì)算機(jī)到什

么地方去取操作數(shù)。

有機(jī)器語言的優(yōu)點(diǎn)是可以被計(jì)算機(jī)直接理

解和執(zhí)行，執(zhí)行速度快，且占用內(nèi)存少。

缺點(diǎn)是面向機(jī)器，通用性差。它要求程

序設(shè)計(jì)人員熟練掌握計(jì)算機(jī)的全部機(jī)器

指令，且要求對計(jì)算機(jī)硬件結(jié)構(gòu)有很好

的了解。用機(jī)器語言編寫的程序可讀性

很差，不易于調(diào)試和維護(hù)。

2.匯編語言

給匯編語言是第二代程序設(shè)計(jì)語言。在匯編語言

中，人們采用了有助于記憶的符號（稱為指令

助記符）來表示機(jī)器指令中的操作碼和地址碼。

指令助記符是一些有意義的英文單詞的縮寫和

符號。例如，匯編語言中采用英文單詞的縮寫

和符號等來表示操作碼。如用ADD表示加法

（addition）、用SUB表示減法（subtract）、

用MOV表示數(shù)據(jù)的傳送（move）、用JMP表示

程序的跳轉(zhuǎn)（jump）等等。而操作數(shù)可以直接

用十進(jìn)制數(shù)書寫，地址碼可以用寄存器名、存

儲單元的符號地址等表示。

?用匯編語言編寫的程序稱為匯編語言源程序。因?yàn)橛?jì)

算機(jī)只能識別用二進(jìn)制代碼表示的機(jī)器指令，而不能

識別匯編語言源程序中的指令助記符。因此必須將由

匯編語言編寫的源程序翻譯成由機(jī)器語言組成的目標(biāo)

程序，這個程序就叫做匯編程序，而這個翻譯的過程

就叫做匯編。匯編程序的工作過程如圖5.1所示。

辨與機(jī)器語言相比，匯編語言有許多優(yōu)點(diǎn)，程序設(shè)計(jì)人

員可以用匯編語言寫出語句少、質(zhì)量高、執(zhí)行速度快

的程序。但是，匯編語言仍是一種面向機(jī)器的語言，

通用性差。它要求程序設(shè)計(jì)人員對計(jì)算機(jī)的硬件結(jié)構(gòu)

如計(jì)算機(jī)的指令系統(tǒng)、CPU中寄存器的結(jié)構(gòu)及存儲器

單元的尋址方式等等有較詳細(xì)的了解，并且要求程序

設(shè)計(jì)人員具有較高的編程技巧。

匯編語言程序-------土-------1

?機(jī)器語言程序

源程序匯編目標(biāo)程序

0%

3.高頻語言

?事實(shí)上，高級語言包括了第三代、第四

代、第五代語言，但本小節(jié)所說“高級

語言”主要是指第三代語言。

<>高級語言是一種接近人的自然語言和數(shù)

學(xué)語言的程序設(shè)計(jì)語言。它易學(xué)易用，

并且不依賴于計(jì)算機(jī)硬件系統(tǒng)。用高級

語言編寫的程序不但表達(dá)直觀，可讀性

好，而且與具體機(jī)器無關(guān)，便于移植，

通用性好。

?高級語言是按照一定的“語法規(guī)則”，由表達(dá)各種不

同意義的“關(guān)鍵字”和“表達(dá)式”組成。例如，用

PRINT表示顯示，用數(shù)學(xué)運(yùn)算符表示加號，用

表示乘號等。這些用英語單詞表示的關(guān)鍵字和數(shù)學(xué)符

號簡化了程序設(shè)計(jì)人員開發(fā)應(yīng)用程序的過程。

?高級語言擺脫了具體機(jī)器的指令系統(tǒng)，不再依賴于機(jī)

器，它們是面向算法過程的語言。用過程化語言編程，

不但要告訴計(jì)算機(jī)“做什么”，還要告訴計(jì)算機(jī)“怎

么做”。用高級語言編程時，程序設(shè)計(jì)人員可以應(yīng)用

自頂向下的程序設(shè)計(jì)方法及結(jié)構(gòu)化的程序控制結(jié)構(gòu)

（順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)）來開發(fā)程序。在

程序中，無論是主程序還是過程子程序，其程序結(jié)構(gòu)

只能由三種基本結(jié)構(gòu)（順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)

構(gòu)）嵌套而成

4.第四代語言(4GL)

器第四代語言比第三代語言更接近于人的自然語

言，它是一種非過程化的語言。用非過程化語

言編程時，只需告訴計(jì)算機(jī)“做什么”，而無

需告訴計(jì)算機(jī)“怎么做”，即無需編寫“怎么

做”的實(shí)現(xiàn)模塊，語言的具體操作過程由計(jì)算

機(jī)系統(tǒng)自動完成。使用非過程化語言只需要說

明所要完成的加工和條件，給出輸入數(shù)據(jù)并指

明輸出形式，就能得到所需結(jié)果。(但是必須

指出，“怎么做”的實(shí)現(xiàn)模塊仍然是用傳統(tǒng)語

言來開發(fā)的。)第四代語言簡單易學(xué)，易于使

用。用第四代語言編程省時省力，用戶無需很

多程序設(shè)計(jì)知識就能開發(fā)應(yīng)用程序。

懿許多第四代語言主要應(yīng)用于數(shù)據(jù)庫領(lǐng)域。結(jié)構(gòu)

化查詢語言SQL(StructuredQueryLanguage)

就是第四代語言的代表。SQL是目前非常流行

的用于關(guān)系型數(shù)據(jù)庫的符合ANSI標(biāo)準(zhǔn)的第四代

語言。SQL被作為關(guān)系型數(shù)據(jù)庫管理系統(tǒng)的標(biāo)

準(zhǔn)語言，它具有數(shù)據(jù)查詢、數(shù)據(jù)定義、數(shù)據(jù)操

縱和數(shù)據(jù)控制功能，可以用來執(zhí)行如更新數(shù)據(jù)

庫中的數(shù)據(jù)，從數(shù)據(jù)庫中提取數(shù)據(jù)等操作。目

前，大多數(shù)流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，如

Oracle、Sybase、MicrosoftSQLServer、

Access等都采用了SQL語言標(biāo)準(zhǔn)。

5.第五代語言(5GL)

籍第五代語言是非過程化的語言，它們提

供了可視化的圖形界面來生成源代碼。

通常第五代語言使用第三代語言或第四

代語言的編譯程序來轉(zhuǎn)換得到相應(yīng)的機(jī)

器語言程序。有些面向?qū)ο蟮拈_發(fā)工具

和網(wǎng)頁開發(fā)工具也屬于第五代語言二例

如VisualBasic、VisualC++、Java就屬

于第五代語言。

5.7.2高級語言與翻譯系統(tǒng)

第通常把用高級語言編寫的程序也稱為“源程

序”，把用二進(jìn)制代碼表示的程序稱為“機(jī)器

代碼程序”或者“目標(biāo)程序”。由于計(jì)算機(jī)只

能識別和執(zhí)行由二進(jìn)制代碼組成的機(jī)器語言，

因此，用高級語言編寫的源程序，必須經(jīng)過一

個“語言處理程序”將它“翻譯”成計(jì)算機(jī)能

夠接受的目標(biāo)程序后，才能被計(jì)算機(jī)執(zhí)行。這

種具有翻譯功能的語言處理程序可以分為兩大

類：編譯程序（又稱為編譯器）和解釋程序

（又稱為解釋器）。

莓(1)編譯類：編譯是指在應(yīng)用源程序執(zhí)行之

前，就將程序源代碼“翻譯”成目標(biāo)代碼，因

此其目標(biāo)程序可以脫離其語言環(huán)境獨(dú)立執(zhí)行。

e現(xiàn)在大多數(shù)的編程語言都是編譯型的。

圖5.2用編譯方式執(zhí)行一個源程序的過程

編譯連接計(jì)算

辨（2）解釋類：應(yīng)用程序源代碼一邊由相應(yīng)語言

的解釋器“翻譯”成目標(biāo)代碼，一邊執(zhí)行。

器缺點(diǎn)是：效率比較低，而且不能生成可獨(dú)立執(zhí)

行的可執(zhí)行文件，應(yīng)用程序不能脫離其解釋器,

但這種方式比較靈活，可以動態(tài)地調(diào)整、修改

應(yīng)用程序。

圖5.3用解釋方式執(zhí)行一個源程序的過程

5.1.3程序設(shè)計(jì)語言的選擇

(1)系統(tǒng)用戶的要求

如果所開發(fā)的系統(tǒng)由用戶負(fù)責(zé)維護(hù)，用戶通常要求用

他們熟悉的語言書寫程序。

(2)可以使用的編譯程序

運(yùn)行目標(biāo)系統(tǒng)的環(huán)境中可以提供的編譯程序往往限制

了可以選用的語言的范圍。

(3)可以得到的軟件工具

如果某種語言有支持程序開發(fā)的軟件工具可以利用，

則目標(biāo)系統(tǒng)的實(shí)現(xiàn)和驗(yàn)證都變得比較容易。

(4)工程規(guī)模

(5)程序員的知識

完全掌握一種新語言需要實(shí)踐。

(6)軟件可移植性要求

如果目標(biāo)系統(tǒng)將在幾臺不同的計(jì)算機(jī)上運(yùn)行，或者預(yù)

期的使用壽命很長，那么選擇一種標(biāo)準(zhǔn)化程度高、程序

可移植性好的語言就是很重要的。

(7)軟件的應(yīng)用領(lǐng)域

選擇語言時應(yīng)該充分考慮目標(biāo)系統(tǒng)的應(yīng)用范圍。

5.2C語言

<>5.2.1C語言簡介

黔在C語言誕生以前，系統(tǒng)軟件主要是用匯

編語言編寫的。由于匯編語言程序依賴

于計(jì)算機(jī)硬件，其可讀性和可移植性都

很差；但一般的高級語言又難以實(shí)現(xiàn)對

計(jì)算機(jī)硬件的直接操作（這正是匯編語

言的優(yōu)勢），于是人們盼望有一種兼有

匯編語言和高級語言特性的新語言。

金七十年代早期，美國貝爾實(shí)驗(yàn)室的Dennis

Ritchie研制出了C語言。C語言同時具有匯編語

言和高級語言的優(yōu)點(diǎn)，其特點(diǎn)是：語言簡潔、

緊湊，使用方便、靈活；運(yùn)算符極其豐富，可

移植性好，可以直接操縱硬件；生成的目標(biāo)代

碼質(zhì)量高，可移植性好（較之匯編語言），程

序執(zhí)行效率高。

鉛80年代初，美國國家標(biāo)準(zhǔn)化協(xié)會（ANSI）,制

定了ANSIC標(biāo)準(zhǔn)（1989年再次做了修訂）。目

前，在微機(jī)上廣泛使用的C語言編譯系統(tǒng)有

MicrosoftC、TurboC、BorlandC等。雖然它

們的基本部分都是相同的，但還是有一些差異,

所以請注意所使用的C編譯系統(tǒng)的特點(diǎn)和規(guī)定。

LC語言程序的總體結(jié)構(gòu)

辨一個完整的C語言程序，是由一個main。函數(shù)

(又稱主函數(shù))和若干個其它函數(shù)結(jié)合而成的,

或僅用一個main。函數(shù)構(gòu)版。

爵【例5,1】僅由main。函數(shù)構(gòu)成的C語言程序。

?/*僅由main。函數(shù)構(gòu)成的C語言程序示例*/

?main()

?{printfCcThisisaCprogram.\n^)；

0)

0程序運(yùn)行結(jié)果為：

金ThisisaCprogram.

【怫a】

■【例5.2】由main。函數(shù)和1個其它函數(shù)max()

構(gòu)成的c語言程序。

?intmax(intx,inty)

e{return(x>y?x:y);}

.main()

辨{intnuml,num2;

卷printf(ctInputthefirstintegernumber:");

辨scanf("％d”，&numl);

辨printfC4Inputthesecondintegernumber:9,);

?scanf("％cT,&num2);

?printf("max=%d\rT,max(numl,num2));

籍程序運(yùn)行情況：

Inputthefirstintegernumber:6一」

Inputthesecondintegernumber:9一」

max=9

齡由上面的程序可知：函數(shù)是c語言程序

的基本單位。main。函數(shù)的作用，相當(dāng)

于其它高級語言中的主程序；其它函數(shù)

的作用，相當(dāng)于子程序。

一個C語言程序，總是從main。函數(shù)開

始執(zhí)行，而不論其在程序中的位置。當(dāng)

主函數(shù)main。執(zhí)行完畢時，亦即程序執(zhí)

行生畢。習(xí)慣上，將主函數(shù)main。放在

最前面。

2.函數(shù)的一般結(jié)構(gòu)

?任何函數(shù)（包括主函數(shù)main。）都是由函數(shù)說明和函

數(shù)體兩部分組成。其一般結(jié)構(gòu)如下：

非［函數(shù)類型］函數(shù)名（函數(shù)參數(shù)表）函數(shù)

說明部分

?｛說明語句部分；

給執(zhí)行語句部分；函數(shù)體部分

辨）

0函數(shù)說明由函數(shù)類型（可缺省）、函數(shù)名和函數(shù)參數(shù)

表三部分組成，其中函數(shù)參數(shù)表的格式為：

?數(shù)據(jù)類型形參［,數(shù)據(jù)類型形參2……］

522C語言的組成

等1.C語言的數(shù)據(jù)類型

-C語言的數(shù)據(jù)類型可分類如下：

金（1）基本類型：分為整型、實(shí)型（又稱浮點(diǎn)

型）、字符型和枚舉型四種。

齡（2）構(gòu)造類型：分為數(shù)組類型、結(jié)構(gòu)類型和共

用類型三種。

船（3）指針類型。

?（4）空類型。

啰C語言中的數(shù)據(jù)，有常量和變量之分，它們分

別屬于上述這些類型。

2,常量和變量

e在程序運(yùn)行過程中，其值不能被改變的量稱為

常量。常量的類型有：整型常量、實(shí)型常量、

字符常量和符號常量。常量的類型，可通過書

寫形式來判別。

器在程序運(yùn)行過程中，其值可以被改變的量稱為

變量。變量有兩個要素：

齡（1）變量名。每個變量都必須有一個名字—變

量名，變量命名遵循標(biāo)識符命名規(guī)則。

齡（2）變量值。在程序運(yùn)行過程中，變量值存儲在

內(nèi)存中。在程序中，通過變量名來引用變量的

值。

0-WIK-MPIWI-

3.語句

據(jù)程序是由一行一行的語句(statement)所

組成的。語句是程序最小的可執(zhí)行單元,

將這些可執(zhí)行單元組合起來，可以構(gòu)成

程序塊、子程序、函數(shù)、模塊、類…等

更高等的可執(zhí)行單元。

喘語句是由關(guān)鍵字(Keyword)＞標(biāo)識符

(Identifier)及特殊符號所組成的。

4.關(guān)鍵字

器關(guān)鍵字(Keyword)是由英文字母所組合而

成的，C語言的關(guān)鍵字共有32個，根據(jù)關(guān)

鍵字的作用，可分其為數(shù)據(jù)類型關(guān)鍵字、

控制語句關(guān)鍵字、存儲類型關(guān)鍵字和其

它關(guān)鍵字四類。

器關(guān)鍵字又稱為保留字，是由C內(nèi)部定義的,

其用途在指示程序如何運(yùn)作。其用法C都

有所規(guī)定，必須遵循這些規(guī)定，否則會

產(chǎn)生錯誤。

啰（1）數(shù)據(jù)類型關(guān)鍵字（12個）：char,double,

enum,float,int,long,short,signed,struct,

union,unsigned,void

黔（2）控制語句關(guān)鍵字（12個）：break,case,

continue,default,do,else,for,goto,if,

return,switch,while

能（3）存儲類型關(guān)鍵字（4個）：auto,extern,

register,static

齡（4）其它關(guān)鍵字（4個）：const,sizeof,typedef,

volatile

標(biāo)識符

0除了C預(yù)先定義的關(guān)鍵字之外，可以自己定義新字，例

如：Do_It_Yourself>M$、kj…,這些自己定義出來的

字稱為標(biāo)識符。定義標(biāo)識符時，必須合乎C的規(guī)定，C

對于定義標(biāo)識符的規(guī)定如下：

給（1）標(biāo)識符由英文字母、中文字、數(shù)字及下劃線構(gòu)成。

辨（2）標(biāo)識符的第一個字符必須是英文字母、中文字、或

是下劃線，例如以下都是正確的標(biāo)識符：A、x、CD、

sun、力口油站、_計(jì)數(shù)器…。

給（3）標(biāo)識符的第二個以后的字符可以是英文字母、中文

字、下劃線或是數(shù)字，例如：A錢、每個_500_元、

_520_...o

辨（4）若標(biāo)識符的第一個字符是下劃線（_）,則標(biāo)識符之

中須含有英文字母、中文字、或數(shù)字，例如_、、

—…都不能當(dāng)作標(biāo)識符。

6.特殊符號

能C所使用的特殊符號很多，在鍵盤上，除

了英文字母之外，其它符號C幾乎都會使

用到，例如+、一、*、/這幾個符號分

別表示算術(shù)運(yùn)算的加減乘除。

j

5.2.3碟程序的語句

辨了解語句的組成元素之后，下面介紹C

語言中常見的語句種類。

給與其它高級語言一樣，C語言也是利用

函數(shù)體中的可執(zhí)行語句，向計(jì)算機(jī)系統(tǒng)

發(fā)出操作命令。按照語句功能或構(gòu)成的

不同，可將C語言的語句分為五類。

a1.空語句

非空語句僅由一個分號構(gòu)成。顯然，空語句什么

操作也不執(zhí)行。

?2.變量聲明語句

器在預(yù)設(shè)的情況下，程序所使用的可變數(shù)據(jù)（稱

為“變量”（variable））都必須先聲明才可以使

用，假設(shè)我們想利用X來存放整數(shù)類型的數(shù)據(jù),

那么須先利用以下語句聲明變量X：

?intX;

黔以語句的組成元素來說，語句中的Int是關(guān)鍵字,

而X則是定義的變量的標(biāo)識符。

辨3.表達(dá)式語句

器表達(dá)式語句由表達(dá)式后加一個分號構(gòu)成。最典

型的表達(dá)式語句是，在賦值表達(dá)式后加一個分

號構(gòu)版的賦值語句。例如，"num=5"是一個

賦值表達(dá)式，而“num=5;"卻是一個賦值語句。

e在外觀上，賦值語句跟數(shù)學(xué)的方程式類似，例

如：

0X=123;

辭但賦值語句不是數(shù)學(xué)的方程式。在數(shù)學(xué)的方程

式中，上面的X及Y稱為未知數(shù)，而程序語言則

將上面的X及Y稱為變量，變量是一個可存放數(shù)

據(jù)的地方，如圖54所示。

圖5.4變量與數(shù)據(jù)的存儲

?此變量叫X'

X=123X123此位置存放X的值

舂對“X=123”語句來說，是把等號右邊

的數(shù)據(jù)存放到等號左邊的變量X所對應(yīng)的

存儲單元中。這個語句中的號，和

數(shù)學(xué)上的等號的意義是大不相同的，例

如：A=A+2這個語句在數(shù)學(xué)上是不成

立的，而在計(jì)算機(jī)程序里，卻是合法的,

相反的，AX2=30這個式子在數(shù)學(xué)上是

成立的，但是在C程序語言里面卻是錯誤

的，因?yàn)樵贑程序語言里面，號左邊

必須是一個變量名稱，而不能是算術(shù)表

達(dá)式。

圖5.5X=Y+10的運(yùn)行過程

(1)取出Y的“值”

②運(yùn)算2+10=12

1(3)放入X的“地址”

華圖5.5表示了“X二丫+10”的運(yùn)算過

程。

◎因止匕，A=A+2這個語句的含意是：將變量A的

存儲單元中所存放的數(shù)據(jù)取出來加上2之后，

再存回A的存儲單元的意思。

4.控制語句

辨控制語句完成一定的控制功能。C語言

只有9條控制語句，又可細(xì)分為三種：

0(1)選擇結(jié)構(gòu)控制語句

器if()?else?，switch。?

(2)循環(huán)結(jié)構(gòu)控制語句

do?while。，for()?,while。?，break,

continue

辨(3)其它控制語句

goto,return

器在C語言中，除實(shí)現(xiàn)順序、選擇和循環(huán)三

種基本結(jié)構(gòu)的9條控制語句外，輸入輸出

操作均由標(biāo)準(zhǔn)庫函數(shù)（不是C語言的組成

部分）來實(shí)現(xiàn)。學(xué)習(xí)C語言，不僅要學(xué)習(xí)

這9條控制語句和各種運(yùn)算符，而且要學(xué)

習(xí)并掌握常用標(biāo)準(zhǔn)庫函數(shù)的使用。

5.復(fù)合語句

辨復(fù)合語句是由大括號括起來的一組(也

可以是1條)語句構(gòu)成。例如：

啰main()

{……

{……}/*復(fù)合語句。

注意：右括號后不需要分號。*/

5.2.4函數(shù)調(diào)用

辨函數(shù)調(diào)用語句由一次函數(shù)調(diào)用加一個分

號(語句結(jié)束標(biāo)志)構(gòu)成。

理例如，printf("ThisisaCfunction

statement,");

齡以上語句會在DOS窗口顯示nThisisaC

functionstatement/1這串字，其中printf

是函數(shù)名稱。

5.3算法與數(shù)據(jù)結(jié)構(gòu)

圖算法與數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序的兩個最基本的

概念。在談到算法與數(shù)據(jù)結(jié)構(gòu)二者的關(guān)系時，

瑞士著名計(jì)算機(jī)科學(xué)家尼可萊沃思(Nikiklaus

Wirth)在1976年曾提出這樣一個公式：

給算法+數(shù)據(jù)結(jié)構(gòu)=程序

午準(zhǔn)確地說，一個程序規(guī)定了某個數(shù)據(jù)結(jié)構(gòu)上的

一個算法。

器算法是程序的核心，它在程序設(shè)計(jì)乃至在整個

計(jì)算機(jī)科學(xué)中都占據(jù)重要地位。

5.3.7算法概述

?計(jì)算機(jī)解題一般可分解成若干操作步驟。

通常把完成某一任務(wù)的操作步驟稱為求

解該問題的算法。程序就是用計(jì)算機(jī)語

言描述的算法。由于組成計(jì)算機(jī)程序的

基本單位是指令，因此計(jì)算機(jī)程序就是

按照工作步驟事先編排好的具有特殊功

能的指令序列，其中每條指令表示一個

或多個操作。

籍韋氏新世界詞典將“算法”定義為：解

決某種問題的任何專門的方法。

歐幾里德算法

<5給定兩個正整數(shù)力和〃求它們的最大公因子

（即能同時整除力和〃的最大正整數(shù)）的步驟

如下：

黎（1）以〃除力并令所得余數(shù)為八，必小于〃；

聶（2）若r=0算法結(jié)束，輸出結(jié)果〃，否則繼續(xù)

步驟3；

老（3）將/7置換為/77,，置換為〃并返回步驟1繼

續(xù)進(jìn)行；

為歐幾里德算法既表述了一個數(shù)的求解過程，同

時又表述了一個判定過程。該過程可以判定刀

和〃是互質(zhì)的，即除1以外力和〃沒有公因子

這個命題的真假。

i.算法的性質(zhì)

器(1)有窮性：一個算法必須總是(對任何合法的輸入

值)在執(zhí)行有限步之后結(jié)束。換言之，任何算法必須

在有限時間內(nèi)完成。

0而且每一步都可在合理的有窮時間內(nèi)完成。

器(2)確定性：算法中的每個步驟都必須有明確的定義,

不允許存在多義性和模棱兩可的解釋。

0(3)能行性：算法中描述的每步操作都應(yīng)是可執(zhí)行的。

例如，當(dāng)B=0時A/B就無法執(zhí)行，不符合能行性的要

求。

?(4)輸入：一個算法必須有0個(自動生成初始數(shù)據(jù))

或多個輸入。

*(5)輸出：一個算法必須產(chǎn)生一個或多個輸出信息。

2.算法的描述

辭算法是對解題過程的精確描述。定義解

決問題的算法對程序員來說通常是最具

挑戰(zhàn)性的任務(wù)，它既是一種技能又是一

門藝術(shù)，要求程序員懂得結(jié)構(gòu)化程序設(shè)

計(jì)概念并具有創(chuàng)造性。對算法的描述是

建立在語言基礎(chǔ)之上的。在將算法轉(zhuǎn)化

為高級語言源程序之前，通常先采用文

字或圖形工具來描述算法。文字工具如

自然語言、偽代碼等，圖形工具如傳統(tǒng)

流程圖、N—S流程圖等。

(1)自然語言

席自然語言是人們?nèi)粘Ｋ玫恼Z言，使用

自然語言不用專門訓(xùn)練，所描述的算法

也通俗易懂。然而其缺點(diǎn)也是明顯的：

首先是由于自然語言的歧義性容易導(dǎo)致

算法執(zhí)行的不確定性；其次是由于自然

語言表示的串行性，因此當(dāng)一個算法中

循環(huán)和分支較多時就很難清晰地表示出

來；此外，自然語言表示的算法不便轉(zhuǎn)

換成用計(jì)算機(jī)程序設(shè)計(jì)語言表示的程序。

(2)傳統(tǒng)流程圖

⑤多情況選擇型

(CASE型)

③先判定型循環(huán)④后判定型循環(huán)

(DO-WHILE)(DO-UNTIL)

辨復(fù)合語句的性質(zhì)：

耶(1)在語法上和單一語句相同，即單一語

句可以出現(xiàn)的地方，也可以使用復(fù)合語

句。

齡(2)復(fù)合語句可以嵌套，即復(fù)合語句中也

可出現(xiàn)復(fù)合語句。

?ANSI(AmericanNationalStandardsInstitute)

頒布了流程圖的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)規(guī)定了用來表

示程序中各種操作的流程圖符號。例如，流程

圖只能使用圖5,6所給出的五種基本控制結(jié)構(gòu)。

通常，在流程圖中用流程線(帶箭頭的實(shí)線)

來連接大部分圖框，這些流程線表示了程序的

執(zhí)行順序。

等流程圖可以很方便地表示順序、選擇和循環(huán)結(jié)

構(gòu)，因此可以表示任何程序的邏輯結(jié)構(gòu)。另外，

用流程圖表示的算法不依賴于任何具體的計(jì)算

機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語言，從而有利于不同環(huán)

境的程序設(shè)計(jì)。流程圖對算法的描述優(yōu)于其他

語言，直觀形象，易于理解，已經(jīng)為世界各國

的程序設(shè)計(jì)人員普遍使用。

(3)N—S流程圖

PP

A=1=2

BAA

B一

1AlA2........./

①順序型②選擇型

⑤多分支選擇理

DQ—陽ILEP

S(CASE型)

S

DO-UNTILP

③WHILE重復(fù)型④UNTIL重復(fù)型

逑N—S流程圖又稱為結(jié)構(gòu)化流程圖，于1973年

由美國學(xué)者I.Nassi和B?Shneiderman提出。

與傳統(tǒng)流程圖不同，N—S圖不用帶箭頭的流程

線來表示程序流程的方向。采用一系列矩形框

來表示各種操作，全部算法寫在一個大的矩形

框內(nèi)，在大框內(nèi)還可以包含其它從屬于它的小

框，這些框一個接一個從上向下排列，程序流

程的方總是從上向下。如圖5.7所示。

:;N—S結(jié)構(gòu)化流程圖比較適合于表達(dá)三種基本結(jié)

構(gòu)，適于結(jié)構(gòu)化程序設(shè)計(jì)，因此很受程序員歡

迎。

(4)偽代碼

給偽代碼，是指不能夠直接編譯運(yùn)行的程

序代碼，它是用介于自然語言和計(jì)算機(jī)

語言之間的文字和符號來描述算法和進(jìn)

行語法結(jié)構(gòu)講解的一個工具。它表面上

很像高級語言的代碼，但又不像高級語

言那樣要接受嚴(yán)格的語法檢查。它比真

正的程序代碼更簡明，更貼近自然語言。

它不用圖形符號，因此書寫方便、格式

緊湊、易于理解，便于向計(jì)算機(jī)程序設(shè)

計(jì)語言算法程序過渡。

求解超時工資算法的偽代碼

MAINMODULE：〃主模塊

CALLinitialization//初始化

CALLProcess〃處理

CALLWrap-UP〃打印輸出

END

PROCESSMODULE：〃處理模塊

DOWHILENotEOF〃開始循環(huán)

CALLReadaRecord〃讀入一個記錄

CALLCalculate〃計(jì)算

CALLAccumulateTotals〃累加到總和

ENDDO

RETURN

令CALCULATEOVERTIMEPAYMODULE：〃計(jì)算超時工資模塊

IFOvertimeHours>0THEN〃如果超時工作

OvertimePay=OvertimeHours*1.5*PayRate

?〃超時工資=超時小時數(shù)*1.5*超時工作每小時報(bào)酬

給ELSE〃否則

?OvertimePay=0〃超時工資為0

ENDIF

?RETURN

e【例5.1】求1+2+3+…+100之和，分

別用傳統(tǒng)流程圖、N—S流程圖及自然語

言描述其算法，并將該算法轉(zhuǎn)化為C語言

源程序。

齡設(shè)變量x表示加數(shù)，y表示被加數(shù)。

(a)傳統(tǒng)流程圖(b)N-S流程圖

<W1)采用圖形工具描述算法如圖5.8所

/pSO

e(2)采用自然語言描述算法如下：

辨將1賦值給X

公將2賦值給R

華將x與y相加結(jié)果存放在x中

您將y加1結(jié)果存放在y中

有若y小于或等于io。轉(zhuǎn)到步驟3繼續(xù)執(zhí)行,

否則算法結(jié)束，結(jié)果為x

器(3)將上述算法轉(zhuǎn)化為C語言源程序:

給main()

?{intX,Y;

辱X=l;

?Y=2;

?while(Y<=100)

》X=X+Y;

>Y=Y+1;

?printf(n%dn,X);

?I

【例5.2】漢諾塔問題

?印度的一座神廟里，由一個銅座支撐著三根寶

石柱子。在第一根柱子上，按照從大到小的順

序套放著64個直徑大小不一的金盤。現(xiàn)在要

將第一根柱子上的64個盤子借助第二根柱子

全部移到第三根柱子上。在移動時應(yīng)遵守下面

的規(guī)則：

籍1每次只能移動一個盤子。

能2盤子只能在三根柱子上移動，不能放在其他

地方。

靠3在移動過程中，必須始終保持大盤在下，小

盤在上。

器當(dāng)這64個盤子全部移到第三根柱子上，世界

末日就要到了。這就是著名的漢諾塔問題。

華漢諾塔問題只能用遞歸方法而不能用其

他方法來求解。所謂遞歸就是將一個較

大的問題歸結(jié)為一個或多個比原問題簡

單，且在結(jié)構(gòu)上與原問題相同子問題的

求解方法。遞歸是計(jì)算學(xué)科中的一個重

要概念。

尊根據(jù)遞歸方法，可以將64個盤子的漢諾塔問

題轉(zhuǎn)化為求解63個盤子的漢諾塔問題。如果

63個盤子的漢諾塔問題能夠解決，則可以先

將63個盤子先移動到第二個柱子上再將最后

一個盤子直接移動到第三個柱子上，最后又一

次將63個盤子從第二個柱子移動到第三個柱

子上這樣則可以解決64個盤子的漢諾塔問題。

依此類推，63個盤子的漢諾塔求解問題可以

轉(zhuǎn)化為62個盤子的漢諾塔求解問題，62個盤

子的漢諾塔求解問題又可以轉(zhuǎn)化為61個盤子

的漢諾塔求解問題，……直到1個盤子的漢諾

塔求解問題。再由1個盤子的漢諾塔的求解求

出2個盤子的漢諾塔直到解出64個盤子的

河涅性I、吊旦而

靠下面用C語言對該問題的求解算法進(jìn)行描述:

&hanoi(intn,charleft,charmiddle,charright)

懿if(n==1)move(1,one,three);

0else{

懿hanoi(n-1,left,right,middle);

0move(1,left,right);

&hanoi(n-1,middle,left,right);

?}}

給注：〃表示〃個盤子的漢諾塔問題，left表示第

一個柱子，middle表示第二個柱子，right表

示第三個柱子。函數(shù)hanoi(n-1,left,right,middle)

表示n-1階漢諾塔從第一個柱子借助第三個柱

子先移到第二個柱子上，函數(shù)

move(1,left,_,right)表示將第一個柱子上最后一

個盤手直接放到第三個柱子上，函數(shù)hanoi(n-

1,middle,left,rignt)表示第n-1個盤子從第二個

柱子借助第一個柱子移到第三個柱子上。

4,算法設(shè)計(jì)的基本策略思想

卷可以看到：用計(jì)算機(jī)求解一個實(shí)際問題,

首先要從這個問題中抽象出一個數(shù)學(xué)模

型，然后設(shè)計(jì)一個解此數(shù)學(xué)模型的算法,

根據(jù)算法編寫程序，經(jīng)過調(diào)試、編譯、

連接和運(yùn)行，完成該問題的求解。所謂

從實(shí)際問題中抽象出一個數(shù)學(xué)模型，就

是要用數(shù)學(xué)的方法抽象其本質(zhì)的內(nèi)容，

實(shí)現(xiàn)對該問題的正確認(rèn)識。

靠對大型問題進(jìn)行算法設(shè)計(jì)，一般采用

“自頂向下，逐步求精”的方法，把大

問題分解為若干小問題，逐步求精。大

型問題的算法設(shè)計(jì)，可歸納為六個基本

策略思想。分別為：分割求解法、動態(tài)

規(guī)劃法、子目標(biāo)法、圖的搜索法、回溯

法、分支與界限法。

(1)分割求解法。

?分而治之的策略思想。它把一個大問題

劃分為原問題的較小子問題，先求出各

子問題的解答，然后把各子問題的解答

合并成整個問題的解。因?yàn)橛煞指罘óa(chǎn)

生的子問題的大小，往往是原問題的較

小規(guī)模，因而通常是遞歸地使用這種方

法。

靠對所有的子問題都進(jìn)行解答。計(jì)算過程

是從小的子問題到較大的子問題，每次

的答案存入一個表格中，作為下面處理

問題的基礎(chǔ)。每個子問題的解決依賴于

一系列子問題的結(jié)果。如何找出后面的

子問題，要依賴于前面一系列子問題的

遞推關(guān)系式，這就是動態(tài)規(guī)劃策略的核

心。

（3）子目標(biāo)法

律就是倒推法。即從某個目標(biāo)或解出發(fā)，

倒推到這個問題的初始陳述。也就是從

某個已知的特定解出發(fā)，反過來求這個

解與已知條件之間存在的關(guān)系，從而得

到一般解的方法。

(4)圖的搜索法

O如果把問題的求解過程用圖或樹這種結(jié)

構(gòu)來描述，即圖中的每一個節(jié)點(diǎn)代替問

題的狀態(tài)，節(jié)點(diǎn)間的連線表示某種可操

作的規(guī)則，那么問題的求解空間就可由

隱含圖來描述。圖的搜索方式就是用某

種策略選擇可操作的某種規(guī)則，并把狀

態(tài)過程用圖結(jié)構(gòu)記錄下來，一直到得出

解為止，也就是從隱含圖中搜索除含有

解路徑的子圖來。

①回溯法

器在問題的求解過程中，有時會發(fā)現(xiàn)使用某一不

適合的操作會阻撓或延遲到達(dá)目標(biāo)的過程。在

這種情況下，需要有這樣的控制策略：先試一

試某一操作，如果以后發(fā)現(xiàn)這個操作不適合，

則允許退回去，另選一個操作來進(jìn)行。這就是

回溯法的控制策略。

0回溯法本質(zhì)是一種搜索算法，但和圖的搜索算

法不同，回溯法在搜索過程中不保存完整的搜

索樹的結(jié)構(gòu)，只記住當(dāng)前工作的一條路徑，回

溯就是對這條路徑進(jìn)行修正；圖的搜索方式則

在搜索過程中記憶下完整的搜索樹。

(6)分支界限法

籍分支界限法的設(shè)計(jì)策略是：利用分支、

限界的方法構(gòu)造一棵搜索樹，求出搜索

樹中每個節(jié)點(diǎn)上的實(shí)際花費(fèi)函數(shù)，求出

花費(fèi)函數(shù)最大(小)值的那種結(jié)構(gòu)。這

就是說，分支界限法是建立一個局部路

徑(或分支)的隊(duì)列。每次都有限擴(kuò)展

當(dāng)前具有最大(小)消耗值分支路徑的

端節(jié)點(diǎn)n(其估價函數(shù)為f(n)=g(n)),直

到生成含有目標(biāo)節(jié)點(diǎn)的路徑為止。

5.算法分析

給解一個問題往往有若干不同的算法，這些算法

決定著根據(jù)該算法編寫的程序性能的好壞。在

保證算法正確性的前提下，如何確定算法的優(yōu)

劣就是一個值得研究的課題。

給在算法的分析中一般應(yīng)考慮以下3個問題：

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

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

e(3)算法是否便于閱讀修改和測試。

等算法時間復(fù)雜度是指算法中有關(guān)操作次

數(shù)，用T(n)表示。丁為英文單詞Time的

第一個字母，T(n)中的。表示問題規(guī)模的

大小。如在累加乘和中。表示待加數(shù)的

個數(shù)，在矩陣相加問題中。表示矩陣的

階數(shù)，在圖中。表示頂點(diǎn)數(shù)等。

舂例如，在上面的漢諾塔問題中，考慮當(dāng)n=64

時，需要移動多少次，要用多少時間。根據(jù)上

面的算法，n個盤子的漢諾塔問題需要移動的

盤子數(shù)是n-1個盤子的漢諾塔,問題需要移動的

盤子數(shù)的2倍加1于是：

0h(n)=2h(n-1)+1

器=2(2h(n-2)+1)+1=22h(n-2)+2+1

有=23h(n-3)+22+2+1

0=2nh(0)+2n-1+..+22+2+1

0=2n-1+...+22+2+1=2n-1

辭因此要完成漢諾塔的搬遷需要移動盤子的次數(shù)

為：

<>264-1=18446744073709551615

酷如果每秒移動一次，也需要花費(fèi)大約5849億

年的時間。假定計(jì)算機(jī)以每秒1000萬個盤子

的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的

時間。由此可知，理論上可以計(jì)算的問題在實(shí)

際上并不一定能行。這是屬于算法復(fù)雜性方面

的研究內(nèi)容。

察漢諾塔問題主要講的是算法的時間復(fù)雜性。關(guān)

于漢諾塔問題算法的時間復(fù)雜度可以用一個指

數(shù)函數(shù)0(2〃)來表示。顯然，當(dāng)〃很大(如

10000)時，計(jì)算機(jī)是無法處理的。而在算法

的時間復(fù)雜度的表示函數(shù)是一個多項(xiàng)式，如

0("2)時則可以處理。

?對于較復(fù)雜的算法，應(yīng)將它分成容易估算的幾

個部分后計(jì)算整個算法的時間復(fù)雜度。最好不

要采用指數(shù)級和階乘級的算法，而應(yīng)盡可能選

用多項(xiàng)式級或線性級等時間復(fù)雜度較小的算法。

另外還要在算法最好、平均和最壞的情況下區(qū)

別執(zhí)行效率的不同。

繪一個問題求解算法的時間復(fù)雜度大于多

項(xiàng)式如指數(shù)函數(shù)時，算法的執(zhí)行時間將

隨。的增加而急劇增長，以致即使是中

等規(guī)模的問題也不能求解出來。在計(jì)算

復(fù)雜性中將這一類問題稱為難解性問題。

人工智能領(lǐng)域中的狀態(tài)圖搜索問題、解

空間的表示或狀態(tài)空間搜索問題就是一

類典型的難解性問題。

e在計(jì)算復(fù)雜性理論中，將所有可以在多項(xiàng)式時

間內(nèi)求解的問題稱為尸類問題，而將所有在多

項(xiàng)式時間內(nèi)可以驗(yàn)證的問題稱為N尸類問題。尸

類問題采用的是確定性算法，N尸類問題采用

的是非確定性算法。P類問題的算法是N尸類

問題算法的一種特例。

?算法的空間復(fù)雜度是指算法在執(zhí)行過程中所占

存儲空間的大小，用S(n)表示。S為英文單詞

Space的第一個字母。與算法的時間復(fù)雜度相

同，算法的空間復(fù)雜度S(n)也可表示為S(n尸「

(g(n))。

532數(shù)據(jù)結(jié)構(gòu)的基本概念

爭數(shù)據(jù)結(jié)構(gòu)是加工的對象。一個程序要進(jìn)

行計(jì)算或處理，總是以某些數(shù)據(jù)為對象

的。而要設(shè)計(jì)一個好的程序就需將這些

松散的數(shù)據(jù)按某種要求組成一種數(shù)據(jù)結(jié)

構(gòu)。

卷在討論數(shù)據(jù)結(jié)構(gòu)之前，先簡單地介紹幾

個相關(guān)概念。

?1.數(shù)據(jù)：在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)是描述客觀事物的數(shù)

字、字符及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處

理的符號的集合。

等2.數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素。在

計(jì)算機(jī)程序中通常將數(shù)據(jù)元素作為一個整體進(jìn)行處理。

有時，一個數(shù)據(jù)元素由若干個數(shù)據(jù)項(xiàng)組成，在這種情

況下，稱數(shù)據(jù)元素為記錄。例如，一個學(xué)生的基本信

息可以作為一個數(shù)據(jù)元素，其中的每一項(xiàng)（如學(xué)號、

姓名、性別、年齡等）為一個數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)

的不可分割的最小單位。最簡單的數(shù)據(jù)元素僅含有一

個數(shù)據(jù)項(xiàng)。

舂3.數(shù)據(jù)結(jié)構(gòu)：隨著計(jì)算機(jī)應(yīng)用的不斷擴(kuò)展和深入，計(jì)

算機(jī)系統(tǒng)處理的數(shù)據(jù)量越來越大，許多數(shù)據(jù)并不是相

互孤立的，而是存在著某種相互關(guān)系，即某種組織形

式。所以確切地說，數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)

系，即數(shù)據(jù)的組織形式。

冬每種高級語言都會提供若干種數(shù)據(jù)類型，供用

戶在程序設(shè)計(jì)中直接使用。數(shù)據(jù)類型可以區(qū)分

為簡單類型的構(gòu)造類型兩大類。簡單類型如整

型、實(shí)型、字符型和布爾型，它們僅含有一個

組成成份；構(gòu)造類型如數(shù)組、字符串和記錄，

它們都由多個成份來構(gòu)成。所謂構(gòu)造類型，其

實(shí)就是由高級語言直接提供的預(yù)先定義好的數(shù)

據(jù)結(jié)構(gòu)。而在程序設(shè)計(jì)中，用戶有時必須自行

構(gòu)造各種較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

能任何一種數(shù)據(jù)類型都是值集合和運(yùn)算集合的統(tǒng)

一體。當(dāng)高級語言定義一種數(shù)據(jù)類型時，它不

僅決定了該類型數(shù)據(jù)的取值形式與范圍，同時

決定了在該類型的數(shù)據(jù)上所能執(zhí)行的操作的種

類。所以當(dāng)使用由高級語言提供的數(shù)據(jù)類型時,

用戶只需了解該類型允許使用的值集，以及在

該類型數(shù)據(jù)上可以執(zhí)行的操作集，用不著關(guān)心

它們的存儲和實(shí)現(xiàn)細(xì)節(jié)。而對于用戶自定義的

數(shù)據(jù)結(jié)構(gòu)，則從結(jié)構(gòu)的建立到各種操作的算法,

全都要由用戶自己實(shí)現(xiàn)。換句話說，數(shù)據(jù)結(jié)構(gòu)

本身包含著算法，要通過一定的算法將它建立

或撤消，并實(shí)現(xiàn)施加在其上的各種基本操作，

例如插入或刪除其中的某個數(shù)據(jù)成份等。

j

4.數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

辨數(shù)據(jù)結(jié)構(gòu)主要是研究程序設(shè)計(jì)中計(jì)算機(jī)

所操作的對象以及它們之間的關(guān)系和運(yùn)

算，概括地說是三個方面，即：數(shù)據(jù)的

邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)（或稱物理

結(jié)構(gòu)）及數(shù)據(jù)的運(yùn)算。

(I)數(shù)據(jù)的邏輯結(jié)構(gòu)

?數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏

輯關(guān)系，它只抽象地反映數(shù)據(jù)元素間的

相互關(guān)系，而不考慮數(shù)據(jù)在計(jì)算機(jī)中的

具體存儲方式，是獨(dú)立于計(jì)算機(jī)的。

器根據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)

構(gòu)的一般邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形

結(jié)構(gòu)和圖狀結(jié)構(gòu)(或稱網(wǎng)狀結(jié)構(gòu))。

辱線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的

關(guān)系。如圖5.11(a)所示。一維數(shù)組是最簡

單的線性結(jié)構(gòu)的例子，堆棧、隊(duì)列和鏈表也是

其重要實(shí)例。

給樹形結(jié)構(gòu)形狀如一棵倒置的樹。樹形結(jié)構(gòu)中的

元素之間存在一個對多個的關(guān)系。如圖5.11

(O所示。樹是非線性結(jié)構(gòu)中最重要的一類

數(shù)據(jù)結(jié)構(gòu)，應(yīng)用十分廣泛。如果限制樹的所有

分枝都不超過兩個后繼結(jié)點(diǎn)，便成了二叉樹。

如圖5.11(b)所示。

0圖狀結(jié)構(gòu)中的元素之間存在多個對多個的關(guān)系。

任何兩個結(jié)點(diǎn)之間都可能存在某種聯(lián)系。如圖

5.11(d)所示。圖狀結(jié)構(gòu)是更為靈活、應(yīng)用

面也更寬的一類數(shù)據(jù)結(jié)構(gòu)。

(b)樹形結(jié)構(gòu)(d)圖狀結(jié)構(gòu)

（2）數(shù)據(jù)的存儲結(jié)構(gòu)

?數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在存儲器中的存儲方

式。數(shù)據(jù)的存儲結(jié)構(gòu)也可以說是邏輯結(jié)構(gòu)在計(jì)

算機(jī)存儲設(shè)備上的物理實(shí)現(xiàn)，有時也被稱為數(shù)

據(jù)的物理結(jié)構(gòu)。

e數(shù)據(jù)存儲結(jié)構(gòu)的基本組織方式有：順序存儲結(jié)

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

莓順序存儲結(jié)構(gòu)借助元素在存儲器中的相對位置

來表示數(shù)據(jù)元素的邏輯關(guān)系；而鏈?zhǔn)酱鎯Y(jié)構(gòu)

借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通

常在數(shù)據(jù)元素上增加一個或多個指針類型的屬

性來實(shí)現(xiàn)這種表示方式。

rW、N，hIII|*LIIiwrI*41

(3)數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算(操作)

??建立數(shù)據(jù)結(jié)構(gòu)

卷?撤消數(shù)據(jù)結(jié)構(gòu)

非■插入數(shù)據(jù)元素。在一個給定的數(shù)據(jù)結(jié)構(gòu)中，在指定位置上增添

一個新的元素。

等?刪除數(shù)據(jù)元素。對一個給定的數(shù)據(jù)結(jié)構(gòu)，刪除某個指定節(jié)點(diǎn)。

0更新數(shù)據(jù)元素。在一個給定的數(shù)據(jù)結(jié)構(gòu)中，改變某個元素的值,

它等于插入和刪除兩個操作的組合。

冷■查找數(shù)據(jù)元素。在一個給定的數(shù)據(jù)結(jié)構(gòu)中，找出滿足指定條件

的元素。

0排序。對一個給定的數(shù)據(jù)結(jié)構(gòu)中的所有的元素按照一定的條件

將它們重新排列順序。

給■遍歷。在一個給定的數(shù)據(jù)結(jié)構(gòu)中，從第一個結(jié)點(diǎn)開始，依次訪

問各個結(jié)點(diǎn)，以便進(jìn)行某種處理。每個結(jié)點(diǎn)只能被訪問一次。

辨?判定某個數(shù)據(jù)結(jié)構(gòu)是否為空或是否已達(dá)到最大允許的容量。

等?統(tǒng)計(jì)數(shù)據(jù)元素的個數(shù)。

莓?dāng)?shù)據(jù)的操作是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，但

數(shù)據(jù)操作的具體實(shí)現(xiàn)要在數(shù)據(jù)的存儲結(jié)構(gòu)上進(jìn)

行，所以數(shù)據(jù)的操作與數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲

結(jié)構(gòu)有直接的關(guān)系。每種數(shù)據(jù)結(jié)構(gòu)都有自己的

一個數(shù)據(jù)操作的集合，即除了上面所說的幾種

數(shù)據(jù)操作之外，還有針對自己的結(jié)構(gòu)的數(shù)據(jù)操

作。止匕外，同一種數(shù)據(jù)操作在不同的數(shù)據(jù)結(jié)構(gòu)

上實(shí)現(xiàn)的效率并不相同。例如，插入操作在順

序存儲結(jié)構(gòu)上實(shí)現(xiàn)的效率比在鏈?zhǔn)酱鎯Y(jié)構(gòu)上

實(shí)現(xiàn)的效率更低。

j

5.學(xué)堿叱構(gòu)的目的

辨在計(jì)算領(lǐng)域中，數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)算法

設(shè)計(jì)的基礎(chǔ)，在計(jì)算科學(xué)中占有十分重

要的地位。對于計(jì)算機(jī)應(yīng)用人員來說，

學(xué)會在程序設(shè)計(jì)中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu),

可簡化算法、節(jié)省空間、提高效率。

給例：印度的工程師常使用數(shù)組而不是鏈

表

533最簡單的數(shù)據(jù)結(jié)構(gòu)-線性表

O(1)定義

專線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有

限序列：

專其中n為表中數(shù)據(jù)元素的個數(shù)，定義為

表的長度。線性表中的所有數(shù)據(jù)元素a：

必須是相同的數(shù)據(jù)類型。

||、吧IIII

(2)線性表的邏輯結(jié)構(gòu)特征

爭線性表的邏輯結(jié)構(gòu)特征是：數(shù)據(jù)元素之

間呈線性關(guān)系。

?第1個：無前驅(qū)，有1個后繼；

?最后一個：有1個前驅(qū)，無后繼；

金其它：有1個前驅(qū)，有1個后繼。

3）線性表的存儲結(jié)構(gòu)

靠線性表的存儲結(jié)構(gòu)分為兩類，一類是順序存儲

結(jié)構(gòu)（又稱為靜態(tài)存儲結(jié)構(gòu)），另一類是鏈?zhǔn)?/p>

存儲結(jié)構(gòu)（又稱為動態(tài)存儲結(jié)構(gòu)）。

線性表的順序存儲，是用一組地址連續(xù)的存儲

單元依次存放線性表的數(shù)據(jù)元素，使邏輯上相

鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中,

而數(shù)據(jù)元素之間的關(guān)系由存儲單元的鄰接關(guān)系

唯一確定。這種采用順序存儲結(jié)構(gòu)存儲的線性

表，也稱為順序表。由于線性表中的所有數(shù)據(jù)

元素的數(shù)據(jù)類型是相同的，因此每個元素占用

同樣大小的存儲單元。

給例如線性結(jié)構(gòu)8=(D,R),其中D=

{a,b,c,d,e,f),R={(b,c),

(c,d),(d,a),(a,f),(f,e)}o

將D中的元素存放在以起始地址s開始的

連續(xù)存儲單元中，為敘述簡單，設(shè)每個

數(shù)據(jù)元素(結(jié)點(diǎn))只存放一個字符(即

字符a,b,c,d,ef),每個結(jié)點(diǎn)占一個存儲

單元，其順序存儲結(jié)構(gòu)如圖5.12所示。

圖5.12順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

(a)順序存儲結(jié)構(gòu)(b)鏈?zhǔn)酱鎯Y(jié)構(gòu)

?順序存儲結(jié)構(gòu)的線性表的優(yōu)點(diǎn)是：簡單、直觀，可隨

機(jī)存取任一元素；缺點(diǎn)是如果在數(shù)據(jù)元素中要插入或

刪除一個元素，將要引起在此元素以后的大量元素的

移動，工作量很大。另外，對于長度可變的線性表，

難以確定存儲空間容量。存儲空間太少不夠用，太多

則浪費(fèi)。

?鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個數(shù)據(jù)元素的存儲包括兩部分：

一部分用于存放數(shù)據(jù)元素的值稱為數(shù)據(jù)域，另一部分

用于存放其直接后繼元素的存儲地址，稱為指針域。

通常將數(shù)據(jù)域和指針域兩部分合稱為一個結(jié)點(diǎn)

(node)o在鏈表中，使用指針聯(lián)系元素，鏈表的每

個數(shù)據(jù)元素可以存放在任意存儲單元，相鄰數(shù)據(jù)元素

的存儲空間可以不連續(xù)，線性表中各元素的存儲順序

與元素之間的關(guān)系可以不一致，而數(shù)據(jù)元素之間的關(guān)

系是由指針來確定的。

器采用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表，稱為線性鏈

表。線性鏈表又可因鏈接方式的不同而分為多

種，一般有單鏈表、雙向鏈表和循環(huán)鏈表。以

下只討論單鏈表，簡稱為鏈表。

器在鏈表中，為了確定表中第一個元素的位置，

需要一個指針指向第一個結(jié)點(diǎn)，稱此指針為頭

指針，第一個結(jié)點(diǎn)也稱為頭結(jié)點(diǎn)。為了標(biāo)識最

后一個結(jié)點(diǎn)，將最后一個結(jié)點(diǎn)的指針置為空，

用或"NULL”表示。若線性表為空表時,

則頭指針為空。前述數(shù)據(jù)結(jié)構(gòu)B=(D,R)的

鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖5.12(b)所示，其中head為

頭指針。

有插入、刪除和存取數(shù)據(jù)元素是所有數(shù)據(jù)結(jié)構(gòu)的

基本操作。若對線性表的這些基本操作加以一

定的限制，則形成下面幾種特殊的線性表：

e(1)后進(jìn)先出(LastInFirstOut),簡稱LIFO

的線性表，它的所有插入刪除和存取都是在線

性表的表尾進(jìn)行的。這種限定只能在一端進(jìn)行

插入和刪除的線性表，稱之為堆棧(stack)或簡

稱棧。實(shí)例：堆起的盤子；箱子中的物體；谷

堆。應(yīng)用：遞歸算法的實(shí)現(xiàn)；計(jì)算機(jī)中多重過

程調(diào)用時現(xiàn)場的保存；編程中某些問題的求解

(如老鼠走迷宮問題、背包問題)。

0(2)先進(jìn)先出(FirstInFirstOut),簡稱FIFO

的線性表，它的所有插入都是在線性表的一端

進(jìn)行的，而所有的刪除和存取又都在線性表的

另一端進(jìn)行。這種限定只能在表的一端進(jìn)行插

入，在另一端進(jìn)行刪除的線性表稱為隊(duì)列。實(shí)

例：排隊(duì)隊(duì)列。應(yīng)用：計(jì)算機(jī)的鍵盤緩沖區(qū)實(shí)

現(xiàn)、操作系統(tǒng)中的多進(jìn)程/多任務(wù)管理、網(wǎng)絡(luò)

中數(shù)據(jù)傳輸?shù)拇?并行轉(zhuǎn)換、計(jì)算機(jī)中的硬

件中斷排隊(duì)、銀行業(yè)中的業(yè)務(wù)模擬分析系統(tǒng)。

(3)限定所有插入刪除和存取都在表的兩端進(jìn)

行的線性表。

辨此外，在編程時常用到的數(shù)組也是線性表的推

廣形式之一。

5.4面向?qū)ο蟪绦蛟O(shè)計(jì)語言的基本概念

^傳統(tǒng)的高級語言程序由一個主程序和若

干個子程序及函數(shù)組成，程序運(yùn)行時總

是從主程序開始，由主程序調(diào)用各子程

序和函數(shù)。程序設(shè)計(jì)人員在編寫程序時

必須將整個程序的執(zhí)行順序十分精確地

設(shè)計(jì)好，然后程序按指定的順序執(zhí)行。

所以，傳統(tǒng)的高級語言稱為面向過程的

語言。如BASIC、C、FORTRAN、

PASCAL>Ada等都是典型的過程性語言。

繪傳統(tǒng)的“面向過程”的方法學(xué)是把世界

分成兩個部分，分別認(rèn)知：

器(1)數(shù)據(jù)(Data)：用于描述各種狀態(tài)的

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

障(2)過程(Procedures)：就是操作這些

狀態(tài)數(shù)據(jù)的程序，有時也稱為“算法”。

靠傳統(tǒng)的“面向過程”的方法學(xué)認(rèn)為數(shù)據(jù)是靜態(tài)

的，是不會自行改變的，需要使用各種各樣的

過程來改變數(shù)據(jù)。它采用過程性語言編程，其

主要特征是：程序由“數(shù)據(jù)定義”加上“算法”

組成，IP:程序=數(shù)據(jù)結(jié)構(gòu)+算法。

專“面向?qū)ο蟆钡姆椒▽W(xué)認(rèn)為世界是由各種各樣

的對象（object）組成的，面向?qū)ο蟪绦蛟O(shè)計(jì)

的基本元素是對象，一個對象可以包含數(shù)據(jù)以

及對這些數(shù)據(jù)進(jìn)行的一組操作。每一個對象都

有兩個特征：狀態(tài)（也稱為屬性、數(shù)據(jù)）與行

為（也稱為方法、操作）。

8每個對象都是通過自己的行為來變化自身的狀態(tài)，一

切變化都是對象自身、或?qū)ο箝g的協(xié)調(diào)而產(chǎn)生的。換

句話說，對象中的數(shù)據(jù)僅屬于對象本身，系統(tǒng)中的其

它對象不允許直接對對象中的數(shù)據(jù)進(jìn)行操作，只可以

向?qū)ο蟀l(fā)送消息。程序中的一切操作都是通過向?qū)ο?/p>

發(fā)送消息來實(shí)現(xiàn)的。對象根據(jù)所接收到的消息，啟動

有關(guān)方法來執(zhí)行相應(yīng)的操作，從而達(dá)到訪問對象中數(shù)

據(jù)的目的。

器面向?qū)ο蠓椒ǖ淖畲髢?yōu)點(diǎn)就是可以重用現(xiàn)存的對象，

把對軟件的改動限制在很小的范圍內(nèi)，從而使軟件的

調(diào)試和修改更方便，使軟件更經(jīng)得起變化。在開發(fā)程

序時，面向?qū)ο蠓椒梢源蟠蟮毓?jié)省程序設(shè)計(jì)的時間

?采用面向?qū)ο蠓椒ǎ绦蜷_發(fā)團(tuán)隊(duì)可以采用那些在結(jié)

構(gòu)化程序開發(fā)中所用的分析、設(shè)計(jì)和編程的技術(shù)和工

具。現(xiàn)今，許多開發(fā)人員使用統(tǒng)一建模語言UML

(UnifiedModelingLanguage)。UML包含了用于面

向?qū)ο蠓椒ㄖ羞M(jìn)行分析、設(shè)計(jì)和編制文檔的標(biāo)準(zhǔn)符號

表不法。

器在九十年代后期，對象管理小組OMG(Object

ManagementGroup)采納了UML作為標(biāo)準(zhǔn)。對象管理

小組是一個為面向?qū)ο髴?yīng)用開發(fā)制定指導(dǎo)方針及標(biāo)準(zhǔn)

規(guī)范的國際性組織。除了UML,對象管理小組還采用

CORBA(CommonObjectRequestBroker

Architecture)作為一種程序設(shè)計(jì)標(biāo)準(zhǔn)。CORBA定義了

網(wǎng)絡(luò)中分處于不同程序中的對象相互通信的方法。

5.4.1面向?qū)ο蟾攀?/p>

o1.對象（Object）

?“對象”是面向?qū)ο蟪绦蛟O(shè)計(jì)的核心。在現(xiàn)實(shí)生活中,

對象可泛指任何事物，包括具體實(shí)體（客觀世界中的

任何事物）和抽象概念（主觀世界中的任何事物）。

出在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對象的概念就是對現(xiàn)實(shí)世界

中對象的模型化，它是代碼和數(shù)據(jù)的組合，同樣具有

自己的狀態(tài)和行為。對象的狀態(tài)用數(shù)據(jù)來表示，稱為

對象的屬性；而對象的行為用對象中的代碼來實(shí)現(xiàn)，

稱為對象的方法。總之，任何對象都由狀態(tài)（也稱為

屬性、數(shù)據(jù)）和行為（也稱為方法、操作）組成。換

句話說，一個對象可以包含數(shù)據(jù)及對這些數(shù)據(jù)進(jìn)行訪

問和處理的一組操作。

II-I.IIMLIIiwrI441

2.屬性(Property)

齡屬性用來表示對象的特性。不同的對象有不同的屬性。

例如，一本書有書名、書號、作者、出版社、出版日

期、價格等屬性，這些屬性會因書的不同而不同。

?以VisualBasic為例，VB中的每個對象都有一組特定的

屬性。如文本框的屬性有名稱(Name)、標(biāo)題

(Caption)＞文本內(nèi)容(Text)、字體大小(Font)、是否

可見(Visible)等。一般來說，每個對象的屬性都有

一組默認(rèn)值。對大多數(shù)屬性都可采用系統(tǒng)提供的默認(rèn)

值，當(dāng)默認(rèn)值不能滿足要求時可以由用戶自己來設(shè)置

所需的屬性值。

等對象的屬性反映了對象的狀態(tài)。在程序系統(tǒng)中，屬性

也就是對象所擁有的數(shù)據(jù)。

03.事件驅(qū)動

齡面向?qū)ο蟪绦蛟O(shè)計(jì)語言是事件驅(qū)動的，

程序設(shè)計(jì)人員只需編寫響應(yīng)用戶動作的

程序，而不必考慮每個步驟按什么順序

執(zhí)行。在這種機(jī)制下，不必編寫一個大

型程序，而是建立一個由若干個微小程

序組成的應(yīng)用程序，這些微小的應(yīng)用程

序都可以由用戶操作來觸發(fā)。這樣就使

編程工作變得比較簡單。下面具體講述

幾個相關(guān)概念。

令（1）事件

辱事件（Event）是面向?qū)ο蟪绦蛟O(shè)計(jì)中對應(yīng)于“消息”

的術(shù)語。

給對象的事件，是一種特定的操作，是指由系統(tǒng)事先設(shè)

定的、能被對象識別和響應(yīng)的動作。一個事件可以是

在鍵盤上按鍵、在窗體上單擊鼠標(biāo)、窗體打開或關(guān)閉、

或者向文本框輸入一個值。例如，在VB中，鼠標(biāo)的單

擊（Click）、雙擊（Dblclick）,窗體的裝載（Load）

等都是事件。

卷通常情況下，事件可以是由用戶操作引起的，也可以

是來自系統(tǒng)、其它應(yīng)用程序或應(yīng)用程序內(nèi)部消息觸發(fā)。

每一種對象能識別的事件是不同的。例如窗體能識別

單擊和雙擊事件，而命令按鈕能識別單擊事件卻不能

識別雙擊事件。但是，多數(shù)事件類型為大多數(shù)對象所

共有。例如命令按鈕和窗體都可以對單擊（Click）事

件做出響應(yīng)。

<>(2)事件過程

需響應(yīng)某個事件所執(zhí)行的操作是通過一段程序代

碼來實(shí)現(xiàn)的，這樣的一段程序代碼稱為事件過

程(EventProcedure),也稱為事件字程序。

一個對象能識別一個或多個事件，因此可以使

用一個或多個事件過程對用戶或系統(tǒng)的事件作

出響應(yīng)。但在程序中究竟使用多少事件過程，

則要由設(shè)計(jì)者根據(jù)程序的具體要求來確定。相

同事件發(fā)