目录
1. 数组的基本概念
数组(Array)也是一种复合数据类型,它由一系列相同类型的元素(Element)组成。例如定义一个由4个int
型元素组成的数组count:
int count[4];
和结构体成员类似,数组count
的4个元素的存储空间也是相邻的。结构体成员可以是基本数据类型,也可以是复合数据类型,数组中的元素也是如此。根据组合规则,我们可以定义一个由4个结构体元素组成的数组:
struct complex_struct {
double x, y;
} a[4];
也可以定义一个包含数组成员的结构体:
struct {
double x, y;
int count[4];
} s;
数组类型的长度应该用一个整数常量表达式来指定[[16](#ftn.id2733250)]。数组中的元素通过下标(或者叫索引,Index)来访问。例如前面定义的由4个int
型元素组成的数组count
图示如下:
图 8.1. 数组count
整个数组占了4个int
型的存储单元,存储单元用小方框表示,里面的数字是存储在这个单元中的数据(假设都是0),而框外面的数字是下标,这四个单元分别用count[0]
、count[1]
、count[2]
、count[3]
来访问。注意,在定义数组int count[4];
时,方括号(Bracket)中的数字4表示数组的长度,而在访问数组时,方括号中的数字表示访问数组的第几个元素。和我们平常数数不同,数组元素是从“第0个”开始数的,大多数编程语言都是这么规定的,所以计算机术语中有Zeroth这个词。这样规定使得访问数组元素非常方便,比如count
数组中的每个元素占4个字节,则count[i]
表示从数组开头跳过4*i
个字节之后的那个存储单元。这种数组下标的表达式不仅可以表示存储单元中的值,也可以表示存储单元本身,也就是说可以做左值,因此以下语句都是正确的:
count[0] = 7;
count[1] = count[0] * 2;
++count[2];
到目前为止我们学习了五种后缀运算符:后缀++、后缀--、结构体取成员.、数组取下标[]、函数调用()。还学习了五种单目运算符(或者叫前缀运算符):前缀++、前缀--、正号+、负号-、逻辑非!。在C语言中后缀运算符的优先级最高,单目运算符的优先级仅次于后缀运算符,比其它运算符的优先级都高,所以上面举例的++count[2]
应该看作对count[2]
做前缀++运算。
数组下标也可以是表达式,但表达式的值必须是整型的。例如:
int i = 10;
count[i] = count[i+1];
使用数组下标不能超出数组的长度范围,这一点在使用变量做数组下标时尤其要注意。C编译器并不检查count[-1]
或是count[100]
这样的访问越界错误,编译时能顺利通过,所以属于运行时错误[[17](#ftn.id2733456)]。但有时候这种错误很隐蔽,发生访问越界时程序可能并不会立即崩溃,而执行到后面某个正确的语句时却有可能突然崩溃(在第 4 节 “段错误”我们会看到这样的例子)。所以从一开始写代码时就要小心避免出问题,事后依靠调试来解决问题的成本是很高的。
数组也可以像结构体一样初始化,未赋初值的元素也是用0来初始化,例如:
int count[4] = { 3, 2, };
则count[0]
等于3, count[1]
等于2,后面两个元素等于0。如果定义数组的同时初始化它,也可以不指定数组的长度,例如:
int count[] = { 3, 2, 1, };
编译器会根据Initializer有三个元素确定数组的长度为3。利用C99的新特性也可以做Memberwise Initialization:
int count[4] = { [2] = 3 };
下面举一个完整的例子:
例 8.1. 定义和访问数组
#include <stdio.h>
int main(void)
{
int count[4] = { 3, 2, }, i;
for (i = 0; i < 4; i++)
printf("count[%d]=%d
", i, count[i]);
return 0;
}
这个例子通过循环把数组中的每个元素依次访问一遍,在计算机术语中称为遍历(Traversal)。注意控制表达式i < 4
,如果写成i <= 4
就错了,因为count[4]
是访问越界。
数组和结构体虽然有很多相似之处,但也有一个显著的不同:数组不能相互赋值或初始化。例如这样是错的:
int a[5] = { 4, 3, 2, 1 };
int b[5] = a;
相互赋值也是错的:
a = b;
既然不能相互赋值,也就不能用数组类型作为函数的参数或返回值。如果写出这样的函数定义:
void foo(int a[5])
{
...
}
然后这样调用:
int array[5] = {0};
foo(array);
编译器也不会报错,但这样写并不是传一个数组类型参数的意思。对于数组类型有一条特殊规则:数组类型做右值使用时,自动转换成指向数组首元素的指针。所以上面的函数调用其实是传一个指针类型的参数,而不是数组类型的参数。接下来的几章里有的函数需要访问数组,我们就把数组定义为全局变量给函数访问,等以后讲了指针再使用传参的办法。这也解释了为什么数组类型不能相互赋值或初始化,例如上面提到的a = b
这个表达式,a
和b
都是数组类型的变量,但是b
做右值使用,自动转换成指针类型,而左边仍然是数组类型,所以编译器报的错是error: incompatible types in assignment
。
习题
1、编写一个程序,定义两个类型和长度都相同的数组,将其中一个数组的所有元素拷贝给另一个。既然数组不能直接赋值,想想应该怎么实现。
[[16](#id2733250)] C99的新特性允许在数组长度表达式中使用变量,称为变长数组(VLA,Variable Length Array),VLA只能定义为局部变量而不能是全局变量,与VLA有关的语法规则比较复杂,而且很多编译器不支持这种新特性,不建议使用。
[[17](#id2733456)] 你可能会想为什么编译器对这么明显的错误都视而不见?理由一,这种错误并不总是显而易见的,在第 1 节 “指针的基本概念”会讲到通过指针而不是数组名来访问数组的情况,指针指向数组中的什么位置只有运行时才知道,编译时无法检查是否越界,而运行时每次访问数组元素都检查越界会严重影响性能,所以干脆不检查了;理由二,[C99 Rationale]指出C语言的设计精神是:相信每个C程序员都是高手,不要阻止程序员去干他们需要干的事,高手们使用count[-1]
这种技巧其实并不少见,不应该当作错误。
2. 数组应用实例:统计随机数
本节通过一个实例介绍使用数组的一些基本模式。问题是这样的:首先生成一列0~9的随机数保存在数组中,然后统计其中每个数字出现的次数并打印,检查这些数字的随机性如何。随机数在某些场合(例如游戏程序)是非常有用的,但是用计算机生成完全随机的数却不是那么容易。计算机执行每一条指令的结果都是确定的,没有一条指令产生的是随机数,调用C标准库得到的随机数其实是伪随机(Pseudorandom)数,是用数学公式算出来的确定的数,只不过这些数看起来很随机,并且从统计意义上也很接近均匀分布(Uniform Distribution)的随机数。
C标准库中生成伪随机数的是rand
函数,使用这个函数需要包含头文件stdlib.h
,它没有参数,返回值是一个介于0和RAND_MAX
之间的接近均匀分布的整数。RAND_MAX
是该头文件中定义的一个常量,在不同的平台上有不同的取值,但可以肯定它是一个非常大的整数。通常我们用到的随机数是限定在某个范围之中的,例如0~9,而不是0~RAND_MAX
,我们可以用%运算符将rand
函数的返回值处理一下:
int x = rand() % 10;
完整的程序如下:
例 8.2. 生成并打印随机数
#include <stdio.h>
#include <stdlib.h>
#define N 20
int a[N];
void gen_random(int upper_bound)
{
int i;
for (i = 0; i < N; i++)
a[i] = rand() % upper_bound;
}
void print_random()
{
int i;
for (i = 0; i < N; i++)
printf("%d ", a[i]);
printf("
");
}
int main(void)
{
gen_random(10);
print_random();
return 0;
}
这里介绍一种新的语法:用#define
定义一个常量。实际上编译器的工作分为两个阶段,先是预处理(Preprocess)阶段,然后才是编译阶段,用gcc
的-E
选项可以看到预处理之后、编译之前的程序,例如:
$ gcc -E main.c
...(这里省略了很多行stdio.h和stdlib.h的代码)
int a[20];
void gen_random(int upper_bound)
{
int i;
for (i = 0; i < 20; i++)
a[i] = rand() % upper_bound;
}
void print_random()
{
int i;
for (i = 0; i < 20; i++)
printf("%d ", a[i]);
printf("
");
}
int main(void)
{
gen_random(10);
print_random();
return 0;
}
可见在这里预处理器做了两件事情,一是把头文件stdio.h
和stdlib.h
在代码中展开,二是把#define
定义的标识符N
替换成它的定义20(在代码中做了三处替换,分别位于数组的定义中和两个函数中)。像#include
和#define
这种以#号开头的行称为预处理指示(Preprocessing Directive),我们将在第 21 章 预处理学习其它预处理指示。此外,用cpp main.c
命令也可以达到同样的效果,只做预处理而不编译,cpp
表示C preprocessor。
那么用#define
定义的常量和第 3 节 “数据类型标志”讲的枚举常量有什么区别呢?首先,define
不仅用于定义常量,也可以定义更复杂的语法结构,称为宏(Macro)定义。其次,define
定义是在预处理阶段处理的,而枚举是在编译阶段处理的。试试看把第 3 节 “数据类型标志”习题2的程序改成下面这样是什么结果。
#include <stdio.h>
#define RECTANGULAR 1
#define POLAR 2
int main(void)
{
int RECTANGULAR;
printf("%d %d
", RECTANGULAR, POLAR);
return 0;
}
注意,虽然include
和define
在预处理指示中有特殊含义,但它们并不是C语言的关键字,换句话说,它们也可以用作标识符,例如声明int include;
或者void define(int);
。在预处理阶段,如果一行以#号开头,后面跟include
或define
,预处理器就认为这是一条预处理指示,除此之外出现在其它地方的include
或define
预处理器并不关心,只是当成普通标识符交给编译阶段去处理。
回到随机数这个程序继续讨论,一开始为了便于分析和调试,我们取小一点的数组长度,只生成20个随机数,这个程序的运行结果为:
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6
看起来很随机了。但随机性如何呢?分布得均匀吗?所谓均匀分布,应该每个数出现的概率是一样的。在上面的20个结果中,6出现了5次,而4和8一次也没出现过。但这说明不了什么问题,毕竟我们的样本太少了,才20个数,如果样本足够多,比如说100000个数,统计一下其中每个数字出现的次数也许能说明问题。但总不能把100000个数都打印出来然后挨个去数吧?我们需要写一个函数统计每个数字出现的次数。完整的程序如下:
例 8.3. 统计随机数的分布
#include <stdio.h>
#include <stdlib.h>
#define N 100000
int a[N];
void gen_random(int upper_bound)
{
int i;
for (i = 0; i < N; i++)
a[i] = rand() % upper_bound;
}
int howmany(int value)
{
int count = 0, i;
for (i = 0; i < N; i++)
if (a[i] == value)
++count;
return count;
}
int main(void)
{
int i;
gen_random(10);
printf("value how many
");
for (i = 0; i < 10; i++)
printf("%d %d
", i, howmany(i));
return 0;
}
我们只要把#define N
的值改为100000,就相当于把整个程序中所有用到N
的地方都改为100000了。如果我们不这么写,而是在定义数组时直接写成int a[20];
,在每个循环中也直接使用20这个值,这称为硬编码(Hard coding)。如果原来的代码是硬编码的,那么一旦需要把20改成100000就非常麻烦,你需要找遍整个代码,判断哪些20表示这个数组的长度就改为100000,哪些20表示别的数量则不做改动,如果代码很长,这是很容易出错的。所以,写代码时应尽可能避免硬编码,这其实也是一个“提取公因式”的过程,和第 2 节 “数据抽象”讲的抽象具有相同的作用,就是避免一个地方的改动波及到大的范围。这个程序的运行结果如下:
$ ./a.out
value how many
0 10130
1 10072
2 9990
3 9842
4 10174
5 9930
6 10059
7 9954
8 9891
9 9958
各数字出现的次数都在10000次左右,可见是比较均匀的。
习题
1、用rand
函数生成[10, 20]之间的随机整数,表达式应该怎么写?
3. 数组应用实例:直方图
继续上面的例子。我们统计一列0~9的随机数,打印每个数字出现的次数,像这样的统计结果称为直方图(Histogram)。有时候我们并不只是想打印,更想把统计结果保存下来以便做后续处理。我们可以把程序改成这样:
int main(void)
{
int howmanyones = howmany(1);
int howmanytwos = howmany(2);
...
}
这显然太繁琐了。要是这样的随机数有100个呢?显然这里用数组最合适不过了:
int main(void)
{
int i, histogram[10];
gen_random(10);
for (i = 0; i < 10; i++)
histogram[i] = howmany(i);
...
}
有意思的是,这里的循环变量i
有两个作用,一是作为参数传给howmany
函数,统计数字i
出现的次数,二是做histogram
的下标,也就是“把数字i
出现的次数保存在数组histogram
的第i
个位置”。
尽管上面的方法可以准确地得到统计结果,但是效率很低,这100000个随机数需要从头到尾检查十遍,每一遍检查只统计一种数字的出现次数。其实可以把histogram
中的元素当作累加器来用,这些随机数只需要从头到尾检查一遍(Single Pass)就可以得出结果:
int main(void)
{
int i, histogram[10] = {0};
gen_random(10);
for (i = 0; i < N; i++)
histogram[a[i]]++;
...
}
首先把histogram
的所有元素初始化为0,注意使用局部变量的值之前一定要初始化,否则值是不确定的。接下来的代码很有意思,在每次循环中,a[i]
就是出现的随机数,而这个随机数同时也是histogram
的下标,这个随机数每出现一次就把histogram
中相应的元素加1。
把上面的程序运行几遍,你就会发现每次产生的随机数都是一样的,不仅如此,在别的计算机上运行该程序产生的随机数很可能也是这样的。这正说明了这些数是伪随机数,是用一套确定的公式基于某个初值算出来的,只要初值相同,随后的整个数列就都相同。实际应用中不可能使用每次都一样的随机数,例如开发一个麻将游戏,每次运行这个游戏摸到的牌不应该是一样的。因此,C标准库允许我们自己指定一个初值,然后在此基础上生成伪随机数,这个初值称为Seed,可以用srand
函数指定Seed。通常我们通过别的途径得到一个不确定的数作为Seed,例如调用time
函数得到当前系统时间距1970年1月1日00:00:00[[18](#ftn.id2734350)]的秒数,然后传给srand
:
srand(time(NULL));
然后再调用rand
,得到的随机数就和刚才完全不同了。调用time
函数需要包含头文件time.h
,这里的NULL
表示空指针,到第 1 节 “指针的基本概念”再详细解释。
习题
1、补完本节直方图程序的main
函数,以可视化的形式打印直方图。例如上一节统计20个随机数的结果是:
0 1 2 3 4 5 6 7 8 9
* * * * * * * *
* * * * * * *
* * *
*
*
2、定义一个数组,编程打印它的全排列。比如定义:
#define N 3
int a[N] = { 1, 2, 3 };
则运行结果是:
$ ./a.out
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
1 2 3
程序的主要思路是:
把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列。
把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列。
把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列。
可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想。你的程序要具有通用性,如果改变了N
和数组a
的定义(比如改成4个数的数组),其它代码不需要修改就可以做4个数的全排列(共24种排列)。
完成了上述要求之后再考虑第二个问题:如果再定义一个常量M
表示从N
个数中取几个数做排列(N == M
时表示全排列),原来的程序应该怎么改?
最后再考虑第三个问题:如果要求从N
个数中取M
个数做组合而不是做排列,就不能用原来的递归过程了,想想组合的递归过程应该怎么描述,编程实现它。
[[18](#id2734350)] 各种派生自UNIX的系统都把这个时刻称为Epoch,因为UNIX系统最早发明于1969年。
4. 字符串
之前我一直对字符串避而不谈,不做详细解释,现在已经具备了必要的基础知识,可以深入讨论一下字符串了。字符串可以看作一个数组,它的每个元素是字符型的,例如字符串"Hello, world.
"
图示如下:
图 8.2. 字符串
注意每个字符末尾都有一个字符" "
做结束符,这里的