1. И с п о л ь з о в а н и е л и н е й н ы х с п и с к о в
В ряде режимов обработки требуется наличие в памяти ЭВМ одновременно всех записей. Такая необходимость возникает, например, при группировке записей по регистрационным номерам.
Решение рассматриваемой задачи может быть выполнено путем использования массива или линейного списка записей.
Здесь обрабатываемый архив документов представлен в памяти ЭВМ в виде массива, каждый компонент которого - это запись, имеющая длину 49 байт.
С точки зрения машинной обработки использование массива для представления группы обрабатываемых записей, хранящихся в архивном файле, имеет два существенных недостатка.
1. Массив всегда имеет фиксированный размер (к примеру Nmax = 500), который не может быть изменен в процессе работы программы. Следовательно, при объявлении массива приходится ориентироваться на его максимально возможный размер, что ведет к неэкономному использованию памяти ЭВМ.
2. При изменении текущего количества компонентов в массиве (добавление новых или удаление существующих) обрабатываемый массив требуется полностью или частично переместить в памяти ЭВМ (сдвигать влево или вправо компоненты массива). Это требует определенных затрат машинного времени, которые тем больше, чем длиннее поле памяти, занимаемое одним компонентом.
Указанные недостатки можно устранить, если для представления группы обрабатываемых документов использовать списковые структуры (стек, очередь и т.п.). Для списка может быть выделено ровно столько памяти, сколько требуется для размещения данной группы записей, причем эта память может быть выделена в любой момент работы программы и освобождена, когда в этом возникнет необходимость. При изменении количества компонентов в списке нет необходимости перемещать их в памяти; для этого достаточно изменить значения соответствующих указателей.
Тем не менее списковые структуры обладают и некоторыми недостатками по сравнению с массивами.
1. Компонент однонаправленного списка занимает на 4 байта больше памяти, чем компонент массива (за счет размещения в нем указателя).
2. Список не предоставляет возможность прямого доступа к его компонентам (например, чтение компонента по его номеру в списке). Это, в частности, исключает возможность применения метода двоичного поиска для нахождения в сгруппированном списке компонента с заданным кодом.
Сравнивая достоинства и недостатки списковых структур, можно сделать вывод, что для задач АУС, в которых объектами обработки в основном являются записи большого размера, списки более предпочтительны по сравнению с массивами.
При использовании линейного списка для представления архива записей необходимо выбрать один из двух простых типов списка: стек или очередь.
Предположим, что читаемые из текстового файла записи "складируются" в стек. Тогда относительный порядок записей, читаемых из стека, будет обратным по отношению к последовательности записей в файле. Это создает определенные неудобства при программной обработке списка, в частности, требует выполнять реверс компонентов стека. В очереди относительный порядок компонентов не отличается от последовательности записей в файле. В связи с этим в задачах обработки архива записей очередь более предпочтительна по сравнению со стеком. Тогда описание компонента очереди может иметь следующий вид:
Type
DateType = record { тип даты }
Day : 1..31; { день }
Month : 1..12; { месяц }
Year : 1960 .. 2015; { год }
end;
TimeType = record { тип времени }
Hour : 0..23; { часы }
Minute : 0..59; { минуты }
end;
CatalType = record { тип параметров каталога }
Name : string[8]; { наименование }
Ext : string[3]; { расширение }
Tip : string[6]; { тип }
Atribut : string[9]; { атрибут }
Cap : word; { емкость, Кб }
Date : DateType; { дата создания }
Time: Timetype; { время создания }
end;
PointerCatal = ^DynCatal; { тип эл-та очереди записей }
DynCatal = record
Inf : CatalType;
Next : PointerCatal;
end;
string80 = string[80];
StringAr = array[1..10] of string80;
Var
np : word; { кол-во компонентов архива }
KeyRegime, { ключ выбора режима работы }
Device : byte; { устройство вывода результатов: }
{ 0 - экран; 1 - экран и магн.диск; }
{ 2 - экран и принтер }
SignArchive : boolean; { признак создания архива }
Reply : char; { символ ответа на запрос программы }
Catal : CatalType; { компонент архива }
Lp,Rp, { левый и правый указатели очереди }
Run : PointerCatal; { текущий указатель очереди архива }
St : StringAr; { строки для печати таблиц }
FileInput, { файл исходных документов }
FileAdd, { файл добавляемых документов }
FileRes : text; { файл результатов }
FileOut { архивный файл записей }
: file of CatalType;
Здесь Inf - информационная часть компонента очереди;
Next - указатель на следующий элемент;
LP, Rp, Run - соответственно левый, правый и текущий указатели очереди.