본문 바로가기

programing150

가변 인수 함수 - 개략적인 구조 void VarFunc(int Fix, ...) { va_list ap; va_start(ap,Fix); while (모든 인수를 다 읽을 때까지) { va_arg(ap,인수타입); } va_end(ap); } - 사용되는 함수들은 매크로 함수로 되어 있음 typedef char * va_list; #define _crt_va_start(ap,v) ( ap = (va_list)_ADDRESSOF(v) + _INTSIZEOF(v) ) #define _crt_va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) ) #define _crt_va_end(ap) ( ap = (va_list)0 ) #define va_start _crt_va.. 2015. 6. 8.
허프만 코드 - 길이가 변하는 이진 코드(variable-length binary code) - 전치 코드 > 빈도대로 정렬한 다음 빈도가 클 수록 길이가 짧음 -> 빈도에 대해 최적화가 덜 됨 => 허프만 코드 - 허프만 코드 > 낮은 빈도순으로 정렬한 다음 가장 낮은 빈도부터 이진 트리를 만들어 나감 > 트리가 만들어 질 경우 노드들의 빈도의 합을 가지고 트리와 원소를 같이 정렬하여 다시 가장 낮은 비도 부터 트리를 만들어 나감 > 알고리즘 만들때 우선순위 큐 이용 2015. 6. 5.
다원 탐색 트리 - AVL트리는 균형 이진 트리의 한 종류 이기 때문에 자료가 많아지면 트리의 높이가 높아짐 -> 다원 탐색 트리 (m-way Search Tree) 1) 각 노드는 0에서 최대 m 개의 서브 트리를 갖음 2) k개의 서브트리를 갖는 노드는 (k-1) 개의 자료를 갖음 (단, k ≤ m) 3) 각 노드 안에서 자료들은 검색 키에 의해 정렬 4) 다음 조건을 항상 만족 Key i ≤ (i번째 서브트리 내의 모든 키 값) ≤ Key (i+1) 5) 모든 서브트리는 m-원 탐색 트리 (B-tree [비 트리]) > m-원 탐색 트리에서 트리 균형을 유지 1) 루트 노드는 leaf 노드이거나, 2에서 m 개의 서브트리를 가짐 2) 루트 노드를 제외한 모든 내부 노드는 아래 개수만큼 서브트리를 가짐 m/2(소수이.. 2015. 6. 4.
해싱 함수 충돌 해결 방법 - 클러스터링 (Clustering) : 자료들이 해시 테이블에 고르게 분포되지 않고 특정 주소들 주위로 뭉치게 되는 현상 - 개방 주소 (Open Addressing) > 조사법 (Probing)이라고도 함 > 주소가 비어있지 않으면 그 다음 주소를 확인하고 안비어 있으면 되풀이 1) 선형 조사법 -> 주소를 1씩 증가 2) 제곱 조사법 -> 주소를 조사 횟수의 제곱만큼씩 증가 3) 이중 해싱 -> 원래 해싱 함수와는 다른 추가적인 해싱 함수 이용 - 체이닝 (Chaining) > 해시 테이블의 구조를 변경하여 각 주소(버킷)에 하나 이상의 검색 키 값이 저장될 수 있도록 함 2015. 6. 4.

티스토리툴바