Презентация к курсовой работе По дисциплине: «Объектно-ориентированное программирование» На тему: «Поиск информации с использованием алгоритмов хеширования» Выполнил : студент группы ИТ-22 Лобан С.В.

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

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

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

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

Описание разработанной программы Для открытия файла необходимо нажать в пункте меню Файл / Открыть

Для хеширования данных – Для вывода хеш-таблицы – Для вывода таблицы – Описание разработанной программы

Для добавления данных в таблицу – Для замены – Для удаления –

Описание разработанной программы Внешний вид программы:

Описание разработанной программы public int HashIndex(string key, int M) // функция хеширования { uint hash = 0; for (int i = 0; i < key.Length; i++) // высчитываем значения хэш. key - ключ (наименование товара) { hash = (hash * 11) + (uint)key[i] + 11; } return (int)(hash % M); // остаток от деления hash на размер таблицы }

Описание разработанной программы public int insert(Tovar s) // вставка эл-та в хеш-таблицу { int i = HashIndex(s.Name, M); // индекс ячейки в которую будет добавляться объект S while (i<M && HashSpisok[i] != null) // поиск пустой ячейки i = (i + 1) % M; // получение адреса новой ячейки HashSpisok[i] = new Tovar(s.Kod, s.Name, s.Cena, s.Kol); // заполнение данной ячейки return i; // возврат адреса ячейки }

Описание разработанной программы public Tovar search(string key) // поиск в хеш-таблице { int i = HashIndex(key,M); // индекс ячейки в которой содержиться товар с наименованием KEY while (i<M && HashSpisok[i] != null) // если ячейка не пуста, то... if (HashSpisok[i].Name == key) // сравнивается введенное наименование товара с ключом { return HashSpisok[i]; // если совпало, то возвращается значение содержимого ячейки i } else i = (i + 1) % M; // иначе получаем адрес следующей ячейки return null; }

Описание разработанной программы public void remove(string key) // удаление из хеш-таблицы { int j; int i = HashIndex(key, M); // индекс ячейки в которой содержиться товар с наименованием KEY while (i < M && HashSpisok[i] != null) // если ячейка не пуста, то... { if (key == HashSpisok[i].Name) // сравнивается введенное наименование товара с ключом break; else i = (i + 1) % M; // иначе получаем адрес следующей ячейки } HashSpisok[i] = null; // присваивание ячейке i значения null for (j = i + 1; j<M && HashSpisok[j] != null; j = (j + 1) % M) // цикл для смещения ячеек { Tovar d = HashSpisok[j]; // временная переменная в которую заносится значение ячейки j HashSpisok[j] = null; // очищается ячейка j insert(d); // вставляется объект d }

Описание разработанной программы public int RazmerTable(int n) // вычисление размера таблицы { int M = n; // минимальный размер таблицы bool f = true; // находит ближайшее простое число, для размера хеш-таблицы while (f) // пока f = true { // вычисляем количество делителей числа M int q = 0; for (int i = 1; i < M; i++) if (M % i == 0) q++; if (q > 1) M++; else f = false; } return M; }

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