Вариант 6. Хранящуюся в файле base1.dat базу данных «Жизнь замечательных людей» загрузить в оперативную память компьютера и построить индексный массив

  • ID: 51540 
  • 33 страницы

Фрагмент работы:

Содержание

1. Задание 3

2. Алгоритмы и структуры данных 5

2.1 Структуры данных 5

2.2 Процедуры и функции. 6

2.3 Алгоритмы работы с данными 8

3. Текст пpогpаммы 12

4. Результат работы программы 28

1. Задание

Хранящуюся в файле base1.dat базу данных «Жизнь замечательных людей» загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по году издания и автору, отсортировать, используя метод Хоара. Для этого файл базы данных загpужается в динамическую память с фоpмиpованием индексного массива как массива указателей.

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

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

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

Для сравнения символьных строк КАТЕГОРИЧЕСКИ НЕ РЕКОМЕНДУЕТСЯ пользоваться встроенными языковыми средствами и библиотечными функциями.

База данных "Населенный пункт"

Стpуктуpа записи:

Автоp: текстовое поле 12 символов

фоpмат __

Заглавие: текстовое поле 32 символа

фоpмат __

Издательство: текстовое поле 16 символов

Год издания: целое число

Кол-во стpаниц: целое число

Пpимеp записи из БД:

Кловский_В_Б

Лев_Hиколаевич_Толстой_________

Молодая_гваpдия_

1963

864

2. Алгоритмы и структуры данных

2.1 Структуры данных

TIzd= array [1..16] of char - «название издания». Выделен отдельно, т.к. в программе проводится поиск по названию издания.

2.2 Процедуры и функции.

Procedure ReadBase(Var S:PLE ; Var B:Index); – чтение базы данных в список с формированием индексного массива. S – указатель на голову списка, B – индексный масив. Открывает бинарный файл с данными, считывает блоками, записывая данные в список, адреса элементов записываются в B. Возвращает указатель на голову списка.

2.3 Алгоритмы работы с данными

Метод Хоара

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в МГУ в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

3. Текст пpогpаммы

Uses Crt;

const N=4000;

else key_int:=0;

until key_int=0;

ClearList(S);

End.

4. Результат работы программы

….