Рекурсивная структура и malloc () - PullRequest
Новая
       10

Рекурсивная структура и malloc ()

1 голос
/ 27 ноября 2011

У меня есть рекурсив struct, который: 

typedef struct dict dict;
struct dict {
    dict *children[M];
    list *words[M];
};

Инициализирован следующим образом: 

dict *d = malloc(sizeof(dict));
bzero(d, sizeof(dict));

Я хотел бы знать, что именно bzero() здесь делает и какмогу ли я malloc() рекурсивно для детей.

Редактировать : Вот как я хотел бы иметь возможность malloc() children и words: 

void dict_insert(dict *d, char *signature, unsigned int current_letter, char *w) {
    int occur;
    occur = (int) signature[current_letter];
    if (current_letter == LAST_LETTER) {
        printf("word found : %s!\n",w);
        list_print(d->words[occur]);
        char *new;
        new = malloc(strlen(w) + 1);
        strcpy(new, w);
        list_append(d->words[occur],new);
        list_print(d->words[occur]);
    }
    else {
        d = d->children[occur];
        dict_insert(d,signature,current_letter+1,w);
    }
}

Ответы [ 3 ]

2 голосов
/ 27 ноября 2011

bzero(3) инициализирует память на ноль. Это эквивалентно вызову memset(3) со вторым параметром 0. В этом случае он инициализирует все переменные-члены нулевыми указателями. bzero считается устаревшим, поэтому вы должны заменить его на memset; В качестве альтернативы вы можете просто позвонить calloc(3) вместо malloc, что автоматически обнулит возвращенную память для вас при успехе.

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

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

1 голос
/ 27 ноября 2011

В общем, когда вы не уверены, что генерирует для вас компилятор, рекомендуется использовать printf для сообщения о размере структуры. В этом случае размер dict должен составлять 2 * M * размера указателя. В этом случае bzero заполнит диктант нулями. Другими словами, все элементы M массивов потомков и слов будут равны нулю.

Чтобы инициализировать структуру, я рекомендую создать функцию, которая принимает указатель на dict и назначает malloc каждому дочернему элементу, а затем вызывает себя для его инициализации: 

void init_dict(dict* d)
{
    int i;
    for (i = 0; i < M; i++)
    {
        d->children[i] = malloc(sizeof(dict));
        init_dict(d->children[i]);

        /* initialize the words elements, too */
    }
}

+ 1 для вас, если вы видите, почему этот код не будет работать как есть. (Подсказка: он имеет бесконечную ошибку рекурсии и нуждается в правиле, которое сообщает ему, насколько глубоко должно быть дочернее дерево, чтобы оно могло прекратить повторение.)

1 голос
/ 27 ноября 2011

bzero просто обнуляет память. bzero(addr, size) по существу эквивалентно memset(addr, 0, size). Что касается того, почему вы используете его, из того, что я видел примерно в половине случаев его использования, это просто потому, что кто-то, хотя обнуление памяти казалось хорошей идеей, даже если она ничего не достигла. В этом случае, похоже, что эффектом будет установка для некоторых указателей значения NULL (хотя это не совсем переносимо для этой цели).

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

void alloc_tree(dict **root, size_t depth) { 
    int i;
    if (depth == 0) {
        (*root) = NULL;
        return;
    }

    (*root) = malloc(sizeof(**root));

    for (i=0; i<M; i++)
        alloc_tree((*root)->children+i, depth-1);       
}

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

...