第一章

　C 語(yǔ)言概述 本章要求：

�。�1）C語(yǔ)句概述； （2）程序的三種基本結(jié)構(gòu)； （3）賦值語(yǔ)句； （4）數(shù)據(jù)的輸入與輸出。

　教學(xué)重點(diǎn)：

　1. C語(yǔ)言的特點(diǎn)。

　2. C語(yǔ)言的編程環(huán)境。

　教學(xué)難點(diǎn)：

　掌握編程環(huán)境的使用方法 教學(xué)方法：

　采用多媒體教學(xué)的方法進(jìn)行講授，學(xué)生在教師指導(dǎo)下通過(guò)計(jì)算機(jī)進(jìn)行操作練習(xí)。

　課時(shí)數(shù)：4 （講授 2 節(jié)課，上機(jī)練習(xí) 2 節(jié)課）

　1.1 C 語(yǔ)言的發(fā)展及特點(diǎn) 1.1.1

　C 語(yǔ)言的發(fā)展過(guò)程

　1、C 語(yǔ)言是國(guó)際上流行的、很有發(fā)展前途的計(jì)算機(jī)高級(jí)語(yǔ)言。C 語(yǔ)言適合于作為“系統(tǒng)描述語(yǔ)言”。它既可以用來(lái)編寫(xiě)系統(tǒng)軟件，也可以用來(lái)編寫(xiě)應(yīng)用程序。

　以前操作系統(tǒng)等系統(tǒng)軟件主要采用匯編語(yǔ)言編寫(xiě)。匯編語(yǔ)言依賴于計(jì)算機(jī)硬件，程序的可讀性、可移植性都比較差。為了提高可讀性和可移植性，人們希望采用高級(jí)語(yǔ)言編寫(xiě)這些軟件，但是一般的高級(jí)語(yǔ)言難以實(shí)現(xiàn)匯編語(yǔ)言的某些操作，特別是針對(duì)硬件的一些操作（如：內(nèi)存地址的讀寫(xiě)-直接硬件、二進(jìn)制位的操作）。人們?cè)O(shè)法尋找一種既具有一般高級(jí)語(yǔ)言特性，又具有低級(jí)語(yǔ)言特性的語(yǔ)言，C 語(yǔ)言就在這種情況下應(yīng)運(yùn)而生。

　2、C 語(yǔ)言的發(fā)展見(jiàn)下圖：

　注：最初 Unix 操作系統(tǒng)是采用匯編語(yǔ)言編寫(xiě)的，B 語(yǔ)言版本的 Unix 是第一個(gè)用高級(jí)語(yǔ)言編寫(xiě)的 Unix。在 C 語(yǔ)言誕生后，Unix 很快用 C 語(yǔ)言改寫(xiě)，C 語(yǔ)言良好的可移植性很快使Unix 從 PDP 計(jì)算機(jī)移植到其它計(jì)算機(jī)平臺(tái)，隨著 Unix 的廣泛應(yīng)用，C 語(yǔ)言也得到推廣。從此C 語(yǔ)言和 Unix 像一對(duì)孿生兄弟，在發(fā)展中相輔相成，Unix 和 C 很快風(fēng)靡全球。

　ALGOL60 -> CPL -> BCPC -> B -> C -> 標(biāo)準(zhǔn) C -> ANSI C -> ISO C ? ALGOL60：一種面向問(wèn)題的高級(jí)語(yǔ)言。ALGOL60 離硬件較遠(yuǎn)，不適合編寫(xiě)系統(tǒng)程序。

　? CPL（Combined Programming language，組合編程語(yǔ)言)：CPL 是一種在ALGOL60 基礎(chǔ)上更接近硬件的一種語(yǔ)言。CPL 規(guī)模大，實(shí)現(xiàn)困難。

　? BCPL（Basic Combined Programming language，基本的組合編程語(yǔ)言）：BCPL是對(duì) CPL 進(jìn)行簡(jiǎn)化后的一種語(yǔ)言。

　? B 語(yǔ)言：是對(duì) BCPL 進(jìn)一步簡(jiǎn)化所得到的一種很簡(jiǎn)單接近硬件的語(yǔ)言。B 語(yǔ)言取BCPL 語(yǔ)言的第一個(gè)字母。B 語(yǔ)言精練、接近硬件，但過(guò)于簡(jiǎn)單，數(shù)據(jù)無(wú)類(lèi)型。B

　3、從 C 語(yǔ)言的發(fā)展歷史可以看出，C 語(yǔ)言是一種既具有一般高級(jí)語(yǔ)言特性(ALGOL60 帶來(lái)的高級(jí)語(yǔ)言特性)，又具有低級(jí)語(yǔ)言特性(BCPL 帶來(lái)的接近硬件的低級(jí)語(yǔ)言特性)的程序設(shè)計(jì)語(yǔ)言。C 語(yǔ)言從一開(kāi)始就是用于編寫(xiě)大型、復(fù)雜系統(tǒng)軟件的，當(dāng)然 C 語(yǔ)言也可以用來(lái)編寫(xiě)一般的應(yīng)用程序。也就是說(shuō)：C 語(yǔ)言是程序員的語(yǔ)言！

　IBM PC 微機(jī) DOS、Windows 平臺(tái)上常見(jiàn)的 C 語(yǔ)言版本有：

　? Borland 公司：

　Turbo C,Turbo C++,Borland C++ C++ Builder(Windows 版本) ? Microsoft 公司：

　Microsoft C Visual C++(Windows 版本) 1.1.2

　C 語(yǔ)言的特點(diǎn)

　C 語(yǔ)言是從“組合編程語(yǔ)言”CPL 發(fā)展而來(lái)，C 語(yǔ)言既具有一般高級(jí)語(yǔ)言特性(ALGOL60帶來(lái)的高級(jí)語(yǔ)言特性)，又具有低級(jí)語(yǔ)言特性(BCPL 帶來(lái)的接近硬件的低級(jí)語(yǔ)言特性)。C 語(yǔ)言具有下面特點(diǎn)（其中 1-6 屬于高級(jí)語(yǔ)言特性，7，8 屬于低級(jí)語(yǔ)言特性）

　1、 C 語(yǔ)言的語(yǔ)言成分簡(jiǎn)潔，緊湊，書(shū)寫(xiě)形式自由 例：將 C 語(yǔ)言程序段與實(shí)現(xiàn)同樣功能的 PASCAL 語(yǔ)言程序段進(jìn)行比較。

　C 語(yǔ)言 PASCAL 語(yǔ)言 含義 說(shuō)明 1 {…} BEGIN…END 復(fù)合語(yǔ)句 (或:語(yǔ)句塊) PASCAL 顯得羅嗦 2 if(e)S; IF(e)THEN S; 條件語(yǔ)句 PASCAL 至少多了一個(gè) THEN關(guān)鍵詞 3 int i; VAR i:INTEGER 定義 i 為整型變量 PASCAL 至少多了一個(gè) VAR 關(guān)鍵詞 4 int a[10]; VAR a:ARRAY[1..10] OF INTEGER 定義 a 為整型一維數(shù)組,10 個(gè)元素 PASCAL 多了 VAR、ARRAY、OF 等關(guān)鍵詞 5 int f(); FUNCTION f():INTEGER 定義 f 為返回值為整型的函數(shù) PASCAL 至 少 多 了 一 個(gè)FUNCTION 關(guān)鍵詞 6 int *p; VAR p:^INTEGER 定義 p 為指向整型變量的指針變量 PASCAL 至少多了一個(gè) VAR 關(guān)鍵詞

　7 i+=2; i:=i+2 賦值語(yǔ)句 C 中如果將一個(gè)變量與另外一個(gè)操作數(shù)運(yùn)算后賦值給原來(lái)的變量，使用復(fù)合的運(yùn)算符可以不要重復(fù)書(shū)寫(xiě)此變量。C 形式上更加簡(jiǎn)潔。

　8 I++ I=I+1 I 自增 1 C 定義了常用的自增 1、自減 1 運(yùn)算符。形式上顯得相當(dāng)簡(jiǎn)潔 2、 C 語(yǔ)言擁有豐富的數(shù)據(jù)類(lèi)型 C 語(yǔ)言具有整型、實(shí)型、字符型、數(shù)組類(lèi)型、指針類(lèi)型、結(jié)構(gòu)體類(lèi)型、共同體類(lèi)型等數(shù)據(jù)類(lèi)型。能方便地構(gòu)造更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)(如：使用指針構(gòu)造鏈表、樹(shù)、棧)。

　3、 C 語(yǔ)言的運(yùn)算符豐富、功能更強(qiáng)大 例如：

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

　x+=5 等價(jià)于 x=x+5 (2) C 語(yǔ)言有條件運(yùn)算符“:”可代替簡(jiǎn)單的 if/else 語(yǔ)句。

　如果需要表示：“如果 x 小于或等于 0，y 為 0；否則 y 為 1”可以采用：

　y=x<=00:1; 如果用一般的程序設(shè)計(jì)語(yǔ)言表示就應(yīng)該像下面這樣表示：

　if(x<=0)y=0;

　else y=1; C 語(yǔ)言避免了一切可能的羅嗦， (3) C 語(yǔ)言中連賦值這種操作都定義為運(yùn)算符，也就是說(shuō)賦值操作本身可以作為表達(dá)式的一部分，參與運(yùn)算。如：

　if((p=malloc(sizeof(int)))==NULL){printf(“Error!”);exit(1);} 如果改寫(xiě)為一般形式：

　p=malloc(sizeof(int));

　if(p==NULL){printf(“Error!”);exit(1);} 又如下面算式是正確的：

　x=y=z=6;

　 如果改寫(xiě)為一般形式：

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

　5、 C 語(yǔ)言對(duì)語(yǔ)法限制不嚴(yán)格，程序設(shè)計(jì)靈活 C 語(yǔ)言不檢查數(shù)組下標(biāo)越界，C 語(yǔ)言不限制對(duì)各種數(shù)據(jù)轉(zhuǎn)化(編譯系統(tǒng)可能對(duì)不合適的轉(zhuǎn)化進(jìn)行警告，但不限制)，不限制指針的使用，程序正確性由程序員保證。

　實(shí)踐中，C 語(yǔ)言程序編譯時(shí)會(huì)提示：“警告錯(cuò)”“嚴(yán)重錯(cuò)誤”。警告錯(cuò)誤表示你使用的語(yǔ)法可能有問(wèn)題，但是你有時(shí)可以忽略，你的程序仍然可以完成編譯工作，然后運(yùn)行。(但是一般情況下警告錯(cuò)，往往意味著程序真的有問(wèn)題，你應(yīng)該認(rèn)真地檢查)“嚴(yán)重錯(cuò)”是不能忽略的，編譯系統(tǒng)發(fā)現(xiàn)嚴(yán)重錯(cuò)誤，就不會(huì)產(chǎn)生目標(biāo)代碼。

　靈活和安全是一對(duì)矛盾，對(duì)語(yǔ)法限制的不嚴(yán)格可能也是 C 語(yǔ)言的一個(gè)缺點(diǎn)，比如：黑客可能使用越界的數(shù)組攻擊你的計(jì)算機(jī)系統(tǒng)。JAVA 語(yǔ)言是優(yōu)秀的網(wǎng)絡(luò)應(yīng)用程序開(kāi)發(fā)語(yǔ)言，它必須保證安全性，它絕對(duì)不允許數(shù)組越界。此外 JAVA 不使用指針，不能直接操作客戶計(jì)算機(jī)上的文件，語(yǔ)法檢查相當(dāng)嚴(yán)格，程序正確性容易保證，但是 JAVA 在編程時(shí)卻缺乏靈活。

　6、 C 語(yǔ)言編寫(xiě)的程序具有良好的可移植性 編制的程序基本上不需要修改或只需要少量修改就可以移植到其它的計(jì)算機(jī)系統(tǒng)或其它的操作系統(tǒng)。

　7、 C 語(yǔ)言可以實(shí)現(xiàn)匯編語(yǔ)言的大部分功能 ? C 語(yǔ)言可以直接操作計(jì)算機(jī)硬件如寄存器，各種外設(shè) I/O 端口等。

　? C 語(yǔ)言的指針可以直接訪問(wèn)內(nèi)存物理地址。

　? C 語(yǔ)言類(lèi)似匯編語(yǔ)言的位操作可以方便地檢查系統(tǒng)硬件的狀態(tài)。

　C 語(yǔ)言適合編寫(xiě)系統(tǒng)軟件。

　8、 C 語(yǔ)言編譯后生成的目標(biāo)代碼小，質(zhì)量高，程序的執(zhí)行效率高 有資料顯示只比匯編代碼效率低 10%-20%。

　1.2 C 語(yǔ)言程序的基本結(jié)構(gòu) 1.2.1

　 簡(jiǎn)單的 C 程序介紹

　例 1.1：

　main() {

　 printf(“This is a C program.\n”); } 說(shuō)明：本程序的功能是輸出一行信息：This is a C program. 其中：

　1、main 表示“主函數(shù)”。每個(gè) C 語(yǔ)言程序都必須有一個(gè) main 函數(shù)，它是每一個(gè) C 語(yǔ)言程序的執(zhí)行起始點(diǎn)（入口點(diǎn)）。main()表示“主函數(shù)”main 的函數(shù)頭。

　2、用{}括起來(lái)的是“主函數(shù)”main 的函數(shù)體。main 函數(shù)中的所有操作（或：語(yǔ)句）都在這一對(duì){}之間。也就是說(shuō) main 函數(shù)的所有操作都在 main 函數(shù)體中。

　3、“主函數(shù)”main 中只有一條語(yǔ)句，它是 C 語(yǔ)言的庫(kù)函數(shù)，功能是用于程序的輸出（顯示在屏幕上），本例用于將一個(gè)字符串“This is a C program.\n”的內(nèi)容輸出。即在屏幕上顯示：

　This is a C program. _

　(回車(chē)/換行) 4、注意：每條語(yǔ)句用“；”號(hào)結(jié)束語(yǔ)句。

　例 1.2: main()

　/* 計(jì)算兩數(shù)之和 */ {

　 int a,b,sum;

　/* 這是定義變量 */

　 a=123;b=456;

　/* 以下 3 行為 C 語(yǔ)句 */

　 sum=a+b;

　 printf(“sum=%d\n”,sum); } 說(shuō)明：本程序計(jì)算兩數(shù)之和，并輸出結(jié)果。

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

　2、/* */括起來(lái)的部分是一段注釋，注釋只是為了改善程序的可讀性，在編譯、運(yùn)行時(shí)不起作用（事實(shí)上編譯時(shí)會(huì)跳過(guò)注釋，目標(biāo)代碼中不會(huì)包含注釋）。注釋可以放在程序任何位置，并允許占用多行，只是需要注意“/*”、“*/”匹配，一般不要嵌套注釋。

　3、int a,b,sum;是變量聲明。聲明了三個(gè)具有整數(shù)類(lèi)型的變量 a,b,sum。C 語(yǔ)言的變量必須先聲明再使用。

　4、a=123;b=456;是兩條賦值語(yǔ)句。將整數(shù) 123 賦給整型變量 a，將整數(shù) 456 賦給整型變量 b。a,b 兩個(gè)變量分別為 123，456。注意這是兩條賦值語(yǔ)句，每條語(yǔ)句均用“；”結(jié)束。

　也可以將兩條語(yǔ)句寫(xiě)成兩行，即：

　a=123; b=456; 由此可見(jiàn) C 語(yǔ)言程序的書(shū)寫(xiě)可以相當(dāng)隨意，但是為了保證容易閱讀要遵循一定的規(guī)范。

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

　6、printf(“sum=%d\n”,sum);是調(diào)用庫(kù)函數(shù)輸出 sum 的結(jié)果。%d 為格式控制表示 sum 的值以十進(jìn)制整數(shù)形式輸出。程序運(yùn)行后，輸出（顯示）：

　sum=579 _

　(回車(chē)/換行) 例 1.3

　說(shuō)明：輸入兩個(gè)整數(shù)，計(jì)算兩者較大的數(shù)，并輸出。

　1、本程序包括兩個(gè)函數(shù)。其中主函數(shù) main 仍然是整個(gè)程序執(zhí)行的起點(diǎn)。函數(shù) max 計(jì)算兩數(shù)中較大的數(shù)。

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

　3、int max(int x,int y)是函數(shù) max 的函數(shù)頭，函數(shù) max 的函數(shù)頭表明此函數(shù)獲得兩個(gè)整數(shù)，返回一個(gè)整數(shù)。

　main()/* 主函數(shù) */ {/* main 函數(shù)體開(kāi)始 */

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

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

　 /* 調(diào)用 max，將調(diào)用結(jié)果賦給 c */

　 c=max(a,b);

　printf(“max=%d”,c); }/* main 函數(shù)體結(jié)束 */

　int max(int x,int y)/* 計(jì)算兩數(shù)中較大的數(shù) */ {/* max 函數(shù)體開(kāi)始 */

　 int z;

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

　 if(x>y)z=x;

　 else z=y;

　 return z;

　/* 將 z 值返回,通過(guò) max 帶回調(diào)用處 */ }/* max 函數(shù)體結(jié)束 */

　4、函數(shù) max 同樣也用{}將函數(shù)體括起來(lái)。max 的函數(shù)體是函數(shù) max 的具體實(shí)現(xiàn)。從參數(shù)表獲得數(shù)據(jù)，處理后得到結(jié)果 z，然后將 z 返回調(diào)用函數(shù) main。

　5、本例還表明函數(shù)除了調(diào)用庫(kù)函數(shù)外，還可以調(diào)用用戶自己定義，編制的函數(shù)。

　1.2.2

　 C 程序結(jié)構(gòu)

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

　1、C 程序由函數(shù)構(gòu)成（C 是函數(shù)式的語(yǔ)言，函數(shù)是 C 程序的基本單位）（以例 1.3 說(shuō)明）

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

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

　? C 函數(shù)庫(kù)非常豐富，ANSI C 提供 100 多個(gè)庫(kù)函數(shù)，Turbo C 提供 300 多個(gè)庫(kù)函數(shù)。

　2、main 函數(shù)（主函數(shù)）是每個(gè)程序執(zhí)行的起始點(diǎn)（以例 1.3 說(shuō)明）

　一個(gè) C 程序總是從 main 函數(shù)開(kāi)始執(zhí)行，而不論 main 函數(shù)在程序中的位置�？梢詫� main函數(shù)放在整個(gè)程序的最前面，也可以放在整個(gè)程序的最后，或者放在其它函數(shù)之間。

　3、一個(gè)函數(shù)由函數(shù)首部和函數(shù)體兩部分組成(以例 1.3 的 max 函數(shù)說(shuō)明) (1)函數(shù)首部：一個(gè)函數(shù)的第一行。

　返回值類(lèi)型 函數(shù)名([函數(shù)參數(shù)類(lèi)型 1 函數(shù)參數(shù)名 1][,…,函數(shù)參數(shù)類(lèi)型 2，函數(shù)參數(shù)名 2]）

　注意：函數(shù)可以沒(méi)有參數(shù)，但是后面的一對(duì)（）不能省略，這是格式的規(guī)定。

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

　{

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

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

　} 4、C 程序書(shū)寫(xiě)格式自由 ? 一行可以寫(xiě)幾個(gè)語(yǔ)句，一個(gè)語(yǔ)句也可以寫(xiě)在多行上。

　? C 程序沒(méi)有行號(hào)，也沒(méi)有 FORTRAN，COBOL 那樣嚴(yán)格規(guī)定書(shū)寫(xiě)格式（語(yǔ)句必須從某一列開(kāi)始）。

　? 每條語(yǔ)句的最后必須有一個(gè)分號(hào)“；”表示語(yǔ)句的結(jié)束。

　5、可以使用/* */對(duì) C 程序中的任何部分作注釋 注釋可以提高程序可讀性，使用注釋是編程人員的良好習(xí)慣。

　實(shí)踐中， ? 編寫(xiě)好的程序往往需要修改、完善，事實(shí)上沒(méi)有一個(gè)應(yīng)用系統(tǒng)是不需要修改、完善的。很多人會(huì)發(fā)現(xiàn)自己編寫(xiě)的程序在經(jīng)歷了一些時(shí)間以后，由于缺乏必要的文檔、必要的注釋，最后連自己都很難再讀懂。需要花費(fèi)大量時(shí)間重新思考、理解原來(lái)的程序。這浪費(fèi)了大量的時(shí)間。如果一開(kāi)始編程就對(duì)程序進(jìn)行注釋，剛開(kāi)始麻煩一些，但日后可以節(jié)省大量的時(shí)間。

　? 一個(gè)實(shí)際的系統(tǒng)往往是多人合作開(kāi)發(fā)，程序文檔、注釋是其中重要的交流工具。

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

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

　不同的計(jì)算機(jī)系統(tǒng)除了提供函數(shù)庫(kù)中的標(biāo)準(zhǔn)函數(shù)外，還按照硬件的情況提供一些專門(mén)的函數(shù)。因此不同計(jì)算機(jī)系統(tǒng)提供的函數(shù)數(shù)量、功能會(huì)有一定差異。

　1.3

　算法及其描述 1、算法：為解決一個(gè)問(wèn)題而采取的方法和步驟稱為“算法”。

　對(duì)于同一個(gè)問(wèn)題可以有不同的解題方法和步驟，也就是有不同的算法。算法有優(yōu)劣，一般而言，應(yīng)當(dāng)選擇簡(jiǎn)單的、運(yùn)算步驟少的，既運(yùn)算快、內(nèi)存開(kāi)銷(xiāo)小的算法（算法的時(shí)空效率）。

　2、算法的 5 大特性 (1)有窮性：一個(gè)算法應(yīng)當(dāng)包含有限的步驟，而不能是無(wú)限的步驟；同時(shí)一個(gè)算法應(yīng)當(dāng)在執(zhí)行一定數(shù)量的步驟后，算法結(jié)束，不能死循環(huán)。

　事實(shí)上“有窮性”往往指“在合理的范圍之內(nèi)”的有限步驟。如果讓計(jì)算機(jī)執(zhí)行一個(gè)歷時(shí)1000 年才結(jié)束的算法，算法盡管有窮，但超過(guò)了合理的限度，人們也不認(rèn)為此算法是有用的。

　(2)確定性 算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不是含糊的、摸棱兩可的。也就是說(shuō)不應(yīng)當(dāng)產(chǎn)生歧義。特別是算法用自然語(yǔ)言描述時(shí)應(yīng)當(dāng)注意這點(diǎn)。

　例如：“將成績(jī)優(yōu)秀的同學(xué)名單打印輸出”就是有歧義的。“成績(jī)優(yōu)秀”是要求每門(mén)課程都90 分以上，還是平均成績(jī)?cè)?90 分以上？不明確，有歧義，不適合描述算法步驟。

　(3)有 0 個(gè)或多個(gè)輸入（即：可以沒(méi)有輸入，也可以有輸入）

　所謂輸入是指算法執(zhí)行時(shí)從外界獲取必要信息。（外界是相對(duì)算法本身的，輸入可以是人工鍵盤(pán)輸入的數(shù)據(jù)，也可以是程序其它部分傳遞給算法的數(shù)據(jù)）

　例如：

　例如：不需要輸入任何信息，就可以計(jì)算出 5��；（0 個(gè)輸入）

　例如：輸入一個(gè)正整數(shù) n，然后判斷 n 是否為素?cái)?shù)；（1 個(gè)輸入）

　例如：如果要計(jì)算兩個(gè)整數(shù)的最大公約數(shù)，則需要輸入 2 個(gè)整數(shù) m，n。（2 個(gè)輸入）

　(4)有 1 個(gè)或多個(gè)輸出（即算法必須得到結(jié)果）

　算法的輸出：算法得到的結(jié)果。算法必須有結(jié)果，沒(méi)有結(jié)果的算法沒(méi)有意義。（結(jié)果可以是顯示在屏幕上的，也可以是將結(jié)果數(shù)據(jù)傳遞給程序的其它部分）

　(5)有效性 算法的每個(gè)步驟都應(yīng)當(dāng)能有效執(zhí)行，并能得到確定的結(jié)果。例如：b=0，則執(zhí)行 a/b 是不能有效執(zhí)行的。

　3、算法的表示方法 為了表示一個(gè)算法，可以用不同的方法。常用的算法表示方法：自然語(yǔ)言，傳統(tǒng)流程圖，結(jié)構(gòu)化流程圖（N-S 流程圖），偽代碼、計(jì)算機(jī)語(yǔ)言等。（重點(diǎn)：傳統(tǒng)流程圖，N-S 流程圖）

　（1）

　用自然語(yǔ)言表示算法 算法可以用自然語(yǔ)言描述的。自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是漢語(yǔ)、英語(yǔ)或其它語(yǔ)言。用自然語(yǔ)言表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義。自然語(yǔ)言表示的含義往往不太嚴(yán)格，要根據(jù)上下文才能準(zhǔn)確判斷其含義。此外，用自然語(yǔ)言描述分支和循環(huán)的算法，不是很直觀。因此，除了簡(jiǎn)單問(wèn)題，一般不采用自然語(yǔ)言描述算法。

�。�2）

　用流程圖表示算法 流程圖表示算法：用一些圖框表示各種操作，用箭頭表示算法流程。用圖形表示算法直觀形象，易于理解。

　美國(guó)標(biāo)準(zhǔn)化協(xié)會(huì) ANSI 規(guī)定了一些常用的流程圖符號(hào)，已為世界各國(guó)程序工作者普遍采用。

　? 起止框：表示算法的開(kāi)始和結(jié)束。一般內(nèi)部只寫(xiě)“開(kāi)始”或“結(jié)束”。

　? 處理框：表示算法的某個(gè)處理步驟，一般內(nèi)部常常填寫(xiě)賦值操作。

　? 輸入輸出框：表示算法請(qǐng)求輸入輸入需要的數(shù)據(jù)或算法將某些結(jié)果輸出。一般內(nèi)部常常填寫(xiě)“輸入…”,“打印/顯示…” ? 菱形框（判斷框）：作用主要是對(duì)一個(gè)給定條件進(jìn)行判斷，根據(jù)給定的條件是否成立來(lái)決定如何執(zhí)行其后的操作。它有一個(gè)入口，兩個(gè)出口。

　? 連接點(diǎn)：用于將畫(huà)在不同地方的流程線連接起來(lái)。同一個(gè)編號(hào)的點(diǎn)是相互連接在一起的，實(shí)際上同一編號(hào)的點(diǎn)是同一個(gè)點(diǎn)，只是畫(huà)不下才分開(kāi)畫(huà)。使用連接點(diǎn)，還可以避免流程線的交叉或過(guò)長(zhǎng)，使流程圖更加清晰。

　? 注釋框：注釋框不是流程圖中必須的部分，不反映流程和操作，它只是對(duì)流程圖中某些框的操作做必要的補(bǔ)充說(shuō)明，以幫助閱讀流程圖的人更好地理解流程圖的作用。

　流程圖是表示算法的較好的工具。流程圖包括以下幾個(gè)部分：表示相應(yīng)操作的框，帶箭頭的流程線，框內(nèi)、框外必要的文字說(shuō)明。注意：流程線一定不要忘記箭頭，因?yàn)樗�反�?yīng)流程執(zhí)行的先后次序。

　傳統(tǒng)流程圖采用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制。因此，使用者可以不受限制地使流程轉(zhuǎn)來(lái)轉(zhuǎn)去，使流程圖變得毫無(wú)規(guī)律。人們對(duì)這種流程圖進(jìn)行改進(jìn)，規(guī)定幾種基本的結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成算法結(jié)構(gòu)，整個(gè)算法結(jié)構(gòu)是由上而下地將各個(gè)基本結(jié)構(gòu)順序排列起來(lái)。這樣可以在一定程度上，提高算法的質(zhì)量。

　三種基本結(jié)構(gòu)，有以下共同點(diǎn)：

　? 只有一個(gè)入口：不得從結(jié)構(gòu)外隨意轉(zhuǎn)入結(jié)構(gòu)中某點(diǎn)。

　? 只有一個(gè)出口：不得從結(jié)構(gòu)內(nèi)某個(gè)位置隨意轉(zhuǎn)出（跳出）。

　? 結(jié)構(gòu)中的每一部分都有機(jī)會(huì)被執(zhí)行到。（沒(méi)有“死語(yǔ)句”）

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

　已經(jīng)證明：由三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜問(wèn)題。由基本結(jié)構(gòu)組成的算法屬于“結(jié)構(gòu)化”算法。

　用流程圖表示的算法直觀形象，比較清楚地顯示出各個(gè)框之間的邏輯關(guān)系，因此得到廣泛使用。每一個(gè)程序編制人員都應(yīng)當(dāng)熟練掌握流程圖，會(huì)看會(huì)畫(huà)。（軟件專業(yè)水平、資格考試也用這種流程圖表示）。

　繪制流程圖可以使用 Visio 3,4…等流程圖設(shè)計(jì)工具。

　（3）

　用 N-S 流程圖表示算法（盒圖）

　既然基本結(jié)構(gòu)的順序組合可以表示任何復(fù)雜的算法結(jié)構(gòu)，那么，基本結(jié)構(gòu)之間的流程線就屬于多余的了。美國(guó)學(xué)者 I.Nassi，B.Shneiderman 提出了一種新的流程圖 N-S 流程圖。這種流程圖中，完全去掉了帶箭頭的流程線。每種結(jié)構(gòu)用一個(gè)矩形框表示。

　N-S 流程圖的流程圖符號(hào)：

　? 順序結(jié)構(gòu)：先執(zhí)行 A 操作，再執(zhí)行 B 操作。

　? 選擇結(jié)構(gòu)：當(dāng) p 條件成立，執(zhí)行 A 操作，當(dāng) p 條件不成立，執(zhí)行 B 操作。A，B 操作允許空操作，即什么都不做。注意選擇結(jié)構(gòu)是一個(gè)整體，代表一個(gè)基本結(jié)構(gòu)。

　? 循環(huán)結(jié)構(gòu)：a)當(dāng)型循環(huán)：當(dāng)條件 p 成立時(shí)，反復(fù)執(zhí)行 A 操作，直到 p 條件不成立為止。當(dāng)型循環(huán)先判斷，再?zèng)Q定是否執(zhí)行循環(huán)體，所以在條件 p 一次都不滿足時(shí)，循環(huán)體 A 可能一次都不執(zhí)行。b)直到型循環(huán)：當(dāng)條件 p 不成立時(shí)，反復(fù)執(zhí)行 A 操作，直到 p 條件成立為止。直到型循環(huán)先執(zhí)行循環(huán)體 A，然后再判斷條件 p，所以循環(huán)體至少執(zhí)行一次。

　一般情況循環(huán)算法既可以用當(dāng)型循環(huán)，也可以用直到型循環(huán)實(shí)現(xiàn)（可以實(shí)現(xiàn)等價(jià)算法）。循環(huán)結(jié)構(gòu)也是一個(gè)整體，同樣也代表一個(gè)基本結(jié)構(gòu)。

　注意：

　三種結(jié)構(gòu)中的 A、B 框可以是一個(gè)簡(jiǎn)單的操作，也可以是 3 個(gè)基本結(jié)構(gòu)之一。也就是說(shuō)基本結(jié)構(gòu)可以嵌套。

　N-S 流程圖表示算法的優(yōu)點(diǎn)：（未找到計(jì)算機(jī)繪盒圖的工具,smartdraw）

　? 比文字描述更加直觀、形象，易于理解； ? 比傳統(tǒng)的流程圖緊湊易畫(huà)； ? 廢除流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成。N-S 流程圖的上下順序就是執(zhí)行時(shí)的順序。N-S 圖表示的算法都是結(jié)構(gòu)化的算法。

　（4）

　用偽代碼表示算法（常常用于算法設(shè)計(jì)）

　用傳統(tǒng)流程圖、N-S 圖表示算法，直觀易懂，但繪制比較麻煩，在設(shè)計(jì)一個(gè)算法時(shí)，可能要反復(fù)修改，而修改流程圖是比較麻煩的，因此，流程圖適合表示算法，但在設(shè)計(jì)算法過(guò)程中使用不是很理想。為了設(shè)計(jì)算法方便，常使用偽代碼工具。

　偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。偽代碼不用圖形符號(hào)，書(shū)寫(xiě)方便，格式緊湊，便于向計(jì)算機(jī)語(yǔ)言算法過(guò)渡。

�。�5）

　用計(jì)算機(jī)語(yǔ)言表示算法 用計(jì)算機(jī)語(yǔ)言表示算法實(shí)際上就是實(shí)際的程序。用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵守所使用的語(yǔ)言的語(yǔ)法規(guī)則。

　結(jié)構(gòu)化算法或程序由三種基本結(jié)構(gòu)順序組成：

　1、順序結(jié)構(gòu) 2、選擇結(jié)構(gòu) 3、循環(huán)結(jié)構(gòu)

　在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)中�？梢杂酶倪M(jìn)流程圖，或 N-S 圖表示。

　例 1：計(jì)算 1x2x3x4x5。（即 5!）

　解：

　算法 1：直接寫(xiě)出算式 S1:

　result<=1x2x3x4x5 很簡(jiǎn)單，一步就完成了。但是考慮一下如果要計(jì)算 100!，是否寫(xiě)都寫(xiě)得累死了。

　算法 2：

　考慮到 1x2x3x4x5 可以改寫(xiě)為：(((1x2)x3)x4)x5)， S1：p1<=1x2 S2: p2<=p1x3 S3: p3<=p2x4 S4: p4<=p3x5

　結(jié)果在 p4 里。

　考慮計(jì)算 100!，同樣此算法也一樣麻煩，要寫(xiě) 99 步。本算法同樣不適合編程。

　但是可以從本算法看出一個(gè)規(guī)律。即：每一步都是兩個(gè)數(shù)相乘，乘數(shù)總是比上一步乘數(shù)增加 1 后參與本次乘法運(yùn)算，被乘數(shù)總是上一步乘法運(yùn)算的乘積�？梢钥紤]用一個(gè)變量 i 存放乘數(shù),一個(gè)變量 p 存放上一步的乘積。那么每一步都可以寫(xiě)成：pxi,然后讓 pxi 的乘積存入 p，即：每一步都是 p<=pxi。也就是說(shuō) p 既代表被乘數(shù)又代表乘積。這樣可以得到算法 3。

　算法 3：

　S0: p<=1,i<=2 S1: p<=pxi, i<=i+1 S2: p<=pxi, i<=i+1 S3: p<=pxi, i<=i+1 S4: p<=pxi, i<=i+1 從算法 3 表面上看與算法 2 差不多，如果要計(jì)算 100!，同樣要寫(xiě) 99 步。但是從算法 3 可以看出 S1-S4 步驟實(shí)際上是一樣的，也就是說(shuō) S1-S4 同樣的操作重復(fù)做了 4 次。計(jì)算機(jī)對(duì)同樣的操作可以用循環(huán)完成，循環(huán)是計(jì)算機(jī)工作的強(qiáng)項(xiàng)（計(jì)算機(jī)高速度運(yùn)算）。算法 4 就是在算法3 的基礎(chǔ)上采用循環(huán)功能的算法實(shí)現(xiàn)。

　算法 4：

　S0: p<=1,i<=2 S1: p<=pxi, i<=i+1

　S2: 如果 i 小于或等于 5，返回重新執(zhí)行步驟 S1 及 S2；否則，算法結(jié)束，此時(shí) p 中的值就是5!的值。

　顯然算法 4 簡(jiǎn)潔，通用性好。如果要計(jì)算 100!只要將 S2 中的循環(huán)判斷條件改為：“…i小于或等于 100…”，算法其余部分不需要做任何修改。

　如果要計(jì)算 1x3x5x7x9x11，只要將 S0：“i<=2”修改為“i<=3”，S1：“i<=i+1”修改為“i<=i+2”, 循環(huán)判斷條件改為：“…i 小于或等于 11…”即可。

　從本例可以看出，同樣的問(wèn)題，算法實(shí)現(xiàn)可以不同。同一問(wèn)題的不同的算法在算法通用性、算法的簡(jiǎn)潔程度上有較大的差異。計(jì)算機(jī)處理有規(guī)律的事情比較方便，盡量考慮將算法某個(gè)部分統(tǒng)一，以便采用循環(huán)處理。

　求 5！的算法（傳統(tǒng)流程圖表示）

　求 5！的算法（N-S 流程圖表示）

　p<=1 i<=2 p<=p*i i<=i+1

　直到 i>5 例 2：

　對(duì)于一個(gè)大于或者等于 3 的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。（素?cái)?shù)，是指除了 1 和該數(shù)本身之外，不能被其它任何整數(shù)整除的數(shù)）（疑問(wèn)？1，2 是否是素?cái)?shù)）

　解：

　分析：根據(jù)素?cái)?shù)定義，對(duì)于一個(gè)≥3 的正整數(shù) n，如果 n 只能被 1，n 整除，那么 n 是素?cái)?shù)；也就是素?cái)?shù)必須滿足兩個(gè)條件：

　1、是≥3 的正整數(shù) 2、只能被 1 和自身整除（被 1 和自身是肯定可以整除的），不能被其它 2-(n-1)的正整數(shù)整除(全部不能整除)。

　反過(guò)來(lái)理解：任何≥3 的正整數(shù) n，如果能夠被 2-(n-1)的任何一個(gè)正整數(shù)整除,那么它一定不是素?cái)?shù)。

　假設(shè)給定的正整數(shù) n，根據(jù)題意，判斷一個(gè)正整數(shù)是否素?cái)?shù)，可以用 n 作為被除數(shù)，分別將 2,3,4…n-1 各個(gè)正整數(shù)作為除數(shù)，如果有任何一個(gè)可以整除，那么 n 不是素?cái)?shù)，如果全部都不能整除，那么 n 是素?cái)?shù)。

　算法：

　S0: 輸入 n

　S1: i<=2 S2: n 被 i 除得到余數(shù) r S3: 如果余數(shù) r=0，表示 n 能被 i 整除，則打印 n“不是素?cái)?shù)”，算法結(jié)束；否則繼續(xù)執(zhí)行 S4 S4: i<=i+1 S5: 如果 i≤n-1，返回執(zhí)行 S2，否則打印 n“是素?cái)?shù)”，算法結(jié)束。

　實(shí)際上，n 不必被 2 到(n-1)的整數(shù)除，只需要被 2 到 n/2 之間的整數(shù)除即可，甚至只需被 2到 sqrt(n)之間的整數(shù)除即可。

　判斷素?cái)?shù)算法（N-S 流程圖表示）

　輸入 n i<=2,w<=0 r<=n%i

　 y

　 r=0

　n

　w<=1

　 i<=i+1 直到 i>n-1 或 w=1

　y

　 w=0

　n 不是素?cái)?shù)

　是素?cái)?shù) 判斷素?cái)?shù)算法（傳統(tǒng)流程圖表示）

　1.4

　C 語(yǔ)言程序的上機(jī)步驟 1、源程序、目標(biāo)程序、可執(zhí)行程序的概念（補(bǔ)充）

　? 程序：為了使計(jì)算機(jī)能按照人們的意志工作，就要根據(jù)問(wèn)題的要求，編寫(xiě)相應(yīng)的程序。程序是一組計(jì)算機(jī)可以識(shí)別和執(zhí)行的指令，每一條指令使計(jì)算機(jī)執(zhí)行特定的操作。

　? 源程序：程序可以用高級(jí)語(yǔ)言或匯編語(yǔ)言編寫(xiě)，用高級(jí)語(yǔ)言或匯編語(yǔ)言編寫(xiě)的程序稱為源程序。C 程序源程序的擴(kuò)展名為“.c” 事實(shí)上我們編寫(xiě)的程序，不管采用什么計(jì)算機(jī)語(yǔ)言，都是源程序，有幾個(gè)人還會(huì)用機(jī)器語(yǔ)言去編程！

　源程序不能直接在計(jì)算機(jī)上執(zhí)行，需要用“編譯程序”將源程序翻譯為二進(jìn)制形式的代碼。

　? 目標(biāo)程序：源程序經(jīng)過(guò)“編譯程序”翻譯所得到的二進(jìn)制代碼稱為目標(biāo)程序。目標(biāo)程序的擴(kuò)展名為“.obj”

　目標(biāo)代碼盡管已經(jīng)是機(jī)器指令，但是還不能運(yùn)行，因?yàn)槟繕?biāo)程序還沒(méi)有解決函數(shù)調(diào)用問(wèn)題，需要將各個(gè)目標(biāo)程序與庫(kù)函數(shù)連接，才能形成完整的可執(zhí)行的程序。

　? 可執(zhí)行程序：目標(biāo)程序與庫(kù)函數(shù)連接，形成的完整的可在操作系統(tǒng)下獨(dú)立執(zhí)行的程序稱為可執(zhí)行程序。可執(zhí)行程序的擴(kuò)展名為“.exe”(在 dos/windows 環(huán)境下) 2、C 語(yǔ)言程序的上機(jī)步驟 輸入與編輯源程序->編譯源程序，產(chǎn)生目標(biāo)代碼-> 連接各個(gè)目標(biāo)代碼、庫(kù)函數(shù)，產(chǎn)生可執(zhí)行程序->運(yùn)行程序。

　3、Turbo C 的使用(DOS 環(huán)境) Turbo C2.0 是 Borland 公司開(kāi)發(fā)的微機(jī)上一個(gè) C 語(yǔ)言集成開(kāi)發(fā)環(huán)境�？梢栽� Turbo C 中完成 C語(yǔ)言程序的編輯、編譯、連接、運(yùn)行、調(diào)試。

　具體操作上機(jī)時(shí)演示（重點(diǎn)：?jiǎn)��?dòng)，退出，重要的菜單項(xiàng)）

　重點(diǎn)菜單項(xiàng)：

　File->new,load,save,write to Compile->compile to obj,make exe file,build all Run->run,go to cursor,trace into,step over,user screen,program reset Debug->Evaluate 4．Visual C 的使用（Windows 環(huán)境）

　Visual C 是 windows 環(huán)境下的 C 應(yīng)用程序,C++應(yīng)用程序,Windows 應(yīng)用程序集成開(kāi)發(fā)環(huán)境。

　作業(yè)：

　書(shū)后習(xí)題 實(shí)驗(yàn)一：熟悉 C 語(yǔ)言程序開(kāi)發(fā)環(huán)境

相關(guān)熱詞搜索：講稿 語(yǔ)言