Почему динамическое распределение (связанные списки / деревья), c

Question

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

NODE *BuildTree(NODE *p, const char *str)
{
    if (p == NULL)
    size_t length = strlen(str) + 1;
    p = (NODE *)malloc(sizeof(NODE));
    p->string = (char *)malloc(length);
    ....
}

typdef struct Node NODE;
struct NODE
{
    char *string;
    size_t count;
    NODE *left, *right;
};

Код должен создать дерево со строками, которые вводятся пользователем.Я предполагаю, что вы динамически распределяете NODE, потому что вы, очевидно, не знаете, сколько детей вам понадобится.Но тогда зачем вам нужен размер строки str, которую нужно ввести?Или это сделано из-за того, как структура определена, и вы хотите выделить точное значение amt, если в структуре указано size_t count [50] и только что была потрачена впустую память.Это идея?Спасибо!

Answer 1

Строка выделена, потому что они используют символ *, а количество символов зависит от того, что помещается в строку.

Если бы ваш профессор сделал char blah[50];, вы бы дали ему достаточно памяти для50 символов.Поэтому я предполагаю, что он хочет позволить кому-то вводить больше, чем статическое количество символов.

Обратите внимание на код вашего профессора:

size_t length = strlen(str) + 1;
p = (NODE *)malloc(sizeof(NODE));
p->string = (char *)malloc(length);

strlen дает длину строки и добавляет ееэто для завершающего символа.Теперь длина может быть установлена ​​равной размеру всей строки, то есть ваш профессор теперь может выделить достаточно символьных байтов для размера строки, в данном случае (length).

Answer 2

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

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

Answer 3

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

Answer 4

Ваше понимание верно.Если введенные пользователем строки имеют неизвестную длину, то в лучшем случае трудно указать размер заранее.Если бы максимальный размер был известен, он мог бы быть объявлен как char string[N];.Но, как вы говорите, это может привести к потере памяти, если есть большие различия в размере.С другой стороны, преимущество создания заранее определенного размера состоит в том, что это может привести к меньшему количеству выделений, что иногда полезно.