Все лабы по инфе за 2ой сем на С++ (palindrome)

Посмотреть архив целиком

АНАЛИЗ ТЕКСТОВЫХ ПАЛИНДРОМОВ


Методические указания для практического занятия

по курсу

"Языки программирования высокого уровня"



Цель занятия


Целью занятия является практическое изучение применения библиотечных функций системы программирования 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, удобно использовать для информационного взаимодействия локальных функций 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.


Случайные файлы

Файл
60333.rtf
53461.doc
DISKINEZ.DOC
93462.rtf
113939.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.