KP___2

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

#define N 227
#define N1 100
#define GR 31000


typedef struct{
    int key;
}item;

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

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

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

List* addL(List * head, item * it);
List* delL(List * head, item * it);
item * searchL(List * head, int key);

void adr_In(AdrHashT * T);
item * adr_Search(AdrHashT * T, int key);
int adr_Ins(AdrHashT * T, item * it);
void adr_Del(AdrHashT * T, item * it);


void c_In(HashC * T, int n);
item * c_Search(HashC * T, int key);
void c_Ins(HashC * T, item * it);
void c_Del(HashC * T, item * it);


int h(int key, int div);
void getP();
void showP(int div);

int minC = 1000, maxC = 0, minS = 1000, maxS = 0, midC = 0, midS = 0;

int cmp = 0;

int swap = 0;

int main()
{
    srand(time(0));
    int mas[N], i;


    AdrHashT * daT = (AdrHashT *)malloc(sizeof(AdrHashT));
    adr_In(daT);
    int sizeT = sizeof(AdrHashT) + sizeof(item[GR]);
    for(i = 0; i < N; i++){
        item * it = (item *)malloc(sizeof(item));
        while(1){
            mas[i] = rand() % GR;
            it->key = mas[i];
            if(adr_Ins(daT, it))break;
        }
        getP();
    }
    printf("Direct adressing:\nHash table size: %d byte; Extra memory 0 byte\nAdding:\n", sizeT);
    showP(N);

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

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

        getP();
    }
    printf("Delete:\n");
    showP(N);

    HashC * chT = (HashC *)malloc(sizeof(HashC));
    c_In(chT, N);
    sizeT = sizeof(HashC)+ 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() % GR;
        it->key = mas[i];
        c_Ins(chT, it);
        getP();
    }
    printf("Method Lanc:\nHash table size: %d bytes;  Extra memory %d bytes\nAdded:\n", sizeT, sizeD);
    showP(N);

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

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

        getP();
    }
    printf("Delete:\n");
    showP(N);
    free(chT);

    HashC * chTN = (HashC *)malloc(sizeof(HashC));
    c_In(chTN, N1);
    sizeT = sizeof(HashC)+ 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() % GR;
        it->key = mas[i];
        c_Ins(chTN, it);
        getP();
    }
    printf("Method Lanc 100:\nHash table size: %d bytes;  Extra memory %d bytes\nAdded:\n", sizeT, sizeD);
    showP(N1);

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

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

        getP();
    }
    printf("Delete:\n");
    showP(N1);
    return 0;
}


void adr_In(AdrHashT * T){
    T->n=GR;
    T->array =(item *)malloc(sizeof(item[T->n]));
    int i;
    for(i = 0; i < T->n; i++){
        T->array[i]=NULL;
    }
}
item * adr_Search(AdrHashT * T, int key){
    return T->array[key];
}

int adr_Ins(AdrHashT * T, item * it){
    cmp++;
    if(T->array[it->key] == NULL){
        swap++;
        T->array[it->key] = it;
        return 1;
    }
    return 0;
}
void adr_Del(AdrHashT * T, item * it){
    swap++;
    T->array[it->key] = NULL;
}

void c_In(HashC * T, int n){
    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 * c_Search(HashC * T, int key){
    return searchL(T->array[h(key, T->n)], key);
}

void c_Ins(HashC * T, item * it){
    swap++;
    T->array[h(it->key, T->n)] = addL(T->array[h(it->key, T->n)], it);
}
void c_Del(HashC * T, item * it){
    swap++;
    T->array[h(it->key, T->n)] = delL(T->array[h(it->key, T->n)], it);
}

int h(int it, int div){
    return it % div;
}


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

        }
        cmp++;
        swap+=2;
        tmp->next = list;
        list->prev = tmp;
    }
    return head;
}
List* delL(List * head, item * itm){
    List * tmp, * temp = head;
    cmp++;
    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){
            cmp += 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;
        }
        cmp++;
    }
    return head;
}
item * searchL(List * head, int key){
    while(head != NULL){
        cmp+=2;
        if(head->it->key == key){
            return head->it;
        }
        head = head->next;
        swap++;
    }
    cmp++;
    return NULL;
}

void showP(int div){
    printf("Sravn:\t min: %d,   mid: %.2f,   max: %d\n", minC, (double)midC/div, maxC);
    printf("Copy:\t min: %d,   mid: %.2f,   max: %d\n\n", minS, (double)midS/div, maxS);
    minC = minS = 1000;
    maxC = maxS = midC = midS = 0;
}

void getP(){
    midC += cmp;
    if(minC > cmp)minC = cmp;
    if(maxC < cmp)maxC = cmp;

    midS += swap;
    if(minS > swap)minS = swap;
    if(maxS < swap)maxS = swap;

    cmp = swap = 0;
}