Цифровая сортировка базы данных "Жизнь замечательных людей"

Министерство Российской Федерации по связи и информатизации

СибГУТИ

Кафедра ПМиК

СиАОД

Курсовая работа

Вариант: N48

Выполнил: студент гр. П-13

Шандро И.М.

Проверил: доц.Курапова Е.В

Дата:

Оценка:

Новосибирск  2003

Содержание

1.  Постановка задачи. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . … .3

2.  Основные идеи . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . … . . .4

2.1.Цифровая сортировка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .4   2.2.Бинарный поиск. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .…. .4

2.3.Двоичное Б - дерево. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . .5

3.  Текст программы. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . … . . 7

4.  Описание программы . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . .16

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

  5.1.Отсортированная база данных. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .18

5.2.Содержимое очереди. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . .20

  5.3.Обход Б – дерева слева – направо. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .22

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

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

Вариант базы данных: “Жизнь замечательных людей”.

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

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

формат <Фамилия> <Буква> <Буква>

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

формат <Имя><Отчество><Фамилия>

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

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

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

Вариант условий упорядочения: по году издания и автору.

На основе упорядоченного списка построить индексный массив.

Далее провести поиск по году издания в упорядоченной базе, и из записей с одинаковой суммой сформировать список.

Из записей полученного списка построить дерево поиска по автору а и произвести поиск по запросу.

2. Основные идеи и характеристики применяемых алгоритмов.

2.1. Цифровая сортировка.

Общая схема алгоритма  выглядит следующим образом.

DO (j:=L;j>=1;j:=j-1)

<сброс очередей Q> ( собственно, их инициализация)

<расстановка элементов списка S в очереди Q по j – ой цифре>

<объединение очередей Q в список S>

OD

В алгоритме: L – число байт, по которым осуществляется сортировка.

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

Для упрощения задачи вводится индексный массив KDI (Key Digit Index), содержащий  номера нужных байтов.

Оценка трудоемкости метода  по времени:

О(L*(n+m)), где m – число очередей Q.

При некоторых L и m трудоемкость порядка O(n).

Однако, если число байт L (длина чисел) велико, то этот метод может проигрывать по сравнению с методом прямого слияния или же методом Хоара (чьи трудоемкости: O(n*log(n))).

2.2. Бинарный поиск.

Если перед нами стоит задача нахождения в массиве заданного элемента, то самый простой и, можно сказать, универсальный(в случае, если мы не знаем об упорядоченности массива) алгоритм следующий:

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

Соответсвенно, трудоемкость такого метода: O(n).

Однако, если нам заранее известно об упорядоченности массива, то применим следующий алгоритм:

берем средний элемент массива и сравниваем с ключом Х;

возможны три ситуации:

- если выбранный элемент = Х то поиск завершен;

- элемент меньше Х, продолжаем поиск в правой половине массива;

- элемент больше Х, продолжаем поиск в левой половине массива;

 Алгоритм двоичного поиска

L:=1; R:=n; find:=no;

DO (L<=R)

M:=[(L+R)/2]

IF (Am = X)   find:=yes FI

IF (Am < X)   L:=M+1

ELSE R:=M-1 FI

OD 

Трудоемкость: O(log(n))

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