第1章 程序設計基礎

本章資源

本章主要介紹程序的概念及程序設計語言的分類、C語言的發展歷史與特點、程序設計的本質、算法及算法表示方法、結構化的程序設計等內容。目的是使讀者初步了解程序設計的內容與方法。

1.1 程序設計語言

計算機和人類之間不能完全使用自然語言進行交流，需要借助計算機能夠理解并執行的“計算機語言”。和人類語言類似，計算機語言是語法、語義與詞匯的集合，它用來表達計算機程序。計算機語言也稱為程序設計語言。

程序設計語言種類較多，C語言是最常用的程序設計語言之一，通過對C語言的擴充還產生了如C++、Java、C#等語言。各種語言具有相通之處，因此學好C語言可以為學習其他語言打下基礎。

1.1.1 什么是程序

人們操作計算機完成各項工作，實際上是由計算機執行其中各種程序實現的，如操作系統、文字處理程序、手機內置的各類應用程序等。簡單的程序可能僅僅向屏幕輸出一段符號，而復雜的程序可以實現更多功能。

程序是用來完成特定功能的一系列指令。通過向計算機發布指令，程序設計人員可以控制其執行某些操作或進行某種運算，從而解決一個具體問題。一個程序總是按照既定順序執行，完成編程人員設計的任務。雖然每個程序內部執行順序可能不同，完成的任務有大有小，但程序編譯成功進入執行狀態后，其功能是不能被隨心所欲修改的，除非重新編寫、編譯并執行程序。

1.1.2 語言的分類

自計算機誕生以來，產生了上千種程序設計語言，有些已被淘汰，有些則得到了推廣和發展。程序設計語言經歷了由低級到高級的發展過程，可以分為機器語言、匯編語言、高級語言和面向對象的語言。低級語言包括機器語言和匯編語言；高級語言有很多種，包括C、Basic、Fortran等；面向對象的語言包括C++、Visual Basic、Java等。越低級的語言越接近計算機的二進制指令，越高級的語言越接近人類的思維方式。

1．機器語言

機器語言是計算機能夠直接識別并執行的二進制指令，執行效率高。但機器語言指令由計算機的指令系統提供，采用二進制，人們閱讀與編寫比較困難，效率低下，容易出錯。不同計算機的指令系統也不同，使得機器指令編寫的程序通用性較差。

2．匯編語言

匯編語言采用助記符來代替機器語言的指令碼，使機器語言符號化，編程效率得到提高。如加法表示為ADD，指令“ADD AX, DX”的含義是將AX寄存器中的數據與DX寄存器中的數據相加，并將結果存入AX內。匯編程序要轉換成二進制形式交由計算機執行，因此執行效率遜于機器語言。使用匯編語言編程，程序設計人員需要對機器硬件有深入了解，沒有擺脫對具體機器的依賴，編程仍然具有較大難度。

3．高級語言

為了解決計算機硬件的高速度和程序編制的低效率之間的矛盾，20世紀50年代末期產生了“程序設計語言”，也稱高級語言。高級語言比較接近自然語言，直觀、精確、通用、易學、易懂，編程效率高，便于移植。例如，語句“c=a+b”表示“求a+b的和，并將結果存入c中”。高級語言有上千種，但實際應用的僅有十幾種，如Basic、Pascal、C、Fortran、ADA、COBOL、PL/I等。

4．面向對象的程序設計語言

面向對象的程序設計語言更接近人們的思維習慣。它將事物或某個操作抽象成類，將事物的屬性抽象為類的屬性，事物所能執行的操作抽象為方法。常用的面向對象語言有Visual C++、Visual Basic、Java等。

計算機不能直接識別高級語言，需要借助編譯軟件將高級語言編寫的源程序轉換成計算機能識別的目標程序。

程序執行有編譯執行和解釋執行兩種方式。

（1）編譯執行方式是將整個源程序翻譯生成一個可執行的目標程序，該目標程序可以脫離編譯環境和源程序獨立存在和執行。

（2）解釋執行方式是將源程序逐句解釋成二進制指令，解釋一句執行一句，不生成可執行文件，它的執行速度比編譯方式慢。

1.1.3 C語言簡介

C語言的誕生源于系統程序設計的深入研究和發展。它作為書寫UNIX操作系統的語言，伴隨著UNIX的發展和流行而得到發展與普及。

（1）1967年，英國劍橋大學的M.Richards在CPL（Combined Programming Language）語言的基礎上，實現了BCPL（Basic Combined Programming Language）語言。

（2）1970年，美國貝爾實驗室的K.Thompson以BCPL語言為基礎，設計了一種類似于BCPL的語言，稱為B語言。他用B語言在PDP-7機上實現了第一個實驗性的UNIX操作系統。

（3）1972年，貝爾實驗室的D.M.Ritchie為克服B語言的諸多不足，在B語言的基礎上重新設計了一種語言，由于是B的后繼，故稱為C語言。

（4）1973年，貝爾實驗室的K.Thompson和D.M.Ritchie合作，用C語言重新改寫了UNIX操作系統。此后隨著UNIX操作系統的發展，C語言的應用越來廣泛，影響越來越大。此時的C語言主要還是作為實驗室產品在使用，并依賴于具體的機器，直到1977年才出現了獨立于具體機器的C語言編譯版本。

隨著微型計算機的普及，C語言版本也呈現多樣化。由于沒有統一標準，這些語言之間出現了許多不一致的地方。為了改變這種情況，美國國家標準學會（ANSI）為C語言制定了一套ANSI標準，就是標準C語言。1983年，美國國家標準學會頒布了C語言的新標準版本“ANSI C”。“ANSI C”比標準C語言有了很大的補充和發展。目前C語言的最新版本為ANSI C99, VC++也支持該標準。

C語言使用靈活，并具有強大生命力，已經廣泛應用于科學計算、工程控制、網絡通信、圖像處理等領域。C語言是結構化的程序設計語言，具有如下特點。

（1）語言簡潔、使用靈活，便于學習和應用。C語言的書寫形式較其他語言更為直觀、精煉。

（2）語言表達能力強。運算符達30多種，涉及的范圍廣，功能強。

（3）數據結構系統化。C語言具有現代語言的各種數據結構，并具有數據類型的構造功能，因此便于實現各種復雜的數據結構的運算。

（4）控制流結構化。C語言提供了功能很強的各種控制流語句（if、while、for、switch等），并以函數作為主要結構，便于程序模塊化，符合現代程序設計風格。

（5）C語言生成的程序質量高，程序運行效率高。實驗表明，C語言源程序生成的可執行程序的運行效率僅比匯編語言的效率低10%～20%。C語言編程速度快，程序可讀性好，易于調試、修改和移植，這些優點是匯編語言無法比擬的。

（6）可移植性好。統計資料表明。C語言程序80%以上的代碼是公共的，因此稍加修改就能移植到各種不同型號的計算機上。

C語言也存在一些不足之處，如編程自由度比較大。但總的來說，C語言是一個出色而有效的現代通用程序設計語言。

1.1.4 C語言組成

C程序由函數構成。一個C程序至少由一個函數構成，而且至少包含一個名為main的主函數。函數由函數首部和函數體組成。函數首部指出函數的類型和函數名，函數體由若干條語句構成，語句的末尾用分號表示。

【例1.1】用一個main函數構成的程序，向屏幕輸出字符串“I like Programming!”。

    #include<stdio.h>//預處理命令，用于包含文件<stdio.h>
    void main( ) //函數首部，main是函數名，即主函數
    {  printf("I like Programming! \n"); //函數printf輸出雙引號內的普通字符
    }

程序的運行結果如下。

說明：

（1）函數可以分成函數首部和函數體。花括弧“{}”括起來的是函數體。

（2）語句由一些基本字符和定義符按照C語言的語法規定組成。每個語句以分號結束。

（3）“//”后邊的文字為注釋，它們不執行，不影響程序的運行。

1.2 計算機的組成與程序設計的本質

程序設計與計算機組成有密切關系，學習計算機組成方面的知識，可以更好地理解程序設計的本質。

1.2.1 計算機系統結構

“計算機之父”馮·諾依曼提出的計算機系統結構如下。

（1）計算機由控制器、運算器、存儲器、輸入設備和輸出設備5個部分構成。

（2）計算機指令和數據均以二進制數形式表示和存放。

（3）計算機按照程序規定的順序將指令從存儲器中取出，并逐條執行。

控制器集中控制其他設備。信息分為數據信息和控制信息兩種。如圖1-1所示，在控制指令的控制下，數據按照如下方式“流動”：由輸入設備輸入數據，存儲在存儲器中，控制器和運算器直接從存儲器中取出數據（包括程序代碼和運算對象）進行處理，結果存儲在存儲器內，并由輸出設備輸出。

圖1-1 馮·諾依曼體系結構

1.2.2 程序設計的本質

程序設計的本質是設計能夠利用計算機的5個部件完成特定任務的指令序列。

【例1.2】用鍵盤輸入價格與斤數，計算櫻桃的總價。

    #include<stdio.h>
    void main()
    {  int price, number, total;
      scanf("%d%d", &price, &number);   //輸入兩個整數
      total=price*number;               //計算，將price乘以number的積存入total
      printf("total=%d\n", total);      //輸出，%d處對應輸出total的值
    }

在運行程序時輸入數據“10 3”后按“回車鍵”，顯示總價為30，程序的運行結果如下。

說明：

（1）整個程序保存在計算機的存儲器中。

（2）數據存儲在存儲器中。3個變量price、number和total，分別占用一塊存儲空間，用于存放價格、斤數和總價。

（3）通過鍵盤輸入價格與斤數。

（4）由運算器來執行乘法，求出總價。

（5）通過輸出設備顯示程序執行的結果。

通過本例可見，一個程序離不開5個部件的配合。一個程序可以沒有輸入，但是一定要有輸出才能知道程序的運行結果。

1.2.3 程序設計的過程

程序設計的一般過程如表1-1所示，在編程解決具體問題時，一般應按照這6個步驟，逐一實施來完成程序。

表1-1 程序設計過程

1．分析和定義實際問題

通過對實際問題的深入分析，準確地提煉、描述要解決的問題，找出已知與未知，明確要求。

2．建立處理模型

實際問題都是有一定規律的數學、物理等過程，用特定方法描述問題的規律和其中的數值關系，是為確定計算機實現算法而做的理論準備。如求解圖形面積一類的問題，可以歸結為數值積分，積分公式就是為解決這類問題而建立的數學模型。

3．設計算法

將要處理的問題分解成計算機能夠執行的若干特定操作，也就是確定解決問題的算法。例如，由于計算機不能識別積分公式，需要將公式轉換為計算機能夠接受的運算，如選擇梯形公式或辛普森（Simpson）公式等。

4．設計流程圖

在編寫程序前給出處理步驟的流程圖，能直觀地反映出所處理問題中較復雜的關系，從而在編程時思路清晰，避免出錯。流程圖是程序設計的良好輔助工具，它作為程序設計資料也便于交流。

5．編寫程序

編程是指用某種高級語言按照流程圖描述的步驟寫出程序，也叫做編碼。使用某種語言編寫的程序叫源程序。

6．調試程序和運行程序

調試程序和運行程序就是將寫好的程序上機檢查、編譯、調試和運行，并糾正程序中的錯誤。

1.3 算法的概念和特性

編寫程序之前，首先要找出解決問題的方法，并將其轉換成計算機能夠理解并執行的步驟，即算法。算法設計是程序設計過程中的一個重要步驟。

1.3.1 什么是算法

算法即解決一個問題所采取的一系列步驟。著名的計算機科學家Nikiklaus Wirth提出如下公式：

程序=數據結構+算法

其中，數據結構是指程序中數據的類型和組織形式。

算法給出了解決問題的方法和步驟，是程序的靈魂，決定如何操作數據，如何解決問題。同一個問題可以有多種不同算法。

1.3.2 算法舉例

計算機程序的算法，必須是計算機能夠運行的方法。理發、吃飯等動作計算機不能運行，而加、減、乘、除、比較和邏輯運算等就是計算機能夠執行的操作。

【例1.3】求1+2+3+4+…+100。

第一種算法是書寫形如“1+2+3+4+5+6+…+100”的表達式，其中不能使用省略號。這種算法太長，寫起來很費時，且經常出錯。

第二種算法是利用數學公式：

相比之下，第二種算法要簡單得多。但是，并非每個問題都有現成的公式可用，如求100!=1×2×3×4×5×…×100。

【例1.4】求5!=1×2×3×4×5。

    step1:  p=1
    step2:  i=2
    step3:  p=p × i
    step4:  i=i+1
    step5:  如果i<=5，那么轉入step3執行
    step6:  輸出p，算法結束

其中p和i是變量，它們各占用一塊內存，變量中存儲的數據是可以改變的。如圖1-2所示。變量可以被賦值，也可以取出值參加運算。本例通過循環條件“i<=5”，使得乘法操作被執行4次。

圖1-2 變量示意

【例1.5】求1×2×3×…×100。

    step1:  p=1
    step2:  i=2
    step3:  p=p × i
    step4:  i=i+1
    step5:  如果i<=100，那么轉入step3執行
    step6:  輸出p，算法結束

只需要在【例1.4】算法的基礎上，將循環條件改為“i<=100”，使得乘法操作執行99次就可以求出100個數的乘積。

【例1.6】求1×3×5×…×101。

    step1:  p=1
    step2:  i=1
    step3:  p=p×i
    step4:  i=i+2
    step5:  如果i<=101，那么轉入step3執行
    step6:  輸出p，算法結束

只需要將i的初值改為1、每次循環增加2就可以了。讀者在學習過程中要多觀摩已有的程序，分析其算法，并力求有所創新。

1.3.3 算法的特性

算法應該具有以下特性。

（1）有窮性。算法經過有限次的運算就能得到結果，而不能無限執行或超出實際可以接受的時間。如果一個程序需要執行1000年才能得到結果，對于程序執行者而言，基本就沒有什么意義了。

（2）確定性。算法中的每一個步驟都是確定的，不能含糊、模棱兩可。算法中的每一個步驟不應當被解釋為多種含義，而應當十分明確。比如，描述“小王遞給小李一件他的衣服”，這里，衣服究竟是小王的，還是小李的呢？

（3）輸入。算法可以有輸入，也可以沒有輸入，即有0個或多個輸入。

（4）輸出。算法必須有一個或多個輸出，用于顯示程序的運行結果。

（5）可行性。算法中的每一個步驟都是可以執行的，都能得到確定的結果，而不能無法執行。比如，用0作為除數就無法執行。

1.4 算法的表示方法

算法的表示方法有很多種，常用的有自然語言、偽代碼、傳統流程圖、N-S流程圖、PAD圖等。本節主要講述常用的算法表示方法，其中流程圖是學習和掌握的重點。

1.4.1 自然語言

使用自然語言，就是采用人們日常生活中的語言。如求兩個數的最大值，可以表示為如果A大于B，那么最大值為A，否則最大值為B。但在描述“陶陶告訴貝貝她的小貓丟了”時，表示的是陶陶的小貓丟了還是貝貝的小貓丟了呢？此處就出現了歧義。可見使用自然語言表示算法時拖沓冗長，容易出現歧義，因此不常使用。

1.4.2 偽代碼

偽代碼用介于自然語言和計算機語言之間的文字和符號來描述算法。例如，求兩個數的最大值可以表示為

if A大于B, then最大值為A, else最大值為B。

偽代碼的描述方法比較靈活，修改方便，易于轉變為程序，但是當情況比較復雜時，不夠直觀，而且容易出現邏輯錯誤。軟件專業人員一般習慣使用偽代碼，而初學者最好使用流程圖。

1.4.3 傳統流程圖

流程圖表示算法比較直觀，它使用一些圖框來表示各種操作，用箭頭表示語句的執行順序。傳統流程圖的常用符號如圖1-3所示。將【例1.5】求1×2×3×…×100的算法描述為傳統流程圖，如圖1-4所示。用傳統流程圖表示復雜的算法時不夠方便，也不便于修改。

圖1-3 傳統流程圖的常用符號

圖1-4 求1×2×3×…×100的傳統流程圖

1.4.4 N-S流程圖

N-S流程圖又稱盒圖，其特點是所有的程序結構均用方框表示。N-S流程圖繪制方便，避免了使用箭頭任意跳轉程序所造成的混亂，更加符合結構化程序設計的原則。它按照從上往下的順序執行語句。【例1.5】求1×2×3×…×100算法的N-S流程圖如圖1-5所示。

圖1-5 求1×2×3×…×100的N-S流程圖

1.5 結構化的程序設計方法

編出程序、得到運行結果只是學習程序設計的基本要求，要全面提高編程的質量和效率，就必須掌握正確的程序設計方法和技巧，培養良好的程序設計風格，使程序具有良好的可讀性、可修改性、可維護性。結構化程序設計方法是目前程序設計方法的主流之一。

1.5.1 結構化程序設計

1966年，Bohra和Jacopini提出了順序結構、選擇結構和循環結構3種基本結構，結構化程序設計方法使用這3種基本結構組成算法。已經證明，用3種基本結構可以組成解決所有編程問題的算法。

1．順序結構

順序結構按照語句在程序中出現的先后次序執行，其流程圖如圖1-6所示。順序結構里的語句可以是單條語句，也可以是一個選擇結構或一個循環結構。

圖1-6 順序結構

2．選擇結構

選擇結構根據條件選擇程序的執行順序。

（1）選擇結構一：流程圖如圖1-7所示，當條件成立時執行語句塊①，否則執行語句塊②。不管執行哪一個語句塊，完成后繼續執行選擇結構后的語句。選擇結構里的語句塊可以是順序語句，也可以是一個選擇結構或一個循環結構。

圖1-7 選擇結構一

（2）選擇結構二：流程圖如圖1-8所示，當條件成立的時候執行語句塊，否則什么都不執行。不管執行或不執行語句塊，完成后繼續執行選擇結構后的語句。

圖1-8 選擇結構二

3．循環結構

循環結構是指設定循環條件，在滿足該條件時反復執行程序中的某部分語句，即反復執行循環體。

（1）循環結構一：當型循環結構如圖1-9所示。判斷條件是否成立，若成立則執行語句塊，重復這一過程；當條件不成立時則不再執行循環體。如果第一次條件就不成立，那么該結構的循環體一次也不執行。

圖1-9 當型循環結構

（2）循環結構二：直到型循環結構如圖1-10所示。先執行一次語句塊，然后判斷條件是否成立，若成立則執行語句塊，重復這一過程，直到條件不成立時不再執行循環體。該結構至少執行一次語句塊。

圖1-10 直到型循環結構

循環結構里的語句塊可以是順序結構，也可以是一個選擇結構或一個循環結構。

1.5.2 結構化程序設計方法

結構化程序設計的思想和方法主要包括以下幾個內容。

（1）程序組織結構化。其原則是對任何程序都以順序結構、選擇結構、循環結構作為基本單元來進行組織。這樣的程序結構清晰、層次分明，各基本結構間相互獨立，方便閱讀和修改。

（2）程序設計采用自頂向下、逐步細化、功能模塊化的方法，就是將實際問題一步步地分解成有層次又相對獨立的子任務，對每個子任務又采用自頂向下、逐步細化的方法繼續進行分解，直至分解到一個個功能既簡單、明確，又獨立的模塊，每個模塊的設計又可以分解為結構化程序設計的3種基本結構。

習題

一、填空題

（1）程序設計語言從低級到高級可以分為______、______、______和______。

（2）程序有______和______兩種執行方式。

（3）算法具有5個特性，分別是______、______、______、______和______。

（4）常用的算法表示方法有______、______、______、______、PAD圖等。

（5）結構化程序設計可以被分解為______、______和______的組合或嵌套形式。

（6）程序設計采用______、______、功能模塊化的方法。

二、簡答題

1．程序設計語言分為幾類，各有什么特點？

2．什么是算法，算法有哪些特性？

3．寫出求解以下問題的算法，分別畫出其傳統流程圖和N-S圖。

（1）有兩個變量a和b，請交換兩個變量的值。

（2）計算。

4．簡述結構化程序設計的一般原則。