C语言 没有malloc的C中的链表

Linked Lists in C without malloc

提问by letsc

#include <stdio.h>

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

node getnode(int a)
{
      struct node n;
      n.i=a;
      n.next=NULL;
      return n;
}

main()
{
     int i;
     node newtemp,root,temp;

     scanf("%d",&i);
     root=getnode(i);
     temp=root;

     while(i--)
     {
         newtemp=getnode(i);

         temp.next=&newtemp;
         if(root.next==NULL)
         {
            root=temp;
         }
        temp=*(temp.next);
     }


     temp=root;

     while( temp.next != NULL )
     {
         printf(" %d ",temp.i);
         temp=*(temp.next);
     }
}

I am trying to create a linked-list without using malloc. The programming is printing only the root and no nodes following it. I couldn`t find the bug. Had there been any memory issue, the gcc compiler would have thrown a segmentation fault.(?) Please ignore the poor programming style..

我试图在不使用 malloc 的情况下创建一个链表。编程只打印根，没有节点跟随它。我找不到错误。如果有任何内存问题，gcc 编译器会抛出一个分段错误。（？）请忽略糟糕的编程风格。

采纳答案by John Marshall

When you initialise temp.next, what is the value of the pointer that you assign to it?

初始化时temp.next，分配给它的指针的值是多少？

temp.next=&newtemp;

Why, it's the same one every time! (Draw a picture if you are unconvinced.)

为什么，每次都是一样的！（不信就画个图。）

Give it up. If you need an indeterminate amount of memory (which, with an indeterminate number of nodes, you do), then you need to allocate memory.

放弃。如果您需要不确定数量的内存（对于不确定数量的节点，您需要），那么您需要分配内存。

回答by Peter G.

You can avoid malloc but not for free:

您可以避免 malloc 但不是免费的：

• On Linux/UNIX you could call brk() and write your own memory allocator.
• On every system you can write your own allocator using a fixed size array as a memory source.
• I do do not see what the alternatives would buy over just malloc/free directly. They're there for a reason.
• Returning local variables to be used outside would be simple but is an error and does not work.

• 在 Linux/UNIX 上，您可以调用 brk() 并编写自己的内存分配器。
• 在每个系统上，您都可以使用固定大小的数组作为内存源编写自己的分配器。
• 我看不出有什么替代品会直接购买 malloc/free。他们在那里是有原因的。
• 返回要在外部使用的局部变量很简单，但会出错并且不起作用。

回答by Seva Alekseyev

You can statically declare an array of node structures and pick new nodes from that array. But then you would've implemented a lame, woefully specialized custom allocator. And the maximum number of nodes available will be the size of that array.

您可以静态声明一个节点结构数组并从该数组中选取新节点。但是你会实现一个蹩脚的、可悲的专用自定义分配器。可用的最大节点数将是该数组的大小。

Alternatively, you can use recursion as an allocation mechanism, and do things to the list on the bottom of the recursion stack.

或者，您可以使用递归作为分配机制，并对递归堆栈底部的列表执行操作。

Both approaches are about equally cludgey.

这两种方法都同样笨拙。

回答by fljx

Of course you can build a linked list or any other data structure without dynamic memory allocation. You can't, no matter how hard you try, though, build it allocating no memory at all.

当然，您可以在没有动态内存分配的情况下构建链表或任何其他数据结构。但是，无论您如何努力，都不能在完全不分配内存的情况下构建它。

Alternative:

选择：

Create a global or static memory pool where you can put your objects, imitating the heap/malloc/free. FreeRTOS does something like. In this situation, you will have a big memory chunk allocated statically since the begining of your program andwill be responsible for managing it, returning the correct pointers when a new node is needed and marking that memory as used.

创建一个全局或静态内存池，您可以在其中放置对象，模拟堆/malloc/free。FreeRTOS 做了类似的事情。在这种情况下，自程序开始以来，您将有一个静态分配的大内存块，并将负责管理它，在需要新节点时返回正确的指针并将该内存标记为已使用。

P.S.: I won't question why you want to avoid malloc. I supose you have a good reason for it.

PS：我不会质疑你为什么要避免 malloc。我想你有一个很好的理由。

In you program, when you do, in line 20:

在你的程序中，当你这样做时，在第 20 行：

     node newtemp,root,temp; 

You are allocatin thre nodes, one of them, "newtemp". Then you do in line 28:

您正在分配三个节点，其中之一是“newtemp”。然后你在第 28 行做：

     newtemp=getnode(i); 

It just copiesthe contents of the returned node over your old "newnode" (controversal, isn't?)

它只是将返回节点的内容复制到旧的“新节点”上（有争议，不是吗？）

So you do, just bellow:

所以你这样做，只是吼叫：

     temp.next=&newtemp; 

That sets a pointer that initially comes from "root.next" to your "newnode".

这将最初来自“root.next”的指针设置为您的“newnode”。

     if(root.next==NULL) 

Will be "NULL" at first pass, but then, only replace the same contents.

第一次通过时将是“NULL”，但随后只替换相同的内容。

    temp=*(temp.next); 
     { 
        root=temp; 
     } 

Is, again, copyingdata from a single allocated object, "*(temp.next)", to another, "temp". It does not create any new node.

再次将数据从单个分配的对象“*(temp.next)”复制到另一个“temp”。它不会创建任何新节点。

It will work if you do like this:

如果您这样做，它将起作用：

#include <stdio.h>

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

#define MAX_NODES   10

node    *create_node( int a )
{ 
    // Memory space to put your nodes. Note that is is just a MAX_NODES * sizeof( node ) memory array.
    static node node_pool[ MAX_NODES ];
    static int  next_node = 0;

    printf( "[node  *create_node( int a )]\r\tnext_node = %d; i = %d\n", next_node, a );
    if ( next_node >= MAX_NODES )
    {
        printf( "Out of memory!\n" );
        return ( node * )NULL;
    }

    node    *n = &( node_pool[ next_node++ ] );

    n->i = a;
    n->next = NULL;

    return n; 
} 

int main( )
{ 
    int i; 
    node    *newtemp, *root, *temp; 

    root = create_node( 0 ); 
    temp = root; 

    for ( i = 1; ( newtemp = create_node( i ) ) && i < MAX_NODES; ++i )
    { 
        temp->next = newtemp; 

        if ( newtemp )
        {
            printf( "temp->i = %d\n", temp->i );
            printf( "temp->next->i = %d\n", temp->next->i );
            temp = temp->next;
        }
    }


    for ( temp = root; temp != NULL; temp = temp->next )
        printf( " %d ", temp->i );

    return  0;
}

The output:

输出：

    $ gcc -Wall -o list_no_malloc list_no_malloc.c 

$ ./list_no_malloc
[node   next_node = 0; i = 0)]
[node   next_node = 1; i = 1)]
temp->i = 0
temp->next->i = 1
[node   next_node = 2; i = 2)]
temp->i = 1
temp->next->i = 2
[node   next_node = 3; i = 3)]
temp->i = 2
temp->next->i = 3
[node   next_node = 4; i = 4)]
temp->i = 3
temp->next->i = 4
[node   next_node = 5; i = 5)]
temp->i = 4
temp->next->i = 5
[node   next_node = 6; i = 6)]
temp->i = 5
temp->next->i = 6
[node   next_node = 7; i = 7)]
temp->i = 6
temp->next->i = 7
[node   next_node = 8; i = 8)]
temp->i = 7
temp->next->i = 8
[node   next_node = 9; i = 9)]
temp->i = 8
temp->next->i = 9
[node   next_node = 10; i = 10
Out of memory!
 0  1  2  3  4  5  6  7  8  9 

回答by Ken Bloom

You only have two memory spaces that you can use to store nodes, and those are rootand newtemp. When you assign a new node to newtempthe old node doesn't exist anymore.

您只有两个可用于存储节点的内存空间，它们是root和newtemp。当您将新节点分配给旧节点时newtemp，旧节点不再存在。

Assuming you entered the number 5at the scanf, before first iteration of the loop, you have:

假设您5在 scanf 处输入了数字，在循环的第一次迭代之前，您有：

5 -> NULL

After the first iteration of the loop, you have

在循环的第一次迭代之后，你有

5 -> 4 -> NULL

After the second iteration of the loop, you have

在循环的第二次迭代之后，你有

5 -> 3 -> NULL

(The node containing 4has been completely replaced by the node containing 3).

（包含的节点4已完全替换为包含 的节点3）。

The only solution is to use malloc, and make getnodereturn a node*.

唯一的解决方案是使用malloc, 并getnode返回 a node*。

回答by Alexander Rafferty

A linked list is something of indeterminate length, and anything of indeterminate length cannot be created without malloc.

链表是不确定长度的东西，没有 malloc 就不能创建任何不确定长度的东西。

I suggest you simply use malloc to allocate the next link in the chain.

我建议你简单地使用 malloc 来分配链中的下一个链接。

回答by rajatkhanduja

When malloc is used, the 'pointer' to that location is passed on to the variable (which is a pointer).

当使用 malloc 时，指向该位置的“指针”被传递给变量（它是一个指针）。

node* new = (node*)malloc(sizeof(node));

Every time this code is used a "new" location is pointed to. On the contrary, you are using normal variables, which have 'statically' allocated memory. That implies, whenever you refer to 'temp' or 'newtemp', you are referring to the same location EACH TIME.

每次使用此代码时，都会指向一个“新”位置。相反，您使用的是普通变量，它们具有“静态”分配的内存。这意味着，每当您提到“temp”或“newtemp”时，您每次都指的是同一位置。

Now you tell me how can you store a 10 element long list using just 3 (root, temp, newtemp) memory locations. You might want to draw out memory locations to imagine what is happening. But remember, each time you call 'temp' its the SAME memory location. For that we must use malloc (or calloc), for dynamically allocating memory.

现在您告诉我如何仅使用 3 个（root、temp、newtemp）内存位置来存储 10 个元素的长列表。您可能想要绘制内存位置来想象正在发生的事情。但请记住，每次调用 'temp' 时都是相同的内存位置。为此，我们必须使用 malloc（或 calloc）来动态分配内存。

In that case, we can make do with few pointers (far lesser than the memory used by the list).

在这种情况下，我们可以使用很少的指针（远小于列表使用的内存）。

回答by Jens Gustedt

Since nobody yet answered this question about the mallocpart in the spirit of modern C (aka C99). If your compiler is conforming to that you have variable length arrays:

由于还没有人malloc以现代 C（又名 C99）的精神回答这个问题。如果您的编译器符合您的可变长度数组：

node myNodes[n];

where nhas some value that is only determined at run time. You probably shouldn't overdo it with this approach since this is limited to the size of the stack, and otherwise you might encounter a stackoverflow.

wheren有一些仅在运行时确定的值。您可能不应该使用这种方法过度使用它，因为这受限于堆栈的大小，否则您可能会遇到 stackoverflow。