Различные типы распределения памяти структуры, используемые для связанного списка в c - PullRequest
Новая
       84

Различные типы распределения памяти структуры, используемые для связанного списка в c

1 голос
/ 08 мая 2020

Я пишу программу для односвязного списка в 'c' двумя способами (они различаются способом выделения памяти для структуры).

1. 

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

typedef struct SingleLinkedList sll;

sll* createNode()
{
    sll* node = (sll*) malloc(sizeof(sll));
    node -> next = NULL;
    return node;
}

2. 

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

typedef struct SingleLinkedList sll;

sll createNode()
{
    sll node;
    node.next = NULL;
    return node;
}

Я хочу знать, как написана вторая программа, верна она или нет?
Если неверно, то почему?
Если правильно, почему я не могу найти такую ​​прогу в инте rnet?

Ответы [ 2 ]

2 голосов
/ 08 мая 2020

Ваша первая программа возвращает указатель на (выделенную) структуру. Вызывающий createNode теперь несет ответственность free() за использование своей памяти до того, как указатель выйдет из области видимости, и за преимущество узла, существующего до тех пор, пока он не станет free() d.

Ваша вторая программа возвращает структуру по значению без «выделенной» памяти. Фактически, структура node, созданная внутри функции createNode, перестает существовать, когда функция возвращает; вызывающая функция получает копию этой (локальной) структуры. (Хотя большинство компиляторов не оптимизируют это до нуля.)

Второй тип встречается нечасто, потому что:

1) это действительно избыточный вызов функции; вместо ... 

ssl node = createNode();

... просто вызовите ... 

ssl node = { 0, NULL };

2) Этот узел, опять же, будет существовать только до конца текущей области. Если вы создаете связанный список, подобный этому, в функции initList(), которая, например, возвращает указатель на первый узел в этом списке, как только initList() возвращает все эти узлы, go выйдет за пределы области видимости, и ваш указатель будет указывать ни при чем. Во всяком случае, не выделенные структуры узлов. ;-) И если вы инициализируете эти узлы в al oop, каждый отдельный узел будет go вне области видимости в конце своей l oop итерации ... все это, скорее всего, не то, что вам нужно. ; -)

0 голосов
/ 08 мая 2020

Для начала обе функции должны быть объявлены с параметром, значение которого используется для инициализации члена данных data созданного узла.

Например, функции могут быть определены следующим образом 

sll * createNode( int data )
{
    sll *node = malloc( sizeof( sll ) );

    if ( node != NULL )
    {
        node->next = NULL;
        node->data = data;
    }

    return node;
}

и 

sll createNode( int data )
{
    sll node = { data, NULL };
    return node;
}

Оба фрагмента кода верны. Будет ли ваша программа неправильной, зависит от того, правильно ли вы будете использовать функции.

Например, вторая функция может использоваться в следующем контексте (добавление нового узла в конец списка): 

int append( sll **head, int data )
{
    while ( *head != NULL )
    {
        head = &( *head )->next;
    }

    *head = malloc( sizeof( sll ) );

    if ( *head ) **head = createNode( data );

    return *head != NULL;
}

Единственный недостаток второго фрагмента кода состоит в том, что в большинстве случаев лучше объединить в одной функции выделение узла и его инициализацию в одной функции вместо разделения этих двух операций, как это делается во втором коде. snippet.

Однако иногда имеет смысл поместить саму инициализацию в отдельную функцию, потому что инициализация может быть достаточно сложной. Это сделает код в целом более читабельным.

Кстати в C ++ это делается именно так за счет использования конструкторов. То есть за инициализацию отвечает конструктор (отдельная функция).

Таким образом, вы можете рассматривать эту функцию 

sll createNode( int data )
{
    sll node = { data, NULL };
    return node;
}

как конструктор объекта типа sll.

Итак, цели функций из представленных двух фрагменты кода разные. Первый динамически выделяет узел. А второй используется для инициализации уже существующего узла.

...