Неверное расположение структуры в C, которая имеет структуры в качестве элементов? - PullRequest
0 голосов
/ 04 апреля 2019

Скажите, у меня есть

struct node {
  struct example *left;
  struct example *right;
  int whatever;
};

struct example { 
  struct example *foo;
  struct example *bar;
}

Теперь, когда я делаю

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

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

Это

a) достаточно места для пустого шаблона структуры.

b) две структуры внутри узла структуры также инициированы? Так я могу начать делать что-то вроде example_node-> left-> foo?

в) Инициирован пример структуры * foo для левой и правой сторон?

Я просто запутался в том, что у меня есть доступ, что мне нужно бесплатно и т. Д.

Ответы [ 3 ]

2 голосов
/ 04 апреля 2019

Учтите, что

  • sizeof(struct node) дает размер структуры node
  • malloc( N ) выделяет N байтов из памяти

Таким образомmalloc(sizeof(struct node)) выделяет как минимум количество байтов, необходимое для хранения struct node.

Внутри структуры node

struct example *left;
struct example *right;
int whatever;

это два указателя дляструктура example и целое число.

Таким образом, выделенная область памяти достаточно велика, чтобы содержать эти 2 указателя и int.Не целые example структуры, только указатели.

Чтобы завершить распределение, вы, вероятно, захотите также выделить две внутренние структуры, например

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

example_node->left  = malloc(sizeof(struct example));
example_node->right = malloc(sizeof(struct example));

Youосвободите эти распределения в обратном порядке,

  1. начните освобождать left и right
  2. Затем освободите структуру node

Как только вы что-то освободите, оно больше не будет доступно.То, что может работать, но это неопределенное поведение.

Таким образом, если вы сначала освободите node, вы не сможете надежно добраться до left и right членов, которые зависят от node (находясь внутри).

free (example_node->left);
free (example_node->right);

free (example_node);
1 голос
/ 04 апреля 2019

Если вы находитесь в среде x64 с упаковкой и без выравнивания, то sizeof( struct node ) == 20, потому что 8 + 8 + 4 == 20:

sizeof( struct example* ) == 8        // Remember this struct member is a pointer, not a value
sizeof( struct example* ) == 8        // Ditto
sizeof( int             ) == 4        // `int` is usually 4 bytes

что на самом деле делает этот malloc? Я знаю, что он должен распределять память так, чтобы example_node мог указывать на адрес где-то, который содержит достаточно байтов для всего узла структуры

Это правильно.

В пользовательской среде типичной настольной операционной системы ваш код будет выполняться в области памяти процесса. Память (часто) поставляется большими кусками, называемыми «страницами», предоставляемыми операционной системой, и malloc среды выполнения C будет запрашивать эти страницы и затем управлять распределением данных в пределах этих страниц.

В среде настольной ОС malloc( 20 ) делает что-то вроде этого:

  • Достаточно ли у нас места на доступной странице для непрерывных 20 байтов?
    • Да? Затем используйте нашу карту внутренней памяти, чтобы найти непрерывную 20-байтовую область и вернуть адрес первого байта этой области.
    • Нет? Затем запросите новую страницу в операционной системе, добавьте ее на карту внутренней памяти и верните адрес области на этой новой странице.
      • Если запрос новой страницы не удался, верните NULL.

a) Достаточно ли места для запуска пустого шаблона структуры

Краткий ответ: да - потому что вы сделали malloc( sizeof( struct node ) ), , однако malloc может потерпеть неудачу (в этом случае возвращается NULL (0), и важно проверять это после каждого Это может произойти из-за нехватки памяти, чрезмерной фрагментации и т. д.

struct node *example_node = malloc(sizeof(struct node));
if( !example_node ) {
    puts( "Allocation failed. Exiting." );
    exit( 1 );
}

b) две структуры внутри узла структуры также инициированы? Так я могу начать делать что-то вроде example_node-> left-> foo?

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

в) Инициирован пример структуры * foo для левого и правого каналов?

Нет. Смотри мой ответ выше.

Ваши случаи struct node и struct example могут быть заполнены рекурсивно до бесконечности - насколько далеко вы зайдете, зависит от вас.

Чтобы создать простое двоичное дерево глубиной 3 узла:

struct node* allocateNode() {
    struct node* newNode = malloc( sizeof( struct node ) );
    if( !newNode ) exit( 1 ); // fast-fail
    newNode.left  = NULL; // zero-out the pointer members because `malloc` does not zero out memory for you!
    newNode.right = NULL;
    return newNode;
}

void initializeNode( struct node* parent ) {

    parent.left  = malloc( sizeof( struct node ) );
    parent.right = malloc( sizeof( struct node ) );
}

void createTree( struct node* parent, int depth ) {

    if( depth <= 0 ) return NULL;

    parent.left  = allocateNode();

    createTree( parent.left, depth - 1 );

    parent.right = allocateNode();

    createTree( parent.right, depth - 1 );
}

void destroyTree( struct node* node ) {

    if( node == NULL ) return;

    destroyTree( node.left );
    destroyTree( node.right );

    free( node );
}

int main( int argc, char* argv[] ) {

    struct node* root = allocateNode();

    createTree( root, 3 );

    // (do stuff here)

    destroyTree( root );

    return 0;
}

Хочу отметить, что вы могли бы сделать это более эффективно, используя calloc и выделив все узлы одновременно:

int main( int argc, char* argv[] ) {

    const size_t n = 7; // a tree 3 layers deep has 7 nodes: 1, 2L, 2R, 3LL, 3LR, 3RL, 3RR
    struct node[] allNodes = calloc( n, sizeof(struct node) ); 
    if( !allNodes ) exit( 1 );

    // Binary heap array representation algorithm:
    size_t lastParent = 3;
    for( size_t i = 0; i < n; i++ ) {

        if( i < lastParent ) {
            allNodes[i].left  = allNodes[ ( 2 * i ) + 1 ];
            allNodes[i].right = allNodes[ ( 2 * i ) + 2 ];
        }
        else {
            allNodes[i].left  = NULL;
            allNodes[i].right = NULL;
        }
    }

    return 0;
}

ВАЖНОЕ ПРИМЕЧАНИЕ !!!!!! 11111!

Никогда не забывайте звонить free за каждый успешный malloc или calloc звонок! В противном случае вы потеряете память!

1 голос
/ 04 апреля 2019

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

Тогда почему мне удалось написать example_node-> left = NULL;сразу вместо того, чтобы выделять память для левого?

Это изменит указатель, записав NULL в память, выделенную указателю, точно так же, как example_node->whatever = 0 записал бы 0 впамять, выделенная для целого числа.Он ничего не делает с какой-либо памятью вне самой структуры узла.Однако, если бы вы сказали example_node->left->foo = NULL, вы бы поступили плохо (тм).


РЕДАКТИРОВАТЬ : Я думаю, что у вас все еще есть проблемы с памятью указателя ипамять под указателем.Давайте попробуем аналогию.Представьте, что вы живете в многоквартирном доме, где вы можете арендовать складские помещения в подвале.Представьте также, что каждая квартира поставляется с мебелью, частью которой является стойка для ключей рядом со входом.Стеллаж для ключей имеет крючок с надписью «Ключ для хранения».

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

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

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

Вы можете открыть только комнату, которую владеете .


node ваша квартира: если вы выделили node (еслиу вас есть квартира) у вас есть место для указателя left (у вас есть крючок с ключом для хранения).node->left имеет выделенную для него память как часть node выделения (вы получаете хук ключа хранилища независимо от того, арендуете ли вы хранилище или нет).

Вы можете назначить NULL на left (ничего не ставить нахук), или вы можете назначить значение указателя (поместив ключ на хук).

Если left равно NULL, вы не можете сделать example_node->left->foo = ..., потому чтонулевой указатель явно говорит, что он не указывает ни на какую выделенную память (не может открыть ни одно хранилище без ключа).

Вы можете сделать example_node->left = 0xdeadbeef (поместите чье-либо хранилищеключ на крючке), но вы не можете , а затем example_node->left->foo = ..., потому что пространство в 0xdeadbeef, скорее всего, не ваше, чтобы вмешиваться (используя чью-то комнату хранения).

Вы можно сделать example_node->left = malloc(...) (арендовать помещение для хранения и поставить ключ на крюк для хранения), и после этого вы сможете сделать example_node->left->foo = ... (потому что вы владеете комнатой иключом, и вы можете добавить туда новое, если хотите).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...