《《C語言程序設(shè)計(jì)》第4章數(shù)組.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《C語言程序設(shè)計(jì)》第4章數(shù)組.ppt（78頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第四章 數(shù) 組,在實(shí)際的應(yīng)用中，經(jīng)常會(huì)遇到某些類型相同并相互具有聯(lián)系的 數(shù)據(jù)。該類數(shù)據(jù)，經(jīng)常要作相關(guān)的處理。如，一個(gè)班30個(gè)人的一門 課程的成績(jī)，求平均成績(jī)、最高或最低成績(jī)。處理這類數(shù)據(jù)的最好 辦法是將其定義成為一個(gè)具有共同特征的集合，這種同類型相關(guān)數(shù) 據(jù)的集合稱為數(shù)組。,Chapter 4 Array,4.1 數(shù)組的基本概念,C 語言可以根據(jù)用戶需要，用基本數(shù)據(jù)類型定義特殊性質(zhì)的數(shù) 據(jù)類型，稱為構(gòu)造類型。構(gòu)造類型有：數(shù)組、結(jié)構(gòu)、聯(lián)合。,數(shù)組：相同數(shù)據(jù)類型變量的有序集合。有序表現(xiàn)在數(shù)組元素在 內(nèi)存中連續(xù)存放。,數(shù)組用一個(gè)名字作為標(biāo)識(shí)。為區(qū)分各元素，每個(gè)元素有一個(gè)用 整型表示的序號(hào)，稱之為下標(biāo)。

2、下標(biāo)可以有多個(gè)，下標(biāo)的個(gè)數(shù)稱為 數(shù)組的維數(shù)。,如：十個(gè)整型變量 k0,k1, k9,一個(gè)下標(biāo)。,數(shù)組名。,三個(gè)學(xué)生三門課程的成績(jī),97.5 80.5 94.5 76.5 81.4 90.0 60.0 64.5 75.0,學(xué)號(hào) 0 1 2,0 1 2 課程,下標(biāo)一：行,下標(biāo)二：列,數(shù)組元素：a11,/* example 4-1(b) 計(jì)算平均成績(jī) */ #include void main(void) int i; float math,ave; ave = 0.0; /* 平均成績(jī)初值為0 */ for(i=0;i10;i+) /* 循環(huán)10次 */ scanf(%f, ,【例4-1】學(xué)生分?jǐn)?shù)

3、的處理問題。有10個(gè)學(xué)生參加數(shù)學(xué)考試，考試成績(jī)由鍵盤輸入，計(jì)算平均成績(jī)。,/* example 4-1(b) 計(jì)算平均成績(jī) */ #include void main(void) int i; float math,ave; ave = 0.0; /* 平均成績(jī)初值為0 */ for(i=0;i=ave) printf(%fn,math); /* 大于平均成績(jī)則打印 */ ,【例4-1(b)】,/* example 4-1(c) 計(jì)算平均成績(jī) */ #include void main(void) int i; float math10,ave; ave = 0.0; /* 平均成績(jī)初值為0

4、*/ for(i=0;i=ave) printf(%fn,mathi); /* 大于平均成績(jī)則打印 */ ,【例4-1(c)】,數(shù)組必須先說明后使用。說明的目的如下：,說明數(shù)組的名字（標(biāo)識(shí)）。 說明數(shù)組的類型。 說明數(shù)組的維數(shù)。 確定各維下標(biāo)的變化范圍。,編譯系統(tǒng)將根據(jù)說明，開辟內(nèi)存單元按特有的順序和相應(yīng)的類 型為各元素分配內(nèi)存單元。,4.2 一維數(shù)組,一維數(shù)組的說明,說明方式：,type array1常量表達(dá)式, , arrayn常量表達(dá)式；,類型說明符，根據(jù)需要可加修飾說明。說明數(shù)組的類型。,數(shù)組名，用標(biāo)識(shí)符命名。,用 包含的常量表達(dá)式。數(shù)組的下標(biāo)從0變化到常量達(dá)式的值減一。,int id

5、5, iyear10; float fScore36;,當(dāng)說明數(shù)組后，編譯時(shí)系統(tǒng)會(huì)根據(jù)定義的類型分配連續(xù)的一段 內(nèi)存單元給數(shù)組的各元素。,id0,id1,id2,id3,id4,系統(tǒng)為數(shù)組分配的連續(xù)內(nèi)存單元，每個(gè)單元占兩個(gè)BYTE。首地址用數(shù)組名id表示。,2. 一維數(shù)組的引用,數(shù)組是一組數(shù)，它們公用一個(gè)數(shù)組名，這是它們公有的屬性，但它們?cè)跀?shù)組中的位置不同，這是它們私有的屬性，為表明數(shù)組中的一個(gè)元素，既要指出其來自于哪個(gè)數(shù)組，這就需要數(shù)組名；又要聲明其在這個(gè)數(shù)組中的位置，這就需要下標(biāo) 。,一維數(shù)組中元素引用的一般形式為： 數(shù)組名下標(biāo)值,說明： 下標(biāo)通常為整型，如果為實(shí)型，系統(tǒng)自動(dòng)取整； 下標(biāo)常

6、常巧妙的和循環(huán)變量相結(jié)合，隨著循環(huán)變量的變化而變化，可以達(dá)到事半功倍的效果； C語言不做下標(biāo)越界的檢查，即語法上對(duì)越界的下標(biāo)不報(bào)錯(cuò)。,3. 一維數(shù)組的存儲(chǔ),計(jì)算機(jī)系統(tǒng)中有著大量的存儲(chǔ)單元，為區(qū)別各個(gè)存儲(chǔ)單元，每一個(gè)存儲(chǔ)單元都有一個(gè)唯一的代表這個(gè)存儲(chǔ)單元的地址，就好像我們每一個(gè)人都有一個(gè)唯一的代表自己的身份證號(hào)一樣。計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)單元的地址的編碼規(guī)則是線性的，以十六進(jìn)制表示，并且從0開始計(jì)數(shù)，因此存儲(chǔ)單元的地址為：0、1、2、.9、A、B、C、D、E、F、10H、. .,如果說明的是一個(gè)數(shù)組，如：int math10; 計(jì)算機(jī)開辟20個(gè)地址連續(xù)的存儲(chǔ)單元（TC環(huán)境下整型占2個(gè)字節(jié)，共有10個(gè)

7、數(shù)組元素），用于存放數(shù)組中的10個(gè)數(shù)組元素，且這20個(gè)存儲(chǔ)單元的首地址標(biāo)記為：數(shù)組名math或 /*說明數(shù)組，同時(shí)初始化全部元素。*/,float fValue10=1.0,2.0,3.0; /*說明數(shù)組，給部分元素初值，其余元素為0。*/,unsigned a =0 x0000,0 x0001,0 x0002; /*當(dāng)數(shù)組元素全部賦初值時(shí)，可以不指定長(zhǎng)度*/,/* example 4-2 數(shù)組的初始化 */ #include void main(void) int i; int a5=1,2,3,4,5; int b5=1,2; int c =1,2,3; for(i=0;i5;i+) /*

8、 循環(huán)5次 */ printf(a%d=%d ,i,ai); /* 輸出a數(shù)組元素 */ printf(n); /* 換行 */ for(i=0;i5;i+) /* 循環(huán)5次 */ ,【例4-2】數(shù)組的初始化示例。編寫代碼4-2如下，其執(zhí)行結(jié)果如圖4-3所示。,printf(b%d=%d ,i,bi); /* 輸出b數(shù)組元素 */ printf(n); /* 換行 */ for(i=0;i5;i+) /* 循環(huán)5次 */ printf(c%d=%d ,i,ci); /* 輸出c元素，注意有危險(xiǎn) */ printf(n); /* 換行 */ ,5.一維數(shù)組的應(yīng)用,【例4-3】兔子繁殖問題。,/*

9、 example 4-3 Fibonacci數(shù)列 */ #include void main(void) int month; int f13=1,1; for(month=2;month13;month+) /* 循環(huán)遞推 */ fmonth = fmonth-1+fmonth-2; /* 計(jì)算數(shù)列 */ for(month=0;month13;month+) printf(%d ,fmonth); /* 輸出數(shù)列 */ ,【例4-4】由鍵盤輸入n個(gè)學(xué)生（設(shè)人數(shù)不超過50人）的數(shù)學(xué)成績(jī)，分別統(tǒng)計(jì)優(yōu)、良、中、及格、不及格的人數(shù)。,/* example 4-4 分別統(tǒng)計(jì)成績(jī) */ #includ

10、e void main(void) int i,n; int a=0,b=0,c=0,d=0,e=0; /* 表示各段人數(shù) */ float math50; printf(“n=?”); /* 輸入人數(shù) */ scanf(“%d”,i+) /* 循環(huán)n次 */ ,if(mathi=90) a+; /* 分別統(tǒng)計(jì) */ else if(mathi=80) b+; else if(mathi=70) c+; else if(mathi=60) d+; else e+; printf(%dt%dt%dt%dt%dn,a,b,c,d,e); /* 打印 */ ,例：,求10個(gè)學(xué)生一門課程的平均分，并輸

11、出低于平均成績(jī)的分?jǐn)?shù)。,#include void main(void) float fScore10,aver=0; int i; for(i=0;i10;i+) scanf(“%f”, ,說明數(shù)組。,循環(huán)輸入各元素的值并累加。,循環(huán)判斷條件，滿足條件輸出。,4.3 二 維 數(shù) 組,在實(shí)際應(yīng)用中，經(jīng)常會(huì)遇到一些用多維索引的數(shù)據(jù)。如：四個(gè) 學(xué)生三門課的成績(jī)。可以用下表表示：,顯然，該表的每一項(xiàng)需要有兩個(gè)索引項(xiàng)。表現(xiàn)為數(shù)組的兩個(gè)下 標(biāo)。超過一個(gè)下標(biāo)的數(shù)組稱為多維數(shù)組。,行：代表某個(gè)學(xué)生。,列：代表某門課程。,二維數(shù)組的說明,說明方式： type array常量表達(dá)式1常量表達(dá)式n,；,n個(gè)整型常

12、量表達(dá)式,數(shù)組元素的個(gè)數(shù)？,int a23 , b452;,多維數(shù)組在內(nèi)存中的順序,int a33；,二維結(jié)構(gòu)： a00 a01 a02 a10 a11 a12 a20 a21 a22,排列順序：先行后列。,a00,a01,a02,a10,a11,a12,a20,a21,a22,下 標(biāo) 為 0 的 行,總原則：最后一個(gè)下標(biāo)先變化，變化一個(gè)周 期后，倒數(shù)第二個(gè)開始變化，如此類推。,a為數(shù)組在內(nèi)存中的首地址。,int b234;,內(nèi)存中的排列？,二維數(shù)組的初始化,數(shù)組可以在說明時(shí)初始化。,全部賦初值,int a23=1,2,3,4,5,6;,下標(biāo)為0的一行,下標(biāo)為1的一行,int b23=1,2,

13、3,4,5,6；,按內(nèi)存順序賦初值。,部分賦初值,int a23= 1 , 2 ；,0行的0列的元素賦初值。0行其余值為0。,int a23=1,2；,對(duì)全體數(shù)組元素賦初值，第一維下標(biāo)可以省略。,int a 3=1, 2, 3, 4, 5, 6;,二維數(shù)組元素的引用,數(shù)組定義后，具備簡(jiǎn)單變量的一切性質(zhì)，可以作為表達(dá)式的運(yùn) 算對(duì)象，也可以被賦值。引用時(shí)，只能引用數(shù)組元素，方式如下：,arrayexp1expn,int a1010 ,y,i=2; ai+26=20; y=ai+26*100/30; a1011=34;,對(duì)4行6列的元素賦值。,參加表達(dá)式運(yùn)算。,C語言不作下標(biāo)檢查，語法正確，但使用危

14、險(xiǎn)，可能造成程序的錯(cuò)誤！,整型表達(dá)式。,5.二維數(shù)組的應(yīng)用,【例4-5】下三角矩陣。,/* example 4-5 下三角矩陣 */ #include void main(void) int i,j; int a44; for(i=0;i=j) aij = 1; /* 下三角 */ else aij = 0; /* 上三角 */ for(i=0;i4;i+), for(j=0;j4;j+) printf(“%4d”,aij); /* 輸出數(shù)列 */ printf(“n”); /* 換行 */ ,【例4-6(a)】二維數(shù)組的轉(zhuǎn)置 。,/* example 4-6(a)二維數(shù)組的轉(zhuǎn)置 */ #in

15、clude void main(void) int i,j; int a33=1,2,3,4,5,6,7,8,9; /* 定義原數(shù)組 */ int b33; /* 定義新數(shù)組 */ for(i=0;i3;i+) /* 外循環(huán)遍歷行 */ for(j=0;j3;j+) /* 內(nèi)循環(huán)遍歷列 */ bij = aji ; /* 計(jì)算新元素 */ for(i=0;i3;i+) for(j=0;j3;j+) printf(“%4d,aij); /* 輸出原數(shù)組 */ printf(“n”); /* 換行 */, printf(“n”); /* 換行 */ for(i=0;i3;i+) for(j=0;j

16、3;j+) printf(%4d,bij); /* 輸出新數(shù)組 */ printf(“n”); /* 換行 */ ,/* example 4-6(b) 二維數(shù)組的轉(zhuǎn)置 */ #include void main(void) int i,j,t; int a33=1,2,3,4,5,6,7,8,9; /* 定義原數(shù)組 */ for(i=0;i3;i+) for(j=0;j3;j+) printf(%4d,aij); /* 輸出原數(shù)組 */ printf(n); /* 換行 */ for(i=0;i3;i+) /* 外循環(huán)遍歷行 */ for(j=0;ji;j+) /* 注意內(nèi)循環(huán)范圍 */ t

17、= aij ; /* 互換元素 */ aij = aji;,【例4-6(b)】,aji = t; for(i=0;i3;i+) for(j=0;j3;j+) printf(%4d,aij); /* 輸出新數(shù)組 */ printf(n); /* 換行 */ ,4.4 字 符 數(shù) 組,C語言沒有字符串變量，可以定義字符數(shù)組，每個(gè)元素存放一 個(gè)字符，從而達(dá)到存放字符串的目的。,字符數(shù)組的說明,char charrayconst exp1const expn,; char a10,b212;,字符數(shù)組的初始化,一維數(shù)組賦初值,char str16= h, e, l, l, o,0; char str2

18、 =”hello ”;,用單個(gè)字符對(duì)每一個(gè)元素賦值。,用字符串對(duì)數(shù)組賦初值。,可以指定長(zhǎng)度，也可不指定長(zhǎng)度。,系統(tǒng)會(huì)在字串的結(jié)尾加0，表示字符串結(jié)束。因此，說明數(shù)組 時(shí)，長(zhǎng)度指定應(yīng)至少比實(shí)際長(zhǎng)度大1，保證賦初值正確。,0,存儲(chǔ)結(jié)構(gòu)：,h,e,l,l,o,0,二維數(shù)組賦初值,二維數(shù)組的每一行可以存放一個(gè)字符串。,char str36=”wang”,”zhang”,”liu”;,str數(shù)組在內(nèi)存中的首地址。,存儲(chǔ)結(jié)構(gòu),字符數(shù)組的輸入輸出,格式輸入輸出函數(shù),輸出： for(i=0;iSTRLEN;i+) printf(“%c”,str i ); /*通過循環(huán)輸出各元素*/ printf(”%s”,s

19、tr); /*用字符串形式輸出*/,輸入： scanf(”%s”,str); /*用字符串輸入整個(gè)數(shù)組*/,用scanf函數(shù)輸入時(shí)space作為輸入的分隔符，因此輸入帶空格 的字符串，會(huì)造成輸入不全。,char a20; scanf(”%s”,a); 輸入：China Anhui Hefei 結(jié)果a數(shù)組的內(nèi)容是：China0,為了解決這個(gè)問題，系統(tǒng)定義如下專用于字符數(shù)組的i/o函數(shù)。,gets( )字符串輸入函數(shù),用法：,char str 80； gets(str)；,作用： 讀入一個(gè)以換行符為終結(jié)符的字符串到str中，用0代替換行符。,數(shù)組名作為函數(shù)的參數(shù)。,puts( )字符串輸出函數(shù),用

20、法：,char string =”China”; puts(string);,數(shù)組名作為函數(shù)的參數(shù)。,作用： 輸出以NULL 即0結(jié)尾的字符串string，自動(dòng)加上換行符。,【例4-7】用格式符%c逐個(gè)輸入和輸出示例。,/* example 4-7 用格式符c逐個(gè)輸入和輸出 */ #include void main(void) int i; char a12; for(i=0;i12;i+) scanf(%c, ,【例4-8】用格式符s整體輸入和輸出示例。,/* example 4-8 用格式符s整體輸入和輸出 */ #include void main(void) char a12; sc

21、anf(%s,a); /* 輸入a數(shù)組元素 */ printf(“%s”,a); /* 輸出a數(shù)組元素 */ printf(n); ,【例4-9】字符輸入輸出舉例,#include void main(void) char str80; int i; gets(str); for(i=0 ; str i !=0; i+) if(stri=a ,判斷字符串結(jié)束。,常用的字符處理函數(shù),C語言定義了一系列的字符處理函數(shù)用于字符串的處理，該類 函數(shù)的原型定義在string.h中。因此，在使用該類函數(shù)時(shí)，應(yīng)在程 序的開始處，加#include ,字符串拷貝函數(shù)strcpy(str1,str2),作用：將

22、str2拷貝到str1中。,用法： char str110, str2 =”Computer”; strcpy(str1,str2); /*str1的內(nèi)容是“Computer”*/ strcpy(str2,”Program”); /*str2的內(nèi)容是“Program”*/,說明：,str1的長(zhǎng)度要足夠長(zhǎng)； str1只能是字符數(shù)組名，str2可以是字符數(shù)組或字符串常量。,字符串連接函數(shù)strcat(str1, str2),作用：將str2連接到str1后（去掉str1的0）。,用法： char str115=“Anhui ”, str2 =”Hefei”; strcat(str1,str2);

23、puts(str1); /*輸出結(jié)果為 Anhui Hefei */,說明：,str1的長(zhǎng)度要足夠長(zhǎng)； str1只能是字符數(shù)組名，str2可以是字符數(shù)組或字符串常量。,測(cè)試字符串長(zhǎng)度函數(shù)strlen(str),作用：測(cè)試字符串的實(shí)際長(zhǎng)度。函數(shù)運(yùn)算得到整型值，該值是 字符串的長(zhǎng)度！,int iLenStr; char str =“China”; iLenStr=strlen(str); printf(“%d”,iLenStr);,結(jié)果？,字符串的比較 strcmp（str1，str2）,作用：對(duì)str1和str2 進(jìn)行逐位無符號(hào)字符（ASCII碼）比較， 直到對(duì)應(yīng)位字符能夠確定關(guān)系或到串尾為止。

24、返回整型比較結(jié)果。,字符的數(shù)值關(guān)系也就是字符的ASCII碼值的數(shù)值關(guān)系。,比較結(jié)果如下：,char str1 =”abcd”; char str2 =“abcd”; int iRe1,iRe2,iRe3; iRe1=strcmp(str1,”abdc”); iRe2=strcmp(str1,str2); iRe3=strcmp(”abcde”,str2);,abcd,abdc,c,d,c-d -1 結(jié)果小于0。,strlwr(str)將str中的大寫字母轉(zhuǎn)換成小寫字母。,strupr(str)將str中的小寫字母轉(zhuǎn)換成大寫字母,#include #include void main(void)

25、 char str1 =c programming! 123,str2=Computer; strlwr(str2); strupr(str1); puts(str1); puts(str2); ,C PROGRAMMING! 123 computer,【例4-10】字符處理函數(shù)示例1,/* example 4-10 字符處理函數(shù) */ #include #include void main(void) int k; char a20=Hello; char b20=world; char c20; k = strlen(a); /* 測(cè)a串長(zhǎng)度 */ printf(k=%dn,k); pri

26、ntf(“%d n”,strcmp(a,b); /* 比較a串和b串 */ strcat(a,b); /* 連接b串到a串 */ strcpy(c,b); /* 復(fù)制b串到c串 */ puts(a); /* 輸出a串 */ puts(b); /* 輸出b串 */ puts(c); /* 輸出c串 */ ,【例4-11】從鍵盤任意輸入5個(gè)學(xué)生的姓名，找出按ASCII碼的順序排在最前面的學(xué)生姓名。,/* example 4-11 找出排在最前面的學(xué)生姓名 */ #include #include void main(void) int i; char name20,minname20; print

27、f(please enter 1 name:); gets(name); /* 輸入第1個(gè)姓名 */ strcpy(minname,name); /* 設(shè)第1個(gè)姓名為最前面的姓名 */ for (i=2;i=5;i+) printf(please enter %d name:,i); gets(name); /* 輸入第i個(gè)姓名 */ if(strcmp(name,minname)0) /* 比較第i個(gè)姓名 */ strcpy(minname,name); /* 修正最前面的姓名 */ puts(minname); /* 輸出最前面的學(xué)生姓名 */ ,例：統(tǒng)計(jì)一行文字中大寫字母、小寫字母及數(shù)字

28、的個(gè)數(shù)。,#include #include void main(void) char str80; int i, iAnum=0, ianum=0,i0num=0; gets(str); for(i=0; i=A ,4.5 數(shù)組的應(yīng)用舉例,數(shù)組是同類型數(shù)據(jù)的集合。便于整體處理數(shù)據(jù)，數(shù)組操作的主 要算法有：,求極值 排序 查找 4.倒序,求極值及其位置,算法演示,一維數(shù)組的極值,#include void main(void) int a10=1,6,-2,5,4,32,47,-66,13,14; int iMax, iPos, i; iPos=0; iMax=a0; for(i=1; iiM

29、ax) iMax = ai; iPos = i; printf(“Max=%5d Position=%5d”,iMax,iPos); ,假定最大值及其位置。,循環(huán)比較,當(dāng)前元素比最大值大，將其 賦值為新的最大值并記錄其位置。,二維數(shù)組求極值,#include void main(void) float a34= 1.0, 3.0, 5.2, 7.4, 4.6, 5.5, 4.2, 1.2, 10.5, 0.23,1.3, 0.5; int i, j, iRow=0,iCol=0; for(i=0; i3; i+) for(j=0;j4;j+) if(aijaiRowiCol) iRow = i

30、; iCol = j; printf(”%f7.2,iRow%5d,iCol%5d”,aiRowiCol,iRow,iCol); ,假定最小值的位置。,二重循環(huán)遍歷所有元素,比較求最小值，記錄其位置。,/* example 4-12 計(jì)算最高分 */ #include void main(void) int i,kmax; float math10,maxmath; printf(please enter:); for(i=0;i10;i+) /* 循環(huán) */ scanf(“%f”,i+) /* 循環(huán)依次與后面的數(shù)比較 */,【例4-12】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，由鍵盤輸入，問最高分是多少？

31、, if(mathi maxmath) /* 如果后面的數(shù)大于假設(shè)的最大 */ kmax = i; /* 修改位置 */ maxmath = mathi; /* 修改最大 */ printf(k=%d,max=%fn,kmax,maxmath); /* 輸出 */ ,【例4-13】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，由鍵盤輸入，問最低分是多少？解題分析：解決了最高分問題，不能發(fā)現(xiàn)，只要將比賽規(guī)則，稍加修改即可。找最高分是找分?jǐn)?shù)高的，而找最低分是找分?jǐn)?shù)低的，將上述代碼4-12中的大于號(hào)改為小于號(hào)即可，當(dāng)然表示最小數(shù)和其位置的變量名也應(yīng)作適當(dāng)?shù)男薷?如最小數(shù)用minmath表示、最小數(shù)位置用kmin表示)，

32、在此不再敘述代碼。,/* example 4-14 計(jì)算最高分和最低分 */ #include void main(void) int i,kmax,kmin; float math10,maxmath,minmath; printf(please enter:); for(i=0;i10;i+) /* 循環(huán) */ scanf(“%f”,i+) /* 循環(huán)依次與后面的數(shù)比較 */,【例4-14】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，由鍵盤輸入，問最高分和最低分各是多少？, if(mathi maxmath) /* 如果后面的數(shù)大于假設(shè)的最大 */ kmax = i; maxmath = mathi; /*

33、 修改最大 */ else if(mathi minmath) /* 如果后面的數(shù)小于假設(shè)的最小 */ kmin = i; minmath = mathi; /* 修改最小 */ printf(kmax=%d,max=%fn,kmax,maxmath);/* 輸出最大 */ printf(kmin=%d,min=%fn,kmin,minmath);/* 輸出最小 */ ,/* example 4-15 計(jì)算最高分 */ #include void main(void) int i,j,k1max,k2max; float score103,maxsco; printf(please enter

34、:); for(i=0;i10;i+) /* 循環(huán) */ for(j=0;j3;j+) scanf(%f,i+) /* 外循環(huán)遍歷行 */,【例4-15】已知10個(gè)學(xué)生的數(shù)學(xué)、物理、化學(xué)成績(jī)，由鍵盤輸入，問最高分是多少？, for(j=0;j maxsco) /* 如果后面的數(shù)大于假設(shè)的最大 */ k1max = i; /* 修改位置 */ k2max = j; maxsco = scoreij; /* 修改最大 */ printf(k1=%d,k2=%d,max=%fn,k1max,k2max,maxsco); ,查 找,查找是在一組數(shù)中，尋找一個(gè)特定的數(shù)，并顯示結(jié)果。,順序查找,順序查找算

35、法：構(gòu)造循環(huán)，使循環(huán)的變量遍歷數(shù)組每個(gè)元素的 下標(biāo)。循環(huán)的過程中讓特定的數(shù)和每個(gè)元素比較，相等則表示找到 該數(shù)，并輸出其下標(biāo)（位置）。,程序設(shè)計(jì)中標(biāo)志的設(shè)置和應(yīng)用：,在程序設(shè)計(jì)中，經(jīng)常要記錄一些狀態(tài)，作為判斷的條件。因此 需要在程序中設(shè)置一些標(biāo)志，通常標(biāo)志是整型變量。,如查找問題，可以先設(shè)置一個(gè)整型變量iFlag=0表示沒有找到， 在查找的過程中一旦找到后，將iFlag賦值為1，結(jié)束查找后，可以 由iFlag值所代表的邏輯狀態(tài)，確定是否已找到特定的數(shù)。,標(biāo)志設(shè)置框圖,int iFlag;,iFlag=0;,是否找到?,iFlag=1;,yes,no,順序查找程序,#include void m

36、ain(void) int i,j,iFlag,a10=4,3,5,1,10,12,2,6,7,9; iFlag=0; scanf(“%d”, ,設(shè)置標(biāo)志為沒找到。,循環(huán)遍歷所有元素,比較設(shè)置標(biāo)志輸出位置。,chp4ex7,/* example 4-16 順序查找 */ #include #include void main(void) int i; int flag=0; /* 設(shè)置標(biāo)志 */ float math10=85,84,75,74,92,90,68,55,66,94; float score; printf(“please enter:”); /* 輸入待查找數(shù)據(jù) */ scan

37、f(%f, /* 循環(huán)繼續(xù)向后進(jìn)行 */,【例4-16】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，由鍵盤任意輸入1個(gè)成績(jī)，查找是否有此成績(jī)。, if(flag=1) printf(%f in %dn,score,i); /* 輸出找到的位置 */ else printf(not found n); /* 輸出沒有找到 */ ,折半查找適用于在有序數(shù)組中查找,在一個(gè)有序的一維數(shù)組中查找某一個(gè)數(shù)。已知某數(shù)組按升序排 列，給定一個(gè)數(shù)，找出該數(shù)在數(shù)組中的位置。 可以通過將區(qū)間折半，快速縮小查找區(qū)間，提高效率！,折半查找算法演示,/* example 4-17 折半查找 */ #include #include voi

38、d main(void) int low,high,mid; int flag=0; /* 設(shè)置標(biāo)志 */ float math10=55,65,68,72,75,83,86,88,90,95; /* 有序表 */ float score; printf(“please enter:”); /* 輸入待查找數(shù)據(jù) */ scanf(%f, /* 修改標(biāo)志 */ else if(scoremathmid),【例4-17】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，而且已經(jīng)按由小到大的順序排列，由鍵盤任意輸入1個(gè)成績(jī)，查找是否有此成績(jī)。,high = mid-1; /* 縮到前一半，修改上界 */ else low

39、= mid+1; /* 縮到后一半，修改下界 */ while( low=high /* 輸出沒有找到 */ ,算法的效率,無論是選擇排序，還是冒泡排序其循環(huán)次數(shù)相同。 外層循環(huán)i從0到MAX-1 內(nèi)層循環(huán)j從i+1到MAX,總次數(shù)： r=1+2+n-1 n*n/2, n為數(shù)組元素個(gè)數(shù)。,問 題：400個(gè)元素求前十名，如何高效率地排序？,方法一：對(duì)400個(gè)元素排完序后，取前10個(gè)。次數(shù)為80000次。,方法二：選擇10個(gè)最大值。次數(shù)為4000次。,假如一次循環(huán)需要1ms 方法一需要80s 方法二需要4s,如何構(gòu)造400取前十名的算法？,折半查找程序,#include void main(voi

40、d) int iTop,iBot,iMid,iS,iFlag,a10=1,2,3,5,6,8,9,10,11,12; iFlag=0; iTop=0; iBot=9; scanf(“%d”, ,初始化查找標(biāo)志及頂、底。,查找循環(huán),折半。,找到。,沒找到，調(diào)整iTop或iBot,chp4ex8, 排 序,排序的概念,排序是將一組隨機(jī)排放的數(shù)按下標(biāo)順序從大到小或從小到大重 新排列。,1 ，5，4，6，7，9,9，7，6，5，4，1,1，4，5，6，7，9,降序,升序,冒泡排序算法,冒泡排序算法演示,冒泡排序程序如下：,#include void main(void) int i, j, a10=4

41、,3,5,1,10,12,2,6,7,9, iTemp; for(i=0; i9 ;i+) for( j=i+1;j10;j+) if(aiaj) iTemp=a i ; a i =a j ; a j =iTemp; for(i=0;i10; i+) printf(”%4d”,ai); ,外層循環(huán)i變化,內(nèi)層循環(huán)j變化,比較交換,chp4ex5,/* example 4-18 冒泡排序 */ #include void main(void) int i,j; float math10,temp; printf(please enter:); for(i=0;i mathj+1) temp =

42、mathj; mathj = mathj+1; mathj+1 = temp; /* 交換 */ for(i=0;i10;i+) /* 循環(huán) */ printf(%5.1f ,mathi); /* 輸出 */ ,【例4-18】已知10個(gè)學(xué)生的數(shù)學(xué)成績(jī)，對(duì)其按升序排列。,思考題,升序的條件如何構(gòu)造？,聯(lián)合排序問題 已知一個(gè)班有36個(gè)同學(xué)，a數(shù)組存放一門課的成績(jī)，m數(shù)組存放 其學(xué)號(hào)。要求將成績(jī)從大到小排序。,提示：應(yīng)考慮的問題是當(dāng)a數(shù)組元素比較交換時(shí)，m數(shù)組如何處 理？,a 5 89.5 m 5 1005 a 7 90.0 m 7 1007,被動(dòng)排序方。,選擇排序,冒泡排序在內(nèi)層循環(huán)的比較中，滿足

43、條件的每次都需要交換。 其中一些交換是無效的，交換算法會(huì)占用系統(tǒng)時(shí)間，從而降低算法 效率。,選擇排序算法的基本思路，每輪排序?qū) i 假定為極值，每次 在a i 到 aMAX中找出個(gè)極值，記錄其位置，最后讓極值位置的 元素與a i 交換。 選擇排序保證每輪排序只有一次交換，且為有效的交換！,選擇排序算法演示,選擇排序程序,#include void main(void) int i, j,iMax,a10=4,3,5,1,10,12,2,6,7,9, iTemp; for(i=0; i9 ;i+) iMax=i; for( j=i+1;j10;j+) if(aiMaxaj)iMax=j; if

44、(iMax!=i) iTemp=ai; ai=aiMax; aiMax=iTemp; for(i=0;i10; i+) printf(”%4d”,ai); ,排序循環(huán),假定最大值位置。,循環(huán)比較找出最大值的位置。,與本次比較的第一個(gè)元素交換。,chp4ex6,升序如何構(gòu)造？,/* example 4-19 選擇排序 */ #include void main(void) int i,j,k; float math10,temp; printf(please enter:); for(i=0;i mathj) k = j; /* 修正最小數(shù)位置 */ if(k!=i),【例4-19】已知10個(gè)學(xué)

45、生的數(shù)學(xué)成績(jī)，利用選擇排序?qū)ζ浒瓷蚺帕小? temp = mathi; mathi = mathk; mathk = temp; /* 將最小數(shù)交換到前面 */ for(i=0;i10;i+) /* 循環(huán) */ printf(%5.1f ,mathi); /* 輸出 */ ,4. 倒序,【例4-20】利用循環(huán)以實(shí)現(xiàn)反向輸出。,/* example 4-20 反向輸出 */ #include void main(void) int i; int math10; printf(please enter:); for(i=0;i=0;i-) /* 循環(huán) */ printf(%d ,mathi);

46、/* 從后向前輸出 */ ,【例4-21】用另一個(gè)數(shù)組 。,/* example 4-21 利用輔助數(shù)組 */ #include void main(void) int i; int math110,math210; printf(please enter:); for(i=0;i10;i+) /* 循環(huán) */ scanf(%d, /* 從前向后輸出 */ ,【例4-21】就地逆置 。,/* example 4-22 就地逆置 */ #include void main(void) int i,temp; int math10; printf(please enter:); for(i=0;i

47、10;i+) /* 循環(huán) */ scanf(“%d”, /* 從前向后輸出 */ ,4.6 算法與效率,通過上述一些例子，可以發(fā)現(xiàn)同一個(gè)問題往往存在幾種不同的算法，多種算法都可以解決問題，每一種算法都有它的特點(diǎn)，當(dāng)然每一種算法都有它的開銷，究竟如何評(píng)價(jià)這些算法的好壞呢？,算法首先必須是正確的，即算法都能解決問題，得到了正確的結(jié)果，除此之外，還需考慮以下幾個(gè)方面的問題：,（1）執(zhí)行算法所耗費(fèi)的時(shí)間； （2）執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間； （3）算法應(yīng)該易于理解、易于調(diào)試、易于維護(hù)等等。,1.算法所耗費(fèi)的時(shí)間,一個(gè)算法所耗費(fèi)的時(shí)間應(yīng)該是算法中每條語句的執(zhí)行時(shí)間之和，而每條語句的執(zhí)行時(shí)間是該語句的執(zhí)行次

48、數(shù)與該語句的執(zhí)行時(shí)間之乘積。每條語句的執(zhí)行時(shí)間與所使用的計(jì)算機(jī)系統(tǒng)有關(guān)，同樣的語句在不同的計(jì)算機(jī)系統(tǒng)中其執(zhí)行時(shí)間不一定相同，這給精確度量算法的時(shí)間帶來困難。,為此我們拋開具體的軟硬件環(huán)境，假設(shè)每一條語句的執(zhí)行時(shí)間是相同的，為一個(gè)標(biāo)準(zhǔn)單位時(shí)間，這樣算法的執(zhí)行時(shí)間就是所有語句的執(zhí)行次數(shù)之和,一條語句的執(zhí)行次數(shù)與其是否在循環(huán)中以及循環(huán)的次數(shù)有關(guān)。 可見語句的執(zhí)行次數(shù)在很大程度上依賴于循環(huán)的次數(shù)，降低循環(huán)的次數(shù)以及循環(huán)的層數(shù)就可以降低算法的時(shí)間。,2.算法所耗費(fèi)的空間,一個(gè)算法所耗費(fèi)的存儲(chǔ)空間來自于3個(gè)方面：,（1）算法自身在計(jì)算機(jī)系統(tǒng)中占有的空間； （2）算法運(yùn)行過程中各種數(shù)據(jù)占有的空間； （3）算

49、法運(yùn)行過程中所需要的輔助空間。,算法運(yùn)行過程中所需要的輔助空間是度量算法空間性能的主要指標(biāo)。,3.算法的可讀性、可調(diào)性、可維護(hù)性,算法的可讀性、可調(diào)性、可維護(hù)性是衡量現(xiàn)代程序性能的一個(gè)重要的指標(biāo)，一個(gè)結(jié)構(gòu)清晰、接口簡(jiǎn)單、易于閱讀的程序，不僅大大減少程序的調(diào)試和維護(hù)成本，也增加程序的穩(wěn)定性和可靠性。,【例4-23】求1100以內(nèi)的偶數(shù)之和。 以下列出3種解法，都可以解決1100以內(nèi)的偶數(shù)之和。,/* example 4-23(a) 求1-100以內(nèi)的偶數(shù)之和 */ #include void main(void) int i; int sum=0; /* 初始化和 */ for(i=2; i=1

50、00; i=i+2) /* 循環(huán)變量的變化就是偶數(shù) */ sum = sum+i; /* 求和 */ printf(sum=%d ,sum); /* 輸出偶數(shù)之和 */ ,/* example 4-23(b) 求1-100以內(nèi)的偶數(shù)之和 */ #include void main(void) int i; int sum=0; /* 初始化和 */ for(i=1; i=100; i=i+1) /* 循環(huán)變量的變化是所有數(shù) */ if (i%2=0) sum = sum+i; /* 求偶數(shù)之和 */ printf(sum=%d ,sum); /* 輸出偶數(shù)之和 */ ,/* example 4-23(c) 求1-100以內(nèi)的偶數(shù)之和 */ #include void main(void) int i; int sum=0; /* 初始化和 */ for(i=1; i=100; i=i+1) /* 循環(huán)變量的變化是所有數(shù) */ if (i%2!=0) continue; /* 奇數(shù)跳過 */ else sum = sum+i; /* 求偶數(shù)之和 */ printf(sum=%d ,sum); /* 輸出偶數(shù)之和 */ ,