II 14 2018 7 26 : : proen@mm.ics.saitama-u.ac.jp 14,, 8 2 12:00 1 O(1) n O(n) O(log n) O(1) 32 : 1G int 4 250 M 2.5 int 21 2 0 100 0 100 #include <stdio.h> #define HASHSIZE 100 /* */ #define NOTFOUND 0 /* */ #define FOUND (!NOTFOUND) /* */ #define EMPTY -1 /* */ 1
void hash1_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; /* i EMPTY */ void hash1_insert(int *array, int n) if (n < 0 n >= HASHSIZE) printf(" \n"); array[n] = n; int hash1_find(int *array, int n) if (n < 0 n >= HASHSIZE) if (array[n] == n) return FOUND; hash1_insert() hash1_find() hash1_init() hash1_find() HASHSIZE 2.1 1 : hash1_insert() hash1_find() 2
#include <stdio.h> int main(void) int hashtable[hashsize]; int data[] = 9, 77, 35, 43, 96 ; int n, i; hash1_init(hashtable); n = sizeof(data) / sizeof(data[0]); for (i = 0; i < n; i++) hash1_insert(hashtable, data[i]); printf("input> "); scanf("%d", &n); if (hash1_find(hashtable, n)!= NOTFOUND) printf(" found\n"); else printf(" not found\n"); return 0; 3 (2) 0 100 100 15 215 0 int void hash2_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; void hash2_insert(int *array, int n) 3
if (n < 0) printf(" \n"); array[n % HASHSIZE] = n; /* HASHSIZE n */ int hash2_find(int *array, int n) if (n < 0) if (array[n % HASHSIZE] == n) return FOUND; f(n) n % HASHSIZE 3.1 2 : 4 2 void hash3_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; void hash3_insert(int *array, int n) int i, hashval; 4
if (n < 0) printf(" \n"); hashval = n % HASHSIZE; for (i = hashval; i < HASHSIZE; i++) if (array[i] == EMPTY) array[i] = n; for (i = 0; i < hashval; i++) if (array[i] == EMPTY) array[i] = n; printf(" \n"); int hash3_find(int *array, int n) int i, hashval; if (n < 0) hashval = n % HASHSIZE; for (i = hashval; i < HASHSIZE; i++) if (array[i] == n) return FOUND; if (array[i] == EMPTY) for (i = 0; i < hashval; i++) if (array[i] == n) return FOUND; if (array[i] == EMPTY) 5
4.1 3 2 2 : hash3_insert() hash3_find() 2 for hash2_insert() hash2_find() 5 2 #define VECTORSIZE 5 struct vector int size; int value[vectorsize]; ; void hash4_init(struct vector *array) int i; for (i = 0; i < HASHSIZE; i++) array[i].size = 0; void hash4_insert(struct vector *array, int n) int hashval, size; if (n < 0) printf(" \n"); hashval = n % HASHSIZE; size = array[hashval].size; if (size < VECTORSIZE) array[hashval].value[size] = n; array[hashval].size++; 6
printf(" \n"); int hash4_find(struct vector *array, int n) int i, hashval, size; if (n < 0) hashval = n % HASHSIZE; size = array[hashval].size; for (i = 0; i < size; i++) if (array[hashval].value[i] == n) return FOUND; 6 6.1 C char char 1 1 ASCII (American Standard Code for Information Interchange) 0x00 0x1F 0x7F 7 A 16 41 10 4 16 + 1 = 65 7
#include <stdio.h> int main(void) char str[8]; str[0] = 5*16+3; str[1] = 6*16+1; str[2] = 6*16+9; str[3] = 7*16+4; str[4] = 6*16+1; str[5] = 6*16+13; str[6] = 6*16+1; str[7] = \0 ; printf("%s\n", str); return 0; Saitama 6.2 C = == string.h (string copy) char *strcpy(char *s, char *t) (string compare) int strcmp(char *s, char *t) strcpy(s, t) t s strcmp(s, t) s t 0 0 6.3 : The x, y ax + by a b 1 1 2 t 3 t 2 4 t 3 t = 5 coeff t i HASHSIZE 8
int hashfunc(char *s) int hashval = 0, coeff = 1, i; for (i = 0; s[i]!= \0 ; i++) hashval += s[i] * coeff; coeff = (coeff * 5) % HASHSIZE; /* */ return hashval % HASHSIZE; 6.4 4 hash_find() : #define MAXLENGTH 128 struct string char str[maxlength]; ; int main(void) struct string hashtable[hashsize]; char *data[] = "Japan", "United Kingdom", "Sweden", "United States", "Brazil", "Egypt" ; char buffer[maxlength], *p; int n, i; hash_init(hashtable); n = sizeof(data) / sizeof(data[0]); for (i = 0; i < n; i++) hash_insert(hashtable, data[i]); /* buffer */ printf("input> "); fgets(buffer, sizeof(buffer), stdin); if ((p = strrchr(buffer, \n ))!= NULL) 9
*p = \0 ; /* */ /* */ if (hash_find(hashtable, buffer)!= NOTFOUND) printf(" found\n"); else printf(" not found\n"); return 0; /* */ #define EMPTY_STRING "" void hash_init(struct string *array) int i; for (i = 0; i < HASHSIZE; i++) strcpy(array[i].str, EMPTY_STRING); void hash_insert(struct string *array, char *str) int i, hashval; if (strcmp(str, EMPTY_STRING) == 0) printf(" \n"); hashval = hashfunc(str); for (i = hashval; i < HASHSIZE; i++) if (strcmp(array[i].str, EMPTY_STRING) == 0) strcpy(array[i].str, str); for (i = 0; i < hashval; i++) if (strcmp(array[i].str, EMPTY_STRING) == 0) strcpy(array[i].str, str); 10
printf(" \n"); int hash_find(struct string *array, char *str) /* hash_insert() */ 11
1: (16 ) 0 1 2 3 4 5 6 7 8 9 A B C D E F 20! " # $ % & ( ) * +, -. / 30 0 1 2 3 4 5 6 7 8 9 : ; < = >? 40 @ A B C D E F G H I J K L M N O 50 P Q R S T U V W X Y Z [ \ ] ^ _ 60 a b c d e f g h i j k l m n o 70 p q r s t u v w x y z ~ 12