6.1. 第 5 周：数据结构¶

6.1.1. 欢迎！¶

课程的前几周向你介绍了编程的基本构建模块。
你在 C 语言中学到的一切将使你能够在 Python 等高级编程语言中实现这些构建模块。
每周，概念都变得越来越具有挑战性，就像山坡变得越来越陡峭一样。本周，随着我们探索数据结构，挑战趋于平缓。
迄今为止，你已经了解了数组如何在内存中组织数据。
今天，我们将讨论在内存中组织数据以及由你不断增长的知识所引发的设计可能性。

6.1.2. 杰克了解事实¶

我们观看了一段由伊隆大学香农·杜瓦尔教授制作的名为 Jack Learns the Facts 的视频。

6.1.3. 数据结构¶

数据结构本质上是内存中的组织形式。
在内存中组织数据的方式有很多种。
抽象数据类型 是我们可以在概念上想象的那些类型。在学习计算机科学时，从这些概念性的数据结构入手通常很有用。学习这些内容将有助于日后更容易理解如何实现更具体的数据结构。

6.1.4. 队列¶

队列是抽象数据结构的一种形式。
队列具有特定的性质。具体来说，它们是 FIFO （先进先出）。你可以想象自己在游乐园排队乘坐游乐设施。队伍中的第一个人最先乘坐。最后一个人最后乘坐。
队列关联着特定的操作。例如，元素可以被入队；也就是说，该元素可以加入队伍或队列。此外，当元素到达队首时，它可以被出队或离开队列。
在代码中，你可以将队列想象如下：
```
const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
queue;
```
请注意，名为 people 的数组类型为 person 。 CAPACITY 表示队列可能达到的最大高度。整数 size 表示队列的实际填充程度，与其可以容纳的容量无关。

6.1.5. 栈¶

队列与栈形成对比。从根本上说，栈的特性不同于队列的特性。具体来说，它是 LIFO 或“后进先出”。就像在餐厅里叠放托盘一样，最后放入堆叠的托盘是第一个可以被取走的。
栈具有与之相关的特定操作。例如，push （压栈）将某物放置到栈顶。pop （弹栈）是从栈顶移除某物。
在代码中，你可以将栈想象如下：
```
const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
stack;
```
注意，名为 people 的数组类型为 person 。 CAPACITY 表示栈可能达到的最大高度。整数 size 表示栈的实际填充程度，与其可能容纳的容量无关。请注意，此代码与队列的代码相同。
你可能会认为上述代码存在局限性，因为数组的容量在此代码中始终是预先确定的。因此，栈可能会一直过大。你可能会想象在 5000 个位置的栈中只使用一个位置。
如果我们的栈是动态的——能够随着元素的添加而增长——那就太好了。

6.1.6. 数组¶

回到第 2 周，我们向你介绍了第一种数据结构。
数组是一块连续的内存块。
你可以将数组想象如下：

线性表

在终端中，输入 code list.c 并按如下方式编写代码：

// Implements a list of numbers with an array of fixed size

#include <stdio.h>

int main(void)
{
    // List of size 3
    int list[3];

    // Initialize list with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Print list
    for (int i = 0; i < 3; i++)
    {
        printf("%i\n", list[i]);
    }
}

请注意，上述内容与我们在本课程早期所学的内容非常相似。内存已为三个项预先分配。你可以下载此代码 here 。

如果我们能够将 4 存放在内存的其他地方，那该多好？根据定义，这将不再是一个数组，因为 4 将不再位于连续的内存中。我们如何连接内存中的不同位置？
在内存中，其他程序、函数和变量也存储着其他值。其中许多可能是曾经使用过但现在可供使用的未用垃圾值。
假设你想在数组中存储第四个值 4 。所需的操作是分配一块新的内存区域，并将旧数组移动到新区域。最初，这块新内存区域将充满垃圾值。
当值被添加到这片新的内存区域时，旧的垃圾值将被覆盖。
最终，所有旧的垃圾值都会被我们的新数据覆盖。
这种方法的一个缺点是设计不佳：每次添加一个数字时，都必须逐项复制数组。

list1.c

基于我们最近获得的知识，我们可以利用对指针的理解来改进此代码的设计。请按以下方式修改你的代码：

// Implements a list of numbers with an array of dynamic size

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // List of size 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Initialize list of size 3 with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // List of size 4
    int *tmp = malloc(4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }

    // Copy list of size 3 into list of size 4
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    // Add number to list of size 4
    tmp[3] = 4;

    // Free list of size 3
    free(list);

    // Remember list of size 4
    list = tmp;

    // Print list
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Free list
    free(list);
    return 0;
}

请注意，首先创建了一个包含三个整数的线性表。然后，三个内存地址可以分别被赋值为 1 、 2 和 3 。接着，创建一个长度为四的线性表。随后，将第一个线性表复制到第二个线性表。值 4 被添加到 tmp 线性表中。由于 list 所指向的内存块不再使用，因此使用命令 free(list) 将其释放。最后， list 指针现在被设置为指向 tmp 所指向的内存块。 list 的内容被打印出来，然后被释放。此外，请注意包含了 stdlib.h 。你可以下载此代码 here 。

将 list 和 tmp 视为指向内存块的指针是很有用的。如上面的示例所示， list 曾指向一个长度为 3 的数组。最后， list 被要求指向一个长度为 4 的内存块。严格来说，在上述代码执行结束时， tmp 和 list 都指向了同一块内存。

list2.c

我们可以不用 for 循环而通过 realloc 来复制数组的一种方法是：

// Implements a list of numbers with an array of dynamic size using realloc

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // List of size 3
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    // Initialize list of size 3 with numbers
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // Resize list to be of size 4
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list);
        return 1;
    }
    list = tmp;

    // Add number to list
    list[3] = 4;

    // Print list
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // Free list
    free(list);
    return 0;
}

注意，线性表通过 realloc 被重新分配到一个新数组。你可以下载此代码 here 。

人们可能会 tempted 为线性表分配远超所需的内存，例如分配 30 个项而非所需的 3 或 4 个。然而，这是一种糟糕的设计，因为它在可能并不需要时浪费了系统资源。此外，几乎无法保证最终会需要超过 30 个项的内存。

6.1.7. 线性表¶

最近几周，你学习了三个有用的基本要素。 struct 是一种你可以自行定义的数据类型。点表示法 中的 . 允许你访问该结构内部的变量。 * 运算符用于声明指针或解引用变量。
今天，你将学习 -> 运算符。它是一个箭头。该运算符会跳转到一个地址并查看结构内部。
链表是 C 语言中最强大的数据结构之一。链表允许你包含位于内存不同区域的值。此外，它们允许你根据需要动态地增长和缩短列表。
你可以想象三个值存储在三个不同的内存区域中，如下所示：
如何将这些值串联成一个线性表？
我们可以将上述数据想象如下：
我们可以利用更多内存，通过指针来跟踪下一项的位置。

请注意，NULL 用于表示线性表中没有 下一个 元素。
按照惯例，我们会额外在内存中保留一个指针，用于跟踪线性表中的第一个元素，该指针称为线性表的 头结点 。
抽象掉内存地址后，线性表将呈现如下形式：
这些盒子称为结点。一个结点同时包含一个项和一个称为 next 的指针。在代码中，你可以将结点想象如下：
```
typedef struct node
{
    int number;
    struct node *next;
}
node;
```
请注意，此结点中包含的项是一个名为 number 的整数。其次，包含一个名为 next 的指向结点的指针，它将指向内存中的另一个结点。

list3.c

我们可以重新创建 list.c 以利用线性表：

// Start to build a linked list by prepending nodes

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Prepend node to list
        n->next = list;
        list = n;
    }
    return 0;
}

首先， node 被定义为一个 struct 。对于线性表中的每个元素，通过 malloc 分配一个 node 大小的内存空间。 n->number （或 n 的数字字段）被赋值为一个整数。 n->next （或 n 的下一个字段）被赋值为 NULL 。然后，该结点被放置在内存位置 list 处的线性表开头。你可以下载此代码 here 。

从概念上讲，我们可以想象创建线性表的过程。首先， node *list 被声明，但它包含一个垃圾值。
接下来，一个名为 n 的结点在内存中被分配。
接下来，结点的 number 被赋值为 1 。
接下来，结点的 next 字段被赋值为 NULL 。
接下来， list 被指向 n 所指向的内存位置。 n 和 list 现在指向同一位置。
然后创建一个新结点。 number 和 next 字段都被填充为垃圾值。
n 的结点（新结点）的 number 值被更新为 2 。
此外， next 字段也会被更新。
最重要的是，我们不想失去与任何这些结点的连接，以免它们永远丢失。因此， n 的 next 字段指向与 list 相同的内存位置。
最后， list 被更新为指向 n 。现在我们有了一个包含两个项的链表。
观察我们的线性表示意图，可以看到最后添加的数字是线性表中第一个出现的数字。因此，如果我们从第一个结点开始按顺序打印线性表，线性表将呈现无序状态。

list4.c

我们可以按正确顺序打印线性表，如下所示：

// Print nodes in a linked list with a while loop

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // Prepend node to list
        n->next = list;
        list = n;
    }

    // Print numbers
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
    return 0;
}

请注意， node *ptr = list 创建了一个临时变量，该变量指向与 list 相同的位置。 while 循环会打印结点 ptr 所指向的内容，然后更新 ptr 使其指向线性表中的 next 结点。你可以在此处下载此代码 here 。

在此示例中，向线性表中插入操作的时间复杂度始终为 \(O(1)\)，因为在线性表前端插入仅需极少的步骤。
考虑搜索该线性表所需的时间，其时间复杂度为 \(O(n)\)，因为在最坏情况下，必须遍历整个线性表才能找到目标元素。向线性表中添加新元素的时间复杂度取决于该元素的插入位置。下文示例将对此进行说明。
链表并非存储在连续的内存块中。只要系统资源充足，它可以扩展到任意大小。然而，其缺点是需要比数组更多的内存来维护线性表结构。对于每个元素，不仅要存储其值，还需存储指向下一个结点的指针。此外，链表无法像数组那样通过索引直接访问，因为要定位第 \(n\) 个元素，必须先遍历前 \(n - 1\) 个元素。因此，上图所示的线性表必须进行线性搜索。故而，在上述构造的线性表中无法执行二分搜索。

list7.c

此外，你可以将数字放置在线性表的末尾，如下面代码所示：

// Appends numbers to a link list

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            // This node is the whole list
            list = n;
        }

        // If list has numbers already
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

注意这段代码如何遍历该线性表以找到末尾。当追加元素（添加到线性表末尾）时，我们的代码将以 \(O(n)\) 运行，因为在添加最后一个元素之前，我们必须遍历整个线性表。此外，请注意使用了一个名为 next 的临时变量来跟踪 ptr->next 。你可以下载此代码 here 。

list8.c

此外，你可以在添加元素时对线性表进行排序：

// Implements a sorted linked list of numbers

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            list = n;
        }

        // If number belongs at beginning of list
        else if (n->number < list->number)
        {
            n->next = list;
            list = n;
        }

        // If number belongs later in list
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }

                // If in middle of list
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
    return 0;
}

请注意，该线性表在构建过程中已保持有序。若要按此特定顺序插入元素，每次插入的代码运行时间仍为 \(O(n)\)，因为在最坏情况下我们需要遍历所有当前元素。你可以下载此代码 here 。

线性表

作为最后的润色，可以创建一个函数来卸载线性表：

// Frees memory in cases of error too

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

void unload(node *list);

int main(void)
{
    // Memory for numbers
    node *list = NULL;

    // Build list
    for (int i = 0; i < 3; i++)
    {
        // Allocate node for number
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            unload(list);
            return 1;
        }
        n->number = get_int("Number: ");
        n->next = NULL;

        // If list is empty
        if (list == NULL)
        {
            list = n;
        }

        // If number belongs at beginning of list
        else if (n->number < list->number)
        {
            n->next = list;
            list = n;
        }

        // If number belongs later in list
        else
        {
            // Iterate over nodes in list
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // If at end of list
                if (ptr->next == NULL)
                {
                    // Append node
                    ptr->next = n;
                    break;
                }

                // If in middle of list
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;
                    ptr->next = n;
                    break;
                }
            }
        }
    }

    // Print numbers
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // Free memory
    unload(list);
    return 0;
}

void unload(node *list)
{
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

请注意， unload 函数会释放整个线性表。你可以下载此代码 here 。

这段代码可能看起来很复杂。然而，请注意，借助指针和上述语法，我们能够将分散在内存不同位置的数据连接起来。

6.1.8. 树¶

数组提供可快速搜索的连续内存。数组还提供了进行二分查找的机会。
我们能否结合数组和链表的最佳特性？
二叉搜索树是另一种数据结构，可用于更高效地存储数据，以便进行搜索和检索。
你可以想象一个已排序的数字序列。
设想中间值成为树的根结点。小于该值的元素置于左侧，大于该值的元素置于右侧。
指针可用于指向每块内存的正确位置，从而将这些结点连接起来。

在代码中，搜索这样一棵树可以实现如下：

bool search(node *tree, int number)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (number < tree->number)
    {
        return search(tree->left, number);
    }
    else if (number > tree->number)
    {
        return search(tree->right, number);
    }
    else if (number == tree->number)
    {
        return true;
    }
}

请注意此搜索函数如何递归地搜索树。如果搜索的数字小于当前结点的数字，则搜索左子树；如果大于，则搜索右子树。这种递归方法使得在树平衡时能够高效搜索，时间复杂度为 O(log n)。

树提供了数组所不具备的动态性。它可以根据我们的意愿增长或缩小。
此外，当树平衡时，这种结构提供的搜索时间为 \(O(log n)\)。

6.1.9. 哈希与哈希表¶

算法时间复杂度的圣杯是 \(O(1)\) 或 常数时间 。也就是说，终极目标是实现即时访问。
哈希的思想是获取一个值，并能够输出一个可作为其后快捷访问途径的值。
例如，对 apple 进行哈希可能得到值 1 ，而对 berry 进行哈希可能得到 2 。因此，查找 apple 就像询问哈希算法 apple 存储在哪里一样简单。虽然从设计角度看并非理想方案（即将所有以 a 开头的项放入一个桶，所有以 b 开头的项放入另一个桶），但这种将哈希值分桶的概念说明了如何使用该思想：哈希值可用于加速查找此类值。
哈希函数是一种将较大值缩减为较小且可预测值的算法。通常，该函数接收一个希望添加到哈希表中的项，并返回一个整数，表示该项应放置的数组索引。
哈希表是数组与链表的绝佳组合。在代码中实现时，哈希表是一个由指向结点的指针组成的数组。
哈希表可以想象如下：

注意，这是一个被赋值为字母表中每个值的数组。
然后，在数组的每个位置，使用一个线性表来跟踪存储在该位置的每个值：
冲突是指向哈希表添加值时，哈希位置已存在某个元素。在上例中，冲突项只是被追加到线性表的末尾。
通过优化哈希表和哈希算法的实现可以减少冲突。你可以设想对上述方法的改进如下：
考虑以下哈希算法示例：

这可以通过如下代码实现：

#include <ctype.h>

unsigned int hash(const char *word)
{
    return toupper(word[0]) - 'A';
}

注意哈希函数如何返回 toupper(word[0]) - 'A' 的值。

作为程序员，你必须做出抉择：是使用更多内存构建较大的哈希表以可能减少查找时间，还是使用较少内存但可能增加查找时间。
该结构的查找时间为 \(O(n)\)。

6.1.10. 字典树¶

字典树是另一种形式的数据结构。字典树是由数组构成的树。
字典树 始终可以在常数时间内进行搜索。
字典树 的一个缺点是它们往往占用大量内存。请注意，仅仅为了存储 Toad ，我们就需要 \(26 \times 4 = 104\) 个结点！
Toad 的存储方式如下：
Tom 随后将被存储如下：
这种结构提供 \(O(1)\) 的查找时间。
这种结构的缺点是使用它需要多少资源。

6.1.11. 总结¶

在本课中，你学习了如何使用指针构建新的数据结构。具体而言，我们深入探讨了…

数据结构
栈与队列
链表
哈希与哈希表
字典树

下次再见！

CS50 计算机科学入门（中文版）

第 6 章数据结构

6.1. 第 5 周：数据结构¶

6.1.1. 欢迎！¶

6.1.2. 杰克了解事实¶

6.1.3. 数据结构¶

6.1.4. 队列¶

6.1.5. 栈¶

6.1.6. 数组¶

6.1.7. 线性表¶

6.1.8. 树¶

6.1.9. 哈希与哈希表¶

6.1.10. 字典树¶

6.1.11. 总结¶

CS50 计算机科学入门（中文版）

第 6 章 数据结构

6.1. 第 5 周：数据结构¶

6.1.1. 欢迎！¶

6.1.2. 杰克了解事实¶

6.1.3. 数据结构¶

6.1.4. 队列¶

6.1.5. 栈¶

6.1.6. 数组¶

6.1.7. 线性表¶

6.1.8. 树¶

6.1.9. 哈希与哈希表¶

6.1.10. 字典树¶

6.1.11. 总结¶

第 6 章数据结构