Programming/DS SorceCode 썸네일형 리스트형 STL 맵 클래스의 활용 : 영어 단어장 STL 맵 클래스의 활용 : 영어 단어장 표준 템플릿 라이브러리는 맵 클래스를 제공한다. 맵은 탐색을 위한 자료구조로 지금까지 맵을 구현할 수 있는 다양한 방법을 공부했다. 우리는 STL 의 맵이 어떤 방법으로 구현되었는지는 관심을 갖지 않는다. 그리고 탐색을 수행하는 자료의 특성에 따라 효율적으로 구현하는 방법이 달라질 수 있다. 이 절에서는 STL의 맵을 사용하기 위해서는 해싱이나 이진 탐색 트리를 고려할 필요 없이 다음과 같이 헤더파일을 포함시키는 것만으로 충분하다. #include using namespace std; 맵에서는 기본적로 키(key) 와 값(value)이 정의되어야 한다. STL의 맵에서도 마찬가지로, 키를 위한 자료형과 값을 위한 자료형을 정해야 한다. 우리는 영어 단어장을 만들 .. 더보기 HashChainMap.h : 해시 체이닝으로 구현된 해시 맵 #pragma once#ifndef ___HashChainMap#define ___HashChainMap// HashChainMap.h : 해시 체이닝으로 구현된 해시 맵 #include "HashNode.h"#include "hashFunctions.h" class HashChainMap {Node* table[TABLE_SIZE];public:HashChainMap() { for (int i = 0; i getLink())print.. 더보기 HashNode.h : 해시 맵을 위한 노드 클래스 #pragma once#ifndef ___HashNode#define ___HashNode// HashNode.h : 해시 맵을 위한 노드 클래스#include "HashRecord.h" class Node : public Record {Node* link;// 다음 노드를 가리키는 포인터 함수public:Node(const char* key, const char* val): Record(key, val), link(NULL) {}Node* getLink() { return link; }void setLink(Node* next) { link = next; }};#endif // !___HashNode 더보기 HashMap.h : 해싱을 이용하는 맵 클래스 #오류 있음 #pragma once#ifndef ___HashMap#define ___HashMap// HashMap.h : 해싱을 이용하는 맵 클래스#include "HashRecord.h"#include "hashFunctions.h" class HashMap {// 해시 맵 클래스 선언Recordtable[TABLE_SIZE];// 해싱 테이블. 크기는 13public:HashMap() { reset(); }// 생성자. 모든 버켓을 비움void reset() {// 모든 버켓을 비움for (int i = 0; i < TABLE_SIZE; i++)table[i].reset();} // 맵의 전체 내용을 출력void display() {for (int i = 0; i < TABLE_SIZE; i++) {print.. 더보기 HashRecord.h : 해시 맵을 위한 keyed Record 클래스 #pragma once#ifndef ___HashRecord#define ___HashRecord// HashRecord.h : 해시 맵을 위한 keyed Record 클래스#include #include #include using namespace std;#define KEY_SIZE 64// 탐색키의 최대길이#define VALUE_SIZE 64// 탐색키와 관련된 정보 class Record {char key[KEY_SIZE];// 키 필드(사전의 경우 "단어")char value[VALUE_SIZE];// 키와 관련된 자료 ("의미")public:Record(const char* k = "", const char*v = "") { set(k, v); }void set(const char* k, c.. 더보기 해싱 해싱 해싱은 키값을 비교하는 것이 아니라 탐색키에 산술적인 연산을 적용하여 항목이 저장되어 있는 위치, 즉 인덱스를 직접 계산하는 방식이다. 이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 하며, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다. 예를 들어 탐색키들이 모두 1 ~ 1000 사이의 정수라고 가정해보자. 그렇다면 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것이다. 자료의 삽입과 탐색은 탐색키를 배열의 인덱스로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 된다. 이들 연산은 명백하게 이다. 이것이 해싱의 기본 아이디어이다. 현실적으로는 탐색키들이 문자열이거나 굉장히 큰 숫자이기 때문에 탐색키.. 더보기 AVL 트리 AVL 트리 AVL 트리는 Adelson - Velskii와 Landis에 의해 제안된 트리로 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차리가 1 이하인 이진 탐색 트리를 말한다. 이 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 틀는 항상 균형 트리를 보장하기 때문에 의 탐색 시간을 보장한다. 삽입과 삭제 연산도 시간 안에 할 수 있다. AVL 트리도 탐색에서는 일반 이진 탐색 트리의 탐색 연산과 동일하다. 따라서 시간 복잡도는 이다. AVL 트리에서 균형이 깨질 수 있는 연산은 삽입과 삭제 연산이다. AVL 트리의 삽입 연산 이진 탐색 트리에서 노드가 삽입되면 삽입되는 위치에서 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수가 영향을 .. 더보기 Search.h : 다양한 탐색 함수를 포함함 헤더 색인 순차 탐색색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m 번째 데이터를 가지고 있다. 이 때 주 자료 리스트와 인덱스 테이블은 모두 정려되어 있어야 한다. 색인 순차 탐색 알고리즘은 우선 인덱스 테이블에서 index[i] 더보기 이전 1 2 3 4 ··· 8 다음