LOCATE(x, L). Эта функция возвращает позицию объекта х в списке L.если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).
RETRIEVE(p, L). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определён, если p = END(L) или в списке L нет позиции p. Элементы должны быть одного типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.
DELETE(p, L). этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a1, a2, …, an, то после выполнения этого оператора он будет иметь вид a1, a2, …, ap-1, ap+1, …, an.
Результат не определён, если в списке L нет позиции p или p = END(L).
NEXT(p, L) и PREVIOUS(p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L.если р – последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда p = END(L). Функция PREVIOUS не определена, если p =
1. Обе функции не определены, если в списке L нет позиции p.
MAKENULL(L). Эта функция делает список L пустым и возвращает позицию
END(L).
FIRST(L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).
8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.
Стеки.
Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют «магазинами», а в английской литературе для обозначения стеков ещё используется аббревиатура LIFO (last-in-first- out – последний вошел – первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STAK (Стек) обычно используют следующие пять операторов.
MAKENULL(S). Делает стек S пустым.
TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).
POP(S). Удаляет из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S),
S). Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.
PUSH(x, S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(x, FIRST(S), S).
EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.
Очереди.
Другой специальный тип списка – очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO»
(аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел – первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей. Для работы с очередями будут использоваться следующие операторы.
MAKENULL(Q) очищает очередь Q, делая её пустой.
FRONT(Q) – функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как
RETRIEVE(FIRST(Q), Q).
ENQUEUE(x, Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом:
INSERT(x, END(Q), Q).
DEQUEUE(x, Q) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q), Q).
EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.
Отображения.
Отображение – это функция, определённая на множестве элементов
(области определения) одного типа (будет обозначаться domaintype – тип области определения функции) и принимающая значения из множества элементов (области значений) другого типа, этот тип будет обозначаться rangetype – тип области значений (конечно, типы domaintype и rangetype могут совпадать). Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу r типа rangetype из области значений, будет записываться как M(d) = r.
Некоторые отображения, подобные square(i) = i2, легко реализовать с помощью функций и арифметических выражений языка Pascal. Но для многих отображений нет очевидных способов реализации, кроме хранения для каждого d значения M(d). Например, для реализации функции, ставящей в соответствие работникам их недельную зарплату, требуется хранить текущий заработок каждого работника.
Рассмотрим операторы, которые можно выполнить над отображением М.
Например, по заданному элементу d типа domaintype мы хотим получить
M(d) или узнать, определено ли M(d) (т.е. узнать, принадлежит ли элемент d области определения М). Или хотим добавить новые элементы в текущую область определения М и поставить им в соответствие элементы из области значений. Очевидна также необходимость иметь оператор, который изменял бы значение M(d). Кроме того, нужно средство «обнуления» отображения, переводящее любое отображение в пустое отображение, т.е. такое, у которого область определения пуста. Всё это можно обобщить в следующие три команды.
MAKENULL(M). Делает отображение М пустым.
ASSIGN(M, d, r). Делает М(d) равным r независимо от того, как M(d) определено ранее.
COMPUTE(M, d, r). Возвращает значение true и присваивает переменной r значение M(d), если последнее определено, и возвращает false в противном случае.
Структуры данных и алгоритмы для внешней памяти.
В алгоритмах, которые обсуждались до сих пор, предполагалось, что объем входных данных позволяет обходиться исключительно основной
(оперативной) памятью. Но как быть, если нужно, например, отсортировать всех государственных служащих по продолжительности их рабочего стажа или хранить информацию из налоговых деклараций всех граждан страны?
Когда возникает необходимость решать подобные задачи, объём обрабатываемых данных намного превышает возможности основной памяти. В большинстве компьютерных систем предусмотрены устройства внешней памяти, такие как жесткие диски, или запоминающие устройства большой ёмкости, на которых можно хранить огромные объёмы данных. Однако характеристики доступа к таким устройствам внешней памяти существенно отличаются от характеристик доступа к основной памяти. Чтобы повысить эффективность использования этих устройств был разработан ряд структур данных и алгоритмов.
В Pascal и некоторых других языках предусмотрен файловый тип данных, предназначенный для представления данных, хранящихся во вторичной памяти. Даже если в языке, которым вы пользуетесь, файловый тип данных не предусмотрен, в операционной системе понятие «внешних» файлов, несомненно, поддерживается. О каких бы файлах ни говорилось (файлах, предусмотренных в Pascal, или файлах, поддерживаемых непосредственно операционной системой), в любом случае придётся действовать в рамках ограничений, касающихся способов доступа к файлам. Операционная система делит вторичную память на блоки одинакового размера. Размер блока зависит от конкретного типа операционной систем и обычно находится в пределах от 521 до 4096 байт.
Файл можно рассматривать как связный список блоков, хотя чаще всего операционная система использует древовидную организацию блоков, при которой блоки, составляющие файл, являются листьями дерева, а каждый внутренний узел содержит указатель на множество блоков файла. Если, например, 4 байт достаточно, чтобы хранить адрес блока, а длинна блока составляет 4096 байт, тогда корневой каталог может содержать указатели максимум на 1024 блока. Таким образом, файлы, состоящие максимум из
1024 блоков (т.е. примерно четырёх миллионов байт), можно представить одним корневым блоком и блоками, содержащими сам файл. Файлы, состоящие из максимум 220 блоков, или 232 байт, можно представить одним корневым блоком, указывающим на 1024 блока промежуточного уровня, каждый из которых указывает на 1024 блока-листа, содержащих определённую часть файла и т.д.
Базовой операцией, выполняемой по отношению к файлам, является перенос одного блока в буфер, находящийся в основной памяти. Буфер представляет собой зарезервированную область в основной памяти, размер которой соответствует размеру блока. Типичная операционная система обеспечивает чтение блоков в том порядке, в котором они появляются в списке блоков, который содержит соответствующий файл, т.е. сначала мы читаем в буфер первый блок файла, затем заменяем его на второй блок, который записывается в тот же буфер, и т.д.
Теперь нетрудно понять концепцию, которая лежит в основе правил чтения файлов в языке Pascal. Каждый файл хранится в виде определённости блоков; каждый такой блок содержит целое число записей.
(Память будет использоваться нерационально, если хранить части одной и той же записи в разных блоках.) Указатель считываний всегда указывает на одну из записей в блоке, который в данный момент находится в буфере.
Когда этот указатель должен переместиться на запись, отсутствующую в буфере, настало время прочитать следующий блок файла.
Аналогично, процесс записи файла в языке Pascal можно рассматривать как процесс создания файла в буфере. Когда записи «записываются» в файл, фактически они перемещаются в буфер для этого файла – непосредственно вслед за записями, которые уже находятся там. Если очередная запись не помещается в буфер целиком, содержимое буфера копируется в свободный блок вторичной памяти, который присоединяется к концу списка блоков для данного файла. После этого можно считать, что буфер свободен для помещения в него очередной порции записей.
Стоимость операций со внешней памятью.
Природа устройств вторичной памяти (например, дисководов) такова, что время, необходимое для поиска блока и чтения его в основную память, достаточно велико, в сравнении со временем, которое требуется для относительно простой обработки данных, содержащихся в этом блоке.
Допустим, например, что имеется блок из 1000 целых чисел на диске, вращающемся со скоростью 1000 об/мин. Время, которое требуется для позиционирования считывающей головки над дорожкой, содержащей этот блок
Страницы: 1, 2, 3
