1.1 Записи фиксированной, переменной и неопределенной длины

При обработке записей, объединенных в последовательную структуру данных, необходимо указывать для данной записи ее длину, которая представляет собой количество символов в записи и обычно выражается в байтах. Записи с точки зрения способа указания их длины, делятся на записи фиксированной, переменной и неопределенной длины.

Записи фиксированной (постоянной) длины имеют одинаковую, заранее известную длину. На рис. 1 показаны пять записей фиксированной длины. Если длины записей в последовательной структуре данных неодинаковы, они указываются в самой записи. Такие записи называют записями переменной длины. На рис. 2 длина очередной записи выделена утолщенной линией.

25

И

В

А

Н

О

В

С

С

2

2

0

9

7

0

Д

И

Р

Е

К

Т

О

Р

23

К

А

Ц

А

П

1

3

1

2

7

5

Б

У

Х

Г

А

Л

Т

Е

Р

24

Л

У

Г

О

В

Г

Е

0

4

0

2

8

0

О

Х

Р

А

Н

Н

И

К

26

П

У

Т

И

Н

А

А

К

2

3

0

2

7

8

С

Е

К

Р

Е

Т

А

Р

Ь

25

Я

К

У

Ш

Е

В

А

П

П

1

9

1

1

6

9

Д

В

О

Р

Н

И

К

Рис. 2. Структура данных с записями переменной длины

Вместо явного указания длины записи можно отмечать окончание записи специальным символом – разделителем, который не должен встречаться среди информационных символов значения записи. Записи, заканчивающиеся разделителем, называются записями неопределенной длины. Пример таких записей показан на рис. 3, а в качестве разделителя использован символ @. Записи переменной и неопределенной длины часто объединяются одним термином «записи нефиксированной длины».

И

В

А

Н

О

В

С

С

2

2

0

9

7

0

Д

И

Р

Е

К

Т

О

Р

@

К

А

Ц

А

П

1

3

1

2

7

5

Б

У

Х

Г

А

Л

Т

Е

Р

@

Л

У

Г

О

В

Г

Е

0

4

0

2

8

0

О

Х

Р

А

Н

Н

И

К

@

П

У

Т

И

Н

А

А

К

2

3

0

2

7

8

С

Е

К

Р

Е

Т

А

Р

Ь

@

Я

К

У

Ш

Е

В

А

П

П

1

9

1

1

6

9

Д

В

О

Р

Н

И

К

@

Рис. 3. Структура данных с записями неопределенной длины

Адреса промежуточных записей фиксированной длины в массиве задаются формулой

A_i = A₀ + (i - 1)∙L,

где A₀ – начальный адрес первой записи; A_i – начальный адрес i-й записи; L – длина одной записи.

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

Последовательные структуры данных из записей фиксированной длины представляются вектором, каждая компонента которого соответствует той или иной записи. Номер записи в массиве указывается в скобках и называется индексом. Тогда, например, при описании последовательной структуры данных в виде А(1:100).(В, С, D) обращение к 33-й по порядку записи может формулироваться в виде А(33).(B, С, D), а обращение к i-й записи как А(i).(В, С, D). В этом случае при обращении к любой записи необходимо указание имени массива А и индекса данной записи. В описании последовательной структуры через двоеточие указываются номера первой и последней записи массива (граничные пары массива); В, С и D в нашем примере – реквизиты, образующие запись А.

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

K(1)

K(2)

…

K(i)

…

K(n)

Номера записей 1 2 i n

Рис. 4. Упорядоченная последовательная организация данных

Атрибуты ключевых полей обозначены через K(i), где i – номер записи, общее число записей – n. Условие упорядоченности записей выглядит следующим образом:

K(i) ≤ K(i+1) – упорядоченность по неубыванию;

K(i) ≥ K(i+1) – упорядоченность по невозрастанию.

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