연관 배열/맵/해시 테이블 데이터 구조를 구현하는 방법 (일반적으로 C++)

Question

음, 나는 작은 전화 번호부 응용 프로그램을 만들고 있는데, 맵을 사용하는 것이 사용할 수있는 최상의 데이터 구조가 될 것이라고 결정했습니다. 어디서부터 시작해야할지 모르겠다. (처음부터 데이터 구조를 구현해야 함)

Answer 1

Tries은 키가 짧은 문자열 인 맵을 구현하는 데 매우 효율적입니다. 위키 피디 어 (Wikipedia) 기사는 그것을 아주 잘 설명합니다.

는 트리의 각 노드에 중복의 연결리스트는 여기

는 트라이의 기본 구조의 일치 저장할 수 있도록 중복 처리하려면

struct Trie { 
    struct Trie* letter; 
    struct List *matches; 
}; 

의 malloc (26 * sizeof 연산자 (구조체 트리는)) 그리고 당신은 배열을 가지고 있습니다. 구두점을 지원하려면 문자 배열의 끝에 추가하십시오.

일치하는 항목은 링크 된 목록이 될 수 있지만 원하는대로 구현됩니다. 구조 목록을 정의하지 않겠습니다.

Answer 2

두 가지 벡터 (하나는 값, 하나는 값)를 사용하는지도 클래스를 만드는 것이 간단합니다. 항목을 추가하려면 하나의 키와 다른 키의 값을 삽입하십시오. 값을 찾으려면 모든 키를 반복하면됩니다. 일단이 작업을 수행하면보다 복잡한 데이터 구조 사용에 대해 생각할 수 있습니다.

Answer 3

가장 간단한 해결책 : 주소 항목이 포함 된 벡터를 사용하고 검색 할 벡터 위로 반복하십시오.

지도는 일반적으로 이진 트리 (균형 조정을 위해 빨간색/검은 색 나무를 찾습니다) 또는 해시 맵으로 구현됩니다. 나무는 조직, 메모리 관리 및 균형 조정에 약간의 오버 헤드가 있으며, 해시 맵에는 좋은 해시 함수가 필요하며 이는 사소하지도 않습니다. 그러나 두 구조는 모두 재미 있습니다. 둘 중 하나 (또는 ​​둘 다 :-))를 구현하면 많은 통찰력을 얻을 수 있습니다.

데이터를 벡터 목록에 유지하고지도에 벡터에 대한 색인 (또는 항목에 대한 포인터)이 포함되도록 고려하십시오. 그러면 이름과 전화 번호에 대해 여러 개의 색인을 쉽게 만들 수 있습니다 그래서 당신은 양쪽 모두에 의해 엔트리를 찾을 수 있습니다. 난 그냥 강력