컴퓨터알고리즘#11

LeeMir, 28 April 2021

사전 ADT

사전 ADT
  • 사전 ADT는 탐색 가능한 형태의 (키, 원소) 쌍 항목들의 모음을 모델링
  • 사전에 관한 주요 작업
    • 탐색
    • 삽입
    • 삭제
  • 두 종류의 사전
    • 무순사전 ADT
    • 순서사전 ADT
  • 응용
    • 직접 응용
      • 연락처 목록
      • 신용카드 사용승인
      • 인터넷주소 매핑
        • 호스트명을 인터넷 주소로 매핑
    • 간접 응용
      • 알고리즘 수행을 위한 보조 데이터 구조
      • 다른 데이터 구조를 구성하는 요소
  • 탐색
    • 비공식적인 탐색
      • 데이터 집단으로부터 특정한 정보를 추출함
    • 공식적인 탐색
      • 사전으로 구현된 데이터 집단으로부터 지정된 키(Key)와 연관된 데이터 원소를 반환함
    • 유일 키 : 한 개의 키에 대해 하나의 데이터 항목만 존재
    • 중복 키 : 한 개의 키에 대해 여러 개의 데이터 항목 존재
무순사전 ADT
  • 기록 파일 : 무순리스트를 사용하여 구현된 사전
    • 사전 항목들을 임의의 순서로 리스트에 저장
    • 소규모의 사전, 또는 삽입은 빈번하지만 탐색이나 삭제는 드물 경우 효율적
순서사전 ADT
  • 일람표 : 순서리스트를 사용하여 구현된 사전
  • 소규모 사전, 또는 탐색은 빈번하지만 삽입이나 삭제는 드문 사전