Процедуры, используемые при работе с нетипизированными файлами

 

BlockRead(F, Buf, N, Nfact) - чтение из файла. Считывается N записей, начиная с текущего места в файле в область памяти, занимаемую переменной Buf. Количество прочитанных байтов равно произведению N на длину записи, указанную в процедуре открытия файла или меньше, если при чтении достигается конец файла. Программа не проверяет, помещается ли считанная информация в область памяти, отведенную переменной Buf. Если при обращении к процедуре используется необязательный параметр Nfact, то в него заносится фактически прочитанное число записей. При этом не возникает ошибки, если достигается конец файла вовремя ввода. По окончании процедуры, указатель файла перемещается на соответствующее число записей вперед.

BlockWrite(F, Buf, N, Nfakt) - запись в файл. Записывается N записей (или меньше, если на диске кончится место) по Size байт каждый (Size задается в процедуре открытия файла). Все записываемые байты данных выбираются начиная с первого байта области, занятой переменной Buf. Необязательный параметр Nfakt становится равным фактическому количеству сделанных записей. По окончании процедуры, указатель файла перемещается на соответствующее число записей вперед.

Функции, используемые при работе с нетипизированными файлами.

 

Возможно использование функций FilePos(F) и FileSizs(F), так же как и для типизированных файлов.

Примеры полной программы работы с нетипизированными файлами можно найти в описаниях Турбо Паскаля 6 и 7 версий, здесь рассмотрим отдельные операторы работы с такими файлами. Например, если нужно записать в файл строку Head из 20 символов, затем значение вещественной переменной Х, занимающей в памяти 6 байт и целочисленный массив Matrix типа mass2, это можно сделать следующими операторами:

...

TYPE

mass2 = array[1..20,5..14] of integer;

...

VAR

Foutput: File;

Head: string[20];

Matrix: mass2;

X: real;

Number: integer;

...

BEGIN

...

Assign(Foutput,'SVALKA.DAN');

Rewrite(Foutput, 1);

...

BlockWrite(Foutput,Head,SizeOf(Head));

BlockWrite(Foutput,X,6);

BlockWrite(Foutput,Matrix,SizeOf(mass2),Number);

if Number <> SizeOf(mass2) then

Writeln(' Не хватает места на диске!');

...

Глава 10. Динамические переменные (списки)

 

Понятие динамических переменных

 

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

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

Для устранения этих недостатков можно использовать динамическое выделение памяти под данные в процессе выполнения программы. Такая динамически выделяемая память размещается уже за пределами статического сегмента, и по объему ограничена только размерами свободной памяти ЭВМ.

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

Значением указателя является физический адрес переменной базового типа, задаваемого идентификатором типа. Синтаксическое выражение для описания ссылочного типа имеет вид

<тип-указатель>::= ^<идентификатор базового типа>

где символ ^ - признак ссылочного типа;

<идентификатор базового типа> - описанное ранее или стандартное имя типа.

Пример описания <тип-указатель>:

Type

mas=array[1..100] of real; {тип - массив вещественных чисел}

dinmas=^mas; {тип указатель для значений переменных типа mas}

 

Переменные ссылочного типа вводятся, как и другие переменные, путем перечисления их имен в разделе описания переменных с указанием типа.

 

Var

Pj:^integer; {указатель целого числа}

Pc:^char; {указатель символа}

Pd:dinmas; {указатель массива}

 

Описание ссылочной переменной отводит в памяти место (4 байта) для размещения ссылки. При этом ссылочной переменной никакого значения (в том числе Nil) не присваивается.

Для приведенного примера описания динамических переменных Pj, Pc, и Pd значениями этих переменных в дальнейшем будут, соответственно адреса данных каких-нибудь переменных базовых типов: соответственно целых, символьных и массива вещественных чисел.

Динамические переменные базового типа не имеют имен. В качестве имени для них используются конструкции вида:

 

^<имя указателя>

 

Например: Pj^, Pc^, Pd^.

Присваивать значения указателям можно тремя способами:

Записав в него адрес существующей статической переменной, получив его операцией @: Pj:=@N; конечно, тип переменной должен соответствовать базовому типу, использованному для описания Pj.

Присваиванием значения другого указателя того же типа или стандартного значения nil.

Присваиванием указателю адреса вновь выделенного места в оперативной памяти – то есть адреса начала динамической переменной.

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

 

	*		Объект типа Рj

New(Pj); Pj

 

 

Чтобы обратиться к динамической переменной, необходимо применить операцию "разыменования" к указателю на эту переменную, используя знак операции "^" после имени указателя. Например, после выделения области памяти для хранения значений динамической переменной, ей можно присвоить значение оператором:

*

Pj^:=3; Pj

 

 

Чтобы освободить выделенную область памяти для использования другими динамическими переменными нужно воспользоваться процедурой Dispose(Pj), которая является обратной, по отношению к процедуре New(Pj):

Dispose(Pj); Pj

 

 

После освобождения выделенной памяти необходимо очистить указатель, ссылавшийся на удаленную динамическую переменную. Это выполняется присваиванием указателю "несуществующего" нулевого адреса nil:

 

Рj:=nil; Pj

 

Для выделения заданной в байтах области динамической памяти можно так же использовать процедуру GetMem, а для освобождения областей динамической памяти, заданных процедурой GetMem служат процедуры FreeMem, Mark и Release.

 

При работе с динамическими переменными важно помнить, что любая память, выделенная процедурой New(), должна быть освобождена в программе процедурой Dispose()!

 

Списочные данные

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

Такие составные данные носят название списков.

Список – это совокупность однотипных данных расположенных в памяти произвольным образом (не подряд). Элементы списка связаны между собой указателями (ссылочными полями). В зависимости от количества ссылочных полей в каждой записи (элементе списка) списки делятся на нуль-, одно-, двух- и многосвязные. Если у списка имеются концевые элементы, он называется линейным, если последний элемент списка связан с первым (или с заголовком) – список называется кольцевым.

В языке Паскаль для списков, в отличие от массивов и структур, нет специального ключевого слова для описания переменных типа списка. Их создают с помощью комбинированных записей, содержащих ссылочные поля.

Ниже приведены схемы различных видов списков записей. На них символами "*" отмечены поля ссылок. Стрелками показаны связи между записями. Поля данных заглавных звеньев обычно используются для хранения общей информации о списках.

Односвязные списки

 

Пример организации односвязного списка приведен ниже.

Type

Z=Record {комбинированный тип для данных}

a: String; {строковое поле}

b, c: Integer; {поле целых чисел}

d: Real {поле вещественных чисел}

end;

P=^S; {тип указатель записи базового типа S}

S=Record {базовый тип для указателей типа Р}

ls:P; {поле типа Р ссылки на следующую запись}

Dt:Z {поле типа Z записи данных}

end;

В этом примере типы Z и S введены для описания переменных - записей, содержащих в своих полях a, b, c, d данные, соответствующие описанным типам полей. P - тип указатель для динамических переменных базового типа S, т.е. значения переменных типа P будут адресами переменных типа S.

Наличие у комбинированной переменной типа S адресного поля ls типа P позволяет включать в состав записи ссылку на последующую запись и хранить таблицы в памяти машины в виде динамических списков связанных записей.

 

Var

Dt:Z; {запись данных}

Uz,U:P {указатели заглавного и текущего звеньев списка}

 

 

 

 

 

Двусвязные списки

 

В двусвязных списках базовый комбинированный тип S для указателей типа P будет иметь два адресных поля: поле ls ссылки на следующую запись списка и поле lp ссылки на предыдущую запись списка. Описание двусвязных списков аналогично приведенному выше (для односвязных списков) с отличием в структуре S:

P=^S; {тип указатель записи базового типа S}

S=Record {базовый тип для указателей типа Р}

ls: P; {поле типа Р ссылки на следующую запись}

lp: P; {поле типа Р ссылки на предыдущую запись}

Dt: Z {поле типа Z записи данных}

end;

 

 

 

 

При работе с одно- и двусвязными списками нужно уметь добавлять элементы в любое место списка, удалять заказанный элемент из списка и перемещаться по списку с целью поиска или выбора информации из списка. Необходимо определять, пуст ли список в данный момент.

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

 

Для линейных и кольцевых списков с заголовком вне кольца, проверяется ссылка из заголовка на следующее звено. Если Uz^.ls=nil, то список пуст. Для кольцевых с заголовком в кольце – если Uz^.ls=Uz, то список пуст.

Выбор данных из списка производится без изменения списка, путем ссылки на информационную часть нужного звена: U^.Dt. Чтобы добраться до нужного звена списка, по нему приходится последовательно перемещаться (в цикле, начиная от начала или от текущего звена). Так же как при работе с массивом, для перехода от элемента A[i] к следующему элементу необходимо выполнить i:=i+1.

При работе со списком следует использовать оператор U:=U^ls.

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

Нульсвязные списки

 

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

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

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

Рассмотрим варианты нульсвязных списков.

Стек – это нульсвязный список, иногда называемый очередью с правилом обслуживания LIFO (Last In – First Out – последним пришел – первым ушел). У стека начало и конец – это одно и то же звено, обычно называемое вершиной стека.

 

Создание пустого стека – это, по сути, создание указателя на вершину стека (N), и присвоение ему значения nil. Этот указатель в дальнейшем играет роль адреса начала и конца стека текущего звена.

Формирование вершины стека можно произвести следующим образом:

Var

S:P1;

Begin

new(S);

...

Очередь – нульсвязный список с правилом обслуживания FIFO (First In – First Out – первым пришел – первым ушел).

 

Для работы с очередью необходимы такие же процедуры, как и для стека. При создании пустой очереди указателям N и K присваивается значение nil. Процедурам добавления в очередь и выбора из очереди приходится передавать указатели на оба конца, так как при создании первого звена, его адрес необходимо занести в оба указателя, а при удалении последнего звена очереди, обоим указателям надо присвоить значение nil.

Дек – это нульсвязный список, в котором добавление и выбор элементов возможен с любого конца. Его можно рассматривать как двусторонний стек или двустороннюю очередь. Название (deque) расшифровывается как double-ended queue – очередь с двумя концами.

 

 

Проще всего дек моделировать двусвязным линейным списком, по которому запрещено перемещаться. Формально для него приходится составлять две процедуры добавления и две процедуры удаления элементов, находящихся на первом и втором концах дека. На практике процедуры добавления можно объединить в одну, используя дополнительный признак – к какому концу добавляется элемент. Хотя оба конца дека равноправны, для определенности одну сторону будем называть началом, обозначая указателем NK, а вторую – концом, с обозначением KN.