Разрушающее» и «неразрушающее» чтение.

Стеки и очереди допускают только «разрушающее» чтение - доступ к чтению очередного компонента возможен только после удаления уже прочитанного.

Отметим одно важное отличие между стеком и очередью в этом отношении. В случае очереди удаляемый компонент можно предварительно перезапомнить (повторно добавить с другого конца). В случае стека перезапоминание неприемлемо - оно «перегораживает» доступ к чтению очередного.

В случае (последовательных) файлов мы имеем «неразрушающее» чтение и связанное с ним понятие - текущий компонент (маркер текущего компонента).

Набор операций для (последовательных) файлов. (*)

· Создать пустой файл F.

PROCEDURE ReWrite(VAR F: TFile)

· Добавить компонент x в файл F.

PROCEDURE Write(x: TVal; VAR F: TFile)

· Установить текущим 1-й компонент файла F.

PROCEDURE Reset(VAR F: TFile)

· Установить текущим следующий компонент файла F.

PROCEDURE Next(VAR F: TFile)(**)

· Посмотреть значение текущего компонента файла F.

FUNCTION Retrieve(F: TFile): TVal(***)

· Проверить на конец файла F.

FUNCTION EOF(F: TFile): BOOLEAN

«Неразрушающее» чтение - это возможность повторного чтения, в этих условиях в определенном смысле реализуем прямой доступ к компонентам памяти. Можно ввести понятие позиция компонента - некий ключ, однозначно определяющий положение компонента в памяти, например просто его порядковый номер в последовательности. Тогда можно рассмотреть операцию «Установить текущим компонент p-ой позиции в файле F», с очевидной реализацией:

PROCEDURE Seek(VAR F: TFile; p: Longint); VAR i: Longint;

BEGIN Reset(F); i: =0; WHILE NOT EOF(F) AND (i< p) DO

BEGIN Next(F); i: =i+1 END END

...Остается конечно вопрос о более эффективной реализации этой операции для конкретных представлений данных типа файл...

Наши рассуждения о памяти процесса изначально проводятся в контексте двух последовательностей - входного потока данных и выходного. С входным потоком связана последовательность «запоминаний» (записи в память), с выходным - последовательность «вспоминаний» (чтения из памяти). Фактически исходный процесс мы трактуем как пару взаимодействующих субпроцессов:

Субпроцесс1: прием последовательности из входного потока

- формирование последовательности в памяти.

Субпроцесс2: просмотр последовательности в памяти

- передача последовательности в выходной поток.

В случае стека последовательность чтения из памяти обратна последовательности записи, в случаях очереди и файла - последовательность чтения совпадает с последовательностью записи.

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

Средства реструктуризации последовательной памяти - это операции вставки элементов в интересующее место памяти (последовательности) и удаления неинтересующих нас элементов из памяти (последовательности).