Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

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. Каждый файл хранится в виде определённости блоков; каждый такой блок содержит целое число записей.

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

Когда этот указатель должен переместиться на запись, отсутствующую в буфере, настало время прочитать следующий блок файла.

Рекомендуем скачать другие рефераты по теме: реферат китай курсовые работы, бесплатные шпаргалки по праву.





Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата