第5章計(jì)算機(jī)程序設(shè)計(jì)問(wèn)題引出計(jì)算機(jī)中的軟件是程序的集合。利用計(jì)算機(jī)解決實(shí)際具體問(wèn)題，必須掌握計(jì)算機(jī)程序設(shè)計(jì)。怎樣進(jìn)行程序設(shè)計(jì)？程序設(shè)計(jì)涉及哪些知識(shí)？通常使用的程序設(shè)計(jì)語(yǔ)言有哪些？這都是本章所要討論的問(wèn)題。什么是程序設(shè)計(jì)？常用程序設(shè)計(jì)語(yǔ)言及其類型、程序設(shè)計(jì)語(yǔ)言的構(gòu)成、程序設(shè)計(jì)方法、算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)等。教學(xué)重點(diǎn)教學(xué)要求熟悉：面向過(guò)程和面向?qū)ο蟪绦蛟O(shè)計(jì)方法；C語(yǔ)言的基本構(gòu)成。了解：算法描述、算法設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的基本類型。

掌握：掌握程序設(shè)計(jì)的基本概念?！?.1程序設(shè)計(jì)概念§5.5算法設(shè)計(jì)§5.4程序設(shè)計(jì)方法§5.3程序設(shè)計(jì)語(yǔ)言的成分§5.2程序設(shè)計(jì)語(yǔ)言計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)§5.6數(shù)據(jù)結(jié)構(gòu)本章教學(xué)內(nèi)容§5.1程序設(shè)計(jì)概念

人們做任何事情都有一定的方法和步驟，這個(gè)方法和步驟就是“程序”，而“程序設(shè)計(jì)”就是規(guī)劃這個(gè)程序，其思想和方法與我們寫文章的思想和方法類似。

瑞士著名計(jì)算機(jī)科學(xué)家、Pascal語(yǔ)言的發(fā)明者尼克萊斯·沃斯(NiklausWirth)教授早在1976年提出了這樣一個(gè)公式：

算法＋數(shù)據(jù)結(jié)構(gòu)＝程序這一公式揭示了計(jì)算機(jī)科學(xué)的兩個(gè)重要支柱：算法和數(shù)據(jù)結(jié)構(gòu)的重要性和統(tǒng)一性，算法、數(shù)據(jù)結(jié)構(gòu)和程序，既不能離開數(shù)據(jù)結(jié)構(gòu)去分析問(wèn)題的算法，也不能脫離算法孤立地研究數(shù)據(jù)結(jié)構(gòu)。算法、數(shù)據(jù)結(jié)構(gòu)和程序三者之間密不可分，但又有各自的含義。5.1.1

什么是程序設(shè)計(jì)5.1.1什么是程序設(shè)計(jì)程序是為計(jì)算機(jī)完成特定任務(wù)，利用算法并結(jié)合合適的數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一系列指令的有序集合。它由程序開發(fā)人員根據(jù)具體的任務(wù)需求,使用相應(yīng)的語(yǔ)言,結(jié)合相應(yīng)的算法和數(shù)據(jù)結(jié)構(gòu)編制而成。算法是對(duì)數(shù)據(jù)處理準(zhǔn)確而完整的具體描述，是由基本運(yùn)算規(guī)則和運(yùn)算順序所構(gòu)成的、完整的解題方法和步驟。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，它反映出數(shù)據(jù)類型和數(shù)據(jù)的組織形式。5.1.2程序設(shè)計(jì)步驟

程序設(shè)計(jì)的任務(wù)是利用計(jì)算機(jī)語(yǔ)言把用戶提出的任務(wù)作出描述并予以實(shí)現(xiàn)。程序設(shè)計(jì)的步驟是根據(jù)給出的具體任務(wù)，編制一個(gè)能夠正確完成該任務(wù)的計(jì)算機(jī)程序。以數(shù)值計(jì)算為例，實(shí)現(xiàn)程序設(shè)計(jì)的一般步驟如圖5-1所示。圖5-1程序設(shè)計(jì)步驟示意圖建立文檔分析問(wèn)題設(shè)計(jì)算法編寫程序程序翻譯分析測(cè)試1、分析問(wèn)題

分析問(wèn)題是進(jìn)行程序設(shè)計(jì)的第一步，體現(xiàn)在以下3個(gè)方面:①分析問(wèn)題給定的條件和要求；②分析解決問(wèn)題的思路；③分析程序的輸入、輸出數(shù)據(jù)。5.1.2程序設(shè)計(jì)步驟2、設(shè)計(jì)算法

設(shè)計(jì)算法就是根據(jù)上一步的分析結(jié)果，設(shè)計(jì)出解題的方法和具體步驟。這一步主要進(jìn)行兩項(xiàng)工作：一是將算法設(shè)計(jì)思路、原則和策略寫成概要性的算法框架;

二是規(guī)劃數(shù)據(jù)的組織方式（數(shù)據(jù)描述），就是根據(jù)程序設(shè)計(jì)的目標(biāo)和對(duì)數(shù)據(jù)處理的要求，確定所處理數(shù)據(jù)的表示方法，即數(shù)據(jù)結(jié)構(gòu)。3、編寫程序

根據(jù)算法描述、數(shù)據(jù)結(jié)構(gòu)及其求解步驟，用一種高級(jí)語(yǔ)言編寫出源程序。有了算法描述，將其轉(zhuǎn)換為任何一種高級(jí)語(yǔ)言程序都不困難，這一步驟常稱為“編碼”(coding)。5.1.2程序設(shè)計(jì)步驟4、程序翻譯

用計(jì)算機(jī)語(yǔ)言編寫的程序稱為源程序，計(jì)算機(jī)并不能識(shí)別源程序，必須對(duì)所編輯的源程序進(jìn)行翻譯，形成可執(zhí)行程序。事實(shí)上，翻譯的過(guò)程也是對(duì)源程序進(jìn)行檢查的過(guò)程，檢查源程序的結(jié)構(gòu)、語(yǔ)法、詞法是否正確。只有翻譯通過(guò)了的程序才能執(zhí)行。5、分析測(cè)試運(yùn)行可執(zhí)行程序，可得到運(yùn)行結(jié)果。但是，能得到運(yùn)行結(jié)果，并不意味著程序是正確的。因此，對(duì)所設(shè)計(jì)的程序都要對(duì)結(jié)果進(jìn)行分析，如果存在問(wèn)題，則需要進(jìn)行分析和測(cè)試。5.1.2程序設(shè)計(jì)步驟

（1）分析程序

在程序設(shè)計(jì)中把“y＝x；”錯(cuò)寫為“x＝y(tǒng)；”，程序不存在語(yǔ)法錯(cuò)誤，能通過(guò)編譯，但運(yùn)行結(jié)果顯然與預(yù)期不符，因此要對(duì)程序進(jìn)行分析調(diào)試（Debug——格雷斯.霍普）。調(diào)試過(guò)程就是通過(guò)上機(jī)發(fā)現(xiàn)和排除程序錯(cuò)誤的過(guò)程。在調(diào)試過(guò)程中，不能只看到某一次結(jié)果是正確的就認(rèn)為程序沒有問(wèn)題。例如，求z＝y(tǒng)/x，當(dāng)x＝8，y＝4時(shí)，求出z的值為0.5是正確的，但如果會(huì)出現(xiàn)x＝0的情況，就無(wú)法求出z的值。這說(shuō)明程序中存在有漏洞，需要對(duì)程序進(jìn)行測(cè)試（test）。

（2）測(cè)試程序

測(cè)試就是設(shè)計(jì)多組測(cè)試數(shù)據(jù)，檢查程序?qū)Σ煌瑪?shù)據(jù)的運(yùn)行情況，發(fā)現(xiàn)程序中存在的漏洞，使程序能適用于各種情況。5.1.2程序設(shè)計(jì)步驟

常用的程序測(cè)試方法分為白盒測(cè)試法和黑盒測(cè)試法。①白盒測(cè)試法。也稱為結(jié)構(gòu)測(cè)試法，是基于程序內(nèi)部語(yǔ)句的邏輯結(jié)構(gòu)的測(cè)試。在設(shè)計(jì)測(cè)試數(shù)據(jù)前，仔細(xì)分析程序內(nèi)部的邏輯結(jié)構(gòu)。②黑盒測(cè)試法。不考慮程序內(nèi)部結(jié)構(gòu)，而只考慮程序功能錯(cuò)誤或遺漏、界面錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)錯(cuò)誤、性能錯(cuò)誤等，因而也把黑盒測(cè)試稱為功能測(cè)試。6、建立文檔

在完成上述工作之后，還應(yīng)建立程序文檔，這既是為日后對(duì)程序進(jìn)行修改時(shí)提供參考，也是為用戶使用提供方便。文檔的內(nèi)容包括：程序名稱、程序功能、運(yùn)行環(huán)境、程序的裝入和啟動(dòng)、需要輸入的數(shù)據(jù)、使用注意事項(xiàng)等。程序文檔是軟件的一個(gè)重要組成部分，無(wú)論是系統(tǒng)軟件還是應(yīng)用軟件，建立程序文檔都是非常必要的。利用計(jì)算機(jī)解決問(wèn)題的程序最終都要通過(guò)程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)，我們把這種語(yǔ)言稱為程序設(shè)計(jì)語(yǔ)言（ProgrammingLanguage)。它是人與計(jì)算機(jī)之間進(jìn)行信息交換的共同“語(yǔ)言”,因而也稱為計(jì)算機(jī)語(yǔ)言（ComputerLanguage)。通常，人們把利用計(jì)算機(jī)語(yǔ)言描述執(zhí)行某種任務(wù)的指令(指示計(jì)算機(jī)執(zhí)行各種操作的命令)集合稱為計(jì)算機(jī)程序。

程序設(shè)計(jì)語(yǔ)言是進(jìn)行軟件開發(fā)的工具，無(wú)論是程序設(shè)計(jì)還是軟件開發(fā)，

最終都要利用程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)。程序設(shè)計(jì)語(yǔ)言伴隨著計(jì)算機(jī)硬件的發(fā)展和計(jì)算機(jī)應(yīng)用的普及而飛速發(fā)展。今天，程序設(shè)計(jì)語(yǔ)言的種類繁多，如果按照程序設(shè)計(jì)方法分類，可將其分為面向過(guò)程程序設(shè)計(jì)語(yǔ)言和面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言兩大類?！?.2

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

5.2.1面向過(guò)程程序設(shè)計(jì)語(yǔ)言所謂“面向過(guò)程”語(yǔ)言，是使用這些語(yǔ)言進(jìn)行程序設(shè)計(jì)的過(guò)程是一個(gè)逐步求精的過(guò)程，它是一種傳統(tǒng)式的程序設(shè)計(jì)語(yǔ)言。如果根據(jù)程序設(shè)計(jì)語(yǔ)言的發(fā)展，或按其與硬件的接近程度來(lái)分類，通?？煞譃闄C(jī)器語(yǔ)言、匯編語(yǔ)言和高級(jí)語(yǔ)言３種類型，如圖5-2所示。程序設(shè)計(jì)語(yǔ)言低級(jí)語(yǔ)言高級(jí)語(yǔ)言機(jī)器語(yǔ)言（第一代語(yǔ)言）匯編語(yǔ)言（第二代語(yǔ)言）Fortran、Basic、C等（第三代語(yǔ)言)StucturedQueryLanguage（第四代…)Lisp、Prolog（稱為第五代語(yǔ)言）圖5-2面向過(guò)程程序設(shè)計(jì)語(yǔ)言1、機(jī)器語(yǔ)言（MachineLanguage）

機(jī)器語(yǔ)言是能夠直接與機(jī)器打交道的、用二進(jìn)制代碼表達(dá)的語(yǔ)言。機(jī)器語(yǔ)言中的每一條語(yǔ)句由操作碼和地址碼組成。例如計(jì)算A=8+10，則機(jī)器語(yǔ)言程序如下：1011000000001000(把8存放到累加器A中)0010110000001010（將10與累加器中的8相加,結(jié)果存放到A中）11110100（停止所有操作）

機(jī)器語(yǔ)言的優(yōu)點(diǎn)是：不需要經(jīng)過(guò)翻譯，計(jì)算機(jī)直接執(zhí)行。因此，不僅執(zhí)行速度快，而且所占的存儲(chǔ)空間小。機(jī)器語(yǔ)言的缺點(diǎn)是：由于用二進(jìn)制編程，因而程序編寫、修改、調(diào)式難度大，而且程序的編寫與機(jī)器硬件系統(tǒng)結(jié)構(gòu)有關(guān)。5.2.1面向過(guò)程程序設(shè)計(jì)語(yǔ)言2、匯編語(yǔ)言（AssembleLanguage）

匯編語(yǔ)言是用一些約定的文字、符號(hào)和數(shù)字按規(guī)定格式來(lái)表示各種不同的指令，再用這些指令來(lái)編寫程序。例如，計(jì)算10＋8，匯編語(yǔ)言程序如下：匯編語(yǔ)言的一般格式為：

MOVAX，8H；將8傳送到AX寄存器中MOVBX，AH；將10傳送到BX寄存器中ADDAX，BX；將AX與BX中的數(shù)據(jù)進(jìn)行相加HLT；結(jié)束該匯編程序顯然，使用匯編語(yǔ)言編程比使用機(jī)器語(yǔ)言編程要方面得多。但同樣地，使用匯編語(yǔ)言編程與計(jì)算機(jī)硬件系統(tǒng)有關(guān)。5.2.1面向過(guò)程程序設(shè)計(jì)語(yǔ)言3、高級(jí)語(yǔ)言（HighLevelLanguage）

為了進(jìn)一步實(shí)現(xiàn)程序自動(dòng)化和便于程序交流，使不熟悉計(jì)算機(jī)具體結(jié)構(gòu)的人也能方便地使用計(jì)算機(jī)，人們又創(chuàng)造了高級(jí)語(yǔ)言。高級(jí)語(yǔ)言中的語(yǔ)句一般都采用自然語(yǔ)匯，并且使用與自然語(yǔ)言語(yǔ)法相近語(yǔ)法體系，例如7+8，用高級(jí)語(yǔ)言（如C/C++語(yǔ)言或Fortran語(yǔ)言）描述，則為：x=7；

y=8；z=x+y;5.2.1面向過(guò)程程序設(shè)計(jì)語(yǔ)言請(qǐng)同學(xué)們思考高級(jí)語(yǔ)言與低級(jí)語(yǔ)言相比，具有哪些優(yōu)點(diǎn)？

(1)

(2)

(3)

我們把支持對(duì)象、類、封裝和繼承特性的語(yǔ)言稱為面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言(Object-OrientedProgrammingLanguage,OOPL).

1、Simula語(yǔ)言Simula語(yǔ)言是由挪威的OleDahl和KrystenNygaard等人于1967年提出的，當(dāng)時(shí)取名為Simula67。它主要為模擬離散事件而設(shè)計(jì)，并引入了對(duì)象、類、繼存等概念。5.2.2面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言

2、Smalltalk語(yǔ)言Smalltalk語(yǔ)言的起源可追隨到20世紀(jì)60年代后期，由美國(guó)的Xerox公司PaloAlto研究中心開發(fā)。經(jīng)過(guò)多次重大修改，形成了Smalltalk-80版本。Smalltalk不僅僅是一種程序設(shè)計(jì)語(yǔ)言,而且還是一個(gè)全新的、反映面向?qū)ο笏枷氲膱D形交互式程序設(shè)計(jì)環(huán)境，這也是導(dǎo)致面向?qū)ο蠹夹g(shù)興起的重要原因之一。

3、C++語(yǔ)言

自從1972年AT＆T貝爾實(shí)驗(yàn)室設(shè)計(jì)了C語(yǔ)言，并以之作為UNIX操作系統(tǒng)的程序設(shè)計(jì)語(yǔ)言之后，從個(gè)人計(jì)算機(jī)到巨型計(jì)算機(jī)，各種型號(hào)的計(jì)算機(jī)都廣泛地支持C語(yǔ)言。進(jìn)入20世紀(jì)80年代后，面向?qū)ο蟪绦蛟O(shè)計(jì)方法在程序設(shè)計(jì)領(lǐng)域引起了普遍重視,AT＆T貝爾實(shí)驗(yàn)室的BjarneStroustrup在C語(yǔ)言的基礎(chǔ)上，吸收了OOPL的特點(diǎn)，開發(fā)了面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言C++。C++語(yǔ)言保留了流行C語(yǔ)言的所有成分，是C語(yǔ)言的改進(jìn)或擴(kuò)充。然而，C++語(yǔ)言更應(yīng)該作為一種全新的、完備的程序設(shè)計(jì)語(yǔ)言看待。5.2.2面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言

4、Java語(yǔ)言

Java語(yǔ)言是一種適合分布式計(jì)算的新型面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，由美國(guó)SunMicrosystem公司于1995年5月推出的一個(gè)支持網(wǎng)絡(luò)計(jì)算的、面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，是目前推廣最快的程序設(shè)計(jì)語(yǔ)言。Java語(yǔ)言將面向?qū)ο?、平臺(tái)無(wú)關(guān)性、穩(wěn)定與安全性、多線程等特性集于一身，為用戶提供了良好的程序設(shè)計(jì)環(huán)境，特別適合于Internet的應(yīng)用開發(fā)。Java語(yǔ)言可以看作是C++的派生語(yǔ)言，它從C++語(yǔ)言中繼存了大量的語(yǔ)言成分，但拋棄了C++語(yǔ)言中多余的、容易引起問(wèn)題的功能，增加了多線程、異常處理、網(wǎng)絡(luò)程序設(shè)計(jì)等方面的支持。5.2.2面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言

5、C#語(yǔ)言

一般地說(shuō)，開發(fā)一個(gè)具有相同功能的程序，用C/C++語(yǔ)言的開發(fā)周期比其它語(yǔ)言長(zhǎng)。人們一直都在尋找一種可以在功能和開發(fā)效率之間達(dá)到更好平衡的語(yǔ)言。針對(duì)這種需求，SunMicrosystem公司推出了面向?qū)ο蟮腏ava，后來(lái)Microsoft公司推出了C#（讀作Csharp）語(yǔ)言。C#起源于C語(yǔ)言家族，在更高層次上重新實(shí)現(xiàn)了C/C++。C#簡(jiǎn)化了C/C++的諸多復(fù)雜性,但提供了空的值類型、枚舉、委托、匿名方法和直接內(nèi)存訪問(wèn),這些都是Java所不具備的。使用C#，可以讓程序員快速建立基于微軟網(wǎng)絡(luò)平臺(tái)的應(yīng)用。同時(shí)，C#提供了大量的開發(fā)工具和服務(wù)，以幫助程序員開發(fā)基于計(jì)算和通信的各種應(yīng)用程序。5.2.2面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言§5.3程序設(shè)計(jì)的語(yǔ)言成分

5.3.1

程序的基本結(jié)構(gòu)用C語(yǔ)言編寫的程序稱為C語(yǔ)言源程序，簡(jiǎn)稱C程序。一個(gè)C程序由一個(gè)或多個(gè)函數(shù)組成，最簡(jiǎn)單的C程序只包含一個(gè)main函數(shù)。函數(shù)是由若干條語(yǔ)句根據(jù)功能邏輯構(gòu)成的，語(yǔ)句是由單詞根據(jù)語(yǔ)法規(guī)則構(gòu)成的，而單詞是由基本符號(hào)根據(jù)詞法規(guī)則構(gòu)成的。雖然不同語(yǔ)言的基本結(jié)構(gòu)形式不近相同，但基本設(shè)計(jì)思想是相似的。C語(yǔ)言程序的基本構(gòu)成如圖5-3所示。符號(hào)單詞語(yǔ)句函數(shù)程序圖5-3C語(yǔ)言程序的構(gòu)成【例5-4】編寫程序求三個(gè)整數(shù)中的較大者。#include<stdio.h>//預(yù)處理intmax(intx，inty，intz)//聲明程序中含有自定義函數(shù)voidmain()//主函數(shù){intm；//定義變量的數(shù)據(jù)類型m=max(6，5，4)；//函數(shù)調(diào)用printf(“％d”，m)；}{intmax；if(x>=y)max=x；//將兩個(gè)數(shù)比較取較大值elsemax=y；if(z>max)max=z；//將兩個(gè)數(shù)的較大值與第三個(gè)數(shù)比較returnmax；}5.3.1程序的基本結(jié)構(gòu)

由該示例程序結(jié)構(gòu)可以看出C語(yǔ)言具有如下特點(diǎn)。

(1)main函數(shù)：C程序是由函數(shù)組成的，一個(gè)C語(yǔ)言成不論有多少個(gè)函數(shù)，都有且只能有一個(gè)main函數(shù)(稱為主函數(shù))。不論main函數(shù)在整個(gè)程序中的什么位置,C程序的執(zhí)行總是從main函數(shù)開始的。

(2)預(yù)處理命令：C程序可以使用預(yù)處理命令(如#include)。預(yù)處理命令以“#”開始，一般放在源程序的最前面。

(3)程序注釋：是對(duì)于所包含的代碼比較長(zhǎng)，結(jié)構(gòu)比較復(fù)雜的源程序添加必要的注釋,以幫助他人或程序員本人日后對(duì)原始程序理解。C99標(biāo)準(zhǔn)提供了兩種注釋方法：一種是由“／*”和“*／”括起來(lái)的任意字符串，另一種是由兩個(gè)正斜線“//”開始直到該對(duì)斜線所在的文本行結(jié)束。5.3.1程序的基本結(jié)構(gòu)

1、基本詞法

(1)字符集：是一些可以區(qū)分的最小符號(hào)，是構(gòu)成語(yǔ)言的基本元素。用C編寫程序時(shí)，除字符型數(shù)據(jù)外，其它所有成分都只能由字符集中的字符構(gòu)成。字符集由4種類型字符組成。①英文字母。包括A～Z和a～z。26個(gè)大寫英文字母和26個(gè)小寫英文字母。大寫英文字母A～Z的代碼為65～90，小寫英文字母a～z的代碼為97～122。②數(shù)字字符。是指0～9的10個(gè)阿拉伯?dāng)?shù)字,對(duì)應(yīng)的ASCII代碼為48～57。③特殊字符。＋，-，＊，/，％，＝，_，(，)，～，!，＠，＃，$，＾，＆等。5.3.2程序的基本要素

④轉(zhuǎn)移字符。主要用來(lái)控制打印輸出的字符，不同的語(yǔ)言有不同的控制方法。在C語(yǔ)言中是用“\”來(lái)描述的,例如\n換行(LF)、\t水平制表(HT)、\a響鈴(BEL)、\b退格(BS)、\f換頁(yè)(FF)、\r回車(CR)、\v垂直制表(VT)、\\反斜杠、\’單引號(hào)、\“雙引號(hào)、\?問(wèn)好、\0空格符(NULL)、\ddd三位八進(jìn)制數(shù)、\xhh二位十六進(jìn)制數(shù)。

(2)標(biāo)識(shí)符：是由程序員定義的單詞，表示符號(hào)常量名、變量名、函數(shù)名、類型名、文件名等的字符序列。C語(yǔ)言的標(biāo)識(shí)符是由字母、數(shù)字和下劃線三種字符構(gòu)成的,且第一個(gè)字符必須是字母或下劃線的字符序列。C語(yǔ)言標(biāo)識(shí)符可分為3類：5.3.2程序的基本要素

①關(guān)鍵字。是具有特定含義的標(biāo)識(shí)符，每個(gè)關(guān)鍵字都有固定的含義，用戶不能改變它的用途，因而又把關(guān)鍵字稱保留字。不同的語(yǔ)言具有不同的關(guān)鍵字,ANSIC標(biāo)準(zhǔn)定義了32個(gè)關(guān)鍵字。例如：if（條件）、for（循環(huán)）、int(整型)、short（短型）、long（長(zhǎng)型）、char（符號(hào)型）。②預(yù)定義標(biāo)識(shí)符。預(yù)定義標(biāo)識(shí)符也具有特定含義，如C語(yǔ)言提供的庫(kù)函數(shù)的名字和編譯預(yù)處理命令。但是C語(yǔ)言允許用戶將這類標(biāo)識(shí)符另作他用，改變其原有意義。③用戶自定義標(biāo)識(shí)符。是用戶根據(jù)自己的需要而定義的標(biāo)識(shí)符，如給變量、常量、函數(shù)、文件等對(duì)象命名。用戶標(biāo)識(shí)符不能與關(guān)鍵字同名，也盡量不要與預(yù)定義標(biāo)識(shí)符同名。5.3.2程序的基本要素

2、常量常量是指在程序的執(zhí)行過(guò)程中其值不能被改變的量。程序中的常量不需要類型說(shuō)明就可以直接使用，常量的類型是由常量本身隱含決定的。C語(yǔ)言中,常量的數(shù)據(jù)類型如圖5-4所示。5.3.2程序的基本要素

字符型常量數(shù)值型常量常量整形常量實(shí)行常量字符常量字符串常量圖5-4常量及其數(shù)據(jù)類型

(1)數(shù)值型常量：包括整型常量和字符型常量。①整型常量。整型常量就是整型常數(shù)，如12、-345、0等。②浮點(diǎn)型常量。又稱實(shí)型常量，如3.141256、1.26E5（1.26×105）等。

(2)字符型常量：包括字符常量和字符串常量。①字符常量。由一對(duì)單引號(hào)括起來(lái)的一個(gè)單一字符，如字符‘A’。②字符串常量。由一對(duì)雙引號(hào)括起來(lái)的字符序列，如字符串‘Computer’。5.3.2程序的基本要素

3、變量變量是指在程序的執(zhí)行過(guò)程中其值可以被改變的量，是程序中數(shù)據(jù)的臨時(shí)存放場(chǎng)所。因此，變量代表內(nèi)存中的一塊存儲(chǔ)區(qū)域，該存儲(chǔ)區(qū)域的名稱就是這個(gè)變量名，而該存儲(chǔ)區(qū)域的內(nèi)容則是變量的值。在程序中變量用來(lái)存放初始值、中間結(jié)果或最終結(jié)果。變量一般要先定義然后才能使用，變量定義的一般形式為：數(shù)據(jù)類型名變量名；在C語(yǔ)言中的變量有三種類型：整型變量、實(shí)型變量和字符變量。這些變量不僅使用方法相同，而且都具有三個(gè)基本要素：名字、類型和值。5.3.2程序的基本要素

4、函數(shù)

在進(jìn)行程序設(shè)計(jì)時(shí)，可以把一個(gè)復(fù)雜問(wèn)題按功能劃分為若干個(gè)簡(jiǎn)單的功能模塊，最后由各功能模塊完成程序要完成的功能，這種方法被稱之為模塊化程序設(shè)計(jì)。模塊化程序設(shè)計(jì)是將某些功能語(yǔ)句或某個(gè)算法寫成一個(gè)獨(dú)立的模塊程序，以便反復(fù)使用，從而簡(jiǎn)化程序設(shè)計(jì)，提高程序設(shè)計(jì)效率。C語(yǔ)言中的函數(shù)可分為兩類：一類是系統(tǒng)提供的函數(shù)，稱為系統(tǒng)函數(shù)(庫(kù)函數(shù))；另一類是由用戶根據(jù)需要編寫的函數(shù)，稱為自定義函數(shù)或用戶函數(shù)。用戶函數(shù)不僅要在程序中定義函數(shù)本身，而且必須在主調(diào)用函數(shù)中對(duì)被調(diào)用函數(shù)進(jìn)行類型說(shuō)明,然后才能使用。5.3.2程序的基本要素

1、基本的數(shù)據(jù)類型

任何一個(gè)計(jì)算機(jī)程序都不可能沒有數(shù)據(jù)，數(shù)據(jù)是程序操作的對(duì)象。通常，一種高級(jí)語(yǔ)言都會(huì)定義一些基本的數(shù)據(jù)類型，通常包括整數(shù)類型、實(shí)數(shù)類型和字符類型等。(1)整型：是最簡(jiǎn)單的數(shù)據(jù)類型。整型變量的定義形式為

Int變量名；(2)實(shí)數(shù)類型：又稱浮點(diǎn)數(shù)據(jù)類型，定義形式為：

float變量名；(3)字符類型：用來(lái)存放字符常量，—個(gè)字符變量只能存放一個(gè)字符。在表示字符型數(shù)據(jù)時(shí)，并不是將字符本身的形狀存入內(nèi)存,而是將字符的ASCII碼存入內(nèi)存。定義格式為：

char變量名；5.3.3程序的數(shù)據(jù)類型

2、指針類型

指針是C語(yǔ)言中一種重要的數(shù)據(jù)類型，掌握指針的使用方法，可以編寫出高質(zhì)量的程序，但如果使用不當(dāng)，則會(huì)帶來(lái)“災(zāi)難”性的后果。由于指針類型在程序中存在(潛伏)著一定的危險(xiǎn)性，所以在C#和Java語(yǔ)言中沒再使用指針類型。

3、結(jié)構(gòu)數(shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型是在基本數(shù)據(jù)類型的基礎(chǔ)上構(gòu)造出來(lái)的數(shù)據(jù)類型，主要包括數(shù)組、結(jié)構(gòu)體和用戶自定義類型等。(1)數(shù)組類型：數(shù)組是若干個(gè)相同類型數(shù)據(jù)的集合。(2)結(jié)構(gòu)體類型：是隸屬于同一個(gè)事物的多個(gè)不同類型數(shù)據(jù)的集合，用來(lái)表示具有若干個(gè)屬性的一個(gè)事物，例如學(xué)生信息。5.3.3程序的數(shù)據(jù)類型

1、算術(shù)運(yùn)算符與表達(dá)式程序語(yǔ)言中最常用的算術(shù)運(yùn)算符有：＋(加)、一(減)、＊(乘)、／(除)、％(求余數(shù))由算術(shù)運(yùn)算符和運(yùn)算對(duì)象組成的式子稱為算術(shù)表達(dá)式。算術(shù)表達(dá)式的值是一個(gè)數(shù)值，具體類型由運(yùn)算符和操作數(shù)確定。例如：3＋5

a*b

(a＋3)/b都是算術(shù)表達(dá)式。5.3.4程序的基本運(yùn)算

2、賦值運(yùn)算符與表達(dá)式

程序語(yǔ)言中的賦值運(yùn)算符用“＝”來(lái)表示。由賦值運(yùn)算符和運(yùn)算對(duì)象組成的式子稱為賦值表達(dá)式，其一般格式為：<變量名>＝<表達(dá)式>賦值運(yùn)算的含義是將賦值運(yùn)算符右邊<表達(dá)式>的值存放到左邊<變量名>所代表的存儲(chǔ)單元中。賦值號(hào)“＝”的作用不同于數(shù)學(xué)中使用的等號(hào)，它沒有相等的含義。例如在C語(yǔ)言中i＝i+1，從數(shù)學(xué)意義上講是不成立的；而在C語(yǔ)言中，它是合法的賦值表達(dá)式，其含義是取出變量i中的值加1后，再將運(yùn)算結(jié)果存回到變量i中去。5.3.4程序的基本運(yùn)算

3、關(guān)系運(yùn)算符與表達(dá)式由關(guān)系運(yùn)算符和運(yùn)算對(duì)象組成的式子稱為關(guān)系表達(dá)式。關(guān)系表達(dá)式的值是一個(gè)邏輯值，即只有“1”、“0”兩個(gè)值，表示“是”、“否”。不同語(yǔ)言中的運(yùn)算符有所不同。在C語(yǔ)言中提供了兩類共6種關(guān)系運(yùn)算符：

(1)大小判斷：＞(大于)、＞＝(大于等于)、＜(小于)、＜＝(小于等于)。

(2)相等判斷：＝＝(等于)、!＝(不等于)。關(guān)系運(yùn)算是比較兩個(gè)運(yùn)算對(duì)象的大小，判斷比較的結(jié)果是否符合給定的條件，因此，關(guān)系運(yùn)算符都是雙目運(yùn)算符。5.3.4程序的基本運(yùn)算

4、自增、自減運(yùn)算符為了簡(jiǎn)化程序語(yǔ)句,在C語(yǔ)言中提供了兩個(gè)特殊的運(yùn)算符,即自增、自減運(yùn)算符。自增、自減運(yùn)算符和變量組成的式子稱為自增、自減表達(dá)式。自增、自減運(yùn)算符是一種特殊的賦值運(yùn)算，參加自增、自減運(yùn)算的運(yùn)算對(duì)象必須是變量，而不能是常量或表達(dá)式?！埃笔亲栽鲞\(yùn)算符，其功能是使變量的值增1。例如：＋＋i等價(jià)于i＝i＋1“――”是自減運(yùn)算符，其功能是使變量的值減1。例如：――i等價(jià)于i＝i―1這兩個(gè)運(yùn)算符是單目運(yùn)算符，即只有一個(gè)運(yùn)算對(duì)象。5.3.4程序的基本運(yùn)算

1、表達(dá)式語(yǔ)句表達(dá)式語(yǔ)句的主要功能是用來(lái)確定變量的內(nèi)容，通常包括賦值語(yǔ)句、復(fù)合語(yǔ)句和函數(shù)調(diào)用語(yǔ)句等。

(1)賦值語(yǔ)句：由賦值表達(dá)式后跟一個(gè)分號(hào)構(gòu)成。C語(yǔ)言的賦值語(yǔ)句是先計(jì)算賦值運(yùn)算符右邊的子表達(dá)式的值，然后將此值賦給賦值運(yùn)算符左邊的變量，例如：z＝x＋y；x＝sin(z)；

(2)復(fù)合語(yǔ)句：由兩條或兩條以上的語(yǔ)句組成。在C語(yǔ)言中，通常把由一對(duì)花括號(hào)“｛｝”括起來(lái)的語(yǔ)句稱為復(fù)合語(yǔ)句或塊語(yǔ)句。例如：5.3.5程序的語(yǔ)句類型{

c＝getchar()；//該句后面的分號(hào)不能省略putchar(c)；//該句后面的分號(hào)不能省略｝//花括號(hào)之后不能再有分號(hào)復(fù)合語(yǔ)句在語(yǔ)法上相當(dāng)一條語(yǔ)句，在結(jié)構(gòu)上可以嵌套，即在復(fù)合語(yǔ)句中還可以包含復(fù)合語(yǔ)句。含有一條或多條說(shuō)明語(yǔ)句的復(fù)合語(yǔ)句稱為分程序，也稱為塊結(jié)構(gòu)。

(3)函數(shù)調(diào)用語(yǔ)句：是由函數(shù)調(diào)用表達(dá)式后跟一個(gè)分號(hào)構(gòu)成。例如：c＝max(a,b)；是一個(gè)賦值表達(dá)式。此時(shí)，函數(shù)作為表達(dá)式的一部分，函數(shù)返回值參與表達(dá)式運(yùn)算。5.3.5程序的語(yǔ)句類型

2、流程控制語(yǔ)句由運(yùn)算符和表達(dá)式構(gòu)成的各種語(yǔ)句在程序中只能按照語(yǔ)句的排列順序執(zhí)行，如果要改變程序的執(zhí)行順序，就要實(shí)行流程控制，即必須具有實(shí)現(xiàn)流程控制語(yǔ)句,并且語(yǔ)句越豐富，其結(jié)構(gòu)形式也就越多，這種語(yǔ)言的表達(dá)功能也就越強(qiáng)。C語(yǔ)言的流程控制語(yǔ)句有9種：

if、switch、while、do-while、for、break、goto、return、continue。正是這些語(yǔ)句，使得能夠方便地構(gòu)成各種復(fù)雜的程序。5.3.5程序的語(yǔ)句類型

程序設(shè)計(jì)語(yǔ)言只是程序開發(fā)的一種工具，但工具本身并不能保證程序質(zhì)量。早期，由于計(jì)算機(jī)硬件條件的限制，運(yùn)算速度與存儲(chǔ)空間都迫使程序員追求高效率,因此編寫程序成為一種技巧與藝術(shù),而程序的可高效性、可靠性、可擴(kuò)充性等因素放在其次地位。隨著計(jì)算機(jī)的應(yīng)用領(lǐng)域越來(lái)越廣泛，程序的規(guī)模以算術(shù)基數(shù)遞增，而程序的邏輯控制難度則以幾何基數(shù)遞增，程序設(shè)計(jì)越來(lái)越困難。在這種情況下，編寫程序不再片面追求高效率，而是綜合考慮程序的可靠性、可擴(kuò)充性、可重用性和可讀性等因素。正是這種需求，刺激了程序設(shè)計(jì)語(yǔ)言和程序設(shè)計(jì)方法的發(fā)展，并且形成了與程序設(shè)計(jì)語(yǔ)言相對(duì)應(yīng)的程序設(shè)計(jì)方法：面向過(guò)程程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。

§5.4

程序設(shè)計(jì)方法

面向過(guò)程程序設(shè)計(jì)方法是最早使用的編程方法，可分為：流程圖程序設(shè)計(jì)、模塊化程序設(shè)計(jì)、結(jié)構(gòu)化程序設(shè)計(jì)。

1、流程圖程序設(shè)計(jì)（FlowChartProgramming）流程圖程序設(shè)計(jì)是最早使用的方法,其優(yōu)點(diǎn)是直觀。設(shè)計(jì)者可以直接觀察整個(gè)系統(tǒng)，了解各部分之間的關(guān)系。但是，流程圖只能表示出程序的結(jié)構(gòu)，而表示不出數(shù)據(jù)的組織結(jié)構(gòu)或輸入輸出模塊的結(jié)構(gòu)，因而只用于簡(jiǎn)單問(wèn)題的程序設(shè)計(jì)。

2、模塊化程序設(shè)計(jì)（ModularProgramming）模塊化程序設(shè)計(jì)是當(dāng)一個(gè)程序十分復(fù)雜時(shí)，可以將它拆分成一系列較小的子程序，直到這些子程序易于理解為止，每個(gè)子程序是一個(gè)獨(dú)立模塊，每個(gè)模塊又可繼續(xù)劃分為更小的子模塊，程序具有一種層次結(jié)構(gòu)。5.4.1面向過(guò)程程序設(shè)計(jì)

(1)模塊化程序設(shè)計(jì)的優(yōu)點(diǎn)：與流程圖程序設(shè)計(jì)相比，模塊化程序設(shè)計(jì)具有如下優(yōu)點(diǎn)：①程序模塊容易編寫、調(diào)試和修改,且程序的易讀性好；②便于分工，即可由多個(gè)程序員同時(shí)進(jìn)行編寫和調(diào)試，有利于加快工作速度；③程序的修改可局部化進(jìn)行；④頻繁使用的功能程序塊可以編制成模塊（子程序）存放在庫(kù)里，以便多次調(diào)用。模塊化方法是對(duì)復(fù)雜問(wèn)題“分而治之”原則在軟件開發(fā)中的具體體現(xiàn)，它將軟件開發(fā)的復(fù)雜性在分解過(guò)程中降低。對(duì)一個(gè)復(fù)雜的系統(tǒng)，如何分解和設(shè)計(jì)成模塊，是模塊化方法的關(guān)鍵。5.4.1面向過(guò)程程序設(shè)計(jì)

(2)模塊化程序設(shè)計(jì)基本原則：把系統(tǒng)分解成模塊，應(yīng)遵循以下原則：①在一個(gè)模塊內(nèi)部體現(xiàn)最大程度的關(guān)聯(lián)，只實(shí)現(xiàn)單一功能的模塊具有這種特性。②最低的耦合度，即不同的模塊之間的關(guān)系盡可能弱。③模塊的層次不能過(guò)深，一般應(yīng)盡量控制在7層以內(nèi)。④接口清晰、信息隱蔽性好。⑤模塊大小適度。⑥盡量采用已有的模塊，提高模塊復(fù)用率。

5.4.1面向過(guò)程程序設(shè)計(jì)3、結(jié)構(gòu)化程序設(shè)計(jì)（StructuredProgramming）

結(jié)構(gòu)化程序設(shè)計(jì)的概念最早是由荷蘭學(xué)者E.W.Dijikstra在1965年提出來(lái)的。它采用自頂向下逐步求精的設(shè)計(jì)方法，先設(shè)計(jì)頂層，然后步步深入，逐層細(xì)分，逐步求精，直到整個(gè)問(wèn)題可用程序設(shè)計(jì)語(yǔ)言明確地描述為止。結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)從程序結(jié)構(gòu)上來(lái)研究與改變傳統(tǒng)的設(shè)計(jì)方法，即程序的設(shè)計(jì)、編寫和測(cè)試都采用一種規(guī)定的組織形式進(jìn)行，而不是想怎么寫就怎么寫。這樣，可使編制的程序結(jié)構(gòu)清晰、易于讀懂、易于調(diào)試和修改，充分顯示出結(jié)構(gòu)化程序設(shè)計(jì)的優(yōu)點(diǎn)。在70年代初,由Boehm和Jacobi提出并證明了的結(jié)構(gòu)定理：任何程序都可由三種基本結(jié)構(gòu)程序構(gòu)成結(jié)構(gòu)化程序，它們是順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。5.4.1面向過(guò)程程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)使得程序結(jié)構(gòu)清晰，可讀性好，在出現(xiàn)問(wèn)題時(shí)，便于查錯(cuò)，易于修改，提高了程序設(shè)計(jì)的質(zhì)量。但隨著軟件規(guī)模和復(fù)雜性的增長(zhǎng)，這種方法越來(lái)越不能適應(yīng)龐大、復(fù)雜軟件的開發(fā)，暴露出許多缺點(diǎn)。在這種背景下，70年代末誕生了面向?qū)ο蟪绦蛟O(shè)計(jì)方法。

面向?qū)ο蟪绦蛟O(shè)計(jì)是一種先進(jìn)的程序設(shè)計(jì)方法，是圍繞著各類事物進(jìn)行程序設(shè)計(jì)的，其本質(zhì)是把數(shù)據(jù)和處理數(shù)據(jù)的過(guò)程（函數(shù)）當(dāng)成一個(gè)整體對(duì)象。面向?qū)ο蟪绦蛟O(shè)計(jì)的實(shí)現(xiàn)需要封裝和數(shù)據(jù)隱藏技術(shù)，需要繼承和多態(tài)性技術(shù)。換句話說(shuō)，面向?qū)ο蠓椒☉?yīng)該具有3個(gè)重要特性，即封裝性、繼承性和多態(tài)性。5.4.2面向?qū)ο蟪绦蛟O(shè)計(jì)

(1)封裝性：就是把一個(gè)數(shù)據(jù)結(jié)構(gòu)同操作數(shù)據(jù)的過(guò)程組合在一起，把它們封裝在一個(gè)類中。這種封裝性能保護(hù)類中的數(shù)據(jù)與過(guò)程的安全，防止外界干擾和誤用。

(2)繼承性：是很符合人的思維方式，通過(guò)繼承，一個(gè)對(duì)象可以獲得另一個(gè)對(duì)象的屬性，并可加入屬于自己的特性。

(3)多態(tài)性：就是一個(gè)接口，多種方式。多態(tài)性的優(yōu)點(diǎn)在于通過(guò)提供一個(gè)相同的接口，可以通過(guò)不同的動(dòng)作來(lái)訪問(wèn)，從而降低了問(wèn)題的復(fù)雜度。

【提示】面向?qū)ο蟪绦蛟O(shè)計(jì)并沒有摒棄結(jié)構(gòu)化程序設(shè)計(jì)方法。相反，它是在充分吸收結(jié)構(gòu)化程序設(shè)計(jì)優(yōu)點(diǎn)的基礎(chǔ)上引進(jìn)了對(duì)象、類等新的、強(qiáng)有力的概念，從而開創(chuàng)了程序設(shè)計(jì)工作的新天地。5.4.2面向?qū)ο蟪绦蛟O(shè)計(jì)隨著Windows廣泛的應(yīng)用，使得程序設(shè)計(jì)的觀念也隨之發(fā)生了顯著變化。在面向?qū)ο蟪绦蛟O(shè)計(jì)的基礎(chǔ)上，人們又把程序設(shè)計(jì)的目標(biāo)投向了面向Windows界面的編程，稱為可視化程序設(shè)計(jì)（VisualProgramming）。所謂可視化程序設(shè)計(jì)，就是在程序設(shè)計(jì)過(guò)程中能夠及時(shí)看到程序設(shè)計(jì)的效果，即具有可視化圖形界面。具有這種功能的編程語(yǔ)言目前有：VisualBasic、VisualC++、C#、Delphi、Java、VisualProlog等?？梢暬绦蛟O(shè)計(jì)以其圖形化的編程方式將面向?qū)ο蠹夹g(shù)的特性體現(xiàn)出來(lái)，通過(guò)用鼠標(biāo)拖曳圖形化的控件就可以完成Windows風(fēng)格界面的設(shè)計(jì)工作，大大減輕了程序設(shè)計(jì)人員的編程工作量，使得開發(fā)軟件這一原本枯燥、難以理解的工作變得相對(duì)輕松快捷。5.4.3可視化程序設(shè)計(jì)在2002年初，微軟公司又推出了VisualC++的最新版本VisualC++.Net，它繼承了以往VisualC++各版本的優(yōu)點(diǎn)，增加了許多新的特性,使得開發(fā)能力更強(qiáng)、開發(fā)的效率更高。VisualBasic繼承了Basic簡(jiǎn)單易學(xué)的特點(diǎn)，也是得到廣泛應(yīng)用的可視化程序設(shè)計(jì)語(yǔ)言,特別適合于初學(xué)者和非專業(yè)人員?？梢暬幊叹哂腥缦绿攸c(diǎn)：

(1)基于面向?qū)ο笏枷耄嚎梢暬幊讨械慕缑婊居煽丶M合而成，控件就是在程序中能夠完成與用戶交互、程序運(yùn)算等功能的部件。

(2)先繪界面后寫代碼：拖拽需要的各類控件，并設(shè)置各種對(duì)象的位置、顏色、大小、字體和標(biāo)題等屬性。然后，針對(duì)不同對(duì)象,對(duì)鍵盤、鼠標(biāo)等操作可能響應(yīng)的事件編寫代碼。5.4.3可視化程序設(shè)計(jì)§5.5

算法設(shè)計(jì)

程序設(shè)計(jì)與算法設(shè)計(jì)密不可分。對(duì)于初學(xué)者而言，程序設(shè)計(jì)的難點(diǎn)在于語(yǔ)言基本要素和語(yǔ)法規(guī)則的掌握，而真正設(shè)計(jì)出高水平程序的基礎(chǔ)是具有良好的算法設(shè)計(jì)。

1、算法的起源

在算法研究史上，最為著名的古老算法是用于求兩個(gè)整數(shù)的最大公約數(shù)的歐幾里德算法。這個(gè)算法最早出現(xiàn)在大約公元前350～300年由古希臘數(shù)學(xué)家歐幾里德（Euclid）寫成的《Elements》（幾何原本）中，因此將其稱為歐幾里德算法，它被人們公認(rèn)為是算法史上的第一個(gè)算法，也稱為輾轉(zhuǎn)相除法。5.5.1算法的基本概念歐幾里德算法是指已知兩個(gè)整數(shù)x和y，用mod(x，y)或者xmody表示x被y除后所得的余數(shù)。求兩個(gè)已知數(shù)x和y(設(shè)x＞y)的最大公約數(shù)的計(jì)算過(guò)程如圖5-5所示。

5.5.1算法的基本概念圖5-5歐幾里德算法YN輸入x，y輸出yr＝0r=x/y的余數(shù)x＝y(tǒng)y＝rr＝0【例5-5】計(jì)算91和52的最大公約數(shù)，用輾轉(zhuǎn)相除法求解過(guò)程如下：Step1：mod(91，52)＝39；Step2：mod(52，39)＝13；Step3：mod(39，13)＝0。請(qǐng)同學(xué)們思考求最大公約數(shù)的思想和方法步驟。

【例5-6】以我國(guó)古代數(shù)學(xué)家“鬼谷子”命題的“鬼谷算題”：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”

[算法分析]

從1開始，取出一個(gè)自然數(shù)判斷它被3、5、7整除后的余數(shù)是否為2、3、2。如果是，則該數(shù)就是所求的數(shù)，求解結(jié)束。否則，用下一個(gè)數(shù)再試，直到找到這個(gè)數(shù)為止。我們用自然語(yǔ)言描述該算法如下：Step1：將N取初始值為1。Step2：如果N被3、5、7整除后的余數(shù)是否為2、3、2，如果是，則輸出N的值，并轉(zhuǎn)Step4；否則，繼續(xù)下一步。Step3：將N值增加1，并轉(zhuǎn)到Step2。Step4：程序結(jié)束。5.5.1

算法的基本概念

2、算法的定義公元825年，一位名叫阿爾·花拉子米的波斯數(shù)學(xué)家寫了一本教科書，書中概括了進(jìn)行數(shù)字四則算術(shù)運(yùn)算的法則?，F(xiàn)代“算法”的英文名詞“Algorithm”就來(lái)源于這位數(shù)學(xué)家的名字。如果僅從計(jì)算機(jī)科學(xué)中的概念來(lái)解釋，算法是用計(jì)算機(jī)解題的精確描述，是逐步（Step-by-step）執(zhí)行某類計(jì)算的方法，是有窮的動(dòng)作的序列或步驟。因此可定義為：

算法是為解決特定問(wèn)題所采取的方法和步驟的描述，是指令的有限序列。算法所處理的對(duì)象就是為解決特定問(wèn)題所涉及的相關(guān)數(shù)據(jù)。5.5.1

算法的基本概念

3、算法的特征著名計(jì)算機(jī)科學(xué)家Knuth把算法歸納為以下5個(gè)顯著特征。ADBCE算法的特征有效性有窮性有零或多個(gè)輸入至少一個(gè)輸出確定性5.5.1算法的基本概念

(1)確定性（Certainty）：算法的每一個(gè)步驟（每一條指令）都必須有確切的含義，不能有二義性（ambiguity）。計(jì)算機(jī)只能根據(jù)程序員給它的具體明確的步驟執(zhí)行，且同一個(gè)步驟不能作多種理解。在算法描述中如果出現(xiàn)“好像”之類的似是而非的語(yǔ)法成分，則非確定的。

(2)有效性（Effectiveness）：又稱可行性，算法中的每一步都能有效地執(zhí)行,即每一條指令都必須是切實(shí)可行的，都能得出確定的結(jié)果。例如，在進(jìn)行x除以y運(yùn)算時(shí)，就不能出現(xiàn)y=0的情況，既保證x除以y操作的有效性。5.5.1

算法的基本概念

(3)有窮性（Finiteness)：一個(gè)算法是有限步驟的描述，因此必須在執(zhí)行有窮步驟之后正常結(jié)束。在算法中如果出現(xiàn)“死循環(huán)”等現(xiàn)象，就不符合算法有窮性的要求。例如求1～10之間自然數(shù)之和的程序：

s=0;

for(i＝1；i＜＝10；i++)s＝s+i；執(zhí)行次數(shù)是10。

(4)有零個(gè)或多個(gè)輸入（Input）：算法一般應(yīng)具有供加工的原始數(shù)據(jù)。

(5)有一個(gè)或多個(gè)輸出（Output）：算法至少要有一個(gè)輸出，沒有輸出的算法是沒有意義的。5.5.1

算法的基本概念

4、算法的目標(biāo)算法的質(zhì)量是一個(gè)十分重要的問(wèn)題，好的算法應(yīng)達(dá)到以下4個(gè)目標(biāo)。

(1)正確可靠：不正確的程序不但不能解決問(wèn)題，反而會(huì)給我們的工作帶來(lái)不必要的麻煩，甚至造成重大損失。

(2)清晰易讀：程序的可讀性和可理解性成為優(yōu)質(zhì)軟件的重要標(biāo)志。

(3)高效工作：執(zhí)行程序的時(shí)間效率和占用內(nèi)存的空間效率要高。在有些情況下，當(dāng)效率成為制約程序運(yùn)行的主要因素時(shí)，編程者需要在效率和可讀性之間作出折中選擇。(4)通用性要好：對(duì)異常情況要能作出適當(dāng)?shù)姆磻?yīng)，留有出口。5.5.1

算法的基本概念

5、算法的結(jié)構(gòu)算法是執(zhí)行任務(wù)的步驟和指令系列，指令的執(zhí)行次序稱為執(zhí)行流程。對(duì)于不同的問(wèn)題，其執(zhí)行的流程可能不同，即存在流程控制問(wèn)題，在算法設(shè)計(jì)中，通常將流程控制簡(jiǎn)稱為算法結(jié)構(gòu)。經(jīng)過(guò)多年的研究和總結(jié)，人們發(fā)現(xiàn)無(wú)論多么復(fù)雜的算法，都可以用三種流程控制結(jié)構(gòu)來(lái)描述：

順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)上述3種結(jié)構(gòu)形式在“算法的描述方法”中介紹。5.5.1

算法的基本概念

1、正確性（Correctness）在計(jì)算機(jī)上運(yùn)行用算法語(yǔ)言描述構(gòu)成的程序時(shí)，該程序也應(yīng)該是正確的，并且該程序?qū)λ锌赡艿暮戏ㄝ斎攵寄苡?jì)算出正確的結(jié)果，即算法的正確性可以概括為以下4個(gè)方面：①程序中的每一條語(yǔ)句都符合語(yǔ)法規(guī)定，這是最基本的要求。②程序?qū)τ趲捉M輸入數(shù)據(jù)都能得出滿足要求的輸出結(jié)果。③程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。④程序?qū)倪x擇的典型、苛刻甚至刁難性的若干組輸入數(shù)據(jù)能得到滿足要求的結(jié)果。例如在處理包含條件的問(wèn)題時(shí)，可以選取條件邊界處的數(shù)據(jù)進(jìn)行輸入，以驗(yàn)證程序的正確性。5.5.2

算法的設(shè)計(jì)要求

2、可讀性（Readality）一個(gè)好的算法應(yīng)便于理解、便于編碼、便于修改等。從書寫角度來(lái)說(shuō)，結(jié)構(gòu)上要直觀、清晰、美觀，并在必要的地方要加上注釋說(shuō)明。另外，算法的描述不要拘泥于一種形式，在算法的每個(gè)部分可以采用最便于理解的描述形式。3、健壯性（Rubustness）一個(gè)算法除了對(duì)合法的輸入數(shù)據(jù)能得到正確的結(jié)果外，還應(yīng)對(duì)非法的或不合乎要求的輸入數(shù)據(jù)作出正確合理的處理，這就要求程序設(shè)計(jì)時(shí)要充分考慮異常情況。健壯性體現(xiàn)了思維的縝密性，如果沒有對(duì)數(shù)據(jù)分析清楚，特別是極端數(shù)據(jù)、特殊數(shù)據(jù)的處理，就很可能使算法失去準(zhǔn)確性。例如，求解三角形的面積的算法可設(shè)計(jì)為：5.5.2

算法的設(shè)計(jì)要求Step1：輸入三條邊的邊長(zhǎng)a、b、c；Step2：計(jì)算s=(a+b+c)/2；5.5.2

算法的設(shè)計(jì)要求Step3：計(jì)算

該算法雖然正確，但缺乏健壯性。當(dāng)輸入的三個(gè)數(shù)不能構(gòu)成一個(gè)三角形時(shí)程序應(yīng)該如何處理？為此，算法可改進(jìn)如下：

Step1：輸入三條邊的邊長(zhǎng)a、b、c；

Step2：如果(a+b)>c且(b+c)>a，執(zhí)行Step3；否則，輸出提示信息“數(shù)據(jù)輸入不合理”并結(jié)束程序；

Step3：計(jì)算s=(a+b+c)/2；Step4：計(jì)算

Step5：輸出area的值。5.5.3

算法的描述方法當(dāng)設(shè)計(jì)好一個(gè)算法之后,可先用描述算法的語(yǔ)言工具將所設(shè)計(jì)的解題步驟記錄下來(lái),然后轉(zhuǎn)化為語(yǔ)言源程序。描述算法的語(yǔ)言工具有：自然語(yǔ)言、程序設(shè)計(jì)語(yǔ)言、偽代碼、圖形法等。

1、用自然語(yǔ)言描述算法

【例5-7】用自然語(yǔ)言描述求1＋3＋5＋…＋n的算法。設(shè)兩個(gè)變量：Sn表示和值，K表示加數(shù)。具體描述如下：

Step1：輸入n的值，n≥1。

Step2：設(shè)兩個(gè)初值變量：用Sn表示和，其初始值為0；用K表示加數(shù)，其初始值為1。

Step3：計(jì)算累加和，即：Sn＝Sn＋K。

Step4：重復(fù)S3、S4兩步，直到K大于n為止。

Step5：輸出Sn值。

2、用偽代碼描述算法【例5-8】用偽代碼語(yǔ)言描述求1＋3＋5＋…＋99的算法。具體描述如下：beginx＝1，y＝3；while（y≤99）{x←x＋yy←y＋2}printxend5.5.3算法的描述方法5.5.3

算法的描述方法

3、用程序設(shè)計(jì)語(yǔ)言描述算法

【例5-9】用C程序設(shè)計(jì)語(yǔ)言描述求1＋3＋5+…＋99的算法。具體描述如下：main(){intx，y；x＝1；for（y＝3；y≤99；y＝y(tǒng)＋2）x＝x＋y；primf（“％d”，x）；}使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述算法具有：清晰、簡(jiǎn)明、一步到位，寫出的算法能直接由計(jì)算機(jī)處理等優(yōu)點(diǎn)。

5.5.3

算法的描述方法

4、用圖形描述算法直接利用程序設(shè)計(jì)語(yǔ)言來(lái)描述算法，雖然能一步到位，但要求編程者對(duì)程序設(shè)計(jì)語(yǔ)言非常地熟練，并且具有相當(dāng)清晰的設(shè)計(jì)思路。但對(duì)于稍復(fù)雜的算法問(wèn)題，很容易出錯(cuò)，所以通常采用圖形描述算法，它具有流程清晰，邏輯性好的優(yōu)點(diǎn)。到目前為止，用圖形描述算法的方法有3種：

流程圖

N-S圖

PAD圖它們各有優(yōu)特點(diǎn)，相比之下，人們更多地習(xí)慣用流程圖描述算法，而且特別適合于初學(xué)者。這里，僅簡(jiǎn)要介紹利用流程圖（Flowchart）描述算法的方法。5.5.3

算法的描述方法表5-1

流程圖符號(hào)符號(hào)符號(hào)名稱功能說(shuō)明終端框算法開始與結(jié)束處理框算法的各種處理操作預(yù)定處理框算法調(diào)用的子算法注解框算法的說(shuō)明信息判斷框算法的條件轉(zhuǎn)移輸入輸出框輸入輸出操作流程線指向另一操作引入、引出連接符表示流程延續(xù)5.5.4算法的基本概念

(1)順序結(jié)構(gòu)：是一種從上之下的結(jié)構(gòu)形式，如圖5-6所示。虛線框內(nèi)是一個(gè)順序結(jié)構(gòu)，即在執(zhí)行完A框內(nèi)所指定的操作后，依此執(zhí)行B框內(nèi)所指定的操作和C框內(nèi)所指定的操作。順序結(jié)構(gòu)是最簡(jiǎn)單的一種基本結(jié)構(gòu)形式。ABC圖5-6順序結(jié)構(gòu)5.5.4算法的基本概念

(2)選擇結(jié)構(gòu)：是根據(jù)給定條件選擇執(zhí)行某個(gè)分支語(yǔ)句的結(jié)構(gòu)。選擇結(jié)構(gòu)可分為兩種結(jié)構(gòu)形式:一種是雙邊結(jié)構(gòu)形式，如圖5-7所示。另一種是單邊結(jié)構(gòu)形式，如圖5-8所示。圖5-7雙邊選擇結(jié)構(gòu)成立不成立AP圖5-8

單邊選擇結(jié)構(gòu)成立不成立ABP

⑶循環(huán)結(jié)構(gòu)：是根據(jù)給定條件重復(fù)執(zhí)行某一操作，直到滿足條件后終止循環(huán)。這種結(jié)構(gòu)具有兩種結(jié)構(gòu)形式：一種是先判斷，然后執(zhí)行相關(guān)操作；另一種是先執(zhí)行相關(guān)操作，然后再判斷。我們把前者稱為“當(dāng)型”循環(huán)，后者稱為“直到型”循環(huán)。①“當(dāng)型（While）”循環(huán)結(jié)構(gòu)，如圖1-9所示。它的功能是當(dāng)判斷條件p1成立時(shí)，執(zhí)行A框操作，完成A框操作后判斷，如果條件P1成立，則繼續(xù)反復(fù)執(zhí)行A框操作；如果條件不成立，此時(shí)不再執(zhí)行A框操作，而是脫離循環(huán)結(jié)構(gòu)，執(zhí)行后續(xù)語(yǔ)句。

②“直到型（Until）”循環(huán)結(jié)構(gòu)，如圖1－10所示。它的功能是先執(zhí)行A框操作，然后判斷給定條件P2。如果條件p2不成立，則再執(zhí)行A框操作。如此反復(fù)進(jìn)行，直到條件P2成立，此時(shí)不再執(zhí)行A框操作，而是脫離循環(huán)結(jié)構(gòu)，執(zhí)行后續(xù)語(yǔ)句。5.5.4算法的基本概念圖1-9“當(dāng)型”循環(huán)結(jié)構(gòu)

成立AP1圖1-10“直到型”循環(huán)結(jié)構(gòu)

不成立

成立P2A由以上三種基本結(jié)構(gòu)組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜的問(wèn)題。由這三種基本結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化”算法，它不存在無(wú)規(guī)律的轉(zhuǎn)向。以上三種基本結(jié)構(gòu)有以下共同特點(diǎn)：●每一個(gè)框都有一條從入口到出口的路徑通過(guò)它，所以結(jié)構(gòu)內(nèi)的每一部分都能被執(zhí)行。

●結(jié)構(gòu)內(nèi)不存在“死循環(huán)”（無(wú)終止的循環(huán)）。

5.5.4算法的基本概念

算法包括數(shù)值計(jì)算算法和非數(shù)值計(jì)算算法兩類。最常使用的數(shù)值算法有：回朔算法排序算法插值算法算法窮舉舉算法遞歸算法迭代算法5.5.5常用算法簡(jiǎn)介

1、窮舉算法（ExhaustiveAttackAlgorithm）窮舉算法也稱為枚舉算法或稱強(qiáng)力算法，就是列舉集合中所有元素，分別判斷命題真?zhèn)巍?/p>

【例5-11】若公雞每只3元，母雞每只5元，小雞每三只1元，求100元買100只雞有多少種方案。

[算法分析]

設(shè)公雞為x，母雞為y，小雞為z，可列出如下的聯(lián)立方程：

x＋y＋z＝1003x＋5y＋z/3＝100這就是“百錢買百雞”的應(yīng)用問(wèn)題。兩個(gè)方程式不可能解出3個(gè)未知數(shù)，但利用計(jì)算機(jī)的高速運(yùn)算特點(diǎn)可以給定x，y，z的各種組合值來(lái)試算，只要結(jié)果符合兩個(gè)表達(dá)式的值都為100即可。5.5.5常用算法簡(jiǎn)介

2、遞推算法（RecurrenceAlgorithm）遞推算法是利用問(wèn)題本身所具有的一種遞推關(guān)系，把所求問(wèn)題分成若干步，并找出相鄰幾步的關(guān)系,然后進(jìn)行遞推求解，因而它是迭代算法的最基本形式?！纠?-12】設(shè)有一組數(shù)據(jù)元素：1，2，5，10，21，42，85,170,341,682,…,要求通過(guò)程序?qū)崿F(xiàn)將它延長(zhǎng)到第50項(xiàng)。

[算法分析]

根據(jù)遞推算法的問(wèn)題分析，考察本題的特點(diǎn)，

從給出的數(shù)據(jù)元素不難發(fā)現(xiàn)：偶數(shù)項(xiàng)是前一項(xiàng)的兩倍，奇數(shù)項(xiàng)是前一項(xiàng)的2倍＋1，即：

a2k＝２a2k-1，a2k＋1＝２a2k＋1這是一種由前項(xiàng)推導(dǎo)后項(xiàng)的遞推關(guān)系,即用遞推算法求解。5.5.5常用算法簡(jiǎn)介5.5.5常用算法簡(jiǎn)介3、遞歸算法（RecursiveAlgorithm）

在定義算法的過(guò)程中用自身的簡(jiǎn)單情況來(lái)定義自身，直接或間接地調(diào)用自身的算法稱為遞歸算法,遞歸算法有以下兩種。

(1)直接遞歸：重復(fù)一個(gè)或一組操作，例如累加、累減、累乘、累除等。計(jì)算機(jī)語(yǔ)言支持a＝a+1，把a(bǔ)＋1后的值賦給a，這就是直接遞歸方法，而不是表達(dá)式計(jì)算。

(2)間接遞歸：程序用到它自身的前一步或前幾步。例如計(jì)算階乘：

2!＝1＊23!＝1＊2＊3＝2!＊3(N＋1)!＝N!＊(N＋1)5.5.5常用算法簡(jiǎn)介遞歸算法能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡(jiǎn)潔精煉，增加可讀性。例如漢諾塔是個(gè)著名難題，但可以用遞歸算法解決它?！纠?-13】編程對(duì)n階勒讓德多項(xiàng)式求解，其定義為：

1(n＝0)Ｐn(x)＝x(n＝1)((2n-1)*x-pn-1(x)-(n-1)*pn-2(x))/n（n≥1)輸入正整數(shù)n和任意數(shù)x，求出勒讓德多項(xiàng)式Pn(x)。

[算法分析]

從勒讓德多項(xiàng)式定義可以看出，多項(xiàng)式Pn(x)是一種遞歸形式的定義。因此要求出勒讓德多項(xiàng)式Pn(x)的值，最簡(jiǎn)單的方法就是編寫一個(gè)遞歸函數(shù)程序來(lái)實(shí)現(xiàn)。5.5.5常用算法簡(jiǎn)介4、分治算法（DivideandConquerAlgorithm）分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題，劃分成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。

【例5-14】對(duì)已排序的n個(gè)元素a[n]，用二分法搜索法在這n個(gè)元素中找出一特定元素x。

[算法分析]

二分搜索的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取中間元素a[n/2]與x比較，可能出現(xiàn)以下三種比較結(jié)果：①若x＝a[n/2]，則找到x，停止搜索；②若x＜a[n/2]，則在a[0]一a[n/2—1]中繼續(xù)搜索x；③若x＞a[n/2]，則在a[n/2十1]-a[n-1]中繼續(xù)搜索x。5.5.5常用算法簡(jiǎn)介5、動(dòng)態(tài)規(guī)劃算法（DynamicProgramming）動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成若干個(gè)相互重疊的子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)決策過(guò)程的一個(gè)階段。一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定問(wèn)題求解的遞推關(guān)系中，將子問(wèn)題的解求解一次并填入表中。當(dāng)需要再次求解此子問(wèn)題時(shí),可以通過(guò)查表獲得該子問(wèn)題的解而不用再次求解,從而避免大量重復(fù)計(jì)算?！纠?-15】計(jì)算斐波那契數(shù)列。斐波那契數(shù)列存在如下遞推關(guān)系式：

f(n-1)＋f(n-2)f(n)＝f(0)＝0，f(1)＝15.5.5常用算法簡(jiǎn)介01123581321340123456789

[算法分析]

注意到計(jì)算f(n)是以計(jì)算它的兩個(gè)重疊子問(wèn)題f(n-1)和f(n-2)的形式來(lái)表達(dá)的，所以可以設(shè)計(jì)一張表填入n＋1個(gè)f(n)的值，如圖5-10所示。

開始時(shí)，根據(jù)遞推關(guān)系式的初始條件可以直接填入0和1,然后根據(jù)遞推關(guān)系式作為運(yùn)算規(guī)則計(jì)算出其它所有元素。顯然，表中最后一項(xiàng)就是f(n)的值。圖5-10動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過(guò)程5.5.5常用算法簡(jiǎn)介6、貪心算法（GreedyAlgorithm）貪心算法是把一個(gè)復(fù)雜問(wèn)題分解為一系列較為簡(jiǎn)單的局部最優(yōu)選擇，每一步選擇都是對(duì)當(dāng)前解的一個(gè)擴(kuò)展，直到獲得問(wèn)題的完整解。貪心算法的典型應(yīng)用是求解最優(yōu)化問(wèn)題?！纠?-16】假設(shè)有面值為5元、2元、1元、5角、2角和1角的貨幣，需要找給顧客4元6角現(xiàn)金，如何才能使付出貨幣的數(shù)量最少?

[算法分析]

為了使付出貨幣的數(shù)量最少，在每一步的選擇中，在不超過(guò)應(yīng)付款金額的條件下,選擇面值最大的貨幣，盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設(shè)計(jì)思想。在解決一個(gè)問(wèn)題時(shí)往往可選用不同的算法，而不同的算法會(huì)決定著該程序性能的好壞。如何評(píng)價(jià)一個(gè)算法的好壞？通常從算法的“時(shí)間復(fù)雜度”和“空間復(fù)雜度”來(lái)考慮。

1、算法的時(shí)間復(fù)雜度（TimeComplexity）算法的時(shí)間復(fù)雜度是度量時(shí)間的復(fù)雜性，即算法的時(shí)間效率的指標(biāo)。具體說(shuō)，時(shí)間復(fù)雜度是與求解問(wèn)題的規(guī)模、算法輸入數(shù)據(jù)相關(guān)的函數(shù),該函數(shù)表示算法運(yùn)行所花費(fèi)的時(shí)間。為了簡(jiǎn)化問(wèn)題，通常用算法運(yùn)行某段代碼的次數(shù)來(lái)代替準(zhǔn)確的執(zhí)行時(shí)間，記為T(n)。T為英文單詞Time的第一個(gè)字母，T(n)中的n表示問(wèn)題規(guī)模的大小，一般指待處理的數(shù)據(jù)量的大小。5.5.6算法的復(fù)雜度5.5.6算法的復(fù)雜度在實(shí)際的時(shí)間復(fù)雜度分析中，經(jīng)?？紤]的是當(dāng)問(wèn)題規(guī)模趨于無(wú)窮大的情形，因此引入符號(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ù)雜度記為：T(n)＝O(f(n))式中，n表示問(wèn)題的規(guī)模；T(n)表示漸進(jìn)時(shí)間復(fù)雜度；f(n)是問(wèn)題規(guī)模n的函數(shù)；O(f(n))取的是函數(shù)f(n)的上界。當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對(duì)所有的n(n≥n0)，滿足T(n)≤c*f(n)此時(shí)將(c*f(n)記作)O(f(n))。5.5.6算法的復(fù)雜度【例5-17】求兩個(gè)n階矩陣相乘的算法代碼如下：

for(i＝1；i<＝n；i++)for(j＝1；j<＝n；j++){c[i][j]＝0；

//語(yǔ)句1

for(k＝0；k<n；k++)c[i][j]＝c[i][j]+a[i][k]*b[k][j]；

//語(yǔ)句2}要計(jì)算上面代碼的時(shí)間復(fù)雜度，其實(shí)只需要計(jì)算語(yǔ)句1和語(yǔ)句2的執(zhí)行此數(shù)（頻率）。設(shè)語(yǔ)句的執(zhí)行次數(shù)為f(n)，語(yǔ)句1的執(zhí)行次數(shù)為n2，語(yǔ)句2的執(zhí)行次數(shù)為n3，則有：f(n)＝n2＋n3因?yàn)閚2＋n3≤c*n3＝O(n3)，所以上面程序段的時(shí)間復(fù)雜度為O(n3)。5.5.6算法的復(fù)雜度

2、算法的空間復(fù)雜度（SpaceComplexity）算法的空間復(fù)雜度是指算法運(yùn)行的存儲(chǔ)空間，是實(shí)現(xiàn)算法所需的內(nèi)存空間的大小?？臻g復(fù)雜度是與求解問(wèn)題規(guī)模、算法輸入數(shù)據(jù)相關(guān)的函數(shù)，記為S(n)。

S為英文單詞Space的第一個(gè)字母，n代表求解問(wèn)題的規(guī)模，一般指待處理的數(shù)據(jù)量的大小?？臻g復(fù)雜度主要也是考慮當(dāng)問(wèn)題規(guī)模趨于無(wú)窮大的情形,符號(hào)“O”同樣被用來(lái)表示空間復(fù)雜度S(n)與求解問(wèn)題規(guī)模n之間的數(shù)量級(jí)關(guān)系。例如，如果

S(n)＝O(n2)表示算法的空間復(fù)雜度與n2成正比，則記為

S(n)＝O(n2)5.5.6算法的復(fù)雜度【例5-18】考察不同變量所占用的存儲(chǔ)空間與空間復(fù)雜度的對(duì)應(yīng)關(guān)系。

intx，y，z；

//算法1

#defineN1000//算法2

intk，j，a[N]，b[2*N]；#defineN100//算法3

intk，j，a[N][10*N]；其中：算法1設(shè)置三個(gè)簡(jiǎn)單變量，占用三個(gè)內(nèi)存單元，其空間復(fù)雜度為O(1)。算法2設(shè)置了兩個(gè)簡(jiǎn)單變量與兩個(gè)一維數(shù)組,占用3n＋2個(gè)內(nèi)存單元,顯然其空間復(fù)雜度為O(n)。算法3設(shè)置了兩個(gè)簡(jiǎn)單變量與一個(gè)二維數(shù)組，占用l0n2＋2個(gè)內(nèi)存單元，顯然其空間復(fù)雜度為O(n2)?！?.6數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。隨著計(jì)算機(jī)的廣泛應(yīng)用，計(jì)算機(jī)加工處理的對(duì)象已由數(shù)值數(shù)據(jù)發(fā)展到字符、表格、圖形、圖像、聲音等各種具有一定結(jié)構(gòu)的非數(shù)值數(shù)據(jù)。因此，計(jì)算機(jī)處理的問(wèn)題可分為兩類：數(shù)值問(wèn)題和非數(shù)值問(wèn)題。對(duì)于數(shù)值問(wèn)題的求解通常是在分析問(wèn)題的基礎(chǔ)上，將各個(gè)量之間的關(guān)系抽象成一定的數(shù)學(xué)模型，然后由計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理。然而，對(duì)于非數(shù)值問(wèn)題的求解卻無(wú)法用數(shù)學(xué)方程來(lái)描述，對(duì)于這一類的問(wèn)題，計(jì)算機(jī)是怎樣實(shí)現(xiàn)對(duì)數(shù)據(jù)處理呢？這就是“數(shù)據(jù)結(jié)構(gòu)”所要研究的問(wèn)題。5.6.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1、數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)（DataStructure)是指相互之間存在某種特定關(guān)系的數(shù)據(jù)元素的集合，是信息的一種組織方式，其目的是為了提高算法的效率。數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data-Rtructure＝（D，R）其中，D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。例如復(fù)數(shù)x＋yi；x,y∈R；Complex＝(D,Ｒ)，D＝{x|x∈R}；R＝{(x,y)}|x，y∈D}；x稱為實(shí)部，y稱為虛部。因此，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題中,計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。5.6