1、,第 1 章 緒 論,問題求解與程序設(shè)計 算法及其描述方法 程序設(shè)計語言 程序的基本構(gòu)成 程序的上機過程 程序風格,本章的基本內(nèi)容是：,1.1 問題求解與程序設(shè)計,人和計算機通過程序進行溝通,需要解決問題的人沒有思維的計算機,1.1 問題求解與程序設(shè)計,程序與程序設(shè)計,程序是能夠?qū)崿F(xiàn)特定功能的指令序列的集合，這些指令序列描述了計算機求解某一問題的工作步驟。 程序設(shè)計是給出解決特定問題的程序的過程，是軟件構(gòu)造活動中的重要組成部分。程序設(shè)計往往以某種程序設(shè)計語言為工具，給出這種語言下的程序。程序設(shè)計過程應當包括分析、設(shè)計、編碼、測試、排錯等不同階段。 程序員:專業(yè)的程序設(shè)計人員稱為程序員。,程序設(shè)

2、計的一般過程,1.1 問題求解與程序設(shè)計,例：哥尼斯堡七橋問題,1.1 問題求解與程序設(shè)計,【問題】17世紀的東普魯士有一座哥尼斯堡城（現(xiàn)在叫加里寧格勒，在波羅的海南岸），城中有一座島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有七座橋?qū)?個城區(qū)連接起來，于是，產(chǎn)生了一個有趣的問題：一個人是否能在一次步行中穿越全部的七座橋后回到起點，且每座橋只經(jīng)過一次。,例：哥尼斯堡七橋問題,1.1 問題求解與程序設(shè)計,【想法抽象模型】可以用A、B、C、D表示4個城區(qū)，用 7 條線表示 7 座橋，將七橋問題抽象為一個圖模型。,例：哥尼斯堡七橋問題,1.1 問題求解與程

3、序設(shè)計,【想法基本思路】是否存在歐拉回路的判定規(guī)則是： （1）如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路； （2）如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路； （3）如果沒有一個地方通奇數(shù)橋，則無論從哪里出發(fā)，都能找到歐拉回路。 由上述判定規(guī)則得到求解七橋問題的基本思路：依次計算圖中與每個節(jié)點相關(guān)聯(lián)的邊的個數(shù)（稱為節(jié)點的度），根據(jù)度為奇數(shù)的節(jié)點個數(shù)判定是否存在歐拉回路。,【算法】求解歐拉回路的算法請參見7.4.2節(jié)。 【程序】求解歐拉回路的程序請參見7.4.2節(jié)。,例：哥尼斯堡七橋問題,1.1 問題求解與程序設(shè)計,1.2 算法及其描述方法,算法：對特定問題求解步驟的一種

4、描述，是指令的有限序列。 算法必須滿足下列五個重要特性： 1. 輸入; 2. 輸出; 3. 有窮性 ; 4. 確定性; 5. 可行性。,解決問題的方法,算法及其特性,1.2 算法及其描述方法,m,例：歐幾里德算法輾轉(zhuǎn)相除法求兩個自然數(shù) m 和 n 的最大公約數(shù),n,r,歐幾里德算法,描述算法：算法設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須清楚準確地將所設(shè)計的求解步驟記錄下來。 使用算法：算法使用者知道如何調(diào)用算法。,描述算法的方法,1.2 算法及其描述方法,1. 自然語言,2. 程序流程圖,1.2 算法及其描述方法,描述算法的方法,1.2 算法及其描述方法,3. 偽代碼,描述算法的方法,偽代碼介于

5、自然語言和程序設(shè)計語言之間,結(jié)構(gòu)、語句和控制成分,處理和條件,1.3 程序設(shè)計語言,1. 第一代程序設(shè)計語言（1GL） 機器語言 2. 第二代程序設(shè)計語言（2GL） 匯編語言 3. 第三代程序設(shè)計語言（3GL） 高級語言 4. 第四代程序設(shè)計語言（4GL） 非過程式語言 5. 第五代程序設(shè)計語言（5GL） 知識型語言,程序設(shè)計語言的發(fā)展,源程序：用高級語言編寫的程序； 目標程序：用機器語言或匯編語言編寫的程序； 機器代碼：由二進制代碼表示的程序。,1.3 程序設(shè)計語言,程序設(shè)計語言的排名,程序設(shè)計語言符號系統(tǒng) 語法：包括詞法規(guī)則和語法規(guī)則，詞法規(guī)則規(guī)定了如何從語言的基本符號構(gòu)成詞法單位（也稱單

6、詞），語法規(guī)則規(guī)定了如何由單詞構(gòu)成語法單位（例如表達式、語句等），這些規(guī)則是判斷一個字符串是否構(gòu)成一個形式上正確的程序的依據(jù)。 語義：包括語義規(guī)則，規(guī)定了各詞法單位和語法單位的具體含義。,1.4 程序設(shè)計語言的基本構(gòu)成,例如 C/C+程序：,1.4 程序設(shè)計語言的基本構(gòu)成,類比自然語言： 基本符號字母 單詞單詞 語句句子 函數(shù)段落 程序文章,1.4 程序設(shè)計語言的基本構(gòu)成,基本字符集,將一些特定的字符按照一定的規(guī)則進行排列就組成了程序，這些特定的字符構(gòu)成了程序設(shè)計語言的基本字符集。 C/C+語言的基本字符集包括： 1. 英文字母：包括26個大寫英文字母AZ和26個小寫英文字符az； 2. 數(shù)字

7、：包括09等10個數(shù)字； 3. 空白符：包括空格符、回車符、制表符； 4. 特殊字符：包括29個特殊字符。,其他任何符號不允許出現(xiàn)在用這種程序設(shè)計語言編寫的程序中,1.4 程序設(shè)計語言的基本構(gòu)成,詞法單位,程序設(shè)計語言的詞法單位也稱為單詞，是由基本字符集中的字符根據(jù)詞法規(guī)則組合而成的。程序設(shè)計語言中基本的單詞有關(guān)鍵字、標識符、運算符、分隔符等四種。,1. 關(guān)鍵字 關(guān)鍵字（也稱保留字）是程序設(shè)計語言預先聲明的單詞，關(guān)鍵字的拼寫是固定的，具有特殊的含義和作用。 C/C+語言的常用關(guān)鍵字如表,詞法單位,1.4 程序設(shè)計語言的基本構(gòu)成,2. 標識符 標識符是編程人員聲明的單詞，用來表示各種程序?qū)ο螅ㄈ?/p>

8、變量、類型、函數(shù)、文件等）的名字。 不同的程序設(shè)計語言對于標識符的構(gòu)成遵循不同的規(guī)則，C/C+語言中標識符的構(gòu)成規(guī)則如下： （1）以字母（大寫或小寫）或下劃線“_”開始； （2）可以由字母（大寫或小寫）、下劃線“_”或數(shù)字（09）組成； （3）大寫字母和小寫字母代表不同的標識符；,詞法單位,1.4 程序設(shè)計語言的基本構(gòu)成,3. 運算符 運算符是程序設(shè)計語言預先規(guī)定的操作符，用于實現(xiàn)特定的算術(shù)運算或邏輯運算。C/C+語言提供了非常豐富的運算符，包括算術(shù)運算符、賦值運算符、關(guān)系運算符、邏輯運算符等 。,C/C+語言的運算符,詞法單位,1.4 程序設(shè)計語言的基本構(gòu)成,4. 分隔符 分隔符是用于分隔單

9、詞或程序正文的單詞。分隔符不表示任何實際的操作，僅用于構(gòu)造程序。,C/C+語言的分隔符,需要強調(diào)的是：由多個字符組成的單詞中間不允許夾有任何其他符號（包括空格），否則可能會改變程序的含義并且引發(fā)錯誤。,語法單位,1.4 程序的基本構(gòu)成,程序設(shè)計語言的語法單位是由單詞根據(jù)語法規(guī)則構(gòu)成的。最常見的語法單位是表達式和語句，是構(gòu)成程序的基本成分。 1. 表達式 表達式由運算符、運算對象（也稱操作數(shù)）和括號組成，能夠?qū)?shù)據(jù)進行各種運算處理。,C/C+語言提供了如下表達式： （1）算術(shù)表達式,語法單位,1.4 程序設(shè)計語言的基本構(gòu)成,（2）關(guān)系表達式,（3）邏輯表達式,（4）賦值表達式,語法單位,1.4

10、程序設(shè)計語言的基本構(gòu)成,（5）條件表達式,（6）逗號表達式,語法單位,1.4 程序設(shè)計語言的基本構(gòu)成,2. 語句 程序用于控制計算機進行數(shù)據(jù)處理以實現(xiàn)問題求解，對數(shù)據(jù)進行處理是由一個個動作組成的，語句是描述動作的基本單位，用來向計算機系統(tǒng)發(fā)出操作指令，程序的功能就是通過執(zhí)行一系列語句來實現(xiàn)的。,C語言提供了如下語句： （1）聲明語句,語法單位,1.4 程序設(shè)計語言的基本構(gòu)成,（2）表達式語句,（3）控制語句,語法單位,1.4 程序設(shè)計語言的基本構(gòu)成,（4）復合語句,（5）空語句,語法單位,1.4 程序設(shè)計語言的基本構(gòu)成,3. 模塊 為了使程序的邏輯清晰，通常將一個復雜的問題分解為多個子問題，每

11、個子問題完成一項基本任務，求解子問題的語句序列構(gòu)成模塊。,模塊化,程序,1.4 程序設(shè)計語言的基本構(gòu)成,一個程序可以是非常簡單的，也可以是特別復雜的，這取決于程序所要實現(xiàn)的功能和具體的程序設(shè)計語言。任何一種程序設(shè)計語言對于程序的構(gòu)成都有具體的規(guī)定，程序必須嚴格按照該語言規(guī)定的語法和表達方式編寫。,1.4 程序設(shè)計語言的基本構(gòu)成,例：求兩個整數(shù)中較大者的程序。,注釋信息,文件包含預處理命令,函數(shù)聲明,第1部分,返回類型，由操作系統(tǒng)檢測,庫函數(shù)，位于stdio.h文件中,函數(shù)調(diào)用，輸出max(6, 5)的結(jié)果,自定義函數(shù)，Max為函數(shù)名,返回類型，與return相對應,第2部分,第3部分,將較大值

12、max返回，即函數(shù)的執(zhí)行結(jié)果,1. 注釋。注釋不是程序的可執(zhí)行語句，在程序中的作用是對程序進行注解和說明。 2. 預處理指令。C/C+程序是由函數(shù)組成的，C/C+語言的函數(shù)分為兩大類：一類是編程人員編寫的函數(shù)，稱為自定義函數(shù)，另一類是C/C+語言編譯器提供的函數(shù)，稱為庫函數(shù)。 3. main函數(shù)。一個C/C+程序不論包含多少個函數(shù)，都有且只能有一個main函數(shù)，稱為主函數(shù)。 4. main函數(shù)的典型構(gòu)成是輸入數(shù)據(jù)、處理數(shù)據(jù)、輸出結(jié)果。 5. main函數(shù)的執(zhí)行。main函數(shù)由操作系統(tǒng)調(diào)用，在main函數(shù)執(zhí)行結(jié)束時通過return語句返回一個狀態(tài)碼，操作系統(tǒng)在程序終止時可以檢測到這個狀態(tài)碼。,1

13、.4 程序設(shè)計語言的基本構(gòu)成,C/C+程序的主要特點：,1.5 程序的上機過程,C/C+程序的上機過程通常包括程序編輯、程序編譯、程序鏈接、運行調(diào)試等幾個步驟 程序編輯。在程序編輯器中錄入程序代碼，并以文本文件的形式保存。 程序編譯。利用編譯器將編輯好的程序翻譯成二進制代碼，生成目標程序。C/C+程序編譯的成品是后綴名為.obj的目標文件。 程序鏈接。編譯后產(chǎn)生的目標文件還不能直接運行，鏈接是把目標文件和其他目標文件（如果有的話）、系統(tǒng)提供的庫函數(shù)、以及操作系統(tǒng)提供的資源，鏈接到一個可執(zhí)行文件中。 運行調(diào)試。生成可執(zhí)行文件后就可以運行了，調(diào)試的目的是發(fā)現(xiàn)并排除程序中的語義錯誤和邏輯錯誤。,1.

14、5 程序的上機過程,編程環(huán)境,1.5 程序的上機過程,廣義上，程序設(shè)計的環(huán)境包括所有與程序設(shè)計相關(guān)的硬件環(huán)境和軟件環(huán)境，狹義上，程序設(shè)計的環(huán)境是指利用程序設(shè)計語言進行程序開發(fā)的編程環(huán)境，這里只討論狹義上的編程環(huán)境。 Microsoft Visual C+ 6.0（以下簡稱VC+）集成開發(fā)環(huán)境,1.5 程序的上機過程,編成環(huán)境 VC+使用工程來管理程序文件。建立一個工程的步驟如下：,1. 單擊“文件”菜單，在彈出的下拉菜單中單擊“新建”選項，在彈出的對話框中選中Win32 Console Application（控制臺應用程序） 2. 在“位置”文本框創(chuàng)建一個文件夾，在“工程名稱”文本框鍵入一個

15、工程名稱，單擊“確定”按鈕。如下圖:,3. 在出現(xiàn)的“Win32 Application Step 1”窗體中選擇“一個空工程”，單擊“完成”按鈕，在新建工程信息窗體中單擊“確定”按鈕，工程“編程環(huán)境”就建立起來了。,編成環(huán)境,1.5 程序的上機過程,廣義上說，程序設(shè)計的環(huán)境包括所有與程序設(shè)計相關(guān)的硬件環(huán)境和軟件環(huán)境。 狹義上說，程序設(shè)計的環(huán)境是指利用程序設(shè)計語言進行程序開發(fā)的編程環(huán)境，這里只討論狹義上的編程環(huán)境。 目前的編程環(huán)境大都是交互式集成開發(fā)環(huán)境（Integrated Design Environment，IDE），包括編輯功能、編譯功能、調(diào)試功能等，此外，還包含許多編程的實用程序。

16、典型的編程環(huán)境是Visual C+，它提供了MFC類庫，可實現(xiàn)許多Windows自動編程功能。由于功能強大，也使其具有一定的復雜性，如何用好語言編程工具和環(huán)境，也是提高編程效率的因素之一。,程序編輯,1.5 程序的上機過程,輸入程序以及修改程序的過程稱為程序編輯。 各個計算機系統(tǒng)的程序編輯過程差異很大，不可能用統(tǒng)一的方式來描述，因此，在程序編輯之前，必須先熟悉所用計算機系統(tǒng)的程序編輯方法。,程序編譯,1.5 程序的上機過程,利用高級語言編寫的程序不能直接在計算機上執(zhí)行，因為計算機只能執(zhí)行二進制的機器指令，所以，必須將高級語言編寫的程序（稱為源程序）轉(zhuǎn)換為在邏輯上等價的機器指令（稱為目標程序），

17、實現(xiàn)這種轉(zhuǎn)換的程序稱為翻譯程序。,1.5 程序的上機過程,程序編譯,編譯程序的作用,C/C+程序的編譯過程,1.5 程序的上機過程,程序編譯,1. 預處理：所謂預處理是指在編譯之前對源程序進行某些預處理工作，如濾掉注釋、文件包含、宏替換等，然后再對預處理之后的源程序進行編譯。,例如，對于如下語句序列：,預處理將第一個“/*”和第一個“*/”之間放置的任何字符都當作是注釋，則濾掉注釋的結(jié)果是：,1.5 程序的上機過程,程序編譯,2. 詞法分析 詞法分析的任務是對源程序進行掃描和分解，濾掉源程序的注釋，按照詞法規(guī)則識別出一個個的單詞，如關(guān)鍵字、變量名、運算符等，并將單詞轉(zhuǎn)化為某種機內(nèi)表示。如果發(fā)現(xiàn)

18、詞法錯誤，則指出錯誤位置，給出錯誤信息。 例如，詞法分析將語句“float rate = 10;”分解為如下5個單詞： float rate = 10 ; 其中：單詞是關(guān)鍵字，單詞是標識符，單詞是運算符，單詞是常量，單詞是分隔符。,1.5 程序的上機過程,程序編譯,3. 語法分析 語法分析是編譯程序的核心部分，它的任務是對詞法分析階段得到的單詞序列按照語法規(guī)則分析出一個個的語法單位，如表達式、語句等。如果發(fā)現(xiàn)語法錯誤，則指出錯誤位置，給出錯誤信息。 例如，語法分析將語句“float rate = 10;”表示成如圖所示的語法樹，并得出分析結(jié)果：是一個語法上正確的賦值語句。,1.5 程序的上機過

19、程,程序編譯,4. 語義分析 語義分析的任務是檢查程序中語義的正確性，以保證單詞或語法單位能有意義地結(jié)合在一起，并為代碼生成收集類型信息。語義分析的一個重要部分是類型檢查，即對每個運算符的運算對象，檢查它們的類型是否合法。 例如，對于語句“float rate = 10;”，語義分析審查運算符“=”的運算對象，發(fā)現(xiàn)rate是實型，而10是整型常量，則在語法分析得到的語法樹上增加一個語義處理結(jié)點，將整型常量轉(zhuǎn)換成實型常量的運算符inttoreal，得到如圖所示的語法樹。,1.5 程序的上機過程,程序編譯,5. 生成代碼 生成代碼的任務是將形式上正確的源程序轉(zhuǎn)換為特定機器的目標程序。顯然，高級語言

20、和計算機的多樣性為目標代碼生成的理論研究和實現(xiàn)技術(shù)帶來很大的復雜性。 例如，對于語句“float a = 10;”，可以生成如下四元式序列： （inttoreal, 10, -, t1） （=, id1, t1, -） 其中，t1是編譯程序生成的臨時變量，id1是標識符rate的內(nèi)部形式。,1.5 程序的上機過程,程序鏈接,運行調(diào)試,1.5 程序的上機過程,一般的編程環(huán)境都提供相應的調(diào)試手段。調(diào)試最主要的方法是設(shè)置斷點并觀察變量。 （1）設(shè)置斷點：可以在程序的任何一個語句上做斷點標記，將來程序運行到這里時會停下來。 （2）觀察變量：當程序運行到斷點的地方停下來后，就可以觀察各個變量的值，判斷此

21、時變量的值是否是你所期望的。如果不是，則說明在斷點之前肯定存在錯誤，這樣，就可以把出錯的范圍集中在斷點之前的程序上。 還有一種常用的調(diào)試方法是單步跟蹤，即一步一步跟蹤程序的執(zhí)行過程，同時觀察變量的變化情況。 調(diào)試是一個需要耐心和經(jīng)驗的過程，也是程序設(shè)計最基本的技能。,1.6 程序風格,標識符的命名規(guī)則 標識符的命名采用如下規(guī)則： 1. 符號常量：用大寫字母表示符號常量，例如：PI、NUM等。 2. 變量：變量名中除第一個單詞外的每個單詞的首字母大寫，例如：studentName、studentAddress等。 3. 函數(shù)：為了與變量名區(qū)分開，函數(shù)名中每個單詞的首字母大寫，例如PrintTri、Max等。需要注意的是，VC+提供的庫函數(shù)是用小寫字母命名的。 4. 自定義數(shù)據(jù)類型：為了與變量名區(qū)分開，自定義數(shù)據(jù)類型名中每個單詞的首字母大寫，并且以單詞Type結(jié)尾，例如StudentType、DateType等。 5. 全局變量：為了便于區(qū)別全局變量和局部變量