链表实现在没有 malloc 的情况下失败

Question

第一个例子是没有动态分配内存的链表例子。但是在这个例子中当我们运行它时，它只会显示10，然后会提供运行时间错误。请帮我找出问题所在。

#include<bits/stdc++.h>

using namespace std;

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

struct Node* head;

void Insert(int x)
{
    struct Node* temp;
    temp=head;

    struct Node* newnode;
    newnode->data=x;
    newnode->next=NULL;

    if(head==NULL)
    {
        head=newnode;
        return;
    }

    while(temp->next!=NULL)
    {
        temp=temp->next;
    }

    temp->next=newnode;

}

void print()
{
    struct Node* temp;
    temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}

int main()
{
    head=NULL;
    Insert(10);
    Insert(20);
    Insert(30);
    print();
}

在下面的示例中，我刚刚使用 malloc 为变量提供动态内存。它按预期完美运行。为什么两者会有这么大的差异？

#include<bits/stdc++.h>

using namespace std;

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

struct Node* head;

void Insert(int x)
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    temp=head;

    struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
    newnode->data=x;
    newnode->next=NULL;
    cout<<"Reached here"<<endl;

    if(head==NULL)
    {
        head=newnode;
        return;
    }

    while(temp->next!=NULL)
    {
        temp=temp->next;
    }

    temp->next=newnode;

}

void print()
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    temp=head;

    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}

int main()
{
    head=NULL;
    Insert(10);
    cout<<"Inserted 10"<<endl;
    Insert(20);
    cout<<"2nd"<<endl;
    Insert(30);
    cout<<"3rd"<<endl;
    print();
}

Answer 1

在您没有 malloc 的示例中，这只是非法代码：

struct Node* newnode;
newnode->data=x;
newnode->next=NULL;

newnode 不是指向任何合法内存，因此使用 newnode 写入内存是未定义的行为。

如果你想要一个链表没有使用 malloc 你必须预先为节点预留内存。例如，您可以在程序启动时创建一个包含 1000 个节点的池，然后在程序执行期间使用这些节点。

喜欢：

 static struct node nodePool[1000];

 struct node* getNode()
 {
     // Add code to find an unused node and return a pointer to the node
     // This will require some extra data object to track which nodes are free
 }

 void freeNode(struct node* p)
 {
     // Add code to mark the node as unused
     // This will require some extra data object to track which nodes are free
 }

void Insert(int x)
{
    ...

    struct Node* newnode = getNode();
    if (newnode == NULL)
    {
        // No more nodes
        add error handling
        return something or exit(1);
    }
    newnode->data=x;
    newnode->next=NULL;

    ...
}

注意：对节点池使用平面数组是可行的，但对性能不利。 Get/fre 节点将是 O(n) 这对程序性能不利。使用池的程序有更高级的池实现，允许 O(1) 操作。一种（非常简单的）方法是将池控制数据实现为具有头指针和尾指针的链表。这将允许 getNode 和 freeNode.

的 O(1) 复杂度

注意：我刚刚注意到这个问题同时标记了C++和C。这个答案是用C写的。对于 C++ 代码，没有（也很少）理由来实现您自己的链表——只需使用 std::list

Answer 2

你的两个例子都是错误的，但原因不同。指针变量需要赋值，就像普通变量一样。所以你的第一个例子是错误的，因为指针变量 newnode 是 uninitialised。查看我添加到您的代码中的评论

struct Node* temp; // temp has no value
temp=head;         // now temp is given a value

struct Node* newnode; // newnode has no value
newnode->data=x;      // ERROR, newnode is used before it's been given a value
newnode->next=NULL;

在给它赋值之前，您不会使用常规变量。跟指针变量没什么区别。

你的第二个例子有相反的错误，你给了temp指针一个值两次！再次看到添加的评论

struct Node* temp=(struct Node*)malloc(sizeof(struct Node)); // temp is given a value
temp=head;                         // now temp is given a different value,
                                   // the first value is discarded

struct Node* newnode=(struct Node*)malloc(sizeof(struct Node)); // newnode is given a value
newnode->data=x;                                       // newnode is being used correctly
newnode->next=NULL;

你可以通过两种方式给一个指针一个不同的值，你可以创建一个新的节点让它指向，这就是 temp=(struct Node*)malloc(sizeof(struct Node)); 所做的，或者你可以让它指向一个已经存在的节点，这就是 temp=head; 所做的。两者都做没有多大意义。在您的第二个示例中，您使用 temp=(struct Node*)malloc(sizeof(struct Node)); 创建的节点永远不会被使用，当您将 temp 指向头节点时，它会被创建然后被丢弃。这称为 内存泄漏 。如果泄漏变得足够大，您的程序将运行内存不足。充其量是浪费。

再想想你将如何使用常规变量，你永远不会写这样的代码int x = 10; x = 20;给一个变量一个值是没有意义的，然后在下一行抛出它value away 并给变量一个不同的值。但这正是您对 temp 变量所做的。同样，指针并不特殊，适用于常规变量的相同规则也适用于指针变量。

链表实现在没有 malloc 的情况下失败

linked list implementation fail without malloc

c

c++

singly-linked-list