-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathChaining.h
More file actions
59 lines (41 loc) · 1.31 KB
/
Chaining.h
File metadata and controls
59 lines (41 loc) · 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#ifndef CHAINING_H
#define CHAINING_H
#pragma warning(disable : 4996) // strcpy()
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // memset()
// 해시테이블 (체이닝)
/*
체이닝: 해시테이블 외부에 데이터를 저장하는 개방 해싱 알고리즘.
충돌을 고려하여 해시테이블이 링크드 리스트의 포인터를 관리한다.
충돌이 발생하면 새 노드를 링크드리스트의 head에 붙인다.
(tail 에 이어붙이려면, tail 찾다가 시간 소모하기 때문)
*/
typedef char* KeyType;
typedef char* ValueType;
// linked list node
typedef struct tagNode {
KeyType key;
ValueType value;
struct tagNode* next; // 다음 노드
}Node;
// linked list (해시값이 같은 주소가 나오는 충돌이 발생해도 리스트에 이어붙인다.)
typedef Node* List;
// 해시테이블
typedef struct tagHashTable {
int tableSize;
List* table;
}HashTable;
// Hash Table 생성/해제
HashTable* CHT_CreateHashTable(int tableSize);
void CHT_DestroyHashTable(HashTable* HT);
// Node 생성/해제
Node* CHT_CreateNode(KeyType key, ValueType value);
void CHT_DestoryNode(Node* target);
void CHT_DestoryList(List list);
// [중요] 삽입, 탐색, 해시
void CHT_Set(HashTable* HT, KeyType key, ValueType value);
ValueType CHT_Get(HashTable* HT, KeyType key);
int CHT_Hash(KeyType key, int keyLength, int tableSize);
/* 링크드 리스트에서 순차탐색이 아닌 이진탐색트리 활용해보기 */
#endif // !CHAINING_H