Могу ли я использовать динамическое распределение памяти, чтобы уменьшить размер массива int и затем перераспределить память? - PullRequest
Новая
       17

Могу ли я использовать динамическое распределение памяти, чтобы уменьшить размер массива int и затем перераспределить память?

0 голосов
/ 22 января 2019

Я создал программу, которая подсчитывает, сколько раз было найдено string в списке, печатает это число на экране и сохраняет его в int *arr.Однако, когда есть два одинаковых strings, результат count очевидно печатается и сохраняется дважды в выводе / списке.У меня такой вопрос: могу ли я проверить, было ли слово найдено дважды, и если да, то free этот блок памяти и использовать realloc() для перераспределения памяти для всего int *arr?Вот мой sortedCount() метод, который делает то, что я сказал выше: 

void sortedCount(int N) {
    int *wordCount;
    int i = 0;
    wordCount = malloc(N * sizeof(int));
    for(i = 0; i < N; i++) {
        wordCount[i] = count(N,wordList[i],1);
    }
    /* free mem */
    free(wordCount);
    return;
}

1 Ответ

0 голосов
/ 22 января 2019

Допустим, у вас есть динамически распределенный массив из words слов: 

char  **word;
size_t  words;

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

Идея состоит в том, что у нас есть два массива words элементов каждый: 

size_t *rootword;
size_t *occurrences;

Массив rootword содержит индекс первого вхождения этого слова, а массив occurrences содержит количество вхождений для каждого первого вхождения слова.

Например, если words = 5и word = { "foo", "bar", "foo", "foo", "bar" }, затем rootword = { 0, 1, 0, 0, 1 } и occurrences = { 3, 2, 0, 0, 0 }.

Чтобы заполнить массивы rootword и occurrences, вы сначала инициализируете два массива так, чтобы все слова были уникальными и встречались ровно один раз."состояние: 

    for (i = 0; i < words; i++) {
        rootword[i] = i;
        occurrences[i] = 1;
    }

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

    for (i = 0; i < words; i++) {

        if (occurrences[i] < 1)
            continue;

        for (j = i + 1; j < words; j++)
            if (occurrences[j] == 1 && strcmp(word[i], word[j]) == 0) {
                /* word[j] is a duplicate of word[i]. */
                occurrences[i]++;
                rootword[j] = i;
                occurrences[j] = 0;
            }
    }

Во внутреннем цикле мы, очевидно, игнорируем слова, которые уже являютсяизвестны как дубликаты (и j повторяется только по словам, где occurrences[j] может быть только 0 или 1).Это также ускоряет внутренний цикл для последующих корневых слов, поскольку мы сравниваем только слова-кандидаты, а не те слова, для которых мы уже нашли корневое слово.

Давайте рассмотрим, что происходит в циклах с вводом word = { "foo", "bar", "foo", "foo", "bar" }. 

 i ╷ j ╷ rootword  ╷ occurrences ╷ description
───┼───┼───────────┼─────────────┼──────────────────
   │   │ 0 1 2 3 4 │ 1 1 1 1 1   │ initial values
───┼───┼───────────┼─────────────┼──────────────────
 0 │ 1 │           │             │ "foo" != "bar".
 0 │ 2 │     0     │ 2   0       │ "foo" == "foo".
 0 │ 3 │       0   │ 3     0     │ "foo" == "foo".
 0 │ 4 │           │             │ "foo" != "bar".
───┼───┼───────────┼─────────────┼──────────────────
 1 │ 2 │           │             │ occurrences[2] == 0.
 1 │ 3 │           │             │ occurrences[3] == 0.
 1 │ 4 │         1 │   2     0   │ "bar" == "bar".
───┼───┼───────────┼─────────────┼──────────────────
 2 │   │           │             │ j loop skipped, occurrences[2] == 0.
───┼───┼───────────┼─────────────┼──────────────────
 3 │   │           │             │ j loop skipped, occurrences[3] == 0.
───┼───┼───────────┼─────────────┼──────────────────
 4 │   │           │             │ j loop skipped, occurrences[4] == 0.
───┼───┼───────────┼─────────────┼──────────────────
   │   │ 0 1 0 0 1 │ 3 2 0 0 0   │ final state after loops.
...