lab10_11 (Готовые ЛР и ДЗ (ИУ5))

Лабораторная работа 10

Обработка символьных строк

Задание.

Провести кодирование и декодирование текста (массива символов) при помощи кода Цезаря¹ с переменным сдвигом по таблице ASCII-кодов. Величина сдвига для каждой позиции в исходном тексте - сумма (по модулю 256) кодов символов слова кодового блокнота, стоящего в блокноте на той же позиции. Если кодовый блокнот имеет слов меньше, чем количество символов в исходном тексте, то по исчерпании слов в нём перейти к первому слову и продолжить. (На основе кодового блокнота целесообразно сначала сформировать по заданному правилу целочисленный массив ключей, который затем использовать при кодировании. Эти действия оформить в виде отдельной функции.)

Исследовать повторяемость символов в закодированном тексте (сколько каких кодов одного и того же исходного символа получено) в зависимости от кодового блокнота и длины исходного текста. Результаты исследования представить в виде таблицы (продумать формат таблицы). Исследование и вывод таблицы результатов следует выполнять в режиме диалога, последовательно вычисляя и выводя результаты для запрашиваемого символа. Статистические данные хранить в массиве int stat[256], Для большей достоверности статистических результатов в качестве исходного текста и кодового блокнота использовать текстовые файлы размером около 1 Кбайта.

Пример программы работы с символьными строками.

!!! Перед выполнением работы выполните приведенный ниже пример программы работы с символьными строками. Особое внимание обратите на используемую последовательность шагов разработки программы и на применение библиотечных функций. Затраты времени на изучение функций библиотеки языка программирования, имеющих отношение к решаемой задаче, окупятся при разработке программы.

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

Определим слово как последовательность алфавитно-цифровых символов, после которых следует знак пунктуации, разделитель или признак конца строки. Слово может находиться либо в начале строки, либо после разделителя или знака пунк­туации. Это можно записать следующим образом (фигурные скобки и вертикаль­ная черта означают выбор из альтернатив):

слово = {начало строки | знак пунктуации | разделитель} символы, составляющие слово
{конец строки | знак пунктуации | разделитель}

I. Исходные данные и результаты

Исходные данные:

1. Текстовый файл неизвестного размера, состоящий из строк длиной не более 80 символов. Поскольку по условию переносы отсутствуют, можно ограни­читься поиском слова в каждой строке отдельно. Для ее хранения выделим строку длиной 81 символ.

2. Слово для поиска, вводимое с клавиатуры. Для его хранения также выделим строку длиной 81 символ.

Результатом работы программы является количество вхождений слова в текст. Представим его в программе в виде целой переменной.

Для хранения длины строки будем использовать именованную константу, а для хранения фактического количества символов в слове — переменную целого типа. Для работы с файлом потребуется служебная переменная соответствующего типа.

II. Алгоритм решения задачи

- Построчно считывать текст из файла.
- Просматривая каждую строку, искать в ней заданное слово. При каждом
нахождении слова увеличивать счетчик.

Детализируем второй пункт алгоритма. Очевидно, что слово может встречаться в строке многократно, поэтому для поиска следует организовать цикл просмотра строки, который будет работать, пока происходит обнаружение в строке последо­вательности символов, составляющих слово.

При обнаружении совпадения с символами, составляющими слово, требуется определить, является ли оно отдельным словом, а не частью другого. (Это один из возможных вариантов решения задачи, не самый лучший. Другой вариант – сначала выделить слово, а затем сравнивать его с заданным). Например, мы задали слово «кот». Эта последовательность символов содержится, например, в словах «котенок», «трикотаж», «трескотня» и «апперкот». Следовательно, требуется проверить символ, стоящий после слова, а в случае, когда слово не находится в начале строки — еще и символ перед словом. Эти символы проверяются на принадлежность множеству знаков пунктуации и разделителей.

III. Программа и тестовые примеры

Разобьем написание программы на последовательность шагов.

Шаг 1. Ввести «скелет» программы (директивы #include, функцию main(), описа­ние переменных, открытие файла). Добавить контрольный вывод введенного сло­ва. Запустив программу, проверить ввод слова и успешность открытия файла. Для проверки вывода сообщения об ошибке следует выполнить программу еще раз, задав имя несуществующего файла.

#include <fstream.h>

int main()

{

const int len = 81;

char word[len],line[len];

cout << " Input the word for search: ";

cin >> word;

ifstream fin("text.txt",ios::in);

if (!fin) { cout << "Error of file opening."<< endl;

return 1; }

return 0;

}

Шаг 2. Добавить в программу цикл чтения из файла, внутри цикла поставить кон­трольный вывод считанной строки:

#include <fstream.h>

int main()

{

const int len = 81;

char word[len], line[len];

cout << "Input the word for search: ";

cin >> word;

ifstream fin("text.txt", ios::in);

if (!fin) { cout << "Error of file opening."<< endl;

return 1;}

while (fin.getline(line, len))

cout << line << endl;

return 0;

}

Шаг З. Добавить в программу цикл поиска последовательности символов, состав­ляющих слово, с контрольным выводом:

#include <fstream.h>

#include <string.h>

int main()

{

const int len = 81;

char word[len], line[len];

cout << "Input the word for search: ";

cin >>word;

int l_word = strlen(word);

ifstream fin("text.txt", ios::in);

if (!fin) { cout << "Error of file opening."<< endl;

return 1;

}

int count =0;

while (fin.getline(line, len)) {

char *p = line;

while( p = strstr(p, word)) {

cout << “coincidence: " << p << endl;

p += l_word;

count++;

}

}

cout << count << endl;

return 0;

}

Для многократного поиска вхождения подстроки в заголовке цикла используется функция strstr. Очередной поиск должен выполняться с позиции, следующей за найденной на предыдущем проходе подстрокой. Для хранения этой позиции определяется вспомогательный указатель р, который на каждой итерации цикла наращивается на длину подстроки. Также вводится счетчик количества совпадений. На данном этапе он считает не количество слов, а количество вхождений последовательности символов, составляющих слово.

Шаг 4. Добавить в программу анализ принадлежности символов, находящихся перед словом и после него, множеству знаков пунктуации и разделителей:

#include <fstream.h>

#include <string.h>

#include <ctype.h>

int main()

{

const int len = 81;

char word[len], line[len];

cout << "Input the word for search: ";

cin >>word;

int l_word = strlen(word);

ifstream fin("text.txt", ios::in);

if (!fin) { cout << "Error of file opening."<< endl;

return 1;

}

int count =0;

while (fin.getline(line, len)) {

char *p = line;

while( p = strstr(p, word)) {

char *c = p; //с-начало подстроки совпадения

p += l_word; //р-конец подстроки совпадения

// подстрока не в начале строки?

if (c != line)

// символ перед подстрокой совпадения не разделитель?

if ( !ispunct(*(c - 1) ) && !isspace(*(c - 1) )) continue;

// символ после слова разделитель?

if ( ispunct(*p) || isspace(*p) || (*p == '\0') ) count++; //подстрока – отдельное слово

}

}

cout << "Number of entering word: "<< count << endl;

return 0;

}

Здесь вводится служебная переменная c для хранения адреса начала вхождения подстроки. Символы, ограничивающие слово, проверяются с помощью функций ispunct и isspace, прототипы которых хранятся в заголовочном файле <ctype.h>. Символ, стоящий после слова, проверяется также на признак конца строки (для случая, когда искомое слово находится в конце строки).

Для тестирования программы требуется создать файл с текстом, в котором задан­ное слово встречается:

• в начале строки;

• в конце строки;

• в середине строки;

• несколько раз в одной строке;

• как часть других слов, находящаяся в начале, середине и конце этих слов;

• в скобках, кавычках и других разделителях.

Длина хотя бы одной из строк должна быть равна 80 символам. Для тестирования программы следует выполнить ее по крайней мере два раза: введя с клавиатуры слово, содержащееся в файле, и слово, которого в нем нет.

Давайте теперь рассмотрим другой вариант решения этой задачи. В библиотеке есть функция strtok, которая разбивает переданную ей строку на лексемы в соот­ветствии с заданным набором разделителей. Если мы воспользуемся этой функ­цией, нам не придется «вручную» выделять и проверять начало и конец слова, потребуется лишь сравнить с искомым словом слово, выделенное с помощью strtok. Правда, список разделителей придется задать вручную:

#include <fstream.h>

#include <string.h>

int main()

{

const int len = 81;

char word[len], line[len];

char *delims = ".,!? /<>|)(*::\"";

cout << "Input the word for search: "; cin >> word;

ifstream fin("text.txt", ios::in);

if (!fin) { cout << "Error of file opening."<< endl;

return 1; }

char *token;

int count = 0;

while (fin.getline(line, len)) {

token = strtok( line, delims ); // 1

while( token != NULL ) {

if ( !strcmp (token, word) ) count++; // 2

token = strtok( NULL, delims ); // 3

}

}

cout << "Number of entering word: "<<count << endl;

return 0;

}

Первый вызов функции strtok в операторе 1 формирует адрес первой лексемы (сло­ва) строки line. Он сохраняется в переменной token. Функция strtok заменяет на NULL разделитель, находящийся после найденного слова, поэтому в операторе 2 можно сравнить на равенство искомое и выделенное слово. В операторе 3 выпол­няется поиск следующей лексемы в той же строке. Для этого следует задать в функ­ции strtok в качестве первого параметра NULL (так запрограммирована функция).

Как видите, программа стала короче и яснее. На этом примере можно видеть, что средства, предоставляемые языком, влияют на алгоритм решения задачи, и поэто­му перед тем, как продумывать алгоритм, необходимо эти средства изучить. Пред­ставьте, во что бы вылилась программа без использования функций работы со стро­ками и символами!

1 Цезарь для шифрования своих посланий использовал следующий прием. При кодировании и декодировании писем он заменял буквы в письме на следующие по алфавиту буквы с постоянным смещением, равным 13, то есть к порядковому номеру буквы в латинском алфавите, содержащим 26 букв, он прибавлял 13 и получал порядковый номер буквы в кодируемом (декодируемом) письме. Если полученный таким образом номер буквы был больше 26, то он уменьшался на 26.