Информатика и технология программирования


Задания к лабораторным работам


Задание рассчитано на выполнение в течение 2-3 лабораторных занятий и предполагает разработку функций поддержки индексного файла с заданной структурой, заполнение файла данных, построение индекса и выполнение операций поиска, добавления, удаления и обновления записи.

1. Построение двухуровнего индекса. Выполнение операций над записями файла с коррекцией таблиц верхнего и нижнего уровней. Сохранение индекса нижнего уровня в файле. Построение индекса верхнего уровня при открытии индекса.

2. Индексный файл с областью переполнения. Выполнение операций с коррекцией области переполнения и основной области. При превышении размера области переполнения 10% от размера основной области производится операция повторного построения основной области.

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

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

5. Индексный файл представляет собой индексное дерево, которое сохраняется в файле записей фиксированной длины "естественным" образом. Записи индексного файла содержат номера записей файла данных. Индекс считывается в память полностью, для записей первых m уровней (задается при загрузке) обеспечивается считывание и связывание записей файла данных для ускорения поиска по индексу. Обеспечить сохранение сбалансированности дерева.

6. Ключом в файле записей фиксированной длины является поле name[30], содержащее строку ограниченного размера. Реализовать функции добавления, удаления и поиска записей по ключу с использованием метода расстановки ключей (хеширования). Для исключения коллизий использовать область переполнения с организацией списков записей. Предложить функцию расстановки и проверить ее эффективность.

7. Ключом в файле записей является целая переменная. Используется хеширование на основе функции середины квадрата. Размер таблицы изменяется: 16,32,64 и так далее записей. При отсутствии в области переполнения свободного места создается новый файл вдвое большего размера и в него переписываются записи из старого файла с использованием новой функции размещения (количество разрядов в "середине квадрата" увеличивается на 1).

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




Начало  Назад  Вперед