[중국에서 온 다이렉트 메일] I READING Computer Science Series·Data Structure, Algorithms and Application: C++ Language Description (원서 2판)

편집자의 선택

권위 있는 데이터 구조 교과서의 두 번째 판입니다.
기본 데이터 구조를 완벽하게 다루며 CS2 과정에 이상적인 책입니다.

간략한 소개

"데이터 구조, 알고리즘 및 응용 - C++ 언어 설명"은 권위 있는 데이터 구조 교과서의 제2판입니다. 기본 데이터 구조를 완벽하게 다루며 CS2 과정에 이상적인 책입니다. 저자 Sartaj Sahni는 단계별 설명과 직관적이고 구체적인 토론, 실제 적용을 통해 독자가 쉽고 즐겁게 학습할 수 있도록 합니다. 이 책의 새 판은 표준 템플릿 라이브러리(STL)의 사용에 중점을 두고 책에서 개발된 데이터 구조와 알고리즘을 해당 STL 구현 방법과 연관시킵니다. 이 책에는 또한 많은 새로운 예제와 연습 문제가 추가되었습니다.
책에 실린 응용 사례는 그 특징이다. Sahni 박사는 정렬, 압축 코딩 및 이미지 처리와 같은 측면을 포함하여 각 데이터 구조 및 알고리즘에 대한 여러 응용 사례를 제공합니다. 이러한 예는 개념과 적용을 결합하고 이론과 실습을 통합하여 개념을 쉽게 이해할 수 있게 만들고 학습에 대한 학생들의 동기와 관심을 높입니다.
"컴퓨터 과학 시리즈·데이터 구조, 알고리즘 및 응용: C++ 언어 설명(원서 제2판)"에서 채택한 실용적인 교수법은 이론 개념을 풍부하게 할 뿐만 아니라 학생들에게 실습할 수 있는 많은 연습 문제를 제공합니다. 책에 있는 800개의 연습 문제) 이해력 문제와 간단한 프로그래밍 및 엔지니어링 설계 문제를 포함한 다양한 연습 문제. 또한 책과 함께 제공되는 웹사이트에는 책에 담긴 모든 프로그램, 샘플 데이터, 실행 결과, 일부 연습에 대한 솔루션, 결과가 포함된 샘플 테스트가 포함되어 있습니다.

저자 소개

사르타즈 사흐니 , 플로리다 대학 컴퓨터 및 정보 과학 공학 석좌 교수, 유럽 과학 아카데미 회원, 전기 전자 공학 협회(IEEE), 컴퓨터 기계 협회(ACM), 미국 협회 회원 AAAS(진흥 발전) 및 미네소타 슈퍼컴퓨팅 연구소(Minnesota Supercomputing Institute), Kan Distinguished Alumni of Indian Institute of Technology, Purpur(LIT). Sahni 박사는 1997년에 IEEE 컴퓨터 부문의 Taylor L Booth 교육상을, IEEE 컴퓨터 부문의 W. Wallace McDowell Award 및 2003 ACM Karl Karlstrom 우수 교육자 상. 그는 현재 ACM "Computing Surveys" 저널의 편집장을 맡고 있으며 17개 저널의 편집 위원회 회원입니다. 그는 인도 칸푸르 공과대학교에서 전기공학 학사학위, 코넬대학교에서 컴퓨터공학 석사 및 박사학위를 취득했으며, 250편 이상의 논문을 발표하고 15권의 교과서를 집필했으며, 효율적인 알고리즘 분야에 대한 연구 성과도 있습니다. 설계 및 분석, 병렬 컴퓨팅, 인터넷, 자동화 설계 및 의료 알고리즘.

목차

C++의 데이터 구조, 알고리즘 및 응용 프로그램 제2판
출판사 메모
번역가의 서문
머리말
1부 예비 지식
1장 C++ 검토
1.1 소개
1.2 기능 및 매개변수
1.2.1 값 매개변수 전달하기
1.2.2 템플릿 기능
1.2.3 참조 매개변수
1.2.4 상수 참조 매개변수
1.2.5 반환 값
1.2.6 오버로드된 함수
1.3 예외
1.3.1 예외 발생
1.3.2 예외 처리
1.4 동적 저장 공간 할당
1.4.1 연산자 신규
1.4.2 1차원 배열
1.4.3 예외 처리
1.4.4 운영자 삭제
1.4.5 2차원 배열
1.5 자신의 데이터 유형
1.5.1 클래스 화폐
1.5.2 다른 설명 방식
1.5.3 연산자 오버로딩
1.5.4 친구 및 보호계급 구성원
1.5.5 #ifndef, #define 및 #endif 문 추가
1.6 예외 클래스 불법ParameterValue
1.7 재귀 함수
1.7.1 재귀 수학 함수
1.7.2 요약
1.7.3 C++ 재귀 함수
1.8 표준 템플릿 라이브러리
1.9 테스트와 디버깅
1.9.1 테스트란 무엇인가
1.9.2 테스트 데이터의 설계
1.9.3 디버깅
1.10 참고문헌 및 추천도서
제2장 프로그램 성과 분석
2.1 프로그램 성과란 무엇인가
2.2 공간 복잡도
2.2.1 공간복잡도의 구성요소
2.2.2 예
2.3 시간 복잡도
2.3.1 시간복잡도의 구성요소
2.3.2 작업 횟수
2.3.3 최고, 최악, 평균 작업 횟수
2.3.4 단계 수
3장 점근 표기법
3.1 소개
3.2 점근적 표기법
3.2.1 빅Ο 표기법
3.2.2 점근적 표기법 Ω 및 Θ
3.3 점근 수학(선택 사항)
3.3.1 빅오 표기법
3.3.2 Ω 표기
3.3.3 Θ 표기법
3.3.4 작은 ο 표기법
3.3.5 특징
3.4 복잡성 분석의 예
3.5 실제 복잡성
3.6 참고문헌 및 추천도서
제4장 성과측정
4.1 소개
4.2 인스턴스 크기 선택
4.3 설계 시험 데이터
4.4 실험 설계
4.5 캐싱
4.5.1 간단한 컴퓨터 모델
4.5.2 캐시 누락이 실행 시간에 미치는 영향
4.5.3 행렬 곱셈
4.6 참고문헌 및 추천도서

2부 데이터 구조
5장 선형 테이블 - 배열 설명
5.1 데이터 객체와 데이터 구조
5.2 선형 테이블 데이터 구조
5.2.1 추상 데이터 유형 LinearList
5.2.2 추상 클래스 선형리스트
5.3 어레이 설명
5.3.1 설명
5.3.2 가변 길이 1차원 배열
5.3.3 클래스 arrayList
5.3.4 C++ 반복자
5.3.5 arrayList의 반복자
5.4 벡터 설명
5.5 배열로 구현된 여러 테이블
5.6 성능 측정
5.7 참고문헌 및 추천 도서
6장 선형 테이블 - 연결된 설명
6.1 단방향 연결리스트
6.1.1 설명
6.1.2 구조 chainNode
6.1.3 클래스 체인
6.1.4 추상 데이터 유형 LinearList의 확장
6.1.5 ExtendedChain 클래스
6.1.6 성능 측정
6.2 순환 연결 리스트와 헤드 노드
6.3 이중 연결 리스트
6.4 연결리스트에 사용되는 어휘
6.5 적용
6.5.1 상자 분류
6.5.2 기수 정렬
6.5.3 볼록 껍질
6.5.4 연합 검색
7장 배열과 행렬
7.1 배열
7.1.1 추상 데이터 유형
7.1.2 C++ 배열 인덱싱
7.1.3 행 주요 매핑과 열 주요 매핑
7.1.4 배열의 배열 사용 설명
7.1.5 행 마스터 설명 및 열 마스터 설명
7.1.6 불규칙한 2차원 배열
7.2 매트릭스
7.2.1 정의 및 작동
7.2.2 클래스 매트릭스
7.3 특수 행렬
7.3.1 정의 및 적용
7.3.2 대각선 행렬
7.3.3 삼중대각 행렬
7.3.4 삼각행렬
7.3.5 대칭행렬
7.4 희소 행렬
7.4.1 기본 개념
7.4.2 단일 선형 테이블로 설명
7.4.3 여러 선형 테이블을 사용하여 설명
7.4.4 성능 측정
8장 스택
8.1 정의 및 적용
8.2 추상 데이터 유형
8.3 어레이 설명
8.3.1 파생 클래스로 구현
8.3.2 arrayStack 클래스
8.3.3 성능 측정
8.4 연결리스트 설명
8.4.1 클래스 파생LinkedStack
8.4.2 linkedStack 클래스
8.4.3 성능 측정
8.5 적용
8.5.1 브래킷 매칭
8.5.2 하노이 타워
8.5.3 열차 객차 재배치
8.5.4 스위치 박스 배선
8.5.5 오프라인 동등 클래스 문제
8.5.6 미로쥐
8.6 참고문헌 및 추천도서
9장 대기열
9.1 정의 및 적용
9.2 추상 데이터 유형
9.3 배열 설명
9.3.1 설명
9.3.2 클래스 arrayQueue
9.4 연결리스트 설명
9.5 적용
9.5.1 열차 객차 재배치
9.5.2 회로 배선
9.5.3 그래프 요소 인식
9.5.4 공장 시뮬레이션
9.6 참고문헌 및 추천도서
10장 점프 목록과 해싱
10.1 사전
10.2 추상 데이터 유형
10.3 선형 테이블 설명
10.4 점프 테이블 표현(선택 사항)
10.4.1 이상적인 상황
10.4.2 삽입과 삭제
10.4.3 레벨 할당
10.4.4 SkipNode 구조
10.4.5 클래스 SkipList
10.4.6 SkipList 메소드의 복잡성
10.5 해시 테이블 설명
10.5.1 이상적인 해싱
10.5.2 해시 함수와 해시 테이블
10.5.3 선형 탐색
10.5.4 체인 해싱
10.6 애플리케이션 - 텍스트 압축
10.6.1 LZW 압축
10.6.2 LZW 압축 구현
10.6.3 LZW 압축해제
10.6.4 LZW 압축해제 구현
10.6.5 성과평가
10.7 참고문헌 및 추천 도서
11장 이진 트리와 기타 트리
11.1 트리
11.2 이진 트리
11.3 이진 트리의 속성
11.4 이진 트리 설명
11.4.1 배열 설명
11.4.2 연결리스트 설명
11.5 이진 트리의 일반적인 연산
11.6 이진 트리 순회
11.7 추상 데이터 유형 BinaryTree
11.8 클래스 linkedBinaryTree
11.9 적용
11.9.1 신호 증폭기 설정
11.9.2 연합 검색
11.10 참고문헌 및 추천도서
12장 우선순위 큐
12.1 정의와 적용
12.2 추상 데이터 유형
12.3 선형 테이블
12.4 힙
12.4.1 정의
12.4.2 큰 루트 힙 삽입
12.4.3 큰 루트 힙 삭제
12.4.4 대규모 루트 힙 초기화
12.4.5 클래스 maxHeap
12.4.6 힙과 STL
12.5 주오 가오슈
12.5.1 높이 우선, 너비 우선 최대 및 최소 왼쪽 높이 트리
12.5.2 최대 HBLT 삽입
12.5.3 최대 HBLT의 삭제
12.5.4 두 개의 가장 큰 HBLT 합병
12.5.5 초기화
12.5.6 클래스 maxHblt
12.6 적용
12.6.1 힙 정렬
12.6.2 기계 스케줄링
12.6.3 허프만 코딩
12.7 참고문헌 및 추천도서
13장 경쟁 트리
13.1 승자 트리 및 애플리케이션
13.2 추상 데이터 유형 WinnerTree
13.3 승자 트리 구현
13.3.1 표현
13.3.2 위너 트리 초기화
13.3.3 대회 재편성
13.3.4 클래스 완료WinnerTree
13.4 패자나무
13.5 적용
13.5.1 첫 번째 맞춤 방법을 사용하여 상자 적재 문제 해결
13.5.2 이웃 적응 방법을 이용한 박스 로딩 문제 해결
13.6 참고문헌 및 추천도서
14장 검색 트리
14.1 정의
14.1.1 이진 검색 트리
14.1.2 이진 검색 트리 인덱싱
14.2 추상 데이터 유형
14.3 이진 검색 트리의 동작과 구현
14.3.1 클래스 BinarySearchTree
14.3.2 검색
14.3.3 삽입
14.3.4 삭제
14.3.5 이진 검색 트리의 높이
14.4 동일한 키워드를 가진 요소가 있는 이진 검색 트리
14.5 이진 검색 트리 인덱싱
14.6 적용
14.6.1 히스토그램
14.6.2 상자 적재 문제에 대한 최적 매칭 방법
14.6.3 교차 배포
15장 검색 트리 균형 조정
15.1 AVL 트리
15.1.1 정의
15.1.2 AVL 트리의 높이
15.1.3 AVL 트리 설명
15.1.4 AVL 검색 트리 검색
15.1.5 AVL 검색 트리 삽입
15.1.6 AVL 검색 트리 삭제
15.2 레드-블랙 트리
15.2.1 기본 개념
15.2.2 레드-블랙 트리에 대한 설명
15.2.3 레드-블랙 트리 탐색
15.2.4 레드-블랙 트리 삽입
15.2.5 레드-블랙 트리 삭제
15.2.6 구현 세부 사항 고려 및 복잡성 분석
15.3 트리 분할
15.3.1 소개
15.3.2 분할 트리 작업
15.3.3 변환 복잡성
15.4 B-트리
15.4.1 인덱스 순차 접근 방식
15.4.2 m진 검색 트리
15.4.3 차수 m의 B-트리
15.4.4 B-트리 높이
15.4.5 B-트리 검색
15.4.6 B-트리 삽입
15.4.7 B-트리 삭제
15.4.8 노드 구조
15.5 참고문헌 및 추천도서
16장 그림
16.1 기본 개념
16.2 응용 프로그램 및 기타 개념
16.3 특징
16.4 추상 데이터 유형 그래프
16.5 비가중 그래프 설명
16.5.1 인접 행렬
16.5.2 인접 연결 리스트
16.5.3 인접 배열
16.6 가중치 그래프 설명
16.7 클래스 구현
16.7.1 다양한 클래스
16.7.2 인접 행렬 클래스
16.7.3 체인 클래스 확장
16.7.4 연결리스트 클래스
16.8 그래프 순회
16.8.1 너비 우선 탐색
16.8.2 너비우선탐색 구현
16.8.3 방법 그래프::bfs의 복잡성 분석
16.8.4 깊이 우선 탐색
16.8.5 깊이 우선 탐색의 구현
16.8.6 메소드 그래프::dfs의 복잡성 분석
16.9 적용
16.9.1 경로 찾기
16.9.2 연결그래프와 그 구성
16.9.3 스패닝 트리

3부 알고리즘 설계 방법
17장 탐욕 알고리즘
17.1 최적화 문제
17.2 그리디 알고리즘의 개념
17.3 적용
17.3.1 컨테이너 적재
17.3.2 0/1 배낭 문제
17.3.3 위상 정렬
17.3.4 양측 적용 범위
17.3.5 단일 소스 최단 경로
17.3.6 최소 비용 신장 트리
17.4 참고문헌 및 추천도서
제18장 분열과 정복
18.1 알고리즘적 사고
18.2 적용
18.2.1 불완전한 체스판
18.2.2 병합 정렬
18.2.3 퀵 정렬
18.2.4 선택
18.2.5 가장 가까운 점 쌍
18.3 재귀 방정식 풀기
18.4 복잡성의 하한
18.4.1 최소최대 문제의 하한
18.4.2 정렬 알고리즘의 하한
19장 동적 프로그래밍
19.1 알고리즘적 사고
19.2 적용
19.2.1 0/1 배낭 문제
19.2.2 행렬 곱셈 체인
19.2.3 모든 정점 쌍 사이의 최단 경로
19.2.4 음수 값을 갖는 단일 소스 최단 경로
19.2.5 네트 그룹의 교차점이 없는 하위 집합
19.3 참고문헌과 추천도서
20장 역추적
20.1 알고리즘적 사고
20.2 적용
20.2.1 컨테이너 적재
20.2.2 0/1 배낭 문제
20.2.3 최대 완전 하위 그래프
20.2.4 여행하는 세일즈맨 문제
20.2.5 회로 기판 배열
21장 분기와 구분
21.1 알고리즘적 사고
21.2 적용
21.2.1 컨테이너 적재
21.2.2 0/1 배낭 문제
21.2.3 최대 완전 하위 그래프
21.2.4 여행하는 세일즈맨 문제
21.2.5 회로 기판 배열

서문/서문

C++의 데이터 구조, 알고리즘 및 응용 프로그램 제2판 데이터 구조 및 알고리즘에 대한 연구는 컴퓨터 과학 및 엔지니어링의 기초입니다. 이 분야의 숙련도는 컴퓨터 자원을 효율적으로 활용하는 프로그램을 개발하는 데 필수적입니다. 따라서 모든 컴퓨터 과학 및 공학 전공에는 이 측면에 전념하는 하나 이상의 과정이 있습니다. 일반적으로 첫 번째 프로그래밍 과정에서는 데이터 구조와 알고리즘(데이터 구조의 스택 및 큐, 알고리즘 정렬 및 행렬 연산)의 기본 사항을 소개합니다. 두 번째 프로그래밍 과정에서는 데이터 구조와 알고리즘에 대한 체계적인 지식을 소개합니다. 그 다음에는 데이터 구조와 알고리즘에 대한 심층적인 연구가 이어질 수 있으며, 일반적으로 한두 과정이 필요합니다.
컴퓨터 과학 및 공학 학부 전공이 너무 많아 많은 대학에서 과정을 통합해야 했습니다. 예를 들어, 플로리다 대학에서는 학부생에게 데이터 구조 및 알고리즘에 대한 한 학기 강좌만 제공됩니다. 이 과정을 수강하기 전에 학생들은 한 학기 동안 Java 프로그래밍과 이산 수학을 공부해야 합니다.
이 책은 데이터 구조와 알고리즘을 전문으로 하는 두 개 이상의 강좌 또는 관련 종합 강좌에서 사용할 수 있습니다. 책은 세 부분으로 나누어져 있다. 1장부터 4장까지의 첫 번째 부분에서는 C++ 프로그래밍의 개념을 검토하고 프로그램 성능을 분석하고 측정하는 방법을 설명합니다. C 언어 프로그래밍에 익숙한 학생들은 1장을 공부하면 C++로 전환할 수 있을 것입니다. 1장은 C++에 대한 입문 지식은 아니지만 매개변수 전달, 템플릿 함수, 동적 저장소 할당, 재귀, 클래스, 상속, 예외 발생 및 캡처와 같이 학생들에게 종종 혼동을 주는 C++의 몇 가지 기본 개념을 포함하고 있습니다. 2장과 3장에서는 프로그램 성능을 분석하고 측정하는 방법(연산 계산, 실행 단계 및 점근 표기법(큰 O, Ω, Θ, 작은 o))을 검토합니다. 4장에서는 프로그램 성능에 대한 실험적 측정을 검토하고 캐시 메모리가 런타임 측정에 미치는 영향을 간략하게 논의합니다. 2장에서는 프로그램 성능 분석 방법인 단순 정렬 ​​알고리즘(버블 정렬, 선택 정렬, 삽입 정렬, 카운팅 정렬), 순차 검색, 호너의 법칙을 활용하여 프로그래밍 입문 과정에서 접하는 일반적인 기본 알고리즘에 대해 심층적으로 연구합니다. 다항식 평가 및 행렬 연산(행렬 추가, 행렬 전치, 행렬 곱셈)을 수행합니다. 3장에서는 이진 검색 알고리즘을 연구합니다. 2장부터 4장까지의 주요 목적은 프로그램 성능을 분석하고 측정하는 방법을 배우는 것이지만 학생들에게 일련의 기본 알고리즘에 대한 숙련도를 제공합니다.
이 책의 두 번째 부분인 5장부터 16장까지는 데이터 구조에 대한 심층적인 연구를 제공합니다. 5장과 6장에서는 각각 데이터의 배열 기술 방법과 포인터(또는 체인) 기술 방법을 연구하여 데이터 구조 연구의 틀을 구축한다. 이 두 장에서는 이 두 가지 데이터 설명 방법을 사용하여 선형 테이블 데이터 구조를 설명하는 C++ 클래스를 만듭니다. 선형 테이블을 기술할 때 다양한 데이터 기술 방법의 성능을 비교하기 위해 실험 데이터를 사용했습니다. 7장 이후의 두 번째 부분에서는 5장과 6장의 설명 방법을 적용하여 배열과 행렬(7장), 스택(8장), 큐(9장) 등 다른 데이터 구조를 설명합니다. 10장, 14장, 15장), 이진 트리(11장), 우선순위 대기열(12장), 경주 트리(15장), 그래프(16장).
이 책은 데이터 구조를 다룰 때 유사성이나 동일성 측면에서 C++ 표준 템플릿 라이브러리(STL)에서 사용하는 구조와 호환되도록 시도합니다. 예를 들어, 5장의 선형 테이블 데이터 구조는 STL의 벡터형 패턴에 따라 구축되었습니다. 이 책에서는 copy, min, max 등의 STL 함수를 사용하여 학생들이 이러한 함수에 익숙해질 수 있도록 합니다.
이 책의 세 번째 부분인 17장부터 21장까지는 일반적으로 사용되는 알고리즘 설계 방법을 연구합니다. 이러한 방법에는 탐욕 알고리즘(17장), 분할 정복 알고리즘(18장), 동적 프로그래밍(19장), 역추적 알고리즘(20장) 및 분기 및 경계 알고리즘(21장)이 포함됩니다. 또한 두 개의 하한(최소최대 문제 및 정렬 문제)(18.4절), 기계 스케줄링을 위한 근사 알고리즘(12.6.2절), 상자 로딩 알고리즘(13.5절) 및 0/1 배낭 문제(17.3.2 축제)에 대한 증명도 포함되어 있습니다. ). 섹션 12.6.2에서는 또한 NP-복합체 문제를 간략하게 소개합니다.
이 책의 특징은 적용에 중점을 두고 있다는 점이다. 책에 나오는 각 데이터 구조와 알고리즘 설계는 여러 응용 사례를 통해 시연됩니다. 일반적으로 각 장의 마지막 섹션에서는 이 장에 소개된 데이터 구조 또는 설계 방법에 대한 특정 응용 프로그램을 제공합니다. 많은 경우 응용 사례가 장의 앞부분에 포함되어 있습니다. 이러한 응용 사례에는 정렬(버블 정렬, 선택 정렬, 삽입 정렬, 계산 정렬, 힙 정렬, 병합 정렬, 퀵 정렬, 상자 정렬, 기수 정렬 및 위상 정렬), 행렬 연산(행렬 추가, 행렬 전치, 행렬) 등 다양한 측면이 포함됩니다. 곱셈), 회로 설계 자동화(회로망 그룹 검색, 회로 배선, 부품 접기, 스위치 박스 배선, 신호 증폭기 설정, 교차 분배, 회로 기판 배열), 압축 코딩(LZW 압축, 허프만 코딩), 계산 기하학(볼록 외피 및 가장 가까운 점 쌍), 시뮬레이션(공장 시뮬레이션), 이미지 처리(그래프 요소 주석), 흥미로운 수학(하노이 타워, 불완전한 체스판, 미로 마우스), 스케줄링(LPT 스케줄링), 최적화(빈 패킹 문제), 컨테이너 로딩, 0 /1 배낭, 행렬 곱셈 체인), 통계(히스토그램, 최대값과 최소값 찾기, k번째 최소값 찾기), 그래프 이론(스패닝 트리, 프리미티브, 최단 경로, 최대 완전 하위 그림, 이분 범위 및 여행하는 세일즈맨) . 이러한 응용 사례를 공부하는 데에는 학생들이 관련 분야에 대한 사전 지식이 필요하지 않습니다. 왜냐하면 이러한 지식이 책에 포함되어 있고, 이러한 지식이 학생들의 학습에 대한 흥미를 높여주기 때문입니다.
우리는 실제 응용과 데이터 구조 및 알고리즘 설계 방법에 대한 기초 연구를 긴밀하게 통합함으로써 학생들의 전문적인 관심을 더욱 자극할 수 있기를 바랍니다. 이 책과 이 책의 웹사이트에 나와 있는 800개 이상의 연습문제를 완성함으로써 학생들의 지식은 더욱 풍부해지고 탄탄해질 것이다.