Цель работы - обработать текст без использования стандартных библиотек для работы с данными символьного типа, провести. сравнение эффективности обработки текста с использованием символьных массивов и динамических списков, отработать навыки работы со списками.
В последние годы персональный компьютер все чаще используется не только для выполнения вычислений, но и для анализа и обработки текстов. Текст при этом представляется как совокупность символьных данных, которые объединяются в структуры типа символьного массива или строки (конструкция String в Паскале или С++). Чаще всего эти структуры различаются формой своего внутреннего представления в памяти ПК. Для удобства работы с символьными данными во многих языках программирования разработаны специальные процедуры и функции, которые могут быть объединены в отдельные библиотеки (например, библиотека String.h в языках С и С++).
При работе с текстом программист должен, прежде всего, уметь правильно выбрать структуру данных для хранения и обработки символьной информации.
Текст физически можно представить как массивом символов, так и списком символов. При этом символьный массив может быть как статическим, так и динамическим.
При использовании статического массива весь объем требуемой памяти выделяется на этапе компиляции. В процессе заполнения массива можно обеспечить запоминание количества элементов в нем, организуя тем самым работу только с заполненной областью памяти. Оставшаяся часть памяти в этом случае расходуется непроизводительно.
Для оптимизации расходования памяти можно использовать динамический массив. Его преимуществом является то, что память под динамический массив выделяется во время выполнения программы по соответствующему запросу. Однако следует учитывать, что при необходимости добавить в массив один элемент придется каждый раз запрашивать память для создания динамического массива новой длины, что потребует времени на поиск непрерывного участка памяти (концепция массива требует, чтобы соседние элементы располагались в последовательных байтах памяти), и также выделение этой памяти, переписи в нее данных из «старого» массива и сохранения новой длины. Таким образом, уйдя от непроизводительной потери памяти, мы придем к дополнительному расходу времени. Следовательно, изменение размера динамического массива на единицу – очень ресурсоемкое и нецелесообразное действие. Память под динамический массив необходимо запрашивать «разумными» частями, чтобы минимизировать возможные потери ресурсов. Обычно новый массив удваивает используемый объём памяти.
Физическая структура и статического и динамического массива дополняется дескриптором, который хранит имя массива, адрес первого элемента, описание элемента, его длину и размер массива.
Список – это динамическая структура данных, каждый элемент которой, содержит данные и адрес следующего элемента (указатель на следующий элемент). Этот адрес у последнего элемента – нулевой. Память под каждый элемент списка выделяется динамически по мере необходимости. При этом в статической памяти хранится адрес первого элемента, или нулевой указатель, если список пуст.
Дескриптор списка содержит имя списка, адрес первого элемента, количество элементов, описание структуры элемента и его длину.
Для доступа к элементу списка необходим просмотр списка с «головы». Такой доступ называется последовательным. В элементе списка можно хранить адрес не только последующего, но и предыдущего элемента. В этом случае список называется двусвязным. Адрес предыдущего у первого элемента и последующего у последнего элемента – нулевой. Двусвязные списки можно просматривать в двух направлениях, т.е. доступ к элементам двусвязного списка возможен с любого конца. Если сделать список кольцевым (то есть в указатель последнего элемента записать адрес первого элемента), то начинать просмотр можно с любого элемента, и в дескрипторе можно хранить адрес любого элемента. Для односвязного, двусвязного, а также для кольцевого списка необходимо хранить в статической памяти хотя бы один указатель, содержащий адрес элемента списка.
Главными операциями над списками являются вставка элемента в список, исключение элемента из списка, поиск элемента в списке. При этом необходимо обеспечить вывод соответствующих сообщений при попытке удаления элемента из пустого списка и не забывать освобождать память при удалении элемента из списка.
Сравнительный анализ реализации структур данных в виде массивов и списков показывает следующее:
· если невозможно заранее узнать количество элементов в структуре, то ее лучше реализовать посредством списка;
· если необходимо реализовать операции включения или исключения элемента по номеру (по позиции), то лучше использовать массивы, так как в массивах возможен прямой доступ к элементу, а при использовании указателей позиция вообще не отслеживается;
· операции включения или исключения элемента из массива выполняются сложнее и дольше, чем в списке;
· использование массивов подразумевает расточительное выделение памяти (сразу под весь массив), зато в списке требуется дополнительная память в каждом элементе для хранения указателя на следующий (предыдущий) элемент.
Таким образом, каждая реализация имеет свои достоинства и недостатки, поэтому при решении конкретной задачи программист должен уметь соотносить преимущества и потери, чтобы осознанно отдать предпочтение одной из реализаций.
Еще одной проблемой при работе с текстами является наличие особенностей реализации алгоритмов их обработки, которые чаще всего вызываются спецификой внутреннего представления символьных структур данных. Эти особенности зачастую остаются скрытыми от программиста, если он пользуется стандартными процедурами и функциями языка программирования, предназначенными для работы с данными символьного типа. Поэтому в данной лабораторной работе предусматривается разработка студентами своих собственных подпрограмм даже в том случае, если имеется их реализованный аналог.
Не следует забывать и о том, что для вызова любой подпрограммы требуется время на передачу параметров в подпрограмму и на возврат результата в вызывающую программу, а также памяти для размещения локальных переменных. Программист должен уметь отказаться от излишнего применения и своих, и стандартных подпрограмм в пользу прямого алгоритмического решения для оптимизации непроизводительных расходов времени и памяти.
Слова текста из малых латинских букв записаны не менее чем через один пробел; текст оканчивается точкой. БЕЗ ИСПОЛЬЗОВАНИЯ конструкции String и стандартных процедур работы со строками написать программу ввода такого текста с клавиатуры и его обработки, используя: а) массив символов, б) список символов.
В приложении приведены примерные варианты заданий.
Общий алгоритм решения поставленной задачи, как правило, не зависит от конкретной реализации структуры данных. Однако все действия над текстом (поиск слов, выделение любого из слов, перестановка букв в слове и т.п.) должны быть описаны подпрограммами, «настроенными» на конкретную реализацию посредством формальных параметров.
Интерфейс программы должен быть понятен неподготовленному пользователю. При разработке интерфейса программы следует предусмотреть:
· указание формата и диапазона вводимых данных;
· блокирование ввода неверных по типу и формату данных;
· указание операции, производимой программой;
· наличие пояснений при выводе результата.
Нужно также вывести на экран информацию о времени выполнения программы при использовании массива и списка и об объеме памяти, требующейся в каждом из этих случаев.
При тестировании программы необходимо:
o проверить правильность ввода и вывода данных (в том числе, отследить попытки ввода данных, неверных по типу и формату);
o обеспечить вывод сообщений при отсутствии входных данных («пустой ввод»);
o проверить правильность выполнения операций, в том числе при полной загрузке системы (полностью заполненном массиве);
o отследить выход за границы массива;
o обеспечить вывод соответствующих сообщений при попытке удаления элемента из пустого списка или массива;
o отследить переполнение массива.
При представлении текста в виде списка необходимо:
o проверить возможность вставки элемента в начало, в конец и в середину списка;
o проконтролировать правильность удаления элемента из конца, середины, начала списка;
o отследить удаление единственного элемента и удаление элемента из пустого списка;
o проверить, как освобождается память при удалении элемента из списка.
В отчете по лабораторной работе должен быть сделан вывод о том, в каких случаях для хранения и обработки текста целесообразно применять статический или динамический массив, а в каких случаях – список. Кроме того, следует указать, какие преимущества и недостатки имеет та или другая реализация. В случае применения динамического массива необходимо обосновано продемонстрировать правильность его использования. Все выводы должны быть подкреплены численными результатами сравнений объёмов памяти и времён выполнения программы при использовании списка и массива.
В отчете по лабораторной работе должны быть даны ответы на следующие вопросы:
1. Какой объем памяти выделяется под хранение символьных данных при использовании различных языков программирования?
2. Какие структуры данных эффективнее использовать для хранения символьной информации?
3. Что такое динамический список, как выделяется и освобождается память под элемент списка?
4. Каким образом эффективнее обрабатывать символьные данные? От чего зависит эффективность обработки?
Отчет должен быть представлен в электронном или печатном виде.
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ. М.: Издат. дом «Вильямс», 2000. С. 45–57.
5. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ: Пер. с англ. М.: МЦНМО, 2001. С.198–202.
Приложение
Примерные варианты заданий
1 Напечатать все слова, отличающиеся от третьего слова, перед печатью удалив центральную букву слова, если оно нечетной длины. Если слов меньше трех – выдать сообщение.
2 Напечатать все слова, отличающиеся от последнего по алфавиту слова текста, перед печатью удалив из слова все гласные буквы.
3 Напечатать все слова, отличающиеся от последнего слова, и совпадающие с начальным отрезком алфавита (a, ab, abc и т.д.)
4 Напечатать все четные по длине слова, отличающиеся от первого слова, и в которые каждая буква входит не менее двух раз.