자료구조(21) - 맵(딕셔너리)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#include<string.h>



/*
자료 : { "banana : 바나나", "apple : 사과", "pineapple : 파인애플", "orange : 오랜지"}
기능1 추가 : 맵에 키, 값 쌍을 추가한다
기능2 삭제 : 맵에 키, 값 쌍을 제거한다
기능3 조회 : 맵에서 키를 통해 저장된 값을 확인한다.
*/

typedef struct Node* treePointer;

typedef struct Node {
	int key;				// 키를 통한 해쉬 값
	char data[10];				// 원래 값(value)
	treePointer left_child;       // 첫째 자식 노드를 가리키는 포인터
	treePointer right_child;       // 둘째 자식 노드를 가리키는 포인터
} node;                     // 노드


// + 노드를 만드는 함수
treePointer make_node(const int key, char* data) {
	treePointer new_node = (treePointer)malloc(sizeof(node));
	new_node->key = key;
	strcpy(new_node->data, data);
	new_node->left_child = NULL;
	new_node->right_child = NULL;

	return new_node;
}


//기능1 삽입 : 원소를 BST에 삽입한다.
treePointer insert(treePointer root, char* key, char* data) {
	//void나 int 대신 treePointer를 쓰면 코드를 간결하게 작성할 수 있다.

	int hash_value = hash(key);

	if (root == NULL) return make_node(hash_value, data);
	// 삽입될 위치를 찾을 때까지 따라가다가, leaf에서 삽입

	if (hash_value < root->key)
		root->left_child = insert(root->left_child, key, data);
	else if (hash_value > root->key)
		root->right_child = insert(root->right_child, key, data);

	return root;
}


treePointer findMin(treePointer root) {
	while (root->left_child != NULL)
		root = root->left_child;
	return root;
}// Delete를 위한 함수, 서브트리의 최소값을 찾음

/*
기능2 삭제 : 원소를 BST에서 삭제한다.
1. 자식 노드가 없는 경우: 해당 노드를 삭제

2. 자식 노드가 하나인 경우: 해당 노드를 삭제하고,
자식 노드를 삭제된 노드의 부모 노드에 연결한다.

3. 자식 노드가 둘인 경우: 삭제할 노드를 삭제하고,
그 자리에 삭제된 노드보다 큰 값 중 가장 작은 노드, 또는
삭제된 노드보다 작은 값 중 가장 큰 노드를 가져와야한다.
*/

treePointer Delete(treePointer root, char* key) {
	//void나 int 대신 treePointer를 쓰면 코드를 간결하게 작성할 수 있다.

	int hash_value = hash(key);

	if (root == NULL) return root;

	// 삭제할 노드 찾기
	if (hash_value < root->key)
		root->left_child = Delete(root->left_child, key);
	else if (hash_value > root->key)
		root->right_child = Delete(root->right_child, key);
	else {
		// 삭제할 노드를 찾았을 때
		if (root->left_child == NULL) {
			// 삭제할 노드가 자식이 0개 혹은 1개인 경우

			treePointer temp = root->right_child;
			// Null과 반대 방향 자식을 가리키기를 동시 처리.

			free(root);
			return temp;
		}
		else if (root->right_child == NULL) {
			// 삭제할 노드가 1개의 자식을 가지는 경우

			treePointer temp = root->left_child;
			free(root);
			return temp;
		}

		// 삭제할 노드가 두 개의 자식을 가지는 경우
		treePointer temp = findMin(root->right_child);
		root->key = temp->key;
		root->right_child = Delete(root->right_child, temp->key);
	}
	return root;
}

// BST의 성질을 이용한 조회의 핵심 기능
char* rec_search(treePointer root, char* key) {
	if (root == NULL) {
		return ""; // 찾지 못한 경우 0 반환
	}

	int hash_value = hash(key);

	if (hash_value < root->key) {
		return rec_search(root->left_child, key);
		// key가 루트의 값보다 작으면 왼쪽

	}
	else if (hash_value > root->key) {
		return rec_search(root->right_child, key);
		// 아니면 오른쪽 이동

	}
	else {
		return root->data;
		// 찾은 경우 1 반환
	}
}

// 기능3 조회 : 원소를 BST에서 조회한다.
void search(treePointer root, char* key) {
	char data[10];
	strcpy(data, rec_search(root, key));

	if (strcmp(data, "")) {
		printf("There is %s, %s in BST\n\n", key, data);
	}
	else {
		printf("There is no %s in BST\n\n", key);
	}
}

int hash(char* str) {
	int length = strlen(str);

	int ret = 0;

	for (int i = 0; i < length; i++) {
		ret += str[i];
	}

	return ret;
}



int main(void) {
	treePointer root = make_node(hash("banana"), "바나나");

	insert(root, "apple", "사과");
	insert(root, "pineapple", "파인애플");
	insert(root, "orange", "오랜지");

	search(root, "banana");
	search(root, "apple");
	search(root, "pineapple");
	search(root, "orange");

	Delete(root, "apple");
	search(root, "apple");
}

#include <stdio.h>
#include <string.h>

#define NODE 6

/*
자료 : { "banana : 바나나", "apple : 사과", "pineapple : 파인애플", "orange : 오랜지"}
기능1 추가 : 맵에 키, 값 쌍을 추가한다
기능2 삭제 : 맵에 키, 값 쌍을 제거한다
기능3 조회 : 맵에서 키를 통해 저장된 값을 확인한다.
*/

// 해시 함수
int hash(char* str) {
	int length = strlen(str);

	int ret = 0;

	for (int i = 0; i < length; i++) {
		ret += str[i];
	}

	return ret % 5;
}


//기능1 추가 : 집합에 원소를 추가한다
void insert(char* set[], char* key, char* data) {
	int hashValue = hash(key);
	set[hashValue] = data;
	printf("%s is added to the set with %s by hash function\n\n", data, key);
}


//기능2 삭제 : 집합에서 원소를 삭제한다
void Delete(char* set[], char* key) {
	int hashValue = hash(key);
	if (!strcmp(set[hashValue], "x")) {
		printf("%s is not in the set\n\n", key);
		return;
	}
	set[hashValue] = "x";
	printf("%s is deleted from the set\n\n", key);
}

//기능3 조회 : 집합에 원소가 속한지 확인한다
void search(char* set[], char* key) {
	int hashValue = hash(key);
	if (!strcmp(set[hashValue],"x")) {
		printf("%s is not in the set\n\n", key);
	}
	else {
		printf("%s, %s is in the set\n\n", key, set[hashValue]);
	}
}

int main(void) {
	char* set[NODE] = { "x", "x", "x", "x", "x", "x"};
	// 매칭되는 원소가 없다면 -1로 해놓음

	insert(set, "banana", "바나나");
	insert(set, "apple", "사과");
	insert(set, "pineapple", "파인애플");
	insert(set, "orange", "오랜지");

	search(set, "banana");
	search(set, "apple");
	search(set, "pineapple");
	search(set, "orange");

	Delete(set, "apple");
	search(set, "apple");
}