Week 5 数据结构

欢迎！

之前几周已经向您介绍了编程的基本组成部分。
你在 C 中学习的所有知识使你能够使用更高级的编程语言（例如 Python）实现这些组成部分。
每周，概念都变得越来越严峻，就像山变得越来越陡。本周，随着我们探索数据结构，挑战变得更加平衡。
其中，您已经了解了内存如何在内存中组织数据中。
今天，我们将讨论如何组织内存中的数据以及随着你不断增长的知识和出现的设计可能性。

数据结构

数据结构本质上是内存中的组织形式。

在内存中组织数据的方法有很多种。

数据类型是我们可以从概念上想象的数据类型。在学习科学的时候，从这些概念数据结构开始通常很有用。学习这些计算机抽象以后更容易理解如何实现更具体的数据结构。

队列

队列是抽象数据结构的一种形式。

具有队列特定的属性。首先，它们是先进先出或“先进先出”。你可以想象自己在游乐园排队等待游乐设施。队列的第一个人可以先上车。最后一个人可以最后上车。
队列有一些特定的操作。例如，一个元素可以进入队列，否则加入队列。另外，当一个元素到达队列首时，它可以出队列，否则离开队列。

在代码中，你可以将队列想象如下：

const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
queue;

请注意，名为 people 的队列类型为 person。CAPACITY 表示队列最多能承载多少元素。整数 size 表示队列当前实际安装了多少元素，而不管它最多能承载多少元素。

栈

队列对比栈。从根本上来说，栈的属性与队列的属性不同。具体来说，它是 LIFO 或“后进先出”。就像在餐厅里堆放托盘一样，最后装入的托盘是第一个可能被拿起的托盘。
栈也有一些特定的操作。例如，push 会把某个元素放到栈顶；pop 会从栈顶删除一个元素。

在代码中，你可能会想象一个栈，如下所示：

const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
stack;

请注意，名为 people 的队列类型为 person。CAPACITY 表示栈最多能多少高。整数 size 表示栈当前实际安装了多少个元素，而不管它最多能容纳多少。请注意，数组和队列的代码是一样的。

你可能会认为上面的代码有一个限制。由于内存的容量是在代码中预先确定的。因此，堆栈可能总是太大。你可能会想象只使用 5000 个堆栈中的一个位置。
如果我们的栈是动态的就更好了：它能够随着元素的加入而增长。

杰克了解事实

我们观看了埃隆大学的 Shannon Duvall 教授制作的名为 Jack Learns the Facts 的视频。

调整储备大小

回到第2周，我们向你介绍了你的第一个数据结构。
内存是一个连续的内存。

你可能会想象如下的存储：

在内存中，还有其他程序、函数和重要存储的其他值。其中许多可能是未使用的垃圾值，它们曾在某个时刻被使用过，但现在可供使用。

想象一下，您想在我们的数据库中存储第四个值 4 。需要分配一个新的内存区域将旧的内存移动到新的数据库吗？首先，这个新的内存区域将填充垃圾值。

当值被添加到这个新的内存区域时，旧的垃圾值将被覆盖。

最终，所有旧的垃圾值都将被我们的新数据覆盖。

这种方法的缺点之一是它的设计非常糟糕：每次添加一个数字时，我们都必须逐项复制内存。

储备

如果我们能够将 4 放置在内存中的其他位置，不是很好吗？根据定义，这将不再是一个阵列，因为 4 将不再连续位于内存中。我们如何连接内存中的不同位置？

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

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

#include

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]);
    }
}

请注意，上面的代码和我们在本课程前面学到的内容非常相似。内存被预先分配给了三个要素。

根据我们最近获得的知识，我们可以利用对指针的理解来创建更好的设计。修改你的代码如下：

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

#include
#include

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 的列表。接下来，把第一个列表复制到第二个列表中。值 4 被添加到 tmp 列表中。由于 list 指向的内存块不再使用，所以用 free(list) 释放它。最后，让 list指针指向 tmp 所指向的内存块。程序打印 list 的内容，然后释放它。另外，请注意这里包含了 stdlib.h。

将 list 和 tmp 视为指向内存块的两个标志是很有用的。如上例所示，list 在某个点指向一个大小为 3 的内存块。到最后，list 被告知指向一个大小为 4 的内存块。从技术上讲，到上述代码结束时，tmp 和 list 都指向相同的块内存。

对于不循环的情况下我们可以使用复制备份的一种方法是使用 realloc：

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

#include
#include

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 重新分配到新的内存。

有人可能会想分配远超列表所需的内存，例如需要 3 个或 4 个位置时直接分配 30 个位置。但是，这是一个糟糕的设计，因为它会因为不一定需要时占用系统资源。另外，也无法保证最终真的会需要超过 30 个元素的空间。

链表

最近几周，你已经了解了三个有用的原语。struct 是你可以自己定义的数据类型。 点表示法中的 . 允许你访问该结构内部的变量。* 运算符用于声明指针或取消引用变量。
今天，我们向您介绍 -> 运算符。这是一个箭头。该运算符转到一个地址并查看结构内部。
链表是允许 C 语言中最强大的数据结构之一。链表允许你包含位于不同内存区域的值。此外，它们是动态的，你可以根据需要增长和缩小列表。

你可能会想象三个值存储在三个不同的内存区域中，如下所示：

如何将这些值粘贴到一个列表中？

我们可以将上图的数据想象如下：

我们可以使用更多的内存，通过指针来记录下一个元素的位置。

请注意，NULL用于指示列表中下一个没有其他内容。

目前，我们会在内存中保留一个元素，即一个指针，用于跟踪列表中的第一个项目，称为列表的“头”。

抽象出内存地址，列表如下所示：

这些盒子称为节点。节点包含一个元素，以及一个名为next的指针。在代码中，你可以将节点想象如下：

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

请注意，此节点中包含的元素是一个名为 number 的整数。其次，它还包含一个名为 next 的节点指针，会指向内存中某处的另一个节点。

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

// Start to build a linked list by prepending nodes

#include
#include
#include

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。对于列表中的每个元素，node 的内存通过 malloc 分配到节点的大小。n->number（或 n 的数字字段）被分配一个整数。n->next（或 n 的下一个字段）被分配为 null。然后，该节点被分配在内存位置 list 处的列表指针。

从概念上讲，我们可以想象创建链表的过程。首先，声明了 node *list ，但它是一个垃圾值。

接下来，在内存中分配一个名为 n 的节点。

接下来，节点的 number 被赋值为 1。

接下来，节点的 next 字段被分配为 NULL。

接下来，list 指向 n 所指向的内存位置。n 和 list 现在指向同一个位置。

然后创建一个新的节点。number 和 next 字段都填充了垃圾值。

n 节点（新节点）的 number 值更新为 2。

另外，next 字段参数更新。

最重要的是，我们不想失去与任何这些节点的连接，捂住它们永远丢失。因此，n 的 next 字段指向与 list 的内存位置相同。

最后，list 被更新为指向 n。现在，我们已经包含了两个元素的链表。

查看列表图表，我们可以看到最后添加的数字是列表中出现的第一个相应数字。，我们如果按顺序打印列表，从第一个节点开始，列表将出现乱序。

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

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

#include
#include
#include

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 节点。

在这个例子中，插入列表总是按照\(O(1)\)的顺序，因为只需要很少的步骤就可以插入到列表的前面。
考虑搜索这个列表所需的时间，它的数量级别是 \(O(n)\)，因为在最坏的情况下，必须搜索整个列表才能找到某个元素。向列表中添加新元素的时间复杂度取决于该元素被添加到哪里。下面的示例对此进行了说明。
链表不存储在连续的内存块中。只要有足够的系统资源，它们就可以随着你的愿望增长。然而，缺点是需要更多的内存来跟踪列表而不是数据库。对于每个元素，你不仅必须存储该元素的值，还必须存储指向下一个节点的指针。另外，存在链表不能像备份中那样进行索引，因为我们需要遍历第一个 \(n - 1\) 元素来替换第一个 \(n\)元素的位置。因此，必须线性搜索上图所示的列表。因此，在如上构造的列表中不可能进行二分搜索。

另外，你可以将数字放在列表中，如下面所示代码：

// Appends numbers to a linked list

#include
#include
#include

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。

另外，你也可以在添加元素时对列表进行排序：

// Implements a sorted linked list of numbers

#include
#include
#include

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)\) 中运行，因为在最坏的情况下，我们必须查看所有当前元素。

也许代码可能看起来很复杂。但是，请注意，使用指针和上面的语法，我们可以将内存中不同位置的数据拼接在一起。

树

备份提供了可以快速搜索的连续内存。备份还提供了进行二分搜索的机会。
我们可以结合备份和链表的优点吗？

二叉搜索树是另一种数据结构，可用于更有效的地存储数据，方便可以搜索和检索数据。

你可以想象一下已排序的数字序列。

想象一下中心值成为树的顶部。那些小于该值的被放置在左侧。最大该值的值位于右侧。

然后可以使用指针指向每个内存区域的正确位置，以便可以连接这些节点中的每个一个。

在代码中，可以按如下方式实现。

// Implements a list of numbers as a binary search tree

#include
#include

// Represents a node
typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

void free_tree(node *root);
void print_tree(node *root);

int main(void)
{
    // Tree of size 0
    node *tree = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 1;
    n->left = NULL;
    n->right = NULL;
    tree->left = n;

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 3;
    n->left = NULL;
    n->right = NULL;
    tree->right = n;

    // Print tree
    print_tree(tree);

    // Free tree
    free_tree(tree);
    return 0;
}

void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

void print_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    print_tree(root->left);
    printf("%i\n", root->number);
    print_tree(root->right);
}

请注意，此搜索函数首先转到 tree 的位置。然后，使用电位来搜索 number。free_tree 函数电位地释放树。print_tree 电位地打印树。

像上面这样的树提供了数据库所不提供的活力。它可以按照我们的意愿生长和缩小。
另外，当树平衡时，应提供\(O(log n)\)的搜索时间。

字典

字典是另一种数据结构。

字典，就像实际的书本字典一样，有一个单词和一个定义，有一个键和一个值。

算法的圣杯的时间复杂度是\(O(1)\)或恒定时间。究竟，最终的访问是即时的。

字典可以通过哈希提供这种访问速度。

哈希和哈希表

哈希是获取一个值并能够输出一个值的想法，该值后面将成为该值的快捷方式。

例如，哈希 apple 可能会哈希为 1 值，而 berry 可能会哈希为 2 。因此，找到 apple 就像询问 hash 算法 apple 存储在哪里一样简单。虽然在设计方面并不理想，但最终将所有 a 放在一个存储桶中，将 b放在另一个存储桶中，这种“存储桶化”哈希值的概念说明了如何使用这个概念：哈希值可用于快捷地查找此类值。
哈希函数是一种算法，它会将增大的值缩小为较小且可预测的值。通常，该函数接收你要加入哈希表的元素，并返回一个整数，表示该元素应该装入队列的哪个索引位置。
哈希表是缓存和链表的奇妙组合。当在代码中实现时，哈希表是指向节点的指针的*缓存。

分布表可以想象如下：

请注意，这是分配了每个值的内存中的字母表。

然后，在数据库的每个位置，使用链表来跟踪存储那里的每个值：

冲突是指当你将值添加到存储表时，并且存储位置已经存在某些内容。在上面，冲突只是简单地附加到列表的补充。

通过更好地编程哈希表和哈希算法可以减少冲突。你可以想象对上述内容的改进如下：

考虑以下哈希算法示例：

这可以用代码实现，如下所示：

#include

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

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

作为程序员，你必须在两者之间做取舍：使用更多内存来创建更大的哈希表，从而可能减少搜索时间；或者使用更少内存，但可能增加搜索时间。
此结构提供\(O(n)\) 的搜索时间。

特里树

Trie是另一种形式的数据结构。Trie是备份树。

Trie总是可以在恒定期限内搜索到。

Trie 的一个缺点是它们往往会占用大量内存。请注意，我们为了存储 Toad 就需要 \(26 \times 4 = 104\) 个 node！

Toad 将存储如下：

Tom 将存储如下：

此结构提供\(O(1)\) 的搜索时间。
这种结构的缺点是需要多少资源才能使用它。

总结

在本课程中，你学习了如何使用指针构建新的数据结构。具体来说，我们深入研究了……

数据结构
栈和队列
调整托盘大小
链表
字典
特里树

下次见！