[學(xué)習(xí)]樊媛媛c語言程序設(shè)計(jì)07-數(shù)組

1、第七章 數(shù) 組 7．1 數(shù)據(jù)結(jié)構(gòu)與數(shù)組的概念 影響程序設(shè)計(jì)的因素除算法外還有數(shù)據(jù)結(jié)構(gòu)。 ■數(shù)據(jù)結(jié)構(gòu)概念 編寫一個(gè)程序除了重視算法的設(shè)計(jì)外，還需重視數(shù)據(jù)類型的選擇，即選擇合適的數(shù)據(jù)類型來存放要處理的數(shù)據(jù)。在程序設(shè)計(jì)中，數(shù)據(jù)類型就稱為數(shù)據(jù)結(jié)構(gòu)，選擇合適的數(shù)據(jù)類型實(shí)際上就是進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。,在程序設(shè)計(jì)中有格言： 數(shù)據(jù)結(jié)構(gòu)+算法=程序 說明數(shù)據(jù)結(jié)構(gòu)與算法同等重要，算法依賴于數(shù)據(jù)結(jié)構(gòu)，對(duì)于同一個(gè)問題的求

2、解，可以采用不同的數(shù)據(jù)結(jié)構(gòu)和不同的算法，對(duì)不同的數(shù)據(jù)結(jié)構(gòu)有不同的算法，其復(fù)雜程度也會(huì)不同，選擇合適的數(shù)據(jù)結(jié)構(gòu)，可以降低算法的復(fù)雜程度。因此，在程序設(shè)計(jì)中應(yīng)重視數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。,例：求任意100個(gè)數(shù)中的最大值。 main() { int i,a,max; max=-32768 for(i=1;imax) max=a; } printf(“\n max=%d”,max); },用一個(gè)簡(jiǎn)單變

3、量作為數(shù)據(jù)結(jié)構(gòu)，合理，算法簡(jiǎn)單,對(duì)于三個(gè)數(shù)的排序：main(){ int a,b,c,t; scanf(“%d,%d,%d”,&a,&b,&c); if(a<b) {t=a; a=b; b=t;} if(a<c) {t=a; a=c; c=t;} if(b<c) {t=b; b=c; c=t; } printf(“\n %d,%d,%d”,a,b,

4、c);}對(duì)于很多個(gè)數(shù)的排序用變量會(huì)很復(fù)雜而用數(shù)組會(huì)使算法很簡(jiǎn)單。,,仍可用變量作為數(shù)據(jù)結(jié)構(gòu),■數(shù)組的概念 一組具有同樣類型的數(shù)據(jù)的集合 統(tǒng)一用一個(gè)名字代表---數(shù)組名（代表一組數(shù)） 將一組數(shù)用一個(gè)名字代表，便于管理。,,int a[10],數(shù)組名,,數(shù)組大小,,數(shù)組中的各成員稱數(shù)組元素，由數(shù)組名加下標(biāo)唯一地確定。,只有一個(gè)下標(biāo)的數(shù)組稱為一維數(shù)組；可有二維數(shù)組、三維數(shù)組、…、七維數(shù)組。,7．2 一維數(shù)組的定義

5、和引用 ■定義 一般形式： 類型符 數(shù)組名[常量表達(dá)式]；  int a[10]; float b[10]； 類型符 數(shù)組名 長度 作用：分配一組連續(xù)的內(nèi)存單元,,,,說明： ●數(shù)組必須先定義后使用。 ●數(shù)組名的命名規(guī)則與變量相同。 ●常量表達(dá)式表示元素的個(gè)數(shù)（長度），下標(biāo) 從0開始。 ●常量表達(dá)式不能包含變量，即不允許作動(dòng)態(tài)定義。,■引用 逐個(gè)引用其

6、元素，不能進(jìn)行整體引用。 引用的一般形式： 數(shù)組名[下標(biāo)] 如：a[0]=50; a[1]=100; a[2]=a[0]+a[1]; 與 a2=a0+a1有根本性的區(qū)別：下標(biāo)可變。,例：從鍵盤輸入10個(gè)數(shù)。用變量：(不方便)scanf(“%d%d%d%d%d%d%d%d%d%d”， &a0,&a1,&a2,&a3,&a4,&a5

7、,&a6,&a7,&a8,&a9);用數(shù)組： (靈活方便) for(i=0;i<10;i++) scanf(“%d”,&a[i]); 用循環(huán)控制輸入個(gè)數(shù)和下標(biāo)的變化。 注意下標(biāo)的變化范圍。,■初始化 eg7-0 在定義數(shù)組的同時(shí)給數(shù)組賦初值。 int a[10]={0,1,2,3,4,5,6,7,8,9}; int a[10]={0,1,2,3,4};

8、 int a[]={0,1,2,3,4};,■應(yīng)用舉例（1）對(duì)100個(gè)學(xué)生的分?jǐn)?shù)統(tǒng)計(jì)最高分、最低分和平均分。 兩種方法： 用變量作為存放初始數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu) 用數(shù)組作為存放初始數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),main() { int i,a,max,min; float aver=0; max=0; min=100; for(i=0;imax) max=a;

9、 if(a<min) min=a; aver+=a; } aver/=100; printf(“\n %d,%d,%f”,max,min,aver); },用變量eg7-1,#define N 100 main() { int i,a[N],max,min; float aver=0; for(i=0;imax) max=a[i];

10、 if(a[i]<min) min=a[i]; aver+=a[i]; } aver/=N; printf(“\n %d,%d,%f”,max,min,aver)； },用數(shù)組eg7-2,找最大最小的位置？eg7-3,max=0; min=0;,if(a[i]>a[max]) max=i;if(a[i]<a[min]) min=i;,（2）統(tǒng)計(jì)高于

11、平均分的人數(shù)。,main(){ int i,a,n; float aver=0; for(i=0;i<100;i++) { scanf(“%d”,&a); aver+=a; } aver/=100;,n=0; for(i=0;iaver)n++; } printf(“\n %d”,n);},用變量,數(shù)據(jù)結(jié)構(gòu)不合理,#define N 100main(){ int

12、 i,a[N],n; float aver=0; for(i=0;iaver)n++; printf(“\n %d”,n);},用數(shù)組eg7-4,（3）對(duì)100個(gè)學(xué)生的分?jǐn)?shù)統(tǒng)計(jì)出每分一檔人數(shù)。 0 ？ 1 ？ 2  ？    3    ？    4

13、    ？ ┇ ┇ 99 ？ 100 ？,#define N 100main(){ int i,a;  for(i=1;i<=N;i++) { scanf(“%d”,&a);  } 輸出 },int i,a,n[N+1];for(i=0;i<N+1;i++) n[i]=0;,n[

14、a]++;,完整程序： eg7-5#define N 100main(){ int i,a,n[N+1]; for(i=0;i=0;i--) printf(“\n %3d:%3d”,i,n[i]);},體會(huì)數(shù)組作為存放結(jié)果的數(shù)據(jù)結(jié)構(gòu)時(shí)的優(yōu)越性。,按10分一檔統(tǒng)計(jì)？ eg7-6#define N 100main(){ int i,a,n[N+1]; for(i=0;i<N+1;i++)

15、n[i]=0;  for(i=1;i<=N;i++) { scanf(“%d”,&a); n[a]++;  }},int i,a,n[11];for(i=0;i<11;i++)n[i]=0;,n[a/10]++;,#define N 10,（4）對(duì)10個(gè)學(xué)生的分?jǐn)?shù)按從小到大的順序排序后輸出。 兩種典型的排序算法：選擇法和起泡法。選擇法基本思想：

16、首先選擇最小的數(shù)放在0位置，再在剩下的數(shù)中選擇最小的數(shù)放在下一位置，┈┈，依次類推，共進(jìn)行9次選擇。 5 8 7 4 3 9 0 1 2 6,每次選擇都要與其后的所有數(shù)進(jìn)行比較換位。 5 8 7 4 3 9 0 1 2 6,,,,,,,,,,,,,,i,j,for(i=0;ia[j]) { t=a[i];

17、 a[i]=a[j]; a[j]=t; },eg7-7#define N 10main(){ int a[N],i,j,t; for(i=0;ia[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } for(j=0;j<N;j++) printf(“%3d”,a[j]); },5 8 7 4 3 9 0 1 2 6,5

18、8 7 4 3 9 0 1 2 6,,,,,,,,,,,,,,i,j,小改進(jìn)：先找最小值所在的位置，最后再換位:,for(i=0;i<N-1;i++) { k=i; for(j=i+1;j<N;j++) if(a[j]<a[k])k=j; t=a[i]; a[i]=a[k]; a[k]=t;

19、},#define N 10main(){ int a[N],i,j,t,k; for(i=0;i<N;i++)scanf(“%d”,&a[i]); for(i=0;i<N-1;i++) { k=i; for(j=i+1;j<N;j++) if(a[j]<a[k])k=j; t=a[i]; a[i]=a[k]; a[k]=t; } for

20、(j=0;j<N;j++) printf(“%3d”,a[j]); }eg7-8,5 8 7 4 3 9 0 1 2 6,起泡法基本思想： 首先將所有數(shù)中的最大值“冒泡”到最后位置，再將剩下的數(shù)中的最大值“冒泡”到上一位置，┈┈，依次類推，共進(jìn)行9次“冒泡”。 每次“冒泡”都是一種翻滾過程，即相鄰兩個(gè)數(shù)進(jìn)行比較換位。 5 8 7 4 3 9 0 1 2 6,,,,,,,,,,

21、,,,,#define N 10main(){ int a[N],i,j,t; for(i=0;ia[j+1]) {t= a[j]; a[j]= a[j+1]; a[j+1]=t;} for(j=0;j<N;j++) printf(“%3d”,a[j]); } 要特別注意兩個(gè)循環(huán)的范圍。eg7-9,5 8 7 4 3 9 0 1 2 6,(5) 循環(huán)移位 對(duì)一數(shù)列中

22、的每個(gè)數(shù)向后移3個(gè)位置，最后3個(gè)數(shù)移到最前面。 5 8 7 4 3 9 0 1 2 6 1 2 6 5 8 7 4 3 9 0,,用循環(huán)移位實(shí)現(xiàn)： 5 8 7 4 3 9 0 1 2 6main(){ int i,j,k,a[10

23、]; for(i=0;i<10;i++)scanf(“%d”,&a[i]);  for(i=0;i<10;i++)printf(“%3d”,a[i]); } eg7-10,for(i=1;i<10;i++)a[i]=a[i-1];,for(i=9;i>0;i--)a[i]=a[i-1];,k=a[9];,a[0]=k;,for(j=1;j<=3;j++){

24、k=a[9];,},用循環(huán)移位實(shí)現(xiàn)： 5 8 7 4 3 9 0 1 2 6#define N 10#define M 3void main(){int i,j,k,a[N];for(i=0;i0;i--) a[i]=a[i-1];a[0]=k;}for(i=0;i<N;i++) printf("%3d,",a[i]);}eg7-10,(6)狐貍找兔子問題

25、 圍繞著山頂有10個(gè)洞，一只兔子和一只狐貍分別住在洞里，狐貍總想吃掉兔子；一天，兔子對(duì)狐貍說：你想吃掉我有一個(gè)條件，先把洞順序編號(hào)，你從最后一個(gè)洞出發(fā)，第一次先到第一個(gè)洞找我，第二次隔一個(gè)洞找，第三次隔兩個(gè)洞找，┈，依次類推，尋找次數(shù)不限，我躲在一個(gè)洞里不動(dòng)，只要找到我你就可以飽餐一頓。狐貍一想只有10個(gè)洞，尋找次數(shù)又不限，那有找不到的呢？馬上答應(yīng)了條件，結(jié)果狐貍跑斷了腿也沒找到，請(qǐng)問兔子躲在哪個(gè)洞里？,,0,1,2,3,5,6,

26、7,8,9,4,,算法思想： 開辟數(shù)組，每個(gè)元素代表一個(gè)洞，并賦初值0，表示各個(gè)洞都還未找，然后按規(guī)律找，每找一個(gè)洞，對(duì)應(yīng)的數(shù)組元素就賦值1，表示已找過，┈┈，最后根據(jù)數(shù)組元素值1與0來識(shí)別各洞是否已找過。,main(){ int i, k=9; int a[10]={0}; for(i=0;i<=10000;i++) { k=(k+i)%10; a[k]=1;  } f

27、or(i=0;i<10;i++) if(a[i]==0) printf(“%3d”,i+1); }eg7-11,7．3 二維數(shù)組的定義和引用 ■定義 一般形式：類型符 數(shù)組名[常量表達(dá)式] [常量表達(dá)式]； int a[3][4]; float b[5][10];  行 列,,,二維數(shù)組的邏輯結(jié)構(gòu)就如同一張表格： a[

28、0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3]   存放形式：按行存放。,,,,,,,,,,a[0],a[1],a[2],二維數(shù)組可以看作是一個(gè)特殊的一維數(shù)

29、組，它的元素又是一個(gè)一維數(shù)組。C語言這樣的處理方法在很多情況下顯得很方便。 與一維數(shù)組相比，二維數(shù)組的定義多一個(gè)長度，其元素多一個(gè)下標(biāo)。 在應(yīng)用中，如果要處理的數(shù)據(jù)如同一數(shù)列，則可定義一維數(shù)組來存放；而如果要處理的數(shù)據(jù)如同一張表格，則應(yīng)定義二維數(shù)組來存放。,■引用 引用形式：數(shù)組名[下標(biāo)][下標(biāo)] 如：a[0][3]=a[1][2]+a[2][3]; 其元素有兩個(gè)下標(biāo)。 例：從鍵盤輸入12個(gè)數(shù)到二維數(shù)

30、組中。 int a[3][4],i,j; for(i=0;i<3;i++) for(j=0;j<4;j++) scanf(“%d”,&a[i][j]);需要用兩重循環(huán)來控制兩個(gè)下標(biāo)的變化。,如果鍵盤輸入的數(shù)據(jù)是：1 2 3 4 5 6 7 8 9 10 11 12, 則在數(shù)組中如何存放？兩個(gè)循環(huán)換位呢？兩個(gè)下標(biāo)換位呢？  int a[3][4],i,j; for(i

31、=0;i<3;i++) for(j=0;j<4;j++) scanf(“%d”,&a[i][j]);   eg7-12-1、 eg7-12-2、 eg7-12-3,for(j=0;j<4;j++) for(i=0;i<3;i++) scanf(“%d”,&a[i][j]);,int a[4][3],i,j; for(i=0;i<3;i++)

32、 for(j=0;j<4;j++) scanf(“%d”,&a[j][i]);,例：輸入一個(gè)表格的數(shù)據(jù)到二維數(shù)組中，并找最 大值所在的位置eg7-13main(){ int a[3][4],i,j,i1,j1; for(i=0;ia[i1][j1]){i1=i; j1=j;} printf(“\n %d,%d”,i1,j1); },■初始化 對(duì)二維數(shù)組賦初值的幾種方法： int

33、 a[3][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12}}; int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12}; int a[3][4]={{1},{5},{9}}; int a[3][4]={{1},{0,6},{0,0,11}}; int a[3][4]={{1},{5,6}}; int a[3][4]={{1},{0},{9}}; int a[]

34、[4]={1,2,3,4,5,6,7,8,9,10,11,12}; int a[][4]={{0,0,3},{0},{9,10}};,■ 舉例（1）矩陣的基本操作 二維數(shù)組的邏輯結(jié)構(gòu)就如同一個(gè)矩陣，因此，矩陣操作都可用二維數(shù)組實(shí)現(xiàn)。,a11 a12 a13 … a1na21 a22 a23 … a2na31 a32 a33 … a3n

35、 … … … …am1 am2 am3 … amn,,,,,,,A=,,假定M=3，N=4,求和：#define M 3#define N 4main(){ int a[M][N],i,j,s=0; ┈┈┈ for(i=0;i<M;i++) for(j=0;j<N;j++) s+=a[i][j]; ┈┈┈ } 上三角？下

36、三角？主對(duì)角線？eg7-14-1、 eg7-14-2、 eg7-14-3、 eg7-14-4、 eg7-14-5,for(i=0;i<M;i++) for(j=i;j<N;j++) s+=a[i][j];,for(i=0;i<M;i++) for(j=0;j<=i;j++) s+=a[i][j];,for(i=0;i<M;i++) for(j=i;j<=i;j++) s+=a[i][j];,f

37、or(i=0;i<M;i++) s+=a[i][i];,1 2 3 45 6 7 89 10 11 12,非方陣轉(zhuǎn)置：aij→bji#define M 3#define N 4main(){ int a[M][N],b[N][M],i,j; ┈┈┈ for(i=0;i<M;i++) for(j=0;j<N;j++) b[j][i]=a

38、[i][j]; ┈┈┈ }eg7-15,1 2 3 45 6 7 89 10 11 12,1 5 9 2 6 103 7 114 8 12,,方陣轉(zhuǎn)置：aij∽aji#define M 3main(){ int a[M][M],i,j,t; ┈┈┈ for(i=0; i<M; i++) for(j=0; j<

39、M; j++) {t=a[i][j]; a[i][j]=a[j][i]; a[j][i]=t;} ┈┈┈ }eg7-16-1、 eg7-16-2,1 2 34 5 67 8 9,for(j=i+1; j<M; j++),1 2 34 5 67 8 9,1 4 72 5 83 6 9,將矩陣中和值為最大的那一行元素與首行對(duì)換。#defi

40、ne M 3#define N 4main(){ int a[M][N],i,j,t,s,smax=-32768,row; ┈┈┈ for(i=0;ismax) {smax=s; row=i;} } for(j=0;j<N;j++) {t=a[0][j];a[0][j]=a[row][j]; a[row][j]=t;} ┈┈┈} eg7-17,1 5 3 8

41、4 6 1 79 2 5 6,9 2 5 64 6 1 71 5 3 8,,7．4 字符數(shù)組 用于存放字符的數(shù)組稱字符數(shù)組。 字符數(shù)組的每一個(gè)元素存放一個(gè)字符。 字符數(shù)組的獨(dú)特之處： （1）字符數(shù)組可以看作字符串變量。 （2）對(duì)字符數(shù)組可以進(jìn)行某些整體操作。 （3）有專用的字符串處理函數(shù)。,1、將字符數(shù)組

42、作為字符串變量 char c[10]; 給c分配10個(gè)字節(jié)的內(nèi)存單元。 把c看作數(shù)組時(shí)，按數(shù)組元素的形式訪問： c[0]=’a’; c[1]=’b’; c[2]=’c’; c[3]=’d’; a b c d char c[10]={‘a(chǎn)’,’b’,’c’,’d’} ; 也屬于字符賦初值的形式。,,,,,,,,,,,,,,如果把字符序列看作一個(gè)整體（字符串），則c就可

43、看作是存放這個(gè)字符串的串變量；但必須在字符序列后加上“字符串結(jié)束標(biāo)志”后，才能成為完整的字符串。 如：c[4]=’\0’; 或 c[4]=0;a b c d \0 也可以按字符串形式初始化： char c[10]=”abcd”; a b c d \0 \0 \0 \0 \0 \0 char c[]=”abcd”; 分配5個(gè)字節(jié) a b c d \0,2、對(duì)字符數(shù)組的整體操作 對(duì)

44、字符數(shù)組的有些操作可以整體進(jìn)行，如輸入輸出。 for(i=0;i<10;i++) printf(“%c”,c[i]); 對(duì)數(shù)組元素操作 printf(“%s”,c); 整體操作 注意以上兩種操作有區(qū)別。 可將前者改為： for(i=0;c[i]!=’\0’;i++)printf(“%c”,c[i]);,對(duì)于輸入： for(i=0;i<1

45、0;i++) scanf(“%c”,&c[i]); 對(duì)數(shù)組元素操作 scanf(“%s”,c); 整體操作 對(duì)字符數(shù)組輸入輸出可以整體進(jìn)行，但不允許整體賦值： char c[10]=”abcd”,x[10]; x=c; 不允許eg7-string.c,對(duì)于二維字符數(shù)組，可以看作是一維的字符串?dāng)?shù)組。 例：從鍵盤輸入10個(gè)人的名字到

46、計(jì)算機(jī)：#define M 20#define N 10 main() { int i; char name[N][M]; 10個(gè)元素的一維字符串?dāng)?shù)組 for(i=0;i<N;i++) scanf(“%s”,name[i]); … } 只給一個(gè)下標(biāo)eg7-18,,3、字符串處理函數(shù) c語言的函數(shù)庫中提供了一系列專用于字符串處理的函數(shù)，需要

47、時(shí)可直接調(diào)用。 使用字符串處理函數(shù)需要包含頭文件string.h （1）puts(字符串) 用于輸出字符串。 其中字符串可以是字符串常量，也可以是字符數(shù)組。 例：eg7-puts.c char str[]=”China”; puts(str); puts(”China”); 兩個(gè)輸出等效,（2）gets(字符數(shù)組) 用于從鍵盤輸入一個(gè)字符串到字符數(shù)組中。 函數(shù)返回字符數(shù)組的起始地址。

48、 例：eg7-gets.c char str[10]; gets(str); 執(zhí)行該函數(shù)調(diào)用時(shí)，計(jì)算機(jī)等待輸入字符串,（3）strcat(字符數(shù)組,字符串) 用于將字符串連接到字符數(shù)組的后面。 其中字符串可以是字符串常量，也可以是字符數(shù)組。 例：eg7-strcat.c char a[10]=”abcd”, b[10]=”xyz”; strcat(a,b); 與str

49、cat(a,”xyz”)等效 puts(a); 輸出結(jié)果是：abcdxyz,（4） strcpy(字符數(shù)組,字符串） 用于將字符串拷貝到字符數(shù)組中。 其中字符串可以是字符串常量，也可以是字符數(shù)組。 例：eg7-strcpy.c char a[10], b[10]=”abcdef”; strcpy(a,b); 與strcpy(a,”abcdef”)等效 不能用a

50、=b 賦值 puts(a); 輸出結(jié)果是：abcdef,（5） strcmp(字符串1，字符串2) 用于比較兩個(gè)字符串的大小。 比較結(jié)果通過函數(shù)的返回值體現(xiàn)： 字符串1=字符串2時(shí)：返回0。 字符串1>字符串2時(shí)：返回一正整數(shù)。 字符串1<字符串2時(shí)：返回一負(fù)整數(shù)。,兩個(gè)字符串之間誰大誰小取決于最先有差異的兩個(gè)字符的ASCII代碼的大小。 如： strcmp(“abcde”,”abcde

51、”); 返回0 strcmp(“abcdefgh”,”abcxyz”)；返回負(fù)整數(shù) strcmp(“a”,”ABCD”)； 返回正整數(shù),例：從鍵盤輸入兩個(gè)字符串，輸出其中大的一個(gè)。#include “string.h” main(){ char a[10],b[10]; gets(a); gets(b); if(strcmp(a,b)>0) puts(a); 不能用a>

52、b else puts(b); }eg7-strcmp.c,（6） strlen(字符數(shù)組) 測(cè)試字符串的實(shí)際長度（從返回值得到）。 （7） strlwr(字符串) 將字符串中的大寫字母全改為小寫字母。 （8） strupr(字符串) 將字符串中的小寫字母全改為大寫字母。 注意：在使用字符串處理函數(shù)時(shí)，別忘了將頭文件string.h包含進(jìn)去。eg7-strfuc.c,4、字符串

53、操作舉例（1）從鍵盤輸入一字符串到數(shù)組a中，再拷貝到數(shù)組b中（不用庫函數(shù)）。 eg7-strcpy.c main() { char a[50],b[50]; int i; scanf(“%s”,a); for(i=0; a[i]; i++) b[i]=a[i]; b[i]=0; printf(“%s”,b); },（2）從鍵盤輸入兩個(gè)字符串到數(shù)組a和b中，在將b中的內(nèi)容連接到a中

54、（不用庫函數(shù)）。main(){ char a[50],b[50]; int i,j; scanf(“%s%s”,a,b); for(i=0; a[i]; i++); for(j=0; b[j]; j++) a[i++]=b[j]; a[i]=0; printf(“%s”,a);} eg7-strcat.c,（3）從鍵盤輸入一字符串，并將其中的大寫字母改成小寫字母后輸出（不用庫