Методические указания для практического занятия по курсу "Стандартные функции, структуры данных и алгоритмы системы программирования языка С"


Цель занятия

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

Формулировка задания

Требуется разработать программу PALINDROME, предназначенную для проверки наличия свойства быть алфавитно-цифровым палиндромом у произвольной последовательности символов. Исследуемая последовательность символов должна передаваться программе через набор аргументов командной строки ее вызова. При анализе заданной последовательности необходимо учитывать только символы, которые являются цифрами или буквами, игнорируя различие строчных и заглавных букв. Результаты проверки должен идентифицировать целочисленный код возврата программы PALINDROME, который передается в операционную среду ее вызова. При этом последовательности символов, которая образует палиндром, должен соответствовать код возврата, равный нулю. Если заданная последовательность не является палиндромом, то код возврата программы PALINDROME должен быть отличен от нуля. По умолчанию пустая последовательность считается палиндромом.
Программа должна быть разработана в системе программирования C, с учетом требований современных стандартов ANSI/ISO C, на основе концепций структурного и функционально-ориентированного программирования. Исходный код программы PALINDROME должен допускать трансляцию в любой реализации компилирующей системы программирования C. Выполняемый код программы PALINDROME должен быть ориентирован на эксплуатацию в среде OS UNIX.

Понятие палиндрома

Палиндромом называется симметричная символьная последовательность, которая одинаково читается слева направо и справа налево. Например, слово "radar" является текстовым палиндромом, потому что его составляет симметричная последовательность букв. Символическая запись целого числа 121 образует числовой палиндром, который составлен из расположенных симметрично десятичных цифр.
В более общем случае свойством палиндрома может обладать произвольный текстовый фрагмент, состоящий из нескольких слов и/или чисел, если исключить из него все разделители между словами и числами. Например, текстовый палиндром, который состоит из нескольких слов, образует фраза "Madam, I'm Adam.", если в ней исключить все символы кроме букв и игнорировать различие регистров букв.

Метод проверки палиндрома

Метод проверки палиндрома основан на анализе совпадения симметрично расположенных символов, которые находятся на одинаковом расстоянии от концов или середины заданной последовательности. Если все симметрично расположенные символы заданной последовательности попарно совпадают, то она является палиндромом. Систематичный метод организации этой проверки состоит в том, чтобы сравнить первую половину последовательности с ее второй половиной, где символы перечислены в порядке, обратном исходному. Если обе половины таким образом модифицированной последовательности совпадают, то исходная последовательность образует палиндром. Например, последовательность "deed", преобразуется в последовательность "dede", обе половины которой совпадают, поэтому исходная последовательность "deed" является палиндромом.
Следует отметить, что в общем случае количество символов сравниваемых фрагментов заданной последовательности может отличаться на единицу, если ее длина равна нечетному числу. Поэтому сравнение обеих половин последовательности необходимо производить в диапазоне символов более короткой из них. Например, последовательность "rotor" из пяти символов представляется в виде последовательности "rorot", диапазон сравнения половин которой равен 2, а последний символ t из второй, более длинной половины, не должен учитываться при сравнении. Сравниваемые фрагменты "ro" и "rot" модифицированной последовательности совпадают по первым двум символам, поэтому исходная последовательность образует палиндром.
Для ревесирования последовательностей обычно применяется циклический сдвиг ее элементов. В данном случае, исходя из соображений удобства программной реализации, целесообразно организовать циклический сдвиг влево всех символов реверсируемой половины заданной последовательности. Циклический сдвиг влево это итерационный процесс, на каждой итерации которого все элементы сдвигаемой части перемещаются на 1 позицию влево, а начальный элемент становится последним в текущем диапазоне сдвига. При этом диапазон сдвига на каждой итерации сокращается на единицу, а количество итераций ограничено длиной реверсируемой последовательности. Например, циклический сдвиг влево полупоследовательности символов "vel" при обработке палиндрома "level" выполняется за две итерации, порождая символьные цепочки "elv" и "lev".
В общем случае исходная последовательность может состоять из нескольких алфавитно-цифровых фрагментов, которые разделяют символы, не являющиеся буквами и цифрами. Поэтому для практической реализации рассмотренного метода проверки палиндрома необходимо предусмотреть предварительную обработку заданной последовательности, чтобы получить строку символов, которая состоит только из строчных букв и/или цифр. Например, исходную последовательность "Madam, I'm Adam" следует предварительно превратить в символьную строку "madamimadam" для последующей проверки палиндрома рассмотренным методом.

Общая структура программы

Исходный текст программы PALINDROME целесообразно сосредоточить в одном файле, который должен содержать спецификацию основной функции main и двух локальных функций preparator и comparison, реализующих процедуры предварительной обработки заданной последовательности и непосредственно метод проверки палиндрома.
Кроме спецификации функций исходный текст программы PALINDROME должен содержать декларации прототипов обеих локальных функций, а также директивы подключения заголовочных файлов string.h, stdlib.h и ctype.h системы программирования C, где сосредоточены объявления прототипов стандартных библиотечных функций, предназначенных для оперативной обработки символьных данных.
Основная функция main должна обеспечивать передачу в программу набора аргументов командной строки, вызов лока./льных функций для их обработки и возврат результата проверки палиндрома с помощью оператора return. Доступ к аргументам командной строки в заголовке функции main должны обеспечивать формальные параметры argc и argv. Параметр argc имеет тип (int) и идентифицирует количество аргументов командной строки. Параметр argv имеет тип (char**) и адресует вектор аргументов командной строки.
Адресное пространство, распределенное под формальные параметры argc и argv, удобно использовать для информационноAЛ взаимодействия локальных функций preparator и comparison, которые последовательно вызываются в блоке основной функции main. В частности, целочисленный код возврата функции preparator присваивается формальному параметру argc, значение которого затем передается в функцию comparison. Точно также, результаты преобразований исходной последовательности в функции preparator, должны сохраняться ее кодом по адресу начального параметра вектора аргументов argv[0] для последующей передачи в функцию comparison. Таким образом, для обеспечения информационного взаимодействия обеих локальных функций программы PALINDROME не требуется каких-либо дополнительных внешних и автоматических переменных кроме формальных параметров основной функции main.
Следует также отметить, что вызов локальной функции comparison должен осуществляться только при положительном коде возврата локальной функции preparator. Любое другое значение ее кода возврата должно приводить к завершению программы PALINDROME.

Преобразование командной строки

Если количество аргументов командной строки вызова программы PALINDROME больше единицы и/или аргументы содержат не только алфавитно-цифровые символы, то необходимо предварительное преобразование задаваемой ими исходной последовательности, которое реализуется локальной функцией preparator. Функция preparator должна обеспечивать преобразование набора аргументов командной строки вызова программы PALINDROME в строку символов, которая содержит алфавитно-цифровую последовательность, состоящую из цифр и/или строчных букв. Для выполнения этого преобразования в функцию preparator необходимо передать формальные параметры argc и argv основной функции main, через которые реализуется доступ к аргументам командной строки. Результат преобразований сохраняется по адресу начального аргумента командной строки, а длина полученной символьной строки передается через целочисленный код возврата оператором return в основную функцию main.
Процесс преобразований, реализуемых функцией preparator, целесообразно разделить на три процедуры: конкатенация аргументов командной строки, унификация классов символов и исключение разделителей. Для организации информационного взаимодействия этих трех процедур следует предусмотреть локальный символьный буфер обмена. Его длина должна быть достаточна для размещения всех аргументов командной строки.
Буфер обмена может быть a priori выделен в форме одномерного статического массива символов или с помощью стандартной библиотечной функции динамического распределения памяти calloc. В этом случае для измерения длины аргументов необходимо использовать библиотечную функцию strlen, а перед возвратом из функции preparator следует освободить выделенную динамически память с помощью библиотечной функции free.
Процедура конкатенации обеспечивает композицию набора аргументов в одну строку таким образом, что каждый следующий аргумент присоединяется к предыдущему справа. Накопление аргументов следует производить в буфере обмена, используя циклический вызов библиотечной функции strcat.
Процедура унификации классов символов должна обеспечивать замену любых символов в буфере обмена, которые не являются буквами или цифрами, на символ пробела и преобразование кодов заглавных букв в коды строчных букв. Для распознавания классов символов можно применить библиотечные предикаты isalnum и isupper. Для изменения регистра букв необходимо использовать библиотечную функцию tolower.
После выполнения указанных преобразований унификации буфер обмена может состоять из алфавитно-цифровых фрагментов, которые разделены одним или несколькими символами пробела. Процедура исключения разделителей должна обеспечивать сжатие информации в буфере обмена, таким образом, чтобы сохранить только лексемы, состоящие из алфавитно-цифровых символов. Для выявления лексем в буфере обмена целесообразно использовать циклический вызов библиотечной функции strtok. Конкатенацию полученных лексем нужно сохранить в виде строки символов с помощью библиотечной функции strcat, используя адресное пространство вектора аргументов argv, для передачи локальной функции comparision с целью последующей проверки свойства палиндрома.
Код локальной функции preparator завершает возврат длины сформированной алфавитно-цифровой последовательности с помощью оператора return. Для ее вычисления можно использовать библиотечную функцию strlen. При этом перед возвратом из функции preparator желательно корректно освободить адресное пространство буфера обмена, используя библиотечную функцию free, если эта область памяти была динамически распределена функцией calloc.

Программирование метода проверки палиндрома

Программную реализацию метода проверки палиндрома в символьной строке, подготовленной функцией preparator в ходе предварительной обработки аргументов командной строки программы PALINDROME, должна обеспечивать локальная функция comparison. Через формальные параметры ей необходимо передать адрес и длину символьной строки, сформированной в функции preparator и сохраненной в адресном пространстве формальных параметров основной функции main. Это значит, что в функцию comparison следует передать значение параметра argc для идентификации длины проверяемой символьной строки и адрес argv[0] для доступа к содержимому проверяемой строки символов. Результат проверки палиндрома должен передаваться в функцию main через целочисленный код возврата. Сам процесс выполнения проверки палиндрома в функции comparison состоит из 2-х операций: реверс и сравнение.
Операция реверса должна обеспечить запись символов проверяемой строки, индексы которых не меньше половины длины строки, в обратном порядке. Такое преобразование можно осуществить путем циклического сдвига влево символов реверсируемой половины строки, используя библиотечную функцию strncpy на каждой итерации цикла сдвига для копирования всех символов сдвигаемой части строки на одну позицию влево. При этом необходимо сохранить начальный символ сдвигаемой половины строки, чтобы получить возможность записать его в последнюю позицию фрагмента сдвига.
Процедура сравнения должна обеспечивать проверку эквивалентности обеих половин символьной строки, сформированной процедурой реверсирования. Диапазон сравнения определяется величиной половины длины проверяемой символьной строки. Программную реализацию сравнения должна обеспечивать библиотечная функция strncmp. Ее целочисленный код возврата определяет результат сравнения и, соответственно, результат проверки палиндрома в строке символов, адресуемой в функцию comparison.
Полученный результат сравнения должен передаваться через целочисленный код возврата функции comparison оператору return, который завершает спецификацию основной функции main, обеспечивая возможность числовой идентификации проверки палиндрома в операционной среде вызова программы PALINDROME.

Порядок разработки программы

Процесс разработки программы PALINDROME должен включать три стандартных этапа: подготовка исходноІн кода, трансляция его в исполняемый модуль и тестирование работы исполняемого модуля. Выполнение указанных этапов может производиться в среде любой реализации OS UNIX, в дистрибутиве которой предусмотрена поддержка инструментальных средств разработки прикладного программного обеспечения.
Для подготовки исходного кода программы PALINDROME может быть применен любой доступный текстовый редактор OS UNIX, например, vi, emacs, jed, joe, microemacs при работе в консольном режиме или xedit, при работе в операционной среде X Window System. Исходный код программы PALINDROME необходимо сосредоточить в текстовом файле, который следует сохранить под именем palindrome.c в любом доступном для записи каталоге файловой системы OS UNIX. Например, вызов экранного редактора joe для подготовки исходного кода программы в текущем каталоге обеспечивает команда:
$ joe palindrome.c
Для трансляции исходного кода программы PALINDROME необходимо применить инструментальные средства компилирующей системы программирования C в формате следующей командной строки:
$ cc -o palindrome palindrome.c
После вызова этой команды при отсутствии ошибок компиляции и компановки в текущем каталоге файловой системы OS UNIX создается выполняемый файл с именем palindrome. Полученный исполняемый код может быть вызван для выполнения в командной строке c требуемым набором аргументов.
Например, проверку палиндрома "Madam I'm Adam" обеспечивается следующая командная строка, согласно которой программе PALINDROME передается три аргумента:
$ palindrome Madam I\'m Adam
Следует отметиь, что в этой командной строке служебный символ обратной дробной черты '\' отменяет специальное действие металитеры одинарной кавычки в среднем аргументе. Кроме того, данная последовательность, как и любая другая, состоящая из нескольких алфавитно-цифровых фрагментов, может быть передана для обработки одним аргументом, если она заключена в двойные кавычки ("). В этом случае командная строка вызова программы PALINDROME должна иметь следующий формат:
$ palindrome "Madam I'm Adam"
Необходимый для анализа результата проверки код завершения программы PALINDROME, так же как и код возврата любой другой программы OS UNIX, автоматически сохраняется в предопределенной переменной окружения $?, которая поддерживается любым командным процессором. Ее значение можно отобразить через поток стандартного вывода, например, с помощью команды echo следующим образом:
$ echo $?
Следует отметить, что можно совместить вызовы программы PALINDROME и команды echo в одной командной строке, используя следующую инструкцию:
$ palindrome Madam I\'m Adam; echo $?
В любом из рассмотренных вариантов командной строки, реализующей вызов программы PALINDROME и визуализацию результата проверки, для заданной последовательности "Madam I'm Adam" в потоке стандартного вывода будет отображено значение 0, потому что она является текстовым палиндромом.
Контрольные задания

Разработать программу, определяющую количество целых чисел в заданном диапазоне, символическое представление квадратов которых в системе счисления по основанию 10 (8, 16) образует цифровой палиндром.

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

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

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


Список литературы
1. Болски М.И. Язык программирования Си. Справочник. - М., Радио и связь, 1988.
2. Уэйт М., Прата С., Мартин Д. Язык Си. Руководство для начинающих. - М., Мир, 1988.
3. Шилдт Г Справочник программиста по C/C++. - М., Вильямс, 2000.