第七章-數(shù)組數(shù)據(jù)結(jié)構(gòu)與數(shù)組的概念-影響程序設(shè)計的因素優(yōu)秀文檔

第七章數(shù)組

7．1數(shù)據(jù)結(jié)構(gòu)與數(shù)組的概念

影響程序設(shè)計的因素除算法外還有數(shù)據(jù)結(jié)構(gòu)?！鰯?shù)據(jù)結(jié)構(gòu)概念

編寫一個程序除了重視算法的設(shè)計外，還需重視數(shù)據(jù)類型的選擇，即選擇合適的數(shù)據(jù)類型來存放要處理的數(shù)據(jù)。在程序設(shè)計中，數(shù)據(jù)類型就稱為數(shù)據(jù)結(jié)構(gòu)，選擇合適的數(shù)據(jù)類型實際上就是進行數(shù)據(jù)結(jié)構(gòu)的設(shè)計。在程序設(shè)計中有格言：

數(shù)據(jù)結(jié)構(gòu)+算法=程序說明數(shù)據(jù)結(jié)構(gòu)與算法同等重要，算法依賴于數(shù)據(jù)結(jié)構(gòu)，對于同一個問題的求解，可以采用不同的數(shù)據(jù)結(jié)構(gòu)和不同的算法，對不同的數(shù)據(jù)結(jié)構(gòu)有不同的算法，其復(fù)雜程度也會不同，選擇合適的數(shù)據(jù)結(jié)構(gòu)，可以降低算法的復(fù)雜程度。因此，在程序設(shè)計中應(yīng)重視數(shù)據(jù)結(jié)構(gòu)的設(shè)計。例：求任意100個數(shù)中的最大值。main(){inti,a,max;max=-32768for(i=1;i<=100;i++){scanf(“%d”,&a);if(a>max)max=a;}printf(“\nmax=%d”,max);}用一個簡單變量作為數(shù)據(jù)結(jié)構(gòu)，合理，算法簡單

對于三個數(shù)的排序：main(){inta,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,c);}對于很多個數(shù)的排序用變量會很復(fù)雜而用數(shù)組會使算法很簡單。仍可用變量作為數(shù)據(jù)結(jié)構(gòu)■數(shù)組的概念inta[10]a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]

一組具有同樣類型的數(shù)據(jù)的集合統(tǒng)一用一個名字代表---數(shù)組名（代表一組數(shù)）數(shù)組元素下標(biāo)數(shù)組名

數(shù)組中的各成員稱數(shù)組元素，由數(shù)組名加下標(biāo)唯一地確定。

將一組數(shù)用一個名字代表，便于管理。只有一個下標(biāo)的數(shù)組稱為一維數(shù)組；可有二維數(shù)組、三維數(shù)組、…、七維數(shù)組。7．2一維數(shù)組的定義和引用

■定義

一般形式：類型符數(shù)組名[常量表達式]；

int

a[10];floatb[10]；

類型符數(shù)組名長度

作用：分配一組連續(xù)的內(nèi)存單元說明：

●數(shù)組必須先定義后使用。

●數(shù)組名的命名規(guī)則與變量相同。

●常量表達式表示元素的個數(shù)（長度），下標(biāo)從0開始。

●常量表達式不能包含變量，即不允許作動態(tài)定義?！鲆?/p>

逐個引用其元素，不能進行整體引用。

引用的一般形式：

數(shù)組名[下標(biāo)]

如：a[0]=50;a[1]=100;a[2]=a[0]+a[1];

與a2=a0+a1有根本性的區(qū)別：下標(biāo)可變。用數(shù)組作為存放初始數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)0？{inti,a,n[101];0？if(s>smax){smax=s;row=i;}for(j=0;j<4;j++)for(i=1;i<=100;i++)printf(“\n%3d:%3d”,i,n[i]);{inta[3][4],i,j,t,s,smax=-32768,row;存放形式：按行存放。字符串1=字符串2時：返回0。printf(“\n%3d:%3d”,i,n[i]);scanf(“%s”,a);例：從鍵盤輸入10個數(shù)。用變量：(不方便)scanf(“%d%d%d%d%d%d%d%d%d%d”，&a0,&a1,&a2,&a3,&a4,&a5,&a6,&a7,&a8,&a9);用數(shù)組：(靈活方便)for(i=0;i<10;i++)scanf(“%d”,&a[i]);

用循環(huán)控制輸入個數(shù)和下標(biāo)的變化。

注意下標(biāo)的變化范圍?！龀跏蓟?/p>

在定義數(shù)組的同時給數(shù)組賦初值。inta[10]={0,1,2,3,4,5,6,7,8,9};inta[10]={0,1,2,3,4};inta[]={0,1,2,3,4};■應(yīng)用舉例（1）對100個學(xué)生的分?jǐn)?shù)統(tǒng)計最高分、最低分和平均分。

兩種方法：用變量作為存放初始數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)用數(shù)組作為存放初始數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)main(){inti,a,max,min;floataver=0;max=0;min=100;for(i=0;i<100;i++){scanf(“%d”,&a);if(a>max)max=a;if(a<min)min=a;aver+=a;}aver/=100;printf(“\n%d,%d,%f”,max,min,aver);}用變量

main(){inti,a[100],max,min;floataver=0;for(i=0;i<100;i++)scanf(“%d”,&a[i]);max=a[0];min=a[0];for(i=0;i<100;i++){if(a[i]>max)max=a[i];if(a[i]<min)min=a[i];aver+=a[i];}aver/=100;printf(“\n%d,%d,%f”,max,min,aver)；}用數(shù)組找最大最小的位置？max=0;min=0;if(a[i]>a[max])max=i;if(a[i]<a[min])min=i;

（2）統(tǒng)計高于平均分的人數(shù)。main(){inti,a,n;floataver=0;for(i=0;i<100;i++){scanf(“%d”,&a);aver+=a;}aver/=100;

n=0;for(i=0;i<100;i++){scanf(“%d”,&a);if(a>aver)n++;}printf(“\n%d”,n);}用變量數(shù)據(jù)結(jié)構(gòu)不合理main(){inti,a[100],n;floataver=0;for(i=0;i<100;i++)scanf(“%d”,&a[i]);for(i=0;i<100;i++)aver+=a[i];aver/=100;n=0;for(i=0;i<100;i++)if(a[i]>aver)n++;printf(“\n%d”,n);}

用數(shù)組1（3）對100個學(xué)生的分?jǐn)?shù)統(tǒng)計出每分一檔人數(shù)。0？1？2

？

3

？

4

？┇┇99？100？main(){inti,a;

for(i=1;i<=100;i++){scanf(“%d”,&a);

}

輸出}inti,a,n[101];for(i=0;i<101;i++)n[i]=0;n[a]++;完整程序：main(){inti,a,n[101];for(i=0;i<101;i++)n[i]=0;

for(i=1;i<=100;i++){scanf(“%d”,&a);n[a]++;

}for(i=100;i>=0;i--)printf(“\n%3d:%3d”,i,n[i]);}體會數(shù)組作為存放結(jié)果的數(shù)據(jù)結(jié)構(gòu)時的優(yōu)越性。按10分一檔統(tǒng)計？main(){inti,a,n[101];for(i=0;i<101;i++)n[i]=0;

for(i=1;i<=100;i++){scanf(“%d”,&a);n[a]++;

}}inti,a,n[11];for(i=0;i<11;i++)n[i]=0;n[a/10]++;（4）對10個學(xué)生的分?jǐn)?shù)按從小到大的順序排序后輸出。

兩種典型的排序算法：選擇法和起泡法。選擇法基本思想：首先選擇最小的數(shù)放在0位置，再在剩下的數(shù)中選擇最小的數(shù)放在下一位置，┈┈，依次類推，共進行9次選擇。

5874390126每次選擇都要與其后的所有數(shù)進行比較換位。

5874390126

ijmain(){inta[10],i,j,t;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(i=0;i<9;i++)for(j=i+1;j<10;j++)if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}5874390126

5874390126

ij

先找最小值所在的位置，最后再換位:main(){inta[10],i,j,t,k;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(i=0;i<9;i++){k=i;for(j=i+1;j<10;j++)if(a[j]<a[k])k=j;t=a[i];a[i]=a[k];a[k]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}起泡法基本思想：

首先將所有數(shù)中的最大值“冒泡”到最后位置，再將剩下的數(shù)中的最大值“冒泡”到上一位置，┈┈，依次類推，共進行9次“冒泡”。每次“冒泡”都是一種翻滾過程，即相鄰兩個數(shù)進行比較換位。5874390126main(){inta[10],i,j,t;for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(j=1;j<=9;j++)for(i=0;i<10-j;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}for(j=0;j<10;j++)printf(“%3d”,a[j]);}要特別注意兩個循環(huán)的范圍。

（(5)循環(huán)移位

對一數(shù)列中的每個數(shù)向后移3個位置，最后3個數(shù)移到最前面。5874390126

1265874390用循環(huán)移位實現(xiàn)：5874390126main(){inti,j,k,a[10];for(i=0;i<10;i++)scanf(“%d”,&a[i]);

for(i=0;i<10;i++)printf(“%3d”,a[i]);}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++){k=a[9];}

(6)狐貍找兔子問題繞圍繞著山頂有10個洞，一只兔子和一只狐貍分別住在洞里，狐貍總想吃掉兔子；一天，兔子對狐貍說：你想吃掉我有一個條件，先把洞順序編號，你從最后一個洞出發(fā)，第一次先到第一個洞找我，第二次隔一個洞找，第三次隔兩個洞找，┈，依次類推，尋找次數(shù)不限，我躲在一個洞里不動，只要找到我你就可以飽餐一頓。狐貍一想只有10個洞，尋找次數(shù)又不限，那有找不到的呢？馬上答應(yīng)了條件，結(jié)果狐貍跑斷了腿也沒找到，請問兔子躲在哪個洞里？12346789105用于輸出字符串。{chara[50];而如果要處理的數(shù)據(jù)如同一張表格，則應(yīng)定義二維數(shù)組來存放。…………{inta[3][4],b[4][3],i,j;max=a[0];min=a[0];aver/=100;a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]（1）對100個學(xué)生的分?jǐn)?shù)統(tǒng)計最高分、最低分和平均分。要特別注意兩個循環(huán)的范圍。scanf(“%d%d%d%d%d%d%d%d%d%d”，for(i=1;i<=100;i++)for(i=0;a[i];i++){s=0;for(j=0;j<4;j++)s+=a[i][j];if(a[i]==0)printf(“%3d”,i+1);與a2=a0+a1有根本性的區(qū)別：下標(biāo)可變。對數(shù)組元素操作算法思想：

開辟數(shù)組，每個元素代表一個洞，并賦初值0，表示各個洞都還未找，然后按規(guī)律找，每找一個洞，對應(yīng)的數(shù)組元素就賦值1，表示已找過，┈┈，最后根據(jù)數(shù)組元素值1與0來識別各洞是否已找過。main(){inti,k=10;inta[10]={0,0,0,0,0,0,0,0,0,0};for(i=1;i<=10000;i++){

k=(k+i)%10;if(k==0)k=10;

a[k-1]=1;

}for(i=0;i<10;i++)if(a[i]==0)printf(“%3d”,i+1);}7．3二維數(shù)組的定義和引用■定義

一般形式：類型符數(shù)組名[常量表達式][常量表達式]；inta[3][4];floatb[5][10];

行列

二維數(shù)組的邏輯結(jié)構(gòu)就如同一張表格：

a[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ù)組可以看作是一個特殊的一維數(shù)組，它的元素又是一個一維數(shù)組。C語言這樣的處理方法在很多情況下顯得很方便。

與一維數(shù)組相比，二維數(shù)組的定義多一個長度，其元素多一個下標(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];

其元素有兩個下標(biāo)。

例：從鍵盤輸入12個數(shù)到二維數(shù)組中。inta[3][4],i,j;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);需要用兩重循環(huán)來控制兩個下標(biāo)的變化。

如果鍵盤輸入的數(shù)據(jù)是：123456789101112,則在數(shù)組中如何存放？兩個循環(huán)換位呢？兩個下標(biāo)換位呢？

inta[3][4],i,j;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);

for(j=0;j<4;j++)for(i=0;i<3;i++)scanf(“%d”,&a[i][j]);for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[j][i]);例：輸入一個表格的數(shù)據(jù)到二維數(shù)組中，并找最大值所在的位置main(){inta[3][4],i,j,i1,j1;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf(“%d”,&a[i][j]);

i1=0;j1=0;for(i=0;i<3;i++)for(j=0;j<4;j++)

if(a[i][j]>a[i1][j1]){i1=i;j1=j;}printf(“\n%d,%d”,i1,j1);}■初始化

對二維數(shù)組賦初值的幾種方法：

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

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

inta[3][4]={{1},{5},{9}};

inta[3][4]={{1},{0,6},{0,0,11}};

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

inta[][4]={{0,0,3},{},{9,10}};■舉例（1）矩陣的基本操作二維數(shù)組的邏輯結(jié)構(gòu)就如同一個矩陣，因此，矩陣操作都可用二維數(shù)組實現(xiàn)。a11a12a13

…a1na21a22a23

…

a2na31a32a33

…

a3n

…………am1am2am3

…amnA=假定M=3，N=4

求和：main(){inta[4][4],i,j,s=0;┈┈┈for(i=0;i<4;i++)for(j=0;j<4;j++)s+=a[i][j];┈┈┈}上三角？下三角？主對角線？for(i=0;i<4;i++)for(j=i;j<4;j++)s+=a[i][j];for(i=0;i<4;i++)for(j=0;j<=i;j++)s+=a[i][j];for(i=0;i<4;i++)for(j=i;j<=i;j++)s+=a[i][j];for(i=0;i<4;i++)s+=a[i][i];1234567810111213141516非方陣轉(zhuǎn)置：aij→bjimain(){inta[3][4],b[4][3],i,j;┈┈┈for(i=0;i<3;i++)for(j=0;j<4;j++)b[j][i]=a[i][j];┈┈┈}123456789101112159261037114812方陣轉(zhuǎn)置：aij∽ajimain(){inta[3][3],i,j,t;┈┈┈for(i=0;i<3;i++)for(j=0;j<3;j++){t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}┈┈┈}123456789for(j=i+1;j<3;j++)將矩陣中和值為最大的那一行元素與首行對換。main(){inta[3][4],i,j,t,s,smax=-32768,row;┈┈┈for(i=0;i<3;i++){s=0;for(j=0;j<4;j++)s+=a[i][j];if(s>smax){smax=s;row=i;}}for(j=0;j<4;j++){t=a[0][j];a[0][j]=a[row][j];a[row][j]=t;}┈┈┈}1538461792567．4字符數(shù)組

用于存放字符的數(shù)組稱字符數(shù)組。字符數(shù)組的每一個元素存放一個字符。

字符數(shù)組的獨特之處：（1）字符數(shù)組可以看作字符串變量。（2）對字符數(shù)組可以進行某些整體操作。（3）有專用的字符串處理函數(shù)。

1、將字符數(shù)組作為字符串變量charc[10];給c分配10個字節(jié)的內(nèi)存單元。把c看作數(shù)組時，按數(shù)組元素的形式訪問：

c[0]=’a’;c[1]=’b’;c[2]=’c’;c[3]=’d’;

abcdcharc[10]={‘a(chǎn)’,’b’,’c’,’d’};也屬于字符賦初值的形式。如果把字符序列看作一個整體（字符串），則c就可看作是存放這個字符串的串變量；但必須在字符序列后加上“字符串結(jié)束標(biāo)志”后，才能成為完整的字符串。

如：c[4]=’\0’;或c[4]=0;

abcd\0也可以按字符串形式初始化：charc[10]=”abcd”;charc[]=”abcd”;分配5個字節(jié)2、對字符數(shù)組的整體操作對字符數(shù)組的有些操作可以整體進行，如輸入輸出。

for(i=0;i<10;i++)printf(“%c”,c[i]);

對數(shù)組元素操作

printf(“%s”,c);

整體操作注意以上兩種操作有區(qū)別。

可將前者改為：for(i=0;c[i]!=’\0’;i++)printf(“%c”,c[i]);對于輸入：

for(i=0;i<10;i++)scanf(“%c”,&c[i]);

對數(shù)組元素操作

scanf(“%s”,c);

整體操作對字符數(shù)組輸入輸出可以整體進行，但不允許整體賦值：

charc[10]=”abcd”,x[10];x=c;

不允許對于二維字符數(shù)組，可以看作是一維的字符串?dāng)?shù)組。例：從鍵盤輸入10個人的名字到計算機：main(){inti;charname[10][20];10個元素的一維字符串?dāng)?shù)組for(i=0;i<10;i++)scanf(“%s”,name[i]);…}

只給一個下標(biāo)將矩陣中和值為最大的那一行元素與首行對換。{chara[50],b[50];5874390126（5）strcmp(字符串1，字符串2)for(i=1;i<=100;i++)printf(“\n%3d:%3d”,i,n[i]);for(i=0;i<3;i++)for(j=i+1;j<10;j++)if(a[j]<a[k])k=j;inti,a,n[101];if(b<c){t=b;b=c;c=t;}注意下標(biāo)的變化范圍。用數(shù)組：(靈活方便)影響程序設(shè)計的因素除算法外還有數(shù)據(jù)結(jié)構(gòu)。首先選擇最小的數(shù)放在0位置，再在剩下的數(shù)中選擇最小的數(shù)放在下一位置，┈┈，依次類推，共進行9次選擇。scanf(“%s”,a);{scanf(“%d”,&a);3、字符串處理函數(shù)

c語言的函數(shù)庫中提供了一系列專用于字符串處理的函數(shù)，需要時可直接調(diào)用。（1）puts(字符串)用于輸出字符串。其中字符串可以是字符串常量，也可以是字符數(shù)組。

例：charstr[]=”China”;puts(str);puts(”China”);兩個輸出等效（2）gets(字符數(shù)組)用于從鍵盤輸入一個字符串到字符數(shù)組中。函數(shù)返回字符數(shù)組的起始地址。例：charstr[10];gets(str);

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

輸出結(jié)果是：abcdxyz（4）strcpy(字符數(shù)組,字符串）用于將字符串拷貝到字符數(shù)組中。其中字符串可以是字符串常量，也可以是字符數(shù)組。

例：chara[10],b[10]=”abcdef”;strcpy(a,b);與strcpy(a,”abcdef