c第1章-緒論201703

1、第1章 引論,1,隨著計算機技術(shù)的迅猛發(fā)展，大量應(yīng)用軟件的面世，使得計算機用戶在日常應(yīng)用中遇到的問題多數(shù)都可以借助現(xiàn)有的軟件來解決，例如Office、Matlab等。但是，在工程領(lǐng)域中，往往遇到的很多問題是繁雜多變的，所以沒有什么軟件可以包羅萬象；而且往往使用通用軟件解決專業(yè)特殊問題時，其效率會很低，甚至可能無法勝任。在這些情況下，用戶自行按照需求開發(fā)能夠完成特定功能的應(yīng)用軟件，就成為唯一的解決辦法。,為什么要學習程序設(shè)計？,2,本章

2、預(yù)期學習成果,3,軟件開發(fā)過程,4,編制程序的基本方法,5,通過收集原始資料，取得對要解決問題的一個清晰的理解，進而確定解決問題的目標以及實現(xiàn)該目標所需要的條件。,分析問題,6,數(shù)據(jù)結(jié)構(gòu)就是一類數(shù)據(jù)的表示及其相關(guān)操作。所以規(guī)劃數(shù)據(jù)結(jié)構(gòu)就是規(guī)劃如何表示和存儲該問題的數(shù)據(jù)；而設(shè)計如何求解問題的方法步驟，則是計算機算法的問題。建構(gòu)合理的數(shù)據(jù)結(jié)構(gòu)往往可以簡化算法，而好的算法設(shè)計又可以使程序具有更高的效率。,規(guī)劃數(shù)據(jù)結(jié)構(gòu)與設(shè)計算法,7,使用

3、多組樣本數(shù)據(jù)，通過手工計算，對方案的正確性進行驗證，看看它是否能夠按照預(yù)想進行工作。,驗證算法,8,選用一種程序設(shè)計語言（如C語言、C++語言、Java語言等）將前面的規(guī)劃和設(shè)計轉(zhuǎn)換成計算機能夠理解的程序。,編碼實現(xiàn),9,“測試”是在計算機上用樣本數(shù)據(jù)運行程序，檢查功能和代碼的正確性?！罢{(diào)試”就是查找和排除程序錯誤，直到能夠得到正確的運行結(jié)果為止。通常將程序中的錯誤稱為Bug，它可能是語法錯誤，也可能是邏輯錯誤。借助在集成環(huán)境的提示信

4、息，大多數(shù)語法錯誤容易找到和改正；但是要找出邏輯錯誤會困難的多，因為導致邏輯錯誤的因素很多。,測試和調(diào)試程序,10,11,問題求解過程,問題描述 【例】某人已經(jīng)在某公司工作四年，去年他的周薪提高了4%，這樣他目前周薪達到了250美元，下周他的周薪還要提高3%。想編寫程序用于在計算機屏幕上顯示其漲薪后的周薪。,12,分析問題,分析問題的目的是確定解決問題的目標、實現(xiàn)該目標所需要的條件分析問題時，首先要研究輸出，然后是輸入輸出就是用戶

5、想要看到的結(jié)果-----新的周薪輸入是實現(xiàn)目標所需要的條件-----當前周薪；增長比率,13,規(guī)劃算法,14,檢查算法,15,編碼實現(xiàn)算法、形成程序,#include using namespace std; void main ( ) {//聲明變量 float currentpay=0.0; float rate=0.0; float raise; float newpay;,16,編碼

6、實現(xiàn)算法、形成程序,//輸入當前周薪和增長比率 cout>currentpay; cout>rate;//計算周薪增長數(shù)目 raise=currentpay*rate;//計算新的周薪 newpay=currentpay+raise;//顯示新的周薪 cout<<"newpay:"<<newpay<<endl;

7、 },17,測試和調(diào)試程序,在計算機中使用樣板數(shù)據(jù)運行并調(diào)試程序。,計算機算法規(guī)定了利用計算機解決某個（或某類）特定問題的一系列運算（或稱操作序列），它是對計算機解題方案的準確與完整的描述。,計算機算法,18,表示算法的方法有很多，常見的方法有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖（三種基本結(jié)構(gòu)的流程圖、N-S流程圖）、偽代碼等。這里簡要介紹幾種常用方法。,算法的表示方法,19,步驟1：輸入n值步驟2：將1 賦值給t步驟3：將1 賦值給

8、i步驟4：計算t×i，結(jié)果賦值給t步驟5：計算i+1，結(jié)果賦值給i步驟6：如果i≤n 成立，則返回到步驟4，并從步驟4繼續(xù)向下執(zhí)行步驟7：輸出t（即輸出最終結(jié)果），計算結(jié)束,【案例1.1】 用自然語言表示求解n!的算法。,20,自然語言是人們?nèi)粘Ｊ褂玫恼Z言，如漢語、英語。使用自然語言描述算法，通俗易懂；但是往往敘述文字沉長，含義不盡嚴格，容易出現(xiàn)歧義性。,【案例1.1】 用自然語言表示求解n!的算法。,21,美國國家標

9、準化協(xié)會ANSI（American National Standard Institute）規(guī)定，使用圖符表示特定的操作，稱為流程圖（也稱為傳統(tǒng)流程圖），并已為世界各國程序設(shè)計者普遍采用。,傳統(tǒng)流程圖表示,22,【案例1.2】用傳統(tǒng)流程圖表示求解n!的算法,線,23,1966年，學者Bohra和Jacopini提出了以下述三種基本結(jié)構(gòu)作為表示算法的基本單元。其中的模塊A或模塊B代表的是一個或一組操作（或運算）。（1）順序結(jié)構(gòu)（2）選

10、擇結(jié)構(gòu)（3）循環(huán)結(jié)構(gòu),結(jié)構(gòu)化流程圖表示,24,按照流程線確定的順序依次執(zhí)行，即從a點進入結(jié)構(gòu)，首先執(zhí)行A，然后執(zhí)行B，最后從b點脫離該結(jié)構(gòu)。,順序結(jié)構(gòu),25,從a點進入結(jié)構(gòu)，按照流程，首先對給出的條件P進行判斷，然后根據(jù)判斷結(jié)果的成立與否來確定執(zhí)行流程：如果P成立，則執(zhí)行A；否則P不成立，則執(zhí)行B或不執(zhí)行任何操作。最后從b點脫離該結(jié)構(gòu)。分析選擇結(jié)構(gòu)不難發(fā)現(xiàn)：結(jié)構(gòu)中無論條件P是否成立，只能執(zhí)行A或B中之一，一定不可能既執(zhí)行A又執(zhí)行B。

11、,選擇結(jié)構(gòu),26,循環(huán)結(jié)構(gòu)可以分為當型和直到型兩類。在當型循環(huán)結(jié)構(gòu)中，從a點進入，重復(fù)執(zhí)行“對條件P1進行判斷，如果P1成立，則執(zhí)行A”，而當條件P1不成立時，循環(huán)結(jié)束，從b點脫離該結(jié)構(gòu)。在直到型循環(huán)結(jié)構(gòu)中，從a點進入，首先執(zhí)行A，然后重復(fù)執(zhí)行“對條件P2進行判斷，如果P2不成立，則執(zhí)行A”，直到條件P2成立時，循環(huán)結(jié)束，從b點脫離該結(jié)構(gòu)。,循環(huán)結(jié)構(gòu),27,分析循環(huán)結(jié)構(gòu)不難發(fā)現(xiàn)：（1）體內(nèi)一定不存在“死循環(huán)（即沒有止境的循環(huán)）”；（

12、2）兩種類型的循環(huán)在使用上是可以互換的。也就是說，凡是可以使用當型循環(huán)處理的問題，也可以使用直到型循環(huán)解決，反之亦然。,循環(huán)結(jié)構(gòu),（a）當型循環(huán) （b）直到型循環(huán),28,只有一個入口（如a），只有一個出口（如b），結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行。而且，一個算法無論多么復(fù)雜，終究可以分解為由順序、選擇和循環(huán)三種基本結(jié)構(gòu)組合而成

13、。或者說，這三種基本結(jié)構(gòu)可以組合應(yīng)用來解決任何復(fù)雜問題。而由這三種基本結(jié)構(gòu)所構(gòu)成的算法稱為結(jié)構(gòu)化算法。,三種基本結(jié)構(gòu)的共同點,29,1971年，國外學者I. Nassi和B. Shneiderman提出了一種新的流程圖形式，稱為N-S流程圖，它在三種基本結(jié)構(gòu)流程圖的基礎(chǔ)上完全去掉了流程線。,?N-S流程圖表示,（a）順序結(jié)構(gòu) （b）選擇結(jié)構(gòu) （c）當型循環(huán)

14、 （d）直到型循環(huán),30,【案例1.3】 用N-S流程圖表示求解n!的算法,31,1.算法的特征2.算法的性能3.算法的評價,算法要素與效率,32,同一個（或同一類）問題可以規(guī)劃不同的解決方案。但是，就算法本身而言，它應(yīng)具有以下主要特征：(1) 有效性：算法中的每一步驟都應(yīng)當是可執(zhí)行的，并能得到確定的結(jié)果；(2) 有窮性：無論算法有多么復(fù)雜，它都必須在有限步驟之后結(jié)束運行，而不能是無限的；(3) 確定性：組成算法

15、的每一步驟應(yīng)該具有確定的語義，而不能有任何歧義；,算法的特征,33,(4) 有零個或多個輸入：部分數(shù)據(jù)在操作之前需要通過外界賦值稱為算法的輸入，它是算法加工的對象。一個算法可以沒有輸入，也可以有多個輸入；(5) 有一個或多個輸出：算法執(zhí)行過程中對外界產(chǎn)生的任何影響（算法的運算結(jié)果）稱為算法的輸出。一個算法至少有一個輸出，也可以有多個輸出。,算法的特征,34,要設(shè)計一個“好”的算法，不僅需要保證算法正確，還要考慮算法的性能。 (1)

16、正確性：對于任意的一組輸入，包括合理的輸入和不合理的輸入，總能得到預(yù)期的輸出；(2) 可讀性：一個清晰易讀的算法有助于對算法的理解，易于調(diào)試和修改；,算法的性能,35,(3) 健壯性：對于非法的輸入，能夠做出適當?shù)姆磻?yīng)或異常情況處理，而不會產(chǎn)生一些莫名其妙的結(jié)果，更不會引起災(zāi)難性的后果；(4) 高效性：算法占用計算機資源量（主要是運行時間和存儲空間）越少效率越高。一般而言，算法的效率與算法占用計算機資源量成反比。,算法的性能,36,

17、面對同一個（或同一類型）問題不同的解決方案，通常又應(yīng)該如何抉擇呢？【案例1.4】 在一組升序排列的n個數(shù)據(jù)中，查找是否存在某指定數(shù)據(jù)。,算法的評價,37,算法1：設(shè)計這個問題的解決方案，很自然采用的方法是順序查找。即從第一個數(shù)據(jù)（也稱為元素）開始逐一比較。此時，最好的情況是只需要比較一次，第一個就是；最壞情況是需要比較n次，最后一個是，或者最后一個也不是，就不存在。假設(shè)每個元素與要查找數(shù)據(jù)相同是等概率的，則平均需要比較n/2次。,算法

18、的評價,38,算法2：采用折半查找的方法（也稱二分查找）。即先和居于中間位置的元素比較。如果比較結(jié)果為相等，則查找成功；如果比較結(jié)果為中間位置的元素小于要查找的數(shù)，則繼續(xù)在前半部分找；否則就繼續(xù)在后半部分去找。該算法最多只需要比較log2n 次。這個案例表明：通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法所需要的存儲空間少和執(zhí)行更快。只有在對這些可行的算法進行分析以后，才能知道哪一個算法效率更高。,算法的評價,39,程

19、序設(shè)計語言，俗稱為編程語言或高級語言，人們利用它能夠準確地向計算機發(fā)出指令。本教材使用的開發(fā)工具Visual Studio 2010是由Microsoft公司推出。Visual C++2010是Visual Studio 2010的一部分，并且更適用于支持開發(fā)面向Windows 7及以上的程序。而Visual Studio是一套功能完備的集成開發(fā)環(huán)境，它集編輯、編譯、調(diào)試、運行等于一體，支持Visual C、Visual Basic

20、、Visual C#等多種語言。,程序設(shè)計語言和開發(fā)工具,40,【案例1.5】 計算10+15。問題背景：編制一個簡單的程序，實現(xiàn)在計算機屏幕上打印 (輸出顯示)計算10+15的信息。編程實現(xiàn)：啟動Visual Studio 2010，創(chuàng)建一個新項目，該項目中添加程序文件并編輯內(nèi)容如下：,VC++集成開發(fā)環(huán)境與使用,41,//1.5計算10+15和10*15----C++語言#include using namespac

21、e std; void main(void ) {cout<<10+15; cout<<10*15;},【案例1.5】 計算10+15。,42,運行結(jié)果： 保存編輯好的程序并按下+，彈出程序運行窗口如下：,【案例1.5】 計算10+15。,43,問題拓展：如何使用一些格式控制符使得輸出更加美觀和友好？//1.5計算10+15和10*15----C++語言#include

22、using namespace std; void main(void ) {cout<<"10+15="<<10+15<<endl;cout<<"10*15="<<10*15<<"\n";},【案例1.5】 計算10+15。,44,說明：程序中“endl”英語意思是end of line，

23、即當前行輸出結(jié)束并換行。它與cout搭配使用，作用是輸出結(jié)束并將光標下移到下一行。程序中“\n”稱為轉(zhuǎn)義字符，它的作用是將光標下移到下一行。,【案例1.5】 計算10+15。,45,一個程序可以分成多個相互獨立的程序模塊（一段程序代碼），這些程序模塊在C/C++程序中被稱為函數(shù)。也就是說，函數(shù)是指一段能夠完成特定功能的獨立執(zhí)行的程序代碼。,一個完整的C/C++程序的基本框架,46,而函數(shù)的作用有兩個，一是方便實現(xiàn)按功能劃分任務(wù)。可以

24、將一個比較復(fù)雜的任務(wù)劃分成若干簡單的子任務(wù)，每個子任務(wù)可以由一個或多個子函數(shù)來完成，這也稱為模塊化功能；二是方便實現(xiàn)源代碼的復(fù)用。完成某個功能函數(shù)的程序代碼只有一處，而需要時可以多處使用它。,一個完整的C/C++程序的基本框架,47,C/C++程序由一個或多個函數(shù)組成，而且一個C/C++程序中一定有且只有一個以main為名稱的函數(shù)，稱為主函數(shù)。程序中有多個函數(shù)時，main( )函數(shù)的位置并不被限定，即可以是任意的。但main( )函數(shù)

25、代表了程序執(zhí)行的起始點和終止點。也就是說，不管main( )函數(shù)位置如何，程序的執(zhí)行總是從main( )函數(shù)中的第一條語句開始，并結(jié)束于main( )函數(shù)的最后一條執(zhí)行語句。,一個完整的C/C++程序的基本框架,48,C/C++語言對關(guān)鍵字以及語句的標點符號（如{、}、(、)、;和,）都嚴格為英文小寫。函數(shù)名之后必有一對小圓括號“（）”，括號中可帶有參數(shù)，也可不帶參數(shù)。“{”與“}”在這里為函數(shù)體的起止符，并必須配對使用?！皗 }”

26、之間的內(nèi)容為函數(shù)體。函數(shù)體一般由任意多行語句組成，并且“；”是每個語句的結(jié)束符。void稱為空類型。這里，表示函數(shù)既沒有參數(shù)傳遞，也沒有返回值。,一個完整的C/C++程序的基本框架,49,[注釋程序目標]#include [頭文件]using namespace std;int main(void ){ [聲明常量] [定義變量] [輸入語句] [計算語句] [輸出語句] return 0;

27、},一個完整的C/C++程序的基本框架,[注釋程序目標]#include [頭文件]using namespace std;void main(void ){ [聲明常量] [定義變量] [輸入語句] [計算語句] [輸出語句]},50,在C/C++程序中，一條條“#include xxx”語句，實質(zhì)上是一條條的編譯預(yù)處理命令，專門用于實現(xiàn)“文件包含”的預(yù)處理操作。簡單地講，編譯預(yù)處理命令的作用就

28、是告訴編譯系統(tǒng)在編譯本程序之前，首先將指定的源文件（如iostream）的全部內(nèi)容（即函數(shù)原型）包含到本程序中來。這些源文件可以是C/C++系統(tǒng)提供的，也可以是用戶提供的。通常把C/C++系統(tǒng)提供的能實現(xiàn)某些特定功能（如輸出功能）的這些源文件稱為系統(tǒng)的頭文件（或標準頭文件，簡稱頭文件）。,“文件包含”的預(yù)處理操作,51,(1) #include using namespace std;(2) #includ

29、e (3) #include "my.h"(4) #include "c:\jys\my.h",“文件包含”命令的幾種形式,52,include命令的前面不能少“#”，其后不能加分號；include命令中用尖括號與用雙引號的區(qū)別：用尖括號（）時，系統(tǒng)在系統(tǒng)目錄中尋找該文件；用雙引號（" "）但沒有給出路徑時，系統(tǒng)在默認用戶路徑和系統(tǒng)目錄中尋找該文件；用雙引號（&

30、quot; "）并給出路徑時，系統(tǒng)在用戶指定的路徑和系統(tǒng)目錄中尋找該文件。通常，系統(tǒng)的頭文件都是使用尖括號來表示。,“文件包含”命令,53,在include命令后應(yīng)配合使用using命令，用于定義命名空間（以避免與用戶命名發(fā)生沖突），且該命令后一定帶有“;”；形式(1)為C++語言的頭文件，形式(2)為C語言的頭文件。C語言頭文件在C++語言中的新命名規(guī)律是：去掉擴展名.h并在原名稱前加小寫字母c。例如：C 頭文件“s

31、tdio.h”在C++中的新名字是“cstdio”,“文件包含”命令,54,在C++語言中，“cin”是輸入流對象，符號“>>”為流提取運算符，“cin>>”用于實現(xiàn)從鍵盤緩沖區(qū)取出數(shù)據(jù)給指定變量；“cout”是輸出流對象，符號“<<”為流插入運算符，“cout<<”用于實現(xiàn)將指定數(shù)據(jù)發(fā)送到顯示器屏幕上。,輸入與輸出操作,55,注釋信息是幫助閱讀程序的說明，屬內(nèi)部文檔，可以增強程序的可讀

32、性，使程序更易理解，但它不屬于程序指令，所以與該程序的運行無關(guān)，在系統(tǒng)編譯時即被忽略。C++提供了兩種注釋方法：(1) 緊隨注釋符“//”之后至本行末位的所有字符為注釋信息；(2) 夾在注釋符“/*”與“*/”之間的所有字符為注釋信息。通常將位于源程序首部的用以說明程序功能的注釋稱為序言注釋；而將位于之后的其他所有注釋稱為解釋性注釋。,注釋符與注釋信息,56,C/C++程序的書寫格式很靈活，一行可書寫多個語句，一個語句也可寫

33、成多行，但書寫時首先應(yīng)該考慮程序的可讀性。通常采用縮進的格式：按不同層次的結(jié)構(gòu)，從不同的起始位置寫起。同一個結(jié)構(gòu)層次中的語句，都向后縮進同樣的字數(shù)。這樣對于整體結(jié)構(gòu)層次一目了然，見圖。當然，采用縮進的書寫格式也只是為了方便閱讀和維護程序，它并不能影響程序的執(zhí)行。,程序的書寫格式,57,(1) 編輯：使用文本編輯器輸入（編輯）編制好的程序（稱為源程序），并保存生成程序文件（稱為源文件），其擴展名為.cpp（C語言源文件擴展名為.c）；

34、(2) 編譯：調(diào)用編譯器對該源程序進行語法及語義分析，轉(zhuǎn)換生成為計算機能直接識別的目標文件，該文件名與源文件名相同，其擴展名為.obj；,上機編輯和運行,58,(3) 鏈接：調(diào)用連接器將程序中所用到的庫文件與該目標文件連接成為一個整體，生成可直接運行的可執(zhí)行文件，該文件名與源文件名相同，其擴展名為.exe；(4) 運行：運行該可執(zhí)行文件，獲得程序的輸出結(jié)果。,上機編輯和運行,59,一般在上機將編寫的程序編輯錄入之后，都需要經(jīng)過程序的

35、調(diào)試和運行，目的是檢查程序是否能夠正常執(zhí)行，以及執(zhí)行的結(jié)果是否與規(guī)定的預(yù)期結(jié)果相符。而如果程序發(fā)生錯誤或出現(xiàn)與預(yù)期結(jié)果不一致的情況，就要查明原因加以糾正。,調(diào)試程序,60,源程序代碼：//1.6查找錯誤并修改#include void main(void) { cout<<"Hello, world！"<<endl},【案例1.6】 調(diào)試程序，查找并糾正錯誤。,61,【案例1

36、.6】 調(diào)試程序，查找并糾正錯誤。,62,程序調(diào)試時，可能會出現(xiàn)的錯誤（稱為Bug）分為兩大類：語法錯誤邏輯錯誤,程序調(diào)試,63,語法錯誤：是編譯系統(tǒng)在編譯的過程中發(fā)現(xiàn)的錯誤，也稱編譯錯誤。這類錯誤又分為：error（錯誤）和warning（警告）。對于編譯出現(xiàn)的錯誤，必須修改成功才能繼續(xù)下一步操作。一般來說，警告多為不恰當?shù)臄?shù)據(jù)類型而引起的錯誤，并不影響后續(xù)的編譯和運行，但是也有些警告如果不被消除，可能會導致運行錯誤。邏輯錯誤

37、：是由于使用了不正確的數(shù)據(jù)或算法等引起的錯誤。通常，會因其輸出并未達到預(yù)期結(jié)果，或運行過程中發(fā)生錯誤（如數(shù)據(jù)發(fā)生溢出）而被發(fā)現(xiàn)。,程序調(diào)試,64,Visual C++2010環(huán)境平臺中，對程序中那些不符合語法的標識符和語句等會以紅色波浪線給出“警示”。換句話說，只要編輯的程序中存在紅色波浪線，就表明紅色波浪線處或相關(guān)部分一定存在問題。C/C++語言對關(guān)鍵字以及語句的標點符號，都嚴格為英文小寫。,程序調(diào)試,65,程序設(shè)計要素包括：①

38、對數(shù)據(jù)的描述，適合的數(shù)據(jù)的類型和數(shù)據(jù)的組織形式（即數(shù)據(jù)結(jié)構(gòu)）；② 對操作的描述，高效的求解問題的方法與步驟（也就是算法）。,本章小結(jié),66,C/C++語言程序是由一個或多個函數(shù)組成的文件，在組成程序的函數(shù)中，必須有且只有一個主函數(shù)main。main()函數(shù)在程序中位置并無限定，可以是任意的，它代表了程序執(zhí)行的起始點和終止點，即不管程序里有多少個函數(shù)，程序總是從主函數(shù)main的第一條語句開始執(zhí)行，并結(jié)束于該函數(shù)的最后一條語句。,本章小結(jié)

39、,67,當源程序中要使用一個或多個庫文件時，需應(yīng)用“文件包含”預(yù)編譯命令。該命令的作用是告訴編譯系統(tǒng)在編譯本程序時把C/C++系統(tǒng)提供的庫文件的內(nèi)容插入到該行的位置。,本章小結(jié),68,一個完整的C/C++程序的基本框架為：[注釋程序目標]#include [頭文件]using namespace std;int main(void ){ [聲明常量] [定義變量] [輸入語句] [計算語句] [輸出