Давайте начнем с логики.
Как обрабатывается строка типа A quick brown fox.?Я бы предложил:
Подсчитать количество слов и объем памяти, необходимый для хранения слов.(В C каждая строка заканчивается нулевым завершающим байтом, \0.)
Выделите достаточно памяти для указателей и слов.
Скопируйте каждое слово из исходной строки.
У нас есть строка в качестве ввода, и мы хотим получить массив строк в качестве вывода.Простейшим вариантом является
char **split_words(const char *source);
, где возвращаемое значение равно NULL в случае ошибки или массив указателей, оканчивающихся указателем NULL в противном случае.Все это распределяется динамически одновременно, поэтому вызов free() для возвращаемого значения освободит как указатели, так и их содержимое.
Давайте начнем реализовывать логику в соответствии с пунктами выше.
#include <stdlib.h>
char **split_words(const char *source)
{
size_t num_chars = 0;
size_t num_words = 0;
size_t w = 0;
const char *src;
char **word, *data;
/* Sanity check. */
if (!source)
return NULL; /* split_words(NULL) will return NULL. */
/* Count the number of words in source (num_words),
and the number of chars needed to store
a copy of each word (num_chars). */
src = source;
while (1) {
/* Skip any leading whitespace (not just spaces). */
while (*src == '\t' || *src == '\n' || *src == '\v' ||
*src == '\f' || *src == '\r' || *src == ' ')
src++;
/* No more words? */
if (*src == '\0')
break;
/* We have one more word. Account for the pointer itself,
and the string-terminating nul char. */
num_words++;
num_chars++;
/* Count and skip the characters in this word. */
while (*src != '\0' && *src != '\t' && *src != '\n' &&
*src != '\v' && *src != '\f' && *src != '\r' &&
*src != ' ') {
src++;
num_chars++;
}
}
/* If the string has no words in it, return NULL. */
if (num_chars < 1)
return NULL;
/* Allocate memory for both the pointers and the data.
One extra pointer is needed for the array-terminating
NULL pointer. */
word = malloc((num_words + 1) * sizeof (char *) + num_chars);
if (!word)
return NULL; /* Not enough memory. */
/* Since 'word' is the return value, and we use
num_words + 1 pointers in it, the rest of the memory
we allocated we use for the string contents. */
data = (char *)(word + num_words + 1);
/* Now we must repeat the first loop, exactly,
but also copy the data as we do so. */
src = source;
while (1) {
/* Skip any leading whitespace (not just spaces). */
while (*src == '\t' || *src == '\n' || *src == '\v' ||
*src == '\f' || *src == '\r' || *src == ' ')
src++;
/* No more words? */
if (*src == '\0')
break;
/* We have one more word. Assign the pointer. */
word[w] = data;
w++;
/* Count and skip the characters in this word. */
while (*src != '\0' && *src != '\t' && *src != '\n' &&
*src != '\v' && *src != '\f' && *src != '\r' &&
*src != ' ') {
*(data++) = *(src++);
}
/* Terminate this word. */
*(data++) = '\0';
}
/* Terminate the word array. */
word[w] = NULL;
/* All done! */
return word;
}
Мы можем проверить вышеупомянутое с помощью небольшого теста main():
#include <stdio.h>
int main(int argc, char *argv[])
{
char **all;
size_t i;
all = split_words(" foo Bar. BAZ!\tWoohoo\n More");
if (!all) {
fprintf(stderr, "split_words() failed.\n");
exit(EXIT_FAILURE);
}
for (i = 0; all[i] != NULL; i++)
printf("all[%zu] = \"%s\"\n", i, all[i]);
free(all);
return EXIT_SUCCESS;
}
Если мы скомпилируем и запустим вышеизложенное, мы получим
all[0] = "foo"
all[1] = "Bar."
all[2] = "BAZ!"
all[3] = "Woohoo"
all[4] = "More"
Недостатки этого подхода(использование одного вызова malloc() для выделения памяти как для указателей, так и для данных) заключается в том, что мы не можем легко увеличить массив;мы действительно можем рассматривать его как один большой комок.
Лучший подход, особенно если мы собираемся динамически добавлять новые слова, - это использовать структуру:
typedef struct {
size_t max_words; /* Number of pointers allocated */
size_t num_words; /* Number of words in array */
char **word; /* Array of pointers */
} wordarray;
К сожалениюНа этот раз нам нужно выделить каждое слово отдельно.Однако, если мы используем структуру для описания каждого слова в общем буфере выделения, скажем,
typedef struct {
size_t offset;
size_t length;
} wordref;
typedef struct {
size_t max_words;
size_t num_words;
wordref *word;
size_t max_data;
size_t num_data;
char *data;
} wordarray;
#define WORDARRAY_INIT { 0, 0, NULL, 0, 0, NULL }
static inline const char *wordarray_word_ptr(wordarray *wa, size_t i)
{
if (wa && i < wa->num_words)
return wa->data + wa->word[i].offset;
else
return "";
}
static inline size_t wordarray_word_len(wordarray *wa, size_t i)
{
if (wa && i < wa->num_words)
return wa->word[i].length;
else
return 0;
}
Идея состоит в том, что если вы объявите
wordarray words = WORDARRAY_INIT;
, вы можете использовать wordarray_word_ptr(&words, i) дляполучить указатель на i -ное слово или указатель на пустую строку, если i -ое слово еще не существует, и wordarray_word_len(&words, i), чтобы получить длину этого слова (намного быстрее, чем вызов strlen(wordarray_word_ptr(&words, i))).
Основная причина, по которой мы не можем использовать char * здесь, заключается в том, что realloc() область данных (на которую указывают указатели слова) может изменить свой адрес.Если бы это произошло, нам пришлось бы настроить каждый указатель в нашем массиве.Вместо этого гораздо проще использовать смещения для области данных.
Единственный недостаток этого подхода заключается в том, что удаление слов не означает соответствующего сокращения в области данных.Однако можно написать простую функцию «компактора», которая перепаковывает данные в новую область, так что дыры, оставленные удаленными словами, «перемещаются» в конец области данных.Обычно в этом нет необходимости, но вы можете добавить элемент в структуру wordarray, скажем, количество потерянных символов в результате удаления слов, чтобы сжатие можно было выполнить эвристически, в следующий раз, когда область данных будет изменена в противном случае..