해시테이블

난수 생성하고 해시테이블 저장 . 그후 탐색, 삭제, 삽입 탐색 을 실행함.

C로 작성 

 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_Num 30

#define Max_num1 10

#define Hash_table 61

#define random 200

 

int gethashkey(int n)

{

int h;

h = n % Hash_table;

return h;

}

int search(int n,int Hash[])

{

int key;

key = gethashkey(n);

if(*(Hash+key) == n)

return n;

else {

key = gethashkey(n+key);

if(*(Hash+key) == n)

return n;

else

return 0;

}

 

}

void deleteHash(int n,int Hash[])

{

int delhash,key;

key = gethashkey(n);

delhash = search(n,Hash);

if(delhash == NULL)

return;

else

{

if(*(Hash+key) == delhash)

*(Hash+key) = -1;

}

}

void insertHash(int n,int Hash[]){

int inhash,key;

key = gethashkey(n);

inhash = search(n,Hash);

if(inhash == NULL)

if(*(Hash+key)== 0 || *(Hash+key) == -1)

*(Hash+key) = n;

else{

while(*(Hash+key) != 0)

key = gethashkey(n+key);

*(Hash+key) = n;

}

}

void main(void)

{

int i,j,key,arr[MAX_Num] = {0},Hash[Hash_table] = {0};

srand(time(NULL));

for(i = 0 ; i<MAX_Num; i++){

*(arr + i) = rand() % random +1;

//난수

for(j=0 ; j<i ; j++) {

if(*(arr+j) == *(arr+i))

i--;

//중복 제거

}

}

 

for(i = 0 ; i<MAX_Num; i++){

key = gethashkey(*(arr + i));

while(*(Hash+key) != 0)

key = gethashkey(*(arr + i)+key);

*(Hash+key) = *(arr+i);

}

 

printf("%d개의 난수\n",MAX_Num);

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

printf("%4d",*(arr+i));

 

printf("\n\n최초의 해시 테이블\n");

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

printf("%4d",*(Hash+i));

 

printf("\n\n탐색 난수 %d개\n",Max_num1);

for(i = 0 ; i<Max_num1; i++){

*(arr + i) = rand() % random +1;

 

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

if(*(arr+j) == *(arr+i))

i--;

}

for(i = 0 ; i<Max_num1; i++){

printf("%4d",*(arr+i));

}

printf("\n\n탐색 결과\n");

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

printf("%4d",search(*(arr + i),Hash));

 

printf("\n\n삭제 난수 %d개\n",Max_num1);

for(i = 0 ; i<Max_num1; i++){

*(arr + i) = rand() % random +1;

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

if(*(arr+j) == *(arr+i))

i--;

}

for(i = 0 ; i<Max_num1; i++){

printf("%4d",*(arr+i));

deleteHash(*(arr + i),Hash);

}

 

 

printf("\n\n삭제 결과후의 해시 테이블\n");

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

printf("%4d",*(Hash+i));

 

 

printf("\n\n삽입 난수 %d개\n",Max_num1);

for(i = 0 ; i<Max_num1; i++){

*(arr + i) = rand() % random +1;

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

if(*(arr+j) == *(arr+i))

i--;

}

for(i = 0 ; i<Max_num1; i++){

printf("%4d",*(arr+i));

insertHash(*(arr + i),Hash);

}

printf("\n\n삽입 결과후의 해시 테이블(-1은 삭제된 데이터)\n");

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

printf("%4d",*(Hash+i));

 

printf("\n\n탐색 난수 %d개\n",Max_num1);

for(i = 0 ; i<Max_num1; i++){

*(arr + i) = rand() % random +1;

 

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

if(*(arr+j) == *(arr+i))

i--;

}

for(i = 0 ; i<Max_num1; i++){

printf("%4d",*(arr+i));

}

printf("\n\n탐색 결과\n");

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

printf("%4d",search(*(arr + i),Hash));

 

printf("\n");

return;

}