2024年-c語言(概述算法)

第一堂課C語言概述算法概述C語言程序設(shè)計第1頁共53頁

第一章C語言程序設(shè)計C語言概述第2頁共53頁

本章要點C語言的特點

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

C程序的結(jié)構(gòu)在計算機上運行C程序的方法C語言程序設(shè)計第3頁共53頁

1.1Ｃ語言的發(fā)展歷史C語言是國際上廣泛流行的高級語言。1963年,劍橋,CPL語言,更近硬件,但規(guī)模大,難以實現(xiàn).1967年,劍橋,MartinRichards,簡化,BCPL語言.1970年,美國貝爾實驗室,KenThompson,簡化,B語言,寫第一個UNIX系統(tǒng).1972～1973年,貝爾實驗室,D.M.Ritchie,B語言基礎(chǔ)上,設(shè)計出C語言,克服B語言的過于簡單、功能有限的不足.1973年，K.Thompson和D.M.Ritchie合作將UNIX的90%以上用C改寫.1978年以后,C語言已先后移植到大、中、小、微型機上已獨立于UNIX和PDP，得以廣泛應用。第4頁共53頁

DennisM．Ritchie：1967年加入貝爾實驗室。他和KenL．Thompson兩人共同設(shè)計并實現(xiàn)了C語言,改變了程序設(shè)計語言發(fā)展的軌跡，是程序設(shè)計語言發(fā)展過程中的一個重要里程碑。與此同時，他們兩人還設(shè)計并實現(xiàn)了UNIX操作系統(tǒng)。正是由于這兩項巨大貢獻，DennisM．Ritchie于1983年獲得了計算機界的最高獎——圖靈獎。此外，他還獲得了ACM、IEEE、貝爾實驗室等授予的多種獎項。

第5頁共53頁

BrianW．Kernighan：是貝爾實驗室計算科學研究中心高級研究人員，著名的計算機科學家。他參加了UNIX系統(tǒng)、C語言、AWK語言和許多其他系統(tǒng)的開發(fā)，同時出版了許多在計算機領(lǐng)域具有影響的著作。

第6頁共53頁

C語言的產(chǎn)生和地位原書名：

TheCProgrammingLanguage作者：

（美）BrianW.Kernighan,DennisM.Ritchie

本書原著即為C語言的設(shè)計者之一DennisM．Ritchie和著名的計算機科學家BrianW．Kernighan合著的

一本介紹C語言的權(quán)威經(jīng)典著作。

C語言已經(jīng)成為全球程序員的公共語言，并由此誕生了兩個新的主流語言C++與Java，它們都建立在C語言的語法和基本結(jié)構(gòu)的基礎(chǔ)上?，F(xiàn)在世界上的許多軟件都是在C語及其衍生的各種語言的基礎(chǔ)上開發(fā)出來的。

第7頁共53頁

1.2Ｃ語言的特點為什么學習C語言？

可進行內(nèi)存物理地址訪問，具有匯編語言的特點

控制流程結(jié)構(gòu)化，以函數(shù)為基本結(jié)構(gòu)進行流程控制

語言簡潔靈活，有32個關(guān)鍵字和9種控制語句

具有構(gòu)造數(shù)據(jù)類型的能力，數(shù)據(jù)結(jié)構(gòu)系統(tǒng)化

語言表達能力強：34種運算符

程序運行效率高，易讀性、可移植性好

語法檢查不夠嚴格，對數(shù)組下標越界不做檢查第8頁共53頁

1.3C語言程序的組成結(jié)構(gòu)例1:/*顯示“Howareyou!”*/#include<stdio.h>main(){printf("Howareyou!");}程序運行結(jié)果是輸出:Howareyou!第9頁共53頁

例2求兩數(shù)之和

#include<stdio.h>

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

{

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

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

b=456;

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

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

}說明：

/*……*/表示注釋。注釋只是給人看的,對編譯和運行不起作用。所以可以用漢字或英文字符表示，可以出現(xiàn)在一行中的最右側(cè)，也可以單獨成為一行。輸出一行信息：sumis579第10頁共53頁

例3:從鍵盤輸入兩個整數(shù)，并顯示這兩個整數(shù)之和。int

ADDxy(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);}主函數(shù)子函數(shù)程序運行情況如下：85↙sum=13第11頁共53頁

C程序的基本結(jié)構(gòu)小結(jié)：(1)C程序是由函數(shù)構(gòu)成的,程序容易實現(xiàn)模塊化。main()/*主函數(shù)說明*/{變量定義/*主函數(shù)體*/

執(zhí)行語句組

}

子函數(shù)名1(參數(shù))/*子函數(shù)說明*/{變量定義/*子函數(shù)體*/

執(zhí)行語句組

}

子函數(shù)名2(參數(shù))/*子函數(shù)說明*/{變量定義/*子函數(shù)體*/

執(zhí)行語句組

}第12頁共53頁

(2)一個函數(shù)由兩部分組成:

函數(shù)的首部：例3中的Addxy函數(shù)首部

intAddxy(intx,inty)

函數(shù)體：花括號內(nèi)的部分。若一個函數(shù)有多個花括號,則最外層的一對花括號為函數(shù)體的范圍。(3)C程序總是從main函數(shù)開始執(zhí)行的,與main函數(shù)的位置無關(guān)。(4)C程序書寫格式自由,一行內(nèi)可以寫幾個語句,一個語句可以分寫在多行上，C程序沒有行號。第13頁共53頁

(5)每個語句和數(shù)據(jù)聲明的最后必須有一個分號。(6)C語言本身沒有輸入輸出語句。輸入和輸出的操作是由庫函數(shù)scanf和printf等函數(shù)來完成的(7)在C語言中，大小寫字母是有區(qū)別的。（C語言習慣用小寫字母）(8)書寫程序時，最好使用規(guī)范的縮進格式的形式。(9)C程序注釋/*……*/可以寫在程序的任何位置上第14頁共53頁

1.4

運行Ｃ程序的步驟和方法1.運行Ｃ程序的步驟上機輸入、編輯源程序?qū)υ闯绦蜻M行編譯與庫函數(shù)連接運行目標程序第15頁共53頁

2.Ｃ程序的開發(fā)環(huán)境

目前使用的大多數(shù)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：可視化面向?qū)ο箝_發(fā)環(huán)境，可以用VisualC++對C程序進行編譯。第16頁共53頁

1.5從三個方面學習Ｃ語言1.學習C語言的語法

數(shù)據(jù)表達：變量定義、正確書寫表達式流程控制：

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;

設(shè)計函數(shù)輸入和輸出第17頁共53頁

2.學習解決問題的方法(算法)

如何求級數(shù)12+22+32+……前100項之和？矩陣轉(zhuǎn)置如何打印乘法表？

數(shù)據(jù)如何按從小到大的順序排序？第18頁共53頁

3.

學習在C語言編程環(huán)境下，編輯、編譯、調(diào)試和運行程序開發(fā)環(huán)境：VisualC++6.0

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

第19頁共53頁

第二章C語言程序設(shè)計算法與程序設(shè)計基礎(chǔ)第20頁共53頁

本章要點

什么是程序設(shè)計什么是算法，如何設(shè)計和表示算法結(jié)構(gòu)化程序設(shè)計的思想和方法第21頁共53頁

計算機語言：是規(guī)則和符號的集合，是與計算機交流的工具。必須具有數(shù)據(jù)表達和數(shù)據(jù)處理（流程控制）的能力。程序：求解問題的指令序列軟件：程序的集合學習語言設(shè)計程序制作軟件概念：學軟件：學思想、學功能、學操作。熟練工種學語言：學規(guī)則、學方法、學設(shè)計、學應用。規(guī)范學習，靈活應用第22頁共53頁

計算機語言分類面向過程語言面向?qū)ο笳Z言FORTRANBASICCPASCALCOBOLLISPC++C#VisualBASICJAVA系統(tǒng)軟件設(shè)計具有圖形功能科學計算商用人工智能第23頁共53頁

2.1程序設(shè)計的基本概念數(shù)據(jù)元素：數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的組織形式程序設(shè)計＝數(shù)據(jù)結(jié)構(gòu)＋算法＋方法＋工具數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣決定了軟件或程序的復雜程度和面貌一個程序應包括兩個方面的內(nèi)容:對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)對操作的描述：算法完整的程序設(shè)計應該包括四部分:第24頁共53頁

程序設(shè)計的步驟分析問題，建立數(shù)學模型確定數(shù)據(jù)結(jié)構(gòu)確定算法，描述算法編制程序，調(diào)試程序運行結(jié)果

一個正確的程序通常包含兩方面的含義：一是書寫正確，二是結(jié)果正確。書寫正確是指程序語法正確，符合程序語言的規(guī)則；結(jié)果正確是指對應于正確的輸入，程序能夠得到所期望的輸出。第25頁共53頁

程序的三種基本結(jié)構(gòu)1.順序結(jié)構(gòu)

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

BA

先執(zhí)行A操作，再執(zhí)行B操作，兩者是順序執(zhí)行關(guān)系。第26頁共53頁

2.選擇結(jié)構(gòu)通過判斷特定條件，選擇一個分支執(zhí)行。當P條件成立時，執(zhí)行A操作，否則執(zhí)行B操作APB

成立不成立

語句不成立P成立當P條件成立時，執(zhí)行語句操作，否則跳過語句操作第27頁共53頁

3.循環(huán)結(jié)構(gòu)

在給定條件下，反復執(zhí)行循環(huán)體，直到條件不滿足為止.(1)形式a（當型循環(huán)結(jié)構(gòu)）不成立PA成立當P條件成立時，反復執(zhí)行A,直到P為零為止。第28頁共53頁

(2)形式b（直到型循環(huán)結(jié)構(gòu)）先執(zhí)行A操作，再判斷P是否成立，若P成立，再執(zhí)行A，直到P不成立為止。AP成立不成立

第29頁共53頁

算法：完成一項任務的具體步驟計算機語言的別名：算法語言1.算法的概念2.2算法概述“一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列?！比魏谓鉀Q問題的過程都是由一定的步驟組成的，把解決問題確定的方法和有限的步驟稱作為算法。第30頁共53頁

例1：計算函數(shù)M(x)的值。函數(shù)M(x)為：算法分析：這是一個數(shù)值運算問題。其中M代表要計算的函數(shù)值，有兩個不同的表達式，根據(jù)x的取值決定采用哪一個算式。根據(jù)計算機具有邏輯判斷的基本功能，用計算機解題的算法如下：第31頁共53頁

①將a、b、c和x的值輸入到計算機；②判斷x≤a?如果條件成立，執(zhí)行第③步，否則執(zhí)行第④步；③按表達式bx+a2計算出結(jié)果存放到M中，然后執(zhí)行第⑤步；④按表達式a(c-x)+c2計算出結(jié)果存放到M中，然后執(zhí)行第⑤步；⑤輸出M的值；⑥算法結(jié)束。這是用自然語言描述的算法第32頁共53頁

例2：有黑和藍兩個墨水瓶，但卻錯把黑墨水裝在了藍墨水瓶子里，而藍墨水錯裝在了黑墨水瓶子里，要求將其互換。算法分析：這是一個非數(shù)值運算問題。因為兩個瓶子的墨水不能直接交換，所以，解決這一問題的關(guān)鍵是需要引入第三個墨水瓶。設(shè)第三個墨水瓶為白色，其交換步驟如下：第33頁共53頁

①將藍瓶中的黑墨水裝入白瓶中②將黑瓶中的藍墨水裝入藍瓶中③將白瓶中的黑墨水裝入黑瓶中④交換結(jié)束第34頁共53頁

2.算法的基本特征

算法是一個有窮規(guī)則的集合，這些規(guī)則確定了解決某類問題的一個運算序列。算法的基本特征：有窮性：算法必須在執(zhí)行有限個操作后終止；

確定性：算法中每一步的含義必須是確切的，不能出現(xiàn)任何二義性；有效性：算法中的每一步操作都應該能有效執(zhí)行，一個不可執(zhí)行的操作是無效的；有零個或多個輸入：執(zhí)行算法時，從外界獲得必要的信息；有一個或多個輸出：算法的解就是輸出。第35頁共53頁

3.算法的常用表示方法可以用不同的方法表示算法，常用方法有：自然語言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖

第36頁共53頁

（1）自然語言自然語言即是使用漢語、英語或其他語言去描述算法。[例]有50名學生的成績，要求將他們之中80分以上的成績打印出來。設(shè)用g代表學生成績，gi

代表第i個學生成績。1）使i=1

；2）如果gi

80，則打印gi

，否則不打印；3）使i的值加1；4）如果i50,返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。特點：描述算法通俗易懂，容易產(chǎn)生歧義。對復雜問題，語句繁瑣、冗長，并且很難清楚地表達算法的邏輯流程，往往需要根據(jù)上下文判別其含義，尤其對描述含有選擇、循環(huán)結(jié)構(gòu)的算法，不太方便和直觀，一般不常使用。第37頁共53頁

(2)傳統(tǒng)流程圖

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

程序流程圖表示開始1

igi>=80輸出gii+1

ii>50結(jié)束成立不成立不成立成立傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制。第39頁共53頁

傳統(tǒng)流程圖的流程可以是：缺點：使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無規(guī)律，難以閱讀、修改，使算法的可靠性和可維護性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無規(guī)律地使流程隨意轉(zhuǎn)向，只能順序的進行下去。

第40頁共53頁

（3）N–S流程圖N-S流程圖由美國學者I.Nassi和B.Shneiderman提出表示算法的圖形工具?；締卧蔷匦慰?用不同的形狀線分割,表示三種結(jié)構(gòu)。只有一個入口,一個出口,沒有流程線。N-S圖的優(yōu)點比文字描述直觀、形象、易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的，N--S流程圖中的上下順序就是執(zhí)行時的順序。第41頁共53頁

三種基本程序結(jié)構(gòu)的N–S流程圖條件TF語句1語句22.選擇結(jié)構(gòu)語句1語句21.順序結(jié)構(gòu)3.循環(huán)結(jié)構(gòu)循環(huán)體循環(huán)體當滿足條件時

直到條件成立循環(huán)結(jié)構(gòu)一循環(huán)結(jié)構(gòu)二第42頁共53頁

0t,0ii+1i

t+it直到i100輸出t的值傳統(tǒng)流程圖與N-S流程圖的比較i100

NY開始0t,0ii+1it+it輸出t的值結(jié)束例1：1+2+3+……+加到100為止第43頁共53頁

例：打印50名學生中成績高于80分的學號和成績用N-S圖表示。第44頁共53頁

1.枚舉法（窮舉法）特點:算法簡單，容易理解，運算量大?；舅枷耄?/p>

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

2.3幾種常用算法介紹第45頁共53頁

如：百元買百雞問題。假定小雞每只0.5元，公雞每只2元，母雞每只3元?，F(xiàn)在有100元錢要求買100只雞，問共有幾種購雞方案？根據(jù)題目設(shè)母雞、公雞、小雞各為x,y,z只，列出方程為：x+y+z=100，3x+2y+0.5z=100利用窮舉法，將各種可能的組合一一測試，輸出符合條件的組合。即在各個變量的取值范圍內(nèi)不斷變化x,y,z的值，窮舉x,y,z全部可能的組合，若滿足方程組則是一組解。第46頁共53頁

#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);}}百元買百雞程序：第47頁共53頁

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

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