머리말 ... xix
옮긴이 머리말 ... xxix
제1장 기본 개념 ... 1
   1.1 개요 : 시스템 생명 주기 ... 1
   1.2 객체 지향 설계 ... 5
      1.2.1 알고리즘적 분해와 객체지향적 분해 ... 5
      1.2.2 객체지향 프로그래밍의 기본적 정의와 개념 ... 5
      1.2.3 프로그래밍 언어의 발전과 C++의 역사 ... 6
   1.3 데이타 추상화와 캡슐화 ... 7
   1.4 C++의 기초 ... 13
      1.4.1 C++에서의 프로그램의 구성 ... 13
      1.4.2 C++에서의 영역(scope) ... 14
      1.4.3 C++명령문과 연산자 ... 16
      1.4.4 C++의 데이타 선언 ... 16
      1.4.5 C++의 주석문 ... 17
      1.4.6 C++에서의 입출력 ... 18
      1.4.7 C++의 함수 ... 20
      1.4.8 C++의 매개변수 전달 ... 21
      1.4.9 C++의 함수 이름 다중화 ... 22
      1.4.10 인라인 함수 ... 22
      1.4.11 C++의 동적 메모리 할당 ... 23
   1.5 알고리즘 명세 ... 24
      1.5.1 소개 ... 24
      1.5.2 순환 알고리즘 ... 30
   1.6 성능 분석과 측정 ... 36
      1.6.1 성능 분석 ... 36
      1.6.2 성능 측정 ... 62
      1.6.3 테스트 데이타의 생성 ... 70
   1.7 참고문헌 ... 75
제2장 배열 ... 77
   2.1 추상 데이타 타입과 C++ 클래스 ... 77
      2.1.1 C++ 클래스 개요 ... 77
      2.1.2 C++에서의 데이타 추상화와 캡슐화 ... 78
      2.1.3 클래스 객체의 선언과 멤버 함수의 기동 ... 79
      2.1.4 특수 클래스 연산 ... 80
      2.1.5 기타 내용 ... 84
      2.1.6 ADT와 C++클래스 ... 85
   2.2 추상 데이타 타입으로서의 배열 ... 87
   2.3 다항식 추상 데이타 타입 ... 90
      2.3.1 다항식 표현 ... 93
      2.3.2 다항식 덧셈 ... 96
      2.3.3 다항식을 배열로 표현하는 경우의 문제점 ... 98
   2.4 희소 행렬 ... 101
      2.4.1 개요 ... 101
      2.4.2 희소 행렬 표현 ... 103
      2.4.3 행렬의 전치 ... 105
      2.4.4 행렬 곱셈 ... 109
      2.4.5 희소 행렬을 배열로 표현하는 경우의 단점 ... 115
   2.5 배열의 표현 ... 117
   2.6 문자열 추상 데이타 타입 ... 121
      2.6.1 문자열 패턴 부합 : 간단한 알고리즘 ... 123
      2.6.2 문자열 패턴 부합 : 크누스-모리스-프라트 알고리즘 ... 124
   2.7 참고문헌 ... 130
   2.8 추가 연습문제 ... 130
제3장 스택과 큐 ... 139
   3.1 C++의 템플리트 ... 139
      3.1.1 템플리트 함수 ... 139
      3.1.2 템플리트를 이용한 컨테이너 클래스의 표현 ... 141
   3.2 스택 추상 데이타 타입 ... 153
   3.3 큐 추상 데이타 타입 ... 153
   3.4 C++의 서브타입과 계승 ... 160
   3.5 미로 문제 ... 165
   3.6 수식의 계산 ... 172
      3.6.1 수식 ... 172
      3.6.2 후위 표기식 ... 174
      3.6.3 중위 표기에서 후위 표기로의 변환 ... 176
   3.7 다중 스택과 큐 ... 180
   3.8 참고문헌 ... 185
   3.9 추가 연습문제 ... 185
제4장 연결 리스트 ... 189
   4.1 단순 연결 리스트 ... 189
   4.2 C++에서의 리스트 표현법 ... 194
      4.2.1 C++에서의 리스트 노드 정의 ... 194
      4.2.2 C++에서 리스트 설계 ... 195
      4.2.3 C++에서 포인터 조작 ... 200
      4.2.4 리스트 조작 연산 ... 201
   4.3 재사용 가능한 연결 리스트 클래스 ... 206
      4.3.1 템플리트를 이용한 연결 리스트 구현 ... 207
      4.3.2 연결 리스트 반복자 ... 208
      4.3.3 연결 리스트 연산 ... 213
      4.3.4 클래스의 재사용 ... 215
   4.4 원형 리스트 ... 216
   4.5 연결 스택과 큐 ... 219
   4.6 다항식 ... 223
      4.6.1 다항식의 단순 연결 리스트 표현 ... 223
      4.6.2 다항식의 덧셈 ... 225
      4.6.3 다항식의 제거 ... 229
      4.6.4 다항식의 원형 리스트 표현 ... 231
      4.6.5 요약 ... 235
   4.7 동치 관계 ... 237
   4.8 희소 행렬 ... 244
      4.8.1 희소 행렬 표현 ... 244
      4.8.2 희소 행렬 입력 ... 248
      4.8.3 희소 행렬 삭제 ... 250
   4.9 이중 연결 리스트 ... 255
   4.10 범용 리스트 ... 259
      4.10.1 범용 리스트의 표현 ... 259
      4.10.2 리스트를 위한 순환 알고리즘 ... 264
      14.10.3 참조 계수, 공유 순환 리스트 ... 269
   4.11 C++에서의 가상 함수와 동적 바인딩 ... 277
   4.12 이질 리스트 ... 282
   4.13 참고문헌 ... 287
제5장 트리 ... 289
   5.1 서론 ... 289
      5.1.1 기본 용어 ... 289
      5.1.2 트리의 표현 ... 292
   5.2 이진 트리 ... 296
      5.2.1 추상 데이타 타입 ... 296
      5.2.2 이진 트리의 특성 ... 298
      5.2.3 이진 트리의 표현 ... 301
   5.3 이진 트리 순회와 트리 반복자 ... 306
      5.3.1 개요 ... 306
      5.3.2 중위 순회 ... 306
      5.3.3 전위 순회 ... 308
      5.3.4 후위 순회 ... 309
      5.3.5 반복적 중위 순회 ... 310
      5.3.6 레벨 순서 순회 ... 313
      5.3.7 스택 없는 순회 ... 314
   5.4 이진 트리의 추가 연산 ... 317
      5.4.1 이진 트리의 복사 ... 317
      5.4.2 동일성 검사 ... 318
      5.4.3 만족성 문제 ... 319
   5.5 스레드 이진 트리 ... 324
      5.5.1 스레드 ... 324
      5.5.2 스레드 이진 트리의 중위 순회 ... 327
      5.5.3 스레드 이진 트리에서의 노드 삽입 ... 328
   5.6 히프 ... 331
      5.6.1 우선 순위 큐 ... 331
      5.6.2 취대 히프의 정의 ... 333
      5.6.3 최대 히프에서의 삽입 ... 335
      5.6.4 최대 히프에서의 삭제 ... 337
   5.7 이진 탐색 트리 ... 340
      5.7.1 정의 ... 340
      5.7.2 이진 탐색 트리의 탐색 ... 341
      5.7.3 이진 탐색 트리에 대한 삽입 ... 343
      5.7.4 이진 탐색 트리에서의 삭제 ... 345
      5.7.5 탐색 트리의 결합과 분할 ... 346
      5.7.6 이진 탐색 트리의 높이 ... 348
   5.8 선택 트리 ... 350
      5.8.1 소개 ... 350
      5.8.2 승자 트리 ... 350
      5.8.3 패자 트리 ... 352
   5.9 포리스트 ... 354
      5.9.1 포리스트의 이진 트리 변환 ... 355
      5.9.2 포리스트 순회 ... 356
   5.10 집합 표현 ... 357
      5.10.1 개요 ... 357
      5.10.2 합집합과 Find 연산 ... 358
      5.10.3 동치 부류의 응용 ... 368
   5.11 자료 구조의 객체 지향 시스템 ... 371
   5.12 이진 트리의 개수 계산 ... 376
      5.12.1 상이한 이진 트리 ... 376
      5.12.2 스택 순열 ... 377
      5.12.3 행렬 곱셈 ... 379
      5.12.4 상이한 이진 트리의 수 ... 381
   5.13 참고문헌 ... 382
제6장 그래프 ... 383
   6.1 그래프 추상 데이타 타입 ... 383
      6.1.1 개요 ... 383
      6.1.2 정의 ... 384
   6.2 기본적인 그래프 연산 ... 398
      6.2.1 깊이 우선 탐색 ... 399
      6.2.2 너비 우선 탐색 ... 401
      6.2.3 연결 요소 ... 402
      6.2.4 신장 트리 ... 403
      6.2.5 이중 결합 요소 ... 405
   6.3 최소 비용 신장 트리 ... 412
      6.3.1 Kruskal 알고리즘 ... 412
      6.3.2 Prim 알고리즘 ... 416
      6.3.3 Sollin 알고리즘 ... 417
   6.4 최단 경로와 이행적 폐쇄 ... 420
      6.4.1 단일 시발점 / 모든 종점 : 양수 간선 비용 ... 420
      6.4.2 단일 시발점 / 모든 종점 : 일반적인 가중치 ... 424
      6.4.3 모든 쌍의 최단 경로 ... 429
      6.4.4 이행적 폐쇄 ... 431
   6.5 작업 네트워크 ... 436
      6.5.1 AOV 네트워크 ... 436
      6.5.2 AOE 네트워크 ... 443
   6.6 참고문헌 ... 452
   6.7 추가 연습문제 ... 453
제7장 정렬 ... 457
   7.1 동기 ... 457
   7.2 삽입 정렬 ... 463
   7.3 퀵 정렬 ... 466
   7.4 얼마나 빠르게 정렬할 수 있는가 ... 471
   7.5 합병 정렬 ... 473
      7.5.1 합병 ... 473
      7.5.2 반복 합병 정렬 ... 479
      7.5.3 순환 합병 정렬 ... 482
   7.6 히프 정렬 ... 87
   7.7 여러 키에 의한 정렬 ... 491
   7.8 리스트와 테이블 정렬 ... 497
   7.9 내부 정렬의 요약 ... 507
   7.10 외부 정렬 ... 512
      7.10.1 서론 ... 512
      7.10.2 k-원 합병 ... 516
      7.10.3 병렬 연산을 위한 버퍼 관리 ... 518
      7.10.4 런의 생성 ... 525
      7.10.5 런의 최적 합병 ... 528
   7.11 참고문헌 ... 533
제8장 해싱 ... 535
   8.1 심벌 테이블 추상 데이터 타입 ... 535
   8.2 정적 해싱 ... 537
      8.2.1 해싱 테이블 ... 537
      8.2.2 해싱 함수 ... 539
      8.2.3 오버플로 처리 ... 543
      8.2.4 오버플로 처리 기법에 대한 이론적인 평가 ... 551
   8.3 동적 해싱 ... 555
      8.3.1 동적 해싱의 배경 ... 555
      8.3.2 디렉토리를 사용하는 동적 해싱 ... 556
      8.3.3 디렉토리를 사용하는 동적 해싱의 분석 ... 563
      8.3.4 디렉토리 없는 동적 해싱 ... 567
   8.4 참고문헌 ... 571
제9장 히프 구조 ... 575
   9.1 최소-최대 히프 ... 575
      9.1.1 정의 ... 575
      9.1.2 최소-최대 히프에 삽입 ... 578
      9.1.3 최소 원소의 삭제 ... 582
   9.2 디프 ... 586
      9.2.1 정의 ... 586
      9.2.2 디프에 삽입 ... 588
      9.2.3 최소 원소의 삭제 ... 591
   9.3 좌향 트리 ... 594
   9.4 이항 히프 ... 603
      9.4.1 비용 상환 ... 603
      9.4.2 이항 히프의 정의 ... 604
      9.4.3 이항 히프에 삽입 ... 607
      9.4.4 두 이항 히프의 결합 ... 607
      9.4.5 최소 원소의 삭제 ... 607
      9.4.6 분석 ... 610
   9.5 피보나치 히프 ... 613
      9.5.1 정의 ... 613
      9.5.2 F-히프에서의 삭제 ... 614
      9.5.3 키 감소 ... 615
      9.5.4 연쇄 분리 ... 615
      9.5.5 분석 ... 617
      9.5.6 최단 경로 문제에 대한 응용 ... 619
   9.6 참고문헌 ... 621
   9.7 추가 연습문제 ... 622
제10장 탐색 구조 ... 625
   10.1 최적 이진 탐색 트리 ... 625
   10.2 AVL 트리 ... 637
   10.3 2-3 트리 ... 654
      10.3.1 정의 및 특성 ... 654
      10.3.2 2-3 트리 탐색 ... 656
      10.3.3 2-3 트리에 삽입 ... 657
      10.3.4 2-3 트리에서의 삭제 ... 661
   10.4 2-3-4 트리 ... 669
      10.4.1 정의 및 특성 ... 669
      10.4.2 하향식 삽입 ... 672
      10.4.3 하향식 삭제 ... 676
   10.5 레드-블랙 트리 ... 679
      10.5.1 정의와 특성 ... 679
      10.5.2 레드-블랙 트리의 탐색 ... 682
      10.5.3 하향식 삽입 ... 682
      10.5.4 상향식 삽입 ... 686
      10.5.5 레드-블랙 트리에서 삭제 ... 687
      10.5.6 레드-블랙 트리의 결합과 분열 ... 689
   10.6 B-트리 ... 694
      10.6.1 m-원 탐색 트리의 정의 ... 694
      10.6.2 m-원 탐색 트리의 탐색 ... 696
      10.6.3 B-트리의 정의와 특성 ... 696
      10.6.4 B-트리의 삽입 ... 700
      10.6.5 B-트리의 삭제 ... 704
      10.6.6 가변 크기의 키 값 ... 708
   10.7 스플레이 트리 ... 712
   10.8 디지탈 탐색 트리 ... 719
      10.8.1 정의 ... 719
      10.8.2 이진 트라이 ... 721
      10.8.3 패트리샤 ... 722
   10.9 트라이 ... 729
      10.9.1 정의 ... 729
      10.9.2 트라이 탐색 ... 730
      10.9.3 샘플링 전략 ... 731
      10.9.4 트라이의 삽입 ... 734
      10.9.5 트라이의 삭제 ... 734
      10.9.6 노드 구조 ... 735
   10.10 차등 화일 ... 737
      10.10.1 개념 ... 737
      10.10.2 블룸 필터 ... 739
   10.11 참고문헌 ... 742
찾아보기 ... 745