Цели: приобретение навыков работы с массивами массивов и си-строками, закрепление навыков организации двойных циклов.
Критерии полноты
cstring.Си-строка или нуль-терминированная строка — структура данных, представляющая собой массив символов, последний из которых (и только он) имеет числовое значение ноль.
Таким образом, строкой можно оперировать только по указателю на начальный символ, не храня её размер явно. Очевидно, что си-строка не может содержать символы с кодом ноль. С другой стороны, если по каким-то причинам завершающий нулевой символ будет потерян, то попытки работы с такой строкой, вероятно, приведут к выходу за пределы выделенного под неё блока памяти, что чревато “падением” приложения или серьёзными ошибками в его работе (в том числе рисками утечек данных).
Си-строки и особенности работы с ними являются одним из основных источников “дыр” в безопасности сетевых приложений, написанных на C, поэтому в программах на C++ рекомендуется использовалась std::string или другие аналогичные возможности из сторонних библиотек. Однако ввиду распространённости си-строк и их примитивности желательно иметь навыки работы с ними.
См. также Работа со строками: cstring.
Данный пример демонстрирует возможную реализацию некоторых действий: чтения массива строк со стандартного потока ввода и вывод массива строк в стандартный поток вывода. Для реализации данных операций используется стандартная библиотека C (см. память и си-строки)
Для вывода строки в поток будем использовать стандартную функцию puts.
Вывод массива строк, учитывая соглашение о том, что последний элемент — нулевой указатель, можно записать в виде простого цикла.
/// Вывести в стандартный поток вывода массив строк.
/// lines -- указатель на массив константных указателей на массивы константных символов.
void putlines(const char* const* lines)
{
if (!lines)
return;
while (*lines)
puts(*lines++);
}Аналогично будет выглядеть и операция освобождения памяти. Предположим, что для выделения памяти на все строки массива и сам массив указателей на строки использовалась стандартная функция malloc — тогда освобождать память надо будет функцией free.
/// Освободить память, занимаемую массивом строк.
void freelines(char** lines)
{
if (!lines)
return;
for (auto p = lines; *p != nullptr; ++p)
free(*p);
free(lines);
}Выполнить чтение строки с потока ввода уже значительно труднее, так как мы не знаем заранее её длину. Стандартная функция gets читает в буфер, размер которого выбирает пользователь, предполагая, что его “хватит”. Такой подход приводит к ошибкам и уязвимостям в коде, поэтому функция gets объявлена устаревшей, и использовать её не рекомендуется.
Вместо gets следует использовать функцию fgets, которая принимает размер буфера. Но она всё равно не решает исходную задачу: буфер фиксированного размера мы должны заготовить заранее под строку неизвестной длины…
В данной ситуации решение может дать одно из двух:
В примере выбран подход (2), а подход (1) прибережём для массива указателей на строки (количество строк тоже заранее не известно).
Подход (2) имеет очевидный недостаток: “прочитанный” текст может не совпасть с исходным текстом из-за вставки разрывов строк, которых в исходном тексте не было. Однако применение данного подхода всё же может быть оправдано следующими соображениями: во-первых наш буфер может быть достаточного размера для реальных текстов (большинство текстов не содержат слишком длинных строк), во-вторых, посимвольное чтение строки “вручную” будет работать на порядок медленнее, чем оптимизированный библиотечный вариант fgets, если поток ввода получает данные из оперативной памяти (кэш или данные, сгенерированные другой программой без записи в файл на диске), что может быть важно в некоторых случаях.
/// Максимальная длина строки (не включая '\0'), возвращаемой нашим вариантом gets.
const size_t MAX_GETS_LENGTH = 1023;
/// Вместо std::gets (которая объявлена устаревшей), мы реализуем
/// собственную функцию gets, создающую строку в динамической памяти.
/// Если строка на вводе слишком длинная, отрезаем на MAX_GETS_LENGTH символах.
/// Возвращает нулевой указатель, если не удалось прочитать ни одного символа.
char* gets()
{
char buffer[MAX_GETS_LENGTH + 1];
if (!fgets(buffer, MAX_GETS_LENGTH + 1, stdin))
return nullptr;
// Узнать длину считанной строки.
auto alloc_len = strlen(buffer) + 1;
// В отличие от gets, fgets записывает в буфер и перевод строки (если хватает места).
// Уберём этот перевод строки.
if (alloc_len > 1 && buffer[alloc_len - 2] == '\n')
{
buffer[alloc_len - 2] = '\0';
--alloc_len;
}
// Выделить в динамической памяти место на копию.
const auto new_str = (char*)malloc(alloc_len);
if (!new_str) // не хватило памяти?
return nullptr;
// Скопировать содержимое буфера в выделенную память.
memcpy(new_str, buffer, alloc_len);
return new_str;
}Массив строк будем увеличивать динамически по мере необходимости. Для этого удобно использовать функцию realloc.
Традиционно реализуется следующая стратегия: выделяется пространства больше, чем задействовано и на каждой итерации проверяется, не исчерпано ли доступное пространство (“ёмкость” capacity). Если исчерпано, то пробуем увеличить его, но не на один элемент, а сразу в 1 < g < 2 раз. Эту константу “роста” выбирают строго меньше 2 для того, чтобы при очередном выделении памяти оказалось возможным задействовать под массив ранее освобождённую память (при g = 2 каждый раз будет выделяться памяти больше, чем суммарно выделялось ранее). В примере выбрано g = 1.5. А уже в случае неудачи кратного увеличения пробуем увеличить хранилище на один элемент.
/// Читаем построчно и складываем в динамический массив указатели.
/// Последний указатель в массиве обязательно нулевой.
/// Возвращает нулевой указатель в случае невозможности выделить память хотя бы на два указателя.
/// Увеличиваем массив "на ходу" по мере необходимости.
char** getlines()
{
auto lines = (char**)calloc(2, sizeof(char*));
if (!lines) // не хватило памяти?
return nullptr;
// Цикл по строкам.
for (size_t item = 0, capacity = 2; lines[item++] = gets();)
{
if (capacity == item + 1) // все элементы массива задействованы -- увеличим его
{
// Попытка 1: попробуем увеличить capacity в 1.5 раза.
capacity += capacity / 2 + 1;
// Для больших capacity возможно переполнение capacity * sizeof(char*).
assert((capacity * sizeof(char*)) / sizeof(char*) == capacity);
if (auto new_lines = (char**)realloc(lines, capacity * sizeof(char*)))
{
lines = new_lines;
}
else // Попытка 2: попробуем увеличить capacity на 1 элемент.
if (auto new_lines = (char**)realloc(lines, (item + 2) * sizeof(char*)))
{
capacity = item + 2;
lines = new_lines;
}
else // Не получается выделить память.
{
lines[item] = nullptr; // закрывающий нулевой указатель
break;
}
}
}
return lines;
}
Удалить однострочные комментарии (открывающий комментарий символ задан в виде параметра) без учёта возможных строковых литералов (т.е. пренебрегаем возможной ситуацией, когда “комментарий” на самом деле может быть не комментарием, а частью строковой константы).
В C++ однострочный комментарий открывается парой символов //, поэтому решение, приведённое ниже, не применимо к коду на языке C++.
Алгоритм. Для каждой строки найти первое вхождение заданного символа и обнулить этот байт.
/// Найти в си-строке str символ ch.
/// Возвращает указатель на найденный символ или нулевой указатель,
/// если символа в строке нет.
char* find_char(char *str, char ch)
{
for (; *str != '\0'; ++str)
{
if (*str == ch)
return str;
}
return nullptr;
}
/// Затереть нулём первый символ, открывающий комментарий,
/// закончив таким образом на нём си-строку.
void remove_comment(char *line, char comment_mark)
{
if (auto pos = find_char(line, comment_mark))
*pos = '\0';
}
/// Удалить комментарии из текста.
void remove_comments(char *text[], char comment_mark)
{
for (; *text != nullptr; ++text)
remove_comment(*text, comment_mark);
}Тестирование: массив строк input содержит вход, массив строк reference содержит ожидаемый результат.
/// Тест функции remove_comments.
bool test_remove_comments()
{
// Исходный текст.
const char *input[] =
{
"",
"# comment",
"something; # comment",
"'hello, world!'",
"'# not a comment but it's OK to cut here too'... # a real comment",
nullptr
};
// Текст результата, который должен получиться.
const char *reference[] =
{
"",
"",
"something; ",
"'hello, world!'",
"'",
nullptr
};
// ...
}Данная функция не дописана, потому что не хватает ряда вспомогательных определений. Дело в том, что input нельзя подать на обработку функцией remove_comments непосредственно. Наши тестовые массивы содержат указатели на содержимое строковых литералов, которое является константой. Изменение содержимого строковых литералов приводит к неопределённому поведению. Поэтому для выполнения теста придётся копировать исходный текст в динамические массивы, которые можно изменять. В отличие от предыдущего примера здесь для управления памятью используем new/delete.
#include <cstring>
/// Определить количество строк в тексте.
std::size_t lines_in_text(const char * const source[])
{
std::size_t source_size = 0;
for (auto p = source; *p != nullptr; ++p)
++source_size;
return source_size;
}
/// Вспомогательная функция для создания копии текста.
/// Она нужна для того, чтобы не изменять значения, заданные строковыми литералами
/// (что чревато неопределённым поведением).
char** copy_text(const char * const source[])
{
// Создать массив строк.
const auto source_size = lines_in_text(source);
auto copy = new char*[source_size + 1];
// Скопировать массив построчно.
for (size_t i = 0; i < source_size; ++i)
{
// Выделить память для новой строки.
const auto line_len = std::strlen(source[i]) + 1;
copy[i] = new char[line_len];
// Скопировать строку (вместе с завершающим нулём).
std::memcpy(copy[i], source[i], line_len);
}
// Записать завершающий нуль.
copy[source_size] = nullptr;
// Вернуть результат.
return copy;
}
/// Освобождение памяти, занятой текстом, созданным с помощью функции copy_text.
void free_text(char *text[])
{
for (auto p = text; *p != nullptr; ++p)
delete[] *p;
delete[] text;
}Сравнивать результат работы remove_comments и содержимое массива reference будем с помощью вспомогательной функции are_equal (её определение и полный текст функции тестирования приведены ниже).
/// Сравнение текстов на равенство.
bool are_equal(const char * const text1[], const char * const text2[])
{
for (; *text1 && *text2; ++text1, ++text2)
{
// Сравнение си-строк на равенство с помощью стандартной функции.
if (std::strcmp(*text1, *text2) != 0)
return false;
}
// Оба указателя должны быть нулевыми, если тексты совпадают.
return *text1 == *text2;
}
/// Тест функции remove_comments.
bool test_remove_comments()
{
// Исходный текст.
const char *input[] =
{
"",
"# comment",
"something; # comment",
"'hello, world!'",
"'# not a comment but it's OK to cut here too'... # a real comment",
nullptr
};
// Текст результата, который должен получиться.
const char *reference[] =
{
"",
"",
"something; ",
"'hello, world!'",
"'",
nullptr
};
auto text = copy_text(input);
remove_comments(text, '#');
const auto result = are_equal(text, reference);
free_text(text);
return result;
}
Дана си-строка, требуется вычленить в ней слова, заполнив массив указателями на первые буквы слов, а пробельные символы заменив нулевыми. Память под массив выделяется извне (пользователем). Функция, решающая данную задачу, принимает указатель на целевой массив и его размер, возвращает указатель на последний необработанный символ (нулевой указатель, если вся строка обработана). Массив указателей на си-строки должен завершаться нулевым указателем.
Алгоритм. Пока исходная строка не кончилась, циклически повторяем два действия: 1) проходим по исходной строке, затирая нулями пробельные символы. Если встретился непробельный символ, то записываем указатель на него на очередную позицию в массиве; 2) двигаемся по строке до первого пробельного символа.
Итак, реализуем эти два действия в виде отдельных функций.
#include <cctype> // isspace
/// Затереть последовательность пробельных символов нулевым символом.
char* zero_spaces(char *text)
{
while (std::isspace(*text))
*text++ = '\0';
return text;
}
/// Пропустить все непробельные символы (кроме завершающего нуля).
char* skip_non_spaces(char *line)
{
while (*line != '\0' && !std::isspace(*line))
++line;
return line;
}Реализация основной функции (назовём её split).
/// Выполнить вычленение "слов" в строке text, указатели на слова записать в массив words.
/// Массив words создаётся кодом, вызывающим эту функцию.
/// Параметром words_size передаётся размер массива words.
char* split(char *text, char *words[], std::size_t words_size)
{
assert(words_size > 1);
const auto max_words = words_size - 1;
for (std::size_t word = 0; word < max_words; ++word)
{
text = zero_spaces(text);
if (*text == '\0')
{
words[word] = nullptr;
return nullptr;
}
words[word] = text;
text = skip_non_spaces(text);
}
words[max_words] = nullptr;
// Перейти к началу следующего слова.
text = zero_spaces(text);
// Возможно, строка кончилась (т.е. был "хвост" из пробельных символов),
// тогда вернуть nullptr.
return *text != '\0' ? text : nullptr;
}Для тестирования нам понадобится только функция are_equal, реализованная в предыдущем примере. Тестирующая функция возвращает “код ошибки”. Это нуль, если ошибок не было обнаружено.
/// Тест split.
int test_split()
{
char text[] = "Just a simple sentence.";
const char *reference[] =
{
"Just",
"a",
"simple",
"sentence.",
nullptr
};
// Проверка случая, когда передан массив достаточного размера.
char *words[10];
if (split(text, words, 10))
return 1; // split должна вернуть нулевой указатель
if (!are_equal(words, reference))
return 2;
// Проверка случая, когда передан массив недостаточного размера.
char long_text[] =
"This program is free software; you can redistribute it and/or modify\n"
"it under the terms of the GNU General Public License as published by\n"
"the Free Software Foundation; either version 3 of the License, or (at\n"
"your option) any later version.";
const auto last_pos = split(long_text, words, 10);
if (!last_pos || sizeof(long_text) < last_pos - long_text)
return 3;
if (*last_pos != 'a') // следующее слово было бы "and/or"
return 4;
const char *long_reference[] =
{
"This",
"program",
"is",
"free",
"software;",
"you",
"can",
"redistribute",
"it",
nullptr
};
if (!are_equal(words, long_reference))
return 5;
return 0; // ошибки не обнаружены.
}
Выполнить конкатенацию массива строк (т.е. получить одну строку, содержащую подряд все строки исходного массива) линейным по числу операций алгоритмом. Массив передаётся указателем const char* const*, длина массива заранее не известна и не передаётся, последний элемент массива — нулевой указатель (завершающий нуль аналогично си-строке). Кроме собственно массива, функция должна принимать указатель на си-строку, которая будет вставляться между строками массива (разделитель).
Пример
Пусть дан входной массив вида:
{
"alpha",
"beta",
"gamma",
nullptr
};и строка-разделитель: ", ". Тогда результирующая строка будет равна "alpha, beta, gamma".
Построить набор строк (массив указателей на строки), заменив в исходном файле заданный символ на нулевые символы.
Пример
Дан текст "One Two Three" и символ-разделитель ' ' (пробел). Результирующий массив должен содержать указатели на три C-строки, равные "One", "Two" и "Three" (и завершающий нуль).
Для заданной максимальной допустимой длины строки выполнить перенос остатков на новые строки (не изменять исходный массив, а построить новый).
Пример
Пусть даны ограничение на ширину строки 6 символов и входной массив вида:
{
"short",
"too long",
"very very long",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
"short",
"too lo",
"ng",
"very v",
"ery lo",
"ng",
nullptr
};Заменить последовательности символов TAB ('\t') в начале каждой строки на пробелы. Количество пробелов, соответствующих одному TAB передавать параметром.
Заменить последовательности пробелов в начале каждой строки на последовательности символов TAB ('\t'). Количество пробелов, соответствующих одному TAB (ширину TAB), передавать параметром. Если последовательность пробелов в начале строки содержит число пробелов, не делящееся нацело на заданную ширину TAB, то оставлять после TAB’ов “лишние” пробелы.
“Раскомментировать” строки. Комментарий начинается с заданного символа и продолжается до конца строки. Удалить первый такой символ (после возможно пустой последовательности пробельных символов) в каждой строке.
Пример
Пусть даны символ ';', открывающий комментарий, и входной массив вида:
{
";; only a comment here",
"; a = 10 ; commented code here",
"b = 20 ; code and comment",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
"; only a comment here",
" a = 10 ; commented code here",
"b = 20 ; code and comment",
nullptr
};“Закомментировать” заданное число строк. Комментарий начинается с заданного символа и продолжается до конца строки. Вставить такой символ в начало каждой строки.
Пример
Пусть даны символ ';', открывающий комментарий, и входной массив вида:
{
"; only a comment here",
" a = 10 ; commented code here",
"b = 20 ; code and comment",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
";; only a comment here",
"; a = 10 ; commented code here",
";b = 20 ; code and comment",
nullptr
};Пусть исходный набор строк можно условно представить в виде следующих друг за другом блоков (A и X — некоторые последовательности строк):
A
X
Aт.е. блок A повторяется в конце набора. При этом A — максимальный по размеру такой блок.
Требуется удалить финальный блок A. Результирующий набор строк должен иметь вид:
A
XУдалить из набора подряд идущие дубликаты строк (т.е. из идущих подряд повторяющихся строк оставлять только первую).
Если префикс строки в массиве совпадает с заданной строкой — удалить его из этой строки.
Пример
Пусть дан префикс "gl" и массив:
{
"glCreateShader",
"glShaderSource",
"glCompileShader",
"glCreateProgram",
"glAttachShader",
"glLinkProgram",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
"CreateShader",
"ShaderSource",
"CompileShader",
"CreateProgram",
"AttachShader",
"LinkProgram",
nullptr
};Если с заданной строкой совпадает суффикс строки — удалить эту строку из массива (удалять “на месте”, т.е. изменять исходный массив).
Пример
Пусть дана строка "A" и массив:
{
"CreateWindow",
"CreateWindowA",
"CreateWindowEx",
"CreateWindowExA",
"A",
"W",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
"CreateWindow",
"CreateWindowEx",
"W",
nullptr
};Разбить массив на два массива строк: лексикографически меньших заданной строки и прочих.
Пример
Пусть дана строка “e” и массив:
{
"alpha",
"beta",
"gamma",
"epsilon",
"zeta",
"aleph",
"beth",
"resh",
nullptr
};Результирующие массивы:
{
"alpha",
"beta",
"gamma",
"aleph",
"beth",
nullptr
};
{
"epsilon",
"zeta",
"resh",
nullptr
};Удалить из массива все строки, являющиеся n-кратным повторением заданной строки, включая пустые строки (т.е. возможен случай n = 0). Строки удалять “на месте”, т.е. не создавать новый массив.
Пусть дана строка “re”, n = 2, и массив:
{
"re",
"rere",
"rerere",
"abc",
"lax",
"relax",
"rerelax",
"rere",
nullptr
};Результирующий массив должен быть равен следующему массиву:
{
"re",
"rerere",
"abc",
"lax",
"relax",
"rerelax",
nullptr
};Найти первое вхождение заданного слова в тексте, представленном массивом строк, при условии, что слово может быть разбито переносом (знаком -, завершающим строку) в любой позиции (остаток переносится на следующую строку). Вхождение определяется как пара чисел: индекс строки в массиве и индекс первого символа слова в строке.
Кувшинов Д.Р. © 2015