C에서 사전 구현
이 기사에서는 C로 사전을 구현하는 방법에 대한 여러 방법을 보여줍니다.
hcreate, hsearch및hdestroy를 사용하여 C에서 사전 기능 구현
일반적으로 C 표준 라이브러리에는 내장 사전 데이터 구조가 포함되어 있지 않지만 POSIX 표준은 사전 기능을 구현하는 데 사용할 수있는 해시 테이블 관리 루틴을 지정합니다. 즉hcreate,hsearch및hdestroy는 해시 테이블 생성, 항목 삽입, 테이블에서 항목 검색, 전체 데이터 구조 할당 해제와 같은 기능을 제공합니다. 구현 된 기능은 최소한이지만 많은 문제 시나리오를 해결할 수 있습니다.
처음에는hcreate함수를 호출하여 주어진 최대 요소 수를 가진 해시 테이블을 생성해야합니다. 이는 유일한 인수로 전달됩니다. hcreate호출 후에는 용량을 수정할 수 없습니다. 따라서 사용자는이 문제를 코드 구조에 반영해야합니다. 테이블이 생성되면hsearch함수를 호출하여 항목을 추가 할 수 있습니다. 2 개의 인수가 필요합니다. 첫 번째는ENTRY유형이며 키에 대해char *의struct로 정의되고 해당 데이터에 대해void *로 정의됩니다. 두 번째 매개 변수는ACTION유형이며, 이는 본질적으로FIND및ENTER라는 두 요소로 구성된enum입니다. 후자의 값은 테이블에서 수행 할 작업을 나타내는 데 사용됩니다.
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
e.key = "Intel";
ep = hsearch(e, FIND);
printf("%s -> %s\n", e.key, (char *)ep->data);
hdestroy();
exit(EXIT_SUCCESS);
}
출력:
Intel -> Willow Cove
코드 예제는 일반 텍스트로 표시되는 키-값 쌍을 보여 주지만 사용자는 해싱 알고리즘을 사용하여 키를 만들고 테이블에 저장할 수 있습니다. 이 경우 간단한 반복을 사용하여 테이블에 6 개 항목을 추가하고 마지막 두 요소를 건너 뛰었습니다. 그러나 다음for루프는 원래 배열의 모든 항목을 쿼리하고 해당 데이터를 인쇄합니다.
hdestroy함수는 해시 테이블 메모리를 해제하는 데 사용되지만 일반적으로 사용자가 생성하는ENTRY개체의 버퍼를 해제하지 않습니다. 따라서 이러한 개체의 포인터가 동적 메모리를 가리키는 경우 호출자는 해당 개체에 대한 핸들을 유지하고 프로그램이 종료되기 전에 할당을 해제해야합니다. 개별 항목은 테이블에서 삭제할 수 없습니다.
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *companies[] = {"Intel", "AMD", "ARM", "Apple",
"Marvell", "Qualcomm", "IBM", "Nvidia"};
static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
"ThunderX2", "Kryo", "z15", "Ampere"};
int main(void) {
ENTRY e;
ENTRY *ep;
const size_t capacity = sizeof companies / sizeof companies[0];
hcreate(capacity);
for (size_t i = 0; i < capacity - 2; i++) {
e.key = companies[i];
e.data = (void *)uarch[i];
ep = hsearch(e, ENTER);
if (ep == NULL) {
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
for (size_t i = 0; i < capacity; i++) {
e.key = companies[i];
ep = hsearch(e, FIND);
ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
: printf("%s -> %s\n", e.key, "Entry not found");
}
hdestroy();
exit(EXIT_SUCCESS);
}
출력:
Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook