Week 4 内存

欢迎！

前几周，我们讨论过图像是由像素这样更小的组成部分构成的。
今天，我们将进一步详细介绍构成这些图像的零和一。特别是，我们将更深入地研究构成文件（包括图像）的基本构建块。
此外，我们将讨论如何访问存储在计算机内存中的底层数据。
开始今天的内容前，请记住，本讲涉及的概念可能需要一些时间才能真正理解。

像素艺术

像素是颜色的小方块，也就是排列在上下、左右网格中的一个个点。

你可以将图像想象为位图，其中 0 代表黑色，1 代表白色。

十六进制

RGB，也就是红、绿、蓝，是表示每种颜色含量的数字。在 Adobe Photoshop 中，你可以看到如下设置：

请注意红色、蓝色和绿色的数量如何改变所选颜色。

从上图中可以看出，颜色并不只是由三个值表示。在窗口底部，还有一个由数字和字符组成的特殊值。255 表示为 FF。为什么会这样？

十六进制是一种计数系统，一共有 16 个计数值。它们如下：

  0 1 2 3 4 5 6 7 8 9 A B C D E F

请注意，F 代表 15。

十六进制也称为 base-16，也就是 16 进制。
使用十六进制计数时，每一列都是 16 的幂。
数字 0 表示为 00。
数字 1 表示为 01。
数字 9 由 09 表示。
数字 10 表示为 0A。
数字 15 表示为 0F。
数字 16 表示为 10。
数字 255 表示为 FF，因为 16 x 15（也就是 F）是 240。再加上 15 就是 255。这是使用两位十六进制系统可以表示的最大数字。
十六进制很有用，因为它可以用更少的数字来表示。十六进制使我们能够更简洁地表示信息。

内存

在前几周，你可能还记得我们用图示表示过一块块连续的内存。把十六进制编号应用到这些内存块上，可以把它们想象成如下形式：

你可以想象，上面的 10 究竟表示内存中的位置，还是表示值 10，可能会让人混淆。因此，按照惯例，十六进制数字通常会加上 0x 前缀，如下所示：

在终端窗口中，输入code addresses.c并编写代码，如下所示：

// Prints an integer

#include

int main(void)
{
    int n = 50;
    printf("%i\n", n);
}

请注意 n 如何与值 50 一起存储在内存中。

你可以想象该程序如何存储该值，如下所示：

指针

C 语言有两个与内存相关的强大运算符：

  & Provides the address of something stored in memory.
  * Instructs the compiler to go to a location in memory.

我们可以通过修改代码来利用这些知识，如下所示：

// Prints an integer's address

#include

int main(void)
{
    int n = 50;
    printf("%p\n", &n);
}

注意 %p，它允许我们查看内存中某个位置的地址。&n 可以直译为“n 的地址”。执行这段代码会返回一个以 0x 开头的内存地址。

指针是某个存储物地址的变量。最简单地说，指针是计算机内存中的地址。

考虑以下代码：

int n = 50;
int *p = &n;

请注意，p 是一个指针，其中包含整数 n 的地址。

修改你的代码如下：

// Stores and prints an integer's address

#include

int main(void)
{
    int n = 50;
    int *p = &n;
    printf("%p\n", p);
}

请注意，这段代码与之前的代码效果相同。我们只是利用了关于 & 和 * 运算符的新知识。

为了说明 * 运算符的用法，请考虑以下内容：

// Stores and prints an integer via its address

#include

int main(void)
{
    int n = 50;
    int *p = &n;
    printf("%i\n", *p);
}

请注意，printf 行打印 p 位置处的整数。 int *p 创建一个指针，其作用是存储整数的内存地址。

你可以将我们的代码可视化如下：

请注意，指针看起来相当大。事实上，指针通常存储为 8 字节值。 p 存储是 50 的地址。

你可以更准确地引导指针可视化为指向另一个地址的一个地址：

字符串

现在我们有了剪刀的心智模型，我们可以在前面的课程中进行一定程度的简化。

修改你的代码如下：

// Prints a string

#include
#include

int main(void)
{
    string s = "HI!";
    printf("%s\n", s);
}

请注意，打印了字符串s。

回想一下，字符串只是一个字符队列。例如，string s = "HI!"可以表示如下：

然而，s 到底是什么？ s 存储在内存中的哪里？正如你可以想象的，s 需要存储在某个位置。你可以将 s 与字符串的关系可视化，如下所示：

请注意名为 s 的指针如何告诉编译器字符串的第一个字节在内存中的位置。

修改你的代码如下：

// Prints a string's address as well the addresses of its chars

#include
#include

int main(void)
{
    string s = "HI!";
    printf("%p\n", s);
    printf("%p\n", &s[0]);
    printf("%p\n", &s[1]);
    printf("%p\n", &s[2]);
    printf("%p\n", &s[3]);
}

请注意，上面打印了字符串 s 中每个字符的内存位置。 & 符号用于显示字符串中每个元素的地址。运行此代码时，请注意元素 0、1、2 和 3 在内存中各自相邻。

你可以按如下方式修改相同代码：

// Declares a string with CS50 Library

#include
#include

int main(void)
{
    string s = "HI!";
    printf("%s\n", s);
}

请注意，这段代码会显示从 s 所在位置开始的字符串。它相当于拿掉了 cs50.h 提供的 string 数据类型这层“训练轮”。这是原始的 C 代码，没有 CS50 库提供的辅助封装。

拿掉这层“训练轮”后，你可以再次修改代码：

// Declares a string without CS50 Library

#include

int main(void)
{
    char *s = "HI!";
    printf("%s\n", s);
}

请注意，CS50.h 已被删除。字符串被实现为 char *。

你可以想象一个数据类型的字符串是如何创建的。
上周，我们学习了如何创建自己的数据类型结构。
CS50 库包含如下结构：typedef char *string
当使用 CS50 库时，该结构允许使用名为 string 的自定义数据类型。

肘关节

卸载能力是对内存位置进行卸载的能力。

你可以修改代码以打印出字符串中的每个内存位置，如下所示：

// Prints a string's chars

#include

int main(void)
{
    char *s = "HI!";
    printf("%c\n", s[0]);
    printf("%c\n", s[1]);
    printf("%c\n", s[2]);
}

请注意，我们在 s 位置打印每个字符。

另外，你可以按如下方式修改代码：

// Prints a string's chars via pointer arithmetic

#include

int main(void)
{
    char *s = "HI!";
    printf("%c\n", *s);
    printf("%c\n", *(s + 1));
    printf("%c\n", *(s + 2));
}

请注意，打印 s 位置的第一个字符。然后，打印 s + 1 位置的字符，依此类推。

同样，请考虑以下事项：

// Prints substrings via pointer arithmetic

#include

int main(void)
{
    char *s = "HI!";
    printf("%s\n", s);
    printf("%s\n", s + 1);
    printf("%s\n", s + 2);
}

请注意，此代码打印存储在 s 入口的各个内存位置的值。

字符串比较

字符串只是由其第一个字节的位置标识的字符存储。

在本课程的前面，我们考虑了整数的比较。我们可以通过在终端窗口中键入 code compare.c 来用代码表示这一点，如下所示：

// Compares two integers

#include
#include

int main(void)
{
    // Get two integers
    int i = get_int("i: ");
    int j = get_int("j: ");

    // Compare integers
    if (i == j)
    {
        printf("Same\n");
    }
    else
    {
        printf("Different\n");
    }
}

请注意，此代码从用户处获取两个圆形文字对它们进行比较。

但是，对于字符串，无法使用 == 运算符比较两个字符串。
使用 == 运算符尝试比较字符串将尝试比较字符串的内存位置而不是其中的字符。因此，我们建议使用 strcmp。

为了说明这一点，请按如下方式修改你的代码：

// Compares two strings' addresses

#include
#include

int main(void)
{
    // Get two strings
    char *s = get_string("s: ");
    char *t = get_string("t: ");

    // Compare strings' addresses
    if (s == t)
    {
        printf("Same\n");
    }
    else
    {
        printf("Different\n");
    }
}

请注意，为两个字符串输入 HI! 仍然会导致输出 Different。

为什么这些字符串看起来不同？你可以使用以下内容来观察地了解原因：

因此，上面的 compare.c 代码实际上是在检查内存地址是否不同，而不是检查字符串本身是否不同。

使用strcmp，我们可以更正我们的代码：

// Compares two strings using strcmp

#include
#include
#include

int main(void)
{
    // Get two strings
    char *s = get_string("s: ");
    char *t = get_string("t: ");

    // Compare strings
    if (strcmp(s, t) == 0)
    {
        printf("Same\n");
    }
    else
    {
        printf("Different\n");
    }
}

请注意，如果字符串相同，strcmp 可以返回 0。

为了进一步说明这两个字符串如何存在于两个位置，请按如下方式修改代码：

// Prints two strings

#include
#include

int main(void)
{
    // Get two strings
    char *s = get_string("s: ");
    char *t = get_string("t: ");

    // Print strings
    printf("%s\n", s);
    printf("%s\n", t);
}

请注意，我们现在如何存储两个单独的字符串，可能位于两个不同的位置。

稍加修改即可看到这两个存储字符串的位置：

// Prints two strings' addresses

#include
#include

int main(void)
{
    // Get two strings
    char *s = get_string("s: ");
    char *t = get_string("t: ");

    // Print strings' addresses
    printf("%p\n", s);
    printf("%p\n", t);
}

请注意，打印语句中的 %s 已更改为 %p。

复制和malloc

编程中的一个常见需求是一个字符串复制到另一个字符串。

在终端窗口中，输入code copy.c并编写代码，如下所示：

// Capitalizes a string

#include
#include
#include
#include

int main(void)
{
    // Get a string
    string s = get_string("s: ");

    // Copy string's address
    string t = s;

    // Capitalize first letter in string
    t[0] = toupper(t[0]);

    // Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

请注意，string t = s 将 s 的地址复制到 t。这并不能实现我们的愿望。字符串没有被复制——只有地址被复制。另外，请注意包含 ctype.h。

你可以将上面的代码可视化如下：

请注意，s 和 t 仍然指向相同的内存块。这不是字符串的真实副本。相反，它们是指向同一个字符串的两个指针。

在解决这个挑战之前，重要的是要确保我们的代码不会遇到“分段错误”，即我们Trie将string s复制到string t，而string t不存在。我们可以使用strlen函数来帮助实现这一点，如下所示：

// Capitalizes a string, checking length first

#include
#include
#include
#include

int main(void)
{
    // Get a string
    string s = get_string("s: ");

    // Copy string's address
    string t = s;

    // Capitalize first letter in string
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }

    // Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

请注意，strlen用于确保string t存在。如果没有，则不会复制任何内容。

为了能够创建字符串的真实副本，我们需要引入两个新的组成部分。首先，malloc 允许程序员分配特定大小的内存块。其次，free 允许你告诉编译器“释放”你之前分配的内存块。

我们可以修改代码来创建字符串的真实副本，如下所示：

// Capitalizes a copy of a string

#include
#include
#include
#include
#include

int main(void)
{
    // Get a string
    char *s = get_string("s: ");

    // Allocate memory for another string
    char *t = malloc(strlen(s) + 1);

    // Copy string into memory, including '\0'
    for (int i = 0; i  strlen(s); i++)
    {
        t[i] = s[i];
    }

    // Capitalize copy
    t[0] = toupper(t[0]);

    // Print strings
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

请注意，malloc(strlen(s) + 1) 创建的内存块的长度是字符串 s 加一。这允许在我们最终复制的字符串中包含 null \0 字符。然后，for 循环遍历字符串 s 把每个值分配给字符串 t 上的相同位置。

事实证明我们的代码效率很低。修改你的代码如下：

// Capitalizes a copy of a string, defining n in loop too

#include
#include
#include
#include
#include

int main(void)
{
    // Get a string
    char *s = get_string("s: ");

    // Allocate memory for another string
    char *t = malloc(strlen(s) + 1);

    // Copy string into memory, including '\0'
    for (int i = 0, n = strlen(s); i  n; i++)
    {
        t[i] = s[i];
    }

    // Capitalize copy
    t[0] = toupper(t[0]);

    // Print strings
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

请注意，n = strlen(s) 现在定义在 for loop 的左侧。最好不要在 for 循环的中间条件下调用不需要的函数，因为它会再次地运行。将 n = strlen(s) 移至左侧时，函数 strlen 仅运行一次。

C 语言有一个名为 strcpy 的内置函数来复制字符串。可以按如下方式实现：

// Capitalizes a copy of a string using strcpy

#include
#include
#include
#include
#include

int main(void)
{
    // Get a string
    char *s = get_string("s: ");

    // Allocate memory for another string
    char *t = malloc(strlen(s) + 1);

    // Copy string into memory
    strcpy(t, s);

    // Capitalize copy
    t[0] = toupper(t[0]);

    // Print strings
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

请注意，strcpy 所做的工作与我们之前的 for 循环所做的工作相同。

如果出现问题，get_string 和 malloc 都会返回 NULL，这是内存中的一个特殊值。你可以编写可检查此 NULL 条件的代码，如下所示：

// Capitalizes a copy of a string without memory errors

#include
#include
#include
#include
#include

int main(void)
{
    // Get a string
    char *s = get_string("s: ");
    if (s == NULL)
    {
        return 1;
    }

    // Allocate memory for another string
    char *t = malloc(strlen(s) + 1);
    if (t == NULL)
    {
        return 1;
    }

    // Copy string into memory
    strcpy(t, s);

    // Capitalize copy
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }

    // Print strings
    printf("s: %s\n", s);
    printf("t: %s\n", t);

    // Free memory
    free(t);
    return 0;
}

请注意，如果获取的字符串长度为 0 或 malloc 失败，则返回 NULL。另外，请注意 free 让计算机你已经完成创建知道 malloc 的内存块。

瓦尔格林德

Valgrind 是一个工具，可以检查你使用 malloc 的程序是否存在与内存相关的问题。具体来说，它会检查你是否 free 你分配的所有内存。

考虑memory.c的以下代码：

// Demonstrates memory errors via valgrind

#include
#include

int main(void)
{
    int *x = malloc(3 * sizeof(int));
    x[1] = 72;
    x[2] = 73;
    x[3] = 33;
}

请注意，运行该程序不会导致任何错误。虽然 malloc 用于为磁盘分配足够的内存，但代码无法使用 free 分配内存。

如果你输入 make memory 后跟 valgrind ./memory，你将获得一份报告，其中报告程序导致内存丢失的位置。valgrind 揭示的一个错误是，我们尝试在数据库的第 4 个位置分配 33 的值，而我们只分配了一个大小为 3 的数据库。另一个错误是我们从未释放 x。

你可以修改代码以释放 x 的内存，如下所示：

// Demonstrates memory errors via valgrind

#include
#include

int main(void)
{
    int *x = malloc(3 * sizeof(int));
    x[1] = 72;
    x[2] = 73;
    x[3] = 33;
    free(x);
}

请注意，再次运行 valgrind 现在不会导致内存泄漏。

垃圾值

当你向编译器请求大量内存时，不能保证该内存值得空。

你分配的内存很可能在被计算机使用之前。因此，你可能会看到垃圾或垃圾值。这是因为你获得了一块内存但没有初始化它。例如，考虑 garbage.c 的以下代码：

#include
#include

int main(void)
{
    int scores[1024];
    for (int i = 0; i  1024; i++)
    {
        printf("%i\n", scores[i]);
    }
}

请注意，运行这段代码时，会为数组分配 1024 个内存位置，但 for 循环很可能显示其中并不是所有值都是 0。当你没有把内存块初始化为零或其他值时，最好始终意识到垃圾值可能存在。

Binky 的登山乐趣

我们观看了斯坦福大学的视频，它帮助我们可视化和理解指针。

交换

在现实世界中，编程的常见需求是交换两个值。当然，如果没有临时存储空间，就很难交换两个值。在实践中，你可以输入 code swap.c 并编写如下代码来查看其实际效果：

// Fails to swap two integers

#include

void swap(int a, int b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i, y is %i\n", x, y);
    swap(x, y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

请注意，虽然此代码运行，但它失效。即使这些值被发送到 swap 函数之后，也不会交换。为什么？

当你把值传给函数时，传过去的只是副本。x 和 y 的作用域仅限于当前代码中的 main 函数。也就是说，在 main 函数的大括号 {} 中创建的 x 和 y，只在 main 函数中有效。在上面的代码中，x 和 y 是按值传递的。

考虑下图：

请注意，我们在本课程中未使用的全局变量位于内存中的一个位置。各种函数存储在内存的另一个区域的stack中。

现在，考虑下图：

请注意，main 和 swap 有两个独立的帧或内存区域。因此，我们不能简单地从一个函数传递值到另一个函数来更改它们。

修改你的代码如下：

// Swaps two integers using pointers

#include

void swap(int *a, int *b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i, y is %i\n", x, y);
    swap(&x, &y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

请注意，变量不是通过Value提交的，而是通过引用提交的。即，向函数提供 a 和 b 的地址。因此，swap函数可以从main函数中知道在哪里对实际的a和b进行更改。

你可以将其想象如下：

渡口

堆溢出是指堆溢出，超出不应该超出的内存区域。
栈溢出是指调用过多函数时，溢出可用内存量。
这两者都被认为是瓶颈。

代码0

在 CS50 中，我们创建了类似 get_int 之类的函数来简化用户获取输入的行为。

scanf 是一个可以获取用户输入的内置函数。

我们可以使用 scanf 相当容易地重新实现 get_int ，如下所示：

// Gets an int from user using scanf

#include

int main(void)
{
    int n;
    printf("n: ");
    scanf("%i", &n);
    printf("n: %i\n", n);
}

请注意，n 的值存储在 scanf("%i", &n) 行中 n 的位置。

然而，Trie 重新实现 get_string 并不容易。考虑以下几点：

// Dangerously gets a string from user using scanf with array

#include

int main(void)
{
    char s[4];
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n", s);
}

请注意，不需要 & ，字符串很特殊。尽管如此，该程序并不会每次运行时都正确运行。在这个程序中，我们没有分配所需字符串的内存量。事实上，因为我们不知道用户可以输入多长的字符串！另外，我们不知道内存位置可能存在哪些垃圾值。

另外，你的代码可以修改如下。但是，我们必须为字符串预先分配一定量的内存：

// Using malloc

#include
#include

int main(void)
{
    char *s = malloc(4);
    if (s == NULL)
    {
        return 1;
    }
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n", s);
    free(s);
    return 0;
}

请注意，如果提供了四个字节的字符串，你可能会收到错误。

通过我们的代码简化如下，我们可以进一步理解预分配的这个本质问题：

#include

int main(void)
{
    char s[4];
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n", s);
}

请注意，如果我们预先分配大小为 4 的数组，输入 cat 时程序可以正常工作。但是，更长的字符串可能会产生错误。

有时，编译器或运行它的系统可能会分配比我们指示的更多的内存。但从根本上来说，上面的代码是不安全的。我们不能相信用户会输入适合我们预先分配的内存的字符串。

文件输入/输出

你可以读取和操作文件。虽然该主题将在未来一周进一步讨论，但请考虑以下 phonebook.c 代码：

// Saves names and numbers to a CSV file

#include
#include
#include

int main(void)
{
    // Open CSV file
    FILE *file = fopen("phonebook.csv", "a");

    // Get name and number
    char *name = get_string("Name: ");
    char *number = get_string("Number: ");

    // Print to file
    fprintf(file, "%s,%s\n", name, number);

    // Close file
    fclose(file);
}

请注意，此代码使用指针来访问文件。

你可以在运行上述代码之前创建一个名为 phonebook.csv 的文件或下载 phonebook.csv。运行上述程序并输入姓名和电话号码后，你会注意到这些数据仍然保留在你的 CSV 文件中。

如果我们想在运行程序之前确保 phonebook.csv 存在，我们可以修改如下代码：

// Saves names and numbers to a CSV file

#include
#include
#include

int main(void)
{
    // Open CSV file
    FILE *file = fopen("phonebook.csv", "a");
    if (!file)
    {
        return 1;
    }

    // Get name and number
    char *name = get_string("Name: ");
    char *number = get_string("Number: ");

    // Print to file
    fprintf(file, "%s,%s\n", name, number);

    // Close file
    fclose(file);
}

请注意，该程序通过调用return 1来阻止NULL卸载。

我们可以通过输入 code cp.c 并编写代码来实现我们自己的复制程序，如下所示：

// Copies a file

#include
#include

typedef uint8_t BYTE;

int main(int argc, char *argv[])
{
    FILE *src = fopen(argv[1], "rb");
    FILE *dst = fopen(argv[2], "wb");

    BYTE b;

    while (fread(&b, sizeof(b), 1, src) != 0)
    {
        fwrite(&b, sizeof(b), 1, dst);
    }

    fclose(dst);
    fclose(src);
}

请注意，此文件创建了我们自己的数据类型，名为 BYTE ，其大小为 uint8_t。然后，该文件读取 BYTE 放入其写入文件。

BMP 也是一组我们可以检查和操作的数据。本周，你将在习题集中亲自实践这一点！

总结

在本课中，你学习了指针，它让你能够访问并操作特定内存位置上的数据。具体来说，我们深入研究了……

像素艺术
十六进制
内存
指针
弦乐
拱顶
字符串比较
前面
malloc 和 Valgrind
垃圾值
交换
溢出
代码0
文件输入/输出

下次见！