为什么在 c 中实现链表时使用动态内存分配（即 malloc()）？

Question

好吧，对于业余程序员来说，这个问题可能听起来很愚蠢。但严重的是，这让我感到困扰，欢迎对我的这个疑问做出严肃的回答。我刚刚开始学习我的第一门数据结构课程。而困扰我的是：

假设使用 C，

//Implementing a node

struct Node
{
     int data;
     struct *Node;
};

现在，在创建节点时，为什么我们在使用 malloc() 的地方使用动态内存分配技术。我们不能只创建一个“结构节点”类型的变量。即类似：

struct Node N1;
 //First node - actually second where !st Node is assumed to be Head.

struct Node *Head = &N1;
struct Node N2;
N2.(*Node) = &N1;

好吧，我的代码的某些部分可能不正确，因为我只是一个初学者并且不精通 C。但是知道您可能已经理解我的基本意思。为什么我们不创建 Node 类型的 Node 类型的变量来分配内存 t 新节点为什么要进入动态内存分配的复杂性？

Answer 1

首先，您在声明结构的方式上存在错误。 struct *本身并不表示类型。您必须提供完整的类型名称：

struct Node
{
     int data;
     struct Node *Node;
};

您当然可以使用上述局部变量来创建链表，但是这将您限制为固定数量的列表元素，即您明确声明的元素。这也意味着您不能在函数中创建列表，因为这些变量会超出范围。

例如，如果你这样做：

struct Node *getList()
{
    struct Node head, node1, node2, node3;
    head.Node = &node1;
    node1.Node = &node2;
    node2.Node = &node3;
    node3.Node = NULL;
    return &head;
}

您的列表将被限制为 4 个元素。你们中的什么人需要成千上万个？此外，通过返回局部变量的地址，它们会在函数返回时超出范围，因此访问它们会导致未定义行为。

通过动态分配每个节点，您只会受到可用内存的限制。

这是使用动态内存分配的示例：

struct Node *getList()
{
    struct Node *head, *current;
    head = NULL;
    current = NULL;

    // open file
    while (/* file has data */) {
        int data = /* read data from file */
        if (head == NULL) {      // list is empty, so create head node
            head = malloc(sizeof(struct Node *));
            current = head;
        } else {                 // create new element at end of list
            current->next = malloc(sizeof(struct Node *));
            current = current->next;
        }
        current->data = data;
        current->Node = NULL;
    }
    // close file
    return head;
}

这是不涉及读取相关数据的细节的伪代码，但您可以看到如何创建一个在程序生命周期内存在的任意大小的列表。