1、第1章 C語言與程序概述,C語言是現(xiàn)在世界上應(yīng)用最廣泛，最受歡迎的計(jì)算機(jī)語言之一。在本章的學(xué)習(xí)中需要掌握以下知識點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)的概念和作用； 算法的概念和作用； 結(jié)構(gòu)化程序設(shè)計(jì)的方法； 三種基本結(jié)構(gòu)； 程序流程圖和N-S流程圖。,1.1 C語言歷史,C語言已經(jīng)經(jīng)歷了幾十年的發(fā)展。在學(xué)習(xí)C語言之前，應(yīng)該要先了解C語言是如何誕生的，它的歷史是怎么樣的。本節(jié)將介紹C言語的誕生、C語言的標(biāo)準(zhǔn)化過程及其重要特點(diǎn)，最后還將展示一個標(biāo)準(zhǔn)的“Hello, world!”的程序。,1.1.1 C語言的誕生,C語言是由著名的計(jì)算機(jī)科學(xué)家Dennis Ritchie創(chuàng)造的，其歷史可以追溯到ALGOL 60。ALGO

2、L 60，也稱為A語言，是純粹的面向描述計(jì)算過程的語言。 C語言的直接前身B語言就是從BCPL發(fā)展而來的。 在19721973年間，Denis Ritchie改進(jìn)了B語言，為其添加了數(shù)據(jù)類型的概念，并將原來的解釋程序改寫為可以在直接生成機(jī)器代碼的編譯程序，并將其命名為C。 現(xiàn)在，C語言已成為用途最為廣泛的計(jì)算機(jī)高級語言，不僅可以用于編寫系統(tǒng)軟件，還可以用于構(gòu)建各個領(lǐng)域的應(yīng)用軟件。,1.1.2 C語言的標(biāo)準(zhǔn)化,C語言發(fā)展到現(xiàn)在已經(jīng)經(jīng)歷了3個標(biāo)準(zhǔn)，分別為K&R C、C89和C99。 1K&R C 2C89或ANSI C 3C99,1.1.3 C語言的特點(diǎn),C語言之所以得到如此迅速的發(fā)展，并成為應(yīng)用

3、最廣泛、最受歡迎的計(jì)算機(jī)語言之一，主要是因?yàn)樗Z法靈活、使用方便，并能實(shí)現(xiàn)高效而強(qiáng)大的功能。C語言具有以下特點(diǎn)： 1使用方便，功能強(qiáng)大 2便于結(jié)構(gòu)化編程 3C語言是中級語言 4執(zhí)行效率高 5C程序可移植性好,1.1.4 Hello, world!,作為結(jié)構(gòu)性語言，C程序的結(jié)構(gòu)十分嚴(yán)整。下面來認(rèn)識一下第一個C程序，這是十分著名的“Hello, world!”程序。這個程序經(jīng)常被用作介紹各種語言的第一個程序，其功能是向屏幕打印一個字符串“Hello, world!”。,1.2 數(shù)據(jù)結(jié)構(gòu)與算法,一般來說，程序由數(shù)據(jù)結(jié)構(gòu)和算法兩個部分組成。數(shù)據(jù)結(jié)構(gòu)是一個一個的實(shí)體，而算法是將它們聯(lián)系在一起的各種手段。

4、學(xué)習(xí)程序首先要了解數(shù)據(jù)結(jié)構(gòu)和算法的概念，以及它們之間的關(guān)系。由于篇幅有限，本小節(jié)將只是簡要地介紹數(shù)據(jù)結(jié)構(gòu)和算法的一些基本知識，要想深入了解數(shù)據(jù)結(jié)構(gòu)和算法，還需要讀者去學(xué)習(xí)其他專門的材料。,1.3 程序設(shè)計(jì),如本章1.1.3小結(jié)所述，C語言是一門便于結(jié)構(gòu)化編程的語言。結(jié)構(gòu)化編程，也就是結(jié)構(gòu)化程序設(shè)計(jì)。那么，什么是結(jié)構(gòu)化程序設(shè)計(jì)呢？結(jié)構(gòu)化程序設(shè)計(jì)有什么好處？通過本小節(jié)的學(xué)習(xí)，讀者可以得到這些問題的答案，同時會為學(xué)習(xí)以結(jié)構(gòu)化程序設(shè)計(jì)為指導(dǎo)思想的C語言程序設(shè)計(jì)打下一個良好的鋪墊。,1.3.1 結(jié)構(gòu)化程序設(shè)計(jì),結(jié)構(gòu)化程序設(shè)計(jì)是荷蘭科學(xué)家E.W.Dijikstra在1965年提出的，其主要思想是通過分解復(fù)

5、雜問題為若干簡單問題的方式降低程序的復(fù)雜性。它的主要觀點(diǎn)是采用自頂向下、逐步細(xì)化的程序設(shè)計(jì)方法，同時嚴(yán)格使用三種基本控制結(jié)構(gòu)構(gòu)造程序。 三種基本控制結(jié)構(gòu)是指順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。所有的程序結(jié)構(gòu)都可以分解為這三個基本控制結(jié)構(gòu)。,1.3.2 三種基本結(jié)構(gòu),按照操作的執(zhí)行順序，程序可以分為三類基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。1996年，計(jì)算機(jī)科學(xué)家Bohm和Jacopini證明：任何簡單或復(fù)雜的算法都可以由順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種結(jié)構(gòu)組合而成。所以，這三種結(jié)構(gòu)就被稱為程序設(shè)計(jì)的三種基本結(jié)構(gòu)，也是結(jié)構(gòu)化程序設(shè)計(jì)建議采用的結(jié)構(gòu)。,1順序結(jié)構(gòu),在順序結(jié)構(gòu)的程序里，各操作是按照它們

6、出現(xiàn)的先后順序執(zhí)行的。如下圖所示，操作1和操作2按自上而下地順序執(zhí)行。這是最簡單的一種基本結(jié)構(gòu)。這個結(jié)構(gòu)里只有一個入口點(diǎn)A和一個出口點(diǎn)B，其特點(diǎn)是從入口點(diǎn)A開始，按順序執(zhí)行所有操作，直至出口點(diǎn)B處。事實(shí)上，所有的程序的總流程總是一個順序結(jié)構(gòu)。,2選擇結(jié)構(gòu),選擇結(jié)構(gòu)，也叫分支結(jié)構(gòu)。選擇結(jié)構(gòu)的程序里存在一些分支，程序通過對一些條件的判斷選擇執(zhí)行的分支。按照分支數(shù)，選擇結(jié)構(gòu)又可以分為單選擇、雙選擇和多選擇三種形式。,雙選擇結(jié)構(gòu)是最常見的，如下圖所示，結(jié)構(gòu)中有兩個分支，必須要執(zhí)行其中一支；如果滿足條件則執(zhí)行操作1，否則執(zhí)行操作2。,2選擇結(jié)構(gòu),2選擇結(jié)構(gòu),單選擇結(jié)構(gòu)如下圖所示，當(dāng)雙選擇結(jié)構(gòu)中某個分支為

7、空時，就稱為單選擇結(jié)構(gòu)。,多選擇結(jié)構(gòu)如下圖所示，有多個分支共存，程序根據(jù)Type值來選擇其中之一執(zhí)行。,2選擇結(jié)構(gòu),3循環(huán)結(jié)構(gòu),在循環(huán)結(jié)構(gòu)中，是反復(fù)地執(zhí)行一系列操作，直到某條件為假（或?yàn)檎妫r才終止循環(huán)。按照判斷條件出現(xiàn)的位置，可以分為while循環(huán)結(jié)構(gòu)和until循環(huán)結(jié)構(gòu)。,while循環(huán)結(jié)構(gòu)中，先判斷條件，如下圖所示。如果A不大于1，則直接退出循環(huán)體到達(dá)流程出口處；如果滿足A大于1，執(zhí)行操作1，并且在操作1結(jié)束后返回到循環(huán)入口，重新判斷條件；如果A還是大于1，再次執(zhí)行操作1，再返回結(jié)構(gòu)入口，如此反復(fù)。,3循環(huán)結(jié)構(gòu),until型循環(huán)結(jié)構(gòu)中，在結(jié)構(gòu)入口處先執(zhí)行循環(huán)體，然后再判斷條件，如下圖所示

8、。當(dāng)程序執(zhí)行完操作1后，判斷A是否大于1。如果是，則再執(zhí)行操作1；然后再次判斷A是否大于1；如果結(jié)果仍然為是，則再次執(zhí)行操作1,3循環(huán)結(jié)構(gòu),3循環(huán)結(jié)構(gòu),在這兩種結(jié)構(gòu)中，操作1都可能被反復(fù)執(zhí)行，直到A的值不大于1，才結(jié)束程序。同樣，循環(huán)型結(jié)構(gòu)也只有一個入口點(diǎn)A和一個出口點(diǎn)B。 合理地使用這三種基本結(jié)構(gòu)，可以組合成復(fù)雜的高級結(jié)構(gòu)；而所有的復(fù)雜結(jié)構(gòu)都可以分解為這三種基本結(jié)構(gòu)。,1.3.3 算法描述方法,當(dāng)算法過程比較復(fù)雜時，單靠自然語言來描述算法將顯得十分困難，讓人難以準(zhǔn)確理解。此時，需要借助其他的算法描述手段，主要有： 算法語言，有偽代碼、各種程序設(shè)計(jì)語言、計(jì)算機(jī)語言等。 圖形描述，如流程圖和N-

9、S圖，圖的描述應(yīng)與算法語言的描述對應(yīng)； 形式語言，用數(shù)學(xué)的方法，可以避免自然語言的二義性。,1偽代碼,偽代碼是介于程序語言和自然語言之間的算法描述，即要具有自然語言通俗易懂的特點(diǎn)，還要能很容易地被轉(zhuǎn)換為程序語言，這就要求偽代碼具有清晰地邏輯結(jié)構(gòu)，并且有準(zhǔn)確的算法步驟。偽代碼的形式有很多種，沒有通用的規(guī)則，根據(jù)需要可以自行決定偽碼的形式。 在本書使用的偽代碼一般為類C偽碼，書寫注重可讀性和邏輯性。下面是上一小節(jié)直接排序算法的偽代碼。該段偽代碼已經(jīng)細(xì)化到編程的每一小步，可以很容易使用C語言代替。,1偽代碼,算法開始： 設(shè)i值為0； 當(dāng)i stuArrayj 設(shè)min的值為j； j自增1； 交換第i

10、個元素和第min個元素； i自增1； 算法結(jié)束,1偽代碼,技巧：在編程時，當(dāng)設(shè)計(jì)好一個算法后，要都先將它們使用偽代碼描述出來，再使用程序語言來實(shí)現(xiàn)。這樣有利于更有條理更有邏輯地書寫程序語言，其作用就像寫文章要先列好提綱一樣。,2.程序流程圖,程序流程圖是算法的圖形描述方式。它使用一些簡單的幾何圖形來表示各種不同性質(zhì)的程序操作，使用流程線將各個圖形連接起來，指示算法的執(zhí)行過程。由于流程圖的符號統(tǒng)一，且畫法簡單，結(jié)構(gòu)清晰，邏輯性強(qiáng)，便于理解，因此成為描述程序流程的主要方法。下圖中的圖形是流程圖中常用的一些標(biāo)志。,2.程序流程圖,2.程序流程圖,在1.3.1小節(jié)介紹三種基本程序結(jié)構(gòu)時，已經(jīng)接觸了流程

11、圖的部分圖形。將1.2.2小節(jié)中的直接排序算法使用流程圖來表示，如下圖所示。,2.程序流程圖,2.程序流程圖,由于本書中的程序都較短小，而程序流程圖描述小型程序時，能夠發(fā)揮其簡單靈活的優(yōu)勢，因此本書主要使用程序流程圖來描述算法流程。,3N-S流程圖,由于程序流程圖使用流程線的導(dǎo)向來引導(dǎo)程序流程。當(dāng)程序流程較復(fù)雜時，框圖中會常常有很多的流程線，導(dǎo)致邏輯雜亂無章，失去了流程圖簡潔清晰的優(yōu)點(diǎn)。后來，當(dāng)結(jié)構(gòu)化程序設(shè)計(jì)方法日益流行后，兩個美國學(xué)者I.Nassi和B.Shneiderman基于結(jié)構(gòu)化思想提出了一種新的流程圖形式，被稱為N-S流程圖，N和S是兩個發(fā)明人名字的首字母。按照結(jié)構(gòu)化設(shè)計(jì)的思想，所有

12、的程序都可以分解成三種基本結(jié)構(gòu)的組合。N-S流程圖為三種基本結(jié)構(gòu)設(shè)計(jì)了特殊的結(jié)構(gòu)圖，并以它們?yōu)榛A(chǔ)來描述其余所有的算法。,下圖為順序結(jié)構(gòu)的N-S表示圖。先執(zhí)行操作1，再執(zhí)行操作2；操作1的方框上方為結(jié)構(gòu)入口，操作2的方框下方為結(jié)構(gòu)出口。,3N-S流程圖,3N-S流程圖,下圖為雙選擇結(jié)構(gòu)，省略其中之一即可得單選擇結(jié)構(gòu)。,3N-S流程圖,下圖中，左圖為while循環(huán)結(jié)構(gòu)，右圖為until循環(huán)結(jié)構(gòu)。,3N-S流程圖,N-S使用這幾種圖形的組合便可以得到所有算法的N-S流程圖。所以，在N-S流程圖中去掉了程序流程圖中眼花繚亂的流程線，并將整個程序流程放在一個大方框內(nèi)，使程序流程更清楚。下圖是直接排序算法的N-S流程圖。,3N-S流程圖,1.4 綜合練習(xí),1、使用偽碼描述使用冒泡排序法將序列從小到大排序的算法，并畫出其程序流程圖或N-S流程圖。 【提示】冒泡排序的基本思想是，對尚未排序的各元素從頭到尾依次比較相鄰的兩個元素是否逆序（與欲排順序相反），若逆序就交換這