Выделение памяти для нового элемента в связанном списке в C

Question

Я пытаюсь создать связанный список, у меня это работает, но я все еще немного сбит с толку.Я использую следующую структуру:

typedef struct _MList
{
    int dx;
    int dy;
    struct _MList *next;
} MList_t, *MList_p;

Я проверил, что эта структура имеет смысл, и у меня есть функция для печати списка:

void mListPrint(MList_t *mList)
{
    MList_p node = mList;
    while (node->next != NULL)
    {
        printf("[%i,%i] ",node->dx,node->dy);
        node = node->next;
    }
    printf("[%i,%i]\n",node->dx,node->dy);
}

Ифункция для создания первого узла:

MList_t mListNew(int dx, int dy)
{
    MList_t newNode;
    newNode.dx = dx;
    newNode.dy = dy;
    newNode.next = NULL;    
    return newNode;
}

С этим нормально работающим я подумал, что попробую создать функцию, которая добавляет узел в конец списка.Моя первая попытка была такой:

void mListAdd(int dx, int dy, MList_t *mList)
{
    MList_p node = mList;

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

    MList_t newNode = mListNew(dx,dy);
    node->next = &newNode;
}

Это выглядело хорошо, пока я не добавил более одного элемента.После длительной отладки выяснилось, что адрес памяти «newNode», созданного в mListAdd, всегда был одинаковым.И так список закончился ссылкой обратно на себя.Почему это так?

Вместо этого я реализовал mListAdd, используя указатель на новый узел, следующим образом:

void mListAdd(int dx, int dy, MList_t *mList)
{
    MList_p node = mList;

    while (node->next != NULL)
    {
        node = node->next;
    }
    MList_p newNode = malloc(sizeof(MList_t));
    *newNode = mListNew(dx,dy);
    mListPrint(newNode);
    node->next = newNode;
}

Это работает отлично, но я считаю, что другой способ должен работать.Или я что-то упускаю очевидное?Я пытаюсь выучить C на собеседовании, используя различные структуры данных, которые я выучил на Java и ML.

Я сожалею о количестве кода, но я подумал, что было бы лучше объяснить мой вопрос как можно более подробно.Спасибо за помощь заранее!

Answer 1

В mListNew вы используете локальную переменную:

MList_t newNode;

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

Вы должны выделить новый узел списка с помощью malloc внутри mListNew и вернуть указатель на новый узел, например:

MList_p mListNew(int dx, int dy)
{
    MList_p newNode = malloc(sizeof(MList_t));
    newNode->dx = dx;
    newNode->dy = dy;
    newNode->next = NULL;    
    return newNode;
}

Answer 2

В первом примере выделяется память в стеке, поэтому ее можно использовать только внутри функции, поэтому вы НЕ ДОЛЖНЫ использовать ее адрес памяти в связанном списке, который может сохраняться вне функции.

Answer 3

Извините, я уверен, что это еще не все, но я не читал дальше "И функцию для создания первого узла"

MList_t mListNew(int dx, int dy)
{
    MList_t newNode;
    newNode.dx = dx;
    newNode.dy = dy;
    newNode.next = NULL;    
    return newNode;
}

newNode создается в стеке. Это определение является локальным по отношению к функции mListNew (), и когда оно возвращается, оно «неопределено».

В соответствии с передовой практикой вам необходимо, чтобы вызывающий абонент выделил (и освободил) память перед вызовом. Например,

void mListNew(int dx, int dy, MList_t *newNode)
{
    newNode->dx = dx;
    newNode->dy = dy;
    newNode->next = NULL;    
}

Остальное я еще не посмотрел ...

Answer 4

Вы должны явно распределить память, используя malloc () или calloc (). Что вы делаете, так это используете структуру, которая живет только в стеке и больше не работает после возврата mListAdd; бывает так, что он еще не перезаписан.