Міністерство освіти і науки України
Харківський патентно-комп’ютерний коледж
Практична робота №4
з дисципліни «Алгоритми і структури даних»
Тема: «Нелінійні структури даних»
Студента групи П-23
Русаков Д.Д.
2014
Завдання: Створити Хеш-таблицю.
Хід роботи:
Хеш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.
Лістинг програми:MYPR4.cpp
#include <cstdlib>
#include <iostream>
#include <time.h>
#include "knight.h"
#include "hash.h"
using namespace std;
int main()
{
knight k;
k.setName("Vitalik");
k.setBallads(30);
k.setArmorWeight(2.403);
k.setLadyLove(false);
knight t;
t.randomData();
Hash<int, knight> myFirstHash(10);
myFirstHash.add(10, k);
myFirstHash.add(11, t);
cout<<myFirstHash.get(11);
return 0;
}
list.h
#ifndef _LIST_H
#define _LIST_H
template<class T>
class ListItem
{
private:
T data;
ListItem<T> *next;
public:
ListItem();
ListItem(const T &item);
void setNext(ListItem<T> *next);
ListItem<T>* getNext() const;
void setData(const T &data);
T& getData();
ListItem<T>& operator=(ListItem<T> arg);
};
template<class T>
class List
{
private:
ListItem<T> *head;
int listSize;
public:
List();
List(const T &item);
~List();
void pushFront(const T &item);
void pushAt(const T &item, int index);
void pushBack(const T &item);
void popFront();
void popAt(int index);
void popBack();
void print(ostream& os) const;
bool empty() const;
T& at(int index) const;
int search(const T& item);
void sort();
int size();
};
template<class T>
List<T>::List()
{
this->head = NULL;
listSize = 0;
}
template<class T>
List<T>::List(const T &item)
{
ListItem<T>* newItem = new ListItem<T>(item);
this->head = newItem;
listSize = 1;
}
template<class T>
List<T>::~List()
{
while(head != NULL)
{
ListItem<T> *tmp = head;
head = head->getNext();
delete tmp;
}
}
template<class T>
void List<T>::pushFront(const T &item)
{
ListItem<T>* newItem = new ListItem<T>(item);
newItem->setNext(this->head);
this->head = newItem;
listSize++;
}
template<class T>
void List<T>::pushAt(const T &item, int index)
{
ListItem<T>* tmp = head;
for(int i = 0; i < index; i++)
{
tmp = tmp->getNext();
}
ListItem<T>* newItem = new ListItem<T>(item);
tmp->setNext(newItem);
listSize++;
}
template<class T>
void List<T>::pushBack(const T &item)
{
ListItem<T>* tail = head;
while(tail->getNext() != NULL)
{
tail = tail->getNext();
}
ListItem<T>* newItem = new ListItem<T>(item);
tail->setNext(newItem);
listSize++;
}
template<class T>
void List<T>::popFront()
{
if(listSize > 0)
{
ListItem<T>* tmp = head;
head = head->getNext();
delete tmp;
listSize--;
}
}
template<class T>
void List<T>::popAt(int index)
{
if(listSize > 0 && index < listSize)
{
if(listSize == 1)
{
this->popFront();
}
else
{
ListItem<T>* last = head;
ListItem<T>* secondLast = head;
for(int i = 0; i < index - 1; i++)
{
secondLast = secondLast->getNext();
}
last = secondLast->getNext();
secondLast->setNext(last->getNext());
delete last;
}
}
}
template<class T>
void List<T>::popBack()
{
if(listSize > 0)
{
if(listSize == 1)
{
ListItem<T>* last = head;
head = NULL;
delete last;
}
else
{
ListItem<T>* last = head;
ListItem<T>* secondLast = head;
while(secondLast->getNext()->getNext() != NULL)
{
secondLast = secondLast->getNext();
}
last = secondLast->getNext();
secondLast->setNext(NULL);
delete last;
}
}
}
template<class T>
void List<T>::print(ostream& os) const
{
ListItem<T>* toPrint = head;
while(toPrint != NULL)
{
os<<toPrint->getData()<<"\n";
toPrint = toPrint->getNext();
}
}
template<class T>
bool List<T>::empty() const
{
return listSize == 0;
}
template<class T>
T& List<T>::at(int index) const
{
ListItem<T>* itemToReturn = head;
for(int i = 0; i < index; i++)
{
itemToReturn = itemToReturn->getNext();
}
return itemToReturn->getData();
}
template<class T>
int List<T>::search(const T& item)
{
ListItem<T>* toSearch = head;
int occurence = 0;
while(toSearch->getNext() != NULL)
{
if(toSearch->getData() == item)
{
return occurence;
}
occurence++;
toSearch = toSearch->getNext();
}
return -1;
}
template<class T>
void List<T>::sort()
{
if(listSize >= 2)
{
for(int i = 0; i < listSize; i++)
{
ListItem<T>* current = head;
for(int j = 0; j < i; j++)
{
current = current->getNext();
}
T minElement = current->getData();
ListItem<T>* minElementPosition = current;
for(ListItem<T>* j = current->getNext();
j != NULL && j->getNext() != NULL; j = j->getNext())
{
if(j->getData() < minElement)
{
minElement = j->getData();
minElementPosition = j;
}
}
T hold = minElement;
minElementPosition->setData(current->getData());
current->setData(hold);
}
}
}
template<class T>
int List<T>::size()
{
return listSize;
}
template<class T>
ListItem<T>::ListItem()
{
this->next = NULL;
}
template<class T>
ListItem<T>::ListItem(const T &item)
{
this->data = item;
this->setNext(NULL);
}
template<class T>
void ListItem<T>::setNext(ListItem<T> *next)
{
this->next = next;
}
template<class T>
ListItem<T>* ListItem<T>::getNext() const
{
return this->next;
}
template<class T>
void ListItem<T>::setData(const T &data)
{
this->data = data;
}
template<class T>
T& ListItem<T>::getData()
{
return this->data;
}
template<class T>
ListItem<T>& ListItem<T>::operator=(ListItem<T> arg)
{
this->data = arg.getData();
return *this;
}
#endif
knight.h
#ifndef KNIGHT_H
#define KNIGHT_H
#include <string>
#include <vector>
using namespace std;
class knight
{
private:
string name;
int ballads;
float armorWeight;
bool ladyLove;
vector<int> computePrefixFunction(const string &s);
public:
knight();
knight(const knight &obj);
void setName(string _name);
string getName() const;
void setBallads(int _ballads);
int getBallads() const;
void setArmorWeight(float _weight);
float getArmorWeight() const;
void setLadyLove(bool _ladyLove);
bool hasLadyLove() const;
void randomData();
int findInName(const string& s);
bool practiceTask();
bool hasVowelsOnEvenPositions();
friend ostream& operator<<(ostream& os, knight& obj);
friend istream& operator>>(istream& is, knight& obj);
bool operator==(const knight& obj);
bool operator>(const knight& obj);
bool operator<(const knight& obj);
};
#endif
knight.cpp
#include <istream>
#include <math.h>
#include <string>
#include <vector>
#include "knight.h"
using namespace std;
knight::knight()
{
}
knight::knight(const knight &obj)
{
setName(obj.getName());
setBallads(obj.getBallads());
setArmorWeight(obj.getArmorWeight());
setLadyLove(obj.hasLadyLove());
}
void knight::setName(string _name)
{
name = _name;
}
string knight::getName() const
{
return name;
}
void knight::setBallads(int _ballads)
{
ballads = _ballads;
}
int knight::getBallads() const
{
return ballads;
}
void knight::setArmorWeight(float _weight)
{
armorWeight = _weight;
}
float knight::getArmorWeight() const
{
return armorWeight;
}
void knight::setLadyLove(bool _ladyLove)
{
ladyLove = _ladyLove;
}
bool knight::hasLadyLove() const
{
return ladyLove;
}
string randomString();
string randomString()
{
int randomSize = 5 + rand() % 5;
char randChar = 'A' + rand() % 26;
string randStr;
randStr += randChar;
for(int i = 0; i < randomSize; i++)
{
randChar = 'a' + rand() % 26;
randStr += randChar;
}
return randStr;
}
void knight::randomData()
{
setName(randomString());
setArmorWeight(10.0 + (rand() % 16) / 3.0);
setBallads(rand() % 15);
setLadyLove(rand() % 2 == 0 ? true : false);
}
int knight::findInName(const string &s)
{
vector<int> pf = computePrefixFunction(s);
const string t = name;
int k = 0, j = 0;
for (int i = 0, k = pf[0]; i < t.size();)
{
j = 0;
while(i + j < t.size() && j + k < s.size() && t[i + j] == s[j + k])
{
j++;
}
if(j + k == s.size())
{
return i;
}
if(j == 0)
{
i ++;
k = 0;
}
else
{
i += j;
k = pf[j];
}
}
return (-1);
}
bool knight::practiceTask()
{
if(this->hasVowelsOnEvenPositions() &&
((int)floor(this->getArmorWeight() * 1000) % 10) == 3)
{
return true;
}
else
{
return false;
}
}
bool knight::hasVowelsOnEvenPositions()
{
for(int i = 1; i < name.length(); i += 2)
{
if((name[i] != 'a') &&
(name[i] != 'e') &&
(name[i] != 'i') &&
(name[i] != 'o') &&
(name[i] != 'u'))
{
return false;
}
}
return true;
}
ostream& operator<<(ostream& os, knight& obj)
{
os<<obj.getName()<<"\n"<<obj.getBallads()<<"\n"<<obj.getArmorWeight()<<"\n"<<obj.hasLadyLove()<<"\n\n";
return os;
}
istream& operator>>(istream& is, knight& obj)
{
string n;
int b;
float a;
bool l;
is>>n>>b>>a>>l;
obj.setName(n);
obj.setBallads(b);
obj.setArmorWeight(a);
obj.setLadyLove(l);
return is;
}
bool knight::operator==(const knight& obj)
{
if(this->getName() == obj.getName() &&
this->getBallads() == obj.getBallads() &&
this->getArmorWeight() == obj.getArmorWeight() &&
this->hasLadyLove() == obj.hasLadyLove())
{
return true;
}
else
{
return false;
}
}
bool knight::operator>(const knight& obj)
{
if(this->getArmorWeight() > obj.getArmorWeight())
{
return true;
}
else
{
return false;
}
}
bool knight::operator<(const knight& obj)
{
if(this->getArmorWeight() < obj.getArmorWeight())
{
return true;
}
else
{
return false;
}
}
vector<int> knight::computePrefixFunction(const string &s)
{
int len = s.size();
vector<int> p(len);
p[0] = 0;
int k = 0;
for(int i = 1; i < len; i++)
{
while((k > 0) && (s[k] != s[i]))
{
k = p[k - 1];
}
if (s[k] == s[i])
{
k++;
}
p[i] = k;
}
return p;
}
hash.h
#ifndef _HASH_H
#define _HASH_H
#include <iostream>
#include <math.h>
#include <vector>
#include "list.h"
using namespace std;
template<class K, class V>
class Pair
{
private:
K key;
V value;
public:
Pair();
Pair(const K& key, const V& value);
void setKey(const K& key);
void setValue(const V& value);
K getKey() const;
V getValue() const;
bool operator==(const Pair& obj);
};
template<class K, class V>
Pair<K, V>::Pair()
{
}
template<class K, class V>
Pair<K, V>::Pair(const K& key, const V& value)
{
this->key = key;
this->value = value;
}
template<class K, class V>
void Pair<K, V>::setKey(const K& key)
{
this->key = key;
}
template<class K, class V>
void Pair<K, V>::setValue(const V& value)
{
this->value = value;
}
template<class K, class V>
K Pair<K, V>::getKey() const
{
return key;
}
template<class K, class V>
V Pair<K, V>::getValue() const
{
return value;
}
template<class K, class V>
bool Pair<K, V>::operator==(const Pair& obj)
{
return key == obj.getKey();
}
//Hash itself
const double hashFunctionConstant = 0.618;
template<class K, class V>
class Hash
{
private:
vector<List<Pair<K, V> > > table;
int maxSize;
int currentSize;
int hashFunction(K key);
public:
Hash(int size);
~Hash();
void add(K key, V value);
V get(K key);
int size();
};
template<class K, class V>
Hash<K, V>::Hash(int size)
{
maxSize = size;
for(int i = 0; i < maxSize; i++)
{
List<Pair<K, V> > tmp;
table.push_back(tmp);
}
currentSize = 0;
}
template<class K, class V>
Hash<K, V>::~Hash()
{
}
template<class K, class V>
void Hash<K, V>::add(K key, V value)
{
Pair<K, V> newPair(key, value);
table[hashFunction(key)].pushFront(newPair);
}
template<class K, class V>
V Hash<K, V>::get(K key)
{
int hf = hashFunction(key);
if(!table[hf].empty())
{
Pair<K, V> toSearch;
toSearch.setKey(key);
return table[hf].at(table[hf].search(toSearch)).getValue();
}
}
template<class K, class V>
int Hash<K, V>::hashFunction(K key)
{
return floor(maxSize * (key * hashFunctionConstant - floor(key * hashFunctionConstant)));
}
#endif
Висновки:
Мною була розроблена хеш-таблиця. Було забезпечено реалізацію основних операторів:
-
пошук елемента;
-
запис елемента;
-
читання елемента.
У ході реалізації цих операторів труднощів не виникало. Також я дізнався, що розрізняють:
-
відкрите хешування — усі елементи, що хешуються в одну комірку, об’єднуються у зв’язний список
-
закрите хешування — усі елементи зберігаються безпосередньо у хеш-таблиці, при потраплянні у зайняту комірку обирається послідовність інших хеш-значень.