Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн
Шрифт:

18.6. Примеры: палиндром

Довольно технических примеров! Попробуем решить маленькую головоломку. Палиндром (palindrome) — это слово, которое одинаково читается как слева направо так и справа налево. Например, слова anna, petep и malayalam являются палиндромами, а слова ida и homesick — нет. Есть два основных способа определить, является ли слово палиндромом.

• Создать копию букв, расположенных в противоположном порядке, и сравнить ее с оригиналом.

• Проверить, совпадает ли первая буква с последней, вторая — с предпоследней, и так далее до середины.

Мы выбираем второй подход. Существует много способов выразить эту идею в коде. Они зависят от представления слова и от способа отслеживания букв в слове. Мы напишем небольшую программу, которая будет по-разному проверять, является ли слово палиндромом. Это просто позволит нам выяснить, как разные особенности языка программирования влияют на внешний вид и работу программы.

18.6.1. Палиндромы, созданные с помощью класса string

Прежде всего напишем вариант программы, используя стандартный класс

string
, в котором индексы сравниваемых букв задаются переменной типа
int
.

bool is_palindrome(const string& s)

{

int first = 0; // индекс первой буквы

int last = s.length–1; // индекс последней буквы

while (first < last) { // мы еще не достигли середины слова

if (s[first]!=s[last]) return false;

++first; // вперед

––last; // назад

}

return true;

}

Мы возвращаем значение true, если достигли середины слова, не обнаружив разницы между буквами. Предлагаем вам просмотреть этот код и самим убедиться, что он работает правильно, когда в строке вообще нет букв, когда строка состоит только из одной буквы, когда в строке содержится четное количество букв и когда в строке содержится нечетное количество букв. Разумеется, мы не должны полагаться только на логику, стараясь убедиться, что программа работает правильно. Попробуем выполнить функцию

is_palindrome
.

int main

{

string s;

while (cin>>s) {

cout << s << " is";

if (!is_palindrome(s)) cout << " not";

cout << " a palindrome\n";

}

}

По существу, причина, по которой мы используем класс

string
, заключается в том, что объекты класса
string
хорошо работают со словами. Они достаточно просто считывают слова, разделенные пробелами, и знают свой размер. Если бы мы хотели применить функцию
is_palindrome
к строкам, содержащим пробелы, то просто считывали бы их с помощью функции
getline
(см. раздел 11.5). Это можно было бы продемонстрировать на примере строк ah ha и as df fd sa.

18.6.2. Палиндромы, созданные с помощью массива

А если бы у нас не было класса

string
(или
vector
) и нам пришлось бы хранить символы в массиве? Посмотрим.

bool is_palindrome(const char s[], int n)

// указатель s ссылается на первый символ массива из n символов

{

int first = 0; // индекс первой буквы

int last = n–1; // индекс последней буквы

while (first < last) { // мы еще не достигли середины слова

if (s[first]!=s[last]) return false;

++first; // вперед

––last; // назад

}

return true;

}

Для того чтобы выполнить функцию

is_palindrome
, сначала необходимо записать символы в массив. Один из безопасных способов (без риска переполнения массива) выглядит так:

istream& read_word(istream& is, char* buffer, int max)

// считывает не более max–1 символов в массив buffer

{

is.width(max); // при выполнении следующего оператора >>

// будет считано не более max–1 символов

is >> buffer; // читаем слово, разделенное пробелами,

// добавляем нуль после последнего символа

return is;