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;
}
Правильная установка ширины потока istream предотвращает переполнение массива при выполнении следующего оператора >>. К сожалению, это также означает, что нам неизвестно, завершается ли чтение пробелом или буфер полон (поэтому нам придется продолжить чтение). Кроме того, кто помнит особенности поведения функции width() при вводе? Стандартные классы string и vector на самом деле лучше, чем буферный ввод, поскольку они могут регулировать размер буфера при вводе. Завершающий символ 0 необходим, так как большинство операций над массивами символов (строка в стиле языка C) предполагают, что массив завершается нулем. Используя функцию read_word(), можно написать следующий код:
int main()
{
const int max = 128;
char s[max];
while (read_word(cin,s,max)) {
cout << s << " is";
if (!is_palindrome(s,strlen(s))) cout << " not";
cout << " a palindromen";
}
}
Вызов strlen(s) возвращает количество символов в массиве после выполнения вызова read_word(), а инструкция cout<<s выводит символы из массива, завершающегося нулем.
Решение задачи с помощью класса string намного аккуратнее, чем с помощью массивов. Это проявляется намного ярче, когда приходится работать с длинными строками (см. упр. 10).
18.6.3. Палиндромы, созданные с помощью указателей
Вместо использования индексов для идентификации символов можно было бы применить указатели.
bool is_palindrome(const char* first, const char* last)
// указатель first ссылается на первую букву
// указатель last ссылается на последнюю букву
{
while (first < last) { // мы еще не достигли середины
if (*first!=*last) return false;
++first; // вперед
––last; // назад
}
return true;
}
Отметим, что указатели можно инкрементировать и декрементировать. Инкрементация устанавливает указатель на следующий элемент массива, а декрементация — на предыдущий. Если в массиве нет следующего или предыдущего элемента, возникнет серьезная ошибка, связанная с выходом за пределы допустимого диапазона. Это еще одна проблема, порожденная указателями.
Функция is_palindrome() вызывается следующим образом:
int main()
{
const int max = 128;
char s[max];
while (read_word(cin,s,max)) {
cout << s << " is";
if (!is_palindrome(&s[0],&s[strlen(s)–1])) cout << " not";
cout << " a palindromen";
}
}
Просто забавы ради мы переписали функцию is_palindrome() следующим образом:
bool is_palindrome(const char* first, const char* last)
// указатель first ссылается на первую букву
// указатель last ссылается на последнюю букву
{
if (first<last) {
if (*first!=*last) return false;
return is_palindrome(first+1,last-1);
}
return true;
}
Этот код становится очевидным, если перефразировать определение палиндрома: слово является палиндромом, если его первый и последний символы совпадают и если подстрока, возникающая после отбрасывания первого и последнего символов, также является палиндромом.
Задание
В этой главе мы ставим два задания: одно необходимо выполнить с помощью массивов, а второе — с помощью векторов. Выполните оба задания и сравните количество усилий, которые вы при этом затратили.
Задание с массивами
1. Определите глобальный массив ga типа int, состоящий из десяти целых чисел и инициализированный числами 1, 2, 4, 8, 16 и т.д.
2. Определите функцию f(), принимающую в качестве аргументов массив типа int и переменную типа int, задающую количество элементов в массиве.
3. В функции f() выполните следующее.
3.1. Определите локальный массив la типа int, состоящий из десяти элементов.
3.2. Скопируйте значения из массива ga в массив la.
3.3. Выведите на печать элементы массива la.
3.4. Определите указатель p, ссылающийся на переменную типа int, и инициализируйте его адресом массива, расположенного в свободной памяти и хранящего такое же количество элементов, как и массив, являющийся аргументов функции.
3.5. Скопируйте значения из массива, являющегося аргументом функции, в массив, расположенный в свободной памяти.
3.6. Выведите на печать элементы массива, расположенного в свободной памяти.
3.7. Удалите массив из свободной памяти.
4. В функции main() сделайте следующее.
4.1. Вызовите функцию f() с аргументом ga.
4.2. Определите массив aa, содержащий десять элементов, и инициализируйте его первыми десятью значениями факториала (т.е. 1, 2*1, 3*2*1, 4*3*2*1 и т.д.).
4.3. Вызовите функцию f() с аргументом aa.
Задание со стандартным вектором
1. Определите глобальный вектор vector<int> gv; инициализируйте его десятью целыми числами 1, 2, 4, 8, 16 и т.д.
2. Определите функцию f(), принимающую аргумент типа vector<int>.
3. В функции f() сделайте следующее.
3.1. Определите локальный вектор vector<int> lv с тем же количеством элементов, что и вектор, являющийся аргументом функции.
3.2. Скопируйте значения из вектора gv в вектор lv.
3.3. Выведите на печать элементы вектора lv.
3.4. Определите локальный вектор vector<int> lv2; инициализируйте его копией вектора, являющегося аргументом функции.
3.5. Выведите на печать элементы вектора lv2.
4. В функции main() сделайте следующее.
4.1. Вызовите функцию f() с аргументом gv.
4.2. Определите вектор vector<int> vv и инициализируйте его первыми десятью значениями факториала (1, 2*1, 3*2*1, 4*3*2*1 и т.д.).
4.3. Вызовите функцию f() с аргументом vv.
Контрольные вопросы
1. Что означает