목차
저자 서문 = ⅰ
역자 서문 = ⅸ
1장 기본 개념 = 1
1.1 개요 : 시스템 생명 주기 = 1
1.2 포인터와 동적 메모리 할당 = 4
1.2.1 포인터 = 4
1.2.2 동적 메모리 할당 = 6
1.2.3 포인터의 위험성 = 8
1.3 알고리즘 명세 = 8
1.3.1 개요 = 8
1.3.2 순환 알고리즘 = 14
1.4 데이타 추상화 = 19
1.5 성능 분석 = 23
1.5.1 공간 복잡도 = 24
1.5.2 시간 복잡도 = 27
1.5.3 점근 표기법(O, V, Q) = 36
1.5.4 실용적 복잡도 = 45
1.6 성능 측정 = 47
1.6.1 시간 측정 = 47
1.6.2 테스트 데이터의 생성 = 49
1.7 참고문헌 = 54
2장 배열과 구조 = 55
2.1 배열 = 55
2.1.1 추상 데이터 타입 = 55
2.1.2 C 언어에서의 배열 = 56
2.2 동적으로 할당된 배열 = 59
2.2.1 1차원 배열 = 59
2.2.2 2차원 배열 = 60
2.3 구조와 유니언 = 63
2.3.1 구조 = 63
2.3.2 유니언 = 66
2.3.3 구조의 내부 구현 = 67
2.3.4 자기 참조 구조 = 67
2.4 다항식 = 69
2.4.1 추상 데이타 타입 = 69
2.4.2 다항식 표현 = 71
2.4.3 다항식 덧셈 = 74
2.5 희소 행렬 = 77
2.5.1 추상 데이타 타입 = 77
2.5.2 희소 행렬 표현 = 79
2.5.3 행렬의 전치 = 80
2.5.4 행렬 곱셈 = 84
2.6 다차원 배열의 표현 = 90
2.7 스트링 = 92
2.7.1 추상 데이타 타입 = 92
2.7.2 C 에서의 스트링 = 93
2.7.3 패턴 매칭 = 97
2.8 참고문헌 = 104
2.9 추가 연습문제 = 105
3장 스택과 큐 = 113
3.1 스택 = 113
3.2 동적 배열을 사용하는 스택 = 118
3.3 큐 = 120
3.4 동적 할당 배열을 이용하는 원형 큐 = 127
3.5 미로 문제 = 129
3.6 수식의 계산 = 135
3.6.1 수식 = 135
3.6.2 후위 표기식의 연산 = 136
3.6.3 중위 표기에서 후위 표기로의 변환 = 141
3.7 다중 스택과 큐 = 146
3.8 추가 연습문제 = 150
4장 리스트 = 155
4.1 단순 연결 리스트 = 155
4.2 C 에서의 체인 표현 = 159
4.3 연결 스택과 큐 = 166
4.4 다항식 = 171
4.4.1 다항식의 표현 = 171
4.4.2 다항식의 덧셈 = 172
4.4.3 다항식의 삭제 = 176
4.4.4 다항식의 원형 리스트 표현 = 177
4.4.5 요약 = 180
4.5 추가 리스트 연산 = 181
4.5.1 체인 연산 = 181
4.5.2 원형 연결 리스트 연산 = 183
4.6 동치 부류 = 185
4.7 희소 행렬 = 190
4.7.1 희소행렬 표현 = 190
4.7.2 희소 행렬 입력 = 193
4.7.3 희소 행렬 출력 = 196
4.7.4 희소 행렬 삭제 = 197
4.8 이중 연결 리스트 = 199
5장 트리 = 205
5.1 개요 = 205
5.1.1 기본 용어 = 205
5.1.2 트리의 표현 = 208
5.2 이진 트리 = 212
5.2.1 추상 데이터 타입 = 212
5.2.2 이진 트리의 성질 = 214
5.2.3 이진 트리의 표현 = 217
5.3 이진 트리 순회 = 220
5.3.1 중위 순회 = 22l
5.3.2 전위 순회 = 222
5.3.3 후위 순회 = 223
5.3.4 반복적 중위 순회 = 223
5.3.5 레벨 순서 순회 = 224
5.3.6 스택 없는 순회 = 225
5.4 이진 트리의 추가 연산 = 226
5.4.1 이진 트리의 복사 = 226
5.4.2 동일성 검사 = 227
5.4.3 만족성 문제 = 227
5.5 스레드 이진 트리 = 232
5.5.1 스레드 = 232
5.5.2 스레드 이진 트리의 중위 순회 = 233
5.5.3 스레드 이진 트리에서의 노드 삽입 = 235
5.6 히프 = 237
5.6.1 우선순위 큐 = 237
5.6.2 최대 히프의 정의 = 239
5.6.3 최대 히프에서의 삽입 = 240
5.6.4 최대 히프에서의 삭제 = 242
5.7 이원 탐색 트리 = 245
5.7.1 정의 = 245
5.7.2 이원 탐색 트리의 탐색 = 246
5.7.3 이원 탐색 트리에서의 삽입 = 248
5.7.4 이원 탐색 트리에서의 삭제 = 249
5.7.5 이원 탐색 트리의 조인과 분할 = 250
5.7.6 이원 탐색 트리의 높이 = 253
5.8 선택 트리 = 255
5.8.1 개요 = 255
5.8.2 승자 트리 = 255
5.8.3 패자 트리 = 256
5.9 포리스트 = 259
5.9.1 포리스트를 이진 트리로 변환 = 259
5.9.2 포리스트 순회 = 260
5.10 분리 집합의 표현 = 262
5.10.1 개요 = 262
5.10.2 Union과 Find 연산 = 262
5.10.3 동치 부류의 응용 = 271
5.11 이진 트리의 개수 계산 = 274
5.11.1 상이한 이진 트리 = 274
5.11.2 스택 순열 = 274
5.11.3 행렬 곱셈 = 277
5.11.4 상이한 이진 트리의 수 = 278
5.12 참고문헌 = 280
6장 그래프 = 281
6.1 그래프 추상 데이터 타입 = 281
6.1.1 개요 = 281
6.1.2 정의 = 283
6.1.3 그래프 표현법 = 287
6.2 그래프의 기본 연산 = 295
6.2.1 깊이 우선 탐색 = 295
6.2.2 너비 우선 탐색 = 297
6.2.3 연결 요소 = 299
6.2.4 신장 트리 = 299
6.2.5 이중결합 요소 = 301
6.3 최소 비용 신장 트리 = 308
6.3.1 Kruskal 알고리즘 = 308
6.3.2 Prim 알고리즘 = 312
6.3.3 Sollin 알고리즘 = 313
6.4 최단 경로와 이행적 폐쇄 = 315
6.4.1 하나의 출발점／모든 목표점: 음이 아닌 간선 비용 = 316
6.4.2 하나의 출발점／모든 목표점: 일반적 가중치 = 319
6.4.3 모든 쌍의 최단 경로 = 324
6.4.4 이행적 폐쇄 = 325
6.5 작업 네트워크 = 331
6.5.1 AOV 네크워크 = 331
6.5.2 AOE 네트워크 = 338
6.6 참고문헌 = 346
6.7 추가 연습문제 = 347
7장 정렬 = 351
7.1 동기 = 351
7.2 삽입 정렬 = 355
7.3 퀵 정렬 = 358
7.4 얼마나 빠르게 정렬할 수 있는가 = 362
7.5 합병 정렬 = 364
7.5.1 합병 = 364
7.5.2 반복 합병 정렬 = 365
7.5.3 순환 합병 정렬 = 367
7.6 히프 정렬 = 371
7.7 여러 키에 의한 정렬 = 373
7.8 리스트와 테이블 정렬 = 380
7.9 내부 정렬 요약 = 389
7.10 외부 정렬 = 395
7.10.1 개요 = 395
7.10.2 k-원 합병 = 399
7.10.3 병렬 연산을 위한 버퍼 관리 = 400
7.10.4 런의 생성 = 407
7.10.5 런의 최적 합병 = 409
7.11 참고문헌 = 414
8장 해싱 = 415
8.1 개요 = 415
8.2 정적 해싱 = 415
8.2.1 해시 테이블 = 415
8.2.2 해시 함수 = 417
8.2.3 오버플로 처리 = 420
8.2.4 오버플로 기법의 이론적 평가 = 427
8.3 동적 해싱 = 431
8.3.1 동적 해싱의 동기 = 431
8.3.2 디렉터리를 사용하는 동적 해싱 = 431
8.3.3 디렉터리가 없는 동적 해싱 = 434
8.4 블룸 필터 = 437
8.4.1 응용-차등 화일 = 437
8.4.2 블룸 필터 설계 = 439
8.5 참고문헌 = 442
9장 우선순위 큐 = 443
9.1 한쪽 끝과 양쪽 끝 우선순위 큐 = 443
9.2 좌향 트리 = 445
9.2.1 높이 편향 좌향 트리 = 445
9.2.2 가중치 편향 좌향 트리 = 451
9.3 이항 히프 = 455
9.3.1 비용 상환 = 455
9.3.2 이항 히프의 정의 = 456
9.3.3 이항 히프에서의 삽입 = 457
9.3.4 두 이항 히프의 합병 = 458
9.3.5 최소 원소의 삭제 = 458
9.3.6 분석 = 460
9.4 피보나치 히프 = 463
9.4.1 정의 = 463
9.4.2 F-heap에서의 삭제 = 464
9.4.3 키-감소 = 465
9.4.4 연쇄 분리 = 465
9.4.5 분석 = 466
9.4.6 최단 경로 문제에 응용 = 469
9.5 페어링 히프 = 471
9.5.1 정의 = 471
9.5.2 합병과 삽입 = 472
9.5.3 키-감소 = 473
9.5.4 최소 삭제 = 475
9.5.5 임의 삭제 = 477
9.5.6 구현 고려 사항 = 478
9.5.7 복잡도 = 479
9.6 대칭 최소-최대 히프 = 480
9.6.1 정의와 성질 = 480
9.6.2 SMMH 표현 = 481
9.6.3 SMMH에서의 삽입 = 481
9.6.4. SMMH에서의 삭제 = 485
9.7 구간 히프 = 491
9.7.1 정의와 성질 = 491
9.7.2 구간 히프에서의 삽입 = 492
9.7.3 최소 원소 삭제 = 494
9.7.4 구간 히프의 초기화 = 496
9.7.5 구간 히프 연산의 복잡도 = 496
9.7.6 보완적 범위 탐색 문제 = 496
9.8 참고문헌 = 500
10장 효율적인 이원 탐색 트리 = 503
10.1 최적 이원 탐색 트리 = 503
10.2 AVL 트리 = 514
10.3 레드-블랙 트리 = 528
10.3.1 정의 = 528
10.3.2 레드-블랙 트리의 표현 = 531
10.3.3 레드-블랙 트리에서의 탐색 = 531
10.3.4 레드-블랙 트리에서의 삽입 = 531
10.3.5 레드-블랙 트리에서의 삭제 = 537
10.3.6 레드-블랙 트리의 조인 = 537
10.3.7 레드-블랙 트리의 분할 = 538
10.4 스플레이 트리 = 542
10.4.1 상향식 스플레이 트리 = 542
10.4.2 하향식 스플레이 트리 = 548
10.5 참고문헌 = 555
11장 다원 탐색 트리 = 557
11.1 m-원 탐색 트리 = 557
11.1.1 정의와 성질 = 557
11.1.2 m-원 탐색 트리에서의 탐색 = 559
11.2 B-트리 = 560
11.2.1 정의와 성질 = 560
11.2.2 B-트리의 원소 수 = 562
11.2.3 B-트리에서의 삽입 = 562
11.2.4 B-트리에서의 삭제 = 567
11.3 B◆U207A◆-트리 = 577
11.3.1 정의 = 577
11.3.2 B◆U207A◆-트리에서의 탐색 = 578
11.3.4 B◆U207A◆-트리에서의 삭제 = 581
11.4 참고문헌 = 586
12장 디지털 탐색 구조 = 587
12.1 디지털 탐색 트리 = 587
12.1.1 정의 = 587
12.1.2 탐색, 삽입, 삭제 = 587
12.2 이진 트라이와 패트리샤 = 588
12.2.1 이진 트라이 = 589
12.2.2 압축 이진 트라이 = 589
12.2.3 패트리샤 = 590
12.3 다원 트라이 = 596
12.3.1 정의 = 596
12.3.2 트라이에서의 탐색 = 599
12.3.3 샘플링 전략 = 600
12.3.4 트라이에서의 삽입 = 602
12.3.5 트라이에서의 삭제 = 602
12.3.6 상이한 길이의 키 = 603
12.3.7 트라이의 높이 = 604
12.3.8 필요 공간과 또 다른 노드 구조 = 604
12.3.9 접두 탐색과 응용 = 608
12.3.10 압축 트라이 = 609
12.3.11 생략 필드를 가진 압축 트라이 = 613
12.3.12 레이블 간선을 가진 압축 트라이 = 613
12.3.13 압축 트라이의 필요 공간 = 617
12.4 접미 트리 = 618
12.4.1 이 스트링을 본 적이 있는가 = 618
12.4.2 접미 트리 자료 구조 = 619
12.4.3 서브스트링 탐색(접미 트리 탐색) = 622
12.4.4 접미 트리의 응용 = 624
12.5 트라이와 인터넷 패킷 전송 = 626
12.5.1 IP 라우팅 = 626
12.5.2 1-비트 트라이 = 626
12.5.3 고정 스트라이드 트라이 = 628
12.5.4 가변 스트라이드 트라이 = 631
12.6 참고문헌 = 633
찾아보기 = 635
