1장 자료 구조의 소개
   1.1 자료 구조의 개요 ... 18
   1.2 자료의 표현 ... 21
      1. 수치적 자료의 표현 ... 21
        ⑴ 정수의 표현 ... 21
        ⑵ 실수의 표현 ... 26
      2. 비 수치적 자료의 표현 ... 30
        ⑴ BCD(Binary Coded Decimal) 코드 ... 30
        ⑵ SBCD(Standard Binary Coded Decimal) 코드 ... 31
        ⑶ EBCDIC(Extended Binary Coded Decimal Interchange Code) 코드 ... 32
        ⑷ ASCII(American Standard Code for Information Interchange) 코드 ... 36
        ⑸ 가중치 코드(weighted code) ... 38
        ⑹ 비가중치 코드(non-weighted code) ... 40
        ⑺ 에러 검출 코드 ... 43
      3. 포인터(pointer) 자료의 표현 ... 46
        ⑴ 정의 ... 46
        ⑵ 매개 변수 전달 기법 ... 46
      4. 스트링(string) 구조 ... 52
        ⑴ 정의 ... 52
        ⑵ 스트링의 활용 ... 52
        ⑶ 서브 스트링의 구분 방법 ... 53
        ⑷ 스트링의 연산 ... 54
   연습문제 ... 57
2장 리스트(list)
   2.1 배열(array) ... 64
      ⑴ 1차원 배열(1 dimensional array) ... 65
      ⑵ 2차원 배열(2 dimensional array) ... 66
      ⑶ 3차원 배열(3 dimentional array) ... 68
      ⑷ 희소 행렬(sparse matrix) ... 71
      ⑸ 행렬의 간단한 예(magic square matrix) ... 71
   2.2 선형 리스트(linear list) ... 74
      ⑴ 선형 리스트에 대하여 처리하는 일반적인 용어들 ... 74
      ⑵ 선형 리스트에서의 삽입 ... 75
      ⑶ 선형 리스트에서의 삭제 ... 76
      ⑷ 선형 리스트의 밀도(density) ... 77
   2.3 연결 리스트(linked list) ... 77
      ⑴ 연결 리스트의 특징 ... 78
      ⑵ 연결 리스트의 구성 요소 ... 78
      ⑶ 연결 리스트의 삽입 알고리즘 ... 79
      ⑷ 연결 리스트의 삭제 알고리즘 ... 80
      ⑸ 연결 리스트를 이용한 스택 표현 ... 80
      ⑹ 연결 리스트를 이용한 큐의 표현 ... 81
      ⑺ 선형 리스트와 연결 리스트의 비교 ... 83
      1. 환상 연결 리스트(circular linked list) ... 83
        ⑴ 적용 ... 83
        ⑵ 장·단점 ... 84
      2. 이중 연결 리스트(doubly linked list) ... 84
        ⑴ 삽입 알고리즘 ... 85
        ⑵ 삭제 알고리즘 ... 87
      3. 이중 환상 연결 리스트(doubly circular linked list) ... 87
   연습문제 ... 89
3장 제한된 구조
   3.1 스택(stack) ... 94
      ⑴ 스택에서 사용되는 용어 ... 94
      ⑵ 스택에서 사용되는 연산 ... 95
      ⑶ 스택에서의 삽입(insert) : push-down 작업 ... 96
      ⑷ 스택에서의 삭제(delete) : pop-up작업 ... 97
      ⑸ 스택의 이용 ... 99
      ⑹ 스택의 오버플로우 발생시 처리 방법 ... 104
   3.2 큐(queue) ... 110
      ⑴ 큐에서 사용되는 연산 ... 110
      ⑵ 큐를 표현하기 위한 조건 ... 110
      ⑶ 큐의 삽입 ... 111
      ⑷ 큐의 삭제 ... 111
      ⑸ 큐에서의 오버플로우 처리 ... 114
      ⑹ 큐의 응용 ... 117
   3.3 데크(deque) ... 118
      ⑴ 데크의 삽입과 삭제 ... 118
      ⑵ 데크의 종류 ... 119
   연습문제 ... 120
4장 트리(Tree)와 그래프(Graph)
   4.1 트리(tree) ... 126
      1. 트리(tree) ... 126
        ⑴ 트리의 용어 ... 127
        ⑵ 트리의 종류 ... 132
        ⑶ 트리의 저장법 ... 134
        ⑷ 트리의 성질 ... 135
        ⑸ 트리의 운행법(tree traversal) ... 136
        ⑹ 트리의 응용 ... 138
      2. 이진 트리(binary tree) ... 138
        ⑴ 이진 트리의 종류 ... 138
        ⑵ 이진트리에서 사용되는 함수의 정의 ... 141
        ⑶ 트리와 이진 트리의 차이점 ... 142
        ⑷ 이진 트리의 저장법 ... 142
        ⑸ 트리의 상호 변환하는 방법 ... 147
        ⑹ 이진 트리의 운행법(binary tree traversal) ... 150
        ⑺ 이진 검색 트리(binary search tree) ... 157
        ⑻ 연산식의 내부 표현(polish notation) ... 158
      3. 스레드 이진 트리(threaded binary tree) ... 168
        ⑴ 스레드 이진 트리의 구조 형식 ... 168
        ⑵ 스레드 이진 트리의 운행법 ... 170
        ⑶ 스레드 이진 트리에서 노드 삽입 ... 172
      4. 이진 트리의 경로 길이 ... 173
        ⑴ 내부 경로(internal path) 길이 ... 173
        ⑵ 외부 경로(external path) 길이 ... 173
        ⑶ 이진 트리에 대한 가중된 경로 길이(weighted path length) ... 174
      5. 이진 트리의 삽입과 삭제 ... 175
        ⑴ 이진 트리의 삽입(binary tree insertion) ... 175
        ⑵ 이진 트리의 삭제 ... 176
   4.2 그래프(graph) ... 178
      1. 그래프의 정의 ... 178
      2. 그래프의 종류 ... 178
        ⑴ 무향 그래프(undirected graph) ... 178
        ⑵ 유향 그래프(directed graph) ... 178
        ⑶ 다중 그래프(multi graph) ... 178
        ⑷ 단순 그래프(single graph ... tree
        ⑸ 완전 그래프(complete graph) ... 179
        ⑹ 종속 그래프(subgraph) ... 179
        ⑺ 정규 그래프(regular graph) ... 180
        ⑻ 연결 그래프(connected graph)와 단절 그래프(disconnected graph) ... 180
        ⑼ 강력 연결 그래프(strongly connected graph) ... 181
        ⑽ 트리 그래프(tree graph) ... 181
      3. 그래프의 용어 ... 181
        ⑴ 인접(adjacent) ... 181
        ⑵ 결합(incident) ... 182
        ⑶ 경로(path) ... 182
        ⑷ 단순 경로(simple path) ... 182
        ⑸ 순환(cycle) ... 182
        ⑹ 차수(degree) ... 182
        ⑺ 거리(distance) ... 183
        ⑻ 진입 차수(in-degree) ... 183
        ⑼ 진출 차수(out-degree) ... 183
        ⑽ 연결 요소(connected components) ... 183
      4. 그래프의 표현(저장법) ... 184
        ⑴ 표를 이용하는 방법 ... 184
        ⑵ 포인터를 사용한 리스트 ... 185
        ⑶ 인접 행렬(adjacency matrix) ... 186
        ⑷ 이행적 폐쇄 행렬(transitive closure matrix) ... 187
        ⑸ 반사 이행적 폐쇄 행렬(reflexive transitive closure matrix) ... 187
        ⑹ 인접 리스트(adjacency list) ... 188
        ⑺ 인접 다중 리스트(adjacency multi list) ... 188
        ⑻ 역 인접 리스트(inverse adjacency list) ... 189
        ⑼ 직교 리스트(orthogonal list) ... 191
      5. 그래프의 운행 ... 191
        ⑴ DFS(Depth First Search : 깊이 우선 탐색) ... 192
        ⑵ BFS(Breadth First Search : 너비 우선 탐색) ... 194
      6. 그래프의 응용 ... 196
        ⑴ 신장 트리(spanning tree) ... 196
        ⑵ 최소 비용 신장 트리(minimal cost spanning tree) ... 196
        ⑶ 최단경로(shortest path) ... 200
        ⑷ AOV(Activity On Vertex network) ... 203
        ⑸ 위상 순서(topological order tree) ... 203
        ⑹ 간선 작업 네트워크(Activity On Edge network : AOE network) ... 204
        ⑺ 임계 경로(critical path) ... 205
   연습문제 ... 206
5장 정렬(Sort)
      1. 정렬 장소에 따른 구분 ... 214
        ⑴ 내부정렬(internal sort) ... 214
        ⑵ 외부정렬(external sort) ... 214
      2. 정렬 방식에 따른 구분(정렬 알고리즘에 따른 구분 방법) ... 214
        ⑴ 비교식 정렬(comparative sorting) ... 214
        ⑵ 분산식 정렬(distributive sorting) ... 214
        ⑶ 주소 계산 정렬(address calculation sort) ... 215
      3. 처리 순서에 따른 구분 ... 215
      4. 정렬 알고리즘의 선택시 고려 사항 ... 215
      5. 정렬 효율의 결정 요소 ... 216
   5.1 내부 정렬(internal sort) ... 216
      1. 삽입 정렬(insert sort) ... 216
        ⑴ 정의 ... 216
        ⑵ 삽입 정렬 알고리즘 ... 217
        ⑶ 삽입 정렬 수행 예제 ... 218
        ⑷ 삽입 정렬 실행 프로그램 ... 218
        ⑸ 비교 횟수와 연산 시간 ... 219
      2. 선택 정렬(selection sort) ... 220
        ⑴ 정의 ... 220
        ⑵ 선택 정렬 알고리즘 ... 220
        ⑶ 선택 정렬 수행 예제 ... 221
        ⑷ 선택 정렬 실행 프로그램 ... 221
        ⑸ 비교 횟수와 연산 시간 ... 222
      3. 버블 정렬(bubble sort) ... 222
        ⑴ 플래그(flag)가 없는 버블 정렬 ... 222
        ⑵ 플래그가 있는 버블 정렬 ... 224
      4. 퀵 정렬(quick sort) ... 228
        ⑴ 정의 ... 228
        ⑵ 퀵 정렬 알고리즘 ... 228
        ⑶ 퀵 정렬 실행 예제 ... 229
        ⑷ 퀵 정렬 실행 프로그램 ... 230
        ⑸ 비교 횟수와 연산 시간 ... 232
      5. 셀 정렬(shell sort) ... 232
        ⑴ 정의 ... 232
        ⑵ 셀 정렬 알고리즘 ... 233
        ⑶ 셀 정렬 실행 예제 ... 234
        ⑷ 셀 정렬 실행 프로그램 ... 235
      6. 2-Way 병합 정렬(2-way merge sort) ... 239
        ⑴ 정의 ... 239
        ⑵ 2-Way 병합 정렬 알고리즘 ... 239
        ⑶ 2-Way 병합 정렬 수행 예제 ... 241
        ⑷ 2-Way 병합 정렬 실행 프로그램 ... 241
        ⑸ 2-Way 병합 정렬 실행 시간 ... 243
      7. 기수 정렬(radix sort) ... 243
        ⑴ 정의 ... 243
        ⑵ 기수 정렬 알고리즘 ... 244
        ⑶ 기수 정렬 수행 예제 ... 244
        ⑷ 기수 정렬 실행 프로그램 ... 245
        ⑸ 기수 정렬 사용 공간 및 실행 시간 ... 247
      8. 힙 정렬(heap sort) ... 247
        ⑴ 정의 ... 247
        ⑵ 힙 정렬 알고리즘 ... 247
        ⑶ 힙 정렬 실행 예제 ... 249
        ⑷ 힙 정렬 실행 프로그램 ... 256
   5.2 외부 정렬(external sort) ... 257
      1. 다상 병합(polyphase merge) ... 257
        ⑴ 서브 파일의 분배 ... 258
      2. 균형 병합(balanced merge) ... 262
        ⑴ 균형 병합 알고리즘 ... 262
        ⑵ 균형 병합 운영 방식 ... 262
        ⑶ 균형 병합 수행 예제 ... 263
      3. 계단식 병합(cascade merge) ... 265
        ⑴ 알고리즘 ... 265
        ⑵ 수행의 예 ... 266
      4. 교대식 병합 정렬(oscillating sort merge) ... 268
   연습문제 ... 275
6장 탐색(Search)
        ⑴ 탐색의 종류 ... 280
        ⑵ 탐색 방법 ... 280
   6.1 비교 탐색(comparision method) ... 281
      1. 순차 탐색 ... 281
        ⑴ 선형 탐색의 평균 탐색 길이 ... 282
        ⑵ 비순서 파일인 경우의 순차 탐색 ... 282
        ⑶ 순서 파일인 경우의 순차 탐색 ... 284
        ⑷ 순차 탐색 프로그램 ... 284
      2. 제어 탐색(control search) ... 285
        ⑴ 이진 탐색(binary search) ... 285
        ⑵ 피보나치 탐색(fibonacci search) ... 287
        ⑶ 보간 탐색(interpolation search) ... 290
      3. 블록 탐색(block search) ... 293
        ⑴ 블록 탐색의 정의 ... 293
        ⑵ 블록 탐색 프로그래밍 ... 294
      4. 이진 트리 탐색(binary tree search) ... 295
        ⑴ 이진 트리 탐색 알고리즘 ... 295
      5. 기타 특수한 경우 ... 299
        ⑴ AVL(Adelson-Velskii & Landis) 트리 ... 299
        ⑵ B-tree(Balanced tree) ... 303
        ⑶ 트라이스 ... 306
   6.2 해싱(hashing) ... 307
      1. 해싱의 처리 방법 ... 307
        ⑴ 해싱 알고리즘 ... 308
      2. 해싱 함수의 종류 ... 311
        ⑴ 제산법(division) ... 311
        ⑵ 제곱법(mid-square) ... 312
        ⑶ 폴딩법(folding) ... 312
        ⑷ 기수 변환법(radix conversion) ... 313
        ⑸ 계수 분석법(digit analysis) ... 313
        ⑹ 대수적 코딩법(algebraic coding) ... 314
        ⑺ 무작위법(pseudo random) ... 315
      3. 오버플로우 처리 방법 ... 315
        ⑴ 선형 방법(linear) ... 315
        ⑵ 무작위 방법(random) ... 316
        ⑶ 2차 방법(quadratic) ... 317
        ⑷ 재해싱 방법(rehashing) ... 317
        ⑸ chaining 방법 ... 317
        ⑹ 오버플로우 공간 처리 방법 ... 317
      4. 해싱 프로그래밍 ... 318
      5. 탐색의 특징 ... 321
   연습문제 ... 322
7장 파일(File) 및 코드(Code)
   7.1 파일(file) ... 328
      1. 파일의 정의 ... 328
      2. 파일의 종류 ... 328
        ⑴ 파일의 분류 ... 328
        ⑵ 데이터 파일 ... 329
        ⑶ 작업 파일 ... 331
        ⑷ 프로그램 파일 ... 331
      3. 자기 테이프 장치 ... 333
        ⑴ 자기 테이프의 구성 ... 334
        ⑵ 자기 테이프의 레이블 ... 334
        ⑶ 자기 테이프의 볼륨(volume) ... 335
        ⑷ 자기테이프의 블록(block) ... 336
        ⑸ 레코드의 형식 ... 337
        ⑹ 용어 ... 339
      4. 자기 디스크 장치 ... 340
        ⑴ 자기 디스크의 구성 ... 341
        ⑵ 자기 디스크의 종류 ... 343
        ⑶ 자기 디스크의 자료 저장 형태 ... 343
        ⑷ 트랙 형식 ... 344
        ⑸ 시크 타임을 최소화 하는 방법 ... 345
      5. 파일 편성 방법 ... 346
        ⑴ 순차 파일(SAM) ... 346
      6. 색인 순차 파일(ISAM) ... 347
        ⑴ 기본 데이터영역(prime data area) ... 348
        ⑵ 인덱스 영역(index area) ... 348
        ⑶ 오버플로우 영역(overflow area) ... 348
      7. 직접 파일 (DAM) ... 351
        ⑴ 절대 주소 이용 ... 351
        ⑵ 상대 주소 이용 ... 351
        ⑶ 인덱스 테이블 이용 ... 351
      8. 다중 리스트 파일 ... 352
      9. 역파일 ... 353
   7.2 코드(code) ... 353
      1. 코드 설계 순서 ... 354
      2. 코드의 종류 ... 354
        ⑴ 순차 코드(sequence code) ... 354
        ⑵ 구분 코드(block code) ... 355
        ⑶ 집단 분류 코드(group classification code) ... 355
        ⑷ 10진 코드 (decimal code) ... 356
        ⑸ 유효 숫자 코드(significant digit code) ... 356
        ⑹ 문자형 코드(letter type code) ... 356
        ⑺ 기호 코드(mnemonic code) ... 357
      3. 코드 체크(code check)방법 ... 357
   연습문제 ... 359
8장 데이터베이스(Database)
   8.1 데이터베이스 구성 요소 ... 364
      1. 속성(attribute) ... 364
      2. 엔티티(entity) ... 364
      3. 관계성(relationship) ... 365
   8.2 데이터베이스의 목적 및 특성 ... 365
      1. 데이터의 독립성(data independence) ... 365
      2. 최소의 중복성 ... 365
      3. 데이터의 공유 ... 366
      4. 데이터의 보안 ... 366
      5. 데이터의 정확성 ... 366
   8.3 데이터베이스 시스템 구성 ... 366
   8.4 데이터베이스 언어 ... 369
      1. 데이터 정의어(DDL : Data Description Language) ... 369
      2. 데이터 조작어(DMC : Data Manipulation Language) ... 369
      3. 데이터 질의어(DQL : Data Query Language) ... 369
   8.5 DBMS(DataBase Management System) ... 370
   8.6 데이터 베이스 모형 ... 370
      1. 망 모형(Network Model) ... 370
      2. 계층 모형(Hierarchical model) ... 371
      3. 관계 모형(Relational model) ... 371
   8.7 데이터 베이스의 설계 단계 ... 372
      1. 요구 조건 분석 ... 373
      2. 개념적 석계 ... 373
      3. 논리적 설계 ... 372
      4. 물리적 설계 ... 374
   연습문제 ... 375
찾아보기 ... 378