c語言 (概述,算法)

c語言(概述,算法)第一堂課C語言程序設計第一章C語言程序設計

本章要點

C語言的特點

C語言的發(fā)展歷史

C程序的結構在計算機上運行C程序的方法

C語言程序設計1.1Ｃ語言的發(fā)展歷史C語言是國際上廣泛流行的高級語言。1963年,劍橋,CPL語言,更近硬件,但規(guī)模大,難以實現.1967年,劍橋,MartinRichards,簡化,BCPL語言.1970年,美國貝爾實驗室,KenThompson,簡化,B語言,寫第一個UNIX系統(tǒng).1972～1973年,貝爾實驗室,D.M.Ritchie,B語言基礎上,設計出C語言,克服B語言的過于簡單、功能有限的不足.1973年，K.Thompson和合作將UNIX的90%以上用C改寫.1978年以后,C語言已先后移植到大、中、小、微型機上已獨立于UNIX和PDP，得以廣泛應用。5DennisM．Ritchie：1967年加入貝爾實驗室。他和KenL．Thompson兩人共同設計并實現了C語言,改變了程序設計語言發(fā)展的軌跡，是程序設計語言發(fā)展過程中的一個重要里程碑。與此同時，他們兩人還設計并實現了UNIX操作系統(tǒng)。正是由于這兩項巨大貢獻，DennisM．Ritchie于1983年獲得了計算機界的最高獎——圖靈獎。此外，他還獲得了ACM、IEEE、貝爾實驗室等授予的多種獎項。6BrianW．Kernighan：是貝爾實驗室計算科學研究中心高級研究人員，著名的計算機科學家。他參加了UNIX系統(tǒng)、C語言、AWK語言和許多其他系統(tǒng)的開發(fā)，同時出版了許多在計算機領域具有影響的著作。7C語言的產生和地位原書名：TheCProgrammingLanguage（美）BrianW.Kernighan,DennisM.Ritchie

本書原著即為C語言的設計者之一DennisM．Ritchie和著名的計算機科學家BrianW．Kernighan合著的一本介紹C語言的權威經典著作。C語言已經成為全球程序員的公共語言，并由此誕生了兩個新的主流語言C++與Java，它們都建立在C語言的語法和基本結構的基礎上。現在世界上的許多軟件都是在C語及其衍生的各種語言的基礎上開發(fā)出來的。

81.2Ｃ語言的特點為什么學習C語言？可進行內存物理地址訪問，具有匯編語言的特點

控制流程結構化，以函數為基本結構進行流程控制

語言簡潔靈活，有32個關鍵字和9種控制語句具有構造數據類型的能力，數據結構系統(tǒng)化

語言表達能力強：34種運算符程序運行效率高，易讀性、可移植性好語法檢查不夠嚴格，對數組下標越界不做檢查91.3C語言程序的組成結構例1:/*顯示“Howareyou!”*/#include<stdio.h>main(){printf("Howareyou!");}程序運行結果是輸出:Howareyou!10例2求兩數之和

#include<stdio.h>

main()/*求兩數之和*/

{

inta,b,sum;/*定義變量為整型*/

a=123;/*變量賦值*/

b=456;

sum=a+b;/*求和*/

printf(″sumis%d＼n″,sum);

}說明：/*……*/表示注釋。注釋只是給人看的,對編譯和運行不起作用。所以可以用漢字或英文字符表示，可以出現在一行中的最右側，也可以單獨成為一行。輸出一行信息：sumis57911例3:從鍵盤輸入兩個整數，并顯示這兩個整數之和。intADDxy(inta,intb){intc;c=a+b;return(c);}main(){intx,y,z;scanf(“%d%d”,&x,&y);z=ADDxy(x,y);printf(“sum=%d\n”,z);}主函數子函數程序運行情況如下：85↙sum=1312C程序的基本結構小結：(1)C程序是由函數構成的,程序容易實現模塊化。main()/*主函數說明*/{變量定義/*主函數體*/執(zhí)行語句組}子函數名1(參數)/*子函數說明*/{變量定義/*子函數體*/執(zhí)行語句組}子函數名2(參數)/*子函數說明*/{變量定義/*子函數體*/執(zhí)行語句組}13(2)一個函數由兩部分組成:

函數的首部：例3中的Addxy函數首部

intAddxy(intx,inty)

函數體：花括號內的部分。若一個函數有多個花括號,則最外層的一對花括號為函數體的范圍。(3)C程序總是從main函數開始執(zhí)行的,與main函數的位置無關。(4)C程序書寫格式自由,一行內可以寫幾個語句,一個語句可以分寫在多行上，C程序沒有行號。14(5)每個語句和數據聲明的最后必須有一個分號。(6)C語言本身沒有輸入輸出語句。輸入和輸出的操作是由庫函數scanf和printf等函數來完成的(7)在C語言中，大小寫字母是有區(qū)別的。（C語言習慣用小寫字母）(8)書寫程序時，最好使用規(guī)范的縮進格式的形式。(9)C程序注釋/*……*/可以寫在程序的任何位置上151.4運行Ｃ程序的步驟和方法1.運行Ｃ程序的步驟上機輸入、編輯源程序對源程序進行編譯與庫函數連接運行目標程序162.Ｃ程序的開發(fā)環(huán)境目前使用的大多數C編譯系統(tǒng)都是集成環(huán)境的?？梢杂貌煌木幾g系統(tǒng)對C程序進行操作常用的有TurboC2.0、TurboC++3.0、VisualC++等

TurboC++3.0：是一個集成環(huán)境，它具有方便、直觀和易用的界面，雖然它也是DOS環(huán)境下的集成環(huán)境，但是可以把執(zhí)行文件tc.exe生成快捷方式放在Windows桌面上，可以支持鼠標操作。

VisualC++6.0：可視化面向對象開發(fā)環(huán)境，可以用VisualC++對C程序進行編譯。171.5從三個方面學習Ｃ語言1.學習C語言的語法數據表達：變量定義、正確書寫表達式流程控制：

if(a>b)x=a;elsex=b;sum=0;i=1;while(i<=5){sum=sum+i;i=i+1;}for(i=1;sum=0;i<=5;i++)sum=sum+i;設計函數輸入和輸出182.學習解決問題的方法(算法)

如何求級數12+22+32+……前100項之和？矩陣轉置如何打印乘法表？數據如何按從小到大的順序排序？193.學習在C語言編程環(huán)境下，編輯、編譯、調試和運行程序開發(fā)環(huán)境：VisualC++6.0

上機作業(yè)1：使用VisualC++6.0編寫簡單的C程序

20第二章C語言程序設計

本章要點什么是程序設計什么是算法，如何設計和表示算法結構化程序設計的思想和方法計算機語言：是規(guī)則和符號的集合，是與計算機交流的工具。必須具有數據表達和數據處理（流程控制）的能力。程序：求解問題的指令序列軟件：程序的集合學習語言設計程序制作軟件概念：學軟件：學思想、學功能、學操作。熟練工種學語言：學規(guī)則、學方法、學設計、學應用。規(guī)范學習，靈活應用23計算機語言分類面向過程語言面向對象語言FORTRANBASICCPASCALCOBOLLISPC++C#VisualBASICJAVA系統(tǒng)軟件設計具有圖形功能科學計算商用人工智能242.1程序設計的基本概念數據元素：數據的最小單位數據結構：數據元素的組織形式程序設計＝數據結構＋算法＋方法＋工具數據結構的優(yōu)劣決定了軟件或程序的復雜程度和面貌一個程序應包括兩個方面的內容:對數據的描述：數據結構對操作的描述：算法完整的程序設計應該包括四部分:25程序設計的步驟分析問題，建立數學模型確定數據結構確定算法，描述算法編制程序，調試程序運行結果一個正確的程序通常包含兩方面的含義：一是書寫正確，二是結果正確。書寫正確是指程序語法正確，符合程序語言的規(guī)則；結果正確是指對應于正確的輸入，程序能夠得到所期望的輸出。26程序的三種基本結構1.順序結構

程序按照語句的書寫次序順序執(zhí)行。BA

先執(zhí)行A操作，再執(zhí)行B操作，兩者是順序執(zhí)行關系。272.選擇結構通過判斷特定條件，選擇一個分支執(zhí)行。當P條件成立時，執(zhí)行A操作，否則執(zhí)行B操作APB成立不成立

語句不成立P成立當P條件成立時，執(zhí)行語句操作，否則跳過語句操作283.循環(huán)結構

在給定條件下，反復執(zhí)行循環(huán)體，直到條件不滿足為止.(1)形式a（當型循環(huán)結構）不成立PA成立當P條件成立時，反復執(zhí)行A,直到P為零為止。29(2)形式b（直到型循環(huán)結構）先執(zhí)行A操作，再判斷P是否成立，若P成立，再執(zhí)行A，直到P不成立為止。AP成立不成立

30算法：完成一項任務的具體步驟計算機語言的別名：算法語言1.算法的概念2.2算法概述“一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列?！比魏谓鉀Q問題的過程都是由一定的步驟組成的，把解決問題確定的方法和有限的步驟稱作為算法。31例1：計算函數M(x)的值。函數M(x)為：算法分析：這是一個數值運算問題。其中M代表要計算的函數值，有兩個不同的表達式，根據x的取值決定采用哪一個算式。根據計算機具有邏輯判斷的基本功能，用計算機解題的算法如下：32①將a、b、c和x的值輸入到計算機；②判斷x≤a?如果條件成立，執(zhí)行第③步，否則執(zhí)行第④步；③按表達式bx+a2計算出結果存放到M中，然后執(zhí)行第⑤步；④按表達式a(c-x)+c2計算出結果存放到M中，然后執(zhí)行第⑤步；⑤輸出M的值；⑥算法結束。這是用自然語言描述的算法33例2：有黑和藍兩個墨水瓶，但卻錯把黑墨水裝在了藍墨水瓶子里，而藍墨水錯裝在了黑墨水瓶子里，要求將其互換。算法分析：這是一個非數值運算問題。因為兩個瓶子的墨水不能直接交換，所以，解決這一問題的關鍵是需要引入第三個墨水瓶。設第三個墨水瓶為白色，其交換步驟如下：34①將藍瓶中的黑墨水裝入白瓶中②將黑瓶中的藍墨水裝入藍瓶中③將白瓶中的黑墨水裝入黑瓶中④交換結束352.算法的基本特征算法是一個有窮規(guī)則的集合，這些規(guī)則確定了解決某類問題的一個運算序列。算法的基本特征：有窮性：算法必須在執(zhí)行有限個操作后終止；

確定性：算法中每一步的含義必須是確切的，不能出現任何二義性；有效性：算法中的每一步操作都應該能有效執(zhí)行，一個不可執(zhí)行的操作是無效的；有零個或多個輸入：執(zhí)行算法時，從外界獲得必要的信息；有一個或多個輸出：算法的解就是輸出。363.算法的常用表示方法可以用不同的方法表示算法，常用方法有：自然語言傳統(tǒng)流程圖結構化流程圖

37（1）自然語言自然語言即是使用漢語、英語或其他語言去描述算法。[例]有50名學生的成績，要求將他們之中80分以上的成績打印出來。設用g代表學生成績，gi代表第i個學生成績。1）使i=1；2）如果gi80，則打印gi，否則不打?。?）使i的值加1；4）如果i50,返回S2，繼續(xù)執(zhí)行；否則，算法結束。特點：描述算法通俗易懂，容易產生歧義。對復雜問題，語句繁瑣、冗長，并且很難清楚地表達算法的邏輯流程，往往需要根據上下文判別其含義，尤其對描述含有選擇、循環(huán)結構的算法，不太方便和直觀，一般不常使用。38(2)傳統(tǒng)流程圖

美國國家標準化協(xié)會ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流向線連接點39程序流程圖表示開始1

igi>=80輸出gii+1

ii>50結束成立不成立不成立成立傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制。40傳統(tǒng)流程圖的流程可以是：缺點：使用者可以毫不受限制地使流程隨意地轉向，使流程圖變得毫無規(guī)律，難以閱讀、修改，使算法的可靠性和可維護性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無規(guī)律地使流程隨意轉向，只能順序的進行下去。41（3）N–S流程圖N-S流程圖由美國學者I.Nassi和B.Shneiderman提出表示算法的圖形工具?；締卧蔷匦慰?用不同的形狀線分割,表示三種結構。只有一個入口,一個出口,沒有流程線。N-S圖的優(yōu)點比文字描述直觀、形象、易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結構是由各個基本結構按順序組成的，N--S流程圖中的上下順序就是執(zhí)行時的順序。42三種基本程序結構的N–S流程圖條件TF語句1語句22.選擇結構語句1語句21.順序結構3.循環(huán)結構循環(huán)體循環(huán)體當滿足條件時直到條件成立循環(huán)結構一循環(huán)結構二430t,0ii+1i

t+it直到i100輸出t的值傳統(tǒng)流程圖與N-S流程圖的比較i100NY開始0t,0ii+1it+it輸出t的值結束例1：1+2+3+……+加到100為止44例：打印50名學生中成績高于80分的學號和成績用N-S圖表示。451.枚舉法（窮舉法）特點:算法簡單，容易理解，運算量大?；舅枷耄?/p>

根據題目的部分條件確定答案的大致范圍，然后在此范圍內對所有可能的情況逐一驗證，直到所有情況均通過驗證。若某個情況符合題目條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。

2.3幾種常用算法介紹46如：百元買百雞問題。假定小雞每只0.5元，公雞每只2元，母雞每只3元?，F在有100元錢要求買100只雞，問共有幾種購雞方案？根據題目設母雞、公雞、小雞各為x,y,z只，列出方程為：x+y+z=100，3x+2y+0.5z=100利用窮舉法，將各種可能的組合一一測試，輸出符合條件的組合。即在各個變量的取值范圍內不斷變化x,y,z的值，窮舉x,y,z全部可能的組合，若滿足方程組則是一組解。47#include"stdio.h"main(){intx,y,z;printf("母雞公雞小雞");for(x=0;x<=33;x++) for(y=0;y<=50;y++) {z=100-x-y; if((3*x+2*y+0.5*z)==100) printf(“\n%-6d%-6d%-6d”, x,y,z);}}百元買百雞程序：48

2.遞推法（迭代法）基本思想：

利用問題本身所具有的某種遞推關系求解問題。從初值出發(fā)，歸納出新值與舊值間直到最后值為止存在的關系，從而把一個復雜的計算過程轉換為簡單過程的多次重復，每次重復都從舊值的基礎上遞推出新值，并由新值代替舊