在C中实现链接列表时，为什么要使用动态内存分配(即malloc())? [英] Why use dynamic memory allocation(i.e. malloc()) when implementing linked list in c?

问题描述

好吧，这个问题对业余程序员来说可能是愚蠢的.但是严重的是，这困扰着我，欢迎对此问题的庄严回答.我刚刚开始学习数据结构方面的第一门课程.而令我困扰的是:

Okay this question may sound stupid to the amateur programmers . But seriously this is bothering me and a solemn answer to this doubt of mine is welcomed. I have just started to take my first ever course in data structures. And what is bothering me is this:

假设使用C，

//Implementing a node

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

现在在创建节点时，为什么要在使用malloc()时使用动态内存分配技术.我们不能只创建"Struct Node"类型的变量.即:

Now while creating a node why do we use the dynamic memory allocation technique where we use malloc(). Can't we just create a variable of type ' Struct Node '. i.e. something like:

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类型的Array的Node类型的变量来分配内存给新节点，为什么会陷入动态内存分配的复杂性呢?

Well some parts of my code may be incorrect because I am only a beginner and not well versed with C. But by know you may have understood what I basically mean. Why don't we create variables of type Node of an Array of type Node to allocate memory t new nodes why get into the complexity of dynamic memory allocation?

推荐答案

首先，您在声明结构时遇到错误. struct * 本身并不表示类型.您必须提供完整的类型名称:

First off, you have an error in how you declare your struct. struct * by itself does not denote a type. You have to give the full type name:

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

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

You can certainly use local variables as above to make a linked list, however that limits you to a fixed number of list elements, i.e. the ones you explicitly declare. That would also mean you can't create a list in a function because those variables would go out of scope.

例如，如果您这样做:

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

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

Your list would be restricted to 4 elements. What of you needed thousands of them? Also, by returning the address of local variables, they go out of scope when the function returns and thus accessing them results in undefined behavior.

通过动态分配每个节点，您仅受可用内存的限制.

By dynamically allocating each node, you're only limited by your available memory.

下面是使用动态内存分配的示例:

Here's an example using dynamic memory allocation:

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

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

This is psedo-code that doesn't go into the details of reading the relevant data, but you can see how you can create a list of arbitrary size that exists for the lifetime of the program.

这篇关于在C中实现链接列表时，为什么要使用动态内存分配(即malloc())?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！