Форум » C/C++ для начинающих (C/C++ for beginners) » Задача: создать символьный массив, не содержащий дублирующихся смежных символов исходной строки » Ответить
Задача: создать символьный массив, не содержащий дублирующихся смежных символов исходной строки
Сыроежка: Допустим, есть некоторая строка [pre2] const char *pass = "Qqqqqqqwwwww11111"; [/pre2] Требуется создать символьный массив, который будет содержать символы этой исходный строки без повторяющихся смежных символов, то есть результирующий массив должен быть строкой вида "Qqw1". Задачу можно разбить на две более простые задачи. Первая - нужно подсчитать, сколько в исходной строке неповторяющихся символов, чтобы знать, какой размер памяти нужно выделить под результирующий массив. Вторая - нужно скопировать исходную строку в результирующий массив, исключая повторяющиеся смежные символы. Обе эти задачи можно сделать с помощью стандартных алгоритмов С++., причем наибольший интерес представляет неочевидное использование алгоритма std::inner_product. Итак, как подсчитать число неповторяющихся символов? Для этого нужно сравнить каждый текущий символ строки с ее последующим символом, и если они не равны, то увеличить счетчик. Если строка содержит всего лишь один символ (будем считать, что пустая строка содержит один символ - символ завершающего нуля '\0'), то сравнивать этот символ с последующим символом не представляется возможным в виду отсутствия такового. Значит для пустой строки, то есть строки содержащей всего один символ, символ завершающего нуля, количество неповторяющихся символов будет равно 1. То есть это сам символ завершающего нуля '\0'. Если же строка не пустая, то для этой цели очень удобно использовать стандартный алгоритм std::inner_product. Вот как будет выглядеть код для этой подзадачи: [pre2] const char *pass = "Qqqqqqqwwwww11111"; size_t n = 1 + std::strlen( pass ); size_t count = 1 + std::inner_product( pass + 1, pass + n, pass, 0u, std::plus<size_t>(), std::not_equal_to<const char>() ); [/pre2] Чтобы этот код работал, нужно в программу включить следующие заголовочные файлы: [pre2] #include <cstring> #include <numeric> #include <functional> [/pre2] Идея состоит в том, что исходная строка сравнивается сама с собой посимвольно, как будто бы сравниваются две отдельные строки. Для этого начальный итератор "первой отдельной" строки сдвинут на одну позицию вперед: pass + 1, тогда как позиция "второй отдельной" строки совпадает с первой позицией исходной строки. Первый функционал алгоритма суммируют несовпадающие символы: std::plus<size_t>(). Второй функционал алгоритма, std::not_equal_to<const char>(), возвращает значение true, которое преобразуется в целочисленную единицу., если сравниваемые символы не равны друг другу. Как можно видеть, получилась достаточно компактная и выразительная запись без использования вручную написанных циклов. Обратите внимание, что завершающий ноль, '\0', также участвует в сравнении символов. Для этого к длине исходной строки была добавлена единица: [pre2] size_t n = 1 + std::strlen( pass ); [/pre2] Все, что теперь осталось сделать - это динамически создать результирующий массив и скопировать в него неповторяющиеся символы исходной строки. Размер создаваемого массива нам известен и равен значению переменной count. Чтобы скопировать неповторяющиеся символы, нужно задействовать второй стандартный алгоритм std::unique_copy: [pre2] char *a = new char[count]; std::unique_copy( pass, pass + n, a ); [/pre2] Дополнительно в код программы нужно будет включить заголовочный файл [pre2] #include <algorithm> [/pre2] Эта задача примечательна неочевидным использованием алгоритма std::inner_product. Этот прием исользования std::inner_product полезно включить в свой арсенал технических приемов. С данным моим решением вместе с другими подходами к решению задачи можно ознакомиться на сайте www.stackoverflow.com по ссылке http://stackoverflow.com/questions/19754090/creating-an-array-without-duplicates/19754631#19754631
Ответов - 1
Сыроежка: Если требуется удалить дублирующиеся символы "на месте", то есть не создавая новой строки, то это можно сделать без затей следующим образом [pre2] char * unique( char *s ) { for ( char *p = s, *q = s; *q++; ) { if ( *p != *q && ++p != q ) *p = *q; } return s; } [/pre2] Эта функция хороша тем, что она может использоваться как в C++ так и в C. Ниже приведена демонстрационная программа, написанная на C [pre2] #include <stdio.h> char * unique( char *s ) { for ( char *p = s, *q = s; *q++; ) { if ( *p != *q && ++p != q ) *p = *q; } return s; } int main(void) { char s[] = "aabbaa"; puts( unique( s ) ); return 0; } [/pre2] Вывод программы [pre2] aba [/pre2] Эта изящная реализация функции вполне подойдет для любого случая применения функции. Однако если вы стремитесь использовать максимально оптимизированный код, то эту функцию можно усовершенствовать. Заметим, что при каждой итерации цикла в функции проверяются два условия [pre2] if ( *p != *q && ++p != q ) *p = *q; [/pre2] Если в строке нет повторяющихся символов, то второе условие ++p != q излишнее, так как мы не собираемся копировать символы. Аналогично если в строке уже встретился повторяющийся символ, то в случае если *p != *q, то всегда будет выполняться условие ++p != q. Переписав соответствующим образом функцию, мы можем избежать проверки этих двух условий одновременно при каждой итерации цикла. Вот как будет выглядеть более оптимизированная функция: [pre2] char * unique( char *s ) { char *p = s, *q = s; while ( *q && *p != *++q ) ++p; while ( *q ) { if ( *p != *++q ) *++p = *q; } return s; } [/pre2] Другие подходы к реализации подобной функции можно посмотреть на www.stackoverflow.com Правда на мой взгляд все остальные решения, представленные по этой ссылке, выглядят не профессионально и являются неудачными.
полная версия страницы