Хеширование

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

СОДЕРЖАНИЕ

• Введение
• 1. Хеширование
• 1.1 Определение хеширования
• 1.2 История
• 1.3 Разрешение коллизий
• 2. Описание задачи и исходных данных
• 2.1 Постановка задачи
• 2.2 Описание исходных данных
• 2.3 Анализ поставленной задачи
• 3. Описание разработанного Приложения
• 3.1 Описание программных модулей
• 3.2 Описание работы методов
• 3.3 Структура программного продукта
• 4. Описание интерфейса
• Заключение
• Список использованных источников
• Приложение А Листинг программы


Введение

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

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

Основной целью данной работы является изучение организации информации методом структуры -- «Хеш-таблица», а также его программная реализация. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C#.

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

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

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

хеширование алгоритм справочный информационный программирование



1. Хеширование

1.1 Определение хеширования

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

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

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

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



1.2 История

Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну, предложившему хеш-кодирование в январе 1953 года.

В 1956 году Арнольд Думи в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число.

Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца, в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.

В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».

1.3 Разрешение коллизий

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

Рисунок 1.1 -- Пример коллизии

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



2. Описание задачи и исходных данных

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

В курсовом проекте поставленной задачей является разработать справочно-информационную (Windows-приложение) систему на языке программирования C# выполняющее следующие функции:

1) чтение из текстового файла информации об объектах класса согласно варианту (таблица 2.1). Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться. Использовать регулярные выражения (предусмотреть проверку по возможности всех полей);

2) вывод исходных данных в виде таблицы;

3) визуализация хеш-таблицы или бинарного дерева;

4) поиск информации по заданному ключу или способу обхода;

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

6) вывод справочной информации о программном продукте и об авторе;

7) демонстрация перегруженных операторов;

8) поиск максимального объекта.

2.2 Описание исходных данных

Исходными данными задачи являются:

1) название предметной области, а точнее название класса и его основные поля указаны в таблице 2.1, которое выбирается согласно варианту выданному преподавателем;

2) текстовый файл с информацией об объектах класса согласно варианту. Количество записей не менее 50. Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться;

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

Таблица 2.1 -- Описание класса

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

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

№ варианта	Ключ	Разрешение конфликтов в хэш--таблицах
13	Название корабля	Двойное хеширование

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

1) создать класс согласно варианту. Класс должен содержать следующие элементы:

а) описание полей класса (выделенное жирным курсивов поле оформить как перечисление);

б) конструкторы с параметрами и по умолчанию, а также необходимые свойства и методы;

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

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

д) перегрузку префиксного и постфиксного инкремента (указать назначение инкремента);

е) перегрузку операторов << и >> (указать назначение операторов);

ж) создание массива из объектов вашего класса;

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

и) предусмотреть обработку и инициализацию исключительных ситуаций;

к) Класс должен реализовывать интерфейс IComparable;

2) разработать интерфейс Windows-приложения автоматизированной системы. Помимо самостоятельно выбранных элементов управления, обязательно могут присутствовать следующие элементы управления: MenuStrip, ContextMenuStrip, Button, TextBox, DataGridView, TextBox, ToolTIp, Panel, Label, ComboBox, OpenFileDialog, SaveFileDialog, PictureBox, CheckBox, RedioButton.

2.3 Анализ поставленной задачи

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

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

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

Наилучшим вариантом (во избежание коллизий) взять следующую функции h1, которая представлена в следующей формуле:

h1 = ,

где h1 -- хеш-функция №1;

C -- сумма кодов ASCII символов ключа;

L -- размер (количество символов) ключа.

В свою очередь, функция h2 имеет вид (формула 2.2):

h2 = L*2,

где h2 -- хеш-функция №2;

L -- размер ключа.

Функции с данными функции (формула 2.1 и формула 2.2) и будут выступать в разрабатываемом программном продукте в качестве функций №1 и №2.



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

3.1 Описание программных модулей

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

Класс «Hash_Table» -- хеш-таблица, содержит в себе следующие методы:

1) «Add» -- метод добавления элемента в хеш-таблицу;

2) «Find» -- метод поиска элемента в хеш-таблице, с помощью «Двойного хэширования», по заданному ключу (введённым пользователем в отдельном окне);

3) «Zamena» -- метод для осуществления замены элементов в хеш-таблице;

4) «Udalenie» -- метод удаления элемента из хеш-таблицы (путём обнуления ячейки);

5) «Max» -- метод, осуществляющий поиск максимального элемента в хеш-таблице по средством операторов отношения и алгоритма организации хеш-таблиц;

6) «Visit» -- метод, осуществляющий проверку ячейки с ключом, ячейка находиться с помощью прохешированного ключа (введённого пользователем).

7) «Zagruzka» -- метод загрузки хеш-таблицы в компонент «DataGridView» (визуализирующий прохешированные элементы).

8) «Save» -- метод сохранения (выгрузки) хеш-таблицы в файл, по указанному пути пользователем.

Класс «Ship» -- корабль (описанная предметная область с её полями и названием класс), включает в себя основные методы:

1) «CompareTo» -- переопределение интерфейса «IComparable», который сравнивает текущий экземпляр с другим объектом того же типа и возвращает целое число, которое показывает, расположен ли текущий экземпляр перед, после или на той же позиции в порядке сортировки, что и другой объект;

2) «Compare_Enum» -- метод, который осуществляет проверку наличия типа корабля считанного из файла в виде корабля указанным в перечислении «Enum».

Также имеется класс «Hash_Cell» -- ячейка хеш-таблицы, который не содержит в себе каких-либо методов, а лишь поля «Value» -- значение ячейки, и «Key» -- ключ ячейки, а также конструктор с параметрами (для инициализации переменных «Value» и «Key»).

3.2 Описание работы методов

Метод «Add» -- вызывается при нажатии пунктов меню «Файл - Открыть» и «Функции с данными - Вставка». Сам алгоритм работы данного метода представлен на рисунке 3.1.

Рисунок 3.1 -- Блок схема метода «Add»

Метод «Visit» -- осуществляет так сказать обход хеш-таблицы. Данный метод не вызывается посредством меню, а выполняет роль второстепенного метода (подпрограммы) для остальных методов.

Алгоритм метод «Visit» представлен на рисунке 3.2.

Рисунок 3.2 -- Блок схема метода «Visit»

Метод «Zamena» -- метод для осуществления замены элементов в хэш-таблице. Сам алгоритм заключается в следующем:

1) произвести поиск элемента с помощью метода «Visit»;

2) удалить найденный элемент из хэш-таблицы;

3) прохешировать новый элемент (на который производиться замена) с помощью метода «Add», алгоритм которого представлен на рисунке 3.1.

Более подробно алгоритм работы метода «Zamena» представлен на рисунке 3.3.



Рисунок 3.3 -- Блок схема метода «Zamena»

Метод «Max» -- осуществляет поиск максимального элемента в хэш-таблице по средством операторов отношения. Алгоритм работы представлен на рисунке 3.4.

Рисунок 3.4 -- Блок схема метода «Max»

Метод «Udalenie» -- удаляет элемент из хэш-таблице. Удаление элемента в хэш-таблице подразумевает под собой обнуления ячейки[8]:

Алгоритм работы метода «Udalenie» более подробно можно увидеть на рисунке 3.5.

Рисунок 3.5 -- Блок схема метода «Udalenie»

Метод «Find» -- метод поиска элемента в хэш-таблице, способом устранения коллизий «Двойное хеширование», по заданному ключу. При использовании данного метода автоматически происходит запуск метода «Visit» -- посещение ячеек хэш-таблицы (рисунок 3.2), в которой происходит поиск данного элемента, и возвращает его обратно в «Find» где происходят второстепенные действия (вывод найденного элемента в отдельную таблицу). Блок схема метода «Find» представлена на рисунке 3.6.

Рисунок 3.9 -- Блок схема метода «Find»

3.3 Структура программного продукта

Программа состоит из двух классов:

1) класс «Hash_Table» -- хэш-таблица, элементы класса отображены в таблице 3.1;

2) класс «Hash_Cell» -- ячейка хэш-таблицы, элементы описаны в таблице 3.2;

3) класс «Ship» -- корабль (предметная область), элементы данного класса показаны и описаны в таблице 3.3.

Таблица 3.1 -- Элементы класса «Hash_Table»

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
Znach	Поле	T: IComparable	Private	Содержимое хеш-таблицы
Mas	Поле	Hash_Cell <T>[]	Public	Хеш-таблица
Hash_Table(int q)	Конструктор	-	Public	Размерность хеш-таблицы
Hash_Table(T Znach)	Конструктор	-	Public	Инициализация «Znach»
h1(string Search)	Метод	int	Public	Функция хеширования №1
H2(string Search)	Метод	int	Public	Функция хеширования №2
Resize(int NewSize)	Метод	void	Public	Изменение размерности хеш-таблицы
Add(T Znachenie)	Метод	void	Public	Добавление значения в хеш-таблицу
Find(string Search)	Метод	void	Public	Поиск элемента в хеш-таблице
Zamena(string Search, string New)	Метод	void	Public	Замена элемента в хеш-таблице
Udalenie(string Search)	Метод	void	Pulic	Удаление элемента из хеш-таблицы
Max()	Метод	void	Public	Поиск максимального элемента в хеш-таблице
Zagruzka(Data GridViewTable)	Метод	void	Public	Занесение хеш-таблица в DataGridView
Save(string Path2)	Метод	void	Public	Сохранение хеш-таблицы в файл



Таблица 3.2 -- Элементы класса «Hash_Cell»

Имя	Вид элемента	Тип	Спецификатор	Описание
Value	Поле	T: IComparable	Public	Содержимое ячейки хеш-таблицы
Key	Поле	int	Public	Ключ ячейки
Hash_Cell(T Value)	Конструктор	-	Public	Инициализация «Value»

Таблица 3.3 -- Элементы класса «Ship»

Имя	Вид элемента	Тип	Спецификатор	Описание
Name_Ship	Поле	string	Private	Название корабля
Draught	Поле	int	Private	Водоизмещение
Country	Поле	int	Private	Страна
view	Перечисление	Enum	Private	Тип корабля
Ship (string Name_Ship, string Draught, string Country, string view)	Конструктор	-	Public	Инициализация полей: Name_Ship, Draught, Country, view
CompareTo (object Data)	Метод	int	Public	Метод сравнения с object
CompareTo (string Data)	Метод	int	Public	Метод сравнения с string
Compare_Enum(string view)	Метод	bool	Public	Сравнение -- существует ли такой тип корабля



4. Описание интерфейса

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

Первый запуск программы вызывает следующее окно, в котором доступны лишь 2 пункта меню (и 3 пункта подменю), данное окно изображено на рисунке 4.1.

Рисунок 4.1 -- Интерфейс справочно-информационной системы при первом запуске

Как видно по рисунку первоначально доступны лишь пункты меню «Файл» и «О программе», и каждой пункт меню содержит свои подпункты, которые изображены на рисунке 4.2.

Рисунок 4.2 -- Первоначальные подпункты меню пунктов «Файл» и «О программе»

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

1) «Файл - Открыть» -- позволяет открыть файл *txt формата для организации хеш-таблицы и осуществления с данной информацией необходимых действий (таких как поиск, удаление и т.д.);

2) «О программе - Об авторе» -- открывает окно, содержащее информацию об авторе программного продукта. Данное окно изображено на рисунке 4.3;

Рисунок 4.3 -- Окно появляющееся при нажатии пункта меню «О программе - Об авторе»

3) «О программе - Справка» -- при нажатии данного пункта появляется окно, которое содержит информацию по работе с данной справочно-информационной системой (рисунок 4.4).



Рисунок 4.4 -- «О программе - Справка»

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

Рисунок 4.5 -- Интерфейс программы после открытия файла

Если при считывании файла (информации в справочно-информационную систему) были обнаружены некорректные записи, то произойдёт вызов окна, на котором изображено количество данных некорректных записей (рисунок 4.6).

Рисунок 4.6 -- Окно отображающее количество некорректных записей

Рисунок 4.7 -- Пункты меню после открытия файла

Становятся доступны следующие пункты меню (рисунок 4.7):

1) «Файл - Сохранить» -- сохранить в текущий открытый файл всю хеш-таблицу, со всеми изменениями;

2) «Файл - Сохранить как» -- сохранить хеш-таблицу со всеми изменениями в новый файл (указание пути сохранения файла предоставляется пользователю);

3) «Функции с данными - Вставка» -- даёт возможность пользователю добавить в хеш-таблицу элемент. Как это происходит, изображено на рисунке 4.9;



Рисунок 4.9 -- Окно «Вставка»

4) «Функции с данными - Поиск» -- позволяет произвести поиск элемента по ключу (рисунок 4.10), либо найти максимальный элемент в хеш-таблице. После выполнения поиска (любым из предложенных) произойдёт вывод найденных элементов в отдельную таблицу (рисунок 4.11);

Рисунок 4.10 -- Окно «Поиск элемента»

Рисунок 4.11 -- Вывод результата после выполнения метода «Функции с данными - Поиск - Поиск элемента» или «Функции с данными - Поиск - Поиск максимального элемента»

5) «Функции с данными - Изменение» -- позволяет изменить уже существующие элементы в хеш-таблице на указанный (в отдельном окне) новый элемент. При нажатии данного пункта меню, произойдёт вызов нового окна «Изменение», в котором необходимо ввести «Старое значение» и «Новое значение», данное окно представлено на рисунке 4.12;

Рисунок 4.12 -- Окно «Изменение»

6) «Функции с данными - Удаление» -- даёт возможность удалить элемент из хеш-таблицы. Работа с данным пунктом изображена на рисунке 4.13;

Рисунок 4.13 -- Окно «Удаление»

При работе с такими пунктами меню как: «Функции с данными - Вставка», «Функции с данными - Поиск - Поиск элемента», «Функции с данными - Изменение», «Функции с данными - Удаление» предусмотрена система «Сохранение информации», то есть если в любом из окон (пунктов меню перечисленных выше) присутствует какая- либо информация, то будет сработана данная система и появится окно (рисунок 4.14) с запросом «В текстовом поле обнаружена информация, вы уверены что хотите выйти?» с возможностью ответа «Да» или «Нет». При нажатии на кнопку «Да» -- произойдёт выход из текущего окна без сохранения информации, при нажатии на кнопку «Нет» -- произойдёт возврат обратно в текущее окно.



Рисунок 4.14 -- Запрос о сохранение текущей информации

Если при работе со справочно-информационной системой (с открытым файлом) попытаться выполнить пункт «Файл - Открыть» (то есть открыть новый файл) или просто при нажатии на кнопку «Закрыть» (выход из программы), произойдёт автоматический запуск окна (рисунок 4.15) с запросом «Сохранить информацию?», если будет нажата кнопка «Да» -- произойдёт сохранение хеш-таблицы в текущий файл, кнопка «Нет» -- означает закрыть программу без сохранения информации, то есть очистка текущей сессии (рисунок 4.16), кнопка «Отмена» -- вернуться обратно в программу без выполнения каких либо действий.

Рисунок 4.15 -- Окно с запросом о сохранении текущей информации

Рисунок 4.16 -- Окно сообщающее что данная сессия обнулена

Заключение

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

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

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

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

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

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

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



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

1. Хеширование [Электронный ресурс]. - Режим доступа: http://ru.wikipedia.org/wiki/Хеширование. - Дата доступа: 15.05.2014.

2. Хеш-таблица [Электронный ресурс]. - Режим доступа: http://ru.wikipedia.org/wiki/Хеш-таблица. - Дата доступа: 16.05.2014.

3. Корман, Т. Алгоритмы: построение и анализ / Лейзерсон Ч., Ривест Р. - МЦНМО, 2001. - 65 с.

4. Чмора, А. Современная прикладная криптография. - Гилиос APB, 2001. - 29 с.

5. Джозеф, А. C# 5.0. Справочник. Полное описание языка. - Издательский дом Вильямс, 2013. - 1008 с.

6. Скит, Д. C#: программирование для профессионалов. - Издательский дом Вильямс, 2011. - 544 с.

7. C Sharp [Электронный ресурс]. - Режим доступа: http://ru.wikipedia.org/wiki/C_Sharp. - Дата доступа: 20.05.2014.

8. Нейгел, К. Visual C#: полный курс. - Издательство «Диалектика», 2010. - 236 с.

9. Разрешение коллизий [Электронный ресурс]. - Режим доступа: http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий. - Дата доступа: 22.05.2014.

10. Павловская, Т.А. C#. Программирование на языке высокого уровня: учебник для вузов. - СПб.: Питер, 2007. - 432 с.



Приложение А Листинг программы

Текст программы Form1.cs

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

using System.IO; //Файлы

using System.Text.RegularExpressions; //Регулярные выражения

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

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

ToolTip tooltip = new ToolTip();

tooltip.SetToolTip(button1,"Добавить");

tooltip.SetToolTip(button2,"Удалить");

tooltip.SetToolTip(button3,"Изменить");

tooltip.SetToolTip(button4,"Поиск");

tooltip.SetToolTip(button5,"Выход");

}

static StreamReader Read;

static string Path;

static int k = 0;

static Hash_Table<Ship> ekz = null; //Экземпляр Хэш-таблицы

class Hash_Table<T> where T : IComparable

{

T Znach;

public Hash_Cell<T>[] Mas;

public Hash_Table(int q)

{

Mas = new Hash_Cell<T>[q];

}

public Hash_Table(T Znach)

{

this.Znach = Znach;

}

public class Hash_Cell<TYPE> where TYPE : IComparable //Ячейка

{

public T Value;

public int Key;

public Hash_Cell(T Value)

{

this.Value = Value;

}



public Hash_Cell()

{

}

} //Ячейка (HASH_CELL)

public int h1(string Search)

{

int h1=0;

for (int i=0;i<Search.Length;i++)

{

h1 += Convert.ToInt32(Char.ToLower(Search[i]));

}

return (h1 / (Search.Length * Search.Length * Search.Length));

}

public int h2(string Search)

{

return (Search.Length*2);

}

public void Resize(int NewSize)

{

Array.Resize(ref Mas, Mas.Length + NewSize);

}

public void Add(T Znachenie)

{

Znach = Znachenie;

int i = 0;

if ((Mas.Length < h1((Znach as Ship).Name_Ship_OutPut)) || (Mas.Length < h1(((Znach as Ship).Name_Ship_OutPut)) + h2(((Znach as Ship).Name_Ship_OutPut))))

{

Resize(h1(((Znach as Ship).Name_Ship_OutPut)) + h2(((Znach as Ship).Name_Ship_OutPut)));

}

if (Mas[h1((Znach as Ship).Name_Ship_OutPut)] == null)

{

Mas[h1((Znach as Ship).Name_Ship_OutPut)] = new Hash_Cell<T>(Znach);

Mas[h1((Znach as Ship).Name_Ship_OutPut)].Key = h1((Znach as Ship).Name_Ship_OutPut);

}

else if (Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut)] == null)

{

Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut)] = new Hash_Cell<T>(Znach);

Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut)].Key = h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut);

}

else

{

i++;

bool Stop = false;

while (Stop != true)

{

if (Mas.Length < (h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i))

{

Resize(h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i);

}

if (Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i] == null)

{

Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i] = new Hash_Cell<T>(Znach);

Mas[h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i].Key = h1((Znach as Ship).Name_Ship_OutPut) + h2((Znach as Ship).Name_Ship_OutPut) * i;

Stop = true;

}

else

{

i++;

}

}

}

}

public void Find(string Search) //Поиск элемента

{

if (Visit(Search) != null)

{

Hash_Cell<T> Data = Visit(Search);

Form6 f6 = new Form6();

f6.dataGridView1.Rows.Clear();

f6.dataGridView1.Rows.Add(Data.Key, (Data.Value as Ship).Name_Ship_OutPut, (Data.Value as Ship).view_OutPut, (Data.Value as Ship).Draught_OutPut, (Data.Value as Ship).Country_OutPut);

f6.ShowDialog();

}

else

{

MessageBox.Show("Данного корабля не существует", "Ошибка поиска", MessageBoxButtons.OK, MessageBoxIcon.Error);

}

}

public Hash_Cell<T> Visit(string Search) //Обход хэш-таблицы

{

int i = 0;

if (Mas.Length >= h1(Search) && Mas[h1(Search)]!=null && (Mas[h1(Search)].Value as Ship).Name_Ship_OutPut == Search)

{

return Mas[h1(Search)];

}

else if (Mas.Length >= h1(Search) + h2(Search) && Mas[h1(Search) + h2(Search)]!=null && (Mas[h1(Search) + h2(Search)].Value as Ship).Name_Ship_OutPut == Search)

{

return Mas[h1(Search) + h2(Search)];

}

else

{

i++;

while (Mas.Length > (h1(Search) + h2(Search) * i))

{

if (Mas.Length >= h1(Search) + h2(Search) * i && Mas[h1(Search) + h2(Search) * i]!=null && (Mas[h1(Search) + h2(Search) * i].Value as Ship).Name_Ship_OutPut == Search)

{

return Mas[h1(Search) + h2(Search) * i];

}

else

{

i++;

}

}

}

return null;

}

public void Zamena(string Search, string New) //Замена

{

if (Visit(Search) != null)

{

int b = Visit(Search).Key;

(Mas[b].Value as Ship).Name_Ship_OutPut = New;

ekz.Add(new Ship((Mas[b].Value as Ship).Name_Ship_OutPut, (Mas[b].Value as Ship).view_OutPut, (Mas[b].Value as Ship).Draught_OutPut, (Mas[b].Value as Ship).Country_OutPut));

Mas[b] = null;

Read = new StreamReader(Path, Encoding.Default);

string str;

str = Read.ReadToEnd();

//str = str.Replace(Search, New);

Regex Regular = new Regex(Search);

str = Regular.Replace(str, New);

Read.Close();

StreamWriter Write = new StreamWriter(Path, false, Encoding.Default);

Write.Write(str);

Write.Close();

}

else

{

MessageBox.Show("Данного корабля не существует", "Ошибка поиска", MessageBoxButtons.OK, MessageBoxIcon.Error);

}

}

public void Udalenie(string Search)

{

if (Visit(Search) != null)

{

int k = Visit(Search).Key;

Mas[k] = null;

}

else

{

MessageBox.Show("Данного корабля не существует", "Ошибка поиска", MessageBoxButtons.OK, MessageBoxIcon.Error);

}

}

public void Max() //Поиск максимального элемента

{

Form6 f6 = new Form6();

Hash_Cell<T> Maximum = new Hash_Cell<T>();

int i = 0;

bool Stop = false;

while (Stop!=true) //Найти в таблице самый первый элемент

{

if (Mas[i] != null)

{

Maximum = Mas[i];

Stop = true;

}

i++;

}

i = Maximum.Key+1;

while (Mas.Length > i)

{

if (Mas[i] != null)

{

if ((Maximum.Value as Ship).CompareTo(Mas[i].Value as Ship) == -1)

{

Maximum = Mas[i];

}

}

i++;

}

f6.dataGridView1.Rows.Clear();

f6.dataGridView1.Rows.Add(Maximum.Key, (Maximum.Value as Ship).Name_Ship_OutPut, (Maximum.Value as Ship).view_OutPut, (Maximum.Value as Ship).Draught_OutPut, (Maximum.Value as Ship).Country_OutPut);

f6.ShowDialog();

}

public void Zagruzka(DataGridView Table)

{

int i=0;

Table.Rows.Clear();

while (Mas.Length > i)

{

if (Mas[i] != null)

{

Table.Rows.Add(Mas[i].Key, (Mas[i].Value as Ship).Name_Ship_OutPut, (Mas[i].Value as Ship).view_OutPut, (Mas[i].Value as Ship).Draught_OutPut, (Mas[i].Value as Ship).Country_OutPut);

}

i++;

}

}

public void Save(string Path2) //Сохранение

{

int i = 0;

Path = Path2;

StreamWriter Write = new StreamWriter(Path, false, Encoding.Default);

while (Mas.Length > i)

{

if (Mas[i] != null)

{

Write.WriteLine((Mas[i].Value as Ship).Name_Ship_OutPut + ";" + (Mas[i].Value as Ship).view_OutPut + ";" + (Mas[i].Value as Ship).Draught_OutPut + ";" + (Mas[i].Value as Ship).Country_OutPut);

}

i++;

}

Write.Close();

}

public static bool operator >(Hash_Cell<T> A, Hash_Cell<T> B) //Сравнение "Больше"

{

if ((A as Ship).CompareTo((B as Ship)) == 1)

{

return true;

}

else

{

return false;

}

}

public static bool operator <(Hash_Cell<T> A, Hash_Cell<T> B) //Сравнение "Меньше"

{

if ((A as Ship).CompareTo((B as Ship)) == -1)

{

return true;

}

else

{

return false;

}

}

public static bool operator ==(Hash_Cell<T> Data, string Search)

{

if ((Data.Value as Ship).CompareTo(Search)==0)

{

return true;

}

else

{

return false;

}

}

public static Hash<T> operator ++()

{

}

public static Hash<T> operator --(Hash<T> Data)

{

}

} //Хэш-таблица (HASH_TABLE)



class Ship: IComparable //Класс "Корабль"

{

string Name_Ship;

enum views { Акат, Бавари, Билландер, Блокшив, Бригантина, Галея, Гидрографическое_судно, Дноуглубительное_судно, Маломерное_судно, Плашкоут, Полакр, Рафт, Баржа, Тартана, Турбоход, Угольщик, Шмак};

views view;

string Draught; //Водоизмещение

string Country;

public string[] type = Enum.GetNames(typeof(views));

public string Name_Ship_OutPut

{

get

{

return this.Name_Ship;

}

set

{

Name_Ship = value;

}

}

public string view_OutPut //Свойство для получения "view"

{

get

{

return Enum.GetName(typeof(views),view);

}

}

public string Draught_OutPut

{

get

{

return this.Draught;

}

}

public string Country_OutPut

{

get

{

return this.Country;

}

}

public Ship() //Пустой конструктор без параметров (для обращения к методам)

{

}

public Ship(string Name_Ship, string view, string Draught, string Country)

{

this.Name_Ship = Name_Ship;

this.view = (views)Enum.Parse(typeof(views), view);

this.Draught = Draught;

this.Country = Country;

}

public int CompareTo (object Data) //Сравнение с "Object"

{

if (string.Compare(this.Name_Ship,(Data as Ship).Name_Ship) > 0) return 1;

if (string.Compare(this.Name_Ship, (Data as Ship).Name_Ship) < 0) return -1;

else return 0;

}

public int CompareTo(string Data) //Сравнение со "String"

{

if (string.Compare(this.Name_Ship, Data)==1) return 1;

if (string.Compare(this.Name_Ship, Data)==-1)return -1;

else return 0;

}

public bool Compare_Enum(string view)

{

if (Enum.IsDefined(typeof(views), view) == true)

{

return true;

}

else

{

return false;

}

}



} //Класс "Корабль"

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

{

if (ekz == null)

{

openFileDialog1.Filter = "Текстовый файл | *.txt";

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

{

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

данныеToolStripMenuItem.Visible = true;

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

this.Height = 420;

string[] str;

Read = new StreamReader(openFileDialog1.FileName, Encoding.Default); //Cоздание «потокового читателя» и связывание его с файловым потоком

Path = openFileDialog1.FileName; //Сохранение пути к текущему файлу

int l = File.ReadAllLines(Path).Length; //Количество строк

if (ekz == null)

{

ekz = new Hash_Table<Ship>(l);

}

string strokFile = Read.ReadLine();

Ship view = new Ship();

if (strokFile != null)

{

while (strokFile != null)

{

str = strokFile.Split(';'); //Отделение слов

try

{

if (view.Compare_Enum(str[1]) == true)

{

ekz.Add(new Ship(str[0], str[1], str[2], str[3]));

}

else

{

k++;

}

}

catch (Exception)

{

k++;

}

finally

{

strokFile = Read.ReadLine();

}

}

ekz.Zagruzka(dataGridView1);

if (k > 0)

{

MessageBox.Show("Обнаруженно некоректных записей: " + k.ToString(), "Открыть файл", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

Read.Close();

}

}

}

else

{

DialogResult = MessageBox.Show("Сохранить текущий файл ?", "Информация", MessageBoxButtons.YesNo, MessageBoxIcon.Question);

if (DialogResult == DialogResult.Yes)

{

ekz.Save(Path);

}

else if (DialogResult == DialogResult.No)

{

this.Height = 355;

k = 0;

ekz = null;

сохранитьToolStripMenuItem.Visible = false;

данныеToolStripMenuItem.Visible = false;

сохранитьКакToolStripMenuItem.Visible = false;

dataGridView1.Rows.Clear();

MessageBox.Show("Текущая сессия обнулена, теперь можете открыть новый файл", "Информация", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

}

}

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

{

ekz.Save(Path);

}

private void изменитьToolStripMenuItem_Click(object sender, EventArgs e)

{

Form2 f = new Form2();

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

{

ekz.Zamena(f.textBox1.Text, f.textBox2.Text);

ekz.Zagruzka(dataGridView1);

}

}

private void удалениеToolStripMenuItem_Click(object sender, EventArgs e)

{

Form3 f = new Form3();

f.Text = "Удаление";

f.label1.Text = "Введите значение для удаления";

f.button1.Text = "Удалить";

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

{

ekz.Udalenie(f.textBox1.Text);

ekz.Zagruzka(dataGridView1);

}

}

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

{

saveFileDialog1.Filter = "Текстовый файл | *.txt";

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

{

ekz.Save(saveFileDialog1.FileName);

}

}

private void вставкаToolStripMenuItem_Click(object sender, EventArgs e)

{

Ship view = new Ship();

Form4 f = new Form4();

for (int i = 0; i < view.type.Count(); i++)

{

f.comboBox1.Items.Add(view.type[i]);

}

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

{

ekz.Add(new Ship(f.textBox1.Text, f.comboBox1.Text, f.textBox2.Text, f.textBox3.Text));

ekz.Zagruzka(dataGridView1);

}

}

private void Form1_FormClosing(object sender, FormClosingEventArgs e)

{

if (ekz!=null)

{

DialogResult = MessageBox.Show("Сохранить информацию ?", "Информация", MessageBoxButtons.YesNoCancel, MessageBoxIcon.Question);

if (DialogResult == DialogResult.Yes)

{

ekz.Save(Path);

}

else if (DialogResult == DialogResult.No)

{

Dispose();

}

else if (DialogResult == DialogResult.Cancel)

{

ShowDialog();

}

}

}

private void поискЭлементаToolStripMenuItem_Click(object sender, EventArgs e)

{

Form3 f = new Form3();

f.Text = "Поиск";

f.label1.Text = "Введите значение для поиска";

f.button1.Text = "Поиск";

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

{

ekz.Find(f.textBox1.Text);

}

}



private void поискToolStripMenuItem1_Click(object sender, EventArgs e)

{

ekz.Max();

}

private void обАвтореToolStripMenuItem_Click(object sender, EventArgs e)

{

MessageBox.Show("Выполнил Толстенков Пётр Сергеевич ПО-32, 2014 г.\nОснованием для разработки курсового проекта служит задание выданное преподавателем Курницовым О.В.", "Об авторе", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

private void справкаToolStripMenuItem_Click(object sender, EventArgs e)

{

Form5 f = new Form5();

f.ShowDialog();

}

private void Form1_Load(object sender, EventArgs e)

{

}

private void button1_Click(object sender, EventArgs e)

{

вставкаToolStripMenuItem_Click(sender,e);

}

private void button2_Click(object sender, EventArgs e)

{

удалениеToolStripMenuItem_Click(sender, e);

}

private void button3_Click(object sender, EventArgs e)

{

изменитьToolStripMenuItem_Click(sender, e);

}

private void button4_Click(object sender, EventArgs e)

{

поискЭлементаToolStripMenuItem_Click(sender, e);

}

private void button5_Click(object sender, EventArgs e)

{

if (ekz != null)

{

DialogResult = MessageBox.Show("Сохранить информацию ?", "Информация", MessageBoxButtons.YesNoCancel, MessageBoxIcon.Question);

if (DialogResult == DialogResult.Yes)

{

ekz.Save(Path);

}

else if (DialogResult == DialogResult.No)

{

Dispose();

}

}

}

}

}

Текст программы Form2.cs

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

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

{

public partial class Form2 : Form

{

public Form2()

{

InitializeComponent();

}<...