Что делает следующая строка кода с malloc?

Question

У меня есть следующая реализация для зеркального отображения двоичного дерева.

#include<stdio.h> 
#include<stdlib.h> 

/* A binary tree node has data, pointer to left child 
    and a pointer to right child */ 
struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

/* Helper function that allocates a new node with the 
    given data and NULL left and right pointers. */ 
struct node* newNode(int data) 

{ 
    struct node* node = (struct node*) 
         malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 

    return(node); 
} 


/* Change a tree so that the roles of the left and 
    right pointers are swapped at every node. 

So the tree... 
     4 
    /\ 
    2 5 
    /\ 
    1 3 

is changed to... 
     4 
    /\ 
    5 2 
     /\ 
     3 1 
*/ 
void mirror(struct node* node) 
{ 
    if (node==NULL) 
    return; 
    else 
    { 
    struct node* temp; 

    /* do the subtrees */ 
    mirror(node->left); 
    mirror(node->right); 

    /* swap the pointers in this node */ 
    temp  = node->left; 
    node->left = node->right; 
    node->right = temp; 
    } 
} 


/* Helper function to test mirror(). Given a binary 
    search tree, print out its data elements in 
    increasing sorted order.*/ 
void inOrder(struct node* node) 
{ 
    if (node == NULL) 
    return; 

    inOrder(node->left); 
    printf("%d ", node->data); 

    inOrder(node->right); 
} 


/* Driver program to test mirror() */ 
int main() 
{ 
    struct node *root = newNode(1); 
    root->left  = newNode(2); 
    root->right  = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 

    /* Print inorder traversal of the input tree */ 
    printf("\n Inorder traversal of the constructed tree is \n"); 
    inOrder(root); 

    /* Convert tree to its mirror */ 
    mirror(root); 

    /* Print inorder traversal of the mirror tree */ 
    printf("\n Inorder traversal of the mirror tree is \n"); 
    inOrder(root); 

    getchar(); 
    return 0; 
} 

Я говорю о следующей строке:

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

У меня есть промежуточное знание C/C++, но я очень боюсь указателей. Даже после нескольких попыток я никогда не мог получить указатели. Я избегаю их, насколько это возможно, но когда приходят к внедрению структур данных, таких как деревья, других вариантов нет. Почему мы используем malloc и sizeof здесь? Также почему мы кастинг (struct node *)?

Answer 1

Прежде всего бросать при использовании malloc в C не нужно. (см. here)

Вы являетесь malloc-ing, потому что вы выделяете кучную память размера узла. Вы видите в C, вы должны иметь в виду, где хранятся все переменные. А именно stack и heap (см here)

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

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

В итоге:

• Переменные в функции являются локальными по отношению к функции, отсюда термин локальная переменная
• Для других функций для доступа к локальной переменной, вы должны распределите память в куче, чтобы передать эту переменную с другими функциями.

Чтобы дать вам пример, почему, рассмотрим следующий код:

#include <stdio.h> 
#include <string.h> 

char *some_string_func() 
{ 
    char some_str[13]; /* 12 chars (for "Hello World!") + 1 null '\0' char */ 

    strcpy(some_str, "Hello World!"); 

    return some_str; 
} 

int main() 
{ 
    printf("%s\n", some_string_func()); 
    return 0; 
} 

Его довольно просто, main просто вызов функции some_str_func которая возвращает локальную переменную some_str, компиляции приведенный выше код будет работать, но не без предупреждений:

test.c: In function ‘some_string_func’: 
test.c:11:9: warning: function returns address of local variable [enabled by default] 

Хотя он компилирует к сведению, что some_str в some_str_func() является , возвращая локальную переменную функции (т. в стеке функции). Поскольку стоп очищается после того, как вы оставите функцию some_str_func(), в main() было бы невозможно, чтобы получить содержимое some_str, которое является «Hello World».

Если вы попытаетесь запустить его, вы получите:

$ gcc test.c 
$ ./a.out 

$ 

Он ничего не печатает, потому что он не может получить доступ к some_str. Чтобы исправить это, вы выделяете некоторое пространство памяти для строки «Hello World». как так:

#include <stdio.h> 
#include <string.h> 

char *some_string_func() 
{ 
    char *some_str; 

    /* allocate 12 chars (for "Hello World!") + 1 null '\0' char */ 
    some_str = calloc(13, sizeof(char)); 

    strcpy(some_str, "Hello World!"); 

    return some_str; 
} 

int main() 
{ 
    char *str = some_string_func(); 
    printf("%s\n", str); 

    free(str); /* remember to free the allocated memory */ 
    return 0; 
} 

Теперь, когда вы скомпилировать и запустить его, вы получите:

$ gcc test.c 
$ ./a.out 
Hello World! 
$ 

Если вы с трудом понимая C, я знаю, что многие люди находят «Язык программирования C» по Брайан У. Керниган и Деннис Ритчи - действительно хорошая рекомендация, однако более современная и графическая (даже забавная, чтобы читать!) Книга - Head First C Дэвид и Дон Гриффитс объясняют многие важные понятия C, такие как куча и стек, разница между динамическими и статическими библиотеками C, почему использование Make-файлов - хорошая идея, как doe s Сделайте работу, и многие другие концепции, ранее не описанные в общих книгах C, определенно заслуживают внимания.

Другим хорошим онлайн-ресурсом является Zed Shaws Learn C the Hard way, в котором он содержит хорошие примеры кода и примечания.

Answer 2

void* malloc (size_t size); 

Выделяют блок

памяти Выделяется блок размером байт памяти, возвращая указатель на начало блока. Содержимое вновь выделенного блока не инициализируется, оставаясь с неопределенными значениями. Если размер равен нулю, возвращаемое значение зависит от конкретной реализации библиотеки (это может быть или не быть нулевым указателем), но возвращаемый указатель не может быть разыменован.

И не произносить результат malloc.

Кроме того, необходимо освободить эту память:

void free (void* ptr); 

Освобождает блок памяти

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

Answer 3

Read: void *malloc(size_t size);

malloc() функция выделяет size байт и возвращает указатель на выделенную память. Память не инициализируется. Если размер равен 0, , то malloc() возвращает либо NULL, либо уникальное значение указателя, которое позже может быть отправлено в free().

Соответственно, в

struct node* node = (struct node*)malloc(sizeof(struct node)); 
    //          ^----size---------^ 

вы выделяете кусок памяти size = sizeof naode байт и адрес возврат из таНоса хранящегося в node указателе.

Примечание У вас есть имя переменной переменной не должно быть node, так как это имя структуры. Ты можешь! но не хорошая практика. Кроме того, sizeof(*pointer) является предпочтительным по сравнению с sizeof(Type) в том случае, когда тип когда-либо изменен.

Боковое примечание. Безопасно избегать не набрасывать обратный адрес функцией malloc и calloc. следующим образом: Do I cast the result of malloc?

Так правильно предпочтительной формой выше утверждения:

struct node* nd = malloc(sizeof *nd); 
    //      ^----size-^ 

Два исправлениях: (1) Удалить напечатанный и (2) изменить имя переменной nd.

Answer 4

вы используете malloc, чтобы, как правило, указатели могли что-то указывать.

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

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

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

Answer 5

Использование sizeof -

sizeof (T) покажет количество байтов, необходимых для хранения переменной типа T

Использование malloc -

Malloc выделяет динамически, то есть во время выполнения (когда ваша программа фактически является exec uted по процессору и его памяти). Мы используем это в основном, когда мы не уверены в объеме памяти, который требуется во время выполнения. Поэтому мы динамически выделяем его во время выполнения, используя malloc.

Используя (struct node*) -

Malloc возвращает указатель на блок памяти с объемом пространства, которое вы просили (по своим параметрам). Это пространство - это просто место в памяти. Таким образом, этот указатель не имеет типа, связанного с ним. Мы передаем этот указатель (struct node*), потому что он позволит машине узнать, что переменные типа (struct node) будут сохранены в этой памяти.

Answer 6

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

alocates достаточно пространства, чтобы провести node структуру