목차
1장 자료 구조 소개 ... 13
1.1 자료 구조의 개요 ... 14
1.1.1 자료(Data)와 정보(Information) ... 14
1.2 숫자의 표현과 연산 ... 16
1.2.1 진법 ... 16
1.2.2 부호 표현 ... 17
1.3 알고리즘의 분석 ... 18
1.4 알고리즘의 기술방법 ... 22
1.4.1 자연 언어 방법 ... 22
1.4.2 흐름도 방법 ... 22
1.4.3 알고리즘의 성능 분석과 복잡도(complexity) ... 24
연습문제(선택형) ... 30
연습문제(서술형) ... 32
2장 C언어의 개요 ... 35
2.1 자료형 ... 36
2.1.1 C언어의 자료형 ... 36
2.1.2 기본 자료형 ... 37
2.1.3 실수형(부동소수점형) ... 37
2.1.4 문자형 ... 38
2.1.5 문자와 문자열 ... 39
2.1.6 열거형(enum) ... 39
2.2 변수와 자료형 ... 40
2.2.1 변수의 정의 ... 40
2.2.2 변수와 자료형 ... 40
2.3 제어 구조 ... 41
2.3.1 선택 제어 구조 ... 41
2.3.2 반복 제어 구조 ... 42
2.4 포인터 ... 45
2.4.1 포인터의 개요 ... 45
2.4.2 다중 포인터 ... 48
2.4.3 메모리 동적 할당 ... 50
2.5 구조체와 공용체 ... 54
2.5.1 구조체 ... 55
2.5.2 공용체 ... 59
연습문제(선택형) ... 63
연습문제(서술형) ... 66
3장 배열과 문자열 ... 69
3.1 순서 리스트(Ordered List) ... 70
3.2 배열의 정의 ... 71
3.2.1 1차원 배열 ... 71
3.2.2 배열과 포인터 ... 74
3.2.3 2차원 배열의 표현 ... 77
3.2.4 3차원 배열의 표현 ... 81
3.3 다항식 ... 86
3.4 희소 행렬의 표현 ... 90
3.4.1 희소행렬 ... 90
3.4.2 희소행렬과 전치 ... 92
3.5 문자열 추상 데이터 타입 ... 97
3.6 문자열 삽입 ... 103
연습문제(선택형) ... 105
연습문제(서술형) ... 108
4장 스택과 큐 ... 111
4.1 스택의 정의 ... 112
4.2 스택의 연산 ... 114
4.2.1 스택의 저장 ... 114
4.2.2 스택의 연산 ... 115
4.3 스택의 응용 ... 117
4.3.1 괄호 처리 ... 117
4.3.2 연산자의 우선 순위 ... 118
4.3.3 수식의 표현방법 ... 120
4.3.4 부프로그램의 처리 ... 123
4.3.5 인터럽트 처리 ... 124
4.4 다중 스택 ... 126
4.4.1 이중 스택 ... 127
4.4.2 일반적인 다중 스택 ... 127
4.5 큐의 정의 ... 129
4.5.1 큐의 순서적 표현방법 ... 129
4.5.2 큐의 저장 ... 130
4.5.3 큐의 연산 ... 131
4.6 큐의 응용 원형 큐(Circular Queue) ... 135
4.6.1 큐의 이동 ... 135
4.6.2 원형 큐의 표현 ... 136
4.7 데큐 (Deque) ... 139
4.7.1 데큐의 정의 ... 139
4.7.2 데큐의 연산 ... 139
4.7.3 데큐의 종류 ... 140
연습문제(선택형) ... 142
연습문제(서술형) ... 146
5장 연결 리스트 ... 149
5.1 배열과 리스트 ... 150
5.2 연결 리스트의 정의 ... 151
5.2.1 단순 연결 리스트(singly linked list) ... 152
5.2.2 연결 리스트의 저장 ... 153
5.2.3 연결 리스트에서의 메모리 관리 ... 159
5.2.4 단순 연결 리스트의 활용 다항식(modify) ... 162
5.3 이중 연결 리스트(Double Linked List) ... 168
5.4 이중 원형 연결 리스트(Doubly circular linked list) ... 174
연습문제(선택형) ... 179
연습문제(서술형) ... 182
6장 되부름 ... 185
6.1 되부름의 정의 ... 186
6.2 되부름 수행 과정 ... 190
6.3 되부름 알고리즘의 설계 ... 194
6.4 하노이 탑 ... 196
6.4.1 하노이 탑의 되부름 알고리즘 ... 196
6.4.2 C언어에 의한 구현 ... 201
연습문제(선택형) ... 203
연습문제(서술형) ... 205
7장 트리(TREE) ... 207
7.1 트리(Tree) ... 208
7.2 트리의 표현 ... 211
7.3 이진 트리 ... 212
7.3.1 이진 트리의 특성 ... 214
7.3.2 이진 트리의 표현 ... 216
7.4 이진 트리의 순회(Traversal) ... 220
7.4.1 중위순회(Inorder Traversal) ... 221
7.4.2 전위순회(Preorder Traversal) ... 223
7.4.3 후위순회(Postorder Traversal) ... 224
7.5 스레드 이진트리의 정의와 표현 ... 225
7.5.1 스레드 이진 트리의 표현 ... 228
7.5.2 스레드 이진트리에서의 노드 삽입ㆍ삭제 ... 230
7.6 이진 탐색 트리의 균형 ... 233
7.6.1 AVL-트리 ... 233
7.6.2 BB-트리 ... 241
연습문제(선택형) ... 242
연습문제(서술형) ... 248
8장 그래프 ... 251
8.1 그래프(Graph) ... 252
8.1.1 그래프의 정의 ... 254
8.2 그래프의 표현 ... 258
8.2.1 인접 행렬(Adjacent matrix) 표현 ... 258
8.2.2 간선 리스트(Edge list) 표현 ... 260
8.2.3 인접 리스트(adjacent list) 표현 ... 262
8.2.4 인접 다중 리스트 ... 264
8.3 그래프의 순회 ... 265
8.3.1 깊이우선탐색(depth first search: DFS) ... 265
8.3.2 너비우선탐색(Breadth first search: BFS) ... 268
8.4 신장트리(Minimal Cost Spanning Tree) ... 270
8.4.1 신장 트리의 정의 ... 270
8.4.2 최소비용 신장 트리 ... 271
8.4.3 Kruskal 알고리즘 ... 274
8.4.4 Prim 알고리즘 ... 278
8.4.5 Sollin 알고리즘 ... 281
8.5 최단 경로(Shortest Path) ... 284
8.5.1 두 정점간의 최단경로(Source-to-Destination Shortest Path) ... 284
8.5.2 SMT(Source-to-Mulitiple Terminal) 최단 경로 ... 287
8.6 간선 작업 네트워크 ... 289
연습문제(선택형) ... 291
연습문제(서술형) ... 293
9장 탐색과 내부 정렬 ... 295
9.1 탐색(Search) ... 296
9.1.1 순차 탐색 ... 298
9.1.2 이진 탐색 ... 300
9.1.3 피보나치 탐색 ... 303
9.2 정렬 ... 307
9.2.1 내부 정렬 ... 308
9.2.2 외부 정렬 ... 344
연습문제(선택형) ... 349
연습문제(서술형) ... 354
10장 해싱 ... 357
10.1 해싱의 정의 ... 358
10.2 정적 해싱 ... 359
10.2.1 해싱 테이블 ... 359
10.2.2 해싱 함수 ... 361
10.2.3 오버플로 처리 ... 363
10.3 동적 해싱 ... 372
10.3.1 디렉토리를 사용하는 동적 해싱 ... 372
10.3.2 디렉토리 없는 동적 해싱 ... 377
연습문제(선택형) ... 381
연습문제(서술형) ... 382
11장 자료 압축 ... 385
11.1 자료 압축 조건 ... 386
11.2 Huffman Coding ... 388
11.3 Shannon-Fano Code ... 398
11.4 Run-Length Encoding ... 400
11.5 Ziv-Lempel 압축 ... 402
11.6 허프만 방식에서의 런-길이 압축 ... 404
찾아보기 ... 416
닫기