第 12 / 187 篇

1.5. 数组与字符串

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C1-C_intro/arrays_strings.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

1.5. Arrays and Strings

数组(array)是 C 的一种构造,它创建一个由相同类型的数据元素组成的有序集合,并把这个集合与一个程序变量关联起来。有序的意思是每个元素在值的集合中都处于特定的位置(即有位置 0 的元素、位置 1 的元素,依此类推),而不是说这些值一定已经排好序。数组是 C 把多个数据值组织在一起、并用单个名字引用它们的主要机制之一。数组有好几种形式,最基本的是一维数组,它可以用来在 C 中实现类似列表的数据结构和字符串。

An array is a C construct that creates an ordered collection of data elements of the same type and associates this collection with a single program variable. Ordered means that each element is in a specific position in the collection of values (that is, there is an element in position 0, position 1, and so on), not that the values are necessarily sorted. Arrays are one of C’s primary mechanisms for grouping multiple data values and referring to them by a single name. Arrays come in several flavors, but the basic form is a one-dimensional array, which is useful for implementing list-like data structures and strings in C.

1.5.1. 数组简介

1.5.1. Introduction to Arrays

C 数组可以存储多个相同类型的数据值。本章讨论静态声明(statically declared)的数组,即数组的总容量(数组最多能存储的元素个数)是固定的,在声明数组变量时就确定了。下一章我们会讨论动态分配的数组和多维数组。

C arrays can store multiple data values of the same type. In this chapter, we discuss statically declared arrays, meaning that the total capacity (the maximum number of elements that can be stored in an array) is fixed and is defined when the array variable is declared. In the next chapter, we discuss dynamically allocated arrays and multi-dimensional arrays.

表 1 给出了一个程序的 Python 版本和 C 版本,该程序初始化一组整数值并把它们打印出来。Python 版本用内置的列表类型存储这组值,而 C 版本用一个 int 类型的数组来存储。

Table 1 shows Python and C versions of a program that initializes and then prints a collection of integer values. The Python version uses its built-in list type to store the list of values, whereas the C version uses an array of int types to store the collection of values.

总的来说,Python 为程序员提供了一个高级的列表接口,隐藏了大部分底层实现细节。而 C 则把底层的数组实现暴露给程序员,由程序员自己去实现更高级的功能。换句话说,数组提供的是底层的数据存储,没有 len、append、insert 等更高级的列表功能。

In general, Python provides a high-level list interface to the programmer that hides much of the low-level implementation details. C, on the other hand, exposes a low-level array implementation to the programmer and leaves it up to the programmer to implement higher-level functionality. In other words, arrays enable low-level data storage without higher-level list functionality, such as len, append, insert, and so on.

表 1. Python 列表与 C 数组的语法对比

Table 1. Syntax Comparison of Lists in Python and Arrays in C

Python 版本

Python version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# An example Python program using a list.


def main():


# create an empty list
my_lst = []

# add 10 integers to the list
for i in range(10):
my_lst.append(i)



# set value at position 3 to 100
my_lst[3] = 100

# print the number of list items
print("list %d items:" % len(my_lst))

# print each element of the list
for i in range(10):
print("%d" % my_lst[i])


# call the main function:
main()

C 版本

C version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* An example C program using an array. */
#include <stdio.h>

int main(void) {
int i, size = 0;

// declare array of 10 ints
int my_arr[10];

// set the value of each array element
for (i = 0; i < 10; i++) {
my_arr[i] = i;
size++;
}

// set value at position 3 to 100
my_arr[3] = 100;

// print the number of array elements
printf("array of %d items:\n", size);

// print each element of the array
for (i = 0; i < 10; i++) {
printf("%d\n", my_arr[i]);
}

return 0;
}

这个程序的 C 版本和 Python 版本有几处相似之处,最明显的是都可以通过下标(indexing)访问单个元素,并且下标值都从 0 开始。也就是说,两种语言都把集合中的第一个元素称为位置 0 上的元素。

The C and Python versions of this program have several similarities, most notably that individual elements can be accessed via indexing, and that index values start at 0. That is, both languages refer to the very first element in a collection as the element at position 0.

这个程序的 C 版本和 Python 版本的主要区别,在于列表或数组的容量,以及如何确定它们的大小(元素个数)。

The main differences in the C and Python versions of this program relate to the capacity of the list or array and how their sizes (number of elements) are determined.

对于 Python 列表:

For a Python list:

1
2
3
my_lst[3] = 100   # Python syntax to set the element in position 3 to 100.

my_lst[0] = 5 # Python syntax to set the first element to 5.

对于 C 数组:

For a C array:

1
2
3
my_arr[3] = 100;  // C syntax to set the element in position 3 to 100.

my_arr[0] = 5; // C syntax to set the first element to 5.

在 Python 版本中,程序员不需要事先指定列表的容量:Python 会根据程序的需要自动增加列表的容量。例如,Python 的 append 函数会自动增大 Python 列表的大小,并把传入的值添加到末尾。

In the Python version, the programmer doesn’t need to specify the capacity of a list in advance: Python automatically increases a list’s capacity as needed by the program. For example, the Python append function automatically increases the size of the Python list and adds the passed value to the end.

相比之下,在 C 中声明数组变量时,程序员必须指定它的类型(数组中每个值的类型)和总容量(存储位置的最大个数)。例如:

In contrast, when declaring an array variable in C, the programmer must specify its type (the type of each value stored in the array) and its total capacity (the maximum number of storage locations). For example:

1
2
3
int  arr[10];  // declare an array of 10 ints

char str[20]; // declare an array of 20 chars

上面的声明创建了一个名为 arr 的变量,它是总容量为 10 的 int 数组;还创建了另一个名为 str 的变量,它是总容量为 20 的 char 数组。

The preceding declarations create one variable named arr, an array of int values with a total capacity of 10, and another variable named str, an array of char values with a total capacity of 20.

为了计算列表的大小(即列表中值的总个数),Python 提供了 len 函数,它返回传给它的任何列表的大小。在 C 中,程序员必须显式地记录数组中元素的个数(例如表 1 中的 size 变量)。

To compute the size of a list (size meaning the total number of values in the list), Python provides a len function that returns the size of any list passed to it. In C, the programmer has to explicitly keep track of the number of elements in the array (for example, the size variable in Table 1).

从这个程序的 Python 版本和 C 版本中可能看不出来的另一个区别,是 Python 列表和 C 数组在内存中的存储方式。C 规定了数组在程序内存中的布局,而 Python 对程序员隐藏了列表的实现方式。在 C 中,各个数组元素被分配在程序内存中的连续位置上。例如,数组的第三个位置在内存中紧跟在第二个位置之后、紧挨在第四个位置之前。

Another difference that might not be apparent from looking at the Python and C versions of this program is how the Python list and the C array are stored in memory. C dictates the array layout in program memory, whereas Python hides how lists are implemented from the programmer. In C, individual array elements are allocated in consecutive locations in the program’s memory. For example, the third array position is located in memory immediately following the second array position and immediately before the fourth array position.

1.5.2. 访问数组的方法

1.5.2. Array Access Methods

Python 提供了多种访问列表元素的方式。而 C 只支持前面介绍的下标访问。有效的下标值范围是从 0 到数组容量减 1。下面是一些例子:

Python provides multiple ways to access elements in its lists. C, however, supports only indexing, as described earlier. Valid index values range from 0 to the capacity of the array minus 1. Here are some examples:

1
2
3
4
5
6
7
8
9
10
11
int i, num;
int arr[10]; // declare an array of ints, with a capacity of 10

num = 6; // keep track of how many elements of arr are used

// initialize first 5 elements of arr (at indices 0-4)
for (i=0; i < 5; i++) {
arr[i] = i * 2;
}

arr[5] = 100; // assign the element at index 5 the value 100

这个例子声明了一个容量为 10 的数组(它有 10 个元素),但只用了前六个(我们当前的值集合大小是 6,而不是 10)。使用静态声明的数组时,数组的部分容量常常闲置不用。因此,我们需要另一个程序变量来记录数组的实际大小(元素个数)(本例中的 num)。

This example declares the array with a capacity of 10 (it has 10 elements), but it only uses the first six (our current collection of values is size 6, not 10). It’s often the case when using statically declared arrays that some of an array’s capacity will remain unused. As a result, we need another program variable to keep track of the actual size (number of elements) in the array (num in this example).

当程序试图访问无效下标时,Python 和 C 的错误处理方式不同。如果用无效的下标值访问列表元素(例如下标超出了列表的元素个数),Python 会抛出 IndexError 异常。在 C 中,则由程序员负责确保代码只用有效的下标值访问数组。因此,对于下面这种访问超出已分配数组边界的元素的代码,程序的运行时行为是未定义的:

Python and C differ in their error-handling approaches when a program attempts to access an invalid index. Python throws an IndexError exception if an invalid index value is used to access elements in a list (for example, indexing beyond the number of elements in a list). In C, it’s up to the programmer to ensure that their code uses only valid index values when indexing into arrays. As a result, for code like the following that accesses an array element beyond the bounds of the allocated array, the program’s runtime behavior is undefined:

1
2
3
int array[10];   // an array of size 10 has valid indices 0 through 9

array[10] = 100; // 10 is not a valid index into the array

C 编译器会毫无怨言地编译访问数组边界之外位置的代码:编译器不做边界检查,运行时也不做。因此,运行这段代码可能导致意想不到的程序行为(而且每次运行的表现可能都不一样)。它可能让程序崩溃,可能改掉另一个变量的值,也可能对程序行为毫无影响。换句话说,这种情况会造成一个程序缺陷,它可能表现为程序的异常行为,也可能不会。所以,作为 C 程序员,你要自己确保数组访问指向的是有效位置!

The C compiler is happy to compile code that accesses array positions beyond the bounds of the array; there is no bounds checking by the compiler or at runtime. As a result, running this code can lead to unexpected program behavior (and the behavior might differ from run to run). It can lead to your program crashing, it can change another variable’s value, or it might have no effect on your program’s behavior. In other words, this situation leads to a program bug that might or might not show up as unexpected program behavior. Thus, as a C programmer, it’s up to you to ensure that your array accesses refer to valid positions!

译注 · 用工具抓越界访问

编译器默认不检查,但现代工具可以帮忙:用 GCC 或 Clang 编译时加上 -fsanitize=address(AddressSanitizer),运行时一旦发生数组越界读写,程序会立刻报错并指出出错的代码行;第 3 章介绍的 Valgrind 也能发现一部分此类错误(Valgrind 更擅长发现堆上的越界,对栈上数组的越界检测能力有限)。

1.5.3. 数组与函数

1.5.3. Arrays and Functions

在 C 中把数组传给函数的语义,与在 Python 中把列表传给函数类似:函数可以修改传入的数组或列表中的元素。下面是一个接收两个参数的函数示例:一个 int 数组参数(arr)和一个 int 参数(size):

The semantics of passing arrays to functions in C is similar to that of passing lists to functions in Python: the function can alter the elements in the passed array or list. Here’s an example function that takes two parameters, an int array parameter (arr), and an int parameter (size):

1
2
3
4
5
6
void print_array(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d\n", arr[i]);
}
}

参数名后面的 [] 告诉编译器,参数 arr 的类型是 int 数组,而不是像参数 size 那样的 int。下一章我们会介绍另一种指定数组参数的语法。数组参数 arr 的容量没有指定:arr[] 表示可以用任意容量的数组实参来调用这个函数。由于仅凭数组变量本身无法得知数组的大小或容量,接收数组的函数几乎总是还有第二个参数来指定数组的大小(上例中的 size 参数)。

The [] after the parameter name tells the compiler that the type of the parameter arr is array of int, not int like the parameter size. In the next chapter, we show an alternate syntax for specifying array parameters. The capacity of the array parameter arr isn’t specified: arr[] means that this function can be called with an array argument of any capacity. Because there is no way to get an array’s size or capacity just from the array variable, functions that are passed arrays almost always also have a second parameter that specifies the array’s size (the size parameter in the preceding example).

要调用带数组参数的函数,就把数组名作为实参传入。下面这段 C 代码展示了调用 print_array 函数的例子:

To call a function that has an array parameter, pass the name of the array as the argument. Here is a C code snippet with example calls to the print_array function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int some[5], more[10], i;

for (i = 0; i < 5; i++) { // initialize the first 5 elements of both arrays
some[i] = i * i;
more[i] = some[i];
}

for (i = 5; i < 10; i++) { // initialize the last 5 elements of "more" array
more[i] = more[i-1] + more[i-2];
}

print_array(some, 5); // prints all 5 values of "some"
print_array(more, 10); // prints all 10 values of "more"
print_array(more, 8); // prints just the first 8 values of "more"

在 C 中,数组变量的名字等价于数组的基地址(base address,即第 0 个元素所在的内存位置)。由于 C 的函数调用采用按值传递的语义,把数组传给函数时,数组的各个元素并不会被逐个传给函数。换句话说,函数并没有得到每个数组元素的副本,而是由数组参数得到数组基地址的值。这一行为意味着,当函数修改作为参数传入的数组的元素时,这些修改在函数返回后会保留下来。例如,看看下面这段 C 程序:

In C, the name of the array variable is equivalent to the base address of the array (that is, the memory location of its 0th element). Due to C’s pass by value function call semantics, when you pass an array to a function, each element of the array is not individually passed to the function. In other words, the function isn’t receiving a copy of each array element. Instead, an array parameter gets the value of the array’s base address. This behavior implies that when a function modifies the elements of an array that was passed as a parameter, the changes will persist when the function returns. For example, consider this C program snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test(int a[], int size) {
if (size > 3) {
a[3] = 8;
}
size = 2; // changing parameter does NOT change argument
}

int main(void) {
int arr[5], n = 5, i;

for (i = 0; i < n; i++) {
arr[i] = i;
}

printf("%d %d", arr[3], n); // prints: 3 5

test(arr, n);
printf("%d %d", arr[3], n); // prints: 8 5

return 0;
}

main 中对 test 函数的调用传入了实参 arr,它的值是 arr 数组在内存中的基地址。test 函数中的参数 a 得到这个基地址值的一份副本。换句话说,参数 a 与实参 arr 指向同一组数组存储位置。因此,当 test 函数修改 a 数组中存储的某个值(a[3] = 8)时,会影响实参数组中的对应位置(arr[3] 现在是 8)。原因在于 a 的值是 arr 的基地址,而 arr 的值也是 arr 的基地址,所以 a 和 arr 指的是同一个数组(内存中同一组存储位置)!图 1 展示了执行到 test 函数即将返回时的栈内容。

The call in main to the test function is passed the argument arr, whose value is the base address of the arr array in memory. The parameter a in the test function gets a copy of this base address value. In other words, parameter a refers to the same array storage locations as its argument, arr. As a result, when the test function changes a value stored in the a array (a[3] = 8), it affects the corresponding position in the argument array (arr[3] is now 8). The reason is that the value of a is the base address of arr, and the value of arr is the base address of arr, so both a and arr refer to the same array (the same storage locations in memory)! Figure 1 shows the stack contents at the point in the execution just before the test function returns.

A stack with two frames: main at the bottom and test on the top. main has two variables, an integer n (5) and an array storing values 0, 1, 2, 8, and 4. Test also has two values, an integer size (2) and an array parameter arr that stores the base memory address of the array in main’s stack frame.

图 1. 带数组参数的函数的栈内容

Figure 1. The stack contents for a function with an array parameter

译注 · 图中内容

栈中有两个帧:main 在下,test 在上。main 有两个变量:整数 n(5)和一个存放 0、1、2、8、4 的数组。test 也有两个变量:整数 size(2)和数组参数(图的 alt 文字写作 arr,对应代码中的参数 a),它存放的是 main 栈帧中那个数组的基地址。

参数 a 得到的是数组实参 arr 的基地址值,这意味着两者指向内存中同一组数组存储位置。我们用从 a 指向 arr 的箭头来表示这一点。被 test 函数修改过的值以高亮显示。修改参数 size 的值不会改变其对应实参 n 的值,但修改 a 所指向的某个元素的值(例如 a[3] = 8)确实会影响 arr 中对应位置的值。

Parameter a is passed the value of the base address of the array argument arr, which means they both refer to the same set of array storage locations in memory. We indicate this with the arrow from a to arr. Values that get modified by the function test are highlighted. Changing the value of the parameter size does not change the value of its corresponding argument n, but changing the value of one of the elements referred to by a (for example, a[3] = 8) does affect the value of the corresponding position in arr.

1.5.4. 字符串与 C 字符串库简介

1.5.4. Introduction to Strings and the C String Library

Python 实现了字符串类型,并提供了丰富的字符串操作接口,但 C 中没有对应的字符串类型。C 的字符串是用 char 值的数组实现的。并非每个字符数组都被用作 C 字符串,但每个 C 字符串都是一个字符数组。

Python implements a string type and provides a rich interface for using strings, but there is no corresponding string type in C. Instead, strings are implemented as arrays of char values. Not every character array is used as a C string, but every C string is a character array.

回想一下,C 中定义的数组可能比程序最终用到的更大。例如,我们在前面「访问数组的方法」一节中看到,可以声明一个大小为 10 的数组,却只用前六个位置。这一点对字符串有重要影响:我们不能假定字符串的长度等于存放它的数组的长度。因此,C 中的字符串必须以一个特殊的字符值——空字符(null character,'\0')——结尾,来标示字符串的结束。

Recall that arrays in C might be defined with a larger size than a program ultimately uses. For example, we saw earlier in the section “Array Access Methods” that we might declare an array of size 10 but only use the first six positions. This behavior has important implications for strings: we can’t assume that a string’s length is equal to that of the array that stores it. For this reason, strings in C must end with a special character value, the null character ('\0'), to indicate the end of the string.

以空字符结尾的字符串称为以空字符结尾的(null-terminated)字符串。虽然 C 中的所有字符串都应当以空字符结尾,但没有正确处理空字符是 C 新手常见的错误来源。使用字符串时要记住,字符数组声明的容量必须足以存放字符串中的每个字符,再加上空字符('\0')。例如,要存放字符串 "hi",至少需要一个含三个 char 的数组(一个存 'h',一个存 'i',一个存 '\0')。

Strings that end with a null character are said to be null-terminated. Although all strings in C should be null-terminated, failing to properly account for null characters is a common source of errors for novice C programmers. When using strings, it’s important to keep in mind that your character arrays must be declared with enough capacity to store each character value in the string plus the null character ('\0'). For example, to store the string "hi", you need an array of at least three chars (one to store 'h', one to store 'i', and one to store '\0').

由于字符串很常用,C 提供了一个字符串库,其中包含操作字符串的函数。使用这些字符串库函数的程序需要包含 string.h 头文件。

Because strings are commonly used, C provides a string library that contains functions for manipulating strings. Programs that use these string library functions need to include the string.h header.

用 printf 打印字符串的值时,在格式字符串中使用 %s 占位符。printf 函数会打印数组实参中的所有字符,直到遇到 '\0' 字符为止。类似地,字符串库函数通常要么通过查找 '\0' 字符来定位字符串的末尾,要么在它们修改的字符串末尾加上一个 '\0' 字符。

When printing the value of a string with printf, use the %s placeholder in the format string. The printf function will print all the characters in the array argument until it encounters the '\0' character. Similarly, string library functions often either locate the end of a string by searching for the '\0' character or add a '\0' character to the end of any string that they modify.

下面是一个使用字符串和字符串库函数的示例程序:

Here’s an example program that uses strings and string library functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h> // include the C string library

int main(void) {
char str1[10];
char str2[10];
int len;

str1[0] = 'h';
str1[1] = 'i';
str1[2] = '\0';

len = strlen(str1);

printf("%s %d\n", str1, len); // prints: hi 2

strcpy(str2, str1); // copies the contents of str1 to str2
printf("%s\n", str2); // prints: hi

strcpy(str2, "hello"); // copy the string "hello" to str2
len = strlen(str2);
printf("%s has %d chars\n", str2, len); // prints: hello has 5 chars
}

C 字符串库中的 strlen 函数返回其字符串参数中的字符个数。字符串结尾的空字符不计入字符串长度,所以 strlen(str1) 的调用返回 2(字符串 "hi" 的长度)。strcpy 函数从源字符串(第二个参数)向目标字符串(第一个参数)一次复制一个字符,直到遇到源字符串中的空字符为止。

The strlen function in the C string library returns the number of characters in its string argument. A string’s terminating null character doesn’t count as part of the string’s length, so the call to strlen(str1) returns 2 (the length of the string "hi"). The strcpy function copies one character at a time from a source string (the second parameter) to a destination string (the first parameter) until it reaches a null character in the source.

注意,大多数 C 字符串库函数都要求调用者传入容量足够的字符数组,以便函数完成工作。例如,你不应该用一个装不下源字符串的目标字符串去调用 strcpy,那样做会导致程序出现未定义行为!

Note that most C string library functions expect the call to pass in a character array that has enough capacity for the function to perform its job. For example, you wouldn’t want to call strcpy with a destination string that isn’t large enough to contain the source; doing so will lead to undefined behavior in your program!

C 字符串库函数还要求传给它们的字符串值格式正确,即以 '\0' 字符结尾。作为 C 程序员,你有责任确保传给 C 库函数处理的是有效的字符串。因此,在上例对 strcpy 的调用中,如果源字符串(str1)没有被初始化为以 '\0' 字符结尾,strcpy 就会越过 str1 数组的边界继续复制,导致可能引起崩溃的未定义行为。

C string library functions also require that string values passed to them are correctly formed, with a terminating '\0' character. It’s up to you as the C programmer to ensure that you pass in valid strings for C library functions to manipulate. Thus, in the call to strcpy in the preceding example, if the source string (str1) was not initialized to have a terminating '\0' character, strcpy would continue beyond the end of the str1 array’s bounds, leading to undefined behavior that could cause it to crash.

原书警示

上面的例子安全地使用了 strcpy 函数。但一般来说,strcpy 存在安全风险,因为它假定目标空间大到足以存放整个字符串,而实际情况未必如此(例如字符串来自用户输入时)。

我们现在先介绍 strcpy,是为了让字符串的入门更简单,在 2.6 节中我们会介绍更安全的替代方法。

The previous example uses the strcpy function safely. In general, though, strcpy poses a security risk because it assumes that its destination is large enough to store the entire string, which may not always be the case (for example, if the string comes from user input).

We chose to show strcpy now to simplify the introduction to strings, but we illustrate safer alternatives in Section 2.6.

下一章我们会更详细地讨论 C 字符串和 C 字符串库。

In the next chapter, we discuss C strings and the C string library in more detail.