Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <iostream>
- using namespace std;
- #define CAPACITY 50000 // размер хеш таблицы
- unsigned long hash_function(char* str) {
- unsigned long i = 0;
- for (int j=0; str[j]; j++)
- i += str[j];
- return i % CAPACITY;
- }
- typedef struct Ht_item Ht_item;
- // определение элементов хеш-таблицы
- struct Ht_item {
- char* key;
- char* value;
- };
- typedef struct LinkedList LinkedList;
- // определеине связного списка
- struct LinkedList {
- Ht_item* item;
- LinkedList* next;
- };
- typedef struct HashTable HashTable;
- // определение хеш таблицы
- struct HashTable {
- // содержание массива указателей
- // на элементы
- Ht_item** items;
- LinkedList** overflow_buckets;
- int size;
- int count;
- };
- static LinkedList* allocate_list () {
- // выделение памяти для указателя списка
- LinkedList* list = (LinkedList*) calloc (1, sizeof(LinkedList));
- return list;
- }
- static LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) {
- // вставляем элемент в связный список
- if (!list) {
- LinkedList* head = allocate_list();
- head->item = item;
- head->next = NULL;
- list = head;
- return list;
- }
- else if (list->next == NULL) {
- LinkedList* node = allocate_list();
- node->item = item;
- node->next = NULL;
- list->next = node;
- return list;
- }
- LinkedList* temp = list;
- while (temp->next) {
- temp = temp->next;
- }
- LinkedList* node = allocate_list();
- node->item = item;
- node->next = NULL;
- temp->next = node;
- return list;
- }
- static Ht_item* linkedlist_remove(LinkedList* list) {
- // удаление хеда связного списка
- if (!list)
- return NULL;
- if (!list->next)
- return NULL;
- LinkedList* node = list->next;
- LinkedList* temp = list;
- temp->next = NULL;
- list = node;
- Ht_item* it = NULL;
- memcpy(temp->item, it, sizeof(Ht_item));
- free(temp->item->key);
- free(temp->item->value);
- free(temp->item);
- free(temp);
- return it;
- }
- static void free_linkedlist(LinkedList* list) {
- LinkedList* temp = list;
- if (!list)
- return;
- while (list) {
- temp = list;
- list = list->next;
- free(temp->item->key);
- free(temp->item->value);
- free(temp->item);
- free(temp);
- }
- }
- static LinkedList** create_overflow_buckets(HashTable* table) {
- // создание переполнения массива связных списков
- LinkedList** buckets = (LinkedList**) calloc (table->size, sizeof(LinkedList*));
- for (int i=0; i<table->size; i++)
- buckets[i] = NULL;
- return buckets;
- }
- static void free_overflow_buckets(HashTable* table) {
- // очищение всех списков массивов переполнения
- LinkedList** buckets = table->overflow_buckets;
- for (int i=0; i<table->size; i++)
- free_linkedlist(buckets[i]);
- free(buckets);
- }
- Ht_item* create_item(char* key, char* value) {
- // создание указателя на новую хеш-таблицу
- Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item));
- item->key = (char*) calloc (strlen(key) + 1, sizeof(char));
- item->value = (char*) calloc (strlen(value) + 1, sizeof(char));
- strcpy(item->key, key);
- strcpy(item->value, value);
- return item;
- }
- HashTable* create_table(int size) {
- // создание новой хеш-таблицы
- HashTable* table = (HashTable*) malloc (sizeof(HashTable));
- table->size = size;
- table->count = 0;
- table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*));
- for (int i=0; i<table->size; i++)
- table->items[i] = NULL;
- table->overflow_buckets = create_overflow_buckets(table);
- return table;
- }
- void free_item(Ht_item* item) {
- // очищение эелементов
- free(item->key);
- free(item->value);
- free(item);
- }
- void free_hashtable(HashTable* table) {
- // очищение таблицы
- for (int i=0; i<table->size; i++) {
- Ht_item* item = table->items[i];
- if (item != NULL)
- free_item(item);
- }
- free_overflow_buckets(table);
- free(table->items);
- free(table);
- }
- void handle_collision(HashTable* table, unsigned long index, Ht_item* item) {
- LinkedList* head = table->overflow_buckets[index];
- if (head == NULL) {
- // создаем список
- head = allocate_list();
- head->item = item;
- table->overflow_buckets[index] = head;
- return;
- }
- else {
- // вставляем в список
- table->overflow_buckets[index] = linkedlist_insert(head, item);
- return;
- }
- }
- void ht_insert(HashTable* table, char* key, char* value) {
- // создаем элемент
- Ht_item* item = create_item(key, value);
- // вычисляем индекс
- int index = hash_function(key);
- Ht_item* current_item = table->items[index];
- if (current_item == NULL) {
- // ключ не существует
- if (table->count == table->size) {
- // хеш-таблица переполнена
- printf("Insert Error: Hash Table is full\n");
- // удалить созданный элемент
- free_item(item);
- return;
- }
- // вставить напрямую
- table->items[index] = item;
- table->count++;
- }
- else {
- // Сценарий 1: нам нужно обновить только value
- if (strcmp(current_item->key, key) == 0) {
- free(table->items[index]->value);
- table->items[index]->value = (char*) calloc (strlen(value) + 1, sizeof(char));
- strcpy(table->items[index]->value, value);
- free_item(item);
- return;
- }
- else {
- // Сценарий 2: коллизия
- handle_collision(table, index, item);
- return;
- }
- }
- }
- char* ht_search(HashTable* table, char* key) {
- // Searches the key in the hashtable
- // and returns NULL if it doesn't exist
- int index = hash_function(key);
- Ht_item* item = table->items[index];
- LinkedList* head = table->overflow_buckets[index];
- // Ensure that we move to items which are not NULL
- while (item != NULL) {
- if (strcmp(item->key, key) == 0)
- return item->value;
- if (head == NULL)
- return NULL;
- item = head->item;
- head = head->next;
- }
- return NULL;
- }
- void ht_delete(HashTable* table, char* key) {
- // удаление элементов из таблицы
- unsigned long index = hash_function(key);
- Ht_item* item = table->items[index];
- LinkedList* head = table->overflow_buckets[index];
- if (item == NULL) {
- // не существует
- return;
- }
- else {
- if (head == NULL && strcmp(item->key, key) == 0) {
- // нет цепочки коллизии. удалить элемент
- // и установить индекс таблицы на ноль
- table->items[index] = NULL;
- free_item(item);
- table->count--;
- return;
- }
- else if (head != NULL) {
- // цепочка коллизий существует
- if (strcmp(item->key, key) == 0) {
- // удалить этот элемент и установить заголовок списка
- // как новый элемент
- free_item(item);
- LinkedList* node = head;
- head = head->next;
- node->next = NULL;
- table->items[index] = create_item(node->item->key, node->item->value);
- free_linkedlist(node);
- table->overflow_buckets[index] = head;
- return;
- }
- LinkedList* curr = head;
- LinkedList* prev = NULL;
- while (curr) {
- if (strcmp(curr->item->key, key) == 0) {
- if (prev == NULL) {
- // первый элемент цеполчки. удалить цепочку
- free_linkedlist(head);
- table->overflow_buckets[index] = NULL;
- return;
- }
- else {
- // в цепочке
- prev->next = curr->next;
- curr->next = NULL;
- free_linkedlist(curr);
- table->overflow_buckets[index] = head;
- return;
- }
- }
- curr = curr->next;
- prev = curr;
- }
- }
- }
- }
- void print_search(HashTable* table, char* key) {
- char* val;
- if ((val = ht_search(table, key)) == NULL) {
- printf("%s does not exist\n", key);
- return;
- }
- else {
- printf("Key:%s, Value:%s\n", key, val);
- }
- }
- void print_hashtable(HashTable* table) {
- printf("\n-------------------\n");
- for (int i=0; i<table->size; i++) {
- if (table->items[i]) {
- printf("Index:%d, Key:%s, Value:%s", i, table->items[i]->key, table->items[i]->value);
- if (table->overflow_buckets[i]) {
- printf(" => Overflow Bucket => ");
- LinkedList* head = table->overflow_buckets[i];
- while (head) {
- printf("Key:%s, Value:%s ", head->item->key, head->item->value);
- head = head->next;
- }
- }
- printf("\n");
- }
- }
- printf("-------------------\n");
- }
- int main() {
- char key[256],value[256];
- int n;
- cout << "Введите количество элементов таблицы: ";
- cin >> n;
- cin.ignore();
- HashTable* ht = create_table(CAPACITY);
- for(int i=0;i<n;i++){
- cout << "Введите ключ: ";
- cin.getline(key,256);
- cout << "Введите значение: ";
- cin.getline(value,256);
- ht_insert(ht, key, value);
- print_search(ht, key);
- print_search(ht, value);
- }
- /*ht_insert(ht, "1", "First address");
- ht_insert(ht, "2", "Second address");
- ht_insert(ht, "Hel", "Third address");
- ht_insert(ht, "Cau", "Fourth address");
- print_search(ht, "1");
- print_search(ht, "2");
- print_search(ht, "3");
- print_search(ht, "Hel");
- print_search(ht, "Cau"); // коллизия!*/
- print_hashtable(ht);
- ht_delete(ht, key);
- ht_delete(ht, value);
- print_hashtable(ht);
- free_hashtable(ht);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement