April 09, 2019TWpower Reading time ~1 minute

[Linux](EN) Use or pass sudo password in shell script

Process file or result of command in while loop line by line in shell script.

Environment and Prerequisite

Linux base system
Bash shell(/bin/bash)

Solution

Use -S option and |

echo "PASSWORD" | sudo -S apt-get update

Usage with file

cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo -S apt-get update

Use --stdin option and |

echo "PASSWORD" | sudo --stdin apt-get update

Usage with file

cat << EOF > password.txt
> PASSWORD
> EOF

cat password.txt | sudo --stdin apt-get update

Reference

April 09, 2019TWpower Reading time ~5 minutes

[Algorithm](EN) Singly Linked List Implementation in C/C++

Implement basic form of singly linked list

Environment and Prerequisite

What is Singly Linked List?

Concept

It is a data structure which have datas in one node and point to other node sequentially.
It is an advantage compared with array in insertion and deletion. However accessing takes O(n).
It is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

Implementation

Common

list is a head of list
You can modify insertion, deletion and finding codes if you want.

#include <stdio.h>
#include <stdlib.h>

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;

Insertion/Delettion Common

It is easy to implement if we consider the head(or first element) of list
It is helpful if there are cur pointer which points current node and prev pointer which points previous node of current node. They are helpful in insertion and deletion.
In deletion, if there is a node that we want to delete, then it returns true. If not, then return false.

Insertion

Like below picture, find the position of new node. Then, point new node’s next to next node and previous node’s next to new node.
There are 3 types of functions.
add : add just new node
ascending_order_add : add node in middle(by ascending order)
add_unique : add only unique node

// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}

Deletion

Like below picture, find the position of node which will be deleted. Then, points previous node’s next to current node’s(which will be deleted) next.
Use curand prev pointers.

// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

Code

#include <stdio.h>
#include <stdlib.h>

// Node
struct Node {
	int data;
	Node * next;
};

// Global list
Node * list;

// Init
void init() {

	if (list == NULL) {
		return;
	}
	else {
		Node * cur;
		cur = list;

		while (cur != NULL) {
			list = cur->next;
			free(cur);
			cur = list;
		}
	}
}

// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}

// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

// Traverse
void traverse() {

	Node * cur = list;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");

}

int main() {

	int arr[9] = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
	int arr_duplicated[18] = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
	int arr_rmv[4] = { 2, 9, 8, 100 };


	// Add to list 1
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		add(arr[i]);
	}
	printf("After add(normal) : ");
	traverse();


	// Add to list 2
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		ascending_order_add(arr[i]);
	}
	printf("After add(ascending) : ");
	traverse();


	// Add to list 3
	init();
	for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
		add_unique(arr_duplicated[i]);
	}
	printf("After add(unique) : ");
	traverse();


	// Remove specific values in list
	for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
		remove(arr_rmv[i]);
	}
	printf("After remove : ");
	traverse();

	return 0;

}

Result

After add(normal) : 9 7 5 3 1 8 6 4 2
After add(ascending) : 1 2 3 4 5 6 7 8 9
After add(unique) : 9 7 5 6 4 2 3 1 8
After remove : 7 5 6 4 3 1

Reference

April 06, 2019TWpower Reading time ~7 minutes

[Algorithm] C/C++에서 삽입정렬을 이용해 상위 n개 구하기

업데이트(2019.07.25) : 삽입정렬 코드 추가

C++에서 삽입정렬을 이용해 상위 n개를 구하는 코드를 작성해보자

환경

삽입정렬이란?

개념

삽입정렬 : 앞에서부터 모든 원소를 탐색하면서 정렬된 앞 부분에 위치를 찾아서 추가하는 방법으로 진행하는 정렬을 의미합니다. 아래 사진을 보시면 시작할 때 제일 앞에 원소는 정렬되어있다고 가정하고 뒤에 원소를 하나하나 탐색하면서 앞의 정렬된 부분에 추가하고 그 뒤에 부분은 밀어주는 방식입니다.
시간복잡도 : O(n^2), 공간복잡도 : O(1)(추가적인 공간 필요X)

아래 GIF는 해당 내용을 이미지로 빠르게 표현한 사진입니다.

전체 자료에서 상위 N개 구하기

방법

여러가지 방법이 있을 수 있습니다.
힙을 사용, 퀵소트를 통해 정렬하고 앞에서 N개를 선택…과 같은 여러 방법이 있지만 모든 작업을 마치고 주어진 자료에서 상위 N개를 선택할 때의 상황에서는 전체가 정렬될 필요가 없고 상위 N개만 필요하기 때문에 삽입정렬이 유리합니다.
만약 모든 작업을 마친게 아니고 매 작업마다 현재 상황에서 가장 우선 순위가 높은 자료를 가져오는 경우라면 힙을 사용하는게 유리합니다.(실제로 우선 순위 큐의 목적)

구현 목표

문자열과 정수값을 가지고 있는 무작위의 노드들에서 정수값이 가장 크고 정수값이 같을 때 문자열이 사전순인 노드 상위 N개를 선택하려한다.

구현

공통

Node는 정렬할 자료의 대상이며 각 Node는 문자열 key와 정수 value를 가지고 있습니다.
nodes : Node들을 가지고 있는 배열입니다.
ranks : nodes에 서 상위 N개의 인덱스를 차례로 저장할 배열입니다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// 데이터
Node nodes[MAX_NUM_OF_DATA];

// 상위 NUM_OF_RANKS개에 해당하는 nodes의 인덱스를 저장할 배열
int ranks[NUM_OF_RANKS];

문자열 비교

비교함수와 복사함수입니다.
일반적으로 사용하는 문자열 함수와 같습니다.

void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}

비교함수

i와 j는 각각 nodes 배열에 있는 인덱스를 의미합니다.
비교는 1. 정수값이 클수록 2. 정수값이 같다면 문자열은 사전순으로에 따라서 비교합니다.
i가 j보다 크다면 양수를 둘이 같다면 0을 그게 아니라면 음수를 반환합니다.

// nodes[i]와 nodes[j]의 value와 key를 비교합니다.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}

초기화

Node의 값들과 ranks 배열의 값들을 초기화합니다.

void init() {

	// 순위 배열 초기화
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 정수값들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}

상위 N개를 찾는 배열에 데이터 삽입

기본적으로 삽입정렬에 기반한 코드를 작성하였습니다.
삽입정렬1과 삽입정렬2가 있으며 1번은 뒤에서부터 비교하면서 위치를 찾는 코드이며 2번은 앞에서부터 비교하면서 위치를 찾는 코드입니다. 1번을 이용해 비교적 코드가 더 간결해질 수 있습니다.
nodes 배열에 있는 node_id를 함수에 전달하면 ranks안에서 삽입정렬을 시행합니다.
이 때 상위 N개 중에서 가장 마지막 값보다 값이 작으면 삽입을 진행하지 않습니다.
1번의 경우, 만약 상위 N개 안에 포함된다면 뒤에서부터 비교해가면서 위치를 찾아갑니다.
2번의 경우, 만약 상위 N개 안에 포함된다면 앞에서부터 값을 찾고 뒤에 값들은 하나씩 자리를 이동시킨 다음에 삽입합니다.

void find_ranks(int node_id) {

	// nodes[node_id]가 제일 뒤에 값보다 작으면 비교하지 않는다.
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// 삽입정렬1
	ranks[NUM_OF_RANKS - 1] = node_id;
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int tmp = ranks[rank_index];
		int j = rank_index - 1;

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	// ranks 배열을 탐색하면서
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// ranks에 현재 node_id를 추가합니다.
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}

메인함수

처음에 NUM_OF_RANKS의 수만큼 우선 정렬을 해줍니다. 처음에는 아무값도 없기때문에 미리 NUM_OF_RANKS만큼 정렬을 해줍니다.
나머지 자료들에 대해서 find_ranks() 함수를 호출하고 결과를 출력합니다.

int main() {

	init();

	// 초기 배열은 비어있는 상태로
	// NUM_OF_RANKS의 수만큼은 직접 대입해준다.

	// NUM_OF_RANKS만큼 먼저 대입
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// 삽입정렬1
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int j = rank_index - 1;
		int tmp = ranks[rank_index];

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	for (int node_id = 1; node_id < NUM_OF_RANKS; ++node_id) {
		for (int rank_index = node_id; rank_index < NUM_OF_RANKS; ++rank_index) {

			// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// ranks에 현재 node_id를 추가합니다.
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// 전체 자료들에 대해 상위 NUM_OF_RANKS개 구하기
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d : \n", i + 1);
		printf("ID : %d\n", ranks[i]);
		printf("Value : %d\n", nodes[ranks[i]].value);
		printf("Key : %s\n", nodes[ranks[i]].key);
	}
	return 0;
}

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// 데이터
Node nodes[MAX_NUM_OF_DATA];

// 상위 NUM_OF_RANKS개에 해당하는 nodes의 인덱스를 저장할 배열
int ranks[NUM_OF_RANKS];

void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}

// nodes[i]와 nodes[j]의 value와 key를 비교합니다.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}

void init() {

	// 순위 배열 초기화
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 정수값들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}

void find_ranks(int node_id) {

	// nodes[node_id]가 제일 뒤에 값보다 작으면 비교하지 않는다.
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// 삽입정렬1
	ranks[NUM_OF_RANKS - 1] = node_id;
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int tmp = ranks[rank_index];
		int j = rank_index - 1;

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	// ranks 배열을 탐색하면서
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// ranks에 현재 node_id를 추가합니다.
			ranks[rank_index] = node_id;
			break;
		}
	}*/
}

int main() {

	init();

	// 초기 배열은 비어있는 상태로
	// NUM_OF_RANKS의 수만큼은 직접 대입해준다.

	// NUM_OF_RANKS만큼 먼저 대입
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {
		ranks[node_id] = node_id;
	}

	// 삽입정렬1
	for (int rank_index = 1; rank_index < NUM_OF_RANKS; ++rank_index) {
		int j = rank_index - 1;
		int tmp = ranks[rank_index];

		while(j >= 0 && my_compare(ranks[j], tmp) < 0){
			ranks[j+1] = ranks[j];
			j--;
		}
		ranks[j+1] = tmp;
	}
	/*
	// 삽입정렬2
	for (int node_id = 1; node_id < NUM_OF_RANKS; ++node_id) {
		for (int rank_index = node_id; rank_index < NUM_OF_RANKS; ++rank_index) {

			// node_id에 해당하는 노드가 ranks[rank_index]에 해당하는 노드보다 크다면
			if (my_compare(ranks[rank_index], node_id) < 0) {
				// 해당 위치부터 뒤에 있는 값들을 ranks에서 한칸씩 밀고
				for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
					ranks[k] = ranks[k - 1];
				}
				// ranks에 현재 node_id를 추가합니다.
				ranks[rank_index] = node_id;
				break;
			}
		}
	}
	*/
	// 전체 자료들에 대해 상위 NUM_OF_RANKS개 구하기
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d : \n", i + 1);
		printf("ID : %d\n", ranks[i]);
		printf("Value : %d\n", nodes[ranks[i]].value);
		printf("Key : %s\n", nodes[ranks[i]].key);
	}
	return 0;
}

참고자료

April 06, 2019TWpower Reading time ~7 minutes

[Algorithm](EN) Find top n elements using insertion sort in C/C++

Use insertion sort to find top n elements in array.

Environment and Prerequisite

Insertion Sort?

Concept

Insertion Sort : Traverse all elements from front to end and insert each element to front sorted array part. As you can see below picture, consider the front array value is sorted. Then traverse all rest elements and insert each element to front sorted array part.
Time Complexity : O(n^2), Space Complexity : O(1)(doesn’t need extra spaces)

Below GIF shows insertion sort.

Find top N elements in datas.

Solution

There are many solutions.
We can use heap, selection after quick sorting… etc there many solutions. However when it is a case that select top n elements after all processings are done it doesn’t need to sort all elements. We only need top n elements so insertion sort could the best solution.
If it is not a case that all processings are done, heap could be the solution. That is why we call heap as priority queue.

Implmentation Goal

We will find top n elements in nodes which have string key and integer value.
Sorting rule will be 1. Integer value 2. Lexicographical order(if integer value are same)

Implementation

Common

Node is a datas that need to be sorted. Node have string key and integer value.
nodes : array with Node data type.
ranks : array which has top n elements of nodes.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// data
Node nodes[MAX_NUM_OF_DATA];

// array for saving top NUM_OF_RANKS of nodes index
int ranks[NUM_OF_RANKS];

String Comparison

Common string compare and copy function.

void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}

Compare Function

i and j each represents index of nodes array.
Compare rule : 1. Integer value 2. Lexicographical order(if integer value are same)
if i is bigger than j then it returns 1, it they are same then returns 0 if not then return -1

// compare nodes[i] and nodes[j] value ans key.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}

Init

Init nodes array and ranks array values.

void init() {

	// ranks array init
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// for random value
	srand(time(NULL));

	// init integer values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// init string key values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}

Insert node data to ranks array

Doing insertion sort in ranks array when node_id in nodes array passes to function.
Return if node_id of node is smaller than last element of ranks array.
If it is included in top n elements(bigger than last element of ranks array), then find its position in ranks array and insert it. Push other elements in ranks array if needed.

void find_ranks(int node_id) {

	// return if nodes[node_id]'s value is smaller than last element of ranks array
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// traverse ranks array
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// if nodes value of index node_id is bigger than current ranks[rank_index]
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// move each values from that point
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// insert node_id to ranks array
			ranks[rank_index] = node_id;
			break;
		}
	}
}

Main Function

First, sort NUM_OF_RANKS elements. At first, there are trash values in ranks array so it needs to be sorted NUM_OF_RANKS elements.
Call find_ranks(node_id) function and print results.

int main() {

	init();

	// insert NUM_OF_RANKS size of data to ranks array
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {

		for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {
			// if ranks array is empty then insert node_id
			if (ranks[rank_index] == -1) {
				ranks[rank_index] = node_id;
				break;
			}
			else {
				// if nodes value of index node_id is bigger than current ranks[rank_index]
				if (my_compare(ranks[rank_index], node_id) < 0) {
					// move each values from that point
					for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
						ranks[k] = ranks[k - 1];
					}
					// insert node_id to ranks array
					ranks[rank_index] = node_id;
					break;
				}
			}
		}
	}

	// Find top NUM_OF_RANKS elements in nodes
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d : \n", i + 1);
		printf("ID : %d\n", ranks[i]);
		printf("Value : %d\n", nodes[ranks[i]].value);
		printf("Key : %s\n", nodes[ranks[i]].key);
	}
	return 0;
}

Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_KEY_LEN 13
#define MIN_KEY_LEN 5
#define MAX_NUM_OF_DATA 5000
#define MAX_VALUE_SIZE 5000
#define NUM_OF_RANKS 5

using namespace std;

struct Node {
	char key[MAX_KEY_LEN];
	int value;
};

// data
Node nodes[MAX_NUM_OF_DATA];

// array for saving top NUM_OF_RANKS of nodes index
int ranks[NUM_OF_RANKS];

void my_str_cpy(char * dest, const char * src) {
	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';
}

int my_str_cmp(const char * str1, const char * str2) {
	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++; str2++;
	}
	return *str1 - *str2;
}

// compare nodes[i] and nodes[j] value ans key.
// nodes[i] > nodes[j] => return 1;
// nodes[i] == nodes[k] => return 0;
// nodes[i] < nodes[j] => return -1;
int my_compare(int i, int j) {
	if (nodes[i].value > nodes[j].value ||
		(nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) < 0)) {
		return 1;
	}
	else if (nodes[i].value == nodes[j].value && my_str_cmp(nodes[i].key, nodes[j].key) == 0) {
		return 0;
	}
	else {
		return -1;
	}
}

void init() {

	// ranks array init
	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		ranks[i] = -1;
	}

	// for random value
	srand(time(NULL));

	// init integer values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		nodes[i].value = rand() % MAX_VALUE_SIZE + 1;
	}

	// init string key values
	for (int i = 0; i < MAX_NUM_OF_DATA; ++i) {
		for (int j = 0; j < MAX_KEY_LEN - 1; ++j) {
			nodes[i].key[j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		nodes[i].key[rand() % MIN_KEY_LEN + MIN_KEY_LEN] = '\0';
	}
}

void find_ranks(int node_id) {

	// return if nodes[node_id]'s value is smaller than last element of ranks array
	if (my_compare(ranks[NUM_OF_RANKS - 1], node_id) > 0) {
		return;
	}

	// traverse ranks array
	for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {

		// if nodes value of index node_id is bigger than current ranks[rank_index]
		if (my_compare(ranks[rank_index], node_id) < 0) {
			// move each values from that point
			for (int j = NUM_OF_RANKS - 1; j > rank_index; --j) {
				ranks[j] = ranks[j - 1];
			}
			// insert node_id to ranks array
			ranks[rank_index] = node_id;
			break;
		}
	}
}

int main() {

	init();

	// insert NUM_OF_RANKS size of data to ranks array
	for (int node_id = 0; node_id < NUM_OF_RANKS; ++node_id) {

		for (int rank_index = 0; rank_index < NUM_OF_RANKS; ++rank_index) {
			// if ranks array is empty then insert node_id
			if (ranks[rank_index] == -1) {
				ranks[rank_index] = node_id;
				break;
			}
			else {
				// if nodes value of index node_id is bigger than current ranks[rank_index]
				if (my_compare(ranks[rank_index], node_id) < 0) {
					// move each values from that point
					for (int k = NUM_OF_RANKS - 1; k > rank_index; --k) {
						ranks[k] = ranks[k - 1];
					}
					// insert node_id to ranks array
					ranks[rank_index] = node_id;
					break;
				}
			}
		}
	}

	// Find top NUM_OF_RANKS elements in nodes
	for (int node_id = NUM_OF_RANKS; node_id < MAX_NUM_OF_DATA; ++node_id) {
		find_ranks(node_id);
	}

	for (int i = 0; i < NUM_OF_RANKS; ++i) {
		printf("%d : \n", i + 1);
		printf("ID : %d\n", ranks[i]);
		printf("Value : %d\n", nodes[ranks[i]].value);
		printf("Key : %s\n", nodes[ranks[i]].key);
	}
	return 0;
}

Reference

April 06, 2019TWpower Reading time ~12 minutes

[Algorithm](EN) Hash table implementation in C/C++

Implement hash table in C/C++

Environment and Prerequisite

C++
Understanding of hash function and linked list

Hash Function

What is Hash Function?

Hash Function : Hash function is any function that can be used to map data of arbitrary size onto data of a fixed size. Sometimes hash function result could be same. In this case we call this as Collision.(H(s1) = H(s2))
In below picture, blue things on left are keys and each key goes into hash function and result into right side hashe values. Later on in hash table values on right side will be used as hash table array index.
Consider H() as hash function, then H(Jonh Smith) = 02

Hash Collision

Case which different key results in same hash value.
Consider H() as hash function and s1 and s2 as different string, then H(s1) = H(s2)
Solution for collision : Chaining or Open Addressing

Example

Below sample is simple hash function which get string and return integer value;
On internet there are many hash function implementations. Shift operation and prime number is widely used in hash function.

int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

Hash Table

Data structure which save pair data key and value
Like below usage, it is a data structure use Lisa Smith as key and save 521-8976 as value.
There are already hash table implementations in each language like map in C++ and dictionary in python.
Theoretically, accessing time complexity is O(c). Hash table use more memory but take advantage of accessing time.
Use Chaining or Open Addressing for collision

Implementation

In this post, I use Chaining for collision.
Use Singly Linked List for Chaining

Common

Hash table implementation using linked list
Node is for data with key and value

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_TABLE 5 // size of table
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // num of datas for hash table
#define DELETE_COUNT 6 // num of datas for deletion
#define FIND_COUNT 8 // num of datas for finding

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // hash table
char keys[MAX_DATA][MAX_KEY]; // keys
int values[MAX_DATA]; // values

Init Function

Make key-value pairs using random function.

void init() {

	// hash table initiation
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// srand and seed for random function
	srand(time(NULL));

	// init values
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// init keys
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}

String Function

Compare and copy function.

void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}

Hash Function

Just use same function as above
Use shift operatoin and prime number
We need to divide it by MAX_TABLE for hash table array.

int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

Add

Simpel linked list hash add implementation
If there is same key in hash table, then replace its value.

void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = hash(key);

	// insert if first is NULL
	if (tb[index] == NULL) {
		tb[index] = new_node;
	}
	// traverse list one by one
	// change duplicated value if not then add it to front

	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// if key is duplicated, then replace its value
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}

		// add to front if it is not duplicated
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}

Find Value

Use linked list for finding.
If there is matching key, then save it to val and return true.
If there is no matching key, then return false

bool find(const char * key, int * val) {

	int index = hash(key);

	Node * cur = tb[index];

	// Find key by traversing list one by one
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}

Deletion

Delete node if key is matched.
Just check the first of list. It makes easy for implementation.

bool destroy(const char * key) {

	int index = hash(key);

	// check first of list
	if (tb[index] == NULL) {
		return false;
	}

	// check first element
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// others
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

Print

Print all key-value pairs while traversing all table and lists.

void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index : %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}

Main

Test add, find and destroy functions.

int main() {

	char tmp_key[MAX_KEY];
	init();

	// Add

	printf("Add to hash table\n");
	for (int i = 0; i < MAX_DATA; ++i) {
		add(keys[i], values[i]);
	}

	print_hash();


	printf("\n");

	// Delete

	printf("Deleted keys : ");
	for (int i = 0; i < DELETE_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		printf("%s ", tmp_key);
		destroy(tmp_key);
	}
	printf("\n");

	print_hash();


	printf("\n");

	// Find

	int val;
	printf("Found : ");
	for (int i = 0; i < FIND_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		if (find(tmp_key, &val)) {
			printf("{ %s, %d } ", tmp_key, val);
		}
	}
	printf("\n");

	return 0;
}

Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_TABLE 5 // size of table
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // num of datas for hash table
#define DELETE_COUNT 6 // num of datas for deletion
#define FIND_COUNT 8 // num of datas for finding

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // hash table
char keys[MAX_DATA][MAX_KEY]; // keys
int values[MAX_DATA]; // values

void init() {

	// hash table initiation
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// srand and seed for random function
	srand(time(NULL));

	// init values
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// init keys
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}

void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}

int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = hash(key);

	// insert if first is NULL
	if (tb[index] == NULL) {
		tb[index] = new_node;
	}
	// traverse list one by one
	// change duplicated value if not then add it to front

	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// if key is duplicated, then replace its value
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}

		// add to front if it is not duplicated
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}

bool find(const char * key, int * val) {

	int index = hash(key);

	Node * cur = tb[index];

	// Find key by traversing list one by one
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}

bool destroy(const char * key) {

	int index = hash(key);

	// check first of list
	if (tb[index] == NULL) {
		return false;
	}

	// check first element
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// others
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index : %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}

int main() {

	char tmp_key[MAX_KEY];
	init();

	// Add

	printf("Add to hash table\n");
	for (int i = 0; i < MAX_DATA; ++i) {
		add(keys[i], values[i]);
	}

	print_hash();


	printf("\n");

	// Delete

	printf("Deleted keys : ");
	for (int i = 0; i < DELETE_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		printf("%s ", tmp_key);
		destroy(tmp_key);
	}
	printf("\n");

	print_hash();


	printf("\n");

	// Find

	int val;
	printf("Found : ");
	for (int i = 0; i < FIND_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		if (find(tmp_key, &val)) {
			printf("{ %s, %d } ", tmp_key, val);
		}
	}
	printf("\n");

	return 0;
}

Verification

Modify hash function name(hash->my_hash)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <map>
#include <string>

#define TOTAL_TEST_CASE 100

#define MAX_TABLE 300 // size of table
#define MAX_KEY 8 // include null
#define MAX_DATA 2000 // num of datas for hash table
#define DELETE_COUNT 1000 // num of datas for deletion

using namespace std;

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // hash table
char keys[MAX_DATA][MAX_KEY]; // keys
int values[MAX_DATA]; // values

void init() {

	// hash table initiation
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// srand and seed for random function
	srand(time(NULL));

	// init values
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// init keys
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}

void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}

int my_hash(const char * str) {
	int hash = 401;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = my_hash(key);

	// insert if first is NULL
	if (tb[index] == NULL) {
		tb[index] = new_node;
	}
	// traverse list one by one
	// change duplicated value if not then add it to front
	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// if key is duplicated, then replace its value
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}
		// add to front if it is not duplicated
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}

bool find(const char * key, int * val) {

	int index = my_hash(key);

	Node * cur = tb[index];

	// Find key by traversing list one by one
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}

bool destroy(const char * key) {

	int index = my_hash(key);

	// check first of list
	if (tb[index] == NULL) {
		return false;
	}

	// check first element
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// others
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index : %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}

int main() {

	int test_case = 1;
	int correct = 0;


	for (test_case = 1; test_case <= TOTAL_TEST_CASE; ++test_case) {

		init();

		bool is_equal = true;

		map<string, int> m;
		map<string, int>::iterator it;


		for (int i = 0; i < MAX_DATA; ++i) {
			add(keys[i], values[i]);
		}
		for (int i = 0; i < MAX_DATA; ++i) {
			if (m.count(keys[i]) == 0) {
				m.insert(make_pair(keys[i], values[i]));
			}
			else {
				m[keys[i]] = values[i];
			}

		}

		for (int i = 0; i < MAX_DATA; ++i) {

			int tmp;
			find(keys[i], &tmp);

			if (m[keys[i]] != tmp) {
				is_equal = false;
			}
		}

		char tmp_key[MAX_KEY];
		for (int i = 0; i < DELETE_COUNT; ++i) {
			my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
			destroy(tmp_key);
			m.erase(tmp_key);
		}

		for (int i = 0; i < MAX_DATA; ++i) {

			int tmp = -1;

			if (find(keys[i], &tmp) == false && m.count(keys[i]) == 0) {
				continue;
			}

			if (find(keys[i], &tmp) == true && m.count(keys[i]) == 1 && m[keys[i]] == tmp) {
				continue;
			}
			else {
				is_equal = false;
			}

		}

		if (is_equal) correct++;

	}

	printf("Total : %d / %d\n", correct, TOTAL_TEST_CASE);

	return 0;
}

Categories

Tags

About

Home

Welcome to TWpower's Tech Blog

Environment and Prerequisite

Solution

Reference

Environment and Prerequisite

What is Singly Linked List?

Concept

Implementation

Common

Insertion/Delettion Common

Insertion

Deletion

Code

Result

Reference

환경

삽입정렬이란?

개념

전체 자료에서 상위 N개 구하기

방법

구현 목표

구현

공통

문자열 비교

비교함수

초기화

상위 N개를 찾는 배열에 데이터 삽입

메인함수

전체 코드

참고자료

Environment and Prerequisite

Insertion Sort?

Concept

Find top N elements in datas.

Solution

Implmentation Goal

Implementation

Common

String Comparison

Compare Function

Init

Insert node data to ranks array

Main Function

Code

Reference

Environment and Prerequisite

Hash Function

What is Hash Function?

Hash Collision

Example

Hash Table

Implementation

Common

Init Function

String Function

Hash Function

Add

Find Value

Deletion

Print

Main

Code

Verification

Reference