Welcome!Data StructuresStacks and QueuesJack Learns the FactsResizing ArraysLinked ListsTreesDictionariesHashing and Hash TablesTriesSumming UpWelcome!前几周的所有内容都向大家展示了编程的基本构建块。你在 C 语言中学到的所有内容将使你能够在更高级的编程语言（如 Python）中实现这些构建块。今天，我们将讨论在内存中的组织数据。Data Structures数据结构 本质上是内存中的组织形式。有许多方法可以在内存中组织数据。抽象数据结构 是我们在概念上可以想象的结构。在学习计算机科学时，从这些概念性数据结构开始通常很有用。学习这些将使以后更容易理解如何实现更具体的数据结构。Stacks and Queues队列 是抽象数据结构的一种形式。队列具有特定的属性。也就是说，它们是 FIFO 或“先进先出”。你可以想象自己在游乐园排队兜风。排队的第一个人首先开始骑行。最后一个人最后骑车。队列具有与之关联的特定操作。例如，可以 对项目进行排队;也就是说，项目可以加入行或队列。此外，项目可以在到达行前排后取消 排队 或离开队列。队列对比 堆栈。从根本上说，堆栈的属性与队列不同。具体来说，它是 LIFO 或“后进先出”。就像在自助餐厅堆放托盘一样，最后放在堆叠中的托盘是第一个可以拿起来的托盘。堆栈具有与之关联的特定操作。例如，push 将某些内容放在堆栈的顶部。Pop 正在从堆栈顶部删除某些内容。在代码中，你可以想象一个堆栈，如下所示：

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

视频加载中...

Resizing Arrays回到第 2 周，我们向你介绍了你的第一个数据结构。数组是连续内存块。你可以想象一个数组，如下所示：在内存中，还有其他值由其他程序、函数和变量存储。其中许多可能是未使用的垃圾值，这些值曾经使用过，但现在可供使用。想象一下，你想在我们的数组中存储4？需要的是分配一个新的内存区域并将旧数组移动到新数组。旧的垃圾值将被我们的新数据覆盖。这种方法的缺点之一是它的设计很糟糕：每次我们添加一个数字时，我们都必须逐项复制数组。如果我们能够将4放在内存中其他地方，那不是很好吗？根据定义，这将不再是数组，因为4将不再位于连续内存中。在终端中，键入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]);      }  }

请注意，以上内容与我们之前在本课程中学到的内容非常相似。我们为三个项目预分配了内存。

基于我们最近获得的知识，我们可以利用我们对指针的理解来在此代码中创建更好的设计。按如下方式修改代码：

  // 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 的列表。接下来，将列表从第一个复制到第二个。4的值将添加到tmp列表中。由于list不再使用指向的内存块，因此使用free(list)命令释放它。最后，编译器被告知现在将list指针指向tmp指向的内存块。list的内容被打印出来，然后释放。

考虑一下list和tmp很有用，因为这两个都指向一大块内存。如上例所示，list在某一点 指向 大小为 3 的数组。到最后，list被告知指向大小为 4 的内存块。从技术上讲，在上述代码结束时，tmp和list两者都指向相同的内存块。C带有一个非常有用的函数，称为realloc，它将为你重新分配内存。 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;  }

请注意，int *tmp = realloc(list, 4 * sizeof(int))这将创建一个大小为四个整数的列表。然后，它将list的值复制到这个新数组中。最后，一个名为tmp的指针指向这个新数组的内存位置。复制由realloc处理。创建该副本后，将释放其list位置的内存。然后，调用list的指针指向tmp的位置，新数组所在的位置。

你可以想象realloc用于队列或堆栈的有用之处。随着数据量的增长，realloc可用于增加或缩小堆栈或队列。Linked Lists最近几周，你了解了三个有用的原语。struct是你可以自己定义的数据类型。.点表示法 允许你访问该结构中的变量。*运算符用于声明指针或取消引用变量。今天，向你介绍->操作员。它是一个箭头。此运算符转到地址并查看结构内部。链表 是 C 语言中最强大的数据结构之一。链表允许你包含位于内存不同区域的值。此外，它们允许你根据需要动态增长和缩小列表。你可以想象三个值存储在三个不同的内存区域，如下所示：如何将这些值拼接在一个列表中？我们可以将上图所示的数据想象如下：

我们可以利用更多的内存来跟踪下一个项目的位置。

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

按照惯例，我们将在内存中再保留一个元素，即指针，用于跟踪列表中的第一项。抽象出内存地址，列表将如下所示：这些框称为 节点。节点 包含一个名为 next 的项和指针。在代码中，你可以想象一个节点，如下所示：

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

请注意，此节点中包含的项是一个名为number的整数。其次，包含一个指向调用next节点的指针，该指针将指向内存中某处的另一个节点。

链表不存储在连续的内存块中。只要存在足够的系统资源，它们就可以根据需要增长。但是，缺点是需要更多的内存来跟踪列表而不是数组。这是因为对于每个元素，你不仅必须存储元素的值，还必须存储指向下一个节点的指针。此外，链表不能被索引成数组中的 类似元素，因为我们需要通过第一个n−1元素来查找第n个元素。因此，必须对上图的列表进行线性搜索。因此，在如上所述构建的列表中不可能进行二叉搜索。从概念上讲，我们可以想象创建链表的过程。首先，node *list被声明，但它具有垃圾值。接下来，在内存中分配一个调用的节点n。接下来，为节点number分配值 1。接下来，节点的next字段分配值NULL。接下来，list被指向n所指向的内存位置。 n和list现在指向同一个地方。然后创建一个新节点。number和next字段都填充了垃圾值。n的节点（新节点）的number值将更新为2 。此外，next字段也会更新。最重要的是，我们不想失去与这些节点中的任何一个的连接，以免它们永远丢失。因此，n的next字段指向与list相同的内存位置。最后，list更新为指向n 。我们现在有一个包含两个项目的链接列表。若要在代码中实现这一点，请按如下所示修改代码：

  // Prepends numbers to a linked list, using while loop to print  #include <cs50.h>  #include <stdio.h>  #include <stdlib.h>  typedef struct node  {      int number;      struct node *next;  }  node;  int main(int argc, char *argv[])  {      // Memory for numbers      node *list = NULL;      // For each command-line argument      for (int i = 1; i < argc; i++)      {          // Convert argument to int          int number = atoi(argv[i]);          // Allocate node for number          node *n = malloc(sizeof(node));          if (n == NULL)          {              return 1;          }          n->number = 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;      }      // Free memory      ptr = list;      while (ptr != NULL)      {          node *next = ptr->next;          free(ptr);          ptr = next;      }  }

请注意，用户在命令行中输入的内容将放入名为n的节点的number字段中，然后将该节点添加到list。例如，./list 1 2将数字1放入一个称为n节点的number字段，然后把指向list节点的指针放入节点的next字段，然后更新list为指向n。对2重复相同的过程。接下来，node *ptr = list创建一个临时变量，指向list指向同一位置。while打印ptr节点指向的内容，然后更新ptr以指向列表中的next节点。最后，释放所有内存。

考虑到搜索此列表所需的时间，它的顺序是O（n），因为在最坏的情况下，必须始终搜索整个列表才能找到项目。向列表中添加新元素的时间复杂度将取决于添加该元素的位置。以下示例对此进行了说明。作为程序员，你可以选择如何实现你的列表。例如，以下代码实现了一个链表，该链表将数字附加到列表的前面：

  // Prepends numbers to a linked list, using for loop to print  #include <cs50.h>  #include <stdio.h>  #include <stdlib.h>  typedef struct node  {      int number;      struct node *next;  }  node;  int main(int argc, char *argv[])  {      // Memory for numbers      node *list = NULL;      // For each command-line argument      for (int i = 1; i < argc; i++)      {          // Convert argument to int          int number = atoi(argv[i]);          // Allocate node for number          node *n = malloc(sizeof(node));          if (n == NULL)          {              return 1;          }          n->number = number;          n->next = NULL;          // Prepend node to list          n->next = list;          list = n;      }      // 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;      }  }

请注意数字如何放置在列表的开头。此插入将按以下顺序运行：O（1），因为执行此操作所需的步骤数不取决于列表的大小。

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

  // Implements a list of numbers using a linked list  #include <cs50.h>  #include <stdio.h>  #include <stdlib.h>  typedef struct node  {      int number;      struct node *next;  }  node;  int main(int argc, char *argv[])  {      // Memory for numbers      node *list = NULL;      // For each command-line argument      for (int i = 1; i < argc; i++)      {          // Convert argument to int          int number = atoi(argv[i]);          // Allocate node for number          node *n = malloc(sizeof(node));          if (n == NULL)          {              return 1;          }          n->number = 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;      }  }

请注意此代码如何沿着此列表向下移动以查找结尾。当附加一个元素时，（添加到列表的末尾）我们的代码将在O（n），因为我们必须先浏览整个列表，然后才能添加最终元素。

此外，你可以在添加项目时对列表进行排序：

  // Implements a sorted list of numbers using a linked list  #include <cs50.h>  #include <stdio.h>  #include <stdlib.h>  typedef struct node  {      int number;      struct node *next;  }  node;  int main(int argc, char *argv[])  {      // Memory for numbers      node *list = NULL;      // For each command-line argument      for (int i = 1; i < argc; i++)      {          // Convert argument to int          int number = atoi(argv[i]);          // Allocate node for number          node *n = malloc(sizeof(node));          if (n == NULL)          {              return 1;          }          n->number = 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;                  }              }          }      }      // 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;      }  }

请注意此列表在生成时是如何排序的。要按此特定顺序插入元素，我们的代码仍将在O（n）对于每次插入，就像在最坏的情况下一样，我们将不得不查看所有当前元素。

Trees二叉搜索树 是另一种数据结构，可用于更有效地存储数据，以便可以搜索和检索数据。你可以想象一个排序的数字序列。想象一下，中心值变成了一棵树的顶部。小于此值的那些将放置在左侧。大于此值的值位于右侧。然后，可以使用指针指向每个内存区域的正确位置，以便可以连接这些节点中的每一个。在代码中，这可以按如下方式实现。

  // Implements a list of numbers as a binary search tree  #include <stdio.h>  #include <stdlib.h>  // 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);  }

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

请注意，此搜索函数首先转到tree的位置。然后，它使用递归来搜索number。

像上面这样的树提供了数组无法提供的动态。它可以随心所欲地增长和缩小。Dictionaries字典 是另一种数据结构。词典与具有单词和定义的实际书籍形式词典一样，具有 键 和 值。时间复杂性的 圣杯 是O（1）或 恒定时间。也就是说，最终的访问是即时的。字典可以提供这种访问速度。Hashing and Hash Tables哈希 是获取一个值并能够输出一个值的想法，该值以后将成为该值的快捷方式。例如，对 苹果 进行哈希处理可以哈希为1，而 浆果 可以哈希为2 。因此，找到 苹果 就像询问 哈希 算法苹果存储在哪里一样简单。虽然在设计方面并不理想，但最终将所有 a 放在一个存储桶中，将 b 放在另一个存储桶中，但这种将哈希值 存储桶化 的概念说明了如何使用此概念：哈希值可用于快捷方式查找此类值。哈希函数 是一种算法，可将较大的值减少为可预测的小值。通常，此函数接收要添加到哈希表中的项目，并返回一个整数，表示应在其中放置该项目的数组索引。哈希表是数组和链表的绝佳组合。在代码中实现时，哈希表是指向 节点 的 指针数组。哈希表可以想象如下：

请注意，这是一个为字母表的每个值分配的数组。

然后，在数组的每个位置，使用链表来跟踪存储在那里的每个值：冲突 是指将值添加到哈希表，并且哈希位置已存在某些内容。在上面，碰撞只是附加到列表的末尾。可以通过更好地对哈希表和哈希算法进行编程来减少冲突。你可以想象对上述内容的改进如下：作为程序员，你必须决定使用更多内存来拥有大型哈希表的优势，并可能减少搜索时间或使用更少的内存并可能增加搜索时间。TriesTries 是另一种形式的数据结构。Tries 始终可在恒定时间内搜索。Trie 的一个缺点是它们往往会占用大量内存。请注意，我们需要26×5=130 node只是为了存放 Hagrid！Hagrid 将存储如下：

Hagrid一次用一个字母拼写，其中一个字母与一个列表 A 中的一个列表 H 相关联，依此类推

然后 Harry 将被存储如下：

Hagrid一次用一个字母拼写，其中一个字母与一个列表 A 中的一个列表 H 相关联，依此类推，Harry拼写类似，Hagrid和Harry共享两个常见的字母 H 和 A

Summing Up

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

数据结构堆栈和队列调整数组大小链表字典尝试

下次见！

原文出处：