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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гомельский государственный технический университет

имени П.О. Сухого»

Факультет автоматизированных и информационных систем

Кафедра «Информатика»

Специальность 1-40 04 01 «Информатика и технологии программирования»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине «Объектно-ориентированное программирование»

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

Исполнитель: студент группы ИП-21

Демиденко В.В.

Руководитель: ст. преподаватель

Романькова Т.Л.

Гомель 2016



Содержание

Введение

1. Использование хеширования для поиска данных

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

1.2 Способы разрешения конфликтов

1.3 Использование средств языка программирования в работе с хеш-таблицами

2. Алгоритмический анализ задачи

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

2.2 Исходные данные

2.3 Графические схемы алгоритмов работы с хеш-таблицами

3. Описание разработанного приложения

3.1 Структура программного комплекса

3.2 Инструкция пользователя

3.3 Описание результатов

Заключение

Список использованных источников

Приложения



Введение

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

В качестве языка программирования был выбран объектно-ориентированный язык программирования C#. С помощью Windows Formsбыл реализован простой интерфейс программы.

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

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок),текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором(таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедиию, алфавитный указатель, мы даже не задумываемся, что упорядочение алфавиту является не чем иным, как хешированием.

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



1. Использование хеширование для поиска данных

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

Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа, в качестве основы поиска, те вычисляется хеш-адрес h(K), который используется для поиска.

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

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

хеширование программирование язык таблица

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

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

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

Хеш-таблица - это структура данных, реализующая интерфейс

ассоциативного массива, то есть она позволяет хранить пары вида "ключ-значение" и выполнять три операции:

1) операцию добавления новой пары;

2) операцию поиска;

3) операцию удаления пары по ключу.

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

Хэш-таблицы должны соответствовать следующим свойствам:

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

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

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

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

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

? метод цепочек (метод прямого связывания);

? метод открытой адресации.

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

Второй метод состоит в том, что в массиве таблицы хранятся пары ключей-значений. Таким образом просматриваются не ссылки, а просто записи таблицы, пока не будет найден нужный ключ или пустая позиция [1].

1.2 Способы разрешения конфликтов

Составление хеш-функции - это не вся работа, которую предстоит вы-

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

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

Рисунок 1.1 - Пример реализации метода цепочек

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

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

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

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

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

Квадратичное зондирование

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

h = h + a²,

где a - это номер попытки. Этот вид адресации достаточно быстр и предсказуем (он проходит всегда один и тот же путь по смещениям 1, 4, 9, 16, 25, 36 и т.д.). Чем больше коллизий в таблице, тем дольше этот путь. С одной стороны, этот метод дает хорошее распределение по таблице, а с другой занимает больше времени для просчета.

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



1.3 Исследование средств языка программирования в работе с хеш-таблицами

В языке C# для работы с хеш-таблицами существует стандартный класс Hashtable. Он предназначен для создания коллекции, в которой для хранения ее элементов служит хеш-таблица. Информация сохраняется в хеш-таблице с помощью механизма, называемого хешированием. При хешировании для определения уникального значения, называемого хеш-кодом, используется информационное содержимое специального ключа. Полученный в итоге хеш-код служит в качестве индекса, по которому в таблице хранятся искомые данные, соответствующие заданному ключу. Преобразование ключа в хеш-код выполняется автоматически, и поэтому сам хеш-код вообще недоступен пользователю. Преимущество хеширования заключается в том, что оно обеспечивает постоянство времени выполнения операций поиска, извлечения и установки значений независимо от величины массивов данных [5].

Также для работы с хеш-таблицами используется класс Dictionary. Данный класс представляет собой сложную структуру данных, позволяющую обеспечить доступ к элементам по ключу. Главное свойство словарей ? быстрый поиск на основе ключей. Можно также свободно добавлять и удалять элементы без накладных расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.

В NET Framework предлагается несколько классов словарей. Главный класс, который можно использовать ? это Dictionary<TKey, TValue>.

Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode() класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode().Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. Мы не станем углубляться в подробности работы этого алгоритма. Емкость словаря всегда выражается простым числом. Реализация метода GetHashCode() должна удовлетворять перечисленным ниже требованиям:

? один и тот же объект должен всегда возвращать одно и то же значение;

? разные объекты могут возвращать одно и то же значение;

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

? он не должен генерировать исключений;

? он должен использовать как минимум одно поле экземпляра;

? значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int;

?хеш-код не должен изменяться на протяжении времени существования объекта.

Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable<T>.Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:

Если истинно А.Equals(В), значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код.

В классе Hashtable доступны также открытые свойства, определенные в тех интерфейсах, которые в нем реализуются. Особая роль принадлежит двум свойствам, Keys и Values, поскольку с их помощью можно получить ключи или значения из коллекции типа Hashtable. Эти свойства определяются в интерфейсе IDictionary следующим образом:



public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

В классе Hashtable не поддерживаются упорядоченные коллекции, и поэтому ключи или значения получаются из коллекции в произвольном порядке. Кроме того, в классе Hashtable имеется защищенное свойство EqualityComparer. А два других свойства, hep и comparer, считаются устаревшими.



2. Алгоритмический анализ задачи

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

Разработать информационно-справочную систему с использованием алгоритмов хеширования. Данные должны храниться в json файле (использовать формат *.json)

Справочник представляет собой набор записей, с полями. Функции приложения: чтение из json файла информации об объекте, вывод исходных данных в виде хеш-таблицы, построение хеш-таблицы с использованием подходящей функции хеширования (ключ: название корабля, разрешение конфликтов в хеш-таблицах: двойное хеширование), редактирование исходных данных (вставка, удаление, замена) с внесением соответствующих изменений в хеш-таблицу, визуализация, поиск информации о странах по заданному ключу с использованием хеширования.

2.2 Исходные данные

Исходные данные для данного проекта взяты по варианту 13

Таблица 1 - Описание класса Корабль

13	Корабль	название корабля, тип, водоизмещение, страна-производитель

Таблица 2 - Разрешение конфликтов

13	название корабля	Двойное хеширование

2.3 Графические схемы алгоритмов работы с хеш-таблицами

В ходе решения задачи были разработаны различные алгоритмы для работы с данными проекта.

Основной алгоритм построения хеш-таблицы показан на рисунке 2.1.

Рисунок 2.1 - Блок-схема построения хеш-таблицы

Основной алгоритм поиска данных в хеш-таблице продемонстрирован на рисунке 2.2



Рисунок 2.2 - Блок-схема поиска данных в хеш-таблице



3. Описание разработанного приложения

3.1 Структура программного комплекса

Структура программного комплекса состоит из трех проектов таких как File, Hash Table, Forms.

класс Ship

Таблица 3 - Элементы класса Country

Имя	Вид элемента	Спецификатор	Описание
name	String	public	Название корабля
type	String	public	Тип корабля
displacement	String	public	Водоизмещение
Manufacturer_country	String	public	Страна производитель
ToString()	String	public	Перегруженный метод возвращающий строковое представление объектов

Содержания проекта Hash Table.

Класс hashtable содержит вложенный класс hashentry, который имеет два поля ключ и данные. Методы hashtable - создание пустой хеш-таблицы, retrieve - поиск по заданному ключу, remove - удаление по заданному ключу, print - визуализация хеш-таблицы, check - проверка наличия места в хеш-таблице, quadraticHashInsert - добавления новой записи в хеш-таблицу.

Таблица 4 - Элементы класса hashtable

Имя	Вид элемента	Спецификатор	Описание
maxSize	Int	private	Размер хеш-таблицы
table	hashentry[]	private	Хеш-таблица

3.2 Инструкция пользователя

Для запуска программы запустите файл:Work.

На рисунке 3.1 изображено главное окно при запуске приложения.

Рисунок 3.1 - Окно приложения при его первоначальном запуске

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

Рисунок 3.2 -Окно при открытии файла

3.3 Описание результатов

При запуске приложения на экран открывается окно основной формы программы.



Рисунок 3.3 - Основное окно программы

В основном меню на вкладке «Файл» можно выбрать следующие операции: открыть, сохранить, выход.

Рисунок 3.4 - Меню с выбором

В меню выберем «Открыть» и выберем файл. После выбора на экран выводится таблица, отражающие информацию о странах.



Рисунок 3.5 - Отображение данных

Далее в меню Редактирование выбираем кнопку «Добавление» построение хеш-таблицы произойдёт автоматически с новой добавленной записью. Пользователю предоставляется возможность ввести данные и тем самым добавить новую запись. На рисунке 3.6 продемонстрировано окно с полями для добавления новой записи.

Рисунок 3.6 - Добавление данных

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



Рисунок 3.7 - Добавление записи

В меню Редактирование можно выбрать кнопку “Удаление” и удаление записи произойдет после введение данных и нажатия кнопки “Удалить”. Процесс удаления показан на рисунке 3.8.

Рисунок 3.8 - Удаление данных

Рисунок 3.8 - После удаления данных

После нажатия кнопки “Удалить” происходит автоматическое обновление в хеш-таблице.



В меню присутствует поле под названием «Поиск». Поиск происходит в хеш-таблице, нажав на кнопку, нужно ввести название корабля по которой будет происходить поиск.

Рисунок 3. 9 - Поиск данных

Рисунок 3.10 - Представление поиска данных

При выборе кнопки “Сохранить” в файл сохраняются изменения которые были произведены операциями добавления, изменения и удаления.

Выбрав в меню пункт «Выход» работа приложения завершится.

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



Рисунок 3.11-Визуализация



Заключение

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

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

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

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

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

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



Список использованных источников

1. Хеширование как процесс получения уникального идентификатора для объекта-Особенности процесса хеширования [Электронный ресурс]. - 2013. - Режим доступа:http://www.tnu.in.ua/study/ refs/d191/file38540.html -Дата доступа: 22.05.2016

2. Хеширование и хеш-таблицы - Квадратичное зондирование [Электронный ресурс]. - 2002. - Режим доступа:http://wm-help.net/lib/b/book/193850104/126 - Дата доступа: 22.05.2016

3. Большая Энциклопедия Нефти Газа - Линейное зондирование [Электронный ресурс]. - 2014. - Режим доступа:http://www.ngpedia.ru/id43131p1.html - Дата доступа: 23.05.2016

4. Wikipedia - свободная энциклопедия [Электронный ресурс]. - 2013. - Режим доступа:https://ru.wikipedia.org/wiki/Хеш-таблица - Дата доступа: 23.05.2016

5. С# и.Net - Класс Hashtable[Электронный ресурс]. - 2011. -

Режим доступа:http://professorweb.ru/my/csharp/charp_theory/ level12/12_5.php - Дата доступа: 24.05.2016

6. С# и.Net - Класс Dictionary [Электронный ресурс]. - 2011. -

Режим доступа:http://professorweb.ru/my/csharp/charp_theory/ level12/12_10.php - Дата доступа: 24.05.2016



Приложения

Приложение А

Листинг программы

Program.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Windows.Forms;

namespace hashing

{

staticclassProgram

{

///<summary>

/// Главная точка входа для приложения.

///</summary>

[STAThread]

staticvoid Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(newmain());

}

}

}



Приложение Б

(обязательное)

Листинг программы

country.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Text;

namespacehashing.fileWork

{

publicclasscountry//делаем класс видимым для других классов

{

publicint id;

publicstring name;

publicstring polity;

publicint area;

publicstring continent;

publicint Id //идентификатор

{

get

{

return id;

}

set

{

id = value;

}

}

publicstringName//свойство доступа к значению листа items

{

get

{

return name;

}

set

{

name = value;

}

}

publicstringPolity//свойство доступа к значению листа items

{

get

{

return polity;

}

set

{

polity = value;

}

}

publicintArea//свойство доступа к значению листа items

{

get

{

return area;

}

set

{

area = value;

}

}

publicstringContinent//свойство доступа к значению листа items

{

get

{

return continent;

}

set

{

continent = value;

}

}

}

}



Приложение В

(обязательное)

Листинг программы

fileactions.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Text;

using System.IO;

usingSystem.Windows.Forms;

usingNewtonsoft.Json; //https://docs.nuget.org/consume/package-manager-dialog

//Сервис- Диспетчер расширений - Установить Диспетчер пакетов NuGet устанавливаем json.net

namespacehashing.fileWork

{

publicclassfileActions

{

List<country>items;

publicList<country>LoadJson(string path)

{

try

{

using (StreamReader r = newStreamReader(path))

{

stringjson = r.ReadToEnd();

items = JsonConvert.DeserializeObject<List<country>>(json);

r.Close();

return items;

}

}

catch

{

MessageBox.Show("Неподдерживаемый тип файла или неверное содержимое. \nФайлнеможетбытьпрочитан.");

returnnull;

}

}

publicvoidSaveJson(string path, List<country>itms)

{

try

{

stringjson = JsonConvert.SerializeObject(itms);

//MessageBox.Show(json);

using (StreamWriter w = newStreamWriter(path))

{

w.Write(json);

w.Close();

MessageBox.Show("Файлсохранён.");

}

}

catch

{

MessageBox.Show("Файл для сохранения не был открыт!");

}

}

publicList<country>Items//свойство доступа к значению листа items

{

get

{

return items;

}

set

{

items = value;

}

}

}

}



Приложение Г

(обязательное)

Листинг программы

addItem.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Text;

usingSystem.Windows.Forms;

usinghashing.fileWork;

usinghashing.program;

namespacehashing.forms

{

publicpartialclassaddItem: Form

{

main m;

publicaddItem()

{

InitializeComponent();

}

privatevoid button2_Click(object sender, EventArgs e)

{

this.Close();

}

privatevoid button1_Click(object sender, EventArgs e)

{

if (m != null&&m.Items != null)

{

if (textBox1.Text != "")

{

country c = newcountry();

int max = 0;

for (inti = 0; i<m.Items.Count; i++) //ищеммаксимальный id

{

if (max <m.Items[i].Id)

max = m.Items[i].Id;

}

c.Id = max + 1;

c.Name = textBox1.Text;

c.Polity = textBox2.Text;

if (textBox3.Text == "")

textBox3.Text = "0";

c.Area = Convert.ToInt32(textBox3.Text);

c.Continent = textBox4.Text;

m.Items.Add(c);

visualization v = newvisualization();

v.fillTable(m.Items, m.dgvFromFile);

this.Close();

}

else

{

MessageBox.Show("Название страны не может быть пустым значением!");

}

}

else

{

MessageBox.Show("Вы ещё не открыли файл для работы.");

this.Close();

}

}

//запрет на ввод всего кроме чисел для площади

privatevoid textBox3_KeyPress(object sender, KeyPressEventArgs e)

{

if ((e.KeyChar<= 47 || e.KeyChar>= 58) &&e.KeyChar != 8)

e.Handled = true;

}

privatevoidaddItem_Load(object sender, EventArgs e)

{

m = this.Ownerasmain; //задаём m значение формы владельца

}

}

}



Приложение Д

(обязательное)

Листинг программы

editItem.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Text;

usingSystem.Windows.Forms;

usinghashing.fileWork;

usinghashing.program;

namespacehashing.forms

{

publicpartialclasseditItem: Form

{

main m;

intcurrentId = 0; //получаем idзаписи которая выделена

publiceditItem()

{

InitializeComponent();

}

privatevoid button2_Click(object sender, EventArgs e)

{

this.Close();

}

//сохранениеизменений

privatevoid button1_Click(object sender, EventArgs e)

{

if (m != null&&m.Items != null)

{

if (textBox1.Text != "")

{

for (inti = 0; i<m.Items.Count; i++) //ищеммаксимальный id

{

if (currentId == m.Items[i].Id)

{

m.Items[i].Name = textBox1.Text;

m.Items[i].Polity = textBox2.Text;

if (textBox3.Text == "")

textBox3.Text = "0";

m.Items[i].Area = Convert.ToInt32(textBox3.Text);

m.Items[i].Continent = textBox4.Text;

i = m.Items.Count; //выходим из цикла

visualization v = newvisualization();

v.fillTable(m.Items, m.dgvFromFile);

this.Close();

MessageBox.Show("Изменения успешно приняты!");

}

}

}

else

{

MessageBox.Show("Название страны не может быть пустым значением!");

}

}

else

{

MessageBox.Show("Вы ещё не открыли файл для работы.");

this.Close();

}

}

privatevoideditItem_Load(object sender, EventArgs e)

{

m = this.Ownerasmain;

textBox1.Text = m.dgvFromFile.CurrentRow.Cells[1].Value.ToString();

textBox2.Text = m.dgvFromFile.CurrentRow.Cells[2].Value.ToString();

textBox3.Text = m.dgvFromFile.CurrentRow.Cells[3].Value.ToString();

textBox4.Text = m.dgvFromFile.CurrentRow.Cells[4].Value.ToString();

currentId = Convert.ToInt32(m.dgvFromFile.CurrentRow.Cells[0].Value.ToString());

}

privatevoid textBox3_KeyPress(object sender, KeyPressEventArgs e)

{

if ((e.KeyChar<= 47 || e.KeyChar>= 58) &&e.KeyChar != 8)

e.Handled = true;

}

}

}



Приложение Е

(обязательное)

Листинг программы

search.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Text;

usingSystem.Windows.Forms;

usingSystem.Diagnostics; //для stopwatch таймера

usinghashing.fileWork;

usinghashing.program;

namespacehashing.forms

{

publicpartialclasssearch: Form

{

main m;

hashing.program.hash h = newprogram.hash(); //объекткласса hash дляполученияметодомgetHash - значенияхешадлятекста

public search()

{

InitializeComponent();

}

privatevoid button2_Click(object sender, EventArgs e)

{

this.Close(); //закрытиеформы

}

privatevoid button1_Click(object sender, EventArgs e)

{

if (m.Hashtable != null)

{

// MessageBox.Show(m.Hashtable.Count.ToString());

if (textBox1.Text != "")

{

// созданиетаймера

Stopwatchstopwatch = newStopwatch();

// начинаемотсчёттаймера

stopwatch.Start();

intsearchHash = h.getHash(textBox1.Text);

stringsearchText = textBox1.Text;

int v = 0;

bool find = false; //true еслинайдёмэлемент

inti = 0;

while(!find)

{

i = searchHash + m.c1 * v * v + m.c2 * v + m.c3; //сразуквадратичноезондированиеотэлементаsearchHash

if (v > 0)

i++; //если попытка не нулевая, то у нас должно быть расстояние МЕЖДУ элементами как квадрат попытки (без i++) между элементами будет на 1 меньше чем квадрат попытки

try

{

if (searchHash == m.Hashtable[i].Hash)

{

if (searchText == m.Hashtable[i].Name)

{

stopwatch.Stop(); //останавливаем таймер - замеряли время поиска

if (MessageBox.Show(this, "Найдено -> \nHASH: " + m.Hashtable[i].Hash + "\nID: " + m.Hashtable[i].Id + "\nНазвание страны: " + m.Hashtable[i].Name + "\nФорма правления: " + m.Hashtable[i].Polity + "\nПлощадь: " + m.Hashtable[i].Area + "\nКонтинент: " + m.Hashtable[i].Continent + "\n\nВремя поиска -> " + stopwatch.Elapsed + "\n\nПродолжить поиск?", "Результат", MessageBoxButtons.YesNo) == DialogResult.Yes)

{

stopwatch.Start(); //продолжаем таймер времени и не выходим из цикла

}

else

{

find = true; //выходим из цикла

}

}

}

}

catch (ArgumentOutOfRangeException)

{

// обрабатываем конец таблицы и делаем принудительный find=true чтобы завершить выполнение while

find = true;

}

if (!find)

{

v++;

}

}

MessageBox.Show("Поискзавершён.");

}

else

{

MessageBox.Show("Вы не ввели название страны!");

}

}

else

{

MessageBox.Show("Для поиска в хеш-таблице вначале необходимо построить хеш-таблицу!");

}

}

//событиевозникающеепризагрузкеформы

privatevoidsearch_Load(object sender, EventArgs e)

{

m = this.Ownerasmain; //задаём m значение формы владельца

}

privatevoid button3_Click(object sender, EventArgs e)

{

if (m.Items != null)

{

if (textBox1.Text != "")

{

// созданиетаймера

Stopwatchstopwatch = newStopwatch();

// начинаемотсчёттаймера

stopwatch.Start();

stringsearchText = textBox1.Text;

for (inti = 0; i<m.Items.Count; i++)

{

if (searchText == m.Items[i].Name)

{

stopwatch.Stop(); //останавливаем таймер - замеряли время поиска

if (MessageBox.Show(this, "Найдено -> \nID: " + m.Items[i].Id + "\nНазвание страны: " + m.Items[i].Name + "\nФорма правления: " + m.Items[i].Polity + "\nПлощадь: " + m.Items[i].Area + "\nКонтинент: " + m.Items[i].Continent + "\n\nВремя поиска -> " + stopwatch.Elapsed + "\n\nПродолжить поиск?", "Результат", MessageBoxButtons.YesNo) == DialogResult.Yes)

{

stopwatch.Start(); //продолжаем таймер времени и не выходим из цикла

}

else

{

i = m.Items.Count; //выходим из цикла

}

}

}

MessageBox.Show("Поиск завершён.");

}

else

{

MessageBox.Show("Вы не ввели название страны!");

}

}

else

{

MessageBox.Show("Для поиска необходимо открыть файл (массив items оказался пустой)!");



Приложение Ж

(обязательное)

Листинг программы

hash.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Text;

usingSystem.Windows.Forms;

namespacehashing.program

{

publicclasshash

{

publicintgetHash(stringkey) //наша функция получения хеша из ключа

{

int constant = 127; //константа

int h = 0; //хеш

int m = key.Length; //размер ключа

string qwerty = "";

foreach (char a in key)

{

h = (constant * h + (int)a)%m;

qwerty = qwerty + "Символ " + a.ToString() + " (int=" + (int)a + ") преобразованв h=" + h + "\n";

}

MessageBox.Show(qwerty);

return h;

}

}



Приложение И

(обязательное)

Листинг программы

hash_country.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Text;

namespacehashing.program

{

publicclasshash_country: hashing.fileWork.country//наследование

{

int hash;

publicint Hash //хеш

{

get

{

return hash;

}

set

{

hash = value;

}

}

}

}



Приложение К

(обязательное)

Листинг программы

visualization.cs

using System;

usingSystem.Collections.Generic;

usingSystem.Text;

usingSystem.Windows.Forms;

usinghashing.fileWork; //даёмдоступкfileWork

usinghashing.program; //даёмдоступк program

namespacehashing.program

{

publicclassvisualization

{

publicvoidfillTable(List<country> items, DataGridViewdgv)

{

try

{

dgv.Visible = false;

dgv.Rows.Clear();

dgv.RowCount = items.Count;

for (inti = 0; i<items.Count; i++)

{

dgv[0, i].Value = items[i].Id;

dgv[1, i].Value = items[i].Name;

dgv[2, i].Value = items[i].Polity;

dgv[3, i].Value = items[i].Area;

dgv[4, i].Value = items[i].Continent;

}

dgv.Visible = true;

}

catch

{

dgv.Rows.Clear();

dgv.Visible = true;

}

}

publicvoidfillHashTable(List<hash_country> items, DataGridViewdgv)

{

try

{

dgv.Visible = false;

dgv.Rows.Clear();

dgv.RowCount = items.Count;

for (inti = 0; i<items.Count; i++)

{

dgv[0, i].Value = items[i].Hash;

dgv[1, i].Value = i.ToString();

dgv[2, i].Value = items[i].Id;

dgv[3, i].Value = items[i].Name;

dgv[4, i].Value = items[i].Polity;

dgv[5, i].Value = items[i].Area;

dgv[6, i].Value = items[i].Continent;

}

dgv.Visible = true;

}

catch

{

dgv.Rows.Clear();

dgv.Visible = true;

}

}

}

}



Приложение Л

(обязательное)

Листинг программы

main.cs

using System;

usingSystem.Collections.Generic;

usingSystem.ComponentModel;

usingSystem.Data;

usingSystem.Drawing;

usingSystem.Text;

usingSystem.Windows.Forms;

usinghashing.fileWork;

usinghashing.program;

usinghashing.forms;

namespace hashing

{

publicpartialclassmain: Form

{

publicstringpathToJsonFile;

publicint c1 = 0;

publicint c2 = 0;

publicint c3 = 0;

fileActions actions = newfileActions();

visualization visual = newvisualization();

List<hash_country>hashtable = newList<hash_country>(); //массивдляхраненияхешейотключей

List<country>passedRows = newList<country>(); //строки для которых не будет найдено места в таблице по квадратичному зондированию

publicList<country> items;

publicList<country> Items //свойстводоступакзначениюлиста items

{

get

{

return items;

}

set

{

items = value;

}

}

publicList<hash_country>Hashtable//свойстводоступакзначениюлиста items

{

get

{

returnhashtable;

}

set

{

hashtable = value;

}

}

public main()

{

InitializeComponent();

}

privatevoidоткрытьToolStripMenuItem_Click(object sender, EventArgs e)

{

OpenFileDialogofd = newOpenFileDialog();

if (ofd.ShowDialog() == DialogResult.OK)

{

pathToJsonFile = ofd.FileName;

items = actions.LoadJson(pathToJsonFile);

visual.fillTable(items, dgvFromFile);

button1.Enabled = true;

button2.Enabled = true;

button3.Enabled = true;

button4.Enabled = true;

button5.Enabled = true;

сохранитьToolStripMenuItem.Enabled = true;

сохранитьКакToolStripMenuItem.Enabled = true;

}

}

//добавить

privatevoid button3_Click(object sender, EventArgs e)

{

addItemai = newaddItem();

ai.Owner = this; //задаёмвладельцадляформы

ai.ShowDialog();

if (autoUpdate.Checked)

{

build_Click(sender, e);

}

}

//изменить

privatevoid button2_Click(object sender, EventArgs e)

{

editItemei = neweditItem();

ei.Owner = this; //задаёмвладельцадляформы

ei.ShowDialog();

if (autoUpdate.Checked)

{

build_Click(sender, e);

}

}

//удалить

privatevoid button1_Click(object sender, EventArgs e)

{

if (dgvFromFile.CurrentRow != null)

{

DataGridViewRow row = dgvFromFile.CurrentRow;

intidToDelete = Convert.ToInt32(row.Cells[0].Value);

for (inti = 0; i<items.Count; i++)

{

if (idToDelete == items[i].Id)

{

items.RemoveAt(i);

i = items.Count;

visualization v = newvisualization();

v.fillTable(items, dgvFromFile);

MessageBox.Show("Записьудалена!");

}

}

if (autoUpdate.Checked)

{

build_Click(sender, e);

}

}

else

{

MessageBox.Show("Не выделена запись для удаления!");

}

}

//сохранить

privatevoidсохранитьToolStripMenuItem_Click(object sender, EventArgs e)

{

actions.SaveJson(pathToJsonFile, items);

}

//сохранитькак...

privatevoidсохранитьКакToolStripMenuItem_Click(object sender, EventArgs e)

{

SaveFileDialogsfd = newSaveFileDialog();

sfd.Filter = "Файлыформата JSON (*.json)|*.json|Всефайлы (*.*)|*.*";

if (sfd.ShowDialog() == DialogResult.OK)

{

pathToJsonFile = sfd.FileName;

pathOpened.Text = pathToJsonFile;

actions.SaveJson(pathToJsonFile, items);

}

}

privatevoid textBox1_KeyPress(object sender, KeyPressEventArgs e)

{

if ((e.KeyChar<= 47 || e.KeyChar>= 58) &&e.KeyChar != 8)

e.Handled = true;

}

//построитьхеш-таблицу

privatevoidbuild_Click(object sender, EventArgs e)

{

if (items != null)

{

int R = 1;

if (checkBox1.Checked) //есливыбранавторазмер

{

if (items.Count< 10)

R = 1;

elseif (items.Count< 1000)

R = Convert.ToInt32(items.Count / Math.Pow(10, Convert.ToInt32(items.Count.ToString().Length - 1)));

textBox4.Text = R.ToString();

}

else

{

if (textBox4.Text == "" || textBox4.Text == "0") textBox4.Text = "1";

R = Convert.ToInt32(textBox4.Text);

}

hashtable = newList<hash_country>();

passedRows = newList<country>();

hash h = newhash();

int M = dgvHash.RowCount = items.Count * items.Count / R;

//проходим по массиву аналогичному данным в таблице dgvFromFile с учётом добавленных\удалённых данных

intvalue = 0;

//заполняем массив пустыми строками

for (inti = 0; i< M; i++)

{

hash_countryqwe = newhash_country();

qwe.Hash = -1;

qwe.Name = "";

hashtable.Add(qwe);

}

if (textBox1.Text == "") textBox1.Text = "0";

if (textBox2.Text == "") textBox2.Text = "0";

if (textBox3.Text == "") textBox3.Text = "0";

c1 = Convert.ToInt32(textBox1.Text);

c2 = Convert.ToInt32(textBox2.Text);

c3 = Convert.ToInt32(textBox3.Text);

richTextBox1.AppendText(hashtable.Count.ToString() + "\n");

for (inti = 0; i<items.Count; i++)

{

//берём первую строку... вычисляем хеш по ключу

value = h.getHash(items[i].Name);

richTextBox1.AppendText(items[i].Name + ": Hash: " + value.ToString() + "\n");

richTextBox1.AppendText("Нашли value=" + value + "\n");

intnewI = 0;

for (int v = 0; newI<hashtable.Count; v++) //циклпопытокдотехпорпокаnewI = hashtable.Count + 1;

{

// уравнение квадратичного зондирования

newI = value + c1 * v * v + c2 * v + c3; //

if (v > 0)

newI++; //если не первое место вставки то должны прибавить 1, чтобы удовлетворять услкв зондирования

try

{

if (hashtable[newI].Name == "") //если пустое (вместо названия Name - индекс заданный по умолчанию)

{

//еслинезанята

hashtable[newI].Hash = value;

hashtable[newI].Id = items[i].Id;

hashtable[newI].Name = items[i].Name;

hashtable[newI].Polity = items[i].Polity;

hashtable[newI].Area = items[i].Area;

hashtable[newI].Continent = items[i].Continent;

richTextBox1.AppendText("Для items[i].Name=" + items[i].Name + " нашлиместо " + newI + " со " + v + " попытки\n");

newI = hashtable.Count; //выходим из цикла после вставки

}

}

catch (ArgumentOutOfRangeException) {

MessageBox.Show("Выходзапределыхеш-таблицы. Строка " + items[i].Name + " с id="+ items[i].Id + " схешем=" + value + "\nненашласебеместовхеш-таблице. \n\nЧтобы избежать этой ошибки, измените модификатор R размера хеш-таблицы!");

}

}

}

visual.fillHashTable(hashtable, dgvHash);

}

}

privatevoid button7_Click(object sender, EventArgs e)

{

if (richTextBox1.Visible)

richTextBox1.Visible = false;

else richTextBox1.Visible = true;

}

//поисквхеш-таблице

privatevoid button6_Click(object sender, EventArgs e)

{

search s = newsearch();

s.Owner = this; //задаёмвладельцадляформы (thisтут-этоформаmain)

s.ShowDialog();

}

privatevoidвыходToolStripMenuItem_Click(object sender, EventArgs e)

{

DialogResult result = MessageBox.Show("Выйтиизпрограммы?", "Выход", MessageBoxButtons.YesNo, MessageBoxIcon.Question);

if (result == DialogResult.No) //Еслинажалнет

{

//То продолжаем работу;

}

if (result == DialogResult.Yes) //ЕслинажалДа

{

MessageBox.Show("Программазавершена");

this.Close();

}

}

}

}

Размещено на Allbest.ru