Блог

Главная - Вопросы по программированию - Использование malloc для бинарных деревьев поиска

Использование malloc для бинарных деревьев поиска

#c #pointers #binary-search-tree

#c #указатели #binary-search-tree

Вопрос:

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

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

Вопрос: Почему malloc используется для tree_t?

 tree_t *make_empty_tree(int func(void*,void*))
{
    tree_t *tree;
    tree = malloc(sizeof(*tree));
    assert(tree!=NULL);
    /* initialize tree to empty */
    tree->root = NULL;
    /* and save the supplied function pointer */
    tree->cmp = func;        
    return tree;
}

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

В конце концов, не является ли указатель: tree достаточной (временной) памятью просто при объявлении? Например, почему вы не можете просто объявлять tree , пропускать malloc и назначать компоненты tree_t структуры?

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

Комментарии:

1. Ну, во-первых, «Возвращает указатель на узел дерева, хранящий объект «ключ», если он существует» , является ложью. Это не то, что делает эта функция. Он возвращает void* в узле дерева, который соответствует указанному ключу. если совпадения нет, возвращается значение NULL. Фактические узлы дерева только вводят изображение в recursive_search_tree функцию, и даже тогда только для поиска правильных данных, соответствующих данному ключу (если он существует). Если бы эта функция выполнялась так, как указано в комментарии, return root->data было return root; бы, и объявленный возвращаемый тип функции, вероятно , был note_t* бы, нет void* .

2. Когда вы это делаете: tree_t *tree; вы объявляете переменную, то tree_t есть переменную-указатель. Он может содержать только значение указателя (он же адрес памяти). Он не может содержать a tree_t — он может указывать только на какую-то другую память (где tree_t хранится a). malloc Вызов резервирует эту «другую память». Итак: нет — вы не можете просто «пропустить malloc»

3. tree является неинициализированным указателем на a tree_t . malloc выделяет необходимую память для tree_t структуры, используя sizeof оператор, в куче . tree_t Структура не является локальной переменной в стеке . Его поля устанавливаются с помощью оператора указателя -> , и указатель возвращается.

4. Кстати, лучше ограничиться одним вопросом. Первый вариант подходит, и то, что вы написали, позволяет другим узнать, в чем может заключаться ваше недопонимание. Следующие вопросы сформулированы некорректно . «Объясните этот код» не помогает. Когда указатели начнут иметь для вас смысл, вы, вероятно, начнете понимать остальное.