HASH 3 // HASH 1이랑 뭐가 다른지 잘 모르겠음

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX 1000

#define SIZE 16

typedef struct data

{

int key;

int next;

}data;

data dT[MAX]; // dataTable

data freeCount;

int a[MAX],

hT[SIZE], // hashTable

freeList = 0,

insertCount = 0,

length[SIZE],

searchCount = 0,

removeCount=0

;

void insert(int k);

void remove(int k);

void lengthCount();

int search(int k);

void main()

{

int i;

srand((unsigned)time(NULL));

for(i=0;i<MAX;i++)

dT[i].next = i+1;

for(i=0;i<SIZE;i++)

hT[i] = -1;

for(i=0;i<MAX;i++)

{

a[i] =(rand() % 2)*10000000 + (rand() % 2)*1000000+ (rand() % 2)*100000 +(rand() % 2)*10000+

(rand() % 2)*1000 + (rand() % 2)*100+ (rand() % 2)*10 +(rand() % 2)  ;

insert(a[i]);

}

printf("\ta[i]\tdT[i]\n");

for(i=0;i<10;i++) // 일단 열 개만 프린트

printf("%10d %10d\n", a[i], dT[i].key);

printf("insertCount %6d Average %6.2f\n", insertCount, (double)insertCount/(double)MAX);

lengthCount();

for(i=0;i<MAX;i++)

{

search(a[i]);

}

printf("searchCount %6d Average %6.2f\n", searchCount, (double)searchCount/(double)MAX);

for(i=0;i<MAX;i++)

{

remove(a[i]);

}

printf("removeCount %6d Average %6.2f\n", removeCount, (double)removeCount/(double)MAX);

}

void insert(int k)

{

int homeBucket, temp;

homeBucket = k % SIZE;

temp = hT[homeBucket];

if (temp == -1)

{

dT[freeList].key = k;

dT[freeList].next = hT[homeBucket];

hT[homeBucket] = freeList;

freeList++;

insertCount++;

length[homeBucket]++;

}

else if(temp != -1)

{

if(temp == dT[temp].key)

{

insertCount++; // 지금 들어온 값이랑 원래 있는 값이 같으면 안 집어 넣는다.

}

else if(temp != dT[temp].key)

{

while(temp != -1)

{

temp = dT[temp].next; // 다르면 그 전 값을 찾아간다.

if(temp == dT[temp].key)

{

break; // 지금 들어온 값이랑 원래 있는 값이 같으면 안 집어 넣는다.

}

insertCount++;

}

if(temp == -1)

{

dT[freeList].key = k;

dT[freeList].next = hT[homeBucket];

hT[homeBucket] = freeList;

freeList++;

length[homeBucket]++;

}

}

}

}

void lengthCount()

{

int min = MAX, max = 0, i,

maxCount = 0,

minCount = 0,

total = 0;

for(i=0; i< SIZE; i++)

{

if (length[i] > max)

{

max = length[i];

maxCount = 0;

}

if (length[i] < min)

{

min = length[i];

minCount = 0;

}

if (length[i] == max)

maxCount++;

if (length[i] == min)

minCount++;

total += length[i];

}

printf("min length %3d:%3dea \tmax length %3d:%3dea\naverage : %3.2f\n", min, minCount, max, maxCount, (double)total/(double)SIZE);

}

int search(int k)

{

int temp;

int homeBucket = k % SIZE;

for(temp = hT[homeBucket]; dT[temp].next != -1 ; temp = dT[temp].next)

{

searchCount++;

if(dT[temp].key = k)

return dT[temp].key;

}

return -1;

}

void remove(int k)

{

int homeBucket, temp;

homeBucket = k % SIZE;

temp = hT[homeBucket];

if (temp == -1)

{

; // 빈 칸이라서 아무 것도 안함

}

else if(temp != -1)

{

if(temp == dT[temp].key)

{

// 지금 들어온 값이랑 원래 있는 값이 같으면 해시에서 삭제하고

// 데이터에서 삭제하고 프리해준다.

freeList = temp;

freeCount = dT[temp];

hT[homeBucket] = dT[temp].next;

removeCount++;

}

else if(temp != dT[temp].key)

{

while(temp != -1)

{

temp = dT[temp].next; // 다르면 그 전 값을 찾아간다.

if(temp == dT[temp].key) // 같으면 삭제 한다.

{

freeList = temp;

freeCount = dT[temp];

hT[homeBucket] = dT[temp].next;

}

removeCount++;

}

if(temp == -1)

{

;// 같은 값이 없으면 아무 것도 안한다.

}

}

}

}