Week9_해시테이블_실습(1)

[ 다람쥐의 창고 정리를 도와주세요!! ]

귀여운 다람쥐 친구가 겨울맞이 식량 창고를 정리하고 있어요. 창고 A에 서랍은 13개가 있고, 무작위로 넣지 않고 해시 함수 값에 따라 먹이를 저장할거래요. (먹이들은 원래 며칠에 획득했는지 날짜로 라벨링되어 있었대요. 예를 들어 13일에 주운 사과, 28일에 선물받은 도토리 등...) 다람쥐는 먹이들에 00, 01, 02, ,....,..,12 이런 식으로 번호 라벨을 붙여놓고, 해시 함수 값에 따라 각각 0번째 서랍, 1번째 서랍, 2번째 서랍,..., 12번째 서랍에 각각 넣기로 했어요!

 

그런데 문제가 있어요. 어느 날 15일에 얻은 먹이(해시 함수 값=2)를 2번째 서랍에 넣으려고 하니까, 이미 서랍에 다른 먹이가 있는거예요.. 어떻게 하면 좋을까요?  

 

먹이의 획득 날짜(=key), 서랍의 개수(=M)

 

---

1. 분리연쇄법 해시테이블로 정리하기 

귀여운 다람쥐 친구가 겨울맞이 식량 창고를 정리하고 있어요. 창고 A에 서랍은 13개가 있고, 무작위로 넣지 않고 해시 함수 값에 따라 먹이를 저장할거래요.  

<조건>

-해시테이블: 크기가 M인 '배열'로 동적 할당

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

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

-삽입 시 충돌 => 버켓 리스트의 맨 앞에 삽입

 

[HOW? by pseudo code]

Alg findElement(k)

    input bucket array A[0..M-1], hash function h, key k

    output element with key k

1. v<--h(k)

2. return A[v].findElement(k)

 

Alg insertItem(k, e)

1. v<--h(k)

2. A[v].insertItem(k, e)

3. return

 

Alg removeElement(k)

1. v<--h(k)

2. return A[v].removeElement(k)

 

Alg initBucketArray()

   input bucket array A[0,...,M-1]

   output bucket array A[0,...M-1] with initialized with null buckets

1. for i<- to M-1 

     A[i]<-empty list

2. return

 

 

STEP1) 구조체 정의

int M; //배열 크기

typedef struct node{
    int key;
    struct node* next;
}Node;    

Node* hashTable;

 

노드

                                     위의 노드가 M개 있는 구조체 배열이 바로 해시테이블 A입니다!!

해시테이블 배열

STEP2) 초기화 함수

void init(){
   for(int i=0;i<M;i++){
        (hashTable+i)->next = NULL;
   }
}

 

STEP3) 해시 함수 정의

int h(int k){
    return k % M;
}

 

STEP4) 삽입

*최초의 삽입이 일어난 경우

*그 다음 노드에 연결하는 경우

삽입 모식도

void insertItem(int x) {
	int v = h(x);
	Node* p = hashTable + v;
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->key = x, newnode->next = NULL;

	if (p->next == NULL) p->next = newnode;
	else {
		newnode->next = p->next;
		p->next = newnode;

	}
}

STEP5) 탐색

*탐색했는데 아무 노드도 없는 경우

*탐색했는데 노드가 이미 있는 경우 => 몇 번째에 위치하는지 위치 반환 (변수 cnt 필요)

int searchItem(int x) {
	int v = h(x);
	int cnt = 0; //몇 번째에 위치하는지
	Node* p = hashTable + v;
	if (p->next == NULL)return 0;
	else {
		while (1) {
			p = p->next;
			cnt++;
			if (p->key == x) return cnt; 
			if (p->next == NULL)return 0; //리스트 끝이면 종료

		}
	}
}

STEP6) 삭제

*삭제할 노드가 없는 경우

*삭제할 노드가 있는 경우 => 키 값 확인 후 => tmp 이용해서 삭제 작업

삭제 모식도

int deleteItem(int x) {
	int v = h(x);
	int cnt = 0;
	Node* p = hashTable + v;
	Node* tmp = hashTable + v;

	if (p->next == NULL)return 0;
	else {
		while (1) {
			p = p->next;
			cnt++;
			if (p->key == x) {
				while (tmp->next != p) {
					tmp = tmp->next; //p 이전까지 포인터 이동
				}
				tmp->next = p->next;
				free(p);
				return cnt;
			}
			if (p->next == NULL)return 0; //리스트 끝이면 종료

		}
		
	}
}

STEP7) 출력

void printTable() {
	for (int i = 0; i < M; i++) {
		Node* p = hashTable + i;
		if (p->next != NULL) {
			p = p->next;
			printf(" %d", p->key); 
			while (p->next!=NULL) { //노드가 또있으면
				p = p->next;
				printf(" %d", p->key);
			}
		}
	}
	printf("\n");
}

STEP8) 메인함수

int main() {

	int key;
	char ch;

	scanf("%d", &M); //배열크기 입력
	hashTable = (Node*)malloc(sizeof(Node) * M); //해시테이블 동적할당
	init();

	while (1) {

		scanf("%c", &ch); //명령어 입력

		if (ch == 'i') {
			scanf("%d", &key);
			insertItem(key);
			getchar();
		}
		else if (ch == 's') {
			scanf("%d", &key);
			printf("%d\n", searchItem(key));
			getchar();
		}
		else if (ch == 'd') {
			scanf("%d", &key);
			printf("%d\n", deleteItem(key));
			getchar();

		}
		else if (ch == 'p') {
			printTable();
			getchar();

		}
		else if (ch == 'e') {
			break;
		}

	}

	return 0;
}