CS-第 5 周

数据结构

信息结构是记忆中组织信息的形式。在内存中组织数据的方法有很多种。

抽象数据结构是我们概念上想象的结构。熟悉这些抽象结构，以后在实践中实现数据结构就更容易了。

---

堆栈和队列

队列是一种抽象数据结构。
队列数据结构按照 FIFO （先进先出，“第一个添加的元素先出现”） 规则运行。
可以想象为人们在景点排队的例子：第一个排队的人先进去，最后一个人最后进去。

可以使用

队列执行以下操作：

• 入队：将新元素添加到队列末尾。
• 出队：从队列开头移除一个元素。

数据结构

Stack 按照 LIFO （后进先出，“最后添加的元素先出现”） 规则运行。 > 例如，厨房里叠盘子：先拿最后一个盘子。

堆栈有以下操作：

• 压入：将新元素放入堆栈。
• 弹出：从堆栈中移除一个元素。

---

大批

Array 是一种在内存中顺序存储数据的方法。数组可以可视化为：

内存可能包含其他程序、函数和变量存储的其他值，以及以前使用过且不再使用的冗余值：

如果我们想向数组添加一个新元素 - 4 -，我们需要分配新的内存并将旧数组移入其中。这个新内存可能充满了垃圾值

:

如果我们将元素移动到数组并添加新值，新值将覆盖新分配的内存中旧的不必要的值：

这种方法的缺点是每次添加新元素时都需要复制整个数组。
如果我们把 4 放在内存的其他地方会怎么样？那么，根据定义，这不再是一个数组，因为 4 与内存中的数组元素不连续。

有时，程序员会分配比所需更多的内存（例如，300 个元素对应30 个元素）。但这是一个糟糕的设计，因为它浪费了系统资源，而且在大多数情况下额外的内存是不必要的。因此，根据具体需要分配内存非常重要。

---

链表

链表是C编程语言中最强大的数据结构之一。它们允许将位于不同内存区域的值组合到一个列表中。它还允许我们根据需要动态扩展或缩小列表。

每个节点存储两个值：

• 值；
• 是一个指针，保存下一个节点的内存地址。 最后一个节点包含NULL，表示其后没有其他元素。

我们将链表第一个元素的地址保存到一个指针（指针）.

在C语言中，我们可以将节点写成：

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

我们看一下

链表的创建过程：

• 我们声明节点 *list:

• 为节点分配内存：

• 输入节点的值：n->number = 1:

• 我们将节点的下一个索引设置为 NULL： n->next = NULL:

• 让我们将列表等于：

• 按照相同的顺序，我们创建一个值为 2 的新节点：

• 为了连接两个节点，我们将 n 的下一个索引设置为列表：

• 最后，我们将列表设置为 n。现在我们有一个由两个元素组成的链表：

在C语言中，我们可以将这个过程的代码写成如下：

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

使用链表时有几个缺点：

• 更多内存：对于每个元素，不仅需要存储元素本身的值，还需要存储指向下一个元素的指针。
• 通过索引调用元素：在数组中我们可以通过索引调用某个元素，但在链表中这是不可能的。要找到特定元素的位置，需要从第一个元素开始按顺序遍历所有元素。

---

树

二叉搜索树 (BST)是一种可以高效存储、搜索和检索数据的信息结构。
让我们得到一个已排序的数字序列：

我们将中心的元素放在顶部，比中心元素小的值放在左边，较大的值放在右边：

我们使用指针将每个元素相互连接：

以下代码展示了如何实现BST:

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

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

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

我们为每个节点分配内存，其值以数字形式存储，因此每个节点都有左和右指示器。 print_tree 函数从左到右按顺序递归打印每个节点。 free_tree 函数递归地从内存中释放数据结构的所有节点。

BST的优点：

• 动态性：我们可以有效地添加或删除元素。
• 搜索效率：在BST中搜索给定元素所需的时间为O(log n)，因为每次搜索时都会排除一半的树。

BST 的缺点：

• 如果树的平衡被打破（比如所有元素都放在一行），搜索效率就会下降到O(n)。
• 需要为每个节点存储左指针和右指针，这会增加计算机的内存消耗。

---

字典

字典就像一本字典，它包含一个单词及其定义，它的元素key (key)和value有 （值）。

如果我们查询

Dictionary 中的某个元素，它会在 O(1) 时间内返回该元素。字典可以通过散列来提供精确的速度。

哈希是使用特殊算法将输入数组中的数据转换为位序列的过程。

哈希函数是一种从任意长度的字符串生成固定长度位的字符串的算法。

哈希表是数组和链表的完美组合。我们可以这样想象：

碰撞 （碰撞） 是指两个不同的输入产生一个哈希值。在上图中，发生碰撞的元素以链表的形式连接起来。通过改进哈希函数，可以降低碰撞概率。

哈希函数的一个简单示例是：

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

本文使用 CS50x 2024 源码。

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