CS-第 5 周

数据结构详解：从数组到树，再到哈希表

本文深入探讨几种常见的数据结构，包括数组、链表、二叉搜索树（BST）和哈希表，并阐述其在内存中的组织方式及优缺点。

信息结构与抽象数据结构

信息结构指的是内存中组织信息的方式，而抽象数据结构则是我们概念上对这些结构的理解。 理解抽象数据结构有助于我们更好地在实践中实现各种数据结构。

---

堆栈和队列

队列是一种遵循FIFO（先进先出）原则的抽象数据结构，类似于排队等候。其主要操作包括入队（添加元素到队列尾部）和出队（移除队列头部元素）。

堆栈则遵循LIFO（后进先出）原则，如同叠盘子。其操作包括压入（添加元素到堆栈顶部）和弹出（移除堆栈顶部元素）。

---

数组

数组是一种在内存中连续存储数据的结构。 如下图所示，数组在内存中占据连续的存储空间。

内存中可能存在其他程序、函数和变量，以及之前使用过的冗余数据。 如果需要向数组添加新元素，则需要重新分配内存并复制整个数组，这会造成效率低下。

预先分配过多的内存虽然可以减少复制操作，但却会浪费系统资源。因此，根据实际需求分配内存至关重要。

---

链表

链表是一种强大的数据结构，它允许将位于不同内存区域的值连接成一个列表，并支持动态扩展或缩小。

每个节点包含两个值：数据值和指向下一个节点的指针。最后一个节点的指针值为NULL，表示链表的结尾。

C语言中，节点可以定义如下：

typedef struct CS-第 5 周 {
    int number;
    struct CS-第 5 周 *next;
} CS-第 5 周;

以下示例展示了链表的创建过程：

链表的缺点包括：需要额外内存存储指针，以及无法通过索引直接访问元素。

---

二叉搜索树 (BST)

二叉搜索树是一种高效存储、搜索和检索数据的树形结构。

BST 的优点在于动态性和搜索效率（O(log n)），缺点在于树不平衡时搜索效率会下降到 O(n)，并且需要额外的内存存储指针。

---

哈希表

哈希表类似于字典，包含键值对。 它利用哈希函数将键映射到数组索引，从而实现 O(1) 的平均查找时间。

哈希冲突（多个键映射到同一个索引）可以通过链表或其他方法解决。 哈希函数的设计对哈希表的性能至关重要。 一个简单的哈希函数示例如下：

#include <ctype.h>

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

本文基于cs50x 2024源码整理。

以上是CS-第 5 周的详细内容。更多信息请关注PHP中文网其他相关文章！