《程序設(shè)計基礎(chǔ)》課件第1章

第1章程序設(shè)計概述1.1程序工作原理1.2程序設(shè)計語言1.3算法概述1.4C語言程序設(shè)計習題

1.1程序工作原理

1.1.1馮·諾伊曼原理

一臺計算機由硬件系統(tǒng)和軟件系統(tǒng)兩大部分組成，硬件是計算機的物質(zhì)基礎(chǔ)，而軟件是計算機的靈魂。沒有軟件，計算機只是一臺“裸機”，有了軟件，計算機才能成為一臺真正的“電腦”。而所有的軟件，都是用計算機程序設(shè)計語言編寫的。程序是指計算機可以直接或間接執(zhí)行的指令的集合。計算機系統(tǒng)通過運行程序來實現(xiàn)各種不同的應(yīng)用。程序設(shè)計語言(ProgrammingLanguage)是一組用來定義計算機程序的語法規(guī)則。一種程序設(shè)計語言能夠準確地定義計算機所需要使用的數(shù)據(jù)，并精確地定義在不同情況下所應(yīng)當采取的行動。當今的計算機模型是由數(shù)學家馮·諾依曼(vonNeumann)提出來的，我們稱其為馮·諾依曼模型(vonNeumannModel)或馮·諾依曼機(vonNeumannMachine)。直到今天，幾乎所有的計算機都是沿用這一模型設(shè)計的。馮·諾依曼機概念基于一個存儲器(用來存儲指令和數(shù)據(jù))、一個控制器(負責從存儲器中逐條取出指令)和一個處理器(通過算術(shù)或邏輯操作來處理數(shù)據(jù))，最后的結(jié)果必須送回存儲器中?？梢园堰@些特點歸結(jié)為以下幾條：

(1)數(shù)據(jù)或指令以二進制形式存儲(數(shù)據(jù)和指令在外形上沒有什么區(qū)別，但每一位二進制數(shù)字有不同的含義)。

(2)“存儲程序”的工作方式(事先要編好程序，執(zhí)行之前先將程序存放到存儲器某個可知的地方)。

(3)程序順序執(zhí)行(可強行改變執(zhí)行順序)。

(4)存儲器的內(nèi)容可以被修改(存儲器的某個單元一旦進入新的數(shù)據(jù)，則該單元原來的數(shù)據(jù)立即消失，被新數(shù)據(jù)代替)。馮·諾依曼體系結(jié)構(gòu)的作用體現(xiàn)在命令式語言的下述三大特性上：

(1)變量存儲器由大量的存儲單元(MemoryCell，MemoryLocation)組成，數(shù)據(jù)就存放在這些單元中。匯編語言通過對存儲單元的命名來訪問數(shù)據(jù)。在命令式語言中，存儲單元及它的名稱由變量(Variable)的概念代替。變量代表一個(或一組)命名的存儲單元，單元可存放值，值可以被修改。

(2)賦值使用存儲概念的另一個后果是每一計算結(jié)果必須存儲，即賦值于某個存儲單元，從而改變該單元的值。

(3)重復語句按順序執(zhí)行，指令存儲在有限的存儲器中，要完成任何復雜的計算，唯一的辦法是重復執(zhí)行某些指令序列。

馮·諾依曼型計算機的兩大特征是“程序存儲”和“采用二進制”。具體地說，在上述計算機中，要實現(xiàn)機器的自動計算，必須先根據(jù)題目的要求，編制出求解該問題的計算程序，并通過輸入設(shè)備將該程序存入計算機的存儲器中，稱之為“程序存儲”。在計算機中，計算程序及數(shù)據(jù)是用二進制代碼表示的，計算機只能存儲并識別二進制代碼表示的計算程序和數(shù)據(jù)，稱之為“采用二進制”。

馮·諾伊曼思想實際上是電子計算機設(shè)計的基本思想，奠定了現(xiàn)代電子計算機的基本結(jié)構(gòu)，開創(chuàng)了程序設(shè)計的時代。1.1.2計算機的構(gòu)成原理

電子計算機硬件通常由5大功能部件組成：存儲器、運算器、控制器、輸入設(shè)備和輸出設(shè)備，5大部件通過總線有機地連接在一起組成計算機的硬件系統(tǒng)。

運算器用來實現(xiàn)算術(shù)、邏輯等各種運算。

存儲器用來存放計算程序及參與運算的各種數(shù)據(jù)。存儲器可以分為內(nèi)存儲器(內(nèi)存)和外存儲器(外存)。

控制器實現(xiàn)對整個運算過程的有規(guī)律的控制。

輸入設(shè)備實現(xiàn)計算程序和原始數(shù)據(jù)的輸入。

輸出設(shè)備實現(xiàn)計算結(jié)果的輸出。隨著制造計算機的器件的發(fā)展，特別是微機的發(fā)展，產(chǎn)生了中央處理器(CPU)。CPU中包括運算器和控制器。

計算機工作時要預先把指揮計算機如何進行操作的指令序列(通常稱為程序)和原始數(shù)據(jù)通過輸入設(shè)備輸入到計算機的內(nèi)部存儲器中。每一條指令中明確規(guī)定了計算機從哪個地址取數(shù)，進行什么操作，然后送到什么地址等步驟。計算機在運行時，先從內(nèi)存中取出第一條指令，通過控制器的譯碼，按指令的要求，從存儲器中取出數(shù)據(jù)進行指定的運算和邏輯操作，然后再按地址把結(jié)果送到內(nèi)存中去。接下來，再取出第二條指令，在控制器的指揮下完成規(guī)定的操作。依此進行下去，直至遇到停止指令。簡而言之，即將程序與數(shù)據(jù)一樣存儲，按程序編排的順序，一步一步地取出指令，自動地完成指令規(guī)定的操作。

我們把按照馮·諾依曼原理構(gòu)造的計算機叫馮·諾依曼計算機，其體系結(jié)構(gòu)稱為馮·諾依曼結(jié)構(gòu)。目前計算機已發(fā)展到了第五代，基本上仍然遵循著馮·諾依曼原理和結(jié)構(gòu)。

1.2程序設(shè)計語言

1.2.1程序設(shè)計語言的發(fā)展

語言是人們交流思想的工具。人類在長期的歷史發(fā)展過程中，為了交流思想、表達感情和交換信息，逐步形成了語言。這類語言，如漢語和英語，通常稱為自然語言。另一方面，人們?yōu)榱四撤N專門用途，創(chuàng)造出種種不同的語言，這類語言通常稱為人工語言。專門用于編制計算機程序的各種人工語言稱為程序設(shè)計語言(ProgramingLanguage)。程序設(shè)計語言按照語言級別可以分為低級語言和高級語言。低級語言包括機器語言和匯編語言。低級語言與特定的機器有關(guān)，其功效高，但使用復雜、繁瑣、費時、易出差錯。機器語言是表示成數(shù)碼形式的機器基本指令集。匯編語言是機器語言部分符號化的結(jié)果。高級語言的表示方法要比低級語言更接近于待解問題的表示方法，其特點是在一定程度上與具體機器無關(guān)，易學、易用、易維護。

計算機的每一個動作、每一個步驟都是按照已經(jīng)編好的程序來執(zhí)行的，而程序需要用人們能掌握的語言來編寫，于是出現(xiàn)了程序設(shè)計語言。計算機程序設(shè)計語言的發(fā)展經(jīng)歷了從機器語言、匯編語言到高級語言的歷程。

1．機器語言

電子計算機所使用的是由“0”和“1”組成的二進制數(shù)，二進制是計算機語言的基礎(chǔ)。計算機發(fā)明之初，人們只能用計算機的語言去命令計算機工作，也就是寫出一串串由“0”和“1”組成的指令序列交由計算機執(zhí)行，這種語言就是機器語言。使用機器語言編寫程序是一件十分繁瑣的工作，特別是在程序有錯需要修改時更加困難，而且編出的程序不便于記憶、閱讀和書寫，還容易出錯。由于每臺計算機的指令系統(tǒng)往往各不相同，因此在一臺計算機上執(zhí)行的程序要想在另一臺計算機上執(zhí)行，必須另編程序，可移植性較差，造成了重復工作。但由于使用的是針對特定型號計算機的語言，故而機器語言運算效率是所有語言中最高的。機器語言是第一代計算機語言。

2．匯編語言

為了克服機器語言難讀、難編、難記和易出錯的缺點，人們用與代碼指令實際含義相近的英文縮寫詞、字母和數(shù)字等符號取代指令代碼，例如用ADD代表加法，用MOV代表數(shù)據(jù)傳遞等。這樣，人們能較容易讀懂并理解程序，使得糾錯及維護變得方便了。這種程序設(shè)計語言稱為匯編語言，即第二代計算機語言。然而計算機是不認識這些符號的，這就需要一個專門的程序負責將這些符號翻譯成二進制數(shù)的機器語言，這種翻譯程序稱為匯編程序。匯編語言仍然是面向機器的語言，使用起來還是比較繁瑣，通用性也差。匯編語言是低級語言。但是，用匯編語言編寫的程序，其目標程序占用內(nèi)存空間少，運行速度快，有著高級語言不可替代的用途。

3．高級語言

不論是機器語言還是匯編語言，都是面向硬件具體操作的，對機器過分依賴，要求使用者必須對硬件結(jié)構(gòu)及其工作原理都十分熟悉，這對非計算機專業(yè)人員來說是難以達到的，對計算機的推廣應(yīng)用不利。計算機事業(yè)的發(fā)展促使人們尋求一些與人類自然語言相接近且能為計算機所接受的通用易學的計算機語言。這種與自然語言相近并被計算機接受和執(zhí)行的計算機語言稱為高級語言。高級語言是面向用戶的語言。無論何種機型的計算機，只要配備上相應(yīng)高級語言的編譯或解釋程序，則用該高級語言編寫的程序就可以運行。

1954年，第一個完全脫離機器硬件的高級語言FORTRAN問世了，自此之后，共有幾百種高級語言出現(xiàn)，其中有重要意義的有幾十種，影響較大、使用較普遍的有FORTRAN、ALGOL、COBOL、BASIC、LISP、Pascal、C、PROLOG、Ada、C++、VC、VB、Delphi、Java等。高級語言的出現(xiàn)使得計算機程序設(shè)計語言不再過度地依賴某種特定的機器或環(huán)境。這是因為高級語言在不同的平臺上會被編譯成不同的機器語言，而不是直接被機器執(zhí)行的。計算機并不能直接地接受和執(zhí)行用高級語言編寫的源程序。高級語言源程序在輸入計算機時，通過“翻譯程序”翻譯成機器語言形式的目標程序，計算機才能識別和執(zhí)行。這種“翻譯”通常有兩種方式，即編譯方式和解釋方式。編譯方式是指在源程序執(zhí)行之前，就將程序源代碼“翻譯”成目標代碼(機器語言)，因此目標程序可以脫離其語言環(huán)境獨立執(zhí)行，使用比較方便、效率較高。但應(yīng)用程序一旦需要修改，必須先修改源代碼，再重新編譯生成新的目標文件(*.obj)才能執(zhí)行。

解釋方式是應(yīng)用程序源代碼一邊由相應(yīng)語言的解釋器“翻譯”成目標代碼(機器語言)，一邊執(zhí)行，因此效率比較低，而且不能生成可獨立執(zhí)行的可執(zhí)行文件，應(yīng)用程序不能脫離其解釋器。但這種方式比較靈活，可以動態(tài)地調(diào)整、修改應(yīng)用程序。高級語言的發(fā)展經(jīng)歷了從早期語言到結(jié)構(gòu)化程序設(shè)計語言，從面向過程到非過程化程序語言的過程。20世紀60年代中后期，軟件越來越多，規(guī)模越來越大，而軟件的生產(chǎn)基本上是各自為政，缺乏科學規(guī)范的系統(tǒng)規(guī)劃與測試、評估標準。其結(jié)果是大批耗費巨資建立起來的軟件系統(tǒng)，由于含有錯誤而無法使用，甚至帶來巨大損失，軟件給人的感覺是越來越不可靠，以致幾乎沒有不出錯的軟件。這一切，極大地震動了計算機界，歷史上稱之為“軟件危機”。人們認識到：大型程序的編制不同于小程序，它應(yīng)該是一項新的技術(shù)，應(yīng)該像處理工程一樣處理軟件研制的全過程。1969年，提出了結(jié)構(gòu)化程序設(shè)計方法；1970年，第一個結(jié)構(gòu)化程序設(shè)計語言Pascal出現(xiàn)，標志著結(jié)構(gòu)化程序設(shè)計時期的開始。

4．面向?qū)ο蟪绦蛟O(shè)計語言

20世紀80年代初開始，在軟件設(shè)計思想上，又產(chǎn)生了一次革命，其成果就是面向?qū)ο蟮某绦蛟O(shè)計。在此之前的高級語言，幾乎都是面向過程的，程序的執(zhí)行是流水線式的，在一個模塊被執(zhí)行完成前，計算機不能干別的事，也無法動態(tài)地改變程序的執(zhí)行方向。這和人們?nèi)粘Ｌ幚硎挛锏姆绞绞遣灰恢碌?。對人而言，希望發(fā)生一件事就處理一件事，也就是說，不能面向過程，而應(yīng)是面向具體的應(yīng)用功能，也就是面向?qū)ο?Object)。面向?qū)ο蟪绦蛟O(shè)計(ObjectOrientedProgramming)語言與以往各種編程語言的根本區(qū)別是程序設(shè)計思維方法不同。面向?qū)ο蟪绦蛟O(shè)計可以更直接地描述客觀世界存在的事物(即對象)及事物之間的相互關(guān)系。面向?qū)ο蠹夹g(shù)強調(diào)的基本原則是直接面對客觀事物本身進行抽象并在此基礎(chǔ)上進行軟件開發(fā)，將人類的思維方式與表達方式直接應(yīng)用在軟件設(shè)計中。1.2.2典型高級語言

目前有各種高級程序設(shè)計語言，其中以下幾種應(yīng)用非常廣泛。

FORTRAN，全稱為FormulaTranslator，意即公式翻譯。它是一種適用于科學計算的高級程序設(shè)計語言。

COBOL，全稱為CommonBusinessOrientedLanguage，意即通用商業(yè)語言。它是適用于數(shù)據(jù)處理的高級程序設(shè)計語言。

BASIC，全稱為Beginner’sAll-purposeSymbolicInstructionCode，意即初學者通用符號指令代碼。這是一種簡單易學，具有會話功能的，適用于科學計算、數(shù)據(jù)處理和實時處理的程序設(shè)計語言。1964年由美國達爾摩斯學院的基米尼和科茨完成設(shè)計并提出了BASIC語言的第一個版本，后經(jīng)過不斷豐富和發(fā)展，從基本的BASIC發(fā)展到GWBASIC、QuickBASIC、TrueBASIC、TurboBASIC、VisualBasic等。VisualBasic是一個基于Windows操作系統(tǒng)的面向?qū)ο蟮目梢暬砷_發(fā)環(huán)境和程序設(shè)計語言，它既有傳統(tǒng)BASIC易學、易懂、易記、易用的特點，又有面向?qū)ο蟆⒖梢暬O(shè)計、事件驅(qū)動、動態(tài)數(shù)據(jù)交換等特點。

Pascal是一種結(jié)構(gòu)化程序設(shè)計語言，由瑞士蘇黎世聯(lián)邦工業(yè)大學的沃斯教授研制，于1971年正式發(fā)表。它是以ALGOL語言為基礎(chǔ)，按照結(jié)構(gòu)化程序設(shè)計原則設(shè)計出來的，它的優(yōu)點是小巧、簡潔、結(jié)構(gòu)清晰、表達能力強、實現(xiàn)效能高。Pascal既重視數(shù)據(jù)結(jié)構(gòu)，又重視程序的結(jié)構(gòu)，具有大量的控制結(jié)構(gòu)，充分反映了結(jié)構(gòu)化程序設(shè)計的思想和要求，直觀易懂，使用靈活，既可用于科學計算，又能用來編寫系統(tǒng)軟件。它適用于科學計算、數(shù)據(jù)處理和描述系統(tǒng)軟件。

C語言是由美國貝爾實驗室提出的。1973年首先用于編寫UNIX操作系統(tǒng)。C程序易讀，程序效率很高，適于描述操作系統(tǒng)、編譯程序和各種軟件工具，已得到廣泛的應(yīng)用。C語言的主要特色是兼顧了高級語言和匯編語言的特點，簡潔、豐富、可移植。C語言提供了結(jié)構(gòu)式編程所需要的各種現(xiàn)代化的控制結(jié)構(gòu)。C語言是一種通用編程語言，使用Ｃ語言編寫程序，既能感覺到使用高級語言的自然，也能體會到利用計算機硬件指令的直接。

LISP是一種表處理語言，是20世紀50年代末60年代初為解決人工智能問題而發(fā)展起來的一種高級程序設(shè)計語言。LISP的理論基礎(chǔ)是數(shù)理邏輯，它很簡單又有很強的表達能力。

Java是Sun公司推出的一種編程語言。它是一種通過解釋方式來執(zhí)行的語言，語法規(guī)則和C++?類似。同時，Java也是一種跨平臺的程序設(shè)計語言。Java非常適合于企業(yè)網(wǎng)絡(luò)和Internet環(huán)境，現(xiàn)在已成為Internet中最受歡迎、最有影響的編程語言之一。Java有許多優(yōu)點：簡單、面向?qū)ο蟆⒎植际?、解釋性、可靠、安全、結(jié)構(gòu)中立性、可移植性、高性能、多線程、動態(tài)性等。1.2.3程序設(shè)計語言發(fā)展趨勢

程序設(shè)計語言是軟件的重要方面。它的發(fā)展趨勢是可視化、智能化和構(gòu)件化。

1．可視化程序設(shè)計技術(shù)

隨著Windows操作系統(tǒng)的廣泛推廣與應(yīng)用，它的可視化圖形界面與所見即所得的視覺效果越來越成為編程語言效仿的典范。典型的可視化程序設(shè)計語言集成環(huán)境有Microsoft公司提供的VisualStudio系列等。Windows系統(tǒng)本身就提供了相應(yīng)的接口功能與系統(tǒng)調(diào)用供程序開發(fā)者使用，所以可視化程序設(shè)計技術(shù)成為程序設(shè)計語言發(fā)展的一個趨勢。

2．智能化程序設(shè)計技術(shù)

程序設(shè)計技術(shù)的智能化主要體現(xiàn)在第4代程序設(shè)計語言中，它改變了傳統(tǒng)的完全手工的編程工作方式，而將編程變成了提問式與填空式的工作方式。在系統(tǒng)給出部分甚至大部分代碼以后，由程序員填入適當?shù)钠渌麅?nèi)容而完成整個編程工作，這樣的工作方式不僅提高了編程工作效率，而且避免了很多在傳統(tǒng)手工方式中存在或容易出現(xiàn)的錯誤。

3．構(gòu)件化程序設(shè)計技術(shù)

以面向?qū)ο蟪绦蛟O(shè)計為基礎(chǔ)，在可視化程序設(shè)計語言集成環(huán)境的支持下，還出現(xiàn)了構(gòu)件化程序設(shè)計的趨勢。程序設(shè)計過程中以標準的構(gòu)件為基本單位來構(gòu)造一個完整的程序，這種工作類似于房屋建筑過程中以磚和瓦為基本單位，只需將它們放置到合適的位置并固定就可以了。而構(gòu)件就相當于程序設(shè)計過程中的磚和瓦，完成對構(gòu)件屬性的定義和操作的說明就完成了所有編程工作。

1.3算法概述

著名計算機科學家沃思提出一個公式：

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

其中，數(shù)據(jù)結(jié)構(gòu)是對程序中數(shù)據(jù)的描述，主要是數(shù)據(jù)的類型和數(shù)據(jù)的組織形式；算法是對程序中操作的描述，即操作步驟。數(shù)據(jù)是操作的對象，操作的目的是對數(shù)據(jù)進行加工處理，以得到期望的結(jié)果。算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象。

1．算法的基本概念

在日常生活中，人們處理問題都有一定的步驟。例如考大學就要有這樣的步驟：要填報名單，交報名費，拿到準考證，再參加考試，填報志愿，得到錄取通知書。這些步驟都按一定的次序進行，缺一不可，次序錯了也不行。廣義地說，為解決一個問題而采取的方法和步驟，就稱為算法。算法解決“做什么”和“怎么做”的問題。計算機算法是用計算機求解一個具體問題或執(zhí)行特定任務(wù)的一組有序的操作步驟(或指令)。解決一個問題，可以有不同的方法和步驟。一般來說，希望采用簡單的和運算步驟少的方法。不僅要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。算法是根據(jù)問題定義中的信息得來的，是對問題處理過程的進一步細化，但它不是計算機可以直接執(zhí)行的，只是編制程序代碼前對處理思想的一種描述，因此它是獨立于計算機的，但它的具體實現(xiàn)是在計算機上進行的。

2．算法的特性

一個算法應(yīng)該具有以下5個重要的特征。

(1)有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束。在執(zhí)行有限步之后，計算必須終止，并得到解答。也就是說，一個算法的實現(xiàn)應(yīng)該在有限的時間內(nèi)完成。

(2)確切性：算法的每一步驟必須有確切的定義。算法中對每個步驟的解釋是唯一的。

(3)零個或多個輸入：輸入指在執(zhí)行算法時需要從外界取得的必要的信息。一個算法有零個(即沒有)或多個輸入，以刻畫運算對象的初始情況。

(4)一個或多個輸出：輸出是算法的執(zhí)行結(jié)果。一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。

(5)有效性：又稱可行性。算法中的每一個步驟能夠精確地運行，并得到確定的結(jié)果，即用筆和紙通過有限次運算可完成。

3．算法的描述

算法的常用表示方法有如下幾種：

(1)使用自然語言描述算法；

(2)使用流程圖描述算法；

(3)使用N-S結(jié)構(gòu)圖表示算法；

(4)使用偽代碼描述算法。

下面以求解n!=1×2×3×4×5×…×(n-1)×n為例說明算法的3種描述方法。第1種：使用自然語言描述求n!的算法。

①確定一個n的值；

②假設(shè)等號右邊的算式項中的初始值i為1；

③假設(shè)變量f中存放n!的值，且初始值為1；

④?i≤n時，執(zhí)行⑤，否則轉(zhuǎn)出執(zhí)行⑧；

⑤計算f乘以i的值后，重新賦值給f；

⑥計算i加1，然后將值重新賦值給i；

⑦轉(zhuǎn)去執(zhí)行④；

⑧輸出f的值，即n!?的值，算法結(jié)束。從上面的這個描述的求解過程中不難發(fā)現(xiàn)，使用自然語言描述算法的方法雖然比較容易掌握，但是存在著很大的缺陷。例如，當算法中含有多分支或循環(huán)操作時很難表述清楚。另外，使用自然語言描述算法還很容易造成歧義(稱之為二義性)，可能使他人對相同的一句話產(chǎn)生不同的理解。

第2種：使用流程圖描述求n!的算法，如圖1-1所示。圖1-1求n！的算法流程圖從圖1-1中，可以比較清晰地看出求解問題的執(zhí)行過程。流程圖用一些圖框表示各種操作。用圖形表示算法，直觀形象，易于理解。在進一步學習使用流程圖描述算法之前，有必要對流程圖中的一些常用符號做一個解釋。流程圖的符號如表1-1所示。表1-1流程圖的符號流程圖的缺點是在使用標準中沒有規(guī)定流程線的用法，因為流程線能夠轉(zhuǎn)移、指出流程控制方向，即算法中操作步驟的執(zhí)行次序。在早期的程序設(shè)計中，曾經(jīng)由于濫用流程線的轉(zhuǎn)移而導致了可怕的“軟件危機”，震動了整個軟件業(yè)，并展開了關(guān)于“轉(zhuǎn)移”用法的大討論。

第3種：使用N-S結(jié)構(gòu)圖描述求n!?的算法。

針對傳統(tǒng)流程圖存在的問題，美國學者I.Nassi和B.Shneiderman于1973年提出一種新的結(jié)構(gòu)化流程圖形式，即N-S結(jié)構(gòu)圖。Chapin在1974年對其進行了進一步擴展，因此，N-S結(jié)構(gòu)圖又稱為Chapin圖或盒狀圖。

N-S結(jié)構(gòu)圖的主要特點是完全取消了流程線，不允許有隨意的控制流，全部算法寫在一個矩形框內(nèi)，該矩形框以3種基本結(jié)構(gòu)(順序、選擇、循環(huán))描述符號為基本復合而成。

無論是使用自然語言還是使用流程圖描述算法，都僅僅是表述了編程者解決問題的一種思路，無法被計算機直接接受并操作。由此引進了第4種非常接近于計算機編程語言的算法描述方法——偽代碼。第4種：使用偽代碼描述求n!?的算法。

算法開始：

輸入n的值;

置i的初值為1;

置f的初值為1;

當i<=?n時，執(zhí)行下面的操作

使f=?f*i;

使i=i+1;

(循環(huán)體到此結(jié)束)

輸出f的值;

算法結(jié)束也可以寫成以下形式：

BEGIN /*算法開始*/

輸入n的值；

i←1； /*為變量i賦初值*/

f←1； /*為變量f賦初值*/

whilei<=n

/*當變量i<=n時，執(zhí)行下面的循環(huán)體語句*/

{f←f*i；

i←i+1；}

輸出f的值；

END /*算法結(jié)束*/偽代碼是一種在書寫程序或描述算法時使用的非正式、透明的表述方法，它并非是一種編程語言。這種方法針對的是一臺虛擬的計算機。偽代碼通常采用自然語言、數(shù)學公式和符號來描述算法的操作步驟，同時采用計算機高級語言(如C、Pascal、VB、C++、Java等)的控制結(jié)構(gòu)來描述算法步驟的執(zhí)行順序。偽代碼書寫格式比較自由，容易表達出設(shè)計者的思想，寫出的算法很容易修改。但是用偽代碼寫的算法不如流程圖直觀，可能會出現(xiàn)邏輯上的錯誤。

4．算法分析

對于同一個問題可以設(shè)計出不同的算法，各種算法之間肯定有是否適合和“好”“差”之分。衡量一個適合的、“好”的算法，在其必須是正確的基礎(chǔ)上，還應(yīng)遵循下列幾個方面：

(1)易讀性：算法應(yīng)易于閱讀和理解，以便于調(diào)試、修改和擴充。

(2)高效性：算法應(yīng)具有較高的時間效率和空間效率，即占用較短的執(zhí)行時間和較少的存儲空間。當然，這兩者都和問題的規(guī)模有關(guān)。

(3)健壯性：正確的輸入能得到正確的輸出，這是算法必須具有的特性之一。但當遇到非法輸入時，算法應(yīng)能做出反應(yīng)或處理(如提示信息等)，而不會產(chǎn)生不需要的或不正確的結(jié)果。

例如，在算法中總是采用較簡單的方法以及模塊化函數(shù)以增強算法的易讀性；采用步驟較少的求解方法以提高算法的時間效率；對可能發(fā)生的各種現(xiàn)象及輸入形式給出應(yīng)對措施以提高算法的健壯性。要確定一個算法是適合的、“好”的算法，就需要進行算法分析。算法分析的兩個主要方面是分析算法的時間效率和空間效率，目的是以求改進算法或?qū)Σ煌乃惴ㄟM行比較。鑒于目前情況下運算空間較為充足，我們把算法的時間效率分析作為主要內(nèi)容。

算法運行的時間分析和程序運行的時間分析是有區(qū)別的。同一算法由不同的程序員所編寫的程序有優(yōu)劣之分，程序運行的時間也就有所不同；程序在不同的機器上運行的速度又和機器本身的速度有關(guān)。而我們感興趣的是對解決問題的算法作時間上的度量分析，或?qū)鉀Q同一問題的兩種或兩種以上的算法運行時間加以比較。

1.4C語言程序設(shè)計

1.4.1C語言的發(fā)展歷史

C語言是國際上流行的、很有發(fā)展前途的計算機高級語言。C語言適合作為“系統(tǒng)描述語言”。它既可以用來編寫系統(tǒng)軟件，也可以用來編寫應(yīng)用程序。以前操作系統(tǒng)等系統(tǒng)軟件主要采用匯編語言編寫。匯編語言依賴于計算機硬件，程序的可讀性、可移植性都比較差。為了提高可讀性和可移植性，人們希望采用高級語言編寫這些軟件，但是一般的高級語言難以實現(xiàn)匯編語言的某些操作，特別是針對硬件的一些操作(如內(nèi)存地址的讀寫，直接硬件、二進制位的操作)。人們設(shè)法尋找一種既具有一般高級語言特性，又具有低級語言特性的語言，C語言就在這種情況下應(yīng)運而生。

C語言的發(fā)展如下：

ALGOL60→CPL→BCPL→B→C→標準C→ANSIC→ISOC

ALGOL60：一種面向問題的高級語言。ALGOL60離硬件較遠，不適合編寫系統(tǒng)程序。

CPL(CombinedProgrammingLanguage，組合編程語言)：CPL是一種在ALGOL60基礎(chǔ)上發(fā)展出來的更接近硬件的語言。CPL規(guī)模大，實現(xiàn)困難。

BCPL(BasicCombinedProgramminglanguage，基本的組合編程語言)：BCPL是對CPL進行簡化后的一種語言。

B語言：B語言是對BCPL進一步簡化所得到的一種很簡單的接近硬件的語言。B語言取BCPL語言的第一個字母。B語言精練、接近硬件，但過于簡單，數(shù)據(jù)無類型。B語言誕生后，UNIX開始用B語言改寫。

C語言：C語言是在B語言基礎(chǔ)上增加數(shù)據(jù)類型而設(shè)計出的一種語言。C語言取BCPL的第二個字母。C語言誕生后，UNIX很快用C語言改寫，并被移植到其他計算機系統(tǒng)。

標準C、ANSIC、ISOC：標準化的C語言。

最初UNIX操作系統(tǒng)是采用匯編語言編寫的，B語言版本的UNIX是第一個用高級語言編寫的UNIX。在C語言誕生后，UNIX很快用C語言改寫，C語言良好的可移植性很快使UNIX從PDP計算機移植到其他計算機平臺，隨著UNIX的廣泛應(yīng)用，C語言也得到推廣。從此C語言和UNIX像一對孿生兄弟，在發(fā)展中相輔相成，UNIX和C很快風靡全球。從C語言的發(fā)展歷史可以看出，C語言是一種既具有一般高級語言特性(ALGOL60帶來的高級語言特性)，又具有低級語言特性(BCPL帶來的接近硬件的低級語言特性)的程序設(shè)計語言。C語言從一開始就是用于編寫大型、復雜系統(tǒng)軟件的，當然C語言也可以用來編寫一般的應(yīng)用程序。也就是說，C語言是程序員的語言。

IBMPC微機DOS、Windows平臺上常見的C語言版本有Borland公司的TurboC、TurboC++、BorlandC++，C++Builder(Windows版本)，以及Microsoft公司的MicrosoftC，VisualC++(Windows版本)等。1.4.2C語言的特點

C語言具有下列特點(其中(1)～(6)屬于高級語言特性，(7)、(8)屬于低級語言特性)：

(1)?C語言的語言成分簡潔、緊湊，書寫形式自由。

將C語言程序段與實現(xiàn)同樣功能的Pascal語言程序段進行比較，如表1-2所示。表1-2C語言程序段與Pascal語言程序段的比較

(2)?C語言擁有豐富的數(shù)據(jù)類型。C語言具有整型、實型、字符型、數(shù)組類型、指針類型、結(jié)構(gòu)體類型、共同體類型等數(shù)據(jù)類型，能方便地構(gòu)造更加復雜的數(shù)據(jù)結(jié)構(gòu)(如使用指針構(gòu)造鏈表、樹、棧)。

(3)?C語言的運算符豐富，功能更強大。

①C語言具有復合的賦值運算符“+[-*/%]=”(加等、減等、乘等、除等),“>>=”“<<=”(右移等、左移等),“&[||！]=”(與等、或等、非等)。

x+=5等價于x=x+5

②C語言有條件運算符“?:”，可代替簡單的if/else語句。如果需要表示：“如果x小于或等于0，則y為0；否則y為1”可以采用：

y=x<=0?0:1;

如果用一般的程序設(shè)計語言表示，就應(yīng)該像下面這樣表示：

if(x<=0)y=0;

elsey=1;

C語言避免了一切可能的啰嗦。③C語言中連賦值這種操作都定義為運算符，也就是說賦值操作本身可以作為表達式的一部分，參與運算。如：

if((p=malloc(sizeof(int)))==NULL){printf(“Error!”);exit(1);}

改寫為一般形式：

p=malloc(sizeof(int));

if(p==NULL){printf(“Error!”);exit(1);}

又如下面算式是正確的：

x=y=z=6;

改寫為一般形式：

z=6;y=6;x=6;

(4)?C語言是結(jié)構(gòu)化的程序設(shè)計語言。C語言具有結(jié)構(gòu)化的控制語句(if/else,switch/case,for,while,do…while)。函數(shù)是C語言程序的模塊單位。

(5)?C語言對語法限制不嚴格，程序設(shè)計靈活。

C語言不檢查數(shù)組下標越界，不限制對各種數(shù)據(jù)的轉(zhuǎn)化(編譯系統(tǒng)可能對不合適的轉(zhuǎn)化進行警告，但不限制)，不限制指針的使用，程序正確性由程序員保證。實踐中，C語言程序編譯時會提示“警告錯”或“嚴重錯誤”。警告錯表示使用的語法可能有問題，但有時可以忽略，程序仍然可以完成編譯工作，然后運行。(但是一般情況下警告錯往往意味著程序真的有問題，應(yīng)該認真地檢查。)“嚴重錯誤”是不能忽略的，編譯系統(tǒng)發(fā)現(xiàn)嚴重錯誤，就不會產(chǎn)生目標代碼。靈活和安全是一對矛盾，對語法限制的不嚴格可能也是C語言的一個缺點，比如黑客可能使用越界的數(shù)組攻擊計算機系統(tǒng)。Java語言是優(yōu)秀的網(wǎng)絡(luò)應(yīng)用程序開發(fā)語言，它絕對不允許數(shù)組越界。此外Java不使用指針，不能直接操作客戶計算機上的文件，語法檢查相當嚴格，程序正確性容易保證，但是Java在編程時卻缺乏靈活性。

(6)?C語言編寫的程序具有良好的可移植性。用C語言編制的程序基本上不需要修改或只需要少量修改就可以移植到其他的計算機系統(tǒng)或其他的操作系統(tǒng)。

(7)?C語言可以實現(xiàn)匯編語言的大部分功能。C語言可以直接操作計算機硬件，如寄存器、各種外設(shè)I/O端口等。C語言的指針可以直接訪問內(nèi)存物理地址。C語言類似匯編語言的位操作可以方便地檢查系統(tǒng)硬件的狀態(tài)。C語言適合編寫系統(tǒng)軟件。

(8)?C語言編譯后生成的目標代碼小，質(zhì)量高，程序的執(zhí)行效率高。有資料顯示，C語言編譯后生成的目標代碼只比匯編代碼效率低10%～20%。1.4.3C語言程序基本結(jié)構(gòu)

1．C語言字符集

字符是C語言最基本的元素。C語言字符集由字母、數(shù)字、空白、標點和特殊字符組成(在字符串常量和注釋中還可以使用漢字等其他圖形符號)。由字符集中的字符可以構(gòu)成C語言進一步的語法成分(如標識符、關(guān)鍵詞、運算符等)。

(1)字母：A～Z，a～z。

(2)數(shù)字：0～9。

(3)空白符：空格、制表符(跳格)、換行符(空行)的總稱?？瞻追嗽谧址⒆址杏幸饬x外，編譯系統(tǒng)忽略其他位置的空白?？瞻追诔绦蛑兄皇瞧鸬介g隔作用。在程序的恰當位置使用空白將使程序更加清晰，增強程序的可讀性。

(4)標點符號、特殊字符。

(5)標識符(名字)：用來標識變量名、符號常量名、函數(shù)名、數(shù)組名、類型名等實體(程序?qū)ο?的有效字符序列。標識符由用戶自定義(取名字)。

2．C語言標識符定義規(guī)則

(1)標識符只能由字母、數(shù)字和下劃線三種字符組成，且第一個字符必須為字母或下劃線。例如：

合法的標識符：Sum,average,_total,Class,day,stu_name,p4050

不合法的標識符：M.D.John,$123,#33,3D64,a>b

(2)大小寫敏感。C程序員習慣變量名小寫，常量名大寫。例如：sum不同于Sum，BOOK不同于book。

(3)?ANSIC沒有限制標識符長度，但各個編譯系統(tǒng)都有自己的規(guī)定和限制(TC為32個字符，MSC為8個字符)。例如：student_name和student_number，如果取8個字符，則這兩個標識符是相同的。

(4)標識符不能與“關(guān)鍵詞”同名，也不能與系統(tǒng)預先定義的“標準標識符”同名。

建議標識符命名應(yīng)當有一定的意義，做到見名知義。

3．關(guān)鍵詞(保留字)

關(guān)鍵詞是C語言規(guī)定的具有特定意義的字符串。

4．運算符

運算符將常量、變量、函數(shù)連接起來組成表達式，表示各種運算。運算符可以由一個或多個字符組成。運算符根據(jù)參與運算的操作數(shù)的個數(shù)分為單目、雙目和三目運算符。

5．分隔符

分隔符包括逗號和空格，起分隔、間隔作用。

6．注釋符

“/*”和“*/”構(gòu)成一組注釋符。編譯系統(tǒng)將“/*”和“*/”之間的所有內(nèi)容看做注釋。編譯時編譯系統(tǒng)忽略注釋。

(1)注釋在程序中的作用是提示或解釋。

注釋與軟件的文檔同等重要，要養(yǎng)成使用注釋的良好習慣，這對軟件的維護相當重要。程序是要給別人看的，自己也許還會看自己幾年前編制的程序(相當于別人看程序)，清晰的注釋有助于他人理解程序、算法的思路。

(2)在軟件開發(fā)過程中，還可以將注釋用于程序的調(diào)試——暫時屏蔽一些語句。

例如，在調(diào)試程序時暫時不需要運行某段語句，而又不希望從程序中刪除它們，則可以使用注釋符將這段程序框起來，暫時屏蔽這段程序，在以后可以方便地恢復。7．程序基本組成

下面通過一些簡單例子來說明C程序的基本組成。

/*源程序1-1*/

main()

{

printf(“ThisisaCprogram.\n”);

}

說明：本程序的功能是輸出一行信息：

ThisisaCprogram.

main表示“主函數(shù)”。每個C語言程序都必須有一個main函數(shù)，它是每一個C語言程序的執(zhí)行起始點(入口點)。main()表示“主函數(shù)”main的函數(shù)頭。

用{}括起來的是“主函數(shù)”main的函數(shù)體。main函數(shù)中的所有操作(或語句)都在這一對{}之間。也就是說，main函數(shù)的所有操作都在main函數(shù)體中。

“主函數(shù)”main中只有一條語句，它是C語言的庫函數(shù)，功能是用于程序的輸出(顯示在屏幕上)。本例用于將一個字符串“ThisisaCprogram.\n”的內(nèi)容輸出，即在屏幕上顯示如下內(nèi)容：

ThisisaCprogram.

_(回車/換行)

注意：每條語句都要用“；”號結(jié)束。

/*源程序1-2*/

main() /*計算兩數(shù)之和*/

{

inta,b,sum; /*這是定義變量*/

a=123;b=456; /*以下3行為C語句*/

sum=a+b;

printf(“sum=%d\n”,sum);

}說明：本程序計算兩數(shù)之和，并輸出結(jié)果。

同樣，此程序也必須包含一個main函數(shù)作為程序執(zhí)行的起點。{}之間為main函數(shù)的函數(shù)體，main函數(shù)所有操作均在main函數(shù)體中。

/*?和?*/?括起來的部分是一段注釋，注釋只是為了改善程序的可讀性，在編譯、運行時不起作用(事實上編譯時會跳過注釋，目標代碼中不會包含注釋)。注釋可以放在程序任何位置，并允許占用多行，只是需要注意“/*”和“*/”匹配，一般不要嵌套注釋。

inta,b,sum;是變量聲明，聲明了3個具有整數(shù)類型的變量a、b、sum。C語言的變量必須先聲明再使用。

a=123;b=456;是兩條賦值語句。將整數(shù)123賦給整型變量a，將整數(shù)456賦給整型變量b。a、b兩個變量分別為123、456。

注意這是兩條賦值語句，每條語句均用“；”結(jié)束。

也可以將這兩條語句寫成兩行，即：

a=123;

b=456;

由此可見，C語言程序的書寫相當隨意，但是為了保證容易閱讀，要遵循一定的規(guī)范。

sum=a+b;是將a、b兩變量內(nèi)容相加，然后將結(jié)果賦值給整型變量sum。此時sum的內(nèi)容為579。

printf(“sum=%d\n”,sum);是調(diào)用庫函數(shù)輸出sum的結(jié)果。%d為格式控制，表示sum的值以十進制整數(shù)形式輸出。

程序運行后，輸出(顯示)如下內(nèi)容：

sum=579

_(回車/換行)

/*源程序1-3*/

main() /*主函數(shù)*/

{ /*main函數(shù)體開始*/

inta,b,c;/*聲明部分定義變量*/

scanf(“%d,%d”,&a,&b);

c=max(a,b);/*調(diào)用max，將調(diào)用結(jié)果賦給c*/printf("max=%d",c);

} /*main函數(shù)體結(jié)束*/

intmax(intx,inty) /*計算兩數(shù)中較大的數(shù)*/

{ /*max函數(shù)體開始*/

intz; /*聲明部分，定義變量*/

if(x>y)z=x;

elsez=y;

returnz; /*將z值返回，通過max帶回調(diào)用處*/

} /*max函數(shù)體結(jié)束*/說明：輸入兩個整數(shù)，計算兩者較大的數(shù)，并輸出。

本程序包括兩個函數(shù)。其中主函數(shù)main仍然是整個程序執(zhí)行的起點。函數(shù)max計算兩數(shù)中較大的數(shù)。

主函數(shù)main調(diào)用scanf函數(shù)獲得兩個整數(shù)，存入a、b兩個變量，然后調(diào)用函數(shù)max獲得兩個數(shù)字中較大的值，并賦給變量c。最后輸出變量c的值(結(jié)果)。

intmax(intx,inty)是函數(shù)max的函數(shù)頭。函數(shù)max的函數(shù)頭表明此函數(shù)獲得兩個整數(shù)，返回一個整數(shù)。

函數(shù)max同樣也用{}將函數(shù)體括起來。max的函數(shù)體是函數(shù)max的具體實現(xiàn)。從參數(shù)表獲得數(shù)據(jù)，處理后得到結(jié)果z，然后將z返回調(diào)用函數(shù)main。本例還表明：除了可以調(diào)用庫函數(shù)外，還可以調(diào)用用戶自己定義、編制的函數(shù)。

綜合上述三個例子，我們對C語言程序的基本組成和形式(程序結(jié)構(gòu))有了一個初步了解：

(1)?C程序由函數(shù)構(gòu)成(C是函數(shù)式的語言，函數(shù)是C程序的基本單位)。

一個C源程序至少包含一個main函數(shù)，也可以包含一個main函數(shù)和若干個其他函數(shù)。函數(shù)是C程序的基本單位。

被調(diào)用的函數(shù)可以是系統(tǒng)提供的庫函數(shù)，也可以是用戶根據(jù)需要自己編寫設(shè)計的函數(shù)。C是函數(shù)式的語言，程序的全部工作都是由各個函數(shù)完成的。編寫C程序就是編寫一個個函數(shù)。

C函數(shù)庫非常豐富，ANSIC提供100多個庫函數(shù)，TurboC提供300多個庫函數(shù)。

(2)?main函數(shù)(主函數(shù))是每個程序執(zhí)行的起始點。

一個C程序總是從main函數(shù)開始執(zhí)行的，而不論main函數(shù)在程序中的位置如何。可以將main函數(shù)放在整個程序的最前面，也可以放在整個程序的最后，或者放在其他函數(shù)之間。

(3)一個函數(shù)由函數(shù)首部和函數(shù)體兩部分組成。

①函數(shù)首部：一個函數(shù)的第一行。

返回值類型函數(shù)名([函數(shù)參數(shù)類型1函數(shù)參數(shù)名1]

?

[,…,函數(shù)參數(shù)類型2，函數(shù)參數(shù)名2])注意：函數(shù)可以沒有參數(shù)，但是后面的一對()不能省略，這是格式的規(guī)定。

②函數(shù)體：函數(shù)首部下用一對{}括起來的部分。如果函數(shù)體內(nèi)有多個{}，則最外層是函數(shù)體的范圍。函數(shù)體一般包括聲明部分和執(zhí)行部分兩部分。

{

[聲明部分]：在這部分定義本函數(shù)所使用的變量。

[執(zhí)行部分]：由若干條語句組成命令序列(可以在其中調(diào)用其他函數(shù))。

}

(4)?C程序書寫格式自由，一行可以寫幾個語句，一個語句也可以寫在多行上。

C程序沒有行號，也沒有FORTRAN、COBOL那樣嚴格規(guī)定的書寫格式(語句必須從某一列開始)。

C語言每條語句的最后必須有一個分號“；”表示語句的結(jié)束。

可以使用?/*?…?*/?對C程序中的任何部分作注釋。注釋可以提高程序可讀性，使用注釋是編程人員的良好習慣。實踐中，編寫好的程序往往需要修改、完善，事實上沒有一個應(yīng)用系統(tǒng)是不需要修改、完善的。很多人會發(fā)現(xiàn)自己編寫的程序在經(jīng)歷了一些時間以后，由于缺乏必要的文檔和注釋，最后連自己都很難再讀懂，需要花費大量時間重新思考、理解原來的程序。這浪費了大量的時間。如果一開始編程就對程序進行注釋，雖然剛開始麻煩一些，但日后可以節(jié)省大量的時間。

一個實際的系統(tǒng)往往由多人合作開發(fā)，程序文檔和注釋是其中重要的交流工具。

8．輸入/輸出

C語言本身不提供輸入/輸出語句，輸入/輸出的操作是通過調(diào)用庫函數(shù)(scanf，printf)完成的。

輸入/輸出操作涉及具體計算機硬件，把輸入/輸出操作放在函數(shù)中處理，可以簡化C語言和C的編譯系統(tǒng)，便于C語言在各種計算機上實現(xiàn)。不同的計算機系統(tǒng)需要對函數(shù)庫中的函數(shù)做不同的處理，以便實現(xiàn)同樣或類似的功能。

不同的計算機系統(tǒng)除了提供函數(shù)庫中的標準函數(shù)外，還按照硬件的情況提供一些專門的函數(shù)。因此不同計算機系統(tǒng)提供的函數(shù)數(shù)量和功能會有一定差異。1.4.4C語言程序的開發(fā)環(huán)境

由高級語言編寫的程序稱為源程序。由于CPU只能直接理解機器語言，不能直接理解源程序，因此由高級語言編寫的源程序必須經(jīng)編譯或解釋加工以后才能被計算機理解。把源程序“翻譯”為機器語言的過程稱為“編譯(compile)”，使用稱為“編譯程序(compiler)”的程序完成編譯任務(wù)。編譯程序把程序員編寫的類自然語言的源程序文件翻譯為機器指令，并以目標文件(*.obj)的形式存放在磁盤上。目標文件不能裝入內(nèi)存運行，必須使用“連接程序(如link.exe)”連接為可執(zhí)行程序文件(*.exe)后才能被執(zhí)行。高級語言編程步驟如圖1-2所示。圖1-2高級語言編程步驟下面以源程序1-3為例說明C程序的上機方法。程序文件名為2.C，C程序開發(fā)環(huán)境為VisualC++6.0。

1．啟動VisualC++6.0開發(fā)環(huán)境

從“開始”菜單中選擇“程序\MicrosoftVisualStudio6.0\

MicrosoftVisualC++6.0”，啟動VC++，顯示VisualC++6.0開發(fā)環(huán)境窗口，如圖1-3所示。圖1-3VisualC++6.0開發(fā)環(huán)境窗口

2．創(chuàng)建一個新項目

(1)單擊“文件(File)”菜單中的“新建(New)”選項，顯示“新建”對話框，如圖1-4所示。選擇對話框中的“工程(Project)”選項卡，以便生成新的工程。在產(chǎn)生新工程時，系統(tǒng)自動生成一個