高級(jí)語(yǔ)言程序設(shè)計(jì)基礎(chǔ)（C C++）：數(shù)組 把數(shù)串起來

共43頁(yè)第1

頁(yè)數(shù)組：把數(shù)串起來共43頁(yè)第2

頁(yè)數(shù)組的基本概念一維數(shù)組二維數(shù)組應(yīng)用實(shí)例

1234數(shù)組共43頁(yè)第3

頁(yè)1數(shù)組的基本概念如何處理一個(gè)班學(xué)生的學(xué)習(xí)成績(jī)？一行文字怎樣存儲(chǔ)？一個(gè)矩陣怎樣存儲(chǔ)？......

數(shù)組一組具有相同數(shù)據(jù)類型的數(shù)據(jù)的有序集合

？這些數(shù)據(jù)的特點(diǎn)：具有相同的數(shù)據(jù)類型。

為了很方便地使用這些數(shù)據(jù)，C語(yǔ)言提供了一種構(gòu)造數(shù)據(jù)類型：數(shù)組。共43頁(yè)第4

頁(yè)其中：mark、str、a是數(shù)組名。方括號(hào)內(nèi)是數(shù)組的長(zhǎng)度。下標(biāo)的個(gè)數(shù)稱為數(shù)組的維數(shù)，mark、str是一維數(shù)組、a是二維數(shù)組。數(shù)組的成員稱為數(shù)組元素。數(shù)組元素的類型稱為該數(shù)組的基類型。數(shù)組mark的基類型是int，數(shù)組str的基類型是char。1數(shù)組的基本概念（續(xù)）例如：存儲(chǔ)學(xué)生成績(jī)用整型數(shù)組

mark[100]，

存儲(chǔ)一行文字用字符數(shù)組

str[200]，

存儲(chǔ)一個(gè)4*6的矩陣用二維整型數(shù)組

a[4][6]。共43頁(yè)第5

頁(yè)2一維數(shù)組一、一維數(shù)組的定義數(shù)據(jù)類型： 數(shù)組的基類型常量表達(dá)式： 數(shù)組的大小例如：float

mark[100];

char

str[200];

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式]

數(shù)組名:

對(duì)數(shù)組的標(biāo)識(shí)，遵循C語(yǔ)言標(biāo)識(shí)符規(guī)則。

mark、str是數(shù)組名。共43頁(yè)第6

頁(yè)常量表達(dá)式是數(shù)組元素的個(gè)數(shù)，即數(shù)組長(zhǎng)度。它必須是常量。

mark的長(zhǎng)度是100

str的長(zhǎng)度是200

2一維數(shù)組（續(xù)）數(shù)據(jù)類型就是數(shù)組元素的數(shù)據(jù)類型，

數(shù)組元素的類型叫做數(shù)組的基類型。

mark是str是實(shí)型數(shù)組、字符數(shù)組下標(biāo)運(yùn)算符數(shù)組名后面的方括號(hào)[]是下標(biāo)運(yùn)算符。

不允許使用（）括號(hào)。共43頁(yè)第7

頁(yè)①floata[0];/*數(shù)組大小為0沒有意義*/②intb(2);/*不能使用圓括號(hào)*/③intk,a[k];/*不能用變量說明數(shù)組大小*/④intd[2.9];/*定義數(shù)組大小的表達(dá)式必須是整型常量表達(dá)式*/二、數(shù)組定義中常見的錯(cuò)誤2一維數(shù)組（續(xù)）

C語(yǔ)言不允許對(duì)數(shù)組的大小進(jìn)行動(dòng)態(tài)說明。數(shù)組的說明語(yǔ)句必須在可執(zhí)行語(yǔ)句之前。共43頁(yè)第8

頁(yè)在說明語(yǔ)句中，方括號(hào)內(nèi)的值是數(shù)組中元素的總數(shù)量。

如：inta[10]；說明數(shù)組a一共有10個(gè)元素?cái)?shù)組下標(biāo)的起始值是0。即，引用數(shù)組的第一個(gè)元素的下標(biāo)是0。數(shù)組a的10個(gè)元素分別是：a[0]、a[1]、…、a[9]。三、一維數(shù)組元素的引用2一維數(shù)組（續(xù)）

數(shù)組元素的引用方式：通過下標(biāo)引用數(shù)組元素，格式：數(shù)組名[下標(biāo)表達(dá)式]

下標(biāo):下標(biāo)表達(dá)式的值必須是整型數(shù)據(jù)。共43頁(yè)第9

頁(yè)數(shù)組中的每個(gè)元素在功能上等價(jià)于一個(gè)一般的變量。 例如：輸入100個(gè)學(xué)生成績(jī)，并求出總成績(jī)。2一維數(shù)組（續(xù)）使用數(shù)組：floatmark[100],sum;

for(i=0;i<100;i++)scanf(”%f”,&mark[i]);

for(sum=0,i=0;i<100;i++)sum+=mark[i];

引用數(shù)組元素的注意事項(xiàng)不用數(shù)組：floatx,sum;

for(i=0;i<100;i++){scanf(”%f”,&x);sum+=x;}共43頁(yè)第10

頁(yè)2一維數(shù)組（續(xù)）四、數(shù)組在內(nèi)存中的存放每個(gè)數(shù)據(jù)元素占用的字節(jié)數(shù)，就是基類型的字節(jié)數(shù)一個(gè)元素占4個(gè)字節(jié)一維數(shù)組：float

mark[100];mark[0]mark[1]mark[2]mark[3]...mark[99]86.592.077.552.0...94.0低地址

高地址共43頁(yè)第11

頁(yè)mark[0]mark[1]mark[2]mark[3]...mark[99]86.592.077.552.0...94.02000H2004H2008H200CH。。。218CH引用數(shù)組元素時(shí)，根據(jù)首地址和下標(biāo)，自動(dòng)計(jì)算出該元素的實(shí)際地址，取出該地址的內(nèi)容進(jìn)行操作。如引用mark[2]:(1)計(jì)算

2000+2*4=2008(2)從取出2008的內(nèi)容下標(biāo)與地址的關(guān)系2一維數(shù)組（續(xù)）

[]為下標(biāo)運(yùn)算符,

數(shù)組名、數(shù)組元素是兩種不同性質(zhì)的數(shù)據(jù)。

數(shù)組名是數(shù)組的首地址，是一個(gè)地址常量。

數(shù)組元素則是數(shù)值。共43頁(yè)第12

頁(yè)共78頁(yè)第12

頁(yè)可以對(duì)靜態(tài)或外部存貯類型的數(shù)組進(jìn)行初始化。在數(shù)組說明的同時(shí)進(jìn)行初始化的一般形式為：數(shù)據(jù)類型數(shù)組名[常量表達(dá)式1]…[常量表達(dá)式n]＝｛初始化數(shù)據(jù)｝；例如：說明一個(gè)1維數(shù)組并初始化，可以使用如下語(yǔ)句：

inta[4]={1,2,3,4}; 結(jié)果相當(dāng)于：a[0]=1;a[1]=2;a[2]=3;a[3]=4;

staticfloatx[5]={1.9,2.0};

相當(dāng)于：x[0]=1.9；x[1]=2.0；其余元素為0值。2一維數(shù)組（續(xù)）五、一維數(shù)組的初始化共43頁(yè)第13

頁(yè)共78頁(yè)第13

頁(yè)若要對(duì)數(shù)組的全部元素初始化，則可省略數(shù)組說明中的大小。

staticinta[]={1,2,3,4};對(duì)多維數(shù)組初始化時(shí)，可采用按行排列賦初值的方式。

inta[2][3]={{1,2,3},{4,5,6}}; 結(jié)果為： a[0][0]=1,a[0][1]=2,a[0][2]=3, a[1][0]=4,a[1][1]=5,a[1][2]=6也可按數(shù)組在內(nèi)存單元的存貯順序進(jìn)行初始化。

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

等價(jià)：inta[2][2][2]={

{1,2},

{3,4},

{5,6},

{7,8}

}; inta[2][2][2]={{{1,2},{3,4}},{{5,6},{7,8}}}2一維數(shù)組（續(xù)）共43頁(yè)第14

頁(yè)共78頁(yè)第14

頁(yè)若要對(duì)數(shù)組中的部分元素進(jìn)行初始化，可采用下例中的方法：

staticinta[2][3]={{1},{4}}; 結(jié)果為：a[0][0]=1,a[1][0]=4,其余元素均為0。

staticinta[3][3]={{1,2},{},{4,5,6}};

結(jié)果為：a[0][0]=1,a[0][1]=2,a[2][0]=4, a[2][1]=5,a[2][2]=6,其余元素均為0。對(duì)多維數(shù)組全部元素進(jìn)行初始化時(shí)，可省略數(shù)組說明中第一維的大小。例如：

staticinta[][3]={1,2,3,4,5,6};注意：此時(shí)只能省略第1維的值。C根據(jù)初始化數(shù)據(jù)的數(shù)量，自動(dòng)確定第1維的大小。2一維數(shù)組（續(xù)）共43頁(yè)第15

頁(yè)例1反向輸出數(shù)組中各元素的值。#include<stdio.h>voidmain(){ staticinta[5]={10,20,30,40,50};

/*說明一個(gè)數(shù)組并進(jìn)行初始化*/

inti=5;

while

(--i>=0) printf("a[%d]=%d\n",i,a[i]);/*循環(huán)控制變量i作為數(shù)組的下標(biāo)*/}2一維數(shù)組（完）輸出結(jié)果：a[4]=50,a[3]=40,a[2]=30,a[1]=20,a[0]=10六、一維數(shù)組的應(yīng)用共43頁(yè)第16

頁(yè)2一維數(shù)組-冒泡排序冒泡排序法思想：假設(shè)6個(gè)整數(shù)為7、-3、43、0、1和237-3430123i=0a[5]a[4]a[3]a[2]a[1]a[0]7-34302317-34323017-3432301743-32301437-32301437-32301437-32310437-3231043723-31043237-31043237-310i=1i=243237-310432371-30432371-30i=3432371-304323710-34323710-3i=44323710-34323710-3比較

a[j]

>

a[j+1]如果成立兩元素交換共43頁(yè)第17

頁(yè)2一維數(shù)組-冒泡排序（續(xù)）冒泡排序程序：當(dāng)n=6時(shí)，進(jìn)行程序抽象i=0a[5]a[4]a[3]a[2]a[1]a[0]437-3230143237-310i=1i=2432371-30i=34323710-3i=44323710-34

i控制外層循環(huán):

for(i=0;i<;i++)n-1

j

控制內(nèi)層循環(huán):

for(j=;j<;j++)0n-1n-1-in-i-1共43頁(yè)第18

頁(yè)程序說明與注釋 #include<stdio.h> #defineN6 voidmain() {inti,j,t,a[N];

for(i=0;i<N;i++){

/*輸入N個(gè)整數(shù)*/

printf(“EnterNo.%2d:",i+1); scanf("%d",&a[i]);

}

for(i=0;i<N-1;i++) /*進(jìn)行N-1輪比較*/

for(j=0;j<N-i-1;j++)/*比較數(shù)組中相鄰兩個(gè)元素*/

if(a[j]>a[j+1]){

t=a[j];a[j]=a[j+1];a[j+1]=t;

}

for(i=N-1;i>=0;i--) /*輸出排序結(jié)果*/

printf("%5d",a[i]); }2一維數(shù)組-冒泡排序（完）共43頁(yè)第19

頁(yè)冒泡排序的缺陷： 在比較交換的過程中大的數(shù)不能一次到位，效率低。2一維數(shù)組-選擇排序7-3430123a[5]a[4]a[3]a[2]a[1]a[0]7-34302317-34323017-3432301743-32301437-32301

選擇排序法的基本思想：以冒泡排序法為基礎(chǔ)，在兩兩比較后并不馬上進(jìn)行交換，而是在找到最小的數(shù)之后，記住最小數(shù)的位置（在數(shù)組中的下標(biāo)），待一輪比較完畢后，再將最小的數(shù)一次交換到位。共43頁(yè)第20

頁(yè)2一維數(shù)組-選擇排序（續(xù)）問題將23、1、0、43、-3和7從小到大排列。選擇排序法

若有N個(gè)數(shù)，則需要進(jìn)行N-1輪排序處理。第1輪排序從1～N個(gè)數(shù)中找出最小的數(shù)，然后將它與第1個(gè)數(shù)交換。第1個(gè)數(shù)則是最小的數(shù)。第2輪排序從2～N個(gè)數(shù)中找出最小的數(shù)，然后將它與第2個(gè)數(shù)交換。第2個(gè)數(shù)則是次小的數(shù)。經(jīng)過N-1輪處理，完成全部N個(gè)數(shù)排序。編程時(shí)使用二重循環(huán)。外面的大循環(huán)控制進(jìn)行N-1輪排序，小循環(huán)找出第

i

輪的最小值。共43頁(yè)第21

頁(yè)2一維數(shù)組-選擇排序（續(xù)）231043-3712345j=0-310

4323

7i=00初始p=1p=j則p=a[p]>a[j]j=12p=j則p=a[p]>a[j]j=2a[p]≯a[j]j=34p=j則p=a[p]>a[j]j=4a[p]≯a[j]j=5p!=i

進(jìn)行交換：t=a[i];a[i]=a[p];a[p]=t;

p：記錄當(dāng)前排序過程中最小值的下標(biāo)

第1輪排序過程共43頁(yè)第22

頁(yè)2一維數(shù)組-選擇排序（續(xù)）

-3104323712345j=0-3

0

14323

7i=11初始

p=2p=j則p=a[p]>a[j]j=2a[p]≯a[j]j=3a[p]≯a[j]j=4a[p]≯a[j]j=5p!=i

進(jìn)行交換：t=a[i];a[i]=a[p];a[p]=t;第2輪排序過程

p：記錄當(dāng)前排序過程中最小值的下標(biāo)

共43頁(yè)第23

頁(yè)程序說明與注釋#defineN6voidmain(){ inti,j,t,p,a[N];

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

{

printf("EnterNo.%2d:",i+1);scanf("%d",&a[i]);}

for(i=0;i<N-1;i++){ /*進(jìn)行N-1次比較*/

p=i; /*p中記錄當(dāng)前排序過程中最小元素的下標(biāo)*/

for(j=i+1;j<N;j++)

if(a[p]>a[j])p=j;/*若有更小的數(shù)則記錄下標(biāo)*/

if(p!=i) {t=a[p];a[p]=a[i];a[i]=t;}

/*一次交換到位*/

}

for

(i=0;i<N;i++)/*輸出排序后的結(jié)果*/

printf("%2d",a[i]);}2一維數(shù)組-選擇排序（續(xù)）共43頁(yè)第24

頁(yè)插入排序法的基本思想 假設(shè)：已經(jīng)存在一個(gè)長(zhǎng)度為N的有序(從小到大排列)的數(shù)據(jù)序列，要將一個(gè)新的數(shù)插入到該序列中，要求插入后的新序列(長(zhǎng)度為N+1)仍然保持有序。 算法的關(guān)鍵是要確定新數(shù)據(jù)插入的合適位置。 對(duì)于一個(gè)有序序列，從后向前進(jìn)行比較，若序列中的數(shù)大于要插入的數(shù)，則將數(shù)列中的數(shù)向后移動(dòng)；否則，完成插入操作。2一維數(shù)組-插入排序共43頁(yè)第25

頁(yè)

12345j=023

i=0第1輪排序過程有序序列的長(zhǎng)度n=0 新插入的數(shù)據(jù)

x=23k=0直接將x插入數(shù)組元素a[k]

中2一維數(shù)組-插入排序（續(xù)）共43頁(yè)第26

頁(yè)23

12345j=0

2323

i=1第2輪排序過程有序序列的長(zhǎng)度n=1 新插入的數(shù)據(jù)

x=1k=1 判斷a[k-1]>x？ 成立，a[k-1]后移

1

23

k=0

停止比較將x

插入到數(shù)組元素a[k]

中2一維數(shù)組-插入排序（續(xù)）共43頁(yè)第27

頁(yè)1 2312345j=0

12323i=2第3輪排序過程有序序列的長(zhǎng)度n=2 新插入的數(shù)據(jù)

x=0k=2 判斷a[k-1]>x？ 成立，a[k-1]后移

0123

k=0

停止比較將x

插入到數(shù)組元素a[k]

中在最前面插入

1123k=1 判斷a[k-1]>x？ 成立，a[k-1]后移2一維數(shù)組-插入排序（續(xù)）共43頁(yè)第28

頁(yè)012312345j=0i=3第4輪排序過程有序序列的長(zhǎng)度n=3 新插入的數(shù)據(jù)

x=43k=3 判斷a[k-1]>x？ 不成立，停止比較將x

插入到數(shù)組元素a[k]

中012343在最后面插入2一維數(shù)組-插入排序（續(xù)）共43頁(yè)第29

頁(yè)01234312345j=001234343i=4第5輪排序過程有序序列的長(zhǎng)度n=4 新插入的數(shù)據(jù)

x=7k=4 判斷a[k-1]>x？ 成立，a[k-1]后移

01

72343k=2判斷a[k-1]>x？ 不成立，停止比較將x

插入到數(shù)組元素a[k]

中在中間插入0

1232343k=3 判斷a[k-1]>x？ 成立，a[k-1]后移2一維數(shù)組-插入排序（續(xù)）共43頁(yè)第30

頁(yè)程序說明與注釋#defineN5inta[N];voidmain(){

inti,k,x;

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

{

printf(“EnterNo.%2d:”,i+1);scanf(“%d”,&x);

sort(

a,i,x

);

}

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

printf(“%d”,a[i]);}sort(inta[],intn,intx){

intk;

for(k=n;k>0;k--)

/*從后向前比較*/

if(a[k-1]>x)a[k]=a[k-1];

/*

將大數(shù)向后移動(dòng)*/

else

break;

/*找到插入的位置，退出*/

a[k]=x;

/*完成插入操作*/}2一維數(shù)組-插入排序（完）共43頁(yè)第31

頁(yè)§7-2一維數(shù)組-三種排序算法比較1.冒泡排序2.選擇排序3.插入排序找出數(shù)組中最小的，與第一個(gè)元素對(duì)換，再重復(fù)上述操作順序比較相鄰兩元素的大小，若左邊元素比右邊的大，則交換，否則不交換，比較需進(jìn)行多次假定第一個(gè)元素是合適的，取出第二個(gè)元素與之比較，若小，插到前面，否則，位置不變，再將第三個(gè)元素與前面兩個(gè)比較，放到有序序列中合適的位置….共43頁(yè)第32

頁(yè)3二維數(shù)組

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式1][常量表達(dá)式2];一、二維數(shù)組的定義二、二維數(shù)組在內(nèi)存的存放形式intarray[3][4];

通?？梢詫⒁粋€(gè)矩陣表示為一個(gè)二維數(shù)組，其中常量表達(dá)式1代表行數(shù)，常量表達(dá)式2代表列數(shù)。二維數(shù)組存放:多維數(shù)組的元素按行順序存放。多維數(shù)組的存儲(chǔ)順序是:

第一維的下標(biāo)變化最慢

共43頁(yè)第33

頁(yè)例如：整型數(shù)組

bb[3][3]={{1,2,3},

{4,5,6},{7,8,9}

};二維數(shù)組存放:多維數(shù)組的元素按行順序存放。地址

值

數(shù)組元素先存放第1行的所有元素；再存放第2行的所有元素；最后存放第3行中的所有元素。b[0][0]b[0][1]b[0][2]b[1][0]b[1][1]b[1][2]b[2][0]b[2][1]b[2][2]1234567893000H3002H3004H3006H3008H300AH300CH300EH3010H3二維數(shù)組（續(xù)）共43頁(yè)第34

頁(yè)§7-3二維數(shù)組數(shù)組名[行下標(biāo)表達(dá)式][列下標(biāo)表達(dá)式];

三、二維數(shù)組的引用若intarray[2][3],i=1,j=2,k=0;則a[i][k],a[j-1][i],a[1][j+k]均為對(duì)array的合法引用。同一維數(shù)組一樣，引用二維數(shù)組，也是引用它的元素。3二維數(shù)組（續(xù)）共43頁(yè)第35

頁(yè)若有inta[2][3]，i=1,j=2;①a[2][3] /*數(shù)組下標(biāo)越界*/②a(1)(2)

/*不能使用圓括號(hào)*/③a[i+j][2]/*行下標(biāo)越界

*/④a[1,0]/*a[1][0]*/

二維數(shù)組引用中常見的錯(cuò)誤3二維數(shù)組（續(xù)）共43頁(yè)第36

頁(yè)

數(shù)據(jù)類型數(shù)組名[常量表達(dá)式1][常量表達(dá)式2]＝｛初始化數(shù)據(jù)｝；四、二維數(shù)組初始化3二維數(shù)組（續(xù)）

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

等價(jià):inta[2][3]={{1,23},{4,5,6}};

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

結(jié)果為：a[0][0]=1,a[0][1]=2,a[0][2]=3, a[1][0]=4,a[1][1]=5,a[1][2]=6

按數(shù)組在內(nèi)存單元的存貯順序進(jìn)行初始化對(duì)多維數(shù)組初始化時(shí)，可采用按行排列賦初值的方式。共43頁(yè)第37

頁(yè)例如：inta[][3]={1,2,3,4,5,6};注意：此時(shí)只能省略第1維的值。C根據(jù)初始化數(shù)據(jù)的數(shù)量，自動(dòng)確定第1維的大小。3二維數(shù)組（完）若要對(duì)數(shù)組中的部分元素進(jìn)行初始化，可采用下例中的方法

staticinta[2][3]={{1},{4}};結(jié)果為：a[0][0]=1,a[1][0]=4,

其余元素均為0。

staticinta[3][3]={{1,2},{},{4,5,6}};結(jié)果為：a[0][0]=1,a[0][1]=2,a[2][0]=4,a[2][1]=5,a[2][2]=6,其余元素均為0。對(duì)多維數(shù)組全部元素進(jìn)行初始化時(shí)，可省略數(shù)組說明中第一維的大小。共43頁(yè)第38

頁(yè)分析：實(shí)現(xiàn)要形成上述矩陣要用5×5的二維數(shù)組。該數(shù)組中每個(gè)元素的值的形成規(guī)律為：數(shù)組中“行下標(biāo)值＜＝列下標(biāo)值”的元素（即對(duì)角線和對(duì)角線之上的各元素）其值為1；數(shù)組中“行下標(biāo)值＞列下標(biāo)值”元素的值為：行下標(biāo)-列下標(biāo)＋１3二維數(shù)組應(yīng)用-輸出矩陣?yán)?形成并輸出矩陣： ┏11111┓ ┃21111┃

A= ┃32111┃ ┃43211┃ ┗54321┛共43頁(yè)第39

頁(yè)#include“stdio.h”voidmain(){inti,j,a[5][5];

for

(i=0;i<=4;i++) /*i為行下標(biāo)*/

for(j=0;j<=4;j++) /*j為列下標(biāo)*/

if

(i<=j)a[i][j]=1;/*生成矩陣*/

elsea[i][j]=i-j+1;

for

(i=0;i<=4;i++) /*按行輸出二維數(shù)組*/

{for(j=0;j<=4;j++) printf("%d",a[i][j]); printf("\n");

}

}3二維數(shù)組應(yīng)用-輸出矩陣（續(xù)）例5程序共43頁(yè)第40

頁(yè)#include<stdio.h>voidmain(){ inti,j,b[3][2],a[2][3]={{1,2,3},{4,5,6}};

/*說明初始化數(shù)組a*/for(i=0;i<=1;i++)

for(j=0;j<=2;j++) b[j][i]=a[i][j]; /*進(jìn)行數(shù)組轉(zhuǎn)置*/for(i=0;i<=2;i++,printf(”\n”))/*按行輸出*/

for(j=0;j<=1;j++) printf("%d",b[i][j]);}3二維數(shù)組應(yīng)用-求矩陣轉(zhuǎn)置例6求矩陣A(2×3)的轉(zhuǎn)置矩陣B(3×2)。┏123┓┏14┓

Ａ＝┃┃