高级语言程序设计基础（C C++）：数组 把数串起来

共43页第1

页数组：把数串起来共43页第2

页数组的基本概念一维数组二维数组应用实例

1234数组共43页第3

页1数组的基本概念如何处理一个班学生的学习成绩？一行文字怎样存储？一个矩阵怎样存储？......

数组一组具有相同数据类型的数据的有序集合

？这些数据的特点：具有相同的数据类型。

为了很方便地使用这些数据，C语言提供了一种构造数据类型：数组。共43页第4

页其中：mark、str、a是数组名。方括号内是数组的长度。下标的个数称为数组的维数，mark、str是一维数组、a是二维数组。数组的成员称为数组元素。数组元素的类型称为该数组的基类型。数组mark的基类型是int，数组str的基类型是char。1数组的基本概念（续）例如：存储学生成绩用整型数组

mark[100]，

存储一行文字用字符数组

str[200]，

存储一个4*6的矩阵用二维整型数组

a[4][6]。共43页第5

页2一维数组一、一维数组的定义数据类型： 数组的基类型常量表达式： 数组的大小例如：float

mark[100];

char

str[200];

数据类型数组名[常量表达式]

数组名:

对数组的标识，遵循C语言标识符规则。

mark、str是数组名。共43页第6

页常量表达式是数组元素的个数，即数组长度。它必须是常量。

mark的长度是100

str的长度是200

2一维数组（续）数据类型就是数组元素的数据类型，

数组元素的类型叫做数组的基类型。

mark是str是实型数组、字符数组下标运算符数组名后面的方括号[]是下标运算符。

不允许使用（）括号。共43页第7

页①floata[0];/*数组大小为0没有意义*/②intb(2);/*不能使用圆括号*/③intk,a[k];/*不能用变量说明数组大小*/④intd[2.9];/*定义数组大小的表达式必须是整型常量表达式*/二、数组定义中常见的错误2一维数组（续）

C语言不允许对数组的大小进行动态说明。数组的说明语句必须在可执行语句之前。共43页第8

页在说明语句中，方括号内的值是数组中元素的总数量。

如：inta[10]；说明数组a一共有10个元素数组下标的起始值是0。即，引用数组的第一个元素的下标是0。数组a的10个元素分别是：a[0]、a[1]、…、a[9]。三、一维数组元素的引用2一维数组（续）

数组元素的引用方式：通过下标引用数组元素，格式：数组名[下标表达式]

下标:下标表达式的值必须是整型数据。共43页第9

页数组中的每个元素在功能上等价于一个一般的变量。 例如：输入100个学生成绩，并求出总成绩。2一维数组（续）使用数组：floatmark[100],sum;

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

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

引用数组元素的注意事项不用数组：floatx,sum;

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

页2一维数组（续）四、数组在内存中的存放每个数据元素占用的字节数，就是基类型的字节数一个元素占4个字节一维数组：float

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

高地址共43页第11

页mark[0]mark[1]mark[2]mark[3]...mark[99]86.592.077.552.0...94.02000H2004H2008H200CH。。。218CH引用数组元素时，根据首地址和下标，自动计算出该元素的实际地址，取出该地址的内容进行操作。如引用mark[2]:(1)计算

2000+2*4=2008(2)从取出2008的内容下标与地址的关系2一维数组（续）

[]为下标运算符,

数组名、数组元素是两种不同性质的数据。

数组名是数组的首地址，是一个地址常量。

数组元素则是数值。共43页第12

页共78页第12

页可以对静态或外部存贮类型的数组进行初始化。在数组说明的同时进行初始化的一般形式为：数据类型数组名[常量表达式1]…[常量表达式n]＝｛初始化数据｝；例如：说明一个1维数组并初始化，可以使用如下语句：

inta[4]={1,2,3,4}; 结果相当于：a[0]=1;a[1]=2;a[2]=3;a[3]=4;

staticfloatx[5]={1.9,2.0};

相当于：x[0]=1.9；x[1]=2.0；其余元素为0值。2一维数组（续）五、一维数组的初始化共43页第13

页共78页第13

页若要对数组的全部元素初始化，则可省略数组说明中的大小。

staticinta[]={1,2,3,4};对多维数组初始化时，可采用按行排列赋初值的方式。

inta[2][3]={{1,2,3},{4,5,6}}; 结果为： a[0][0]=1,a[0][1]=2,a[0][2]=3, a[1][0]=4,a[1][1]=5,a[1][2]=6也可按数组在内存单元的存贮顺序进行初始化。

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

等价：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一维数组（续）共43页第14

页共78页第14

页若要对数组中的部分元素进行初始化，可采用下例中的方法：

staticinta[2][3]={{1},{4}}; 结果为：a[0][0]=1,a[1][0]=4,其余元素均为0。

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

结果为：a[0][0]=1,a[0][1]=2,a[2][0]=4, a[2][1]=5,a[2][2]=6,其余元素均为0。对多维数组全部元素进行初始化时，可省略数组说明中第一维的大小。例如：

staticinta[][3]={1,2,3,4,5,6};注意：此时只能省略第1维的值。C根据初始化数据的数量，自动确定第1维的大小。2一维数组（续）共43页第15

页例1反向输出数组中各元素的值。#include<stdio.h>voidmain(){ staticinta[5]={10,20,30,40,50};

/*说明一个数组并进行初始化*/

inti=5;

while

(--i>=0) printf("a[%d]=%d\n",i,a[i]);/*循环控制变量i作为数组的下标*/}2一维数组（完）输出结果：a[4]=50,a[3]=40,a[2]=30,a[1]=20,a[0]=10六、一维数组的应用共43页第16

页2一维数组-冒泡排序冒泡排序法思想：假设6个整数为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页第17

页2一维数组-冒泡排序（续）冒泡排序程序：当n=6时，进行程序抽象i=0a[5]a[4]a[3]a[2]a[1]a[0]437-3230143237-310i=1i=2432371-30i=34323710-3i=44323710-34

i控制外层循环:

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

j

控制内层循环:

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

页程序说明与注释 #include<stdio.h> #defineN6 voidmain() {inti,j,t,a[N];

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

/*输入N个整数*/

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

}

for(i=0;i<N-1;i++) /*进行N-1轮比较*/

for(j=0;j<N-i-1;j++)/*比较数组中相邻两个元素*/

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--) /*输出排序结果*/

printf("%5d",a[i]); }2一维数组-冒泡排序（完）共43页第19

页冒泡排序的缺陷： 在比较交换的过程中大的数不能一次到位，效率低。2一维数组-选择排序7-3430123a[5]a[4]a[3]a[2]a[1]a[0]7-34302317-34323017-3432301743-32301437-32301

选择排序法的基本思想：以冒泡排序法为基础，在两两比较后并不马上进行交换，而是在找到最小的数之后，记住最小数的位置（在数组中的下标），待一轮比较完毕后，再将最小的数一次交换到位。共43页第20

页2一维数组-选择排序（续）问题将23、1、0、43、-3和7从小到大排列。选择排序法

若有N个数，则需要进行N-1轮排序处理。第1轮排序从1～N个数中找出最小的数，然后将它与第1个数交换。第1个数则是最小的数。第2轮排序从2～N个数中找出最小的数，然后将它与第2个数交换。第2个数则是次小的数。经过N-1轮处理，完成全部N个数排序。编程时使用二重循环。外面的大循环控制进行N-1轮排序，小循环找出第

i

轮的最小值。共43页第21

页2一维数组-选择排序（续）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

进行交换：t=a[i];a[i]=a[p];a[p]=t;

p：记录当前排序过程中最小值的下标

第1轮排序过程共43页第22

页2一维数组-选择排序（续）

-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

进行交换：t=a[i];a[i]=a[p];a[p]=t;第2轮排序过程

p：记录当前排序过程中最小值的下标

共43页第23

页程序说明与注释#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++){ /*进行N-1次比较*/

p=i; /*p中记录当前排序过程中最小元素的下标*/

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

if(a[p]>a[j])p=j;/*若有更小的数则记录下标*/

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

/*一次交换到位*/

}

for

(i=0;i<N;i++)/*输出排序后的结果*/

printf("%2d",a[i]);}2一维数组-选择排序（续）共43页第24

页插入排序法的基本思想 假设：已经存在一个长度为N的有序(从小到大排列)的数据序列，要将一个新的数插入到该序列中，要求插入后的新序列(长度为N+1)仍然保持有序。 算法的关键是要确定新数据插入的合适位置。 对于一个有序序列，从后向前进行比较，若序列中的数大于要插入的数，则将数列中的数向后移动；否则，完成插入操作。2一维数组-插入排序共43页第25

页

12345j=023

i=0第1轮排序过程有序序列的长度n=0 新插入的数据

x=23k=0直接将x插入数组元素a[k]

中2一维数组-插入排序（续）共43页第26

页23

12345j=0

2323

i=1第2轮排序过程有序序列的长度n=1 新插入的数据

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

1

23

k=0

停止比较将x

插入到数组元素a[k]

中2一维数组-插入排序（续）共43页第27

页1 2312345j=0

12323i=2第3轮排序过程有序序列的长度n=2 新插入的数据

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

0123

k=0

停止比较将x

插入到数组元素a[k]

中在最前面插入

1123k=1 判断a[k-1]>x？ 成立，a[k-1]后移2一维数组-插入排序（续）共43页第28

页012312345j=0i=3第4轮排序过程有序序列的长度n=3 新插入的数据

x=43k=3 判断a[k-1]>x？ 不成立，停止比较将x

插入到数组元素a[k]

中012343在最后面插入2一维数组-插入排序（续）共43页第29

页01234312345j=001234343i=4第5轮排序过程有序序列的长度n=4 新插入的数据

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

01

72343k=2判断a[k-1]>x？ 不成立，停止比较将x

插入到数组元素a[k]

中在中间插入0

1232343k=3 判断a[k-1]>x？ 成立，a[k-1]后移2一维数组-插入排序（续）共43页第30

页程序说明与注释#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];

/*

将大数向后移动*/

else

break;

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

a[k]=x;

/*完成插入操作*/}2一维数组-插入排序（完）共43页第31

页§7-2一维数组-三种排序算法比较1.冒泡排序2.选择排序3.插入排序找出数组中最小的，与第一个元素对换，再重复上述操作顺序比较相邻两元素的大小，若左边元素比右边的大，则交换，否则不交换，比较需进行多次假定第一个元素是合适的，取出第二个元素与之比较，若小，插到前面，否则，位置不变，再将第三个元素与前面两个比较，放到有序序列中合适的位置….共43页第32

页3二维数组

数据类型数组名[常量表达式1][常量表达式2];一、二维数组的定义二、二维数组在内存的存放形式intarray[3][4];

通常可以将一个矩阵表示为一个二维数组，其中常量表达式1代表行数，常量表达式2代表列数。二维数组存放:多维数组的元素按行顺序存放。多维数组的存储顺序是:

第一维的下标变化最慢

共43页第33

页例如：整型数组

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

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

};二维数组存放:多维数组的元素按行顺序存放。地址

值

数组元素先存放第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二维数组（续）共43页第34

页§7-3二维数组数组名[行下标表达式][列下标表达式];

三、二维数组的引用若intarray[2][3],i=1,j=2,k=0;则a[i][k],a[j-1][i],a[1][j+k]均为对array的合法引用。同一维数组一样，引用二维数组，也是引用它的元素。3二维数组（续）共43页第35

页若有inta[2][3]，i=1,j=2;①a[2][3] /*数组下标越界*/②a(1)(2)

/*不能使用圆括号*/③a[i+j][2]/*行下标越界

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

二维数组引用中常见的错误3二维数组（续）共43页第36

页

数据类型数组名[常量表达式1][常量表达式2]＝｛初始化数据｝；四、二维数组初始化3二维数组（续）

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

等价:inta[2][3]={{1,23},{4,5,6}};

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

结果为：a[0][0]=1,a[0][1]=2,a[0][2]=3, a[1][0]=4,a[1][1]=5,a[1][2]=6

按数组在内存单元的存贮顺序进行初始化对多维数组初始化时，可采用按行排列赋初值的方式。共43页第37

页例如：inta[][3]={1,2,3,4,5,6};注意：此时只能省略第1维的值。C根据初始化数据的数量，自动确定第1维的大小。3二维数组（完）若要对数组中的部分元素进行初始化，可采用下例中的方法

staticinta[2][3]={{1},{4}};结果为：a[0][0]=1,a[1][0]=4,

其余元素均为0。

staticinta[3][3]={{1,2},{},{4,5,6}};结果为：a[0][0]=1,a[0][1]=2,a[2][0]=4,a[2][1]=5,a[2][2]=6,其余元素均为0。对多维数组全部元素进行初始化时，可省略数组说明中第一维的大小。共43页第38

页分析：实现要形成上述矩阵要用5×5的二维数组。该数组中每个元素的值的形成规律为：数组中“行下标值＜＝列下标值”的元素（即对角线和对角线之上的各元素）其值为1；数组中“行下标值＞列下标值”元素的值为：行下标-列下标＋１3二维数组应用-输出矩阵例5形成并输出矩阵： ┏11111┓ ┃21111┃

A= ┃32111┃ ┃43211┃ ┗54321┛共43页第39

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

for

(i=0;i<=4;i++) /*i为行下标*/

for(j=0;j<=4;j++) /*j为列下标*/

if

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

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

for

(i=0;i<=4;i++) /*按行输出二维数组*/

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

}

}3二维数组应用-输出矩阵（续）例5程序共43页第40

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

/*说明初始化数组a*/for(i=0;i<=1;i++)

for(j=0;j<=2;j++) b[j][i]=a[i][j]; /*进行数组转置*/for(i=0;i<=2;i++,printf(”\n”))/*按行输出*/

for(j=0;j<=1;j++) printf("%d",b[i][j]);}3二维数组应用-求矩阵转置例6求矩阵A(2×3)的转置矩阵B(3×2)。┏123┓┏14┓

Ａ＝┃┃