Пирамидальная сортировка.

Предположим, что дана пирамида с элементами h_l+1, ..., h_r для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду h_l, ..., h_r. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

Обменная сортировка разделением (быстрая сортировка).

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 4 части. Алгоритм применяется к каждой четвертинке и т.д. Разделение заканчивается, когда в каждой части остается 1 элемент.

19. Дайте определение «Рекурсия», «Условие завершения рекурсии», «Косвенная рекурсия».

Рекурсия – процедура (функция), которая обращается к самой себе или вызывает саму себя. Содержание и мощность рекурсивного определения, а также главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов. Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. Главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Косвенной или взаимной рекурсией называется организация вызовов нескольких процедур и функций по кругу (первая процедура вызывает вторую, вторая - третью, ..., n-я процедура вызывает первую).

20. Дайте понятие «текстовый файл». Опишите формат объявления текстового файла.

Текстовые файлы состоят из последовательности символов, разделенных на строки. Каждый текстовый файл разделяется на строки неопределенной длины, которые заканчиваются символом конец строки. Каждый символ представлен во внутреннем коде ASCII и занимает 1 байт. Текстовый файл отличается от символьного не только делением на строки. В текстовый файл можно записать и из него прочитать информацию любого типа. Если эта информация не символьная, то в процессе чтения или записи происходит ее преобразование из символьной формы во внутреннюю и обратно.

К текстовым файлам возможен только последовательный доступ. С текстовыми файлами работают различные редакторы текстов. Текстовые файлы имеют стандартный тип TEXT.

Формат описания

VAR < имя файла>: TEXT;

21. Дайте понятие «нетипизированный файл». Опишите формат объявления нетипизированного файла.

Файлы без типа используются обычно при копировании файлов, когда не важна внутренняя структура записи файла. Если длина сегмента на диске 1024 байта, то количество блоков в группе равно 8 при длине блока 128 символов.

Обмен информацией происходит непосредственно между программой и файлом без использования буферной памяти. Адресация блоков производится по их номерам. Блоки в этом случае являются компонентами файла. Использование файлов без типа приводит к экономии памяти.

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

Формат описания

VAR < имя файла > : FILE;

BLOCKREAD(<имя файла>,<переменная>,<число компонент> [,<факт.число>]); – для чтения блока из файла.

BLOCKWRITE(<имя файла>,<переменная>,<число компонент> [,<факт.число>]); – для записи блока в файл.

Здесь <имя файла> – имя файла без типа; <переменная> – имя переменной для чтения или записи; <число компонент> – количество передаваемых компонент за один раз; <фактическое число> – количество фактически переданных записей длиной 128 байт.

Файл для блочного ввода-вывода описывается с типом FILE. Для файла без типа нельзя использовать процедуры READ и WRITE.

При открытии файла без типа можно указать длину записи файла в байтах. Она указывается вторым параметром при обращении к процедуре RESET или REWRITE, в качестве которого используется выражение типа WORD. Если длина записи не указана, она принимается равной 128 байтам.

22. Дайте понятие «типизированного файл». Опишите формат объявления типизированного файла. Перечислите процедуры и функции, необходимые при работе с типизированными файлами с краткой характеристикой.

Типизированный файл - это последовательность элементов одного типа. При последовательном обращении к файлу текущий указатель переходит от элемента к элементу.

Формат описания

TYPE <имя>=FILE OF <тип элементов>

VAR < имя файла > : <имя>

или без объявления файлового типа

VAR < имя файла > : FILE of <тип элементов>;

Если есть необходимость нарушения последовательной записи или чтения из файла, текущий указатель, может быть изменен процедурой SEEK (МуFilе, n); где n - требуемое положение указателя. Нумерация элементов типизированного файла начинается с нуля.

Seek (МуFilе, 0); - устанавливает указатель в начальной позиции (на первый элемент).

Seek (МуFilе, FileSize(МуFilе)); - устанавливает указатель после последнего элемента, то есть на признак конца файла.

Примечание. Функция FileSize(МуFilе) возвращает количество элементов типизированного файла МуFilе. Текущую позицию указателя дает функция FilePos (МуFilе);

Функция IOResult предназначена для поиска ошибок, возникающих при работе с файлами. Эта функция возвращает результат последней операции ввода/вывода, если автоматический контроль за ошибками, возникающими при выполнении операций ввода/вывода, отключен с помощью директивы компилятора {$I-}. При безошибочном выполнении операций ввода/вывода функция IOResult всегда возвращает результат равный нулю. Поэтому, как правило, ее используют в операции сравнения с нулем. При использовании функции IOResult нужно помнить о том, что она возвращает величину, которую можно интерпретировать как флаг ошибки лишь в том случае, когда эта функция вызывается следом за операцией ввода/вывода. А если Вы хотите провести анализ ошибки позже, Вам придется сохранить возвращаемое значение в некоторой промежуточной переменной.

Изменение имени файла производится процедурой RENAME(МуFilе, FileName);

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

Уничтожение части файла от текущего положения до конца производится процедурой TRUNCATE(МуFilе);

Уничтожение всего файла производится процедурой ERASE(МуFilе); действие которой эквивалентно удалению файла в операционной системе DOS.

23. Раскройте суть понятия «объект». Перечислите свойства объекта с краткой их характеристикой.

Объект – это структура, компонентами которой являются данные-поля объекта и процедуры (функции) - методы объекта. Все данные и методы инкапсулированы в одном объекте.

Определение типа ОБЪЕКТ:

TYPE ИмяОбъекта = OBJECT

Поля данных;

Заголовки методов;

END;

Все поля данных предшествуют методам. Поля – любые структуры данных кроме файлов. Все поля предшествуют методам. Полями могут быть любые структуры данных, кроме файлов.

Метод – это процедура (или функция), объявление которой включено в объявление объектного типа. Метод выполняет действие над объектом – экземпляром объектного типа. Включая объявление методов в объявление объектного типа, программист явно указывает какие действия могут быть выполнены над объектом. Инкапсуляция является важнейшим свойством объекта, на котором строится ООП. Инкапсуляция заключается в том, что объект скрывает свои детали, которые несущественны для использования объекта, т.е. пользователь класса должен видеть и использовать только список полей объекта и методов и не вникать в его внутреннюю реализацию. Этот прием еще называется сокрытие данных, благодаря которому защищаются такие сведения клиента, как баланс счета. Инкапсуляция является средством организации доступа к данным только через соответствующие методы.

Наследование – это порождение новых типов объектов (потомков) из уже имеющихся типов объектов (предков или прародителей). Объекты Потомки получают по наследству все поля и методы объекта Предка, могут быть дополнены новыми полями и методами, и, кроме того, могут переопределять методы объекта Предка, сохраняя или изменяя при этом у одноимённых методов списки формальных параметров и типы возвращаемых значений. Поля объекта Предка в объекте Потомке заменять нельзя.

Любой метод объекта Предка может быть вызван в любом методе объекта Потомка. В этом случае перед именем вызываемого метода указывается имя типа объекта Предка.

При вызове метода прямого Предка в версии Турбо Паскаль 7.0 достаточно предварительно указать ключевое слово INHERITED (унаследованный).

Синтаксически наследование выражается следующим образом:

Type ИмяОбъектаНаследника= OBJECT(ИмяОбъектаПредка)

Новые поля объекта наследника;

Новые методы объекта наследника;

END;

Полиморфизм – это свойство родственных объектов (т.е. объектов, имеющих одного общего родителя) решать схожие по смыслу проблемы разными способами. Изменяя алгоритм того или иного метода в потомках объекта, программист может придавать этим потомкам отсутствующие у родителя специфические свойства. Для изменения метода необходимо перекрыть его в потомке, т.е. объявить в потомке одноименный метод и реализовать в нем нужные свойства. В результате в объекте-потомке и объекте-родителе будут действовать два одноименных метода, имеющих разную алгоритмическую основу и придающих объектам разные свойства.

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

Если несколько объектных типов связаны между собой отношениями родитель-потомок, то указателю на базовый тип может быть присвоено значение указателя на любой из дочерних типов.

24. Раскройте суть понятия ООП. Опишите назначение конструктора и деструктора.