Создать 2D массив динамического размера в C

Question

Допустим, у нас есть строка слов, разделенных запятой. Я хочу написать код на C для хранения этих слов в переменной.

Пример

amazon, google, facebook, twitter, salesforce, sfb

Мы не знаем, сколько слов присутствует.

Если бы я делал это в C, я думал, что мне нужно сделать 2 итерации. Первая итерация, я считаю, сколько слов присутствует. Затем на следующей итерации я сохраняю каждое слово.

Step 1: 1st loop -- count number of words
....
....
//End 1st loop. num_words is set. 

Step 2:
// Do malloc using num_words.
char **array = (char**)malloc(num_words* sizeof(char*));

Step 3: 2nd loop -- Store each word. 
// First, walk until the delimiter and determine the length of the word
// Once len_word is determined, do malloc
*array= (char*)malloc(len_word * sizeof(char));
// And then store the word to it

// Do this for all words and then the 2nd loop terminates

Можно ли сделать это более эффективно? Я не люблю иметь 2 петли. Я думаю, что должен быть способ сделать это в 1 цикле только с простыми указателями.

Единственное ограничение заключается в том, что это должно быть сделано в C (из-за ограничений, которые не находятся под моим контролем)

Answer 1

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

Для анализа буфера строки ввода вы можете использовать strtok для токенизации отдельных слов.

При сохранении проанализированных слов в массиве списка слов вы можете использовать strdup для создания копии токенизированного слова. Это необходимо для слова persist . То есть все, на что вы указывали в буфере строк в первой строке, будет засорено, когда вы прочитаете вторую строку (и так далее ...)

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

char **words;
size_t wordmax;
size_t wordcount;

int
main(int argc,char **argv)
{
    char *cp;
    char *bp;
    FILE *fi;
    char buf[5000];

    --argc;
    ++argv;

    // get input file name
    cp = *argv;
    if (cp == NULL) {
        printf("no file specified\n");
        exit(1);
    }

    // open input file
    fi = fopen(cp,"r");
    if (fi == NULL) {
        printf("unable to open file '%s' -- %s\n",cp,strerror(errno));
        exit(1);
    }

    while (1) {
        // read in next line -- bug out if EOF
        cp = fgets(buf,sizeof(buf),fi);
        if (cp == NULL)
            break;

        bp = buf;
        while (1) {
            // tokenize the word
            cp = strtok(bp," \t,\n");
            if (cp == NULL)
                break;
            bp = NULL;

            // expand the space allocated for the word list [if necessary]
            if (wordcount >= wordmax) {
                // this is an expensive operation so don't do it too often
                wordmax += 100;

                words = realloc(words,(wordmax + 1) * sizeof(char *));
                if (words == NULL) {
                    printf("out of memory\n");
                    exit(1);
                }
            }

            // get a persistent copy of the word text
            cp = strdup(cp);
            if (cp == NULL) {
                printf("out of memory\n");
                exit(1);
            }

            // save the word into the word array
            words[wordcount++] = cp;
        }
    }

    // close the input file
    fclose(fi);

    // add a null terminator
    words[wordcount] = NULL;

    // trim the array to exactly what we need/used
    words = realloc(words,(wordcount + 1) * sizeof(char *));

    // NOTE: because we added the terminator, _either_ of these loops will
    // print the word list
#if 1
    for (size_t idx = 0;  idx < wordcount;  ++idx)
        printf("%s\n",words[idx]);
#else
    for (char **word = words;  *word != NULL;  ++word)
        printf("%s\n",*word);
#endif

    return 0;
}

Answer 2

Мы не знаем, сколько слов присутствует.

Мы знаем num_words <= strlen(string) + 1. Нужна только 1 «петля». Обман здесь - быстрый переход s через strlen().

// *alloc() out-of-memory checking omitted for brevity
char **parse_csv(const char *s) {
  size_t slen = strlen(s);
  size_t num_words = 0;
  char **words = malloc(sizeof *words * (slen + 1));

  // find, allocate, copy the words
  while (*s) {
    size_t len = strcspn(s, ",");
    words[num_words] = malloc(len + 1);
    memcpy(words[num_words], s, len);
    words[num_words][len] = '\0';
    num_words++;
    s += len;    // skip word
    if (*s) s++; // skip ,
  }

  // Only 1 realloc() needed.
  realloc(words, sizeof *words *num_words);  // right-size words list
  return words;
}

Это заставляет отправить на NULL завершить список, поэтому

  char **words = malloc(sizeof *words * (slen + 1 + 1));
  ...
  words[num_words++] = NULL;
  realloc(words, sizeof *words *num_words);
  return words;

---

Рассматривая наихудший случай для начального char **words = malloc(...);, я беру строку, подобную ",,," с ее 3 ',', которая будет составлять 4 слова "", "", "", "". При необходимости измените код для таких патологических случаев.

Answer 3

То, что вы ищете, это http://manpagesfr.free.fr/man/man3/strtok.3.html

(со страницы руководства)

Функция strtok () анализирует строку в последовательность токенов. При первом вызове strtok () анализируемая строка должна быть указана в str. При каждом последующем вызове, который должен анализировать одну и ту же строку, str должен быть NULL.

Но этот поток выглядит как дубликат Разделенная строка с разделителями в C Если вы не обязаны создавать свою собственную реализацию ...