4089

Структуры и алгоритмы обработки данных. Расчет БД Жизнь замечательных людей

Курсовая

Информатика, кибернетика и программирование

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

Русский

2015-01-15

352 KB

43 чел.

Задание

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

При работе с базой данных (БД) учесть следующие замечания:

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

Библиографическая БД «Жизнь замечательных людей» хранит записи следующей стpуктуpы:

 

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

фоpмат <Фамилия>_<буква>_<буква>

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

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

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

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

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

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

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

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

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

1963

864


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

Согласно заданию программа должна последовательно выполнить следующие действия:

  •  загрузить в память все записи БД;
  •  выполнить сортировку записей методом прямого слияния с использованием очередей;
  •  построить индексный массив;
  •  выполнить поиск записей по ключу, введенному пользователем, с использованием массива и формированием очереди из найденных записей;
  •  вывести на экран результаты поиска, если это согласовано пользователем;
  •  построить массив, упорядоченный по году издания книг, необходимый для построения ДОП;
  •  построить ДОП по приближенному алгоритму А2;
  •  выполнить поиск в ДОП по ключу, введенному пользователем с выводом информации о количестве найденных изданий;

Кроме того, программа должна протоколировать результаты работы в файле журнала программы KR.LOG, создаваемого в каталоге с исполняемым файлом программы.

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

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

Действие

Загрузка записей БД в оперативную память

Тип подпрограммы

Функция

Описание

Размещает в динамически создаваемых структурах, организованных в очередь, записи, последовательно считываемые из БД.

Входные параметры

нет

Выходные параметры

нет

Результат

указатель на созданную очередь

Действие

Сортировка очереди

Тип подпрограммы

Процедура

Описание

Сортирует очередь методом прямого слияния

Вх./вых. параметры

указатель на сортируемую очередь

Действие

Построение индексного массива

Тип подпрограммы

Функция

Описание

Распределяет динамическую память для размещения элементов массива в количестве, равном числу записей БД. Сохраняет в элементах массива адреса записей.

Входные параметры

указатель на отсортированную очередь

Выходные параметры

нет

Результат

указатель на созданный индексный массив

Действие

Поиск по ключу в упорядоченной БД

Тип подпрограммы

Функция

Описание

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

Входные параметры

указатель на индексный массив

Выходные параметры

нет

Результат

указатель на созданную очередь или пустой

Действие

Вывод на экран очереди результатов поиска

Тип подпрограммы

Процедура

Описание

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

Входные параметры

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

Выходные параметры

нет

Действие

Построение массива, упорядоченного по году издания книг

Тип подпрограммы

Функция

Описание

Обойти АВЛ-дерево слева направо, сохраняя в элементах массива указатели на вершины АВЛ-дерева.

Входные параметры

указатель на вершину АВЛ-дерева

количество элементов массива

Выходные параметры

нет

Результат

указатель на созданный массив, упорядоченный по году издания книг, содержащий указатели на вершины АВЛ-дерева с рассчитанными весами

Действие

Построение АВЛ-дерева

Тип подпрограммы

Функция (вспомогательная)

Описание

Последовательно перебирая элементы очереди результатов поиска, добавить в АВЛ-дерево вершину, если год издания не найден в АВЛ-дереве, увеличить вес вершины, если год ее год совпадает с годом элемента очереди.

Входные параметры

указатель на вершину АВЛ-дерева,

количество элементов массива

Выходные параметры

нет

Результат

указатель на корень АВЛ-дерева

Действие

Построение ДОП (алгоритм А2)

Тип подпрограммы

Функция

Описание

Добавлять вершины, адресуемые элементами массива, в соответствии с приближенным алгоритмом А2.

Входные параметры

указатель на массив вершин, упорядоченный по году издания книг, с рассчитанными весами

Выходные параметры

нет

Результат

указатель на корень ДОП

Действие

Поиск по ключу в ДОП с выводом информации о количестве найденных изданий

Тип подпрограммы

Функция

Описание

Спускаясь по ветвям ДОП, найти вершину с годом равным ключу. Вывести на экран вес вершины.

Входные параметры

указатель на корень ДОП, ключ поиска

Выходные параметры

нет

Результат

указатель на найденную вершину или пустой


Основные алгоритмы

Сортировка последовательностей методом прямого слияния

В основе метода прямого слияния лежит операция слияния серий. р-серией называется упорядоченная последовательность из р элементов.

Пусть имеются две упорядоченные серии a и b длины q и r соответственно. Необходимо получить упорядоченную последовательность с, которая состоит из элементов серий a и b. Сначала сравниваем первые элементы последовательностей a и b. Минимальный элемент перемещаем в последовательность с. Повторяем действия до тех пор, пока одна из последовательностей a и b не станет пустой, оставшиеся элементы из другой последовательности переносим в последовательность с. В результате получим (q+r)-серию.

Пусть длина списка S равна степени двойки, т.е. 2k, для некоторого натурального k. Разобьем последовательность S на два списка a и b, записывая поочередно элементы S в списки а и b. Сливаем списки a и b с образованием двойных серий, то есть одиночные элементы сливаются в упорядоченные пары, которые записываются попеременно в очереди c0 и c1. Переписываем очередь c0 в список a, очередь c1 – в список b. Вновь сливаем a и b с образованием серий длины 4 и т. д. На каждом итерации размер серий увеличивается вдвое. Сортировка заканчивается, когда длина серии превысит общее количество элементов в обоих списках. Если длина списка S не является степенью двойки, то некоторые серии в процессе сортировки могут быть короче.

Трудоёмкость метода прямого слияния определяется сложностью операции слияния серий. На каждой итерации происходит ровно n перемещений элементов списка и не более n сравнений. Количество итераций равно . Тогда

C < n, M=n+n.

Дополнительные n перемещений происходят во время начального расщепления исходного списка. Асимптотические оценки для М и С имеют следующий вид

С=О(n log n), М=О(n log n) при n → ∞.

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


 

Обход дерева слева направо

При обходе дерева слева направо выполняется обход левого поддерева, корня, правого поддерева.

Результат обхода: 4 2 5 1 3 6.

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

Обход слева направо(p: pVertex) 

IF(p NIL)

Обход слева направо (pLeft)

Печать(pData)

Обход слева направо (pRight)

FI

Приближенный алгоритм А2 построения ДОП

Дерево поиска, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска (ДОП). Средневзвешенная высота дерева с n вершинами:

hср=(w1h1+w2h2+...+wnhn)/W, где

wn – вес вершины Vn,пропорциональный частоте ее поиска

hn – высота, на к-рой расположена вершина Vn

W – вес дерева (сумма весов всех вершин)

Алгоритм (А2) использует предварительно упорядоченный набор вершин. В качестве корня выбирается такая вершина, что разность весов левого и правого поддеревьев была минимальна. Для этого путем последовательного суммирования весов определяем вершину Vk, для которой справедливы неравенства:

,  .

Тогда в качестве "центра тяжести" может быть выбрана вершина Vk, Vk-1 или Vk+1, т. е. вершина, для которой разность весов левого и правого поддерева минимальна. Далее действия повторяются для каждого поддерева.

Сложность алгоритма как функция от n (количество элементов) зависит следующим образом: время Т = О(n log n), память М = О(n) при n. (Время определяется трудоемкостью сортировки элементов, а память - размером массива для хранения элементов). Дерево, построенное приближенным алгоритмом А2, асимптотически приближается к оптимальному (с точки зрения средней высоты) при n.

Поиск вершины в дереве поиска

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

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

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

Поиск вершины с ключом Х 

p: = Root

DO (p NIL)

IF(pData < x) p:= pRight

ELSEIF (pData >x) p: = pLeft

ELSE

OD { pData = x }

OD 

IF (p NIL) <вершина найдена>

ELSE <вершина не найдена>

OD 

Максимальное количество сравнений при поиске равно Сmax = 2h, где h высота дерева.

Построение АВЛ-дерева

Дерево поиска называется сбалансированным по высоте, или АВЛ-деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.

Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавляем новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, ищем вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменяем структуру дерева для восстановления баланса с помощью процедур поворотов:

Адельсон - Вельский и Ландис доказали теорему, гарантирующую, что АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин: log(n+1) hАВЛ(n) < 1,44 log(n+2) - 0,328 при n.

Поиск элемента с заданным ключом, включение нового элемента, удаление элемента - каждое из этих действий в АВЛ-дереве можно произвести в худшем случае за О(log n) операций.


Основные структуры данных

Запись БД tRow

Структура хранит информацию о книге, считанную из БД (автор, название, издатель, год издания, количество страниц).

 tAuthor = array [1 .. 12] of char;

 tTitle = array [1 .. 32] of char;

 tPublisher = array [1 .. 16] of char;

 pRow = ^tRow;

 tRow = record

   Author: tAuthor;

   Title: tTitle;

   Publisher: tPublisher;

   Year: Word;

   PageCount: Word;

 end;

Элемент очереди tQueueItem

Структура хранит указатели на следующую структуру tQueueItem и на структуру tRow.

pQueueItem = ^tQueueItem;

tQueueItem = record

  Next: pQueueItem;

  Data: pRow;

end;

Очередь tQueue

Структура хранит указатели на первую и последние структуры списка tQueueItem. Используется при загрузке БД в память, поиске в БД.

pQueue = ^tQueue;

tQueue = record

 Head,

 Tail: pQueueItem;

end;

Вершина дерева tVertex

Структура хранит указатели на левую и правую дочерние вернины, данные, вес и баланс. Используется при работе с ДОП и АВЛ-деревом.

 pVertex = ^tVertex;

 tVertex = record

   Data: Word;

   Weight: Word;

   Balance: Integer;

   Left,

   Right: pVertex;

 end;

 

Динамический массив tArrayOfpRow

Массив хранит указатели на структуры tRow. Используется при поиске в упорядоченной БД.

 

pArrayOfpRow = ^tArrayOfpRow;

tArrayOfpRow = array [1 .. cMaxCount] of pRow;

Динамический массив tArrayOfpVertex

Массив хранит указатели на структуры tVertex. Используется при построении ДОП.

pArrayOfpVertex = ^tArrayOfpVertex;

tArrayOfpVertex = array [1 .. cMaxCount] of pVertex;


Исходный текст программы

program KR;

uses

 Crt, Dos;

const

 cMaxCount = 10000;

 {константа, определяющая максимальное число элементов в динамическом массиве}

 cPersonKeyLength = 3;

 {длина ключа поиска по названию книги}

 cYearKeyLength = 4;

 {длина ключа поиска по году издания книги}

 cMaxKeyLength = cYearKeyLength;

 {максимальная длина ключа поиска}

type

 tAuthor = array [1 .. 12] of char;

 {тип данных автора книги}

 tTitle = array [1 .. 32] of char;

 {тип данных названия книги}

 tPublisher = array [1 .. 16] of char;

 {тип данных издательства книги}

 pRow = ^tRow;

 {указатель на тип данных книги}

 tRow = record

 {тип данных книги}

   Author: tAuthor;

   Title: tTitle;

   Publisher: tPublisher;

   Year: Word;

   PageCount: Word;

 end;

 tKey = array [1 .. cMaxKeyLength] of char;

 {тип данных ключа поиска}

 pQueueItem = ^tQueueItem;

 {указатель на элемент очереди}

 tQueueItem = record

 {тип элемента очереди}

   Next: pQueueItem;

   Data: pRow;

 end;

 pQueue = ^tQueue;

 {указатель на очередь}

 tQueue = record

 {тип очереди}

   Head,

   Tail: pQueueItem;

 end;

 pArrayOfpRow = ^tArrayOfpRow;

 tArrayOfpRow = array [1 .. cMaxCount] of pRow;

 {типы для динамического массива}

 pVertex = ^tVertex;

 {указатель на вершину}

 tVertex = record

 {тип вершины дерева}

   Data: Word;

   Weight: Word;

   Balance: Integer;

   Left,

   Right: pVertex;

 end;

 FuncIsValidKeyChar = function(const c: char): Boolean;

 {процедурный тип для функции проверки допустимости введенного символа ключа поиска}

var

 Log: Text;

 {файл журнала программы}

 Count,

 {количество записей в БД}

 IndexSearchCount: Integer;

 {количество записей, найденных с помощью индексного массива}

 function GetQueue: pQueue; forward;

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

 procedure SortQueue(var s: pQueue); forward;

 {процедура сортировки очереди методом слияния}

 procedure AddItemToQueue(var s: pQueue; const r: pRow); forward;

 {функция добавления элемента в очередь}

 procedure DelQueue(var s: pQueue); forward;

 {процедура освобождения памяти, занимаемой очередью}

 function GetIndexArray(const q: pQueue): pArrayOfpRow; forward;

 {процедура создания индексного массива}

 procedure DelIndexArray(var a: pArrayOfpRow); forward;

 {процедура освобождения памяти, занимаемой индексным массивом}

 function FindKeyInArray(const a: pArrayOfpRow; const Key: array of char): pQueue; forward;

 {функция поиска в базе данных с помощью индексного массива}

 function GetTree(const q: pQueue): pVertex; forward;

 {функция построения дерева оптимального поиска (ДОП)}

 function FindKeyInTree(const Root: pVertex; const Key: Word): pVertex; forward;

 {функция поиска в ДОП}

 procedure DelTree(var p: pVertex); forward;

 {процедура освобождения памяти, занимаемой деревом}

 procedure PrintQueue(const q: pQueue); forward;

 {процедура вывода на экран очереди результатов поиска}

 procedure PrintQueueToLog(const q: pQueue); forward;

 {процедура вывода в файл жернала очереди результатов поиска}

 function IsValidPersonKeyChar(const c: char): Boolean; far; forward;

 {функция проверки валидности символа, введеного для ключа поиска по названию книги}

 function IsValidYearKeyChar(const c: char): Boolean; far; forward;

 {функция проверки валидности символа, введеного для ключа поиска по году издания книги}

 procedure GetKey(var Key: tKey;

   const KeyLength: Byte;

   const Msg: String;

   IsValidKeyChar: FuncIsValidKeyChar); forward;

 {процедура получения ключа поиска по названию или году издания в зависимости переданной

  функции проверки символа}

 function YearKeyToWord(const Year: tKey): Word; forward;

 {функция конвертации массива символов (ключ поиска - год издания) в тип Word}

 procedure OpenLog(var F: Text); forward;

 {процедура открытия файла журнала}

 procedure CloseLog(var F: Text); forward;

 {процедура закрытия файла журнала}

 procedure OpenLog(var F: Text);

 {процедура открытия файла журнала}

 var

   fPath: String;

   fDir: DirStr;

   fName: NameStr;

   fExt: ExtStr;

 begin

   fPath := ParamStr(0);

   FSplit(fPath, fDir, fName, fExt);

   Assign(F, fDir + 'KR.LOG');

   Rewrite(F);

 end;

 procedure CloseLog(var F: Text);

 {процедура закрытия файла журнала}

 begin

   Close(F);

 end;

 procedure AddItemToQueue(var s: pQueue; const r: pRow);

 {процедура добавления элемента в очередь}

 var

   p: pQueueItem;

 begin

   New(p);

   p^.Next := nil;

   p^.Data := r;

   s^.Tail^.Next := p;

   s^.Tail := p;

 end; {AddItemToQueue}

 function GetQueue: pQueue;

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

 type

   tDBFile = file of tRow;

 var

   s: pQueue;

   procedure OpenDB(var F: tDBFile);

   {процедура открытия файла базы данных}

   var

     fPath: String;

     fDir: DirStr;

     fName: NameStr;

     fExt: ExtStr;

   begin

     fPath := ParamStr(0);

     FSplit(fPath, fDir, fName, fExt);

     Assign(F, fDir + 'BASE1.DAT');

     Reset(F);

   end; {OpenDB}

   procedure CloseDB(var F: tDBFile);

   {процедура закрытия файла базы данных}

   begin

     Close(F);

   end; {CloseDB}

 var

   db: tDBFile;

   row: pRow;

 begin

   WriteLn('Загрузка БД в оперативную память ... ');

   New(s);

   s^.Tail := @s^.Head;

   OpenDB(db);

   Count := FileSize(db);

   while not Eof(db) do

   begin

     New(row);

     Read(db, row^);

     AddItemToQueue(s, row);

   end;

   CloseDB(db);

   GetQueue := s;

   WriteLn('  Загружено записей: ', Count);

   WriteLn(Log, 'Загружено в оперативную память записей: ', Count);

 end; {GetQueue}

 procedure SortQueue(var s: pQueue);

 {процедура сортировки очереди методом слияния}

   function Greater(const i1, i2: pQueueItem): Boolean;

   {функция сравнения элементов очереди;

    возвращает True если i1 > i2, иначе False}

   var

     i, l: Integer;

     s1, s2: tTitle;

   begin

     s1 := i1^.Data^.Title;

     s2 := i2^.Data^.Title;

     l := High(s1);

     i := 1;

     while (s1[i] = s2[i]) and (i < l) do

       Inc(i);

     Greater := s1[i] > s2[i];

   end; {Greater}

   procedure MoveItem(var i: pQueueItem; var q: tQueue);

   {процедура перемещения элемента в активную очередь}

   begin

     q.Tail^.Next := i;

     q.Tail := i;

     i := i^.Next;

     q.Tail^.Next := nil;

   end; {MoveItem}

 var

   a, b, {рабочие списки}

   x, y: pQueueItem; {рабочие указатели}

   c: array [0 .. 1] of tQueue; {массив из 2х очередей}

   i, {номер активной очереди}

   p, {предполагаемый размер серии}

   q, {фактический размер серии в списке a}

   r, {фактический размер серии в списке b}

   m: Integer; {текущее количество элементов в списках a и b}

 begin

   WriteLn('Сортировка БД');

   {расщепление очереди}

   a := s^.Head;

   b := s^.Head^.Next;

   x := a;

   y := b;

   while y <> nil do

   begin

     x^.Next := y^.Next;

     x := y;

     y := y^.Next;

   end;

   p := 1;

   while p < Count do

   begin

     c[0].Tail := pQueueItem(@c[0].Head);

     c[1].Tail := pQueueItem(@c[1].Head);

     i := 0;

     m := Count;

     while m > 0 do

     begin

       if m >= p then q := p else q := m;

       Dec(m, q);

       if m >= p then r := p else r := m;

       Dec(m, r);

       while (q <> 0) and (r <> 0) do

       {Слияние q-серии из списка а с r-серией из списка b, запись результата в активную очередь с}

       begin

         if Greater(a, b) then

         begin

           MoveItem(b, c[i]);

           Dec(r);

         end

         else

         begin

           MoveItem(a, c[i]);

           Dec(q);

         end;

       end; {while (q <> 0) and (r <> 0)}

       while q > 0 do

       begin

         MoveItem(a, c[i]);

         Dec(q);

       end;

       while r > 0 do

       begin

         MoveItem(b, c[i]);

         Dec(r);

       end;

       i := 1 - i;

     end; {while(m > 0)}

     a := c[0].Head;

     b := c[1].Head;

     p := p * 2;

   end; {while(p < Count)}

   s^.Head := c[1 - i].Head;

   WriteLn('  Выполнено');

 end; {SortQueue}

 procedure DelQueue(var s: pQueue);

 {процедура освобождения памяти, занимаемой очередью}

 var

   p: pQueueItem;

 begin

   p := s^.Head;

   while p <> nil do

   begin

     s^.Head := s^.Head^.Next;

     Dispose(p);

     p := s^.Head;

   end;

   Dispose(s);

   s := nil;

 end; {DelQueue}

 function GetIndexArray(const q: pQueue): pArrayOfpRow;

 {процедура создания индексного массива}

 var

   a: pArrayOfpRow;

   i: Integer;

   p: pQueueItem;

 begin

   WriteLn('Построение индексного массива');

   GetMem(a, SizeOf(pRow) * Count);

   p := q^.Head;

   for i := 1 to Count do

   begin

     a^[i] := p^.Data;

     p := p^.Next;

   end;

   GetIndexArray := a;

   WriteLn('  Выполнено');

 end; {GetIndexArray}

 procedure DelIndexArray(var a: pArrayOfpRow);

 {процедура освобождения памяти, занимаемой индексным массивом}

 begin

   FreeMem(a, SizeOf(pRow) * Count);

 end; {DelIndexArray}

 function FindKeyInArray(const a: pArrayOfpRow; const Key: array of char): pQueue;

 {функция поиска в базе данных с помощью индексного массива}

   function Equals(const s1, s2: array of char): Boolean;

   {функция сравнения массивов символов;

    возвращает True s1 = s2, иначе False}

   var

     i: Integer;

   begin

     i := 0;

     while s1[i] = s2[i] do

       Inc(i);

     Equals := i = cPersonKeyLength;

   end;

 var

   i: Integer;

   s: pQueue;

 begin

   IndexSearchCount := 0;

   New(s);

   s^.Head := nil;

   s^.Tail := @s^.Head;

   for i := 1 to Count do

     if Equals(a^[i]^.Title, Key) then

     begin

       AddItemToQueue(s, a^[i]);

       Inc(IndexSearchCount);

     end;

   FindKeyInArray := s;

   WriteLn('  Найдено книг: ', IndexSearchCount);

   WriteLn(Log, 'Найдено книг: ', IndexSearchCount);

 end; {FindKey}

 function GetTree(const q: pQueue): pVertex;

 {функция построения дерева оптимального поиска (ДОП)}

 type

   pArrayOfpVertex = ^tArrayOfpVertex;

   tArrayOfpVertex = array [1 .. cMaxCount] of pVertex;

   {типы для динамического массива, исаользуемого при построении ДОП}

 var

   a: pArrayOfpVertex;

   procedure A2(var Root: pVertex; const L, R: Integer);

   {процедура построения ДОП}

     procedure AddVertex(var r: pVertex; const v: pVertex);

     {процедура добавления вершины в ДОП}

     begin

       if r <> nil then

         if v^.Data < r^.Data then

           AddVertex(r^.Left, v)

         else

           AddVertex(r^.Right, v)

       else

         r := v;

     end; {AddVertex}

   var

     i, w, s: Integer;

   begin

     w := 0;

     s := 0;

     if L <= R then

     begin

        for i := L to R do

          w := w + a^[i]^.Weight;

        i := L;

        while i < R do

        begin

          if (s < w / 2) and ((s + a^[i]^.Weight) >= w / 2) then

            Break;

          s := s + a^[i]^.Weight;

          Inc(i);

        end;

        AddVertex(Root, a^[i]);

        A2(Root, L, i - 1);

        A2(Root, i + 1, R);

     end;

   end; {A2}

   function GetAVLTree(const q: pQueue): pVertex;

   {функция построения АВЛ-дерева}

   var

     flag: Boolean; {признак роста АВЛ-дерева}

     procedure AddVertex(var p: pVertex; const d: Word);

     {процедура добавления вершины в АВЛ-дерево}

     var

       v1, v2 : pVertex;

     begin

       if p = nil then

       begin

         New(p);

         with p^ do

         begin

           Data := d;

           Left := nil;

           Right := nil;

           Balance := 0;

           Weight := 1;

         end;

         flag := True;

       end {if p = nil}

       else

         if d < p^.Data then

         begin

           AddVertex(p^.Left, d);

           if flag then

             case p^.Balance of

               1: begin

                 p^.Balance := 0;

                 flag := false;

               end;

               0: p^.Balance := -1;

              -1: begin {балансировка дерева}

                 v1 := p^.Left;

                 if v1^.Balance = -1 then

                 begin {LL-поворот}

                   p^.Left := v1^.Right;

                   v1^.Right := p;

                   p^.Balance := 0;

                   p := v1;

                 end {LL}

                 else

                 begin {LR-поворот}

                   v2 := v1^.Right;

                   v1^.Right :=  v2^.Left;

                   v2^.Left := v1;

                   p^.Left := v2^.Right;

                   v2^.Right := p;

                   if v2^.Balance = -1 then

                     p^.Balance := 1

                   else

                     p^.Balance := 0;

                   if v2^.Balance = 1 then

                     v1^.Balance := -1

                   else

                     v1^.Balance := 0;

                   p := v2;

                 end; {LR}

                 p^.Balance := 0;

                 flag := false

               end {балансировка дерева}

             end {case p^.Balance}

           end {if d < p^.Data}

           else if d > p^.Data then

           begin

             AddVertex(p^.Right, d);

             if flag then

               case p^.Balance of

                 -1: begin

                    p^.Balance := 0;

                    flag := false;

                 end;

                 0: p^.Balance := 1;

                 1: begin {балансировка дерева}

                   v1 := p^.Right;

                   if v1^.Balance = 1 then

                   begin {RR-поворот}

                     p^.Right := v1^.Left;

                     v1^.Left := p;

                     p^.Balance := 0;

                     p := v1;

                   end {RR}

                   else

                   begin {RL-поворот}

                     v2 := v1^.Left;

                     v1^.Left :=  v2^.Right;

                     v2^.Right := v1;

                     p^.Right := v2^.Left;

                     v2^.Left := p;

                     if v2^.Balance = 1 then

                       p^.Balance := -1

                     else

                       p^.Balance := 0;

                     if v2^.Balance = -1 then

                       v1^.Balance := 1

                     else

                       v1^.Balance := 0;

                     p := v2;

                   end; {RL}

                   p^.Balance := 0;

                   flag := false

                 end {балансировка дерева}

               end {case p^.Balance}

           end {if d > p^.Data}

           else {if d = p^.Data}

             Inc(p^.Weight);

     end; {AddVertex}

   var

     Root: pVertex;

     Item: pQueueItem;

   begin

     Root := nil;

     Item := q^.Head;

     flag := False;

     while Item <> nil do

     begin

       AddVertex(Root, Item^.Data^.Year);

       Item := Item^.Next;

     end;

     GetAVLTree := Root;

   end; {GetAVLTree}

   procedure DelAVLTree(const a: pArrayOfpVertex; const ItemCount: Integer);

   {процедура удаления АВЛ-дерева}

   var

     i: Integer;

   begin

     for i := 1 to ItemCount do

     begin

       a^[i]^.Left := nil;

       a^[i]^.Right := nil;

     end;

   end; {DelAVLTree}

   function GetIndexArray(const Root: pVertex; const ItemCount: Integer): pArrayOfpVertex;

   {процедура построения индексного массива, используемого при построении ДОП}

   var

     a: pArrayOfpVertex;

     i: Integer;

     procedure WalkTreeL2R(const p: pVertex);

     {процедура обхода дерева слева направо и

      инициализации упорядоченного индексного массива}

     begin

       if p <> nil then

       begin

         WalkTreeL2R(p^.Left);

         a^[i] := p;

         Inc(i);

         WalkTreeL2R(p^.Right);

       end;

     end;

   begin

     i := 1;

     GetMem(a, SizeOf(pVertex) * ItemCount);

     WalkTreeL2R(Root);

     GetIndexArray := a;

   end; {GetIndexArray}

   procedure DelIndexArray(var a: pArrayOfpVertex; const ItemCount: Integer);

   {процедура удаления индексного массива}

   begin

     FreeMem(a, SizeOf(pVertex) * ItemCount);

   end; {DelIndexArray}

   function GetSize(const p: pVertex): Integer;

   {функция для расчета размера дерева}

   begin

     if p = nil then

       GetSize := 0

     else

       GetSize := 1 + GetSize(p^.Left) + GetSize(p^.Right);

   end; {GetSize}

   procedure PrintIndexArray(const a: pArrayOfpVertex; const ItemCount: Integer);

   {процедура вывода в журнал индексного массива}

   var

     i: Integer;

   begin

     WriteLn(Log, 'Массив для построения ДОП (', ItemCount, ' элементов):');

     for i := 1 to ItemCount do

       with a^[i]^ do

         WriteLn(Log, Data:5, '(', Weight:2, ')');

     WriteLn(Log);

   end; {PrintIndexArray}

   procedure PrintTree(const p: pVertex; const Msg: String);

   {процедура вывода дерева в журнал}

     procedure _PrintTree(p: pVertex; Level: Integer);

     var

       i: Integer;

     begin

       if p <> nil then

       begin

         _PrintTree(p^.Right, Level + 1);

         for i := 1 to Level do

           Write(Log, '    ');

         WriteLn(Log, p^.Data:4, '(', p^.Weight:2, ')');

         _PrintTree(p^.Left, Level + 1);

       end;

     end;

   begin

     WriteLn(Log, Msg);

     _PrintTree(p, 1);

     WriteLn(Log);

   end; {PrintTree}

 var

   Root: pVertex;

   Size: Word;

 begin

   WriteLn('Построение дерева оптимального поиска (ДОП)');

   Root := GetAVLTree(q);

   PrintTree(Root, 'АВЛ-дерево:');

   Size := GetSize(Root);

   a := GetIndexArray(Root, Size);

   PrintIndexArray(a, Size);

   DelAVLTree(a, Size);

   Root := nil;

   A2(Root, 1, Size);

   DelIndexArray(a, Size);

   PrintTree(Root, 'ДОП (алгоритм А2):');

   GetTree := Root;

   WriteLn('  Выполнено');

 end; {GetTree}

 function FindKeyInTree(const Root: pVertex; const Key: Word): pVertex;

 {функция поиска в дереве вершины по заданному ключу}

 var

   p: pVertex;

   c: Word;

 begin

   p := Root;

   while (p^.Data <> Key) and (p <> nil) do

   begin

     if p^.Data < Key then

       p := p^.Right

     else

       if p^.Data > Key then

         p := p^.Left;

   end;

   if p <> nil then c := p^.Weight else c := 0;

   WriteLn('  Найдено книг, изданных в ', Key, ' году: ', c);

   WriteLn(Log, 'Найдено книг, изданных в ', Key, ' году: ', c);

   FindKeyInTree := p;

 end; {FindKeyInTree}

 procedure DelTree(var p: pVertex);

 {процедура освобождения памяти, занимаемой деревом поиска}

 begin

   if p <> nil then

   begin

     DelTree(p^.Left);

     DelTree(p^.Right);

     Dispose(p);

     p := nil;

   end;

 end; {DelTree}

 procedure PrintBookInfo(var F: Text; const BI: pRow);

 {процедура вывода в заданный файл информации о книге}

 begin

   with BI^ do

     WriteLn(F,

       Author,

       ' "', Title, '": ',

       Publisher,  ',',

       Year:5, ',',

       PageCount:4, ' с.')

 end; {PrintBookInfo}

 procedure PrintQueue(const q: pQueue);

 {процедура вывод на экран очереди с результатами поиска}

 var

   p: pQueueItem;

   RowNo: Integer;

   procedure PrintHorLine;

   begin

     WriteLn('-------------------------------------------------------------------------------');

   end; {PrintHorLine}

   function NeedsToContinue: Boolean;

   {функция проверки необходимости продолжения вывода на экран результатов поиска и печати "шапки" результатов}

     procedure PrintTableHeader;

     begin

       clrscr;

       PrintHorLine;

       WriteLn('   Автор                  Заглавие                 Издательство    Год   Ч.стр.');

       PrintHorLine;

     end;

   const

     cRowsPerScreen = 19;

   begin

     if RowNo = cRowsPerScreen then

     begin

       Write(#13#10'Для продолжения просмотра нажмите любую клавишу (ESC для прекращения) ...');

       if ReadKey = #27 then

         NeedsToContinue := False

       else

       begin

         WriteLn;

         RowNo := 0;

         NeedsToContinue := True;

       end;

     end

     else

       NeedsToContinue := True;

     if RowNo = 0 then

       PrintTableHeader;

   end;

 begin

   p := q^.Head;

   RowNo := 0;

   while (p <> nil) and NeedsToContinue do

   begin

     PrintBookInfo(Output, p^.Data);

     p := p^.Next;

     Inc(RowNo);

   end;

   PrintHorLine;

 end; {PrintQueue}

 procedure PrintQueueToLog(const q: pQueue);

 {вывод очереди в файл журнала}

 var

   p: pQueueItem;

 begin

   p := q^.Head;

   while p <> nil do

   begin

     PrintBookInfo(Log, p^.Data);

     p := p^.Next;

   end;

   WriteLn(Log);

 end; {PrintQueueToLog}

 function IsValidPersonKeyChar(const c: char): Boolean;

 {функция проверки валидности символа, введенного для ключа поиска по названию книги}

 begin

   case c of

     #65  .. #90  {A .. Z},

     #97  .. #122 {a .. z},

     #128 .. #159 {А .. Я},

     #160 .. #239 {а .. я}:

     IsValidPersonKeyChar := True

   else

     IsValidPersonKeyChar := False;

   end;

 end; {IsValidPersonKeyChar}

 function IsValidYearKeyChar(const c: char): Boolean;

 {функция проверки валидности символа, введенного для ключа поиска по года издания книги}

 begin

   case c of

     #48 .. #57: {0 .. 9}

     IsValidYearKeyChar := True

   else

     IsValidYearKeyChar := False;

   end;

 end; {IsValidYearKeyChar}

 procedure GetKey(

   var Key: tKey;

   const KeyLength: Byte;

   const Msg: String;

   IsValidKeyChar: FuncIsValidKeyChar);

 {процедура получения ключа поиска по названию или году издания в зависимости переданной

  функции проверки символа}

 var

   c: char;

   i: Integer;

   procedure Error;

   begin

     Sound(500);

     Delay(50);

     NoSound;

     c := #0;

   end; {Error}

 begin

   Write(Msg);

   i := 1;

   repeat

     c := ReadKey;

     if IsValidKeyChar(c) then

if i <= KeyLength then

       begin

         Write(c);

         Key[i] := c;

  Inc(i);

       end

else

  Error

     else

     case c of

       #13: if i <= KeyLength then

  Error;

       #8: if i > 1 then

       begin

         Write(c);

         Key[i] := #0;

  Dec(i);

         clreol;

       end

else

  Error;

     else

       Error;

     end;

   until c = #13;

   WriteLn;

 end; {GetKey}

 function YearKeyToWord(const Year: tKey): Word;

 {функция конвертации массива символов (ключ поиска - год издания) в тип Word}

 var

   i, k: Word;

 begin

   k := 0;

   for i := 1 to cMaxKeyLength do

     k := k + Trunc((Ord(Year[i]) - 48) * Exp(Ln(10) * (cMaxKeyLength - i)));

   YearKeyToWord := k;

 end; {YearKeyToWord}

 procedure PrintKRInfo;

 {процедура вывода на экран информации о работе}

 begin

   clrscr;

   WriteLn('            Курсовая работа'#13#10);

   WriteLn('              (вариант 3)'#13#10);

 end;

var

 q: pQueue;

 a: pArrayOfpRow;

 t: pVertex;

 Key: tKey;

begin

 OpenLog(Log);

 PrintKRInfo;

 q := GetQueue;

 SortQueue(q);

 a := GetIndexArray(q);

 DelQueue(q);

 GetKey(Key,

   cPersonKeyLength,

   'Введите ключ поиска в массиве по названию книги (3 первые буквы фамилии): ',

   IsValidPersonKeyChar);

 q := FindKeyInArray(a, Key);

 DelIndexArray(a);

 if IndexSearchCount <> 0 then

 begin

   PrintQueueToLog(q);

   Write('  Для просмотра результатов поиска нажмите любую клашу (ESC для продолжения) ...');

   if ReadKey <> #27 then

     PrintQueue(q);

   t := GetTree(q);

   GetKey(Key,

     cYearKeyLength,

     'Введите ключ поиска в ДОП (год издания): ',

     IsValidYearKeyChar);

   FindKeyInTree(t, YearKeyToWord(Key));

   DelTree(t);

 end;

 DelQueue(q);

 CloseLog(Log);

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

Действия, выполняемые программой, последовательно выводятся на экран:

Результаты поиска в упорядоченной базе данных выводятся на экран, если это согласовано пользователем:


Содержимое файла протокола программы KR.LOG:

Загружено в оперативную память записей: 4000

Найдено книг: 125

Зосимова Т М "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1918, 337 с.

Янов У А     "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1904, 120 с.

Батыров К И  "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1963, 266 с.

Жакова У Н   "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1954, 527 с.

Архипов К В  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1957, 644 с.

Патриков И Г "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1906, 158 с.

Евграфов А Л "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1910, 517 с.

Янов У А     "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1967, 698 с.

Остапов Г Л  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1976, 777 с.

Зосимова В М "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1956, 227 с.

Евграфов А Л "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1958, 152 с.

Жакова Й Н   "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1968, 611 с.

Янов В З     "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1906, 883 с.

Зосимова Т М "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1931, 344 с.

Глебов М В   "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1926, 128 с.

Жакова С В   "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1983, 657 с.

Патриков Е Н "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1976, 373 с.

Архипова П Р "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1973, 386 с.

Архипов С П  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1937, 340 с.

Климова Б С  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1913, 844 с.

Зосимов Е Ж  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1907, 360 с.

Зосимов Й У  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1995, 700 с.

Батыров К И  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1937, 798 с.

Евграфов Е У "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1906, 371 с.

Зосимов Т Б  "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1993, 695 с.

Жакова У Н   "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1946, 239 с.

Власов Б И   "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1937, 163 с.

Остапов Г Ж  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1997, 326 с.

Глебова О Е  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1935, 300 с.

Жаков У П    "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1910, 367 с.

Хасанов П Б  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1910, 239 с.

Тихонов Н Д  "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1952, 637 с.

Жакова С В   "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1916, 508 с.

Сабиров Н Т  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1997, 669 с.

Евграфов А Л "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1942, 699 с.

Сабиров Р Н  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1975, 347 с.

Архипова П О "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1992, 244 с.

Архипов В Р  "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1962, 367 с.

Жаков Л Д    "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1994, 629 с.

Феофанов Л Ж "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1973, 229 с.

Феофанов Б А "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1943, 497 с.

Батырова С К "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1993, 163 с.

Сабиров Р Н  "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1920, 130 с.

Муамаров Ж Н "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1918, 826 с.

Муамаров И Л "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1946, 193 с.

Муамаров И Л "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1989, 163 с.

Евграфов А Л "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1970, 609 с.

Батырова С К "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1916, 120 с.

Евграфов Е У "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1987, 414 с.

Глебова Е И  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1928, 813 с.

Сабиров Р А  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1917, 704 с.

Жаков Л Д    "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1939, 135 с.

Евграфов Е У "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1939, 663 с.

Муамаров Ж Н "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1973, 821 с.

Архипов С З  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1988, 860 с.

Зосимов Е Ж  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1898, 124 с.

Архипов В Р  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1990, 283 с.

Архипов В К  "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1989, 231 с.

Сабиров Р А  "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1976, 407 с.

Архипов В К  "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1993, 702 с.

Феофанов Б А "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1924, 223 с.

Климова Б С  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1905, 672 с.

Жаков Л Д    "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1981, 799 с.

Патриков Е Н "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1986, 203 с.

Батырова С К "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1909, 497 с.

Архипова П Р "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1925, 540 с.

Глебова Е И  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1922, 822 с.

Архипов Е Л  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1955, 831 с.

Тихонов Н Д  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1984, 548 с.

Феофанов Л Ж "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1969, 374 с.

Тихонов Н Д  "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1901, 334 с.

Зосимова В М "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1934, 683 с.

Сабиров Р Н  "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1994, 101 с.

Патриков Л У "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1954, 520 с.

Янов В З     "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1944, 560 с.

Зосимова В М "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1927, 682 с.

Тихонова Д Ж "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1946, 330 с.

Тихонова Д Ж "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1923, 818 с.

Остапов Г Ж  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1898, 583 с.

Патриков Е Н "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1997, 564 с.

Жакова С В   "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1926, 147 с.

Сабиров К С  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1975, 300 с.

Феофанов Л Ж "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1996, 673 с.

Жакова Й Н   "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1915, 432 с.

Патриков И Г "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1899, 875 с.

Глебова Е И  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1923, 834 с.

Зосимов Й У  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1938, 269 с.

Сабирова Е З "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1971, 147 с.

Янов В З     "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1899, 707 с.

Сабиров Т У  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1906, 169 с.

Остапов Г Л  "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1953, 880 с.

Сабиров К С  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1975, 269 с.

Янов И К     "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1922, 713 с.

Патриков Е Н "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1923, 406 с.

Ахмедов К Й  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1979, 195 с.

Климов М А   "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1971, 571 с.

Остапов Т Т  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1947, 804 с.

Зосимов Й У  "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1959, 283 с.

Сабиров Н Т  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1978, 112 с.

Глебова Е И  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1952, 282 с.

Жакова С В   "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1995, 164 с.

Зосимов Й У  "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1955, 231 с.

Гедеонов М С "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1948, 757 с.

Архипов В К  "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1966, 213 с.

Батыров К И  "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1917, 792 с.

Муамаров Ж Н "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1985, 788 с.

Архипова П Р "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1982, 316 с.

Зосимов З У  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1942, 359 с.

Глебова О Е  "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1945, 364 с.

Феофанов Л Ж "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1920, 483 с.

Хасанов Б Д  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1994, 207 с.

Климова Б С  "Зосим Ромуальдович Хасанов     ": Герасимов and Co, 1910, 377 с.

Зосимов З У  "Зосим Ромуальдович Хасанов     ": Жаков и сыновья , 1951, 215 с.

Жакова У Н   "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1992, 449 с.

Феофанов Л Д "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1997, 743 с.

Евграфов Е У "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1982, 134 с.

Гедеонов Й С "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1928, 350 с.

Янов И К     "Зосим Ромуальдович Хасанов     ": Феофанов-Edition, 1990, 314 с.

Остапов Г Л  "Зосим Ромуальдович Хасанов     ": Зосимов Ltd     , 1922, 381 с.

Сабиров Р Н  "Зосим Ромуальдович Хасанов     ": Жаков Ltd       , 1940, 195 с.

Евграфов Е У "Зосим Ромуальдович Хасанов     ": Батыров Ltd     , 1943, 740 с.

Архипов В Р  "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1936, 648 с.

Феофанов Л Ж "Зосим Ромуальдович Хасанов     ": Архипов Ltd     , 1920, 492 с.

Муамаров К Н "Зосим Ромуальдович Хасанов     ": Феофанов and Co , 1914, 862 с.

Патриков Л У "Зосим Ромуальдович Хасанов     ": Патриков Ltd    , 1924, 246 с.

АВЛ-дерево:

                       1997( 4)

                           1996( 1)

                   1995( 2)

                       1994( 3)

               1993( 3)

                   1992( 2)

                       1990( 2)

           1989( 2)

                           1988( 1)

                       1987( 1)

                   1986( 1)

                           1985( 1)

                       1984( 1)

               1983( 1)

                           1982( 2)

                       1981( 1)

                   1979( 1)

                       1978( 1)

       1976( 3)

                       1975( 3)

                   1973( 3)

                       1971( 2)

               1970( 1)

                   1969( 1)

                       1968( 1)

           1967( 1)

                       1966( 1)

                   1963( 1)

               1962( 1)

                       1959( 1)

                   1958( 1)

   1957( 1)

                       1956( 1)

                           1955( 2)

                   1954( 2)

                           1953( 1)

                       1952( 2)

                               1951( 1)

                           1948( 1)

                               1947( 1)

               1946( 3)

                           1945( 1)

                       1944( 1)

                           1943( 2)

                   1942( 2)

                           1940( 1)

                       1939( 2)

                           1938( 1)

           1937( 3)

                           1936( 1)

                       1935( 1)

                           1934( 1)

                   1931( 1)

                       1928( 2)

                           1927( 1)

               1926( 2)

                       1925( 1)

                   1924( 2)

                           1923( 3)

                       1922( 3)

                           1920( 3)

       1918( 2)

                       1917( 2)

                   1916( 2)

                           1915( 1)

                       1914( 1)

                           1913( 1)

               1910( 4)

                       1909( 1)

                   1907( 1)

           1906( 4)

                   1905( 1)

               1904( 1)

                       1901( 1)

                   1899( 2)

                       1898( 2)

Массив для построения ДОП (76 элементов):

1898( 2)

1899( 2)

1901( 1)

1904( 1)

1905( 1)

1906( 4)

1907( 1)

1909( 1)

1910( 4)

1913( 1)

1914( 1)

1915( 1)

1916( 2)

1917( 2)

1918( 2)

1920( 3)

1922( 3)

1923( 3)

1924( 2)

1925( 1)

1926( 2)

1927( 1)

1928( 2)

1931( 1)

1934( 1)

1935( 1)

1936( 1)

1937( 3)

1938( 1)

1939( 2)

1940( 1)

1942( 2)

1943( 2)

1944( 1)

1945( 1)

1946( 3)

1947( 1)

1948( 1)

1951( 1)

1952( 2)

1953( 1)

1954( 2)

1955( 2)

1956( 1)

1957( 1)

1958( 1)

1959( 1)

1962( 1)

1963( 1)

1966( 1)

1967( 1)

1968( 1)

1969( 1)

1970( 1)

1971( 2)

1973( 3)

1975( 3)

1976( 3)

1978( 1)

1979( 1)

1981( 1)

1982( 2)

1983( 1)

1984( 1)

1985( 1)

1986( 1)

1987( 1)

1988( 1)

1989( 2)

1990( 2)

1992( 2)

1993( 3)

1994( 3)

1995( 2)

1996( 1)

1997( 4)

ДОП (алгоритм А2):

                   1997( 4)

                           1996( 1)

                       1995( 2)

               1994( 3)

                   1993( 3)

                       1992( 2)

           1990( 2)

                       1989( 2)

                           1988( 1)

                   1987( 1)

                           1986( 1)

                       1985( 1)

               1984( 1)

                           1983( 1)

                       1982( 2)

                   1981( 1)

                           1979( 1)

                       1978( 1)

       1976( 3)

                       1975( 3)

                   1973( 3)

               1971( 2)

                           1970( 1)

                       1969( 1)

                           1968( 1)

                   1967( 1)

                           1966( 1)

                       1963( 1)

           1962( 1)

                           1959( 1)

                       1958( 1)

                           1957( 1)

                   1956( 1)

                       1955( 2)

               1954( 2)

                           1953( 1)

                       1952( 2)

                   1951( 1)

                           1948( 1)

                       1947( 1)

   1946( 3)

                           1945( 1)

                       1944( 1)

                   1943( 2)

                       1942( 2)

                           1940( 1)

               1939( 2)

                       1938( 1)

                   1937( 3)

                       1936( 1)

           1935( 1)

                           1934( 1)

                       1931( 1)

                   1928( 2)

                       1927( 1)

               1926( 2)

                           1925( 1)

                       1924( 2)

                   1923( 3)

       1922( 3)

                   1920( 3)

                       1918( 2)

               1917( 2)

                       1916( 2)

                   1915( 1)

                           1914( 1)

                       1913( 1)

           1910( 4)

                           1909( 1)

                       1907( 1)

                   1906( 4)

               1905( 1)

                           1904( 1)

                       1901( 1)

                   1899( 2)

                       1898( 2)

Найдено книг, изданных в 1909 году: 1


 

А также другие работы, которые могут Вас заинтересовать

67044. Вмій дружбою дорожити 132 KB
  Тип заходу: метод проектів створення колективної творчої роботи сюжетного малюнка на дошці по сценарію заходухлопчик з дівчинкою друзі під сонцем з написом ДРУЖБА промені якого містять Золоті правила спілкування хмаринки уточнення поняття дружби в небі птахи на крилах яких поради...
67045. Година здоров’я «Богатирські яблука» 44.5 KB
  Мета: ознайомити дітей з корисними властивостями яблука, зміцнювати здоров’я дітей, розвивати бажання пізнати нове, розширювати знання дітей про яблука, виховувати естетичний смак, дбайливе ставлення до природи, прагнення дітей бути здоровими, сильними.
67046. ДЗВОНИ СКОРБОТИ 53.5 KB
  А навесні цього ж року в Україні помирало 25 тисяч людей щодня 1000 щогодини 17 щохвилини. Зокрема постанова Раднаркому УРСР Про заходи підсилення хлібозаготівлі яку було ухвалено 20 листопада 1932 року за своїм змістом нагадувала смертний вирок: З оголошенням цієї постанови припинили видачу будьяких натуральних авансів...
67047. ДЕНЬ ПАМ’ЯТІ ЖЕРТВ ГОЛОДОМОРУ 50.5 KB
  Не звільняється пам'ять відлунює знову роками. Сталося це літа Божого 1932го Сталося це літа Божого Яке запам'ятається кожному Навічно важко гірко. Запізнілими дзвонами шукаємо мільйони українських душ щоб вписати їх в історію Пам'яті.
67048. Золотий голос України 1017 KB
  Мета: розширити і закріпити знання учнів про птахів про їхню поведінку спосіб життя спілкування роль і місце у природі значення у житті людини; розвивати допитливість спостережливість інтерес до пташиного світу; виховувати у школярів любов та бережливе ставлення до пернатих.
67049. Сценарій відкриття фестивалю «Гончарівські читання» 124.5 KB
  Щедра земля під високим волошковим небом, омита синіми водами моря, що наввипередки вихваляються своїми білопінними хвилями. Сині плеса озер, що манять своєю прохолодою, ріки – швидкоплинні, гірські, бурхливі, повноводні. Ти - глибока й неймовірно бездонна в голубих, наче ніжні незабудки...
67050. Гра – подорож для учнів 3 класу 98 KB
  Мета: формувати у дітей усвідомлення цінності власного життя та здоров’я; розширити і збагатити знання учнів про овочі, їхні лікувальні властивості; спонукати до творчої активності, викликати свідоме бажання дізнатись щось нове і самостійно знаходити відповіді на поставлені запитання...
67051. Кримські гори 79 KB
  Назви заповідники Карпат Карпатський Горгани Ви добре засвоїли особливості місцевості Карпатських гір а сьогодні ми ознайомимося з природною зоною півдня України виконавши завдання природничого диктанту. Риба яка поширена в річках Карпатських гір форель. Хижий птах карпатських гір орел.
67052. ПРАВИЛА ГОСТИННОСТІ 33 KB
  Гостинність – уміння так прийняти гостей, щоб їм було добре, приємно, цікаво. Якщо ви запросили свого товариша до себе в гості, повинні подбати про те, щоб гість гарно провів час. До зустрічі слід підготуватися заздалегідь: Прибрати; Самому гарно одягнутися; Бути доброзичливим, до гостя ставитися з повагою...