그 외 공부/Algorithm
# 15_Hash
ssangeun
2017. 11. 22. 09:55
# The source code
|
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98 |
//hash, chaining(SLL):collsion(중복)을 해결하는 방법, linear probing:collsion(중복)을 해결하는 방법, bucket(index)
//loading density : 100개의 용량중에 5개만 차있으면 5%, collsion이 발생할 확률과 비례 혹은 공간 낭비의 확률
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
struct student
{
char name[20];
int stno;
unsigned short age;
struct student * next;
};
typedef struct student STUDENT;
#define hashTable_sz 30
STUDENT *hashTable[hashTable_sz];
int hashFunction(char * str)
{
// 문자값을 모두 더한다
// % hashTable_sz
int sum = 0;
int len = strlen(str);
int i;
for (i = 0; i < len; i++)
{
sum += str[i];
}
return (sum%hashTable_sz);
}
void addToHashTable(char *name, int stno, unsigned short age)
{
STUDENT *cur = (STUDENT*)malloc(sizeof(STUDENT));
int idx;
strcpy_s(cur->name, strlen(name) + 1, name);
cur->stno = stno;
cur->age = age;
cur->next = 0;
idx = hashFunction(name);
if (hashTable[idx] == 0)
{
hashTable[idx] = cur;
return;
}
else
{
STUDENT *tmp = hashTable[idx];
while (tmp->next != 0)
{
tmp = tmp->next;
}
tmp->next = cur;
return;
}
}
void searchIntheHash(char * name)
{
// 찾기
int idx;
STUDENT * cur;
idx = hashFunction(name);
cur = hashTable[idx];
if (cur == 0)
{
printf("null");
return;
}
while (strcmp(cur->name, name) != 0)
{
cur = cur->next;
if (cur == 0)
{
return;
}
}
printf("%s %d %d \n", cur->name, cur->stno, cur->age);
}
void main()
{
addToHashTable("박철수", 200, 19);
addToHashTable("김철수", 201, 18);
addToHashTable("이철수", 202, 17);
addToHashTable("오철수", 203, 16);
addToHashTable("송철수", 204, 15);
searchIntheHash("이철수");
} |
cs |
# The result
