Связанные списки в C без malloc

Question

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

Я пытаюсь создать связанный список без использования malloc.Программирование печатает только корень и никаких узлов после него.Я не смог найти ошибку.Если бы возникла какая-либо проблема с памятью, компилятор gcc вызвал бы ошибку сегментации. (?) Пожалуйста, не обращайте внимания на плохой стиль программирования ..

Answer 1

Когда вы инициализируете temp.next, какое значение указателя вы ему назначаете?

temp.next=&newtemp;

Да ведь каждый раз одно и то же! (Нарисуйте картинку, если вы не уверены.)

Брось это. Если вам нужен неопределенный объем памяти (который вам необходим с неопределенным числом узлов), то вам нужно выделить память.

Answer 2

Вы можете избежать malloc, но не бесплатно:

• В Linux / UNIX вы можете вызвать brk () и написать свой собственный распределитель памяти.
• В каждой системе вы можете написать свой собственный распределитель, используя массив фиксированного размера в качестве источника памяти.
• Я не вижу, что бы альтернативы покупали напрямую через malloc / free. Они там по причине.
• Возвращение локальных переменных, которые будут использоваться снаружи, будет простым, но является ошибкой и не работает.

Answer 3

У вас есть только два пространства памяти, которые вы можете использовать для хранения узлов, это root и newtemp.Когда вы присваиваете новый узел newtemp, старый узел больше не существует.

Предполагая, что вы ввели число 5 в scanf, перед первой итерацией цикла вы получите:

5 -> NULL

После первой итерации цикла вы получите

5 -> 4 -> NULL

После второй итерации цикла вы получите

5 -> 3 -> NULL

(узел, содержащий 4 полностью заменен узлом, содержащим 3).

Единственное решение - использовать malloc и заставить getnode вернуть node*.

Answer 4

Вы можете статически объявить массив структур узлов и выбрать новые узлы из этого массива.Но тогда вы бы реализовали неудачный специализированный пользовательский распределитель.И максимальное количество доступных узлов будет равным размеру этого массива.

В качестве альтернативы вы можете использовать рекурсию в качестве механизма выделения и выполнять действия со списком в нижней части стека рекурсии.1004 * Оба подхода примерно одинаковы.

Answer 5

Конечно, вы можете создать связанный список или любую другую структуру данных без динамического выделения памяти.Вы не можете, как бы вы ни старались, создать его без выделения памяти.

Альтернатива:

Создать глобальный или статический пул памяти, куда вы можете поместить свои объекты,имитируя кучу / malloc / free.FreeRTOS делает что-то вроде.В этой ситуации у вас будет большой фрагмент памяти, выделенный статически, так как начало вашей программы и будет отвечать за управление им, возвращая правильные указатели, когда нужен новый узел, и помечая эту память как использованную.

PS: Я не буду спрашивать, почему вы хотите избежать malloc.Я полагаю, у вас есть веская причина для этого.

В вашей программе, когда вы это делаете, в строке 20:

     node newtemp,root,temp; 

Вы выделяете узлы, один из них, "newtemp",Затем вы делаете в строке 28:

     newtemp=getnode(i); 

Это просто копирует содержимое возвращенного узла поверх вашего старого "нового узла" (противоречие, не так ли)

Так и сделайте, просто ниже:

     temp.next=&newtemp; 

Устанавливает указатель, который изначально идет от "root.next" на ваш "newnode".

     if(root.next==NULL) 

Будет "NULL"при первом прохождении, но затем заменить только одно и то же содержимое.

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

Снова, копирование данных из одного выделенного объекта, "* (temp.next)",другой, "темп".Он не создает никакого нового узла.

Он будет работать, если вы сделаете так:

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

Вывод:

    $ 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 

Answer 6

Связанный список имеет неопределенную длину, и без malloc невозможно создать что-либо неопределенного размера.

Я предлагаю просто использовать malloc для выделения следующей ссылки в цепочке.

Answer 7

Когда используется malloc, указатель на это местоположение передается переменной (которая является указателем).

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

Каждый раз, когда используется этот код, указывается «новое» местоположение. Напротив, вы используете обычные переменные, которые «статически» выделяют память. Это означает, что всякий раз, когда вы ссылаетесь на «temp» или «newtemp», вы ссылаетесь на одно и то же местоположение КАЖДОЕ ВРЕМЯ.

Теперь вы скажете мне, как сохранить список из 10 элементов, используя только 3 (root, temp, newtemp) ячейки памяти. Возможно, вы захотите нарисовать места памяти, чтобы представить, что происходит. Но помните, что каждый раз, когда вы вызываете 'temp', это ОДНО ЖЕ место памяти. Для этого мы должны использовать malloc (или calloc) для динамического распределения памяти.

В этом случае мы можем обойтись несколькими указателями (намного меньше, чем память, используемая списком).

Answer 8

Так как никто еще не ответил на этот вопрос о части malloc в духе современного C (он же C99). Если ваш компилятор соответствует этому, у вас есть массивы переменной длины :

node myNodes[n];

, где n имеет некоторое значение, которое определяется только во время выполнения. Вы, вероятно, не должны переусердствовать с этим подходом, поскольку он ограничен размером стека, иначе вы можете столкнуться с переполнением стека.