第四章 數(shù) 組,在實際的應用中，經(jīng)常會遇到某些類型相同并相互具有聯(lián)系的 數(shù)據(jù)。該類數(shù)據(jù)，經(jīng)常要作相關(guān)的處理。如，一個班30個人的一門 課程的成績，求平均成績、最高或最低成績。處理這類數(shù)據(jù)的最好 辦法是將其定義成為一個具有共同特征的集合，這種同類型相關(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ù)組用一個名字作為標識。為區(qū)分各元素，每個元素有一個用 整型表示的序號，稱之為下標。下標可以有多個，下標的個數(shù)稱為 數(shù)組的維數(shù)。,如：十個整型變量 k0,k1, k9,一個下標。,數(shù)組名。,三個學生三門課程的成績,97.5 80.5 94.5 76.5 81.4 90.0 60.0 64.5 75.0,學號 0 1 2,0 1 2 課程,下標一：行,下標二：列,數(shù)組元素：a11,/* example 4-1(b) 計算平均成績 */ #include void main(void) int i; float math,ave; ave = 0.0; /* 平均成績初值為0 */ for(i=0;i<10;i+) /* 循環(huán)10次 */ scanf(%f, ,【例4-1】學生分數(shù)的處理問題。有10個學生參加數(shù)學考試，考試成績由鍵盤輸入，計算平均成績。,/* example 4-1(b) 計算平均成績 */ #include void main(void) int i; float math,ave; ave = 0.0; /* 平均成績初值為0 */ for(i=0;i=ave) printf(%fn,math); /* 大于平均成績則打印 */ ,【例4-1(b)】,/* example 4-1(c) 計算平均成績 */ #include void main(void) int i; float math10,ave; ave = 0.0; /* 平均成績初值為0 */ for(i=0;i=ave) printf(%fn,mathi); /* 大于平均成績則打印 */ ,【例4-1(c)】,數(shù)組必須先說明后使用。說明的目的如下：,說明數(shù)組的名字（標識）。 說明數(shù)組的類型。 說明數(shù)組的維數(shù)。 確定各維下標的變化范圍。,編譯系統(tǒng)將根據(jù)說明，開辟內(nèi)存單元按特有的順序和相應的類 型為各元素分配內(nèi)存單元。,4.2 一維數(shù)組,一維數(shù)組的說明,說明方式：,type array1常量表達式, , arrayn常量表達式；,類型說明符，根據(jù)需要可加修飾說明。說明數(shù)組的類型。,數(shù)組名，用標識符命名。,用 包含的常量表達式。數(shù)組的下標從0變化到常量達式的值減一。,int id5, iyear10; float fScore36;,當說明數(shù)組后，編譯時系統(tǒng)會根據(jù)定義的類型分配連續(xù)的一段 內(nèi)存單元給數(shù)組的各元素。,id0,id1,id2,id3,id4,系統(tǒng)為數(shù)組分配的連續(xù)內(nèi)存單元，每個單元占兩個BYTE。首地址用數(shù)組名id表示。,2. 一維數(shù)組的引用,數(shù)組是一組數(shù)，它們公用一個數(shù)組名，這是它們公有的屬性，但它們在數(shù)組中的位置不同，這是它們私有的屬性，為表明數(shù)組中的一個元素，既要指出其來自于哪個數(shù)組，這就需要數(shù)組名；又要聲明其在這個數(shù)組中的位置，這就需要下標 。,一維數(shù)組中元素引用的一般形式為： 數(shù)組名下標值,說明： 下標通常為整型，如果為實型，系統(tǒng)自動取整； 下標常常巧妙的和循環(huán)變量相結(jié)合，隨著循環(huán)變量的變化而變化，可以達到事半功倍的效果； C語言不做下標越界的檢查，即語法上對越界的下標不報錯。,3. 一維數(shù)組的存儲,計算機系統(tǒng)中有著大量的存儲單元，為區(qū)別各個存儲單元，每一個存儲單元都有一個唯一的代表這個存儲單元的地址，就好像我們每一個人都有一個唯一的代表自己的身份證號一樣。計算機系統(tǒng)中，存儲單元的地址的編碼規(guī)則是線性的，以十六進制表示，并且從0開始計數(shù)，因此存儲單元的地址為：0、1、2、.9、A、B、C、D、E、F、10H、. .,如果說明的是一個數(shù)組，如：int math10; 計算機開辟20個地址連續(xù)的存儲單元（TC環(huán)境下整型占2個字節(jié)，共有10個數(shù)組元素），用于存放數(shù)組中的10個數(shù)組元素，且這20個存儲單元的首地址標記為：數(shù)組名math或 /*說明數(shù)組，同時初始化全部元素。*/,float fValue10=1.0,2.0,3.0; /*說明數(shù)組，給部分元素初值，其余元素為0。*/,unsigned a =0 x0000,0 x0001,0 x0002; /*當數(shù)組元素全部賦初值時，可以不指定長度*/,/* 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;i<5;i+) /* 循環(huán)5次 */ printf(a%d=%d ,i,ai); /* 輸出a數(shù)組元素 */ printf(n); /* 換行 */ for(i=0;i<5;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;i<5;i+) /* 循環(huán)5次 */ printf(c%d=%d ,i,ci); /* 輸出c元素，注意有危險 */ printf(n); /* 換行 */ ,5.一維數(shù)組的應用,【例4-3】兔子繁殖問題。,/* example 4-3 Fibonacci數(shù)列 */ #include void main(void) int month; int f13=1,1; for(month=2;month<13;month+) /* 循環(huán)遞推 */ fmonth = fmonth-1+fmonth-2; /* 計算數(shù)列 */ for(month=0;month<13;month+) printf(%d ,fmonth); /* 輸出數(shù)列 */ ,【例4-4】由鍵盤輸入n個學生（設人數(shù)不超過50人）的數(shù)學成績，分別統(tǒng)計優(yōu)、良、中、及格、不及格的人數(shù)。,/* example 4-4 分別統(tǒng)計成績 */ #include 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)計 */ 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個學生一門課程的平均分，并輸出低于平均成績的分數(shù)。,#include void main(void) float fScore10,aver=0; int i; for(i=0;i<10;i+) scanf(“%f”, ,說明數(shù)組。,循環(huán)輸入各元素的值并累加。,循環(huán)判斷條件，滿足條件輸出。,4.3 二 維 數(shù) 組,在實際應用中，經(jīng)常會遇到一些用多維索引的數(shù)據(jù)。如：四個 學生三門課的成績?？梢杂孟卤肀硎荆?顯然，該表的每一項需要有兩個索引項。表現(xiàn)為數(shù)組的兩個下 標。超過一個下標的數(shù)組稱為多維數(shù)組。,行：代表某個學生。,列：代表某門課程。,二維數(shù)組的說明,說明方式： type array常量表達式1常量表達式n,；,n個整型常量表達式,數(shù)組元素的個數(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,下 標 為 0 的 行,總原則：最后一個下標先變化，變化一個周 期后，倒數(shù)第二個開始變化，如此類推。,a為數(shù)組在內(nèi)存中的首地址。,int b234;,內(nèi)存中的排列？,二維數(shù)組的初始化,數(shù)組可以在說明時初始化。,全部賦初值,int a23=1,2,3,4,5,6;,下標為0的一行,下標為1的一行,int b23=1,2,3,4,5,6；,按內(nèi)存順序賦初值。,部分賦初值,int a23= 1 , 2 ；,0行的0列的元素賦初值。0行其余值為0。,int a23=1,2；,對全體數(shù)組元素賦初值，第一維下標可以省略。,int a 3=1, 2, 3, 4, 5, 6;,二維數(shù)組元素的引用,數(shù)組定義后，具備簡單變量的一切性質(zhì)，可以作為表達式的運 算對象，也可以被賦值。引用時，只能引用數(shù)組元素，方式如下：,arrayexp1expn,int a1010 ,y,i=2; ai+26=20; y=ai+26*100/30; a1011=34;,對4行6列的元素賦值。,參加表達式運算。,C語言不作下標檢查，語法正確，但使用危險，可能造成程序的錯誤！,整型表達式。,5.二維數(shù)組的應用,【例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;i<4;i+), for(j=0;j<4;j+) printf(“%4d”,aij); /* 輸出數(shù)列 */ printf(“n”); /* 換行 */ ,【例4-6(a)】二維數(shù)組的轉(zhuǎn)置 。,/* example 4-6(a)二維數(shù)組的轉(zhuǎn)置 */ #include void main(void) int i,j; int a33=1,2,3,4,5,6,7,8,9; /* 定義原數(shù)組 */ int b33; /* 定義新數(shù)組 */ for(i=0;i<3;i+) /* 外循環(huán)遍歷行 */ for(j=0;j<3;j+) /* 內(nèi)循環(huán)遍歷列 */ bij = aji ; /* 計算新元素 */ for(i=0;i<3;i+) for(j=0;j<3;j+) printf(“%4d,aij); /* 輸出原數(shù)組 */ printf(“n”); /* 換行 */, printf(“n”); /* 換行 */ for(i=0;i<3;i+) for(j=0;j<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;i<3;i+) for(j=0;j<3;j+) printf(%4d,aij); /* 輸出原數(shù)組 */ printf(n); /* 換行 */ for(i=0;i<3;i+) /* 外循環(huán)遍歷行 */ for(j=0;j<i;j+) /* 注意內(nèi)循環(huán)范圍 */ t = aij ; /* 互換元素 */ aij = aji;,【例4-6(b)】,aji = t; for(i=0;i<3;i+) for(j=0;j<3;j+) printf(%4d,aij); /* 輸出新數(shù)組 */ printf(n); /* 換行 */ ,4.4 字 符 數(shù) 組,C語言沒有字符串變量，可以定義字符數(shù)組，每個元素存放一 個字符，從而達到存放字符串的目的。,字符數(shù)組的說明,char charrayconst exp1const expn,; char a10,b212;,字符數(shù)組的初始化,一維數(shù)組賦初值,char str16= h, e, l, l, o,0; char str2 =”hello ”;,用單個字符對每一個元素賦值。,用字符串對數(shù)組賦初值。,可以指定長度，也可不指定長度。,系統(tǒng)會在字串的結(jié)尾加0，表示字符串結(jié)束。因此，說明數(shù)組 時，長度指定應至少比實際長度大1，保證賦初值正確。,0,存儲結(jié)構(gòu)：,h,e,l,l,o,0,二維數(shù)組賦初值,二維數(shù)組的每一行可以存放一個字符串。,char str36=”wang”,”zhang”,”liu”;,str數(shù)組在內(nèi)存中的首地址。,存儲結(jié)構(gòu),字符數(shù)組的輸入輸出,格式輸入輸出函數(shù),輸出： for(i=0;i<STRLEN;i+) printf(“%c”,str i ); /*通過循環(huán)輸出各元素*/ printf(”%s”,str); /*用字符串形式輸出*/,輸入： scanf(”%s”,str); /*用字符串輸入整個數(shù)組*/,用scanf函數(shù)輸入時space作為輸入的分隔符，因此輸入帶空格 的字符串，會造成輸入不全。,char a20; scanf(”%s”,a); 輸入：China Anhui Hefei 結(jié)果a數(shù)組的內(nèi)容是：China0,為了解決這個問題，系統(tǒng)定義如下專用于字符數(shù)組的i/o函數(shù)。,gets( )字符串輸入函數(shù),用法：,char str 80； gets(str)；,作用： 讀入一個以換行符為終結(jié)符的字符串到str中，用0代替換行符。,數(shù)組名作為函數(shù)的參數(shù)。,puts( )字符串輸出函數(shù),用法：,char string =”China”; puts(string);,數(shù)組名作為函數(shù)的參數(shù)。,作用： 輸出以NULL 即0結(jié)尾的字符串string，自動加上換行符。,【例4-7】用格式符%c逐個輸入和輸出示例。,/* example 4-7 用格式符c逐個輸入和輸出 */ #include void main(void) int i; char a12; for(i=0;i<12;i+) scanf(%c, ,【例4-8】用格式符s整體輸入和輸出示例。,/* example 4-8 用格式符s整體輸入和輸出 */ #include void main(void) char a12; scanf(%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ù)時，應在程 序的開始處，加#include ,字符串拷貝函數(shù)strcpy(str1,str2),作用：將str2拷貝到str1中。,用法： char str110, str2 =”Computer”; strcpy(str1,str2); /*str1的內(nèi)容是“Computer”*/ strcpy(str2,”Program”); /*str2的內(nèi)容是“Program”*/,說明：,str1的長度要足夠長； str1只能是字符數(shù)組名，str2可以是字符數(shù)組或字符串常量。,字符串連接函數(shù)strcat(str1, str2),作用：將str2連接到str1后（去掉str1的0）。,用法： char str115=“Anhui ”, str2 =”Hefei”; strcat(str1,str2); puts(str1); /*輸出結(jié)果為 Anhui Hefei */,說明：,str1的長度要足夠長； str1只能是字符數(shù)組名，str2可以是字符數(shù)組或字符串常量。,測試字符串長度函數(shù)strlen(str),作用：測試字符串的實際長度。函數(shù)運算得到整型值，該值是 字符串的長度！,int iLenStr; char str =“China”; iLenStr=strlen(str); printf(“%d”,iLenStr);,結(jié)果？,字符串的比較 strcmp（str1，str2）,作用：對str1和str2 進行逐位無符號字符（ASCII碼）比較， 直到對應位字符能夠確定關(guān)系或到串尾為止。返回整型比較結(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) 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); /* 測a串長度 */ printf(k=%dn,k); printf(“%d n”,strcmp(a,b); /* 比較a串和b串 */ strcat(a,b); /* 連接b串到a串 */ strcpy(c,b); /* 復制b串到c串 */ puts(a); /* 輸出a串 */ puts(b); /* 輸出b串 */ puts(c); /* 輸出c串 */ ,【例4-11】從鍵盤任意輸入5個學生的姓名，找出按ASCII碼的順序排在最前面的學生姓名。,/* example 4-11 找出排在最前面的學生姓名 */ #include #include void main(void) int i; char name20,minname20; printf(please enter 1 name:); gets(name); /* 輸入第1個姓名 */ strcpy(minname,name); /* 設第1個姓名為最前面的姓名 */ for (i=2;i<=5;i+) printf(please enter %d name:,i); gets(name); /* 輸入第i個姓名 */ if(strcmp(name,minname)<0) /* 比較第i個姓名 */ strcpy(minname,name); /* 修正最前面的姓名 */ puts(minname); /* 輸出最前面的學生姓名 */ ,例：統(tǒng)計一行文字中大寫字母、小寫字母及數(shù)字的個數(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ù)組的應用舉例,數(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; iiMax) iMax = ai; iPos = i; printf(“Max=%5d Position=%5d”,iMax,iPos); ,假定最大值及其位置。,循環(huán)比較,當前元素比最大值大，將其 賦值為新的最大值并記錄其位置。,二維數(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; i<3; i+) for(j=0;j<4;j+) if(aij<aiRowiCol) iRow = i; iCol = j; printf(”%f7.2,iRow%5d,iCol%5d”,aiRowiCol,iRow,iCol); ,假定最小值的位置。,二重循環(huán)遍歷所有元素,比較求最小值，記錄其位置。,/* example 4-12 計算最高分 */ #include void main(void) int i,kmax; float math10,maxmath; printf(please enter:); for(i=0;i<10;i+) /* 循環(huán) */ scanf(“%f”,i+) /* 循環(huán)依次與后面的數(shù)比較 */,【例4-12】已知10個學生的數(shù)學成績，由鍵盤輸入，問最高分是多少？, if(mathi maxmath) /* 如果后面的數(shù)大于假設的最大 */ kmax = i; /* 修改位置 */ maxmath = mathi; /* 修改最大 */ printf(k=%d,max=%fn,kmax,maxmath); /* 輸出 */ ,【例4-13】已知10個學生的數(shù)學成績，由鍵盤輸入，問最低分是多少？解題分析：解決了最高分問題，不能發(fā)現(xiàn)，只要將比賽規(guī)則，稍加修改即可。找最高分是找分數(shù)高的，而找最低分是找分數(shù)低的，將上述代碼4-12中的大于號改為小于號即可，當然表示最小數(shù)和其位置的變量名也應作適當?shù)男薷?如最小數(shù)用minmath表示、最小數(shù)位置用kmin表示)，在此不再敘述代碼。,/* example 4-14 計算最高分和最低分 */ #include void main(void) int i,kmax,kmin; float math10,maxmath,minmath; printf(please enter:); for(i=0;i<10;i+) /* 循環(huán) */ scanf(“%f”,i+) /* 循環(huán)依次與后面的數(shù)比較 */,【例4-14】已知10個學生的數(shù)學成績，由鍵盤輸入，問最高分和最低分各是多少？, if(mathi maxmath) /* 如果后面的數(shù)大于假設的最大 */ kmax = i; maxmath = mathi; /* 修改最大 */ else if(mathi < minmath) /* 如果后面的數(shù)小于假設的最小 */ kmin = i; minmath = mathi; /* 修改最小 */ printf(kmax=%d,max=%fn,kmax,maxmath);/* 輸出最大 */ printf(kmin=%d,min=%fn,kmin,minmath);/* 輸出最小 */ ,/* example 4-15 計算最高分 */ #include void main(void) int i,j,k1max,k2max; float score103,maxsco; printf(please enter:); for(i=0;i<10;i+) /* 循環(huán) */ for(j=0;j<3;j+) scanf(%f,i+) /* 外循環(huán)遍歷行 */,【例4-15】已知10個學生的數(shù)學、物理、化學成績，由鍵盤輸入，問最高分是多少？, for(j=0;j maxsco) /* 如果后面的數(shù)大于假設的最大 */ k1max = i; /* 修改位置 */ k2max = j; maxsco = scoreij; /* 修改最大 */ printf(k1=%d,k2=%d,max=%fn,k1max,k2max,maxsco); ,查 找,查找是在一組數(shù)中，尋找一個特定的數(shù)，并顯示結(jié)果。,順序查找,順序查找算法：構(gòu)造循環(huán)，使循環(huán)的變量遍歷數(shù)組每個元素的 下標。循環(huán)的過程中讓特定的數(shù)和每個元素比較，相等則表示找到 該數(shù)，并輸出其下標（位置）。,程序設計中標志的設置和應用：,在程序設計中，經(jīng)常要記錄一些狀態(tài)，作為判斷的條件。因此 需要在程序中設置一些標志，通常標志是整型變量。,如查找問題，可以先設置一個整型變量iFlag=0表示沒有找到， 在查找的過程中一旦找到后，將iFlag賦值為1，結(jié)束查找后，可以 由iFlag值所代表的邏輯狀態(tài)，確定是否已找到特定的數(shù)。,標志設置框圖,int iFlag;,iFlag=0;,是否找到?,iFlag=1;,yes,no,順序查找程序,#include void main(void) int i,j,iFlag,a10=4,3,5,1,10,12,2,6,7,9; iFlag=0; scanf(“%d”, ,設置標志為沒找到。,循環(huán)遍歷所有元素,比較設置標志輸出位置。,chp4ex7,/* example 4-16 順序查找 */ #include #include void main(void) int i; int flag=0; /* 設置標志 */ float math10=85,84,75,74,92,90,68,55,66,94; float score; printf(“please enter:”); /* 輸入待查找數(shù)據(jù) */ scanf(%f, /* 循環(huán)繼續(xù)向后進行 */,【例4-16】已知10個學生的數(shù)學成績，由鍵盤任意輸入1個成績，查找是否有此成績。, if(flag=1) printf(%f in %dn,score,i); /* 輸出找到的位置 */ else printf(not found n); /* 輸出沒有找到 */ ,折半查找適用于在有序數(shù)組中查找,在一個有序的一維數(shù)組中查找某一個數(shù)。已知某數(shù)組按升序排 列，給定一個數(shù)，找出該數(shù)在數(shù)組中的位置。 可以通過將區(qū)間折半，快速縮小查找區(qū)間，提高效率！,折半查找算法演示,/* example 4-17 折半查找 */ #include #include void main(void) int low,high,mid; int flag=0; /* 設置標志 */ float math10=55,65,68,72,75,83,86,88,90,95; /* 有序表 */ float score; printf(“please enter:”); /* 輸入待查找數(shù)據(jù) */ scanf(%f, /* 修改標志 */ else if(score<mathmid),【例4-17】已知10個學生的數(shù)學成績，而且已經(jīng)按由小到大的順序排列，由鍵盤任意輸入1個成績，查找是否有此成績。,high = mid-1; /* 縮到前一半，修改上界 */ else low = 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ù)組元素個數(shù)。,問 題：400個元素求前十名，如何高效率地排序？,方法一：對400個元素排完序后，取前10個。次數(shù)為80000次。,方法二：選擇10個最大值。次數(shù)為4000次。,假如一次循環(huán)需要1ms 方法一需要80s 方法二需要4s,如何構(gòu)造400取前十名的算法？,折半查找程序,#include void main(void) 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”, ,初始化查找標志及頂、底。,查找循環(huán),折半。,找到。,沒找到，調(diào)整iTop或iBot,chp4ex8, 排 序,排序的概念,排序是將一組隨機排放的數(shù)按下標順序從大到小或從小到大重 新排列。,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,3,5,1,10,12,2,6,7,9, iTemp; for(i=0; i<9 ;i+) for( j=i+1;j<10;j+) if(ai<aj) iTemp=a i ; a i =a j ; a j =iTemp; for(i=0;i<10; 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 = mathj; mathj = mathj+1; mathj+1 = temp; /* 交換 */ for(i=0;i<10;i+) /* 循環(huán) */ printf(%5.1f ,mathi); /* 輸出 */ ,【例4-18】已知10個學生的數(shù)學成績，對其按升序排列。,思考題,升序的條件如何構(gòu)造？,聯(lián)合排序問題 已知一個班有36個同學，a數(shù)組存放一門課的成績，m數(shù)組存放 其學號。要求將成績從大到小排序。,提示：應考慮的問題是當a數(shù)組元素比較交換時，m數(shù)組如何處 理？,a 5 89.5 m 5 1005 a 7 90.0 m 7 1007,被動排序方。,選擇排序,冒泡排序在內(nèi)層循環(huán)的比較中，滿足條件的每次都需要交換。 其中一些交換是無效的，交換算法會占用系統(tǒng)時間，從而降低算法 效率。,選擇排序算法的基本思路，每輪排序?qū) i 假定為極值，每次 在a i 到 aMAX中找出個極值，記錄其位置，最后讓極值位置的 元素與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; i<9 ;i+) iMax=i; for( j=i+1;j<10;j+) if(aiMax<aj)iMax=j; if(iMax!=i) iTemp=ai; ai=aiMax; aiMax=iTemp; for(i=0;i<10; i+) printf(”%4d”,ai); ,排序循環(huán),假定最大值位置。,循環(huán)比較找出最大值的位置。,與本次比較的第一個元素交換。,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個學生的數(shù)學成績，利用選擇排序?qū)ζ浒瓷蚺帕小? temp = mathi; mathi = mathk; mathk = temp; /* 將最小數(shù)交換到前面 */ for(i=0;i<10;i+) /* 循環(huán) */ printf(%5.1f ,mathi); /* 輸出 */ ,4. 倒序,【例4-20】利用循環(huán)以實現(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); /* 從后向前輸出 */ ,【例4-21】用另一個數(shù)組 。,/* example 4-21 利用輔助數(shù)組 */ #include void main(void) int i; int math110,math210; printf(please enter:); for(i=0;i<10;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<10;i+) /* 循環(huán) */ scanf(“%d”, /* 從前向后輸出 */ ,4.6 算法與效率,通過上述一些例子，可以發(fā)現(xiàn)同一個問題往往存在幾種不同的算法，多種算法都可以解決問題，每一種算法都有它的特點，當然每一種算法都有它的開銷，究竟如何評價這些算法的好壞呢？,算法首先必須是正確的，即算法都能解決問題，得到了正確的結(jié)果，除此之外，還需考慮以下幾個方面的問題：,（1）執(zhí)行算法所耗費的時間； （2）執(zhí)行算法所耗費的存儲空間； （3）算法應該易于理解、易于調(diào)試、易于維護等等。,1.算法所耗費的時間,一個算法所耗費的時間應該是算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)與該語句的執(zhí)行時間之乘積。每條語句的執(zhí)行時間與所使用的計算機系統(tǒng)有關(guān)，同樣的語句在不同的計算機系統(tǒng)中其執(zhí)行時間不一定相同，這給精確度量算法的時間帶來困難。,為此我們拋開具體的軟硬件環(huán)境，假設每一條語句的執(zhí)行時間是相同的，為一個標準單位時間，這樣算法的執(zhí)行時間就是所有語句的執(zhí)行次數(shù)之和,一條語句的執(zhí)行次數(shù)與其是否在循環(huán)中以及循環(huán)的次數(shù)有關(guān)。 可見語句的執(zhí)行次數(shù)在很大程度上依賴于循環(huán)的次數(shù)，降低循環(huán)的次數(shù)以及循環(huán)的層數(shù)就可以降低算法的時間。,2.算法所耗費的空間,一個算法所耗費的存儲空間來自于3個方面：,（1）算法自身在計算機系統(tǒng)中占有的空間； （2）算法運行過程中各種數(shù)據(jù)占有的空間； （3）算法運行過程中所需要的輔助空間。,算法運行過程中所需要的輔助空間是度量算法空間性能的主要指標。,3.算法的可讀性、可調(diào)性、可維護性,算法的可讀性、可調(diào)性、可維護性是衡量現(xiàn)代程序性能的一個重要的指標，一個結(jié)構(gòu)清晰、接口簡單、易于閱讀的程序，不僅大大減少程序的調(diào)試和維護成本，也增加程序的穩(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<=100; 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ù)之和 */ ,