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

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

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

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

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

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

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

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

第5頁(yè)共53頁(yè)

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

第6頁(yè)共53頁(yè)

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

TheCProgrammingLanguage作者：

（美）BrianW.Kernighan,DennisM.Ritchie

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

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

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

第7頁(yè)共53頁(yè)

1.2Ｃ語(yǔ)言的特點(diǎn)為什么學(xué)習(xí)C語(yǔ)言？

可進(jìn)行內(nèi)存物理地址訪問(wèn)，具有匯編語(yǔ)言的特點(diǎn)

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

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

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

語(yǔ)言表達(dá)能力強(qiáng)：34種運(yùn)算符

程序運(yùn)行效率高，易讀性、可移植性好

語(yǔ)法檢查不夠嚴(yán)格，對(duì)數(shù)組下標(biāo)越界不做檢查第8頁(yè)共53頁(yè)

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

例2求兩數(shù)之和

#include<stdio.h>

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

{

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

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

b=456;

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

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

}說(shuō)明：

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

例3:從鍵盤輸入兩個(gè)整數(shù)，并顯示這兩個(gè)整數(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ù)程序運(yùn)行情況如下：85↙sum=13第11頁(yè)共53頁(yè)

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

執(zhí)行語(yǔ)句組

}

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

執(zhí)行語(yǔ)句組

}

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

執(zhí)行語(yǔ)句組

}第12頁(yè)共53頁(yè)

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

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

intAddxy(intx,inty)

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

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

1.4

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

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

目前使用的大多數(shù)C編譯系統(tǒng)都是集成環(huán)境的?？梢杂貌煌木幾g系統(tǒng)對(duì)C程序進(jìn)行操作常用的有TurboC2.0、TurboC++3.0、VisualC++等

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

VisualC++6.0：可視化面向?qū)ο箝_(kāi)發(fā)環(huán)境，可以用VisualC++對(duì)C程序進(jìn)行編譯。第16頁(yè)共53頁(yè)

1.5從三個(gè)方面學(xué)習(xí)Ｃ語(yǔ)言1.學(xué)習(xí)C語(yǔ)言的語(yǔ)法

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

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è)計(jì)函數(shù)輸入和輸出第17頁(yè)共53頁(yè)

2.學(xué)習(xí)解決問(wèn)題的方法(算法)

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

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

3.

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

上機(jī)作業(yè)1：使用VisualC++6.0編寫(xiě)簡(jiǎn)單的C程序

第19頁(yè)共53頁(yè)

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

本章要點(diǎn)

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

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

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

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

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

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

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

程序按照語(yǔ)句的書(shū)寫(xiě)次序順序執(zhí)行。

BA

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

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

成立不成立

語(yǔ)句不成立P成立當(dāng)P條件成立時(shí)，執(zhí)行語(yǔ)句操作，否則跳過(guò)語(yǔ)句操作第27頁(yè)共53頁(yè)

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

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

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

第29頁(yè)共53頁(yè)

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

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

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

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

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

2.算法的基本特征

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

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

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

第36頁(yè)共53頁(yè)

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

代表第i個(gè)學(xué)生成績(jī)。1）使i=1

；2）如果gi

80，則打印gi

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

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

美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(hào)：起止框判斷框處理框輸入/輸出框注釋框流向線連接點(diǎn)第38頁(yè)共53頁(yè)

程序流程圖表示開(kāi)始1

igi>=80輸出gii+1

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

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

第40頁(yè)共53頁(yè)

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

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

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

0t,0ii+1i

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

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

例：打印50名學(xué)生中成績(jī)高于80分的學(xué)號(hào)和成績(jī)用N-S圖表示。第44頁(yè)共53頁(yè)

1.枚舉法（窮舉法）特點(diǎn):算法簡(jiǎn)單，容易理解，運(yùn)算量大?；舅枷耄?/p>

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

2.3幾種常用算法介紹第45頁(yè)共53頁(yè)

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

#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頁(yè)共53頁(yè)

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

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