컴퓨터알고리즘#4

LeeMir, 10 March 2021

기초 데이터 구조

데이터구조의 기본 재료
  • 건물과 비유
    • 데이터구조 : 재료, 자재, 구조
    • 알고리즘 : 조명, 냉난방, 환기, 개폐 시스템
  • 기본 재료
    • 배열
    • 연결리스트
  • 차후의 고급 데이터구조를 구축하는 기본 재료
  • 추상적이기 보다는 구체적 (컴퓨터 구조에 가까움)
배열
  • 배열 : 순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들
  • 배열명(V) : 배열 전체를 일컫는 기호
  • 배열크기(N) : 원소를 저장하는 셀들의 개수
  • 배열첨자(i) : 셀의 순위
    • 시작 : 0 또는 일반적으로 LB(Lower Bound)
    • 끝 : N-1 또는 일반적으로 UB(Upper Bound)
  • 배열원소(V[i]) : 배열 V의 첨자 i에 저장된 원소
  • 배열표시 : V[LB..UB]
  • 배열의 메모리 할당
    • 배열의 선언 : V[LB..UB]
    • 컴파일 시, 배열의 셀들은 베이스(base)라 불리는 배열의 첫째 셀 위치부터 시작하여 차례로 할당된다
    • 각 셀은 베이스로부터 오프셋(offset) 만큼 떨어지게 된다
      • V[LB..UB]의 base로부터 V[k]의 offset = k - LB
  • 다차원 배열
    • 1차원 배열과 다른 점
      • 배열의 방들은 n > 1차원에 할당된다
      • 배열크기 : 각 차원 크기의 곱 (ex : 3x3)
      • 배열첨자 : 각 차원에서의 방의 순위
      • 알고리즘을 설계할 때에는 차원을 갖는 것처럼 생각하나, 메모리에 저장될 때에는 일직선에 저장된다
연결리스트
  • 동적메모리에 할당된, 링크(pointer)에 의해 연결된 유한 개수의 데이터원소 노드들
    • 연결리스트 명(L) : 연결리스트의 시작 위치, 즉, 첫 노드의 주소
    • 연결리스트의 크기(n) : 연결리스트 내 노드 수
  • 노드에 대한 메모리 할당
    • 노드 : 한 개의 데이터원소를 저장하기 위해 동적 메모리에 할당된 메모리
    • 노드를 위한 메모리의 동적 할당과 해제는 실행시간에 system call에 의해 처리된다
  • 단일 연결리스트
    • 연속 노드로 구성된, 가장 단순한 연결 데이터 구조
    • 메모리에 순차적으로 저장되지 않고 여기저기 분산되어 저장되어도 상관 없다
    • 노드 저장내용
      • 원소 : 데이터 원소
      • 링크 : 다음 노드의 주소
        • 다음 노드가 없는 경우 Null 링크를 저장
    • 접근점
      • 첫 노드, 즉, 헤드노드의 주소
        • 헤드 노드는 포인터 형식, 노드 형식, 헤더 형식으로 구현할 수 있다
  • 이중 연결리스트
    • 추가 링크를 사용하여 역방향 순회도 가능
    • 노드 저장내용
      • 원소
      • 링크 : 다음 노드의 주소
      • 링크 : 이전 노드의 주소
    • 접근점
      • 헤드 노드의 주소
      • 테일 노드의 주소
  • 원형 연결리스트
    • 단일 연결리스트에서 마지막 노드의 링크가 Null이 아닌, 헤드 노드의 주소
  • 헤더와 트레일러
    • 헤드노드 바로 앞에 특별한 헤더 노드를 추가하여 작업 편의성을 증진
    • 같은 목적으로 테일노드 바로 뒤에 트레일러 노드를 추가할 수 있다
    • 이러한 특별 노드에는 더미 데이터를 저장한다