Структуры и алгоритмы обработки данных. Ключарев А.А - 64 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

64
ключено, что какой-то неизвестный указатель после перемещений за-
писи будет содержать неправильный адрес записи.
1.4.1. Организация
Существуют несколько способов организации данных в виде фай-
лов:
– последовательный файл;
– хешированные файлы;
– индексированные файлы;
– B-деревья.
Рассмотрим кратко первые три способа использования (B-деревья
рассмотрим более подробно далее).
При простой (и наименее эффективной) организации данных в виде
последовательных файлов используются такие примитивы чтения и за-
писи файлов, которые встречаются во многих языках программирова-
ния (например, read() и write() в языке Паскаль). В этом случае за-
писи могут храниться в любом порядке.
Поиск записи осуществляется путем полного просмотра файла. Встав-
ку в файл можно выполнять путем присоединения соответствующей
записи в конец файла. В случае изменения записи необходимо осуще-
ствить поиск требуемой записи, а затем внести в нее изменения.
При удалении записи тоже необходимо найти удаляемую запись, а
затем определенным вариантом удалить. Один из вариантов – сдвинуть
все записи, следовавшие за удаленной записью, на одну позицию впе-
ред (осуществляя при сдвиге перенос записей между блоками). Однако
такой подход не годится, если записи являются закрепленными, посколь-
ку указатель на i-ю запись в файле после выполнения такой операции
будет указывать на (i+1)-ю запись. В этом случае необходимо опреде-
ленным образом помечать уделенные записи, но не смещать оставшие-
ся на место удаленных (и не должны вставлять на их место новые запи-
си). Существуют два способа помечать удаленные записи:
1) заменить значение записи на специальное значение, которое ни-
когда не может стать значением неудаленной записи;
2) предусмотреть для каждой записи специальный бит удаления, ко-
торый содержит, например, 1 в удаленных записях и 0 – в неудаленных
записях.
Очевидным недостатком последовательного файла является то, что
операции с такими файлами выполняются медленно. Выполнение каж-

Страницы