기초 데이터 구조

고급 데이터 구조를 구축하는데 사용 가능한 데이터 구조로, 비교적 구체적이다.

배열

정의

순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들

• 배열명 V
• 배열크기 N : 원소를 저장하는 셀 개수
• 배열첨자 i
  • 시작첨자 : LB 또는 0
  • 끝첨자 : UB 또는 N-1
• 배열원소 V[i]
• 배열표시(선언) V[LB..UB]

선언, 베이스, 오프셋

1차원 배열을 예시로 설명한다.

• 선언
  LB=0, UB=5인 1차원 배열은 V[5..10]와 같이 선언
  → N=6, 5≤i≤10
• 베이스 : 배열의 첫 원소 ( e.g. V[5] )
• 오프셋 : 어떤 셀이 베이스로부터 떨어진 정도
  → 어떤 셀 V[k]의 offset = k-LB ( e.g. V[9]의 offset = 9-5 = 4 )

다차원배열

다차원 배열은 행우선 순서(저차원 우선 순서)로 메모리에 할당된다.
→ 차수가 낮은 것의 인덱스 증가속도가 느리다.

(e.g.) V[0..2, 5..7] 인 2차원 배열의 메모리 할당 상태

선언

LB=0이면

• 2차원 배열 : V[$N_1$
• 3차원 배열 : V[$N_1$
• 4차원 배열 : V[$N_1$

일반적으로

• 2차원 배열 : V[$LB_1$
• 3차원 배열 : V[$LB_1$
• 4차원 배열 : V[$LB_1$

오프셋

배열 V[$LB_1$

• 2차원 배열 : $[ (k_1-LB_1)(UB_2-LB_2+1) ]+(k_n-LB_2)$
• 3차원 배열 : $[ (k_1-LB_1)(UB_2-LB_2+1)(UB_3-LB_3+1) + (k_2-LB_2)(UB_3-LB_3+1) ]+(k_n-LB_3)$

연결리스트

정의

동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터원소 노드들

• 노드 : 한 개의 데이터 원소를 저장하기 위해 동적 메모리에 할당된 메모리
  • 헤드(head) 노드 : 의미있는 원소를 가진 첫 번째 노드
  • 테일(tail) 노드 : 의미있는 원소를 가진 마지막 노드
  • 헤더(header) 노드 : 헤드노드 앞에 위치한, 모조원소를 가진 노드
  • 트레일러(trailer) 노드 : 테일노드 뒤에 위치한, 모조원소를 가진 노드
• 연결리스트 명 L : 연결리스트의 시작 위치 (=첫 노드 주소)
• 연결리스트 크기 n : 노드 수

노드 기본연산

• getnode() : 노드 메모리 할당 + 주소 반환 (메모리 고갈시 null반환)
• putnode() : 노드 메모리 해제

단일 연결리스트

	L
[el][link]--->[el][link]---> [el][∅]

• 특징 : 연속 노드로 구성. 가장 단순한 연결 데이터 구조
• 저장내용
  • 원소
  • next 링크
• 접근점 : 헤드노드

이중 연결리스트

[∅][el][next]<--->[prev][el][next]<--->[prev][el][next]<--->[prev][el][∅]

• 특징 : 역방향 순회 가능
• 저장내용
  • 원소
  • prev 링크
  • next 링크
• 접근점 : 헤드노드, 테일노드

원형 연결리스트

┌-> [el][link]--->[el][link]---> [el][link]
└--------------------------------------┘

• 특징 : 마지막 노드의 링크가 헤드노드를 가리킴
• 저장내용
  • 원소
  • next 링크
• 접근점 : 헤드노드

기타

• 원형 헤더 연결리스트 : 헤더가 있는 원형 연결리스트. 테일노드가 헤더를 가리킴
• 원형 이중 연결리스트 : 헤드의 prev가 테일을, 테일의 next가 헤드를 가리킴
• 헤더 및 트레일러 이중 연결리스트 : 헤더, 트레일러가 있는 '이중 연결리스트'
• 헤더 및 트레일러 원형 이중 연결리스트 : 헤더, 트레일러가 있는 '원형 이중 연결리스트'