KP_2

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <time.h>

#define N 227
#define N1 100
#define MAX 31000

int compare = 0;
int swap = 0;

int minCompare = 1000, maxCompare = 0, minSwap = 1000, maxSwap = 0, midCompare = 0, midSwap = 0;

typedef struct{
    int key;
}item;

typedef struct{
    int n;
    item ** array;
}DAHashTable;

typedef struct MyList{
    item * it;
    struct MyList * next;
    struct MyList * prev;
}List;


typedef struct{
    int n;
    List ** array;
}CHHashTable;

void DA_INIT(DAHashTable * T);
int DA_INSERT(DAHashTable * T, item * it);
void DA_DELETE(DAHashTable * T, item * it);
item * DA_SEARCH(DAHashTable * T, int key);

void CH_INIT(CHHashTable * T);
void CH_INSERT(CHHashTable * T, item * it);
void CH_DELETE(CHHashTable * T, item * it);
item * CH_SEARCH(CHHashTable * T, int key);
List* addToList(List * head, item * it);
List* deleteFromList(List * head, item * it);
item * searchInList(List * head, int key);

int h(int key);
void calculateCS();
void displayCS();



int main()
{
    srand(time(0));
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int mas[N], i;
    //Пряма адресація
    DAHashTable * daT = (DAHashTable *)malloc(sizeof(DAHashTable));
    DA_INIT(daT);
    int sizeT = sizeof(DAHashTable) + sizeof(item[MAX]);
    for(i = 0; i < N; i++){
        item * it = (item *)malloc(sizeof(item));
        while(1){
            mas[i] = rand() % MAX;
            it->key = mas[i];
            if(DA_INSERT(daT, it))break;
        }
        calculateCS();
    }
    printf("Direct adressing:\nHash table size: %d байт; Extra memory 0 байт\nAdding:\n", sizeT);
    displayCS();

    for(i = 0; i < N; i++){
        item * it = DA_SEARCH(daT, mas[i]);
        calculateCS();
    }
    printf("Search:\n");
    displayCS();

    for(i = 0; i < N; i++){
        item * it = DA_SEARCH(daT, mas[i]);
        DA_DELETE(daT, it);

        calculateCS();
    }
    printf("Delete:\n");
    displayCS();

    //Метод Ланцюгів
    CHHashTable * chT = (CHHashTable *)malloc(sizeof(CHHashTable));
    CH_INIT(chT);
    sizeT = sizeof(CHHashTable)+ sizeof(List)*N + sizeof(item)*N;///SIZE
    int sizeD = sizeof(List)*N;
    for(i = 0; i < N; i++){
        item * it = (item *)malloc(sizeof(item));
        mas[i] = rand() % MAX;
        it->key = mas[i];
        CH_INSERT(chT, it);
        calculateCS();
    }
    printf("Method Lanc:\nHash table size: %d bytes;  Extra memory %d bytes\nAdded:\n", sizeT, sizeD);
    displayCS();

    for(i = 0; i < N; i++){
        item * it = CH_SEARCH(chT, mas[i]);
        calculateCS();
    }
    printf("Search:\n");
    displayCS();

    for(i = N-1; i >=0; i--){
        item * it = CH_SEARCH(chT, mas[i]);
        CH_DELETE(chT, it);

        calculateCS();
    }
    printf("Delete:\n");
    displayCS();


    //Метод Ланцюгів 100
    CHHashTable * chTN = (CHHashTable *)malloc(sizeof(CHHashTable));
    CH_INIT(chTN);
    sizeT = sizeof(CHHashTable)+ sizeof(List)*N1 + sizeof(item)*N1;///SIZE
    sizeD = sizeof(List)*N1;
    for(i = 0; i < N1; i++){
        item * it = (item *)malloc(sizeof(item));
        mas[i] = rand() % MAX;
        it->key = mas[i];
        CH_INSERT(chTN, it);
        calculateCS();
    }
    printf("Method Lanc 100:\nHash table size: %d bytes;  Extra memory %d bytes\nAdded:\n", sizeT, sizeD);
    displayCS();

    for(i = 0; i < N1; i++){
        item * it = CH_SEARCH(chTN, mas[i]);
        calculateCS();
    }
    printf("Search:\n");
    displayCS();

    for(i = N1-1; i >=0; i--){
        item * it = CH_SEARCH(chTN, mas[i]);
        CH_DELETE(chTN, it);

        calculateCS();
    }
    printf("Delete:\n");
    displayCS();
    return 0;
}


//З прямою адресацією
void DA_INIT(DAHashTable * T){
    T->n=MAX;
    T->array =(item *)malloc(sizeof(item[T->n]));
    int i;
    for(i = 0; i < T->n; i++){
        T->array[i]=NULL;
    }
}
item * DA_SEARCH(DAHashTable * T, int key){
    return T->array[key];
}

int DA_INSERT(DAHashTable * T, item * it){
    compare++;
    if(T->array[it->key] == NULL){
        swap++;
        T->array[it->key] = it;
        return 1;
    }
    return 0;
}
void DA_DELETE(DAHashTable * T, item * it){
    swap++;
    T->array[it->key] = NULL;
}

void CH_INIT(CHHashTable * T){
    T->n=N;
    T->array =(List *)malloc(sizeof(List[T->n]));
    int i;
    for(i = 0; i < T->n; i++){
        T->array[i]=NULL;
    }
}
item * CH_SEARCH(CHHashTable * T, int key){
    return searchInList(T->array[h(key)], key);
}

void CH_INSERT(CHHashTable * T, item * it){
    swap++;
    T->array[h(it->key)] = addToList(T->array[h(it->key)], it);
}
void CH_DELETE(CHHashTable * T, item * it){
    swap++;
    T->array[h(it->key)] = deleteFromList(T->array[h(it->key)], it);
}

int h(int it){
    return it % N;
}


List * addToList(List * head, item * it){
    List * tmp = head;
    List * list = (List *)malloc(sizeof(List));
    swap+=2;
    list->it = it;
    list->next = NULL;
    compare++;
    if(head == NULL){
        swap+=2;
        head = list;
        list->prev = NULL;
    }
    else{
        while(tmp->next != NULL){
            compare++;
            swap++;
            tmp = tmp->next;

        }
        compare++;
        swap+=2;
        tmp->next = list;
        list->prev = tmp;
    }
    return head;
}
List* deleteFromList(List * head, item * itm){
    List * tmp, * temp = head;
    compare++;
    if(head->it->key == itm->key){
        swap+=3;
        tmp = head;
        head = head->next;
        if(head != NULL)head->prev = NULL;
        free(tmp);
    }
    else{
        while(temp->next != NULL){
            compare += 2;
            if((temp->next)->it->key == itm->key){
                swap+=3;
                tmp = temp->next;
                if (tmp->next!=NULL) tmp->next->prev = temp;//???
                temp->next = tmp->next;
                free(tmp);
                break;
            }
            swap++;
            temp = temp->next;
        }
        compare++;
    }
    return head;
}
item * searchInList(List * head, int key){
    while(head != NULL){
        compare+=2;
        if(head->it->key == key){
            return head->it;
        }
        head = head->next;
        swap++;

//        printf("%d ", head->it->key);
    }
    compare++;
    return NULL;
}

void calculateCS(){
    midCompare += compare;
    if(minCompare > compare)minCompare = compare;
    if(maxCompare < compare)maxCompare = compare;

    midSwap += swap;
    if(minSwap > swap)minSwap = swap;
    if(maxSwap < swap)maxSwap = swap;

    compare = swap = 0;
}
void displayCS(){
    printf("Sravn:\t min: %d,   mid: %.2f,   max: %d\n", minCompare, (double)midCompare/N, maxCompare);
    printf("Copy:\t min: %d,   mid: %.2f,   max: %d\n\n", minSwap, (double)midSwap/N, maxSwap);
    minCompare = minSwap = 1000;
    maxCompare = maxSwap = midCompare = midSwap = 0;
}