第6章数组.doc

第6章 数组
6.1 怎样定义和引用一维数组

6.1.1 怎样定义一维数组
一般格式：
类型 数组名[常量表达式];
如：
int a[10];
说明：
（1）数组名的命名规则遵循C语言的标识符；
（2）常量表达式，用来指定该数组中元素的个数，也就是该数组的长度。该长度必须在这里是一个常量表达式（数字常量、符号常量），不能是变量。由于前面已经指定了类型，指定了元素个数后，该数组一共占用的空间大小就确定了，如：上例，a是int型，每个int型在VC中占4字节，而后面又定义了10个元素，所以，a共占用了4*10=40个字节的空间；
（3）可以使用sizeof运算来求出某个数组占用了多少空间；
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
1000
1004
1008

1020

1036
特别强调，其中常量表达式不能是变量，如：
int n=10;
int a[n]; //错误，因为n是变量
#define N 10
int b[N]; //正确，因为N是符号常量
int c[N+3]; //正确的，因为N+3是常量表达式
对于以下定义：
int a[10];
那么，系统就会在内存中划出一片存储空间，如右图：
显然，每个元素在内存中都是连续的，从而可以根据上一个元素的地址，来计算出下一个元素的地址，假设a的第0个元素存在1000地址上，那么，a[5]的地址：Add(a[0])+5*4=1020。而对a[i]的地址：
Add(a[i])=Add(a[0]+i*4)
（4）数组定义后，元素的排列是从a[0]开始的，因此定义的int a[10]中，只有a[0]~a[9]，并不存在a[10]这个元素。
（5）数组定义后，其中的每个元素的值都是不确定的（就是不知道值为多少，也可以说是随机的），如果想要在定义时就有初值，可以有两种方法：
方法一：用static来修饰，那么，该数组中的每个元素都会被初始化为0：
static int b[10]; //数组b中的10个元素每个值都是0
int a[10]; //数组a中的10个元素值不确定
方法二：在定义时，同时给出值，如：
int c[10]={1,2,3}; //给出了3个值
如果所给的值比数组元素少，那么后面的每个元素都会自动初始化成0，如上面的c数组，后面的c[3]~c[9]都是0
（6）前面第4点说了，定义的a[10]的元素是从a[0]~a[9]，没有a[10]这个元素，如果在程序中引用了a[10]，实际上是一种“越界错误”，但是在VC中，一般还发现不了。
6.1.2 怎样引用一维数组元素
引用一维数组元素最常用的方法就是：
数组名[下标]
如上面定义的：
int a[10]={1,2,3};
现在要引用第2个数：
a[2]=123;
还可以有别的引用方式：
（1）引用时，下标可以是变量：
for(i=0;i<10;i++)
a[i]=2*i;
其中的a[i]就是引用；
（2）可以仿照后面的指针进行引用，如要引用a[5]元素：
*(a+5)=345;
6.1.3 一维数组的初始化
一维数组的通常初始化方式：
（1）在定义数组时，全部数组元素赋予初值，如：
int a[10]={1,2,3,4,5,6,7,8,9,10};
如果给出了所有的元素的值，那么，在定义时元素的个数可以省略，如上面的a，后面已经给了10个元素的值，那么可以省略10：
int a[ ]={1,2,3,4,5,6,7,8,9,10};
（2）可以只给数组中的一部分元素赋初值，如：
int a[10]={1,2,3};
只给了3个元素的值，那么后面所有的元素全部取为0
（3）如果想给数组每个元素都取为0,可以写为：
int a[10]={0};
6.1.4 一维数组应用举例
Eg6.1：通常引用一维数组的方式，就是用一个for循环，如：
int a[10];
int i;
//要对a进行赋初值，可以用一个for循环进行：
for(i=0;i<10;i++) //i是从0开始，到9结束，用的是<10，不能用<=10
{
a[i]=2*i;
}
//如果要用户输入10个元素进行赋初值，可以用scanf
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
//也可以从后往前进行赋初值：
for(i=9;i>=0;i--)
{
a[i]=2*i;
}
//要处理数组a，实际上只能对a中的元素一个一个进行，无法进行整体操作，如：
for(i=0;i<10;i++)
{
a[i]=a[i]*2;
}
//输出数组，也是一个元素一个元素进行输出，通常也是用一个for：
for(i=0;i<10;i++)
{
printf("%5d",a[i]); //每个元素占5个位置，从而在屏幕上对齐
}
Eg6.2：已知有一个数组a如下：
int a[10]={1,2,3,4,5,6,7,8,9,10};
现在要将a数组逆置，就是原来a[0]的值变成a[9]的值等。
方法一：再定义一个数组b，其大小与a相同，将a中的元素反过来赋值给b，从而b就达到了a的逆置，再将a拷贝回去即可。如下图所示：
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
a

0
1
2
3
4
5
6
7
8
9
b
那么b[0]的值来自于a[9]，而b[3]的值来自于a[6]，……，a[i]的值来自于b[9-i]，这样，可以编程如下：
for(i=0;i<10;i++)
{
b[i]=a[9-i];
}
再将b拷回去：
for(i=0;i<10;i++)
{
a[i]=b[i];
}
方法二：不需要数组b，直接在a中进行，实际上只需要让a[0]与a[9]进行交换，a[1]与a[8]进行交换，……，a[i]与a[9-i]进行交换便可，注意这个交换只能交换一次，不能重复交换，也就是说，要控制循环的次数，对于10个元素来说，只要交换5对元素，对于有n个元素来说，要交换n/2对元素：
int t;
for(i=0;i<10/2;i++) //注意交换次数
{
t=a[i];
a[i]=a[9-i];
a[9-i]=t;
}
Eg6.3：插入：向数组中指定位置插入一个元素，如，原来的数组a：
49
27
36
58
64
19
72
86
31

0
1
2
3
4
5
6
7
8
9
a
a
...

19
49
27
36
58
64
88
19
72
86
31
0
1
2
3
4
5
6
7
8
9
...

19
①
②
③
④
int a[20]={49,27,36,58,64,19,72,86,31};
现在要向a中的第5个位置插入元素88，效果如下：
a[20]={49,27,36,58,64,19,72,86,31};
显然，需要挪动的元素个数为：9-5（原来数组中元素个数-要插入的位置），这些元素应该是：a[5]、a[6]、a[7]、a[8]这4个元素，且应该是倒过来移，就是先将a[8]移动到a[9]，再将a[7]移动到a[8]上，以此类推，可得如下的程序段：
for(j=8;j>=5;j--)
a[j+1]=a[j];
用变量表示，n表示原来数组a中的元素个数，k表示要插入的元素位置，可得：
for(j=n-1;j>=k;j--)
a[j+1]=a[j];
最后一步，就是将元素x插入到a[k]位置上去：
a[k]=x;
完整的代码如下：
void main()
{
int a[20]={49,27,36,58,64,19,72,86,31};
int n=9; //数组a中原来有9个数
int k=5; //向第k个位置中插入元素x
int x=99; //欲插入的元素值
int i,j;
printf("\n插入前，数组a：");
for(i=0;i<n;i++)
printf("%5d",a[i]);
for(j=n-1;j>=k;j--) //从a[k]这个元素开始，每个元素向后挪动一个位置，注意要从后往前开始挪动
a[j+1]=a[j];
a[k]=x; //元素x插入到a[k]中。
n++; //元素个数加1
printf("\n插入手，数组a：");
for(i=0;i<n;i++)
printf("%5d",a[i]);
putchar('\n');
}
Eg6.4：删除：从数组中指定位置删除一个元素，如，原来的数组a：
49
27
36
58
64
19
72
86
31

0
1
2
3
4
5
6
7
8
9
a
a
...

19
49
27
36
58
64
72
86
31
31

0
1
2
3
4
5
6
7
8
9
...

19
int a[20]={49,27,36,58,64,19,72,86,31};
现在要删除a中的第5个位置的元素19，效果如下：
a[20]={49,27,36,58,64,19,72,86,31};
显然，需要挪动的元素个数为：9-5-1（原来数组中元素个数-要插入的位置-1），这些元素应该是：a[6]、a[7]、a[8]这3个元素，就是先将a[6]移动到a[5]，再将a[7]移动到a[6]上，以此类推，a[j]应该移动到a[j-1]个位置上去，可得如下的程序段：
for(j=k+1;j<n;j++)
a[j-1]=a[j];
n--;
Eg6.5：用数组求Fibonacci数列问题，打印出前20个元素，并求和
Fibonacci数列是：1,1,2,3,5,8,……
显然，可以让a[0]=1,a[1]=1，从a[2]开始，每个元素都为前面两个元素的和，也就是说，a[i]=a[i-1]+a[i-2];这个i应该从2开始到19结束。
可编程如下：
int a[30];
int i,sum=0;
a[0]=1;
a[1]=1;
sum+=a[0]+a[1];
for(i=2;i<20;i++)
{
a[i]=a[i-1]+a[i-2];
sum+=a[i];
}
printf("前20个Fibonacci数列为：\n");
for(i=0;i<20;i++)
{
printf("%10d",a[i]);
if((i+1)%5==0)
putchar('\n');
}
printf("\n它们的和为：%d\n",sum);
Eg6.6：查找从数组a中查找指定的元素：
49
27
36
58
64
19
72
86
31

0
1
2
3
4
5
6
7
8
9
a
...

19
int a[20]={49,27,36,58,64,19,72,86,31}
可查找以下四种元素
（1）最大值：可得86，位置为7
（2）最小值：可得19，位置为5
（3）与某个存在的元素相等的第一个元素：x=58，可得位置为3
（4）不存在的某个元素：x=100，不存在
对于（1）和（2），可假定max=a[0]就是最大值（或最小值），然后从a[1]开始，每个元素与max相比较，如果发现一个元素比max更大，则说明找到了一个可能是最大的数，让max＝这个数，这样直到最后，就能找到最大值。可编程如下：
Eg6.7：排序：
6.2 怎样定义和引用二维数组
6.1.1 怎样定义二维数组
类型 数组名[行号常量表达式][列号常量表达式];
如：
int a[5][10];
其中第一维通常称为行，第二维通常称为列，如上面的a就有5行10列，就是说，每行有10个元素，它们是如下排列的：
a[0][0],a[0][1],a[0][2],……,a[0][9]
a[1][0],a[1][1],a[1][2],……,a[1][9]
……
a[4][0],a[4][1],a[4][2],……,a[4][9]
显然，一共有5*10＝50个元素。且这50个元素也是一个接一个地顺序存放在内存中，从而，也可以像一维数组一个快速计算其地址，如上例，假设a[0][0]的地址为1000，那么a[2][7]的地址Add(a[2][7])=1000+(2*10+7)*4，也就是说，对于a[i][j]的地址Add(a[i][j])=1000+(i*10+j)*4
上面的计算是C语言的方式，这种方式有一个前提：按行存放，就是优先满足一行，再下一行，有些编译器会按列序存放，就是优先满足一列，再存到下一列中，如：
int a[5][10];
如果按列序存放，则其存放的顺序为：
a[0][0]->a[1][0]->a[2][0]->a[3][0]->a[4][0]->a[1][1]->a[2][1]……->a[3][9]->a[4][9]
那么在这种存放方式下，a[2][7]的地址＝1000+(7*5+2)*4
也就是说，a[i][j]的地址Add(a[i][j])=1000+(j*5+i)*4
6.1.2 怎样引用二维数组
引用二维数组需要给出行下标和列下标来，如：
a[2][3]=123;
6.1.3 二维数组的初始化
（1）在定义时进行：
int a[3][5]={
{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15}
};
（2）在定义时，也可以只用一个大括号：
int a[3][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
（3）也可以在定义时，只给某些元素赋初值，如：
int a[3][5]={
{1,2,},
{6},
{11,12,13,14}
};
那么，像a[0][2]、a[1][3]等元素的初值系统会自动取为0
（4）还可以在定义时，只给某些行取初值：
int a[3][5]={
{1,2,},
{},
{11,12,13,14}
};
则第1行中的所有元素全部取为0
（5）如果给初值时，已经明确给出了几行，那么定义时行号可以省略，如：
int a[ ][5]={
{1,2,},
{6},
{11,12,13,14}
};
已经明确给了3行的值，那么行数3可以省略
（6）如果将所有的元素全部给了值，且不是用若干个{}来表示行，也可以省略行号，如：
int a[ ][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
因为已经给了15个元素，且每行有5个元素，那么系统会自动取3行，但是，如果给的不是15个元素，而是17个元素，那么系统知道，应该取4行，且后面的3个元素自动取为0.
（7）如果在定义时，没有取初值，那么可以在程序用一般用一个二重循环进行赋值，如：
int a[5][10];
int i,j;
for(i=0;i<5;i++) //0~4行
{
for(j=0;j<10;j++) //0~9列
{
a[i][j]=i+j;
}
}
（8）在输出一个二维数组时，通常会每行占一行，就是说，需要控制输出格式：
for(i=0;i<5;i++) //0~4行
{
for(j=0;j<10;j++) //0~9列
{
printf("%5d",a[i][j]);
}
putchar('\n'); //换行
}
6.1.4 二维数组应用举例
Eg6.8 用二维数组输出杨辉三角，所谓杨辉三角，就是每个元素都等于其上一行的对应元素及其前一元素的和：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
可以用二维数组实现，第0行不用，且每行的第0列也不用，从第1行开始，第1列取为1，然后后面每个元素均为前一行的对应元素的和，如：
a[i][j]=a[i-1][j]+a[i-1][j-1]
且第i行应该有i个元素，可得下图：
int a[20][20]={0}; //全部初始化为0
int i,j;
a[1][1]=1;
for(i=2;i<=10;i++)
{
for(j=1;j<=i;j++) //第i行，只需要计算i个元素
{
a[i][j]=a[i-1][j]+a[i-1][j-1];
}
}
//下面开始打印这个杨辉三角
for(i=1;i<=10;i++)
{
for(j=1;j<=i;j++)
{
printf("%7d",a[i][j]);
}
putchar('\n');
}
0
0
0
0
0
0
0
0
0

0
1
2
3
4
5
6
7
8
9
0
1
0

0
1
1
0

0
1
2
1
0

0
1
3
3
1

0

0

0

0

0
1
2
3
4
5
6
7
8
9
Eg 6.9 用二维数组计算矩阵：
（1）矩阵的查找
（2）矩阵的和
（3）矩阵的积
（4）行列互换
先看查找，从一个二维数组中，查找一个指定的值（最大值、最小值、指定的元素值等），如有如下的二维数组：
int a[3][4]={49,56,23,64,78,61,19,41,23,38,88,97};
则最大值为97,其位置为：第2行的第3个
最小值为19,位置为第1行的第2个
仍然可以使用二维数组，先假定a[0][0]是最大值max：
int max,l_max_i,l_max_j; //分别表示最大值及其位置
max=a[0][0];
l_max_i=0;
l_max_j=0;
for(i=0;i<3;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j]>max)
{
max=a[i][j];
l_max_i=i;
l_max_j=j;
}
}
}
如果要找x=78：
int l_x_i,l_x_j;
int x=78;
int flag=0; //先假定没找到
for(i=0;i<3;i++)
{
for(j=0;j<4;j++)
{
if(a[i][j==x)
{
l_x_i=i;
l_x_j=j;
flag=1;
break;
}
}
if(flag==1)
break; //已经找到，直接退出该循环
}
if(flag==1) //找到了，输出相应的信息
{
}else //没找到，此时的l_x_i和l_x_j没有意义
{
}
6.3 字符数组
在定义一维数组时，如果类型为char型，那么这个一维数组就是是字符数组，如：
int a[10];
char s[10];
字符数组与int型数组没有本质的区别，与int型数组类似，可以进行上面的操作。
但是，字符数组如果在末尾加一个'\0'之后，该字符数组就有更多的应用。
如：
char s1[20]="Chinese";
char s2[20]={'C','h','i','n','e','s','e'};
char s3[ ]= {'C','h','i','n','e','s','e'};
char s4[7]= {'C','h','i','n','e','s','e'};
char s5[8]= {'C','h','i','n','e','s','e'};
char s6[ ]="Chinese";
其中s3没有指定数组的大小，系统会自动去数后面的数（7个），那么，s3就取成7个char型大小，所以s3与s4是等价的。
对于s5来说，后面只有7个字符，但是前面大小为8，则有一个a[7]没有初值，系统会自动取为0，所以s5相当于：
char s5[8]= {'C','h','i','n','e','s','e',0};
对于s2来说，大小为20个元素，显然，后面有13个0：
char s2[20]={'C','h','i','n','e','s','e',0,0,0,0,0,0,0,0,0,0,0,0,0};
如果某个字符数组后面至少有一个0（0是它的ASCII码，如果用字符表示这个0号字符，可用'\0'），那么这个字符数组就称为字符串。
如上面的s2、s5后面都至少有一个'\0'，所以它们是字符串
而s3、s4后面没有'\0'，它们不是字符串
如果要定义一个字符串的一维数组，还可以用""来括起来，如上面的s1，后面的"Chinese"是一个用""括起来的字符串，，且s1的大小为20个元素。
'C'
0
h
1
i
2
n
3
e
4
s
5
e
6
\0
7
s2
\0
...
\0
19
而s6没有指定大小，那么系统会去数，其中Chines占7个char，系统还会自动在后面加一个\0，故s6的大小为8个字节空间。
其中的一个字符串末尾的\0就称为字符串的结束标志。
有了这个标志，字符串的编程就与int型的不同，可以用这个标志来判断是否已经到了末尾。如下图：
由于有了这个标志，一般可以用while循环来进行。
Eg 6.10 输出s2：
方法一：用for循环，输出该数组的所有的元素：
int i;
char s2[20]={'C','h','i','n','e','s','e'};
for(i=0;i<20;i++)
putchar(s2[i]);
方法二：用while循环，直到遇到\0就结束输出：
i=0;
while( s2[i]!='\0')
{
putchar(s2[i]);
i++;
}
方法三：如果确定该字符数组是字符串（就是一定有那个'\0'），还可以用printf的%s格式输出：
printf("%s",s2);
方法四：方法三：如果确定该字符数组是字符串（就是一定有那个'\0'），还可以用puts(s2)进行输出：
puts(s2);
Eg 6.11 将字符串s2中的所有元素大小写互换：
原来：char s2[20]={'C','h','i','n','e','s','e'};
互换后s2中的内容为："cHINESE"
实际上思想就是从s2[0]开始，直到\0前面，一个一个进行处理，如果这个字符是大写的字母，则将其+32就变成小写，如果是小写字母，就将其-32，如果不是字母，则直接跳过。
i=0;
while(s2[i]!='\0')
{
if(s2[i]>='A' && s2[i]<='Z') //大写字母
s2[i]=s2[i]+32;
else if(s2[i]>='a' && s2[i]<='z') //小写字母
s2[i]=s2[i]-32;
i++;
}
其中的这个循环：
i=0;
while(s2[i]!='\0')
{
//操作s2
i++
}
是字符串编程中万能的循环。
Eg 6.12 求字符串s2字符的个数，就是\0前面的个数：
i=0;
while(s2[i]!='\0')
{
i++
}
最后，i的值就是s2的字符个数
课后练习：
教材P168的第1~15题。