7.1. Методические указания
7.1.1. Необходимое вступление
Для решения задач по обработке символьных строк необходимо использовать массив символов, т. к. встроенного типа для строк у С/С++ нет. Альтернативой в С++ является использование класса string библиотеки стандартных шаблонов STL, но это выходит за рамки данного руководства.
Массив символов можно объявить с запасом, чтобы обрабатываемая строка с гарантией в нем поместилась:
charstr[256]; // Строка не более 255 символов
Не стоит забывать, что после последнего символа введенной с консоли строки автоматически добавляется символ с кодом 0, что позволяет организовывать циклы по строке вида:
for (int i=0; str[i]!=0; i++) { … }
Если строка формируется программой, то необходимо предусмотреть добавление нулевого символа в ее конец.
Для ввода строки можно использовать стандартную функцию scanf():
scanf(“%s”, &str[0]); // Или короче: scanf(“%s”, str);
Но необходимо помнить, что для scanf() пробел внутри строки является признаком ее завершения, поэтому для ввода строк с пробелами используется другая функция:
gets(str);
7.1.2. Пример решения простой задачи
Задача 1: Дана строка. Определить количество строчных латинских и русских букв.
Для решения данной задачи полезно помнить, что тип char является по сути свой целочисленным, т. е. в памяти ЭВМ хранятся и обрабатываются коды символов. Для решения задач такого типа обычно достаточно одного цикла по строке, в котором и находятся все требуемые величины.
Определение принадлежности любого символа заданной группе символов удобно выполнять с помощью отдельной функции isLetter(). В данном примере эта функция используется два раза для каждого символа: проверяется, является ли он строчной английской буквой или строчной русской соответственно. Множества символов, принадлежность к которым нужно определить, задаются в главной функции и передаются функции isLetter() через параметры.
Текст программы:
#include<stdio. h>
#include<locale. h>
// Функция проверки: принадлежит ли указанный символ заданному алфавиту
bool isLetter(char c, char abc[])
{
for(int i=0; abc[i]!=0; i++) // Цикл по строке с алфавитом
{
if(abc[i] == c)
return true; // Символ найден
}
return false; // Символ не найден
}
int _tmain(int argc, _TCHAR* argv[])
{
// Задаем алфавиты для русских и английских букв
char smallEnglish[] = "qwertyuioplkjhgfdsazxcvbnm";
char smallRussian[] = "йцукенгшщзхъэждлоррпавыфячсмитьбю";
char str[256]; // Буфер для вода строки
int n_str_lat = 0; // Количество строчных латинских
int n_str_rus = 0; // Количество строчных русских
setlocale(LC_CTYPE, "Russian"); // Для ввода-вывода русских букв
printf("Input string:\n"); // Ввод исходной строки
scanf("%s", str);
for(int i=0; str[i]!=0; i++) // Цикл по всем ее символам
{
if(isLetter(str[i], smallEnglish)) // Проверка русских
n_str_lat++;
else
if(isLetter(str[i], smallRussian)) // Проверка латинских
n_str_rus++;
}
// Печать результата работы
printf("n_str_lat = %d, n_str_rus = %d \n", n_str_lat, n_str_rus);
return 0;
}
7.1.3. Пример решения задачи средней сложности
Задача 2: Из имеющегося словаря выбрать наиболее длинное слово, в котором все буквы разные.
Нужно определиться, что собой представляет словарь. Будем считать, что словарь – это последовательность слов, каждое из которых представляет собой массив символов. Так как слова не нужно сравнивать друг с другом, то они могут обрабатываться последовательно, то есть достаточно одного символьного массива на весь словарь.
Для определения, разные буквы в слове или нет будем использовать массив размером с количество букв (для латинских букв – 26). Нулевой элемент массива соответствует букве ‘a’, первый – ‘b’ и т. д. Значение элемента массива равно 1, если такая буква в слове есть и 0 – если нет.
Текст программы:
const int n_char = 26; // Количество букв в алфавите
const int max_len = 128; // Максимальная длина слова
int _tmain(int argc, _TCHAR* argv[])
{
int n_words; // Число слов в словаре
char word[max_len]; // Буфер для ввода слова
char max_word[max_len]; // Наиболее длинное слово с разными буквами
int m[n_char]; // Массив для проверки букв
int max_dl = 0; // Максимальная длина слова
printf("n_words=");
scanf("%d", &n_words); // Ввод количества слов
for(int i=0; i<n_words; i++) // Цикл по словам
{
scanf("%s", word); // Ввод проверяемого слова
// Зануление массива, используемого для проверки повтора букв
for(int j=0; j<n_char; j++) m[j]=0;
int different = 0; // Считаем все буквы разными
int j;
for(j=0; word[j]!=0; j++)
{
int index = word[j]-'a'; // Индекс буквы в массиве
if(m[index] == 0)
m[index] = 1; // Если буквы не было – теперь есть
else
different = 1; // Буква была – они не все разные
}
if(different == 0) // Если одинаковых букв нет
{
if(j>max_dl) // Длина текущего слова больше максимума
{
max_dl = j;
// копируем слово в другую строку вместе с нулем
for(int k=0; k<=j; k++) max_word[k] = word[k];
}
}
}
// Печать результата при наличии искомых слов и при их отсутствии
if(max_dl > 0)
printf("Word is: %s\n", max_word);
else
printf("No Word Found!\n");
return 0;
}
7.1.4. Пример решения задачи повышенной сложности
Задача 3: В имеющемся словаре найти слова, которые могут быть полностью составлены из других слов с помощью конкатенации. Например, «БАЛКОН» = «БАЛ» + «КОН»
Текст программы:
const int max_len = 128; // Максимальная длина слова
const int max_words = 128; // Максимальная длина словаря
int length(char* word)
{
// Определение длины слова
int len=0;
while(word[len]!=0) len++;
return len;
}
void AddWord(int i, char** slovar, char* word)
{
int len=length(word);
// Добавление слова в словарь
slovar[i] = new char[len+1];
for(int j=0; j<=len; j++) slovar[i][j] = word[j];
}
void copy(char buf[], char *word)
{
// Копирование строки в другую
int i=0;
while(word[i]!=0) { buf[i]=word[i]; i++; }
buf[i] = 0; // Добавление в конец строки символа 0
}
void concat(char buf[], char *word)
{
// Сцепление двух строк
int len=length(buf);
copy(buf+len, word);
}
bool equal(char* s1, char* s2)
{
// Сравнение двух строк
int i=0;
while(s1[i]!=0)
{
if(s1[i] != s2[i]) return false; // Разные символы
i++;
}
if(s2[i] != 0)
return false; // Строка закончилась раньше другой
else
retur ntrue; // Строки совпадают
}
bool test_equal(char* si, char* sj, char* sk)
{
// Проверка возможности составления одной строки из двух других
if(length(si) == length(sj)+length(sk)) // Проверка длины строк
{
char buf[max_len*2]; // Буфер для слияния двух строк
copy(buf, sj);
concat(buf, sk); // Копируем первую и добавляем вторую
if(equal(si, buf)) // Проверка совпадения
{
// Печеть результата
printf("%s = %s + %s\n", si, sj, sk);
return true;
}
return false; // Не совпали по буквам
}
else
return false; // Не совпали по длине
}
bool test_words(char** slovar, int n_words)
{
// Проверка всех комбинаций слов из словаря
bool found = false;
for(int i=0; i<n_words; i++) // Цикл по первому слову
{
for(int j=0; j<n_words; j++) // Цикл по второму слову
{
if(j==i) continue; // Не сравнивать само с собой
for(int k=j+1; k<n_words; k++) // Цикл по третьему слову
{
// Не сравнивать само с собой
if(k==i) continue;
// Сравниваем: первое = второе + третье
found |= test_equal(slovar[i], slovar[j], slovar[k]);
// Сравниваем: первое = третье + второе
found |= test_equal(slovar[i], slovar[k], slovar[j]);
}
}
}
return found; // Возвращаем результат сравнения
}
void free_mem(char** slovar, int n_words)
{
// Удаление словаря из памяти
for(int i=0; i<n_words; i++)
delete [] slovar[i];
delete slovar;
}
int _tmain(int argc, _TCHAR* argv[])
{
int n_words; // Количество слов в словаре
char word[max_len]; // Буфер для ввода слова
char** slovar = new char*[max_words]; // Словарь
printf("n_words="); // Ввод количества слов
scanf("%d", &n_words);
// Создание словаря
for(int i=0; i<n_words; i++)
{
scanf("%s", word); // Ввод слова
AddWord(i, slovar, word); // Добавление в словарь
}
// Сама проверка
bool ok = test_words(slovar, n_words); // Если есть слова - печатаем
if(!ok)
printf("No Words Found!\n"); // Таких слов не было
// Освобождение памяти
free_mem(slovar, n_words);
return 0;
}
7.2. Задачи для самостоятельного решения
7.2.1. Простые задачи
Написать функцию (и тестирующую функцию main), которая:
Дана строка. Определить количество содержащихся в ней цифр. Дана строка. Определить количество содержащихся в ней прописных латинских букв. Дано натуральное число. Перевести число в строку без использования стандартных функций языка. Дана строка, содержащая натуральное число. Вывести сумму цифр этого числа. Задана строка, изображающая двоичную запись натурального числа. Вывести десятичную запись этого же числа. Дана строка, изображающая арифметическое выражение вида <цифра> ± <цифра> ± <цифра> ±…± <цифра>, где на месте «±» стоит знак сложения «+» или вычитания «-» (например, 4+7-2-8). Вывести значение данного выражения. Дан символ C и строка S. Удвоить каждое вхождение символа C в строку S. Дан символ C и строки S, S0. После каждого вхождения символа C в строку Sвставить строку S0. Даны строки S и S0. Удалить из строки Sпоследнюю подстроку, совпадающую с S0. Если совпадающих подстрок нет, то выдать исходную строку без изменений.7.2.2. Задачи средней сложности
Написать функцию (и тестирующую функцию main), которая:
Текст записан одной длинной строкой. Признаком красной строки служит символ $. Переформатировать текст в 60-символьные строки, формируя абзацы. Дана строка. Преобразовать в ней все прописные буквы в строчные. Текст записан одной длинной строкой. В заданном тексте найти самое длинное слово. Текст записан одной длинной строкой. Подсчитать частоту встречаемости каждого слова в тексте. Имеется большой словарь русских слов. Найти в нем слова-палиндромы, которые читаются одинаково как слева направо, так и справа налево. Например, АННА, ШАЛАШ и т. д. В имеющемся словаре найти группы слов, записанные одними и теми же буквами и отличающиеся только их порядком, т. е. одно из другого может получено посредством перестановки букв (например, КОРМА, КОМАР). В имеющемся словаре найти пары слов (анаграммы), при прочтении каждого из которых в обратном направлении образуется другое слово пары, например, (ПОЛК, КЛОП), (БАР, РАБ). Для заданного достаточно длинного слова найти в имеющемся словаре все слова, в которых использованы только буквы, имеющиеся в заданном слове (с учетом кратности вхождения). Задан набор ключевых слов, а также текст, в котором хранится длинный список названий книг и научных работ. Выбрать названия, содержащие хотя бы одно из заданных ключевых слов. Дана строка, состоящая из русских слов, набранных заглавными буквами и разделенных пробелами (одним или несколькими). Найти количество слов, содержащих букву «А».7.2.3. Задачи повышенной сложности
Написать функцию (и тестирующую функцию main), которая:
