Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Регистрация постояльцев в гостинице

Регистрация постояльцев в гостинице

Разработка информационной системы для регистрации постояльцев в гостинице с использованием структур данных и алгоритмов. Методы хеширования и сортировки данных. Обходы бинарных деревьев. Линейный однонаправленный список. Описание и тестирование программы.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 09.03.2014
Размер файла 2,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Размещено на http://www.allbest.ru/

САНКТ - ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Отчет по курсовой работе

По предмету Структуры и алгоритмы обработки данных

На тему:

Регистрация постояльцев в гостинице

Выполнил студент 4836 группы:

Колпачков Михаил

Проверил: Матьяш В.А.

Санкт - Петербург 2010 г.

Содержание

  • Введение
  • 1. Алгоритмы и структуры данных
  • 1.1 Хеш-таблицы. Открытое Хеширование
  • 1.2 АВЛ-дерево
  • 1.3 Обходы бинарных деревьев
  • 1.4 Сортировка пузырьком
  • 1.5 Алгоритм Боуера и Мура (БМ)
  • 1.6 Линейный однонаправленный список
  • 4. Описание программы
  • 5. Тестирование программы
  • Заключение
  • Список использованной литературы

Задание на курсовой проект

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

предметная область - Регистрация постояльцев в гостинице;

метод хеширования - Открытое хеширование;

метод сортировки - Пузырьковый;

вид списка - Линейный однонаправленный;

метод обхода дерева - Прямой;

алгоритм поиска слова в тексте - Боуера и Мура (БМ).

1 Информационная система для предметной области "Регистрация постояльцев в гостинице" должна осуществлять ввод, хранение, обработку и вывод данных о:

постояльцах;

гостиничных номерах;

вселении и выселении постояльцев.

2 Данные о каждом постояльце должны содержать:

№ паспорта - строка формата "NNNN-NNNNNN", где N - цифры;

ФИО - строка;

Год рождения - целое;

Адрес - строка;

Цель прибытия - строка.

Примечание - длина строк (кроме № паспорта) определяется студентом самостоятельно.

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

4 Данные о каждом гостиничном номере должны содержать:

программа алгоритм сортировка хеширование

№ гостиничного номера - строка формата "ANNN", где A - буква, обозначающая тип номера (Л - люкс, П - полулюкс, О - одноместный, М - многоместный), NNN - порядковый номер (цифры);

Количество мест - целое;

Количество комнат - целое;

Наличие санузла - логическое;

Оборудование - строка.

Примечание - длина строки "Оборудование", содержащая перечень оборудования номера (телевизор, холодильник и пр.) определяется студентом самостоятельно.

5 Данные о гостиничных номерах должны быть организованны в виде АВЛ-дерева поиска, упорядоченного по "№ гостиничного номера".

6 Данные о вселении или выселении постояльцев должны содержать:

№ паспорта - строка, формат которой соответствует аналогичной строке в данных о постояльцах;

№ гостиничного номера - строка, формат которой соответствует аналогичной строке в данных о гостиничных номерах;

Дата заселения - строка;

Дата выселения - строка.

Примечания:

А) Наличие в этих данных записи, содержащей в поле "№ паспорта" значение X и в поле "№ гостиничного номера" значение Y означает заселение постояльца с номером паспорта X в гостиничный номер Y. Отсутствие такой записи означает, что постоялец с номером паспорта X не проживает в гостиничном номере Y.

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

7 Данные о вселении или выселении постояльцев должны быть организованны в виде списка, который упорядочен по первичному ключу - "№ гостиничного номера". Вид списка и метод сортировки определяются вариантом задания.

8 Информационная система "Регистрация постояльцев в гостинице" должна осуществлять следующие операции:

регистрация нового постояльца;

удаление данных о постояльце;

просмотр всех зарегистрированных постояльцев;

очистка данных о постояльцах;

поиск постояльца по № паспорта. Результаты поиска - все сведения о найденном постояльце и № гостиничного номера, в котором он проживает;

поиск постояльца по ФИО. Результаты поиска - список найденных постояльцев с указанием № паспорта и ФИО;

добавление нового гостиничного номера;

удаление сведений о гостиничном номере;

просмотр всех имеющихся гостиничных номеров;

очистка данных о гостиничных номерах;

поиск гостиничного номера по "№ гостиничного номера". Результаты поиска - все сведения о найденном гостиничном номере, а также ФИО и № паспортов постояльцев, которые вселены в этот гостиничный номер;

поиск гостиничного номера по фрагментам "Оборудования". Результаты поиска - список найденных гостиничных номеров с указанием "№ гостиничного номера, количества мест, количества комнат, оборудования;

регистрация вселения постояльца;

регистрация выселения постояльца.

9 Состав данных о постояльцах или гостиничных номерах, выдаваемых при просмотре всех зарегистрированных постояльцев или просмотре всех имеющихся гостиничных номеров, определяется студентом самостоятельно, но должен содержать не менее двух полей.

10 Метод поиска постояльца по ФИО определяется студентом самостоятельно. Выбранный метод необходимо сравнить с альтернативными методами.

11 Поиск гостиничного номера по фрагментам "Оборудования" должен осуществляться путем систематического обхода АВЛ-дерева поиска. Метод обхода определяется вариантом задания. При поиске гостиничного номера по фрагментам "Оборудования" могут быть заданы как полный перечень оборудования гостиничного номера, так и его часть (например, указан только телевизор). Для обнаружения заданного фрагмента в полном перечне оборудования гостиничного номера должен применяться алгоритм поиска слова в тексте, указанный в варианте задания.

12 Регистрация вселения постояльца должна осуществляться только при наличии свободных мест в занимаемом гостиничном номере.

Введение

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

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

ввод, хранение, обработку и вывод данных о постояльцах;

ввод, хранение, обработку и вывод данных о гостиничных номерах;

ввод, хранение, обработку и вывод данных о вселении и выселении постояльцев.

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

1.1 Хеш-таблицы. Открытое Хеширование

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией.

Например, на hashTable рис. 1 - это массив из 8 элементов. Каждый элемент представляет собой указатель на линейный список, хранящий числа. Хеш-функция в этом примере просто делит ключ на 8 и использует остаток как индекс в таблице. Это дает нам числа от 0 до 7. Поскольку для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм гарантирует допустимые значения индексов.

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

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

Рис. 1: Хеш-таблица

Чтобы вставить в таблицу новый элемент, мы хешируем ключ, чтобы определить список, в который его нужно добавить, затем вставляем элемент в начало этого списка. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует разместить в списке, на начало которого указывает hashTable [3]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий.

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

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай - когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько из возможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 битах, unsigned short int - в 16, unsigned long int - в 32.

II. Деление (размер таблицы hashTableSize - простое число). Этот метод использован в последнем примере. Хеширующее значение hashValue, изменяющееся от 0 до (hashTableSize - 1), равно остатку от деления ключа на размер хеш-таблицы. Вот как это может выглядеть:

typedef int HashIndexType;

HashIndexType Hash (int Key) {

return Key % HashTableSize;

}

Для успеха этого метода очень важен выбор подходящего значения hashTableSize. Если, например, hashTableSize равняется двум, то для четных ключей хеш-значения будут четными, для нечетных - нечетными. Ясно, что это нежелательно - ведь если все ключи окажутся четными, они попадут в один элемент таблицы. Аналогично, если все ключи окажутся четными, то hashTableSize, равное степени двух, попросту возьмет часть битов Key в качестве индекса. Чтобы получить более случайное распределение ключей, в качестве hashTableSize нужно брать простое число, не слишком близкое к степени двух.

III. Мультипликативный метод (размер таблицы hashTableSize есть степень 2n). Значение key умножается на константу, затем от результата берется n бит. В качестве такой константы Кнут рекомендует золотое сечение (sqrt (5) - 1) /2 = 0.6180339887499. Пусть, например, мы работаем с таблицей из hashTableSize=32 (25) элементов, хэширование производится байтами (8 бит, unsigned char). Тогда необходимый множитель: 28*sqrt (5) - 1) /2 = 158.

IV. Далее, умножая 8-битовый ключ на 158, будем получать некоторое 16-битное число. Для таблицы длиной 25 в качестве хеширующего значения берем 5 старших битов младшего слова, содержащего такое произведение. Вот как можно реализовать этот метод:

/* 8-bit index */

typedef unsigned char HashIndexType;

static const HashIndexType K = 158;

/* 16-bit index */

typedef unsigned short int HashIndexType;

static const HashIndexType K = 40503;

/* 32-bit index */

typedef unsigned long int HashIndexType;

static const HashIndexType K = 2654435769;

/* w=bitwidth (HashIndexType), size of table=2**m */

static const int S = w - m;

/* Преобразование типа убирает старшее слово, т. е

* лишние биты слева, а сдвиг убирает лишнее справа

*/

HashIndexType HashValue = (HashIndexType) (K * Key) >> S;

Пусть, например, размер таблицы hashTableSize равен 1024 (210). Тогда нам достаточен 16-битный индекс и величине сдвига S будет присвоено значение 16 - 10 = 6. В итоге получаем:

typedef unsigned short int HashIndexType;

HashIndexType Hash (int Key) {

static const HashIndexType K = 40503;

static const int S = 6;

return (HashIndexType) (K * Key) >> S;

}

V. Аддитивный метод для строк переменной длины (размер таблицы равен 256). Для строк переменной длины вполне разумные результаты дает сложение по модулю 256. В этом случае результат hashValue заключен между 0 и 255.

typedef unsigned char HashIndexType;

HashIndexType Hash (char *str) {

HashIndexType h = 0;

while (*str) h += *str++;

return h;

}

VI. Исключающее ИЛИ для строк переменной длины (размер таблицы равен 256). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX).

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

typedef unsigned char HashIndexType;

unsigned char Rand8 [256];

HashIndexType Hash (char *str) {

unsigned char h = 0;

while (*str) h = Rand8 [h ^ *str++];

return h;

}

Здесь Rand8 - таблица из 256 восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным.

VIII. Исключающее ИЛИ для строк переменной длины (размер таблицы <= 65536). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до 65536. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 16-битовое.

typedef unsigned short int HashIndexType;

unsigned char Rand8 [256];

HashIndexType Hash (char *str) {

HashIndexType h;

unsigned char h1, h2;

if (*str == 0) return 0;

h1 = *str; h2 = *str + 1;

str++;

while (*str) {

h1 = Rand8 [h1 ^ *str];

h2 = Rand8 [h2 ^ *str];

str++;

}

/* h is in range 0.65535 */

h = ( (HashIndexType) h1 << 8) | (HashIndexType) h2;

/* use division method to scale */

return h % HashTableSize

}

Размер хеш-таблицы должен быть достаточно большим, чтобы в ней оставалось разумно большое число пустых мест. Чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n. Если размер таблицы равен 1, то таблица вырождается в один список длины n. Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n/100 элементов в каждом. Это сильно уменьшает длину списка, в котором нужно искать.

1.2 АВЛ-дерево

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

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г.М. Адельсона-Вельского и Е.М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962.

Общие свойства

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

,

где - золотое сечение,

то имеем оценку на высоту АВЛ-дерева h = O (log (n)), где n - число узлов. Следует помнить, что O (log (n)) - мажоранта, и ее можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя log (2) = 1). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму.

function TreeDepth (Tree: TAVLTree): byte;

begin

if Tree <> nil then

result: = 1 + Max (TreeDepth (Tree^. left),TreeDepth (Tree^. right))

else

result: = 0;

end;

Тип дерева можно описать так

TKey = LongInt;

TInfo = LongInt;

TBalance = - 1.1;

TAVLTree = ^ TAVLNode;

TAVLNode = record

left, right: TAVLTree;

key: TKey;

info: TInfo;

{ Поле определяющее сбалансированность вершины }

balance: TBalance;

end;

Балансировка

Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Используются 4 типа вращений:

1. Малое левое вращение

Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота С <= высота R.

2. Большое левое вращение

Данное вращение используется тогда, когда (высота b-поддерева - высота L) = 2 и высота c-поддерева > высота R.

3. Малое правое вращение

Данное вращение используется тогда, когда (высота b-поддерева - высота R) = 2 и высота С <= высота L.

4. Большое правое вращение

Данное вращение используется тогда, когда (высота b-поддерева - высота R) = 2 и высота c-поддерева > высота L.

В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.

Из-за условия балансированности высота дерева О (lg (N)), где N - количество вершин, поэтому добавление элемента требует O (lg (N)) операций.

Алгоритм добавления вершины

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

1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.

2. Включения новой вершины в дерево и определения результирующих показателей балансировки.

3. "Отступления" назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо - балансировка.

Расширим список параметров обычной процедуры вставки параметром-переменной flag, означающим, что высота дерева увеличилась. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl - высота левого поддерева, hr - высота правого поддерева } Включение вершины в левое поддерево приведет к

1. hl < hr: выравняется hl = hr. Ничего делать не нужно.

2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.

3. hl > hr: теперь hl - hr = 2, - требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^. left^. left) выше правого (Tree^. left^. right), то требуется двойной правый поворот, иначе хватит и малого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево. Процедура вставки предложенная Н. Виртом

procedure TAVL. InsertNode (Var Tree: TAVLTree; const akey: TKey; const ainfo: TInfo; Var flag: Boolean);

Var

Node1, Node2: TAVLTree;

begin

if Tree = nil then

begin

New (Tree);

flag: = true;

with Tree^ do

begin

key: = akey;

info: = ainfo;

left: = nil;

right: = nil;

balance: = 0;

end;

inc (AVL. FNodes);

end

else if Tree^. key > akey then

begin

InsertNode (Tree^. left,akey,ainfo,flag);

if flag then

case Tree^. balance of

1: begin Tree^. balance: = 0; flag: = false; end;

0: Tree^. balance: = - 1;

1: { Balance }

begin

Node1: = Tree^. left;

if Node1^. balance = - 1 then

{ LL }

begin

Tree^. left: = Node1^. right;

Node1^. right: = Tree;

Tree^. balance: = 0;

Tree: = Node1;

end

else

{LR}

begin

Node2: = Node1^. right;

Node1^. right: = Node2^. left;

Node2^. left: = Node1;

Tree^. left: = Node2^. right;

Node2^. right: = Tree;

if Node2^. balance = - 1 then Tree^. balance: = 1 else Tree^. balance: = 0;

if Node2^. balance = 1 then Node1^. balance: = - 1 else Node1^. balance: = 0;

Tree: = Node2;

end;

Tree^. balance: = 0;

flag: = false

end

end

end

else if Tree^. key < akey then

begin

InsertNode (Tree^. right,akey,ainfo,flag);

if flag then

case Tree^. balance of

1: begin Tree^. balance: = 0; flag: = false; end;

0: Tree^. balance: = 1;

1: { Balance }

begin

Node1: = Tree^. right;

if Node1^. balance = 1 then

{ RR }

begin

Tree^. right: = Node1^. left;

Node1^. left: = Tree;

Tree^. balance: = 0;

Tree: = Node1;

end

else

{RL}

begin

Node2: = Node1^. left;

Node1^. left: = Node2^. right;

Node2^. right: = Node1;

Tree^. right: = Node2^. left;

Node2^. left: = Tree;

if Node2^. balance = 1 then Tree^. balance: = - 1 else Tree^. balance: = 0;

if Node2^. balance = - 1 then Node1^. balance: = 1 else Node1^. balance: = 0;

Tree: = Node2;

end;

Tree^. balance: = 0;

flag: = false

end

end

end

end;

Алгоритм удаления вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.

Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O (N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O (log (N)).

Расстановка балансов при удалении

Как уже говорилось, если удаляемая вершина - лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист - ей находится "замена", и обратный обход дерева происходит от родителя "замены". Непосредственно после удаления элемента - "замена" получает баланс удаляемого узла.

При обратном обходе: если при переходе к родителю пришли слева - баланс уменьшается на 1, если же пришли справа - увеличивается на 1.

Это делается до тех пор, пока при изменении баланса он не станет равным ?1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке.

Расстановка балансов при одинарном повороте

Обозначим:

"Current" - узел, баланс которого равен ?2 или 2: то есть тот, который нужно повернуть (на схеме - элемент a)

"Pivot" - ось вращения. +2: левый сын Current'а, ?2: правый сын Current'а (на схеме - элемент b)

Если поворот осуществляется при вставке элемента, то баланс Pivot'а равен либо 1, либо ?1. В таком случае после поворота балансы обоих устанавливаются равными 0.

При удалении всё иначе: баланс Pivot'а может стать равным 0 (в этом легко убедиться).

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Pivot:

Направление поворота

Old Pivot. Balance

New Current. Balance

New Pivot. Balance

Левый или Правый

-1 или +1

0

0

Правый

0

-1

+1

Левый

0

+1

-1

Расстановка балансов при двойном повороте

Pivot и Current - те же самые, но добавляется третий участник поворота. Обозначим его за "Bottom": это (при двойном правом повороте) левый сын Pivot'а, а при двойном левом - правый сын Pivot'а.

При данном повороте - Bottom в результате всегда приобретает баланс 0, но от его исходного баланса зависит расстановка балансов для Pivot и Current.

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Bottom:

Направление

Old Bottom. Balance

New Current. Balance

New Pivot. Balance

Левый или Правый

0

0

0

Правый

+1

0

-1

Правый

-1

+1

0

Левый

+1

-1

0

Левый

-1

0

+1

Оценка эффективности

Г.М. Адельсон-Вельский и Е.М. Ландис доказали теорему, согласно которой высота АВЛ-дерева с N внутренними вершинами заключена между log2 (N+1) и 1.4404*log2 (N+2) - 0.328, то есть высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших N имеет место оценка 1.04*log2 (N). Таким образом, выполнение основных операций 1 - 3 требует порядка log2 (N) сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.

1.3 Обходы бинарных деревьев

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

Существует несколько принципиально разных способов обхода дерева:

Обход в прямом порядке

Каждый узел посещается до того, как посещены его потомки.

Для корня дерева рекурсивно вызывается следующая процедура:

Посетить узел

Обойти левое поддерево

Обойти правое поддерево

Примеры использования обхода:

· решение задачи методом деления на части

· разузлование сверху

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

1.4 Сортировка пузырьком

Расположим массив сверху вниз, от нулевого элемента - к последнему.

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

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

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

template<class T>

void bubbleSort (T a [], long size) {

long i, j;

T x;

for (i=0; i < size; i++) { // i - номер прохода

for (j = size-1; j > i; j--) { // внутренний цикл прохода

if (a [j-1] > a [j]) {

x=a [j-1]; a [j-1] =a [j]; a [j] =x;

}

}

}

}

Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta (n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.

Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.

1.5 Алгоритм Боуера и Мура (БМ)

Алгоритм Бойера-Мура, разработанный двумя учеными - Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Прежде чем рассмотреть работу этого алгоритма, уточним некоторые термины. Под строкой мы будем понимать всю последовательность символов текста. Собственно говоря, речь не обязательно должна идти именно о тексте. В общем случае строка - это любая последовательность байтов. Поиск подстроки в строке осуществляется по заданному образцу, т.е. некоторой последовательности байтов, длина которой не превышает длину строки. Наша задача заключается в том, чтобы определить, содержит ли строка заданный образец.

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

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

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть у нас есть набор символов из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца "abbad" в строке "abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма:

Таблица смещений для образца "abbad”.

Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

Три символа образца совпали, а четвертый - нет. Сдвигаем образец вправо на одну позицию:

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:

Еще раз сдвигаем образец на 2 позиции:

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

1.6 Линейный однонаправленный список

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

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

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

struct address {

char name [40];

char street [40];

char city [20];

char state [3];

char zip [11];

struct address *next; /* ссылка на следующий адрес */

} info;

Приведенная ниже функция slstore () создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.

void slstore (struct address *i,

struct address **last)

{

if (! *last) *last = i; /* первый элемент в списке */

else (*last) - >next = i;

i->next = NULL;

*last = i;

}

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

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

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

Следующая функция, sls_store (), вставляет структуры типа address в список рассылки, упорядочивая его по возрастанию значений в поле name. Функция принимает указатели на указатели на первый и последний элементы списка, а также указатель на вставляемый элемент. Поскольку первый или последний элементы списка могут измениться, функция sls_store () при необходимости автоматически обновляет указатели на начало и конец списка. При первом вызове данной функции указатели first и last должны быть равны нулю.

/* Вставка в упорядоченный односвязный список. */

void sls_store (struct address *i, /* новый элемент */

struct address **start, /* начало списка */

struct address **last) /* конец списка */

{

struct address *old, *p;

p = *start;

if (! *last) { /* первый элемент в списке */

i->next = NULL;

*last = i;

*start = i;

return;

}

old = NULL;

while (p) {

if (strcmp (p->name, i->name) <0) {

old = p;

p = p->next;

}

else {

if (old) { /* вставка в середину */

old->next = i;

i->next = p;

return;

}

i->next = p; /* вставка в начало */

*start = i;

return;

}

}

(*last) - >next = i; /* вставка в конец */

i->next = NULL;

*last = i;

}

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

void display (struct address *start)

{

while (start) {

printf ("%s\n", start->name);

start = start->next;

}

}

При вызове функции display () параметр start должен быть указателем на первую структуру в списке. После этого функция переходит к следующему элементу, на который указывает указатель в поле next. Процесс прекращается, когда next равно нулю.

Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля name:

struct address *search (struct address *start, char *n)

{

while (start) {

if (! strcmp (n, start->name)) return start;

start = start->next;

}

return NULL; /* подходящий элемент не найден */

}

Поскольку функция search () возвращает указатель на элемент списка, содержащий искомое имя, возвращаемый тип описан как указатель на структуру address. При отсутствии в списке подходящих элементов возвращается нуль (NULL).

Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента. На рис.4 показаны все три операции.

Ниже приведена функция, удаляющая заданный элемент из списка структур address.

void sldelete (

struct address *p, /* предыдущий элемент */

struct address *i, /* удаляемый элемент */

struct address **start, /* начало списка */

struct address **last) /* конец списка */

{

if (p) p->next = i->next;

else *start = i->next;

if (i==*last && p) *last = p;

}

Функции sldelete () необходимо передавать указатели на удаляемый элемент, предшествующий удаляемому, а также на первый и последний элементы. При удалении первого элемента указатель на предшествующий элемент должен быть равен нулю (NULL). Данная функция автоматически обновляет указатели start и last, если один из них ссылается на удаляемый элемент.

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

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

Программа состоит из нескольких файлов исходных текстов программ.

Все функции описаны в хедер файлах. Их предназначение:

Parserlib. h - функции-парсеры для проверки валидности данных;

Registration. h - Работа с односвязным списком,

функциональность: регистрация вселения/выселения постояльца

hastable. h - Работа с хеш-таблицей

функциональность: работа с информацией о постояльцах

avl. h - работа с АВЛ-деревом

функциональность: работа с гостиничными номерами

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

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

Avl. h

/**********************************************

работа с АВЛ-деревом

функциональность: работа с гостиничными номерами

***********************************************/

// структура нода

struct NODE

{

char Number [5]; // номер гостиничного номера

int CountBads; // количество спальных мест

int CountRooms; // количество комнат

int CountFreeBads; // количество оставшихся свободных мест

char toilet; // наличие санузла

char equipment [1000]; // оборудование номера

int Flag;

struct NODE *Left_Child;

struct NODE *Right_Child;

};

int convertnum (char *); // вспомогательная функция для получения номера гостиничного номера без префикса в виде int

struct NODE * Binary_Tree (char *, int, int, char, char *, struct NODE *, int *); // Добавление элемента в дерево

struct NODE * Balance_Right_Heavy (struct NODE *, int *); // перебалансировка дерева при удалении узла

struct NODE * Balance_Left_Heavy (struct NODE *, int *); // перебалансировка дерева при удалении узла

struct NODE * Delete_Element (struct NODE *, int, int *, int *); // удаление узла из дерева

void DeleteAllAVL (struct NODE **); // удаление всего дерева

void Output (struct NODE *); // вывод дерева на экран

int boyer_moore (char *, char *); // функция поиска подстроки по алгоритму Боуера-Мура

void findequip (struct NODE *, char *, int *); // ищем номера по фрагментам оборудования

void find_hotel_room (struct NODE *, char *, struct element *, struct NodeHash **, int *); // поиск по № гостиничного номера (с использованием дерева, хеш-таблицы и тд)

void find_numbers (struct NODE *, char *, int *, int *, int); // проверка наличия гостиничного номера в базе (поиск номера в дереве)

void printsk (char *,.);

avl. cpp

#define _CRT_SECURE_NO_WARNINGS

#include<string. h>

#include<conio. h>

#include<windows. h>

#include "avl. h"

#include "hashtable. h"

#include "registration. h"

# define F 0

# define T 1

// ----------------------------------------

/*вспомогательная функция для получения номера гостиничного номера без префикса в виде int*/

int convertnum (char *Number)

{

char tmp [3];

tmp [0] =* (Number+1);

tmp [1] =* (Number+2);

tmp [2] =* (Number+3);

return atoi (tmp);

}

// ----------------------------------------

/* Добавление элемента в дерево */

struct NODE * Binary_Tree (char *Number, int CountBads, int CountRooms, char toilet, char *equipment, struct NODE *Parent, int *H)

{

struct NODE *Node1;

struct NODE *Node2;

// если дерево пусто

if (! Parent)

{

Parent = (struct NODE *) malloc (sizeof (struct NODE));

strcpy (Parent->Number,Number);

Parent->Number [4] ='\0';

Parent->CountBads=CountBads;

Parent->CountFreeBads=CountBads;

Parent->CountRooms=CountRooms;

Parent->toilet=toilet;

strcpy (Parent->equipment,equipment);

Parent->Left_Child = NULL;

Parent->Right_Child = NULL;

Parent->Flag = 0;

*H = T;

return (Parent);

}

if (convertnum (Number) == convertnum (Parent->Number))

{

printsk ("Невозможно добавление двух номеров с одинаковыми номерами!");

_getch ();

return (Parent);

}

if (convertnum (Number) < convertnum (Parent->Number))

{

Parent->Left_Child = Binary_Tree (Number,CountBads, CountRooms, toilet,equipment, Parent->Left_Child, H);

if (*H)

/* Левая ветвь стала выше */

switch (Parent->Flag)

{

case 1:

/* Right heavy */

Parent->Flag = 0;

*H = F;

break;

case 0:

/* Balanced tree */

Parent->Flag = - 1;

break;

case - 1:

/* Left heavy */

Node1 = Parent->Left_Child;

if (Node1->Flag == - 1)

{

// printf ("\n Left to Left Rotation\n");

Parent->Left_Child = Node1->Right_Child;

Node1->Right_Child = Parent;

Parent->Flag = 0;

Parent = Node1;

}

else

{

// printf ("\n Left to right rotation\n");

Node2 = Node1->Right_Child;

Node1->Right_Child = Node2->Left_Child;

Node2->Left_Child = Node1;

Parent->Left_Child = Node2->Right_Child;

Node2->Right_Child = Parent;

if (Node2->Flag == - 1)

Parent->Flag = 1;

else

Parent->Flag = 0;

if (Node2->Flag == 1)

Node1->Flag = - 1;

else

Node1->Flag = 0;

Parent = Node2;

}

Parent->Flag = 0;

*H = F;

}

}

if (convertnum (Number) > convertnum (Parent->Number))

{

Parent->Right_Child = Binary_Tree (Number, CountBads, CountRooms, toilet,equipment, Parent->Right_Child, H);

if (*H)

/* Правая ветвь стала выше */

switch (Parent->Flag)

{

case - 1:

/* Left heavy */

Parent->Flag = 0;

*H = F;

break;

case 0:

/* Balanced tree */

Parent->Flag = 1;

break;

case 1:

/* Right heavy */

Node1 = Parent->Right_Child;

if (Node1->Flag == 1)

{

// printf ("\n Right to Right Rotation\n");

Parent->Right_Child = Node1->Left_Child;

Node1->Left_Child = Parent;

Parent->Flag = 0;

Parent = Node1;

}

else

{

// printf ("\n Right to Left Rotation\n");

Node2 = Node1->Left_Child;

Node1->Left_Child = Node2->Right_Child;

Node2->Right_Child = Node1;

Parent->Right_Child = Node2->Left_Child;

Node2->Left_Child = Parent;

if (Node2->Flag == 1)

Parent->Flag = - 1;

else

Parent->Flag = 0;

if (Node2->Flag == - 1)

Node1->Flag = 1;

else

Node1->Flag = 0;

Parent = Node2;

}

Parent->Flag = 0;

*H = F;

}

}

return (Parent);

}

// ----------------------------------------

/* Balancing Right Heavy */

struct NODE * Balance_Right_Heavy (struct NODE *Parent, int *H)

{

struct NODE *Node1, *Node2;

switch (Parent->Flag)

{

case - 1:

Parent->Flag = 0;

break;

case 0:

Parent->Flag = 1;

*H = F;

break;

case 1:

/* Rebalance */

Node1 = Parent->Right_Child;

if (Node1->Flag >= 0)

{

// printf ("\n Right to Right Rotation\n");

Parent->Right_Child = Node1->Left_Child;

Node1->Left_Child = Parent;

if (Node1->Flag == 0)

{

Parent->Flag = 1;

Node1->Flag = - 1;

*H = F;

}

else

Parent->Flag = Node1->Flag = 0;

Parent = Node1;

}

else

{

// printf ("\n Right to Left Rotation\n");

Node2 = Node1->Left_Child;

Node1->Left_Child = Node2->Right_Child;

Node2->Right_Child = Node1;

Parent->Right_Child = Node2->Left_Child;

Node2->Left_Child = Parent;

if (Node2->Flag == 1)

Parent->Flag = - 1;

else

Parent->Flag = 0;

if (Node2->Flag == - 1)

Node1->Flag = 1;

else

Node1->Flag = 0;

Parent = Node2;

Node2->Flag = 0;

}

}

return (Parent);

}

// ----------------------------------------

/* Balancing Left Heavy */

struct NODE * Balance_Left_Heavy (struct NODE *Parent, int *H)

{

struct NODE *Node1, *Node2;

switch (Parent->Flag)

{

case 1:

Parent->Flag = 0;

break;

case 0:

Parent->Flag = - 1;

*H = F;

break;

case - 1:

/* Rebalance */

Node1 = Parent->Left_Child;

if (Node1->Flag <= 0)

{

// printf ("\n Left to Left Rotation\n");

Parent->Left_Child = Node1->Right_Child;

Node1->Right_Child = Parent;

if (Node1->Flag == 0)

{

Parent->Flag = - 1;

Node1->Flag = 1;

*H = F;

}

else

Parent->Flag = Node1->Flag = 0;

Parent = Node1;

}

else

{

// printf ("\n Left to Right Rotation\n");

Node2 = Node1->Right_Child;

Node1->Right_Child = Node2->Left_Child;

Node2->Left_Child = Node1;

Parent->Left_Child = Node2->Right_Child;

Node2->Right_Child = Parent;

if (Node2->Flag == - 1)

Parent->Flag = 1;

else

Parent->Flag = 0;

if (Node2->Flag == 1)

Node1->Flag = - 1;

else

Node1->Flag = 0;

Parent = Node2;

Node2->Flag = 0;

}

}

return (Parent);

}

// ----------------------------------------

/* Перемещаем ноду с найденым ключом с последним правым ключем левого ребенка */

struct NODE * Delete (struct NODE *R, struct NODE *Temp, int *H)

{

struct NODE *Dnode = R;

if (R->Right_Child! = NULL)

{

R->Right_Child = Delete (R->Right_Child, Temp, H);

if (*H)

R = Balance_Left_Heavy (R, H);

}

else

{

Dnode = R;

strcpy (Temp->Number,R->Number);

R = R->Left_Child;

free (Dnode);

*H = T;

}

return (R);

}

// ----------------------------------------

/* Удаление элемента из дерева */

struct NODE * Delete_Element (struct NODE *Parent, int Number, int *H, int *status)

{

struct NODE *Temp;

if (! Parent)

{

printsk ("\n База пуста или номер не найден!");

return (Parent);

}

else

{

if (Number < convertnum (Parent->Number))

{

Parent->Left_Child = Delete_Element (Parent->Left_Child, Number, H, status);

if (*H)

Parent = Balance_Right_Heavy (Parent, H);

}

else if (Number > convertnum (Parent->Number))

{

Parent->Right_Child = Delete_Element (Parent->Right_Child, Number, H, status);

if (*H)

Parent = Balance_Left_Heavy (Parent, H);

}

else

{

Temp = Parent;

if (Temp->Right_Child == NULL)

{

Parent = Temp->Left_Child;

*H = T;

free (Temp);

*status=1;

}

else if (Temp->Left_Child == NULL)

{

Parent = Temp->Right_Child;

*H = T;

free (Temp);

*status=1;

}

else

{

Temp->Left_Child = Delete (Temp->Left_Child, Temp, H);

if (*H)

Parent = Balance_Right_Heavy (Parent, H);

*status=1;

}

}

}

return (Parent);

}

// ----------------------------------------

/*удаление всего дерева*/

void DeleteAllAVL (struct NODE **Parent)

{

struct NODE *t = *Parent;

if (t! = NULL)

{

DeleteAllAVL (&t->Left_Child);

DeleteAllAVL (&t->Right_Child);

free (t);

}

}

// ----------------------------------------

/* Вывод дерева */

void Output (struct NODE *Tree)

{

if (Tree)

{

Output (Tree->Left_Child);

printsk ("\n№ гостиничного номера: %s \nКоличество мест: %i \nКоличество комнат: %i \nНаличие санузла: %c \nОборудование: %s\n\n", Tree->Number, Tree->CountBads, Tree->CountRooms, Tree->toilet,Tree->equipment);

Output (Tree->Right_Child);

}

}

// ----------------------------------------

/*функция поиска подстроки по алгоритму Боуера-Мура*/

int boyer_moore (char * haystack, char * needle)

{

int i, j, k;

int needle_table [256];

int needle_len = strlen (needle);

int haystack_len = strlen (haystack);

char *tmp= (char*) malloc (haystack_len*sizeof (char));

strcpy (tmp,haystack);

if (needle_len <= haystack_len)

{

for (i = 0; i < 256; i++)

needle_table [i] = needle_len;

for (i = 1; i < needle_len; i++)

needle_table [needle [i]] = needle_len-i;

i = needle_len;

j = i;

while ( (j > 0) && (i <= haystack_len))

{

j = needle_len;

k = i;

while ( (j > 0) && (tmp [k-1] == needle [j-1]))

{

k--;

j--;

}

i += needle_table [tmp [i]];

}

if (k > haystack_len - needle_len)

return 0;

else

return k + 1;

}

else

return 0;

}

// ----------------------------------------

/*поиск № по номеру гостиничного номера*/

void find_hotel_room (struct NODE *Tree, char *Number, struct element *pbegin, struct NodeHash **hashtable, int *status)

{

struct element *pv=pbegin;

int hashkey;

struct NodeHash *tmp;

if (Tree)

{

find_hotel_room (Tree->Left_Child, Number, pbegin, hashtable, status);

find_hotel_room (Tree->Right_Child, Number, pbegin, hashtable, status);

if (strcmp (Tree->Number,Number) ==0)

{

*status=1;

printsk ("\n№ гостиничного номера: %s \nКоличество мест: %i \nКоличество комнат: %i \nНаличие санузла: %c \nОборудование: %s\n\n", Tree->Number, Tree->CountBads, Tree->CountRooms, Tree->toilet,Tree->equipment);

while (pv! =0)

{

if (strcmp (pv->Number,Number) ==0)

{

printsk ("\nНомер паспорта заселенного постояльца: %s", pv->passport);

hashkey=hash (pv->passport);

tmp=* (hashtable+hashkey);

while (tmp! =0)

{

if (strcmp (tmp->passport,pv->passport) ==0)

printsk ("\nФИО: %s",tmp->fio);

tmp=tmp->next;

}

}

pv=pv->next;

}

}

}

}

// ----------------------------------------

/*ищем номера по фрагментам оборудования*/

void findequip (struct NODE *Tree, char *equip, int *status)

{

if (Tree)

{

if (boyer_moore (Tree->equipment, equip))

{

printsk ("\n№ гостиничного номера: %s \nКоличество мест: %i \nКоличество комнат: %i \nНаличие санузла: %c \nОборудование: %s\n\n", Tree->Number, Tree->CountBads, Tree->CountRooms, Tree->toilet,Tree->equipment);

*status=1;

}

findequip (Tree->Left_Child, equip, status);

findequip (Tree->Right_Child, equip, status);

}

}

// ----------------------------------------

/*проверка наличия гостиничного номера в базе (поиск номера в дереве)

и вычисляем количество оставшихся свободных мест в номере*/

void find_numbers (struct NODE *Tree, char *Number, int *status, int *CountFreeBads, int key)

{

if (Tree)

{

if (strcmp (Tree->Number,Number) ==0)

{

*status=1;

if (key==0)

*CountFreeBads=-- (Tree->CountFreeBads);

else if (Tree->CountFreeBads==-1) *CountFreeBads=++ (++ (Tree->CountFreeBads));

return;

}

find_numbers (Tree->Left_Child, Number, status, CountFreeBads, key);

Страница:


Подобные документы

  • Разработка информационной системы учёта номеров в гостинице

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

    курсовая работа [1,8 M], добавлен 08.01.2014

  • Разработка базы данных "Гостиничный комплекс"

    Разработка и создание информационной базы данных в СУБД MS Access, которая будет содержать: сведения о гостинице; сведения о составе номеров в гостинице и обстановке в них; регистрацию покупателей в гостинице; ведение учета покупателей и данных о них.

    курсовая работа [586,6 K], добавлен 06.05.2010

  • База данных поликлиники

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

    курсовая работа [325,6 K], добавлен 05.12.2013

  • Разработка справочно-информационной системы "Справочник по оборудованию"

    Использование бинарных деревьев для поиска данных. Схемы алгоритмов работы с бинарным деревом. Проектирование алгоритмов и программ. Структура программного комплекса. Язык С# как средство для разработки автоматизированной информационной системы "Адрес".

    курсовая работа [914,9 K], добавлен 14.11.2013

  • База данных по регистрации больных в поликлинике

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

    курсовая работа [37,0 K], добавлен 07.12.2010

  • Разработка информационно-справочной системы с использованием алгоритмов хеширования

    Использование хеширования для поиска данных. Хеширование и хеш-таблицы. Способы разрешения конфликтов. Использование средств языка программирования в работе с хеш-таблицами. Описание разработанного приложения. Структура программы. Инструкция пользователя.

    курсовая работа [1,1 M], добавлен 19.08.2016

  • Разработка программы регистрации доступа клиентов в базу данных с конфиденциальной информацией

    Общая характеристика организации Муниципального автономного учреждение "Хоккейная команда Кузбасс". Разработка программы регистрации в системе программирования Delphi. Тестирование разработанной программы. Руководства пользователю и администратору.

    дипломная работа [1,3 M], добавлен 07.06.2012

  • Разработка информационной системы по регистрации абитуриентов в учебном заведении

    Характеристика функциональных возможностей разрабатываемой программы в среде Delphi для регистрации абитуриентов. Описание алгоритма и структуры данной программы. Поиск данных в базе по заданным параметрам. Описание модулей и листинг программы.

    курсовая работа [801,5 K], добавлен 19.07.2011

  • Хранение и обработка данных с использованием линейных списков

    Реализация линейных списков в языке программирования C++. Основные операции при работе с ними. Разработка интерфейса и алгоритмов. Описание работы программы на псевдокоде. Составление программного кода. Тестирование, отладка и результат работы программы.

    курсовая работа [1,1 M], добавлен 07.01.2014

  • Разработка класса Точка

    Разработка и тестирование программы класса Точка. Спецификация программы. Сценарий диалога с пользователем. Разработка структур данных и алгоритмов. Таблица параметров функций программы. Текст программы на языке C++. Особенности тестирования программы.

    лабораторная работа [43,1 K], добавлен 21.07.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены