Week 2 数组
欢迎！
在上一节课中，我们学习了 C，这是一种基于文本的编程语言。
本周，我们将更深入地了解一些额外的构建块，它们会帮助我们从底层开始学习更多编程知识。
从根本上说，除了编程的基本要素之外，本课程也关乎问题解决。因此，我们还会进一步关注如何处理计算机科学问题。
到课程结束时，你将学会如何使用前面提到的这些构建块，解决各种各样的计算机科学问题。
阅读水平
本课程中我们会解决的一个现实问题，是理解阅读水平。
在一些同学的帮助下，我们展示了不同阅读水平的文本。
本周，量化阅读水平将成为你众多编程挑战之一。
编译
加密是把明文隐藏起来，使旁人无法直接阅读的行为。相应地，解密就是把一段加密文本还原成人类可读形式的行为。
一段加密后的文本可能如下所示：
U I J T J T D T 5 0
- 回想上周，你学习了编译器：这是一种专门的计算机程序，可以把源代码转换成计算机能够理解的机器代码。
例如，你可能有如下计算机程序：
#include
int main(void)
{
printf("hello, world\n");
}
编译器会把上面的代码转换成如下机器代码：
作为 CS50 学生所使用的编程环境 VS Code，使用了名为 clang 的编译器，也就是 c language。
- 你可以在终端窗口中输入以下命令来编译代码：
clang -o hello hello.c。
命令行参数是在命令行中提供给 clang 的内容，例如 -o hello hello.c。
- 在终端窗口中运行
./hello，你的程序就会按预期运行。
请看上周的以下代码：
#include
#include
int main(void)
{
string name = get_string("What's your name? ");
printf("hello, %s\n", name);
}
要编译这段代码，可以输入
clang -o hello hello.c -lcs50。如果你输入
make hello，它会运行一个命令，执行 clang 并创建一个可供用户运行的输出文件。VS Code 已经预先配置好，使得
make会为了方便用户而和 clang 一起运行许多命令行参数。上面的内容是为了说明编译代码的过程和概念，让你能更深入地理解；不过，在 CS50 中使用
make完全没问题，而且这也是课程的预期做法！编译包含四个主要步骤，包括以下内容：
第一，预处理会把你代码中的头文件，也就是由 # 标记的内容（例如 #include <cs50.h>），有效地复制并粘贴到你的文件中。在这一步中，来自 cs50.h 的代码会被复制到你的程序中。类似地，就像你的代码包含 #include <stdio.h> 一样，计算机上某处 stdio.h 中的代码也会被复制到你的程序里。这个步骤可以形象地表示如下：
string get_string(string prompt);
int printf(string format, ...);
int main(void)
{
string name = get_string("What's your name? ");
printf("hello, %s\n", name);
}
第二，编译会把你的程序转换成汇编代码。这个步骤可以形象地表示如下：
...
main:
.cfi_startproc
# BB#0:
pushq %rbp
.Ltmp0:
.cfi_def_cfa_offset 16
.Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
.Ltmp2:
.cfi_def_cfa_register %rbp
subq $16, %rsp
xorl %eax, %eax
movl %eax, %edi
movabsq $.L.str, %rsi
movb $0, %al
callq get_string
movabsq $.L.str.1, %rdi
movq %rax, -8(%rbp)
movq -8(%rbp), %rsi
movb $0, %al
callq printf
...
第三，汇编涉及编译器把汇编代码转换成机器代码。这个步骤可以形象地表示如下：
01111111010001010100110001000110
00000010000000010000000100000000
00000000000000000000000000000000
00000000000000000000000000000000
00000001000000000011111000000000
00000001000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
10100000000000100000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
01000000000000000000000000000000
00000000000000000100000000000000
00001010000000000000000100000000
01010101010010001000100111100101
01001000100000111110110000010000
00110001110000001000100111000111
01001000101111100000000000000000
00000000000000000000000000000000
00000000000000001011000000000000
11101000000000000000000000000000
00000000010010001011111100000000
00000000000000000000000000000000
00000000000000000000000001001000
...
最后，在链接步骤中，你所包含的库中的代码也会被转换成机器代码，并与你的代码合并。最终会输出一个可执行文件。
调试
- 每个人在写代码时都会犯错。
调试是定位并移除代码中 bug 的过程。
本课程中你会用到的一种调试技巧叫做橡皮鸭调试法：你可以对一个无生命的物体（或对自己）讲解代码，帮助自己思考代码为什么没有按预期工作。当你的代码遇到问题时，可以考虑把问题大声说出来，甚至真的对一只橡皮鸭讲解。如果你不想和一只小塑料鸭说话，也完全可以和身边的人交流！
我们创建了 CS50 Duck 和 CS50.ai，作为帮助你调试代码的工具。
请看上周的以下图片：
请看下面这段故意插入了 bug 的代码：
// Buggy example for printf
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("#\n");
}
}
请注意，这段代码打印了四个方块，而不是三个。
在终端窗口中输入
code buggy0.c，并写入上面的代码。运行这段代码时，会出现四块砖，而不是预期的三块。
printf 是一种非常有用的调试代码方式。你可以按如下方式修改代码：
// Buggy example for printf
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("i is %i\n", i);
printf("#\n");
}
}
请注意，这段代码会在循环的每次迭代中输出 i 的值，从而帮助我们调试代码。
运行这段代码后，你会看到多条语句，包括 i is 0、i is 1、i is 2 和 i is 3。看到这些之后，你可能会意识到代码还需要进一步修正如下：
#include
int main(void)
{
for (int i = 0; i 3; i++)
{
printf("#\n");
}
}
请注意，<= 已经被替换为 <。
这段代码还可以进一步改进如下：
// Buggy example for debug50
#include
#include
void print_column(int height);
int main(void)
{
int h = get_int("Height: ");
print_column(h);
}
void print_column(int height)
{
for (int i = 0; i height; i++)
{
printf("#\n");
}
}
请注意，编译并运行这段代码仍然会产生 bug。
为了解决这个 bug，我们会使用一个新工具。
调试中的第二种工具称为调试器，这是程序员创建的软件工具，用来帮助追踪代码中的 bug。
在 VS Code 中，已经为你提供了预配置的调试器。
要使用这个调试器，首先设置一个断点：点击代码某一行左侧、行号左边的位置。点击后，你会看到一个红点出现。可以把它想象成一个停止标志，要求编译器暂停，让你思考代码在这个位置发生了什么。
第二，运行
debug50 ./buggy0。你会注意到调试器启动后，代码中的某一行会以类似金色的颜色高亮显示。字面意义上，代码已经在这一行暂停了。请注意窗口左上角会显示所有局部变量，包括当前还没有值的h。在窗口顶部，你可以点击step over按钮，程序会继续逐步执行。注意观察h的值如何变化。虽然这个工具不会直接告诉你 bug 在哪里，但它会帮助你放慢节奏，逐步看到代码是如何运行的。你也可以使用
step into，进一步查看有问题代码的细节。
数组
在第 0 周，我们讨论过
bool、int、char、string等数据类型。每种数据类型都需要一定数量的系统资源：
bool 1 byte
int 4 bytes
long 8 bytes
float 4 bytes
double 8 bytes
char 1 byte
string ? bytes
在你的计算机内部，可用内存是有限的。
从物理层面看，在计算机内存中，你可以想象不同类型的数据是如何存储的。比如，char 只需要 1 byte 内存，可能看起来如下：
类似地，一个需要 4 bytes 的 int 可能如下所示：
我们可以创建一个程序来探索这些概念。在终端中输入 code scores.c，并编写如下代码：
// Averages three (hardcoded) numbers
#include
int main(void)
{
// Scores
int score1 = 72;
int score2 = 73;
int score3 = 33;
// Print average
printf("Average: %f\n", (score1 + score2 + score3) / 3.0);
}
请注意，右侧的数字是浮点值 3.0，因此最终计算结果会以浮点值形式得到。
- 运行
make scores后，程序会运行。
你可以想象这些变量是如何存储在内存中的：
数组是一系列连续存储在内存中的值。
int scores[3] 是告诉编译器：请提供三个连续的、大小为 int 的内存位置，用来存储三个 scores。基于我们的程序，你可以把代码修改如下：
// Averages three (hardcoded) numbers using an array
#include
#include
int main(void)
{
// Scores
int scores[3];
scores[0] = 72;
scores[1] = 73;
scores[2] = 33;
// Print average
printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
}
请注意，score[0] 会通过对名为 scores 的数组在位置 0 进行索引，查看该内存位置中存储的值。
可以看到，虽然上面的代码可以工作，但仍有改进空间。请将代码修改如下：
// Averages three numbers using an array and a loop
#include
#include
int main(void)
{
// Get scores
int scores[3];
for (int i = 0; i 3; i++)
{
scores[i] = get_int("Score: ");
}
// Print average
printf("Average: %f\n", (scores[0] + scores[1] + scores[2]) / 3.0);
}
请注意，我们使用 scores[i] 对 scores 进行索引，其中 i 由 for 循环提供。
我们可以简化，或者说抽象掉平均值的计算。请将代码修改如下：
// Averages three numbers using an array, a constant, and a helper function
#include
#include
// Constant
const int N = 3;
// Prototype
float average(int length, int array[]);
int main(void)
{
// Get scores
int scores[N];
for (int i = 0; i N; i++)
{
scores[i] = get_int("Score: ");
}
// Print average
printf("Average: %f\n", average(N, scores));
}
float average(int length, int array[])
{
// Calculate average
int sum = 0;
for (int i = 0; i length; i++)
{
sum += array[i];
}
return sum / (float) length;
}
请注意，这里声明了一个名为 average 的新函数。另外，还声明了一个 const，也就是常量 N。最重要的是，请注意 average 函数接收 int array[]，这意味着编译器会把一个数组传递给这个函数。
- 数组不仅可以作为容器：它们还可以在函数之间传递。
字符串
string本质上就是一个char类型变量的数组：也就是字符数组。
要探索 char 和 string，请在终端窗口中输入 code hi.c，并编写如下代码：
// Prints chars
#include
int main(void)
{
char c1 = 'H';
char c2 = 'I';
char c3 = '!';
printf("%c%c%c\n", c1, c2, c3);
}
请注意，这会输出一个由字符组成的字符串。
类似地，请对代码做如下修改：
#include
int main(void)
{
char c1 = 'H';
char c2 = 'I';
char c3 = '!';
printf("%i %i %i\n", c1, c2, c3);
}
请注意，把 %c 替换为 %i 后，会打印 ASCII 码。
结合下面这张图，你可以看到字符串是一个字符数组，它从第一个字符开始，以一个称为 NUL character 的特殊字符结束：
如果用十进制来想象，你的数组会如下所示：
为了进一步理解 string 的工作方式，请将代码修改如下：
// Treats string as array
#include
#include
int main(void)
{
string s = "HI!";
printf("%c%c%c\n", s[0], s[1], s[2]);
}
请注意，printf 语句展示了名为 s 的数组中的三个值。
和之前一样，我们可以按如下方式把 %c 替换为 %i：
// Prints string's ASCII codes, including NUL
#include
#include
int main(void)
{
string s = "HI!";
printf("%i %i %i %i\n", s[0], s[1], s[2], s[3]);
}
请注意，这会打印字符串的 ASCII 码，包括 NUL。
假设我们想同时表示 HI! 和 BYE!。请将代码修改如下：
// Multiple strings
#include
#include
int main(void)
{
string s = "HI!";
string t = "BYE!";
printf("%s\n", s);
printf("%s\n", t);
}
请注意，这个示例声明并使用了两个字符串。
你可以把它形象地表示如下：
我们还可以进一步改进这段代码。请将代码修改如下：
// Array of strings
#include
#include
int main(void)
{
string words[2];
words[0] = "HI!";
words[1] = "BYE!";
printf("%s\n", words[0]);
printf("%s\n", words[1]);
}
请注意，这两个字符串都存储在一个 string 类型的数组中。
我们可以把这两个字符串合并到一个字符串数组里。
#include
#include
int main(void)
{
string words[2];
words[0] = "HI!";
words[1] = "BYE!";
printf("%c%c%c\n", words[0][0], words[0][1], words[0][2]);
printf("%c%c%c%c\n", words[1][0], words[1][1], words[1][2], words[1][3]);
}
请注意，这里创建了一个 words 数组。它是一个字符串数组。每个单词都存储在 words 中。
字符串长度
编程中，尤其是在 C 中，一个常见问题是找出数组的长度。我们如何在代码中实现这一点？请在终端窗口中输入 code length.c，并编写如下代码：
// Determines the length of a string
#include
#include
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
// Count number of characters up until '\0' (aka NUL)
int n = 0;
while (name[n] != '\0')
{
n++;
}
printf("%i\n", n);
}
请注意，这段代码会一直循环，直到找到 NUL 字符。
可以把计数过程抽象到一个函数中，从而改进这段代码，如下所示：
// Determines the length of a string using a function
#include
#include
int string_length(string s);
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
int length = string_length(name);
printf("%i\n", length);
}
int string_length(string s)
{
// Count number of characters up until '\0' (aka NUL)
int n = 0;
while (s[n] != '\0')
{
n++;
}
return n;
}
请注意，一个名为 string_length 的新函数会一直计数字符，直到找到 NUL。
由于这是编程中非常常见的问题，其他程序员已经在 string.h 库中创建了寻找字符串长度的代码。你可以按如下方式修改代码来获取字符串长度：
// Determines the length of a string using a function
#include
#include
#include
int main(void)
{
// Prompt for user's name
string name = get_string("Name: ");
int length = strlen(name);
printf("%i\n", length);
}
请注意，这段代码使用了文件顶部声明的 string.h 库。进一步地，它使用了该库中的一个名为 strlen 的函数，用来计算传入字符串的长度。
- 我们的代码可以站在前人程序员的肩膀上，使用他们创建的库。
ctype.h 是另一个非常有用的库。假设我们想创建一个程序，把所有小写字符转换成大写字符。在终端窗口中输入 code uppercase.c，并编写如下代码：
// Uppercases a string
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
if (s[i] >= 'a' && s[i] 'z')
{
printf("%c", s[i] - 32);
}
else
{
printf("%c", s[i]);
}
}
printf("\n");
}
请注意，这段代码会迭代字符串中的每一个值。程序会查看每个字符。如果该字符是小写字母，就从它的值中减去 32，把它转换成大写字母。
回想上周的内容，你可能还记得这张 ASCII 值表：
0
NUL
16
DLE
32
SP
48
0
64
@
80
P
96
`
112
p
1
SOH
17
DC1
33
!
49
1
65
A
81
Q
97
a
113
q
2
STX
18
DC2
34
”
50
2
66
B
82
R
98
b
114
r
3
ETX
19
DC3
35
#
51
3
67
C
83
S
99
c
115
s
4
EOT
20
DC4
36
$
52
4
68
D
84
T
100
d
116
t
5
ENQ
21
NAK
37
%
53
5
69
E
85
U
101
e
117
u
6
ACK
22
SYN
38
&
54
6
70
F
86
V
102
f
118
v
7
BEL
23
ETB
39
’
55
7
71
G
87
W
103
g
119
w
8
BS
24
CAN
40
(
56
8
72
H
88
X
104
h
120
x
9
HT
25
EM
41
)
57
9
73
I
89
Y
105
i
121
y
10
LF
26
SUB
42
*
58
:
74
J
90
Z
106
j
122
z
11
VT
27
ESC
43
+
59
;
75
K
91
[
107
k
123
{
12
FF
28
FS
44
,
60
<
76
L
92
\
108
l
124
13
CR
29
GS
45
-
61
=
77
M
93
]
109
m
125
}
14
SO
30
RS
46
.
62
>
78
N
94
^
110
n
126
~
15
SI
31
US
47
/
63
?
79
O
95
_
111
o
127
DEL
- 当一个小写字符减去
32后，会得到同一个字符的大写版本。
虽然这个程序可以完成我们想要的事情，但使用 ctype.h 库会有更简单的方法。请将程序修改如下：
// Uppercases string using ctype library (and an unnecessary condition)
#include
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
if (islower(s[i]))
{
printf("%c", toupper(s[i]));
}
else
{
printf("%c", s[i]);
}
}
printf("\n");
}
请注意，程序会迭代字符串中的每个字符。toupper 函数会接收 s[i]。每个字符（如果是小写）都会被转换成大写。
值得一提的是，toupper 会自动知道只把小写字符转换成大写。因此，你的代码可以简化如下：
// Uppercases string using ctype library
#include
#include
#include
#include
int main(void)
{
string s = get_string("Before: ");
printf("After: ");
for (int i = 0, n = strlen(s); i n; i++)
{
printf("%c", toupper(s[i]));
}
printf("\n");
}
请注意，这段代码使用 ctype 库把字符串转换成大写。
- 你可以在 Manual Pages 上阅读
ctype库的全部功能。
命令行参数
Command-line arguments 是在命令行中传递给程序的参数。例如，你在 clang 后面输入的所有语句都被视为命令行参数。你也可以在自己的程序中使用这些参数！
在终端窗口中输入 code greet.c，并编写如下代码：
// Uses get_string
#include
#include
int main(void)
{
string answer = get_string("What's your name? ");
printf("hello, %s\n", answer);
}
请注意，这会对用户说 hello。
不过，如果能在程序运行之前就接收参数，是不是更好？请将代码修改如下：
// Prints a command-line argument
#include
#include
int main(int argc, string argv[])
{
if (argc == 2)
{
printf("hello, %s\n", argv[1]);
}
else
{
printf("hello, world\n");
}
}
请注意，这个程序知道 argc，也就是命令行参数的数量；还知道 argv，也就是在命令行中作为参数传入的字符数组。
- 因此，按照这个程序的语法，执行
./greet David会让程序输出hello, David。
你可以使用下面的代码打印每一个命令行参数：
// Prints command-line arguments
#include
#include
int main(int argc, string argv[])
{
for (int i = 0; i argc; i++)
{
printf("%s\n", argv[i]);
}
}
退出状态
当程序结束时，计算机会收到一个特殊的退出码。
当程序无错误退出时，会向计算机提供状态码
0。通常，当发生错误并导致程序结束时，计算机会收到状态码1。
你可以输入 code status.c，并编写如下程序来说明这一点：
// Returns explicit value from main
#include
#include
int main(int argc, string argv[])
{
if (argc != 2)
{
printf("Missing command-line argument\n");
return 1;
}
printf("hello, %s\n", argv[1]);
return 0;
}
请注意，如果你没有提供 ./status David，会得到退出状态 1。然而，如果你确实提供了 ./status David，会得到退出状态 0。
你可以在终端中输入
echo $?，查看上一次运行命令的退出状态。可以想象，你也许会使用上面程序的一部分来检查用户是否提供了正确数量的命令行参数。
密码学
密码学是加密和解密消息的技艺。
现在，有了数组、字符和字符串这些构建块，你就可以加密和解密消息了。
plaintext 和一个 key 会被提供给一个 cipher，从而得到加密后的文本。
密钥是与明文一起传递给密码算法的特殊参数。密码算法会使用密钥来决定如何实现自己的加密算法。
本周，你将完成与上述内容类似的编程挑战。
总结
在本课中，你进一步学习了编译的细节，以及数据如何存储在计算机中。具体来说，你学习了……
编译器通常如何工作。
如何使用四种方法调试代码。
如何在代码中使用数组。
数组如何把数据存储在连续的内存区域中。
字符串本质上如何只是字符数组。
如何在代码中与数组交互。
命令行参数如何传递给你的程序。
密码学的基本构建块。
下次见！