[알고리즘] 해시테이블(2) - 예제

[문제1] 해시테이블을 분리연쇄법을 이용해 충돌을 처리하는 해시테이블 프로그램

- 해시테이블은 크기가 M인 배열로 동적 할당한다

- 입력 키는 중복이 없는 자연수다

- 키x에 대한 해시함수 h(x) = x % M을 사용한다

- 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다

삽입(i) : 키 x를 받아 해시테이블에 삽입

탐색(s) : 키 x가 해시테이블에 존재하는지 탐색(해당 키가 있다면 키가 저장된 순위를 출력, 없다면 0출력)

삭제(d) : 키 x가 해시테이블에 존자하면 삭제(해당 키가 있다면 키가 저장된 순위를 출력, 없다면 0출력)

출력(p) : 해시테이블에 저장된 키들을 순서대로 인쇄

종료(e) : 프로그램 종료

입력예시     출력예시

13 i 34 i 23 i 26 i 21 s 36 s 26 s 34 s 21 p d 21 s 34 d 8 e

0 1 2 1  26 21 34 23 1 1 0

#include<stdio.h> #include<stdlib.h> struct node { int number; struct node *next; }; struct node *hashTable; int M; int h(int x) { return x; } void insertItem(int x) { int v = h(x); struct node *p = hashTable + v; struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->number = x; newnode->next = NULL; if (p->next == NULL) { p->next = newnode; } else { newnode->next = p->next; p->next = newnode; } } int searchItem(int x) { int v = h(x), count = 0; struct node *p = hashTable + v; if (p->next == NULL) { return 0; } else { while (1) { p = p->next; count++; if (p->number == x) { return count; } if (p->next == NULL) { return 0; } } } } int deleteItem(int x) { int v = h(x), count = 0; struct node *pt = hashTable + v, *p = hashTable + v; if (p->next == NULL) { return 0; } else { while (1) { p = p->next; count++; if (p->number == x) { while (pt->next != p) { pt = pt->next; } pt->next = p->next; free(p); return count; } if (p->next == NULL) { return 0; } } } } void printTable() { struct node *p; for (int i = 0; i < M; i++) { p = hashTable + i; if (p->next != NULL) { p = p->next; printf(" %d", p->number); while (p->next != NULL) { p = p->next; printf(" %d", p->number); } } } printf("\n"); } void freeTable() { struct node *p, *q; for (int i = 0; i < M; i++) { if ((hashTable + i)->next != NULL) { p = (hashTable + i)->next; q = p; while (q->next != NULL){ p = p->next; free(q); q = p; } } } free(hashTable); } void main() { int key; char select; scanf("%d", &M); hashTable = (struct node*)malloc(sizeof(struct node)*M); for (int i = 0; i < M; i++) { (hashTable + i)->number = NULL; (hashTable + i)->next = NULL; } while (1) { scanf("%c", &select); if (select == 'i') { scanf("%d", &key); insertItem(key); getchar(); } else if (select == 's') { scanf("%d", &key); printf("%d\n", searchItem(key)); getchar(); } else if (select == 'd') { scanf("%d", &key); printf("%d\n", deleteItem(key)); getchar(); } else if (select == 'p') { printTable(); getchar(); } else if (select == 'e') { break; } } freeTable(); }

[문제2] 해시테이블을 선형조사법을 이용해 충돌을 처리하는 해시테이블 프로그램

- 해시테이블은 크기가 M인 배열로 동적 할당한다

- n은 M보다 작은 자연수로 최대 삽입 개수이다

- 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수이다

- 키 x에 대한 해시함수 h(x) = x % M을 사용한다

- 저장된 키 값이 없는 빈 버켓은 0으로 처리한다

삽입(i) : 키 x를 해시테이블에 삽입(삽입시 배열 인덱스를 출력, 충돌이 일어나면 충돌횟수만큼C를 인쇄한 후, 삽입에 성공한 주소를 출력)

탐색(s) : 키 x를 해시테이블에 존재하는지 탐색(키가 저장된 주소와 값을 출력, 없으면 -1 출력)

종료(e) : 프로그램 종료

입력예시    출력예시

7 3 i 17011112 i 17012345 i 17012687 s 17011111 e	6 0 CC1 -1
13 10 i 16110243 i 17011111 i 17012331 i 17012354 i 17013672 i 16012342 s 17012354 i 15013986 i 102067 i 113478 i 14012322 s 16110243 e	6 0 11 8 C1 C9 8 17012354 CC2 4 CC3 12 6 16110243

#include<stdio.h> #include<stdlib.h> int *hashTable, M; int h(int x, int M) { return x % M; } int getNextBucket(int v, int i) { return (v + i) % M; } void insertItem(int x) { int v = h(x, M), i = 0, b; while (i < M) { b = getNextBucket(v, i); if (hashTable[b] == 0) { hashTable[b] = x; for (int j = 0; j < i; j++) { printf("C"); } printf("%d\n", b); return; }                                                                                                                                                                                                                                                                                                                                                                                                     else { i = i + 1; } } } void searchItem(int x) { int v = h(x, M), i = 0, b; while (i < M) { b = getNextBucket(v, i); if (hashTable[b] == 0) { printf("-1\n"); return; } else if (hashTable[b] == x) { printf("%d %d\n", b, hashTable[b]); return; } else { i = i + 1; } } printf("-1\n"); } void main() { int n, key; char select; scanf("%d", &M); hashTable = (int*)malloc(sizeof(int)*M); for (int i = 0; i < M; i++) { *(hashTable + i) = 0; } scanf("%d", &n); while (1) { scanf("%c", &select); if (select == 'i') { scanf("%d", &key); insertItem(key); getchar(); } else if (select == 's') { scanf("%d", &key); searchItem(key); } else if (select == 'e') { break; } } free(hashTable); }

[문제3] 해시테이블을 이중해싱을 이용해 충돌을 처리하는 해시테이블 프로그램

- 해시테이블은 크기가 M인 배열로 동적 할당한다

- n은 M보다 작은 자연수로 최대 삽입 개수이다

- 입력 키는 중복이 없는 2자리 이상의 자연수이다

- 키 x에 대한 첫 번째 해시함수 h(x) = x % M, 두 번째 해시함수 h'(x) = q - (x % q)를 사용한다

- 저장된 키가 없는 빈 버켓은 0으로 처리한다

입력(i) : 키 x를 입력받아 해시테이블에 삽입(삽입시 저장된 주소(배열인덱스)를 출력, 충돌이 일어날경우 충돌 횟수만큼C를 출력한 후, 삽입에 성공한 주소를 출력)

탐색(s) : 키 x가 해시테이블에 존재하는지 탐색(키가 존재할 경우 키가 저장된 주소와 값을 출력, 없을 경우 -1출력)

출력(p) : 현재의 해시테이블 출력

종료(e) : 해시테이블 출력 후 프로그램 종료

입력예시        출력예시

13 10 11 i 25 i 13 i 16 i 15 i 70 p i 28 i 31 i 20 i 14 s 20 s 27 i 38 e

12 0 3 2 5  13 0 15 16 0 70 0 0 0 0 0 0 25 C7 CC9 CC11 1 11 20 -1 CCC4  13 14 15 16 38 70 0 28 0 31 0 20 25

#include<stdio.h> #include<stdlib.h> int M, n, q, *hashTable; int h(int x) { return x % M; } int h2(int x) { return q - (x % q); } int getNextBucket(int v, int i, int k) { return(v + i * h2(k) % M) % M; } void insertItem(int k) { int v = h(k); int i = 0, b; while (i < M) { b = getNextBucket(v, i, k); if (hashTable[b] == 0) { hashTable[b] = k; for (int j = 0; j < i; j++) { printf("C"); } printf("%d\n", b); return; } else { i = i + 1; } } } void searchItem(int k) { int v = h(k); int i = 0, b; while (i < M) { b = getNextBucket(v, i, k); if (hashTable[b] == 0) { printf("-1\n"); return; } else if (hashTable[b] == k) { printf("%d %d\n", b, hashTable[b]); return; } else { i = i + 1; } } printf("-1\n"); } void printTable() { for (int i = 0; i < M; i++) { printf(" %d", hashTable[i]); } printf("\n"); } void main() { int key; char select; scanf("%d", &M); hashTable = (int*)malloc(sizeof(int)*M); for (int i = 0; i < M; i++) { *(hashTable + i) = 0; } scanf("%d", &n); scanf("%d", &q); while (1) { scanf("%c", &select); if (select == 'i') { scanf("%d", &key); insertItem(key); getchar(); } else if (select == 's') { scanf("%d", &key); searchItem(key); getchar(); } else if (select == 'p') { printTable(); getchar(); } else if (select == 'e') { printTable(); break; } } free(hashTable); }