Колинько 4 семестр 2018 / АиСД 3 лаб
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра вычислительной техники
отчет
по лабораторной работе №3
по дисциплине «Алгоритмы и структуры данных»
Тема: «Хеш-таблицы»
Вариант №42
|
Студенты гр. 6307 |
|
Лазарев С.О. Медведев Е.Р. |
|
Преподаватель |
|
Колинько П.Г. |
Санкт-Петербург
2018
СОДЕРЖАНИ
ЦЕЛЬ 3
ЗАДАНИЕ 3
Временная сложность 5
ВЫВОДЫ 6
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 7
ПРИЛОЖЕНИЕ 8
ЗАДАНИЕ 3
Временная сложность 5
ВЫВОДЫ 6
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 7
ПРИЛОЖЕНИЕ 8
ЦЕЛЬ 3
ЗАДАНИЕ 3
Временная сложность 5
ВЫВОДЫ 6
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 7
ПРИЛОЖЕНИЕ 8
ЦЕЛЬ
Получить практические навыки по работе с хеш-таблицами.
ЗАДАНИЕ
Составить и отладить программу для вычисления шестого множества по пяти заданным, представленным в форме хеш-таблиц.
F = (A & B) \ (C & D) ^ E.
Решение задачи
Пример:
Рис 1. Элементы множества А в хеш-таблице.
Рис 2. Элементы множества В в хеш-таблице.
Рис 3. Элементы множества С в хеш-таблице.
Рис 4. Элементы множества D в хеш-таблице.
Рис 5. Элементы множества E в хеш-таблице.
Рис 6. Результат вычисления A & B
Рис 7. Результат вычисления C & D
Рис 8. Результат вычисления (A & B) / (C & D)
Рис 9. Искомый результат F = (A & B) / (C & D) ^ E
Временная сложность
Таблица 1. Временная сложность
|
|
В лучшем |
В худшем случае |
|
Расход памяти |
O(n) |
O(n) |
|
Вставка |
O(1) |
O(n) |
|
Удаление |
O(1) |
O(n) |
|
XOR |
O(n) |
O(n^2) |
|
& |
O(n) |
O(n^2) |
|
\ |
O(n) |
O(n^2) |
|
F |
O(n) |
O(n^2) |
ВЫВОДЫ
Мы получили навыки работы с хеш-таблицами. Размер таблицы выбран m = 6 для удобного представления на экране. Также это становится возможным с использованием цепочек переполнения. Коэффициенты a = 7 и b = 3 выбраны согласно рекомендации в методических указаниях. (a и b – простые числа, a близкое к m и b близкое к 1). Если пренебречь удобством, можно выбрать размер таблицы m = 2*U, где U – универсум (в нашем случае U = 66), чтобы снизить вероятность появления коллизий.
.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
-
Алгоритмы и структуры данных. – Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию, часть 2, глава 1 «Работа с иерархией объектов: наследование и полиморфизм».
ПРИЛОЖЕНИЕ
main.cpp
#include "hash_set.h"
#include <time.h>
#include <iostream>
const int N = 66; // Мощность множества
HashSet generate();
int main()
{
srand(time(NULL));
HashSet a, b, c, d, e, f1,f2,f3,f4,f;
a = generate();
b = generate();
c = generate();
d = generate();
e = generate();
std::cout << "A:" << std::endl << a << std::endl;
std::cout << "B:" << std::endl << b << std::endl;
std::cout << "C:" << std::endl << c << std::endl;
std::cout << "D:" << std::endl << d << std::endl;
std::cout << "E:" << std::endl << e << std::endl;
std::cout << "-----------------------------------------------------" << std::endl;
f1 = a & b;
std::cout << "a & b" << std::endl << f1 << std::endl;
f2 = c & d;
std::cout << "c&d" << std::endl << f2 << std::endl;
f3 = ((a&b) / (c&d));
std::cout << "(a&b) / (c&d)" << std::endl << f3 << std::endl;
std::cout << "F = (A & B) / (C & D) ^ E" << std::endl << std::endl;
f = ((a&b) / (c&d)) ^ e;
std::cout << "F:" << std::endl << f << std::endl;
std::cin.get();
return 0;
}
HashSet generate()
{
HashSet result = HashSet();
static char *uni = new char[N];
int k = 48;
for (int i = 0; i < N-1; i++) {
uni[i] = k;
k++;
}
int count = rand() % (N + 1);
char x;
for (int i = 0; i < count; i++)
{
int p = rand() % (N - i);
if (p)
{
result.add(uni[p + i] - '0');
x = uni[i];
uni[i] = uni[i + p];
uni[i + p] = x;
}
}
return result;
}
HashSet.cpp
#include "hash_set.h"
Entry HashSet::null = Entry(-1);
int HashSet::dataSize = 6;
HashSet::HashSet()
{
data = new Entry *[dataSize];
for (int i = 0; i < dataSize; i++)
data[i] = &null;
};
HashSet::HashSet(const HashSet & set)
{
data = new Entry *[dataSize];
for (int i = 0; i < dataSize; i++)
data[i] = &null;
for (int i = 0; i < dataSize; i++)
for (Entry * j = set.data[i]; j != &null; j = j->next)
{
data[i] = new Entry(j->key, data[i]);
}
}
HashSet::HashSet(HashSet && set)
{
data = set.data;
size = set.size;
set.data = nullptr;
}
HashSet::~HashSet()
{
delete[] data;
}
int HashSet::hash(int key) const
{
return (7 * key + 3) % dataSize;
}
bool HashSet::add(int key)
{
int h = hash(key);
if (contains(key))
return false;
data[h] = new Entry(key, data[h]);
return true;
}
bool HashSet::contains(int key)const
{
int h = hash(key);
for (Entry * i = data[h]; i != &null; i = i->next)
if (key == i->key)
return true;
return false;
}
HashSet HashSet::operator=(const HashSet& set)
{
return HashSet(set);
}
HashSet HashSet::operator=(HashSet && set)
{
data = set.data;
size = set.size;
set.data = nullptr;
return *this;
}
HashSet HashSet::operator |(const HashSet& set)const
{
HashSet result = HashSet(set);
for (int i = 0; i < dataSize; i++)
for (Entry * j = data[i]; j != &null; j = j->next)
{
if (!result.contains(j->key))
result.add(j->key);
}
return result;
}
HashSet HashSet::operator /(const HashSet& set)const
{
HashSet result;
for (int i = 0; i < dataSize; i++)
for (Entry * j = data[i]; j != &null; j = j->next)
{
if (!set.contains(j->key))
result.add(j->key);
}
return result;
}
HashSet HashSet::operator &(const HashSet& set)const
{
HashSet result = HashSet();
for (int i = 0; i < dataSize; i++)
for (Entry * j = data[i]; j != &null; j = j->next)
{
if (set.contains(j->key))
result.add(j->key);
}
return result;
}
HashSet HashSet::operator ^(const HashSet& set)const
{
HashSet result = HashSet();
for (int i = 0; i < dataSize; i++)
for (Entry * j = data[i]; j != &null; j = j->next)
{
if (!set.contains(j->key))
result.add(j->key);
}
for (int i = 0; i < dataSize; i++)
for (Entry * j = set.data[i]; j != &null; j = j->next)
{
if (!contains(j->key))
result.add(j->key);
}
return result;
}
std::ostream& operator<<(std::ostream& os, const HashSet& set)
{
for (int i = 0; i < set.dataSize; i++)
{
os << "[" << i << "] : ";
for (Entry * j = set.data[i]; j != &HashSet::null; j = j->next)
{
os << j->key << " --> ";
}
os << " -|" << std::endl;
}
return os;
}
Hash_set.h
#pragma once
#include <iostream>
class Entry
{
public:
Entry * next;
int key;
Entry(int key, Entry * next = nullptr) :key(key), next(next) {};
~Entry()
{
delete next;
};
};
class HashSet
{
private:
Entry * * data;
static Entry null;
static int dataSize;
int size;
int hash(int key) const;
public:
HashSet();
HashSet(HashSet &&);
HashSet(const HashSet &);
~HashSet();
friend std::ostream & operator<<(std::ostream& os, const HashSet& set);
bool add(int key);
bool contains(int key)const;
HashSet operator=(const HashSet&);
HashSet operator=(HashSet &&);
HashSet operator |(const HashSet&)const;
HashSet operator &(const HashSet&)const;
HashSet operator ^(const HashSet&)const;
HashSet operator /(const HashSet&)const;
};