C程序設(shè)計(jì)教程課件第2章

數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)，以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。算法對(duì)操作的描述。即要求計(jì)算機(jī)進(jìn)行操作的步驟。算法+數(shù)據(jù)結(jié)構(gòu)=程序沃思算法程序員數(shù)據(jù)結(jié)構(gòu)語(yǔ)言工具程序設(shè)計(jì)方法算法廣義地說，為解決一個(gè)問題而采取的方法和步驟，就稱為“算法”。對(duì)同一個(gè)問題，可以有不同的解題方法和步驟。為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。非數(shù)值運(yùn)算算法數(shù)值運(yùn)算算法算法數(shù)值運(yùn)算的目的是求數(shù)值解。由于數(shù)值運(yùn)算往往有現(xiàn)成的模型，可以運(yùn)用數(shù)值分析方法，因此對(duì)數(shù)值運(yùn)算的算法的研究比較深入，算法比較成熟。計(jì)算機(jī)在非數(shù)值運(yùn)算方面的應(yīng)用遠(yuǎn)超在數(shù)值運(yùn)算方面的應(yīng)用。非數(shù)值運(yùn)算的種類繁多，要求各異，需要使用者參考已有的類似算法，重新設(shè)計(jì)解決特定問題的專門算法。簡(jiǎn)單的算法舉例【例2.1】求1×2×3×4×5S1:先求1乘以2，得到結(jié)果2S2:將步驟1得到的乘積2再乘以3，得到結(jié)果6S3:將6再乘以4，得24S4:將24再乘以5，得120算法步驟S1:令p=1，或?qū)懗?=>p(表示將1存放在變量p中)S2:令i=2，或?qū)懗?=>i(表示將2存放在變量i中)S3:使p與i相乘，乘積仍放在變量p中，可表示為:p*i=>pS4:使i的值加1，即i+1=>iS5:如果i不大于5，返回重新執(zhí)行S3及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。算法步驟若題目改為:求1×3×5×7×9×113=>ii+2=>i若i≤11，返回S3；否則，結(jié)束或者若i>11，結(jié)束；否則，返回S3i=32用這種方法表示的算法具有一般性、通用性和靈活性簡(jiǎn)單的算法舉例【例2.2】有50個(gè)學(xué)生，要求輸出成績(jī)?cè)?0分以上的學(xué)生的學(xué)號(hào)和成績(jī)S1:1=>iS2:如果gi≥80，則輸出ni和gi，否則不輸出

S3:i+1=>iS4:如果i≤50，返回到S2，繼續(xù)執(zhí)行，否則，算法結(jié)束算法步驟n：表示學(xué)生學(xué)號(hào)下標(biāo)i：表示第幾個(gè)學(xué)生n1：表示第一個(gè)學(xué)生的學(xué)號(hào)ni：表示第i個(gè)學(xué)生的學(xué)號(hào)g：表示學(xué)生的成績(jī)g1：表示第一個(gè)學(xué)生的成績(jī)gi：表示第i個(gè)學(xué)生的成績(jī)簡(jiǎn)單的算法舉例【例2.3】判定2000—2500年中的每一年是否為閏年，并將結(jié)果輸出S1:2000=>yearS2:若year不能被4整除，則輸出year的值和“不是閏年”。然后轉(zhuǎn)到S6，檢查下一個(gè)年份S3:若year能被4整除，不能被100整除，則輸出year的值和“是閏年”。然后轉(zhuǎn)到S6S4:若year能被400整除，輸出year的值和“是閏年”，然后轉(zhuǎn)到S6S5:輸出year的值和“不是閏年”S6:year+1=>yearS7:當(dāng)year≤2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，否則算法停止算法步驟Year被100整除，又能被400整除01030402Year被4整除，但不能被100整除Year不能被4整除其他非閏年非閏年閏年閏年簡(jiǎn)單的算法舉例

S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)signS5:term=sign(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否則算法結(jié)束算法步驟sign：表示當(dāng)前項(xiàng)的數(shù)值符號(hào)term：表示當(dāng)前項(xiàng)的值sum：表示當(dāng)前項(xiàng)的累加和deno：表示當(dāng)前項(xiàng)的分母簡(jiǎn)單的算法舉例【例2.5】給出一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)S1:輸入n的值S2:i=2（i作為除數(shù)）S3:n被i除，得余數(shù)rS4:如果r=0，表示n能被i整除，則輸出n“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5S5:i+1=>iS6:如果i≤n-1，返回S3；否則輸出n的值以及“是素?cái)?shù)”，然后結(jié)束算法步驟解題思路:所謂素?cái)?shù)(prime)，是指除了1和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù)。

算法的特性12345有窮性

一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的確定性

算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的有零個(gè)或多個(gè)輸入所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息有一個(gè)或多個(gè)輸出算法的目的是為了求解，“解”就是輸出有效性算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果算法的表示偽代碼結(jié)構(gòu)化流程圖傳統(tǒng)流程圖自然語(yǔ)言用流程圖表示算法起止框輸入輸出框判斷框處理框流程線連接點(diǎn)注釋框算法的流程圖表示舉例【例2.6】將例2.1的算法用流程圖表示。

求1×2×3×4×5。S1:1=>pS2:2=>iS3:p*i=>pS4:i+1=>iS5:如果i≤5，則返回S3；否則結(jié)束算法步驟開始1=>p2=>ip*i=>pi+1=>i結(jié)束YN輸出pi>5P:表示被乘數(shù)i:表示乘數(shù)算法的流程圖表示舉例【例2.7】例2.2的算法用流程圖表示。有50個(gè)學(xué)生，要求輸出成績(jī)?cè)?0分以上的學(xué)生的學(xué)號(hào)和成績(jī)。S1:1=>iS2:如果gi≥80，則輸出ni和gi，否則不輸出

S3:i+1=>iS4:如果i≤50，返回到S2，繼續(xù)執(zhí)行，否則，算法結(jié)束算法步驟開始1=>ii+1=>i1=>ii+1=>ii>50結(jié)束YN輸入ni、gii>50Ygi≥80Y輸出ni、giNn：表示學(xué)生學(xué)號(hào)下標(biāo)i：表示第幾個(gè)學(xué)生n1：表示第一個(gè)學(xué)生的學(xué)號(hào)ni：表示第i個(gè)學(xué)生的學(xué)號(hào)g：表示學(xué)生的成績(jī)g1：表示第一個(gè)學(xué)生的成績(jī)gi：表示第i個(gè)學(xué)生的成績(jī)算法的流程圖表示舉例【例2.8】例2.3判定閏年的算法用流程圖表示。

判定2000—2500年中的每一年是否為閏年，將結(jié)果輸出。開始2000=>yearNYear不能被4整除Y輸出year“是閏年”NYear不能被100整除YYear不能被400整除輸出year“不是閏年”N輸出year“是閏年”輸出year“不是閏年”Year+1=>yearYear>2500YY結(jié)束算法的流程圖表示舉例

S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)*signS5:term=sign*(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否則算法結(jié)束算法步驟sign：表示當(dāng)前項(xiàng)的數(shù)值符號(hào)term：表示當(dāng)前項(xiàng)的值sum：表示當(dāng)前項(xiàng)的累加和deno：表示當(dāng)前項(xiàng)的分母開始1=>sum1=>sign結(jié)束輸入sumdeno>100YN2=>deno(-1)*sign=>signsign*(1/deno)=>termsum+term=>sumdeno+1=>deno簡(jiǎn)單的算法舉例【例2.10】例2.5判斷素?cái)?shù)的算法用流程圖表示。

對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。

算法步驟開始n/i的余數(shù)=>r結(jié)束輸出n“是素?cái)?shù)”

YN2=>ii+1=>i輸入nr=0輸出n“不是素?cái)?shù)”傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒有嚴(yán)格限制。因此，使用者可以不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無(wú)規(guī)律，閱讀時(shí)要花很大精力去追蹤流程，使人難以理解算法的邏輯。三種基本結(jié)構(gòu)AB順序結(jié)構(gòu)ABP真假選擇結(jié)構(gòu)P假真循環(huán)結(jié)構(gòu)A三種基本結(jié)構(gòu)的特點(diǎn)1只有一個(gè)入口2只有一個(gè)出口3結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到4結(jié)構(gòu)內(nèi)不存在“死循環(huán)”用N-S流程圖表示算法用偽代碼表示算法偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來描述算法。它如同一篇文章一樣，自上而下地寫下來。每一行(或幾行)表示一個(gè)基本操作。它不用圖形符號(hào)，因此書寫方便，格式緊湊，修改方便，容易看懂，也便于向計(jì)算機(jī)語(yǔ)言算法(即程序)過渡。算法的流程圖表示舉例【例2.16】求5!，用偽代碼表示。S1:1=>pS2:2=>iS3:p*i=>pS4:i+1=>iS5:如果i≤5，則返回S3；否則結(jié)束算法步驟P:表示被乘數(shù)i:表示乘數(shù)begin (算法開始)1=>p

2=>I

whilei≤5

{p*i=>p

i+1=>I

}

printpend (算法結(jié)束)偽代碼算法的流程圖表示舉例

begin (算法開始)1=>sign

1=>sum

2=>deno

whiledeno≤100

{(-1)*sign=>sign

sign*(1/deno)=>term

sum+term=>sum

deno+1=>deno

}

printsumend (算法結(jié)束)偽代碼S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)*signS5:term=sign*(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否則算法結(jié)束算法步驟sign：表示當(dāng)前項(xiàng)的數(shù)值符號(hào)term：表示當(dāng)前項(xiàng)的值sum：表示當(dāng)前項(xiàng)的累加和deno：表示當(dāng)前項(xiàng)的分母用計(jì)算機(jī)語(yǔ)言表示算法【例2.18】將例2.16表示的算法（求5!）用C語(yǔ)言表示。S1:1=>pS2:2=>iS3:p*i=>pS4:i+1=>iS5:如果i≤5，則返回S3；否則結(jié)束算法步驟P:表示被乘數(shù)i:表示乘數(shù)#include<stdio.h>intmain(){ inti,p; p=1;

i=2;

while(i<=5)

{

p=p*i;

i=i+1;

}

printf(″%d\n″,p);

return0;}用計(jì)算機(jī)語(yǔ)言表示算法

#include<stdio.h>intmain(){ intsign=1; doubledeno=2.0,sum=1.0,term;

while(deno<=100)

{

sign=-sign;

term=sign/deno;

sum=sum+term;

deno=deno+1;

}

printf(″%f\n″,sum);