2014級(jí)程序設(shè)計(jì)語(yǔ)言課件第五章數(shù)組

第五章數(shù)組數(shù)組知識(shí)點(diǎn)體系問(wèn)題的提出二維及多維數(shù)組排序算法查找算法一維數(shù)組集合操作矩陣應(yīng)用一、問(wèn)題的提出？（1）用基本數(shù)據(jù)類(lèi)型可以解決所有問(wèn)題嗎？例如：對(duì)某班學(xué)生的成績(jī)按由高到底的次序進(jìn)行排序。

3名？30名？如何描述這一列數(shù)據(jù)？采用一維數(shù)組一、問(wèn)題的提出？（2）路徑求解：如何求解a到e的最短路徑？如何存儲(chǔ)圖呢？二維數(shù)組5C數(shù)據(jù)類(lèi)型基本類(lèi)型構(gòu)造類(lèi)型指針類(lèi)型空類(lèi)型void定義類(lèi)型struct枚舉類(lèi)型enum整型浮點(diǎn)型數(shù)值類(lèi)型字符類(lèi)型char短整型short長(zhǎng)整型long整型int單精度型float雙精度型double數(shù)組結(jié)構(gòu)體struct共用體union二、數(shù)組的概念（1）數(shù)組是具有一定順序關(guān)系的若干相同

類(lèi)型變量的集合體。組成數(shù)組的變量稱為

該數(shù)組的元素。數(shù)組屬于復(fù)合數(shù)據(jù)類(lèi)型。二、數(shù)組的概念（2）一維數(shù)組的定義類(lèi)型說(shuō)明符數(shù)組名[常量表達(dá)式]

例如：inta[10],b[35]；

表示a為整型數(shù)組，有10個(gè)元素：a[0],a[1],...a[9]表示b為整型數(shù)組，有35個(gè)元素：b[0],b[1]...b[34]無(wú)a[10]數(shù)組長(zhǎng)度,可以是常量和符號(hào)常量，不能用變量三、一維數(shù)組的操作____定義（1）三、一維數(shù)組的操作____初始化（2）初始化全部元素

inta[10]={0,1,2,3,4,5,6,7,8,9};

等價(jià)于a[0]=0，a[1]=1，a[2]=2，…a[9]=9初始化部分元素

inta[10]={0,1,2,3};等價(jià)于a[0]=0，a[1]=1，a[2]=2，a[3]=3,a[4]=0,a[5]=0,…a[9]=0根據(jù)數(shù)據(jù)初值個(gè)數(shù)系統(tǒng)自動(dòng)定義數(shù)組長(zhǎng)度

inta[]={1,2,3,4,5}等價(jià)于

inta[5]={1,2,3,4,5}三、一維數(shù)組的操作____內(nèi)存分配（3）例:

inta[5]={11,22,33,44,55};1122335544a[0]a[1]a[2]a[3]a[4]a數(shù)組名[下標(biāo)]，如：a[5]下標(biāo)可以為常量，也可以為變量或表達(dá)式，但其值必須是整數(shù)；只能逐個(gè)引用數(shù)組元素；不能一次引用整個(gè)數(shù)組，每個(gè)元素的引用方法與一般變量相同。下標(biāo)不能越界：編譯程序不檢查是否越界，下標(biāo)越界，將訪問(wèn)數(shù)組以外的空間，可能帶來(lái)嚴(yán)重后果例如：

int

a[10];for(j=0;j<10;j++)

scanf(“%d”,&a[j]);a[0]=a[5]+a[7]-a[2*3]；三、一維數(shù)組的操作____數(shù)組的使用（4）

scanf(“%d”,a);正確？()#include<stdio.h>voidmain(){

inti,j;

floatx[20],y,z;

inta[97.8];……

x[i+j*2]=i+j;z=x[y*2];printf("%f",x[0]);printf("%f",x[20]);scanf("%f",&x);scanf("%f",&x[3]);printf("%f",x);

floaty[20];y=x;y[10]=x[10];}下標(biāo)表達(dá)式的值必須是一個(gè)整數(shù)下標(biāo)表達(dá)式的值應(yīng)大于等于0小于數(shù)組的大小定義數(shù)組的大小必須是一個(gè)正整數(shù)常量數(shù)組不能作為一個(gè)整體直接輸入輸出，用元素?cái)?shù)組不能作為一個(gè)整體相賦值，用元素【案例1】輸入10個(gè)實(shí)數(shù)，并求出這10個(gè)實(shí)數(shù)的平均值#include<stdio.h>voidmain(void){ inti; floatx[10],sum=0; printf("輸入10個(gè)數(shù):"); for(i=0;i<10;i++) { scanf("%f",&x[i]); sum+=x[i]; } printf(“10個(gè)數(shù)字是："); for(i=0;i<10;i++) { printf("%f",x[i]); } printf("\n平均數(shù)是:%f\n",sum/10);}三、一維數(shù)組的操作____案例1（6）【案例2】寫(xiě)出下面程序的運(yùn)行結(jié)果#include<stdio.h>voidmain(){ inti,a[10]; for(i=0;i<=9;i++) a[i]=i; for(i=9;i>=0;i--) printf(“%d,”,a[i]);}運(yùn)行結(jié)果:9,8,7,6,5,4,3,2,1,0三、一維數(shù)組的操作____案例2（6）三、一維數(shù)組的操作____案例3（8）【案例3】求一列數(shù)中的最小值#include<stdio.h>voidmain(){ inti,a[10],min;min=a[0]; for(i=0;i<=9;i++) if(a[i]<min)

填空

printf(“min=%d\n”,min);}101223835544a[0]a[1]a[2]a[3]a[4]【案例4】用數(shù)組來(lái)處理求Fibonacci數(shù)列問(wèn)題定義并初始化數(shù)組for(i=2;i<20;i++)f[i]=f[i-1]+f[i-2]for(i=0;i<20;i++)i%5==0NY打印換行打印f[i]fn=1(n=0,1)fn-1+fn-2(n≥2)1,1,2,3,5,8,13…三、一維數(shù)組的操作____案例4（9）【案例4】用數(shù)組來(lái)處理求Fibonacci數(shù)列問(wèn)題#include<stdio.h>voidmain(){ inti;intf[20]={1,1};for(i=2;i<20;i++)f[i]=f[i-1]+f[i-2];for(i=0;i<20;i++){if(i%5==0)printf(“\n”);printf(“%12d”,f[i]);}}三、一維數(shù)組的操作____案例3（9）二維數(shù)組的定義類(lèi)型說(shuō)明符數(shù)組名[常量表達(dá)式1][常量表達(dá)式2]例如：inta[3][4]；

表示a為整型數(shù)組，存放3行4列，共12個(gè)整型數(shù)組元素：a[0][0],a[0][1],a[0][2],a[0][3],a[1][0].....a[2][3]。四、二維數(shù)組的操作____定義（1）行數(shù)列數(shù)二維數(shù)組元素標(biāo)識(shí)：a[i][j],i表示行下標(biāo)，j表示列下標(biāo).注意：下標(biāo)不能越界四、二維數(shù)組的操作____邏輯結(jié)構(gòu)（2）a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][2]a[2][0]a[2][1]a[2][2]a[2][3]二維數(shù)組的邏輯結(jié)構(gòu)可以看成是一個(gè)表格或矩陣?yán)纾篿nta[3][4]；a[0]:a[1]:a[2]:四、二維數(shù)組的操作____存儲(chǔ)結(jié)構(gòu)（3）014523a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[0][0]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]a[1][2]67101189a[0]a[1]a[2]例如：inta[3][4]；分行給二維數(shù)組賦初值inta[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};分行給部分元素賦初值intb[3][4]={{1},{0,6},{0,0,11}};所有數(shù)據(jù)寫(xiě)在一個(gè){}內(nèi)，按存儲(chǔ)順序依次賦值intc[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};根據(jù)給定初值,系統(tǒng)自動(dòng)定行數(shù)intd[][3]={{1},{2},{3,4,5}};等價(jià)于

d[3][3]intf[][3]={1,2,3,4,5,6};等價(jià)于

f[2][3]

四、二維數(shù)組的操作____初始化（4）注意：此時(shí)只能省略第1維的值。C根據(jù)初始化數(shù)據(jù)的數(shù)量，自動(dòng)確定第1維的大小12345678

910111210000600

00110

100200345

123456四、二維數(shù)組的操作____案例1（5）【案例1】遍歷二維數(shù)組，求出最小、最大值及其位置a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][2]a[2][0]a[2][1]a[2][2]a[2][3]四、二維數(shù)組的操作____案例1（5）voidmain(void){inti,j,rmax,rmin,cmax,cmin,min,max,a[3][4];for(i=0;i<3;i++)for(j=0;j<4;j++)scanf("%d",&a[i][j]);min=max=a[0][0];rmax=rmin=cmax=cmin=0;for(i=0;i<3;i++)for(j=0;j<4;j++){if(a[i][j]>max){max=a[i][j];rmax=i;cmax=j;}if(a[i][j]<min) {min=a[i][j];rmin=i;cmin=j;}}

printf(“max=%d,rmax=%d,cmax=%d\n”,max,rmax,cmax);}【案例2】設(shè)計(jì)一程序，將一個(gè)4行4列的二維數(shù)組中行和列元素互換（數(shù)學(xué)上稱為矩陣的轉(zhuǎn)置），并存放到另一個(gè)數(shù)組中。例如：11121314151617181920212223242526a=11151923121620241317212514182226b=四、二維數(shù)組的操作____案例2（6）voidmain(void){inta[4][4]={{11,12,13,14},{15,16,17,18},{19,20,21,22},{23,24,25,26}};intb[4][4],i,j;for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",a[i][j]); printf("\n");}for(i=0;i<4;i++) for(j=0;j<4;j++) b[j][i]=a[i][j]; printf("數(shù)組b:\n");for(i=0;i<4;i++){ for(j=0;j<4;j++) printf("%d",b[i][j]); printf("\n");}}四、二維數(shù)組的操作____案例2（6）分兩種情況：即數(shù)組元素作函數(shù)參數(shù)和數(shù)組名作函數(shù)的參數(shù)。數(shù)組元素作函數(shù)參數(shù)時(shí)和一般變量作函數(shù)參數(shù)是一樣的,是值傳遞

數(shù)組名（是數(shù)組存儲(chǔ)區(qū)的首地址）作函數(shù)參數(shù)時(shí)與數(shù)組元素作參數(shù)不同，是地址傳遞。五、數(shù)組作為函數(shù)的參數(shù)（1）main(){

intmultiple

(intx)；inti,s=0,a[5]={1,2,3,4,5};for(i=0;i<5;i++)s=s+multiple

(a[i]);printf("s=%d\n",s);}intmultiple

(intx){inty;y=x*10;return(y);}

輸出結(jié)果：s=150五、數(shù)組作為函數(shù)的參數(shù)_數(shù)組元素做參數(shù)（2）把數(shù)組名做實(shí)參進(jìn)行參數(shù)傳遞，就是把數(shù)組存儲(chǔ)區(qū)的首地址傳給形參。這種傳遞方式稱為：地址傳遞

要求：實(shí)參和形參分別定義數(shù)組,且類(lèi)型應(yīng)一致，形參數(shù)組大小(多維數(shù)組第一維)可不指定。形參數(shù)組名實(shí)際是地址變量。（因?yàn)橛脕?lái)存放數(shù)組存儲(chǔ)區(qū)首地址）這時(shí)實(shí)參和形參對(duì)應(yīng)同一個(gè)數(shù)組存儲(chǔ)區(qū)，所以傳遞是雙向的。傳遞整個(gè)數(shù)組給另一個(gè)函數(shù)，是將數(shù)組的首地址作為參數(shù)傳過(guò)去（地址傳遞

)，所以效率自然比拷貝全部數(shù)據(jù)效率高。

五、數(shù)組作為函數(shù)的參數(shù)_數(shù)組名做參數(shù)（3）【案例3】

求學(xué)生的平均成績(jī)floataverage(intstu[],intn);main(){intscore[10],i;floatav;printf("Input10scores：\n");for(i=0;i<10;i++)scanf("%d",&score[i]);av=average(score

,

10);printf("Averageis：%.2f",av);}floataverage(intstu[],intn){inti;floatav,total=0;for(i=0;i<n;i++)total+=stu[i];av=total/n;returnav;}..2109score569372….….88stu10n五、數(shù)組作為函數(shù)的參數(shù)_數(shù)組名做參數(shù)（4）【案例4】（數(shù)組分段交換或數(shù)組循環(huán)左移k位）長(zhǎng)度為n的數(shù)組a可以分為兩段，前面k個(gè)元素為一段，后面n-k個(gè)元素為另一段。編程交換兩組元素的位置，交換之后每一組內(nèi)部元素的相對(duì)位置保持不變。例如，數(shù)組a如下：a={1,2,3,4,5,6,7,8}.k=3,兩組交換之后數(shù)組變成:a={4,5,6,7,8,1,2,3}五、數(shù)組作為函數(shù)的參數(shù)_數(shù)組名做參數(shù)（5）解決方案1：使用臨時(shí)數(shù)組#include<stdio.h>voidarray_swap(inta[],intn,intk){intt[50];inti;

for(i=0;i<k;i++)

//將數(shù)組a的第一段(用a[0～k-1]表示)拷貝到臨時(shí)數(shù)組t中

t[i]=a[i];for(i=k;i<=n-1;i++)//將數(shù)組a的第二段（用a[k～n-1]表示）向前移動(dòng)k個(gè)元素a[i-k]=a[i];for(i=0;i<k;i++)//將數(shù)組t的元素拷貝到數(shù)組a的后面k個(gè)位置（a[k～n-1]）a[n-k+i]=t[i];}12345678at0kn-1解決方案1：使用臨時(shí)數(shù)組#include<stdio.h>voidarray_swap(inta[],intn,intk){intt[50];inti;for(i=0;i<k;i++)//將數(shù)組a的第一段(用a[0～k-1]表示)拷貝到臨時(shí)數(shù)組t中t[i]=a[i];

for(i=k;i<=n-1;i++)//將數(shù)組a的第二段（用a[k～n-1]表示）向前移動(dòng)k個(gè)元素

a[i-k]=a[i];for(i=0;i<k;i++)//將數(shù)組t的元素拷貝到數(shù)組a的后面k個(gè)位置（a[k～n-1]）a[n-k+i]=t[i];}12345678123at0kn-1解決方案1：使用臨時(shí)數(shù)組#include<stdio.h>voidarray_swap(inta[],intn,intk){intt[50];inti;for(i=0;i<k;i++)//將數(shù)組a的第一段(用a[0～k-1]表示)拷貝到臨時(shí)數(shù)組t中t[i]=a[i];

for(i=k;i<=n-1;i++)//將數(shù)組a的第二段（用a[k～n-1]表示）向前移動(dòng)k個(gè)元素

a[i-k]=a[i];for(i=0;i<k;i++)//將數(shù)組t的元素拷貝到數(shù)組a的后面k個(gè)位置（a[k～n-1]）a[n-k+i]=t[i];}45678123at0kn-1解決方案1：使用臨時(shí)數(shù)組#include<stdio.h>voidarray_swap(inta[],intn,intk){intt[50];inti;for(i=0;i<k;i++)//將數(shù)組a的第一段(用a[0～k-1]表示)拷貝到臨時(shí)數(shù)組t中t[i]=a[i];for(i=k;i<=n-1;i++)//將數(shù)組a的第二段（用a[k～n-1]表示）向前移動(dòng)k個(gè)元素a[i-k]=a[i];

for(i=0;i<k;i++)//將數(shù)組t的元素拷貝到數(shù)組a的后面k個(gè)位置（a[k～n-1]）

a[n-k+i]=t[i];}45678123123at0kn-1解決方案2：數(shù)組元素逆序法對(duì)下列數(shù)組a={1,2,3,4,5,6,7,8}.以k=3為分界點(diǎn)，分成兩段，對(duì)第一段和第二段分別逆序，結(jié)果如下：a’={3,2,1,8,7,6,5,4}再對(duì)a’整體逆序得：a’’={4,5,6,7,8,1,2,3}解決方案2：數(shù)組逆序算法/*功能：逆序數(shù)組a中指定區(qū)間a[l]～a[h]的元素*/voidarray_reverse(inta[],intl,inth){intt;while(l<h)

{

t=a[l];a[l]=a[h];a[h]=t;

l++;h--;}}12345678alh18解決方案2：數(shù)組逆序算法/*功能：逆序數(shù)組a中指定區(qū)間a[l]～a[h]的元素*/voidarray_reverse(inta[],intl,inth){intt;while(l<h)

{t=a[l];a[l]=a[h];a[h]=t;

l++;h--;}}82345671alh

l

h解決方案2：數(shù)組逆序算法/*功能：逆序數(shù)組a中指定區(qū)間a[l]～a[h]的元素*/voidarray_reverse(inta[],intl,inth){intt;while(l<h)

{t=a[l];a[l]=a[h];a[h]=t;

l++;h--;}}87345621ahl解決方案2：數(shù)組逆序算法/*功能：逆序數(shù)組a中指定區(qū)間a[l]～a[h]的元素*/voidarray_reverse(inta[],intl,inth){intt;while(l<h)

{t=a[l];a[l]=a[h];a[h]=t;

l++;h--;}}87654321ahlvoidarray_swap(inta[],intn,intk){array_reverse(a,0,k-1);//對(duì)第一段逆序

array_reverse(a,k,n-1);//對(duì)第二段逆序

array_reverse(a,0,n-1);//對(duì)整個(gè)數(shù)組逆序}main(){inta[]={1,2,3,4,5,6,7,8};inti,n=8,k=3;printf("交換前\n");for(i=0;i<n;i++)printf("%3d",a[i]);printf("\n");array_swap(a,n,k);//調(diào)用函數(shù)

printf("交換后(分段位置:%d)\n",k);for(i=0;i<n;i++)

printf("%3d",a[i]);printf("\n");}12345678ak0123456732145678a32187654a45678123a【案例5】埃拉托斯特尼(Eratosthene)篩法求不超過(guò)正整數(shù)N的素?cái)?shù)

思路：定義一個(gè)數(shù)組prime[N],存儲(chǔ)以下奇數(shù)：3、5、7、9、11、13……95、97、99…從第0個(gè)元素開(kāi)始，其后的各個(gè)元素若是第0個(gè)元素的倍數(shù)，則將其值置為0，表示該元素不是素?cái)?shù)再?gòu)牡?個(gè)元素開(kāi)始……一直到從第sqrt(N)個(gè)元素開(kāi)始，其后元素如是第sqrt(N)個(gè)元素的倍數(shù)，則將其值置位0這時(shí)數(shù)組prime中不為0的元素是素?cái)?shù)35791113151719212325272931333537394143450000000000⑴變量設(shè)置及初始化：我們用數(shù)組prime表示1～N之間的所有素?cái)?shù)，數(shù)組prime按如下規(guī)律初始化：intprime[]={2,3,5,7,9,……}，設(shè)置一個(gè)指示變量k作數(shù)組prime的下標(biāo)，用prime[k]作篩子，k的初值為1，為了后面解釋方便，稱k為篩下標(biāo)變量?！纠堪＠兴固啬?Eratosthene)篩法求不超過(guò)正整數(shù)N的素?cái)?shù)

3579111315171921232527293133353739414345⑵算法框架根據(jù)篩法的思想，可以寫(xiě)出下面的框架①初始化數(shù)組prime,初始化篩下標(biāo)變量k=1；②如果prime[k]>=sqrt(N)轉(zhuǎn)第⑥步，否則執(zhí)行第③步；③取出prime[k]，從數(shù)組中刪除prime[k]的倍數(shù)；④確定k的下一個(gè)值k'，prime[k+1]～prime[N]中最小的素?cái)?shù)必定是下一個(gè)可用的篩子，這個(gè)最小的素?cái)?shù)的下標(biāo)即為k'；⑤k=k'，轉(zhuǎn)第②步；⑥輸出數(shù)組prime中的非0元素，即為1～N之間的所有素?cái)?shù)?！纠堪＠兴固啬?Eratosthene)篩法求不超過(guò)正整數(shù)N的素?cái)?shù)

35791113151719212325272931333537394143450000000000算法名：篩法求素?cái)?shù)begin

初始化數(shù)組prime；初始化k=1；

while(prime[k]<=sqrt(n)){k=sieve(prime,n,k)；/*用prime[k]作篩子，對(duì)數(shù)組prime作篩選*/

}output(prime);end【例】埃拉托斯特尼(Eratosthene)篩法求不超過(guò)正整數(shù)N的素?cái)?shù)

35791113151719212325272931333537394143450000000000Sieve函數(shù)：intsieve(intprime[],intn,intk){inti;for(i=k+1;i<n;i++)//用prime[k]作篩子，清除數(shù)組prime中prime[k]的倍數(shù)

if(prime[i]&&prime[i]%prime[k]==0)prime[i]=0;k++;//求下一個(gè)可用的篩下標(biāo)

while(prime[k]==0)k++;returnk;}357911131517192123252729313335373941434500000000erat_sieve函數(shù)：voiderat_sieve(intprime[],intn){inti,m,k; prime[0]=2;

m=sqrt(n);n=n/2; for(i=1;i<n;i++) prime[i]=2*i+1; k=1;while(prime[k]<=m)k=sieve(prime,n,k);//用prime[k]作篩子，對(duì)數(shù)組prime作篩選}主函數(shù)#include<stdio.h>#include<math.h>intsieve(intprime[],intn,intk);voiderat_sieve(intprime[],intn);voidmain(){ intprime[10000]; inti,n,cnt; printf("輸入整數(shù)n(1~n):"); scanf("%d",&n);

erat_sieve(prime,n);cnt=0;//cnt用于統(tǒng)計(jì)prime總的素?cái)?shù)個(gè)數(shù)

for(i=0;i<n/2;i++) if(prime[i]) { cnt++; if(cnt%8==0)//每行輸出8個(gè)素?cái)?shù)

printf("%-8d\n",prime[i]); else printf("%-8d",prime[i]); } printf("\n1～%d之間的素?cái)?shù)個(gè)數(shù)=%d\n",n,cnt);}如果prime[i]不為0，表示是素?cái)?shù)P137-5.9從一列有序數(shù)中，刪除相同數(shù)據(jù)例：求學(xué)生的平均成績(jī)

#include<stdio.h>

floataverage(intstu[10],intn);main(){intscore[10],i;floatav;printf("Input10scores：\n");for(i=0;i<10;i++)scanf("%d",&score[i]);av=average(score

,

10);printf("Averageis：%.2f",av);}floataverage(int

stu[],intn){inti;floatav,total=0;for(i=0;i<n;i++)total+=stu[i];av=total/n;returnav;}實(shí)參用數(shù)組名形參用數(shù)組定義..2109score569372….….88stu雙向傳遞實(shí)參和形參數(shù)組類(lèi)型應(yīng)一致10n

數(shù)組名做函數(shù)的實(shí)參和形參在主調(diào)函數(shù)和被調(diào)函數(shù)中分別定義數(shù)組。實(shí)參數(shù)組和形參數(shù)組類(lèi)型應(yīng)一致。實(shí)參數(shù)組和形參數(shù)組大小不一定一致，形參數(shù)組可以不指定大小，但形參數(shù)組名后面的方括號(hào)不能省略。

由于數(shù)組名代表數(shù)組的起始地址,故數(shù)組名做函數(shù)的實(shí)參和形參時(shí)不是“值傳遞”，而是“地址傳遞”。因此，形參數(shù)組各元素的值如果發(fā)生變化,會(huì)使實(shí)參數(shù)組各元素的值發(fā)生同樣的變化。六、多維數(shù)組作函數(shù)參數(shù)（1）函數(shù)定義形參可以省略第一維大小，但是第二維的大小不可省略；

f