Подтвердить что ты не робот

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

#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 бы сбросил ошибку сегментации. (?) Пожалуйста, игнорируйте плохой стиль программирования.

4b9b3361

ОТВЕТЫ

Ответ 1

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

temp.next=&newtemp;

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

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

Ответ 2

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

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

Ответ 3

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

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

5 -> NULL

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

5 -> 4 -> NULL

После второй итерации цикла у вас есть

5 -> 3 -> NULL

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

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

Ответ 4

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

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

Оба подхода примерно одинаковы.

Ответ 5

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

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

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

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

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

     node newtemp,root,temp;

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

     newtemp=getnode(i);

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

Итак, вы делаете, просто рев:

     temp.next=&newtemp;

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

     if(root.next==NULL)

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

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

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

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

#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

Ответ 6

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

node myNodes[n];

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