Хешування

Тернопільський національний технічний університет імені Івана Пулюя

Факультет комп’ютерно-інформаційних систем та програмної інженерії

Кафедра програмної інженерії

ЗВІТ

До лабораторної роботи №4

“ Хешування ”

з навчальної дисципліни <<Алгоритми та структури даних >>

Підготував:

Студент

групи СП-12

Мінько Віталій

Тернопіль 2017

Мета роботи:набути практичних навичок по реалізації хеш-таблиць з відкритим хешуванням

Короткі теоретичні відомості : 

Хеш-таблиця являє собою узагальнення звичайного масиву. Вона використовується тоді , коли не зручно використовувати масив.

h()- хеш-функція.

Кажуть, що елемент з ключем k хешується в комірку h(k).

Величина h(k) називається хеш-значенням ключа k.

Елементи хеш-таблиці ще називаються сегментами хеш-таблиці.

Хеш-таблиці бувають: -Відкриті,-Закриті.

Функції хеш-таблиць :

MAKENULL - створення хеш-таблиці
MEMBER - перевірка на наявність елемента в хеш-таблиці
INSERT - вставка елемента в таблицю
DELETE - видалення елеманта з таблиці
PRINT  - друк таблиці

Завдання : Реалізувати функції для робот из хеш-таблицею на основі методу відкритого хешування. В якості елементів хеш-таблиці вибрати стрічки (масив символів).

typedef char nametype[20];

struct celltype {

    nametype element;

    celltype* next;

};

const int DICT_SIZE = 5;

typedef celltype* DICTIONARY[DICT_SIZE];

//хеш-функція

int hash (nametype x) {

    int sum = 0;

     for (unsigned int i = 0; i < strlen(x); i++)

         sum += (int) x[i];

    return sum % (DICT_SIZE) ;

}

MAKENULL

void MAKENULL (DICTIONARY A){

for(int i=0;i

                A[i]=NULL;

}

MEMBER

bool MEMBER (nametype x,DICTIONARY A){

        celltype* current;

        current=A[hash(x)];

        while(current !=NULL){

                if(current->element == x)

                        return true;

                else

                        current=current->next;

                        return false;

        }

}
INSERT

void INSERT(nametype x,DICTIONARY A){

        int bucket;

        celltype* oldheader;

        if(MEMBER(x,A)==false){

                bucket=hash(x);

                oldheader=A[bucket];

                new A[bucket];

                A[bucket]element=x;

                A[bucket]->next=oldheader;