1、第 章 數(shù)組,問題的引入,例：輸入10個(gè)學(xué)生某門學(xué)科的成績(jī),求平均成績(jī)。,1、當(dāng)讀入下一分?jǐn)?shù)時(shí)，前一分?jǐn)?shù)值是否還能找到？ 2、如何將低于平均成績(jī)的分?jǐn)?shù)打印出來？,在程序設(shè)計(jì)中存儲(chǔ)單個(gè)數(shù)據(jù)時(shí)，需要根據(jù)數(shù)據(jù)的類 型定義相應(yīng)的變量來保存。如存儲(chǔ)一個(gè)整數(shù)時(shí)需要定義 一個(gè)整數(shù)變量來保存，存儲(chǔ)一個(gè)實(shí)數(shù)時(shí)需要定義一個(gè)單 精度或雙精度變量來保存，存儲(chǔ)含有多個(gè)成分的一個(gè)記 錄數(shù)據(jù)時(shí)，需要定義該類型的一個(gè)結(jié)構(gòu)變量來保存。,若在程序設(shè)計(jì)中需要存儲(chǔ)同一數(shù)據(jù)類型的、彼此相 關(guān)的多個(gè)數(shù)據(jù)時(shí)，如存儲(chǔ)數(shù)學(xué)上使用的一個(gè)數(shù)列或一個(gè) 矩陣中的全部數(shù)據(jù)時(shí)，顯然采用定義簡(jiǎn)單變量的方法是 不行的，這就要求定義出能夠同時(shí)存儲(chǔ)多個(gè)值的變量，

2、 這種變量在程序設(shè)計(jì)中稱為數(shù)組（相同類型的若干個(gè)元 素所組成的有序集合）。,在實(shí)際應(yīng)用中，一組相關(guān)的數(shù)據(jù)之間可能存在著一 維關(guān)系，也可能存在著二維關(guān)系，等等。如下表：,概述,C+數(shù)據(jù)類型： 基本類（簡(jiǎn)單類）字符型/整型/實(shí)型/枚舉型 構(gòu)造類（組合類）數(shù)組/結(jié)構(gòu)體/共用體 指針類 空類型（void） 基本類型單個(gè)出現(xiàn)的變量，每個(gè)變量可以代表一個(gè)確定的數(shù)據(jù)（變量值），且具有一定屬性。如 static int x,y;但變量間不存在確定的相互關(guān)系。 構(gòu)造類型由基本類型按一定規(guī)則組成。其中數(shù)組 ：由一組有序數(shù)據(jù)（數(shù)組元素）組成,這些數(shù)據(jù)保存在連續(xù)的內(nèi)存空間，每個(gè)元素具有相同類型,因此占有相同大小的存儲(chǔ)

3、單元，具有統(tǒng)一數(shù)組名，用下標(biāo)確定其順序，但可以取各自值。,如 static int a5;其中： 1. 表示a是個(gè)數(shù)組，而不是一個(gè)簡(jiǎn)單變量a 2. 5表示該數(shù)組共有5個(gè)元素 3. 元素編號(hào)即下標(biāo)從0開始，a0表示第一個(gè)元素，a4表示第5個(gè)元素（最后一個(gè)） 一般化：假設(shè)m和n是常量，則數(shù)組am的第一個(gè)元素是a0,最后一個(gè)元素是am-1;數(shù)組amn的第一個(gè)元素是a00,最后一個(gè)元素是am-1n-1,以此類推。,數(shù)組的用處很多。簡(jiǎn)單例子：要讀入某班全體50位同學(xué)某科學(xué)習(xí)成績(jī)，然后進(jìn)行簡(jiǎn)單處理（求平均成績(jī)、最高分、最低分）,分析：若用簡(jiǎn)單變量，需50個(gè)不同變量名，如stu1,stu2,stu50，要用

4、很多個(gè)cin命令。而用數(shù)組，可共用一個(gè)cin命令，并利用循環(huán)結(jié)構(gòu)讀取。,同變量一樣，數(shù)組也必須先定義，后使用。 定義內(nèi)容： 數(shù)組名 ：必須是合法標(biāo)示符 類型（存儲(chǔ)屬性/數(shù)據(jù)類型） 大?。ňS數(shù)/元素個(gè)數(shù)） 定義的一般形式： 存儲(chǔ)屬性 數(shù)據(jù)類型 數(shù)組名常量表達(dá)式常量表達(dá)式 常量表達(dá)式：常量或符號(hào)常量，其值必須為正，不能為變量 ！如：int n=5;int an;這樣定義是錯(cuò)誤的，如下為正確的：int a10,b54; char name8, ch23; static float x8*2+1, table234; #define NUM 40 int aNUM,bNUM+2;,數(shù)組定義,數(shù)組的初始

5、化,可以在定義數(shù)組的同時(shí)賦初值，如：,可以省略第一維數(shù)組大小，如： int a =, b3=;,省略元素值，如：,int a5=0; int b32=0;(全部元素初始化為0 ),int a 3=1,2,3,4,5,6,7 ; (思考第一維的大小?),靜態(tài)/外部數(shù)組未初始化,默認(rèn)初值是0（數(shù)值）或0（字符）. auto數(shù)組未初始化，初值為不可預(yù)料的數(shù)。,只能逐個(gè)引用數(shù)組元素,不能一次引用整個(gè)數(shù)組 .引用數(shù)組元素要注意下標(biāo)不要越界(編譯程序不檢查是否“越界”).引用示例 : a23 a2-12*3-1 ax(x為整型表達(dá)式或變量) int a5; for (i=0;i5;i+) (注意下標(biāo)不要越

6、界) coutai;,數(shù)組元素的引用,用一維數(shù)組來處理Fibonicci數(shù)列的前20項(xiàng)。 f1 = 1 n = 1 f2 = 1 n = 2 fn = fn-1 + fn-2 n 3,void main()int i; int f20 = 1,1; /* f1、f2已知 */ for(i=2; i20; i+) fi = fi-1 + fi-2; for(i=0; i20; i+) if (i%5 = 0) coutendl; coutsetw(12)fi; ,#include #include ,【例】以下程序的運(yùn)行結(jié)果是什么？ #include void main()int a3=1,2,

7、3,4,5,6,0; couta11a21a31; ,結(jié)果：500,1 2 3 4 5 0 6 0 0 0 0 0,【例】顯示如下圖形:1 0 0 0 0 2 1 0 0 0 3 2 1 0 0 4 3 2 1 0 5 4 3 2 1,a55分析: a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 a20 a21 a22 a23 a24 a30 a31 a32 a33 a34 a40 a41 a42 a43 a44,void main()int a55=1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,i,j; for(i=0;i=4;i+) for(j

8、=0;j=4;j+) coutaij; coutn; ,例：讀入某班全體50位同學(xué)某科學(xué)習(xí)成績(jī)，然后進(jìn)行簡(jiǎn)單處理（求平均成績(jī)、最高分、最低分）,例:找出一個(gè)二維數(shù)組的鞍點(diǎn),即該位置上的元素在該行上最大,在該列上最小,也可能沒有鞍點(diǎn).,【例】有一34矩陣，編程求其元素最大值并輸出其行、列號(hào)。 void main() int i,j,x,y,max; int a 4=3,5,8,1,6,9,7,12,-6; max=a00; for (i=0;imax) max=aij; x=i; y=j; coutmax is a x y = max n; ,3 5 8 1 6 9 7 12 -6 0 0 0,

9、結(jié)果：max is a13=12,用數(shù)組元素作函數(shù)實(shí)參此時(shí)可把數(shù)組元素看作普通變量(單向值傳遞).特點(diǎn)：主調(diào)函數(shù)中的實(shí)參數(shù)組元素(帶下標(biāo)) 被調(diào)函數(shù)中的形參普通變量 調(diào)用結(jié)果：形參值的變化對(duì)實(shí)參值無影響(二者分占不同內(nèi)存）,數(shù)組作為函數(shù)參數(shù),【例】void main() int a=1,2,3,4,5,6; static int b6=2,3,0,4; int i; sum(int,int,int);for (i=0;i6;i+) sum(ai,bi,i); couta=ai,b=bi; void sum(int x,int y,int z) x=z;y=z; ,結(jié)果： a=1,b=2 a=2

10、,b=3 a=3,b=0 a=4,b=4 a=5,b=0 a=6,b=0,用數(shù)組名作函數(shù)實(shí)參若int a6;則數(shù)組名a表示數(shù)組的起始地址.此時(shí),是把實(shí)參數(shù)組的起始地址“傳給”形參數(shù)組 .本質(zhì)：對(duì)應(yīng)的數(shù)組元素(不是形參與實(shí)參)共享同一內(nèi)存單元(所謂“雙向的地址傳送”).特點(diǎn)：主調(diào)函數(shù)中的實(shí)參數(shù)組名(不帶下標(biāo)) 被調(diào)函數(shù)中的形參數(shù)組名或數(shù)組定義式 調(diào)用結(jié)果：兩數(shù)組同下標(biāo)者為同值 .,數(shù)組作為函數(shù)參數(shù),【例】void main() int a=1,2,3,4,5,6; static int b6=2,3,0,4; int i; sum(int ,int ,int);for (i=0;i6;i+) s

11、um(a,b,i); couta=ai,b=bi; void sum(int x ,int y ,int z) xz=z+2;yz=z; ,傳址,結(jié)果： a=2,b=0 a=3,b=1 a=4,b=2 a=5,b=3 a=6,b=4 a=7,b=5,例：下面的程序定義了一個(gè)3x4的數(shù)組，表示3個(gè)學(xué)生，每個(gè)學(xué)生有4門成績(jī)，求所有學(xué)生中的最好成績(jī)。 int maximum(int4,int,int); void main()int sg34=68,77,73,86,87,96,78,86,90,70, 81,86; coutmax) max=gradeij; return max;,字符數(shù)組的初始

12、化 char c5=a,b,c; c3和c4自動(dòng)定為0 字符串在內(nèi)存中以字符數(shù)組存放,因此可以用字符串直接初始化字符數(shù)組. char c5=“abc”;思考：char c =“abc”; 數(shù)組c的數(shù)組長(zhǎng)度？ 字符串以字符串結(jié)束標(biāo)志0(即空字符)結(jié)束(可以思考A和“A”在內(nèi)存中存放的區(qū)別),因此 char c =“abc”;等價(jià)于 char c =a,b,c,0);既數(shù)組c的數(shù)組長(zhǎng)度為4,當(dāng)然char c5=“abc”;的數(shù)組長(zhǎng)度仍為5.,字符數(shù)組和字符串,字符數(shù)組char c5;的輸入 法一(逐字符輸入)：int i; for(i=0;ici; 法二(字符串輸入)：cinc; 注意：此法輸入的

13、字符串以空格或回車結(jié)束,即輸入的字符串不可能包括空格！如輸入：abc def回車后,c對(duì)應(yīng)的字符串為“abc”,而不是“abc def”.另外此法輸入的字符串串長(zhǎng)有可能比數(shù)組長(zhǎng)度要長(zhǎng)，應(yīng)引起注意！ 要想輸入帶空格的字符串,可使用函數(shù)cin.get或者cin.getline. 此例對(duì)應(yīng)cin.get(c,6,n) 或者cin.getline(c,6,n),字符數(shù)組char c5;的輸出法一：int i; for(i=0;i5;i+) coutci;法二：coutc; 輸出一個(gè)字符串，直到遇到0為止，因此輸出的字符串有可能和數(shù)組不一樣。,【例】比較以下字符數(shù)組長(zhǎng)度是否相同： char a =”AB

14、CD”; char b = “ABCD”; char c =A,B,C,D;,(5),(5),(4),【例】下列程序段的運(yùn)行結(jié)果是： char a5=a,b, 0,d,0; couta;,（ab）,二維數(shù)組可以看成特殊的一維數(shù)組，這個(gè)特殊的一維數(shù)組的元素又是一個(gè)一維數(shù)組。即a34可看成數(shù)組長(zhǎng)度為3的一維數(shù)組，而此一維數(shù)組的每個(gè)元素又是一個(gè)數(shù)組長(zhǎng)度為4的一維數(shù)組。如下圖所示：,所以a0對(duì)二維數(shù)組a來說是元素名，但對(duì)一維數(shù)組a00,a01,a02,a03來說卻是數(shù)組名.,【例】分析以下程序的運(yùn)行結(jié)果： void main()char word310;int i;for (i=0;iwordi; c

15、outwordi-2;運(yùn)行時(shí)，輸入：12345（回車）abcdef （回車）ABCDEFG（回車）,結(jié)果：abcdef,將一個(gè)字符串直接給一個(gè)字符數(shù)組只能夠出現(xiàn)在初始化中,不能夠出現(xiàn)在賦值語句中！也不能把一個(gè)字符數(shù)組直接賦值給另一個(gè)字符數(shù)組，如：char c5,d5;c=“abc”;d=c;是錯(cuò)誤的！ 要使用string.h的函數(shù)strcpy(to字符數(shù)組1,from字符數(shù)組2)如:strcpy(c,”abc”); strcpy(d,c);,字符串處理函數(shù),【例】以下程序的輸出結(jié)果是 。 #include “string.h” void main( ) char s10,sp =”HELLO”

16、; strcpy(s,sp); s0=h; s6=!; couts; ,hELLO,strcat( ) 字符串連接函數(shù)形式：strcat(目的字符數(shù)組，源字符串)；作用：將源字符串連接到目的字符數(shù)組后面。函數(shù)返回值：目的字符數(shù)組的地址。注意：目的字符數(shù)組要定義得足夠大。,【例】以下程序的輸出結(jié)果是 _。 #include string.h void main() char a =abcde; char b =12345; strcat(b,a); couta , b; ,abcde,12345abcde,【例】以下程序的輸出結(jié)果是 _。 #include string.h void main(

17、) char a80=”AB”,b80=”LMNP”; int i=0; strcat(a,b); while (ai+!=0) bi=ai; coutb; ,LBLMNP,比較兩個(gè)字符串(字符數(shù)組)的大小要使用string.h的函數(shù) strcmp(字符數(shù)組1,字符數(shù)組2)不能直接使用關(guān)系運(yùn)算符( = 0時(shí),字符串1字符串2；strcmp函數(shù)返回值0時(shí),字符串1字符串2； 思考:如何判斷str1是否等于str2？,要寫成 if(strcmp(str1,str2)=0) .不可寫成 if(str1=str2) .,#include “string.h” void main() int i; ch

18、ar str10,temp10=”Control”; for ( i=0; istr; if(strcmp(temp,str)0) strcpy(temp,str); couttemp;,【例】運(yùn)行以下程序時(shí)，從鍵盤輸入：BOOKCUTGAMEPAGE(表示回車)，則運(yùn)行結(jié)果是什么？,變量跟蹤： temp str 比較,i=0,Control,BOOK,0,i=1,Control,CUT,0,i=2,Control,GAME,0,GAME,i=3,GAME,PAGE,0,PAGE,求字符串實(shí)際長(zhǎng)度可使用string.h的函數(shù)strlen(字符數(shù)組),它不包括字符串的結(jié)束符0.如: char a

19、10=“abcde”; 則strlen(a)=5 ,sizeof(a)=10,【例】以下程序段的運(yùn)行結(jié)果是什么？ char a =”tr0willn”; coutsizeof(a)tstrlen(a);,結(jié)果：10 3,數(shù)組元素的排序,一 輸入10個(gè)數(shù)，用“冒泡法”對(duì)10個(gè)數(shù)排序（由小到大）。 “冒泡法”算法：以六個(gè)數(shù)9、8、5、4、2、0為例。第1趟比較,第一次：8、9、5、4、2、0,第二次：8、5、9、4、2、0,第三次：8、5、4、9、2、0,第四次：8、5、4、2、9、0,第五次：8、5、4、2、0、9,第1趟比較產(chǎn)生第一個(gè)最大數(shù)：9,對(duì)剩下的五個(gè)數(shù)： 8、5、4、2、0進(jìn)行第2趟比

20、較,第一次：5、8、4、2、0,第二次：5、4、8、2、0,第三次：5、4、2、8、0,第四次：5、4、2、0、8,第2趟比較產(chǎn)生第二個(gè)最大數(shù)：8依此類推，便可實(shí)現(xiàn)排序。,第1趟比較后，剩5個(gè)數(shù)未排好序；兩兩比較5次 第2趟比較后，剩4個(gè)數(shù)未排好序；兩兩比較4次 第3趟比較后，剩3個(gè)數(shù)未排好序；兩兩比較3次 第4趟比較后，剩2個(gè)數(shù)未排好序；兩兩比較2次 第5趟比較后，全部排好序； 兩兩比較1次,算法結(jié)論：對(duì)于n個(gè)數(shù)的排序，需進(jìn)行n-1趟比較，第i趟比較需進(jìn)行n-i次兩兩比較。,for(i=1;iaj+1) t=aj; aj=aj+1; aj+1=t; ,改進(jìn)后的算法for(i=1;iaj+1)

21、 t=aj; aj=aj+1; aj+1=t; flag=1; if(flag=0) break;,二 輸入10個(gè)數(shù)，用“選擇法”對(duì)10個(gè)數(shù)排序（由小到大）。 “選擇法”算法：以六個(gè)數(shù)9、8、5、4、2、0為例。第1趟比較,第一次：8、9、5、4、2、0,第二次：5、9、8、4、2、0,第三次：4、9、8、5、2、0,第四次：2、9、8、5、4、0,第五次：0、9、8、5、4、2,第1趟比較產(chǎn)生第一個(gè)最小數(shù)：0,對(duì)剩下的五個(gè)數(shù)： 9、8、5、4、2進(jìn)行第2趟比較,第一次：8、9、5、4、2,第二次：5、9、8、4、2,第三次：4、9、8、5、2,第四次：2、9、8、5、4,第2趟比較產(chǎn)生第二個(gè)

22、最小數(shù)：2依此類推，便可實(shí)現(xiàn)排序。,算法總結(jié)：對(duì)于n個(gè)數(shù)的排序，需進(jìn)行n-1趟比較，第i趟比較時(shí)要將第i+1個(gè)開始的元素依次與第i個(gè)元素進(jìn)行兩兩比較，后者小于前者就進(jìn)行交換。,for(i=0;in-1;i+) for(j=i+1;jn;j+) if(ajai) t=ai; ai=aj; aj=t; ,for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(k!=i) t=ai; ai=ak; ak=t; ,改進(jìn)后的選擇排序算法,三 插入排序基本思想：（假定從小到大排序）依次從后面拿一個(gè)數(shù)和前面已經(jīng)排好序的數(shù)進(jìn)行比較，比較的過程是從已經(jīng)排好序的數(shù)中最后一個(gè)數(shù)開始比較，如果比這個(gè)數(shù)，繼續(xù)往前面比較，直到找到比它大的數(shù)，然后就放在它的后面，如果一直沒有找到，肯定這個(gè)數(shù)已經(jīng)比較到了