Курсовая работа по дисциплине: Структуры и алгоритмы обработки данных. 2-й Семестр. Вариант №2

Постановка задачи

Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить дерево поиска заданного типа, упорядочивающее данные сначала по первому полю, затем по второму и т.д.
Провести поиск по ключу в построенном дереве поиска. В качестве ключа использовать три буквы ФИО студента. (Например, ключ поиска для Сидорова Ивана Кузьмича – СИК). Из записей с одинаковым ключом сформировать очередь. Вывести содержимое очереди.
При выполнении задания главное внимание следует уделить эффективности применяемых алгоритмов, исключению всех лишних операций.
Операции, выражающие логически завершенные действия, рекомендуется оформлять в виде подпрограмм, грамотно выбирая между процедурами и функциями. Имена переменных и подпрограмм, параметры подпрограмм, используемые языковые конструкции должны способствовать удобочитаемости программы.
Для сравнения символьных строк КАТЕГОРИЧЕСКИ НЕ РЕКОМЕНДУЕТСЯ пользоваться встроенными языковыми средствами и библиотечными функциями.

Ваpианты баз данных (БД)

Общие замечания
Все текстовые поля следует pассматpивать как символьные массивы (array of char), а не стpоки (string). Это сделано для совместимости между языками Паскаль и Си, а также из-за того, что в базах данных не принято хранить лишнюю информацию, такую как длина строки. Если длина поля пpевышает pазмеp хpанимой в нем инфоpмации, то оно дополняется пpобелами спpава. Каждое текстовое поле имеет свой фоpмат, котоpый опpеделяет смысл записанных в него данных. Пpи описании фоpмата в угловых скобках < и > указываются отдельные его элементы (сами угловые скобки в состав текста не входят); пpобелы обозначаются с помощью символа подчеpкивания. Если поле включает только один текстовый элемент, то фоpмат не указывается.
Целочисленные поля пpедставляются 16-pазpядными положительными числами (типа word в Паскале).
Пpи описании стpуктуpы записей в пpогpаммах необходимо точно соблюдать поpядок и pазмеp полей.



ПРИМЕЧАНИЕ. Предварительный просмотр содержимого баз данных возможен с помощью программы VIEWBASE.EXE

Содержимое архива следует распаковать в отдельную папку и запустить файл VIEWBASE.EXE (файлы с расширением dat должны находиться в этой же папке)

(Вам будет предложено ввести цифру от 1 до 4, которая соответствует номеру вашего варианта и номеру базы данных)



Описание баз данных

B= 1 ВАЖНО:(файл base1.dat)

Библиогpафическая база данных "Жизнь замечательных людей"


Стpуктуpа записи:
Автоp: текстовое поле 12 символов
фоpмат <Фамилия>_<буква>_<буква>
Заглавие: текстовое поле 32 символа
фоpмат <Имя>_<Отчество>_<Фамилия>
Издательство: текстовое поле 16 символов
Год издания: целое число
Кол-во стpаниц: целое число

Пpимеp записи из БД:
Кловский_В_Б
Лев_Hиколаевич_Толстой_________
Молодая_гваpдия_
1963
864

D = 2 Двоичное Б-дерево



Основные идеи и хаpактеpистики пpименяемых алгоpитмов и стpуктуp данных

1.
В начале работы программы осуществляется загрузка базы данных в динамическую память. Для хранения одной записи базы данных используется запись типа TRecInf, которая включает в себя все поля записи базы данных (автор, заглавие, издательство, год издания, количество страниц). В качестве указателя на запись типа TRecInf объявлен тип PRecInf.
Для хранения указателей на записи базы данных применяется индексный массив db, который имеет размер 4000 – по количеству записей в базе данных.

Для загрузки базы данных в динамическую память вызывается процедура Load, которая создает записи базы данных в динамической памяти и сохраняет указатели на них в массиве db. После загрузки база данных отображается на экране. Для этого вызывается процедура BrowseDB.


2.
Из записей массива db строится дерево поиска – двоичное Б-дерево. Расскажем кратко, что представляет собой двоичное Б-дерево.

Двоичное Б-дерево состоит из вершин с одним или двумя элементами.

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

Таким образом, страницы Б-дерева теряют свою целостность и элементы списков начинают играть роль вершин в двоичном дереве. Однако остается необходимость делать различия между ссылками на потомков (вертикальными) и ссылками на одном уровне (горизонтальными), а также следить, чтобы все листья были на одном уровне.

Построение двоичного Б-дерева происходит путем добавления новой вершины в уже существующее дерево. Введем логическую переменную VR, показывающую вертикальный рост дерева (в случае, если страница переполнилась и средний элемент передается на вышележащий уровень) и логическую переменную HR, определяющую горизонтальный рост дерева (если новый элемент размещается на этой же условной странице). Также определим показатель баланса BAL для каждой вершины, который принимает значение 0, если у данной вершины есть только вертикальные ссылки (вершина одна на странице), и значение 1, если у данной вершины есть правая горизонтальная ссылка.

При добавлении элементов в двоичное Б-дерево различают 4 ситуации, возникающих при росте левых или правых поддеревьев. Самый простой случай - рост правого поддерева вершины А, когда А - единственный элемент на странице. Тогда вертикальная ссылка просто превращается в горизонтальную (HR=1, баланс вершины А равен 1). Если на странице уже два элемента, то при добавлении новой вершины С средняя вершина В передается на вышестоящий уровень (VR=1, баланс вершины В равен 0).

В случае роста левого поддерева, если вершина В одна на странице, то вершина А добавляется на эту страницу. Однако левая ссылка не может быть горизонтальной, поэтому требуется переопределение ссылок (HR=1, баланс вершины А равен 1). Если на странице два элемента, то средняя вершина В поднимается на вышестоящий уровень (VR=1, баланс вершины В равен 0).

В программе для хранения информации о вершине используется запись типа TNode, указатель на нее PNode. В каждой записи типа TNode имеются поля: inf - указатель на информацию о книге, left- указатель на левую вершину, right - указатель на правую вершину, balance - баланс вершины.

Для создания дерева вызываем функцию CreateTree, которая для каждого элемента массива db вызывает процедуру AddNode, которая, в свою очередь, добавляет очередную вершину в дерево, упорядочивая записи сначала по первому полю, затем по второму и т.д. Для сравнения записей используется функция CompareRec, которая возвращает 0, если записи равны, -1, если первая запись меньше, 1, если первая запись больше.
Функция CreateTree возвращает корень созданного дерева.

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

Указатель на начало очереди – qHead, на конец – qTail. Для хранения элемента очереди используется запись типа TInf, указатель на нее PInf. В каждой записи типа TInf имеются поля: inf – указатель на запись базы данных в динамической памяти и next - указатель на следующий элемент очереди.

После того, как очередь будет сформирована, она отображается на экране. Для этого вызывается процедура BrowseQueue.



Распечатка текста пpогpа

Работа зачтена без замечаний.
Сдано в 2014 г.