[22-2] 자료구조 정리
쌓아놓은 더미, LIFO(가장 최근에 들어온 데이터가 가장 먼저 나감)
- create(max_size) : 최대 크기가 max_size인 공백스택을 생성
- push() : 스택에 주어진 데이터를 추가
- pop() : 스택에서 데이터를 삭제와 동시에 반환
- is_empty() : 스택이 공백상태인지 검사
- is_full() : 스택이 포화상태인지 검사
- peek() : 요소를 스택에서 삭제하지 않고 보기(read)만 하는 연산
먼저 들어온 데이터가 먼저 나가는 자료구조, FIFO
- create(max_size) : 최대 크기가 max_size인 공백큐 생성
- init() : 큐를 초기화
- is_empty() : 큐가 공백상태인지 검사
- is_full() : 큐가 포화상태인지 검사
- enqueue() : 큐의 끝에 요소 추가
- dequeue() : 큐의 맨 앞에 있는 요소를 삭제와 동시에 반환
- peek() : 큐의 맨 앞에 있는 요소를 삭제하지 않고 보기(read)만 하는 연산
double-ended queue, 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐
- create(max_size) : 최대 크기가 max_size인 공백덱 생성
- init() : 덱을 초기화
- is_empty() : 덱이 공백상태인지 검사
- is_full() : 덱이 포화상태인지 검사
- add_front() : 덱의 앞에 요소 추가
- add_rear() : 덱의 끝에 요소 추가
- delete_front() : 덱의 앞에 있는 요소를 삭제와 동시에 반환
- delete_rear() : 덱의 뒤에 있는 요소를 삭제와 동시에 반환
- get_front() : 덱의 앞에 있는 요소를 삭제하지 않고 보기(read)만 하는 연산
- get_rear() : 덱의 뒤에 있는 요소를 삭제하지 않고 보기(read)만 하는 연산
항목들이 차례대로 저장되어 있고, 리스트의 항목들은 순서 또는 위치를 가짐
- insert(list, pos, item) : pos 위치에 요소를 추가함 -> 아무 곳에나 데이터를 삽입할 수 있음
- insert_last(list, item) : 맨 끝에 요소를 추가함
- insert_first(list, item) : 맨 처음에 요소를 추가함
- delete(list, pos) : pos 위치의 요소를 제거함
- clear(list) : 리스트의 모든 요소를 제거함
- get_entry(list, pos) : pos 위치의 요소를 반환함
- get_length(list) : 리스트의 길이를 구함
- is_empty(list) : 리스트가 비었는지를 검사함
- is_full(list) : 리스트가 꽉 찼는지를 검사함
- print_list(list) : 리스트의 모든 요소를 표시함
계층적 자료구조, 부모 - 자식 관계의 노드들로 이루어짐
[ 트리의 용어 ]
- 노드(node) : 트리의 구성요소
- 루트(root) : 부모가 없는 노드
- 서브 트리(subtree) : 하나의 노드와 그 노드의 자손들로 이루어진 트리
- 단말노드(terminal node) : 자식이 없는 노드
- 비단말노드(nonterminal node) : 적어도 하나의 자식을 가지는 노드
- 레벨(level) : 트리의 각층의 번호 -> 맨 위가 1
- 높이(height) : 트리의 최대 레벨
- 차수(degree) : 노드가 가지고 있는 자식 노드의 개수
우선순위를 가진 항목들을 저장하는 큐, FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나감
- create() : 우선순위 큐를 생성
- init(q) : 우선순위 큐 q를 초기화
- is_empty(q) : 우선순위 큐 q가 비어있는가를 검사함
- is_full(q) : 우선순위 큐 q가 가득 찼는가를 검사함
- insert(q, x) : 우선순위 큐 q에 요소 x를 추가함
- delete(q) : 우선순위 큐로부터 우선순위가 가장 높은 요소를 삭제하고 이 요소를 반환함
- find(q) : 우선순위가 가장 높은 요소를 반환함
연결되어 있는 객체 간의 관계를 표현, G = (V, E) : 정점의 집합과 간선의 집합
- create_graph() : 그래프를 생성
- init(g) : 그래프 g를 초기화함
- insert_vertex(g, v) : 그래프 g에 정점 v를 삽입함
- insert_edge(g, u, v) : 그래프 g에 간선 (u, v)를 삽입함
- delete_vertex(g, v) : 그래프 g의 정점 v를 삭제함
- delete_edge(g, u, v) : 그래프 g의 간선 (u, v)를 삭제함
- is_empty(g) : 그래프 g가 공백 상태인지 확인함
- adjacent(v) : 정점 v에 인접한 정점들의 리스트를 반환함
- destroy_graph(g) : 그래프 g를 제거함
물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것, 일반적으로 정렬시켜야 될 대상은 레코드, 키(key) 필드로 레코드와 레코드를 구별함
[ 여러 가지 정렬 ]
- 선택 정렬 (selection sort) : 가장 작은 숫자를 선택해서 정렬된 리스트에 보냄
- 삽입 정렬 (insertion sort) : 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정 반복
- 버블 정렬 (bubble sort) : 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환
- 쉘 정렬 (shell sort) : 전체 리스트를 일정 간격(gap)의 부분 리스트로 나누어서 나뉘어진 각각의 부분 리스트를 삽입 정렬 함
- 합병 정렬 (merge sort) : 입력 배열을 두 개의 균등한 크기로 분할하고, 분할된 부분 배열들을 각각 따로 정렬, 정렬된 두 개의 부분 배열을 합병하여 전체 리스트를 정렬함
- 퀵 정렬 (quick sort) : 리스트를 2개의 부분 리스트로 비균등 분할하고, 각각의 부분 리스트를 다시 재귀 호출하여 퀵 정렬함
- 힙 정렬 (heap sort) : 정렬할 n개의 요소들을 최소 힙에 삽입, 요소를 한 번에 하나씩 힙에서 삭제하여 저장
- 기수 정렬 (radix sort) : 자릿수에 따라 버킷에 넣었다가 꺼냄
여러 개의 자료 중에서 원하는 자료를 찾는 작업, 탐색을 효율적으로 수행하는 것은 매우 중요
[ 여러 가지 탐색 ]
- 순차 탐색 (sequential search) : 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사하는 방법
- 이진 탐색 (binary search) : 정렬된 배열에서의 탐색 방법, 탐색의 범위를 반으로 줄여가며 탐색 진행
- 색인 순차 탐색 (indexed sequential search) : 인덱스 테이블을 사용하여 탐색의 효율 증대, 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 함
- 보간 탐색 (interpolation search) : 탐색 키가 존재할 위치를 예측하여 탐색하는 방법