C++로 쉽게 풀어쓴 자료구조

CHAPTER 01 자료구조와 알고리즘
1.1 자료구조
자료구조란?
자료구조의 분류
1.2 알고리즘
알고리즘이란?
프로그램 = 자료구조 + 알고리즘
알고리즘 기술 방법
1.3 추상 자료형
추상화란?
추상 자료형이란?
추상 자료형과 C++
1.4 알고리즘의 성능 분석
실행 시간 측정 방법
알고리즘의 복잡도 분석 방법
시간 복잡도 함수
빅오 표기법
빅오 표기법 이외의 표기법
최선, 평균, 최악의 경우
1.5 자료구조 표기법
ADT ? Class Diagram ? C++
UML Diagram
C++
표준 템플릿 라이브러리(STL)
연습문제
프로그래밍 프로젝트

CHAPTER 02 배열과 클래스
2.1 배열
배열의 개념
배열의 추상 자료형
1차원 배열
2차원 배열
함수의 파라미터로서의 배열
2.2 클래스
구조체의 개념
클래스와 C++ 문법
교재에서 거의 사용하지 않는 C++ 문법
2.3 배열과 클래스의 응용: 다항식 프로그램
다항식의 추상 자료형
다항식의 표현 방법
다항식 프로그램의 구현
희소 다항식의 표현
연습문제
프로그래밍 프로젝트

CHAPTER 03 스택
3.1 스택의 추상 자료형
스택이란?
스택의 추상 자료형
스택의 활용 예
스택의 구현 방법
3.2 스택의 구현
배열을 이용한 스택의 표현
배열을 이용한 스택의 구현
복잡한 구조의 항목에 대한 스택의 구현
연결 리스트를 이용한 스택
3.3 스택의 응용: 괄호 검사
괄호 검사와 스택
괄호 검사 알고리즘
괄호 검사 프로그램 구현
3.4 스택의 응용: 수식의 계산
수식의 계산과 스택
후위 표기 수식의 계산
후위 표기 수식 계산 프로그램 구현
중위 표기 수식의 후위 표기 변환 알고리즘
중위 표기 수식의 후위 표기 변환 프로그램 구현
3.5 미로 탐색 문제와 표준템플릿 라이브러리(STL)
미로 탐색 문제
미로 탐색 알고리즘
표준 템플릿 라이브러리(STL)
STL을 이용한 미로 탐색 프로그램 구현
연습문제
프로그래밍 프로젝트

CHAPTER 04 큐
4.1 큐의 추상 자료형
큐(Queue)란?
큐의 추상 자료형
큐의 활용
4.2 큐의 구현
선형 큐
원형 큐
삽입과 삭제 알고리즘
원형 큐의 구현
연결 리스트로 구현한 큐
4.3 덱
덱의 소개
덱 추상 자료형
배열을 이용한 원형 덱의 구현
연결된 덱의 구현
4.4 큐의 응용: 은행 시뮬레이션
시뮬레이션
은행 서비스 시뮬레이션 문제
4.5 덱의 응용: 미로 탐색 프로그램
깊이 우선 탐색과 너비 우선 탐색
STL의 큐를 이용한 미로 탐색
STL의 덱을 이용한 DFS 탐색
STL의 덱을 이용한 BFS 탐색
연습문제
프로그래밍 프로젝트

CHAPTER 05 포인터와 연결 리스트
5.1 포인터
포인터의 개념
함수와 포인터
배열과 포인터
객체와 포인터
자체 참조 클래스
함수 포인터
포인터에 대한 연산
포인터 사용 시 주의점
5.2 동적 메모리 할당
동적 메모리 할당의 개념
동적 메모리 할당과 해제를 위한 연산자
2차원 배열의 동적 할당
5.3 연결 리스트
연결 리스트란?
연결 리스트의 구조
연결 리스트의 종류
5.4 연결 리스트로 구현한 스택
연결 리스트로 구현한 스택의 구조
연결된 스택의 동작
연결 리스트로 구현한 스택: 학생 정보 스택
5.5 포인터의 응용: 연결 리스트로 구현한 큐
연결 리스트로 구현한 큐의 구조
연결된 큐의 연산
연결된 큐의 구현
복잡한 구조 항목에 대한 연결된 큐 구현: 학생 정보 큐
연습문제
프로그래밍 프로젝트

CHAPTER 06 리스트
6.1 리스트 추상 자료형
리스트란?
리스트의 추상 자료형
6.2 배열로 구현한 리스트
데이터 멤버
주요 연산
배열을 이용한 리스트 구현
6.3 연결 리스트로 구현된 리스트
연결 리스트로 구현된 리스트
시작 노드 표현 방법: 헤드 포인터와 헤드 노드
단순 연결 리스트를 이용한 리스트의 구현
6.4 다양한 형태의 연결 리스트
원형 연결 리스트(circular linked list)
이중 연결 리스트(doubly linked list)
이중 연결 리스트로 구현된 리스트
이중 연결 리스트로 구현한 덱
6.5 연결 리스트의 응용: 라인 편집기
라인 편집기란?
라인 편집기의 구현
연습문제
프로그래밍 프로젝트

CHAPTER 07 순환
7.1 순환의 소개
순환이란?
순환 호출의 내부적인 구현
순환 알고리즘의 구조
순환↔반복
순환의 원리
순환 알고리즘의 성능
7.2 거듭제곱 값 계산
7.3 피보나치수열의 계산
7.4 하노이 탑 문제
반복적인 형태로 바꾸기 어려운 순환
7.5 다중 순환
다중 순환이란?
영역 채색 문제
미로 탐색 문제
연습문제
프로그래밍 프로젝트

CHAPTER 08 트리
8.1 트리의 개념
트리의 용어들
트리의 표현
8.2 이진트리 소개
이진트리란?
이진트리의 성질
이진트리의 추상 자료형
8.3 이진트리의 표현
배열 표현법
링크 표현법
8.4 링크 표현법을 이용한 이진트리의 구현
8.5 이진트리의 순회
이진트리 순회 방법
전위, 중위, 후위 순회 구현
레벨 순회
8.6 이진트리 연산
트리의 노드 개수 구하기
단말 노드 개수 구하기
높이 구하기
8.7 이진트리 응용
수식 트리
디렉터리 용량 계산
8.8 스레드 이진트리
연습문제
프로그래밍 프로젝트

CHAPTER 09 이진 탐색 트리
9.1 이진 탐색 트리
탐색이란?
이진 탐색 트리란?
이진 탐색 트리의 추상 자료형
이진 탐색 트리의 기본 틀 설계
9.2 이진 탐색 트리의 연산
탐색 연산
삽입 연산
삭제 연산
9.3 이진 탐색 트리 프로그램
9.4 이진 탐색 트리의 성능 분석
9.5 이진 탐색 트리의 응용: 영어 사전
연습문제
프로그래밍 프로젝트

CHAPTER 10 우선순위 큐
10.1 우선순위 큐
우선순위 큐란?
우선순위 큐 추상 자료형
10.2 우선순위 큐의 구현 방법
배열을 사용하는 방법
연결 리스트를 사용하는 방법
힙을 사용하는 방법
10.3 힙(Heap)
힙의 개념
힙의 구현 방법
힙의 기본 틀 설계
삽입 연산
삭제 연산
힙의 복잡도 분석
10.4 힙의 응용: 힙 정렬
힙을 사용한 정렬
STL의 우선순위 큐를 사용한 정렬
10.5 힙의 응용: 허프만 코드
허프만 코드란?
허프만 코드 생성 방법
허프만 코드 구현
연습문제
프로그래밍 프로젝트

CHAPTER 11 그래프
11.1 그래프란?
그래프의 역사
그래프의 종류
그래프의 용어
그래프의 추상 자료형
11.2 그래프의 표현
인접 행렬을 이용한 그래프의 표현
인접 행렬을 이용한 그래프 클래스의 구현
인접 리스트를 이용한 그래프의 표현
인접 리스트를 이용한 그래프 클래스의 구현
11.3 그래프의 탐색
깊이 우선 탐색
깊이 우선 탐색의 구현
너비 우선 탐색
너비 우선 탐색의 구현
11.4 연결 성분
11.5 신장 트리
11.6 위상 정렬
연습문제
프로그래밍 프로젝트

CHAPTER 12 가중치 그래프
12.1 가중치 그래프란?
12.2 가중치 그래프의 표현
가중치의 표현
인접 행렬을 이용한 가중치 그래프 구현
12.3 최소 비용 신장 트리
최소 비용 신장 트리란?
Kruskal의 MST 알고리즘
Kruskal 알고리즘의 구현
Prim의 MST 알고리즘
Prim 알고리즘의 구현
12.4 최단 경로
최단 경로 문제란?
Dijkstra의 최단 경로 알고리즘
Dijkstra 알고리즘의 구현
Floyd의 최단 경로 알고리즘
Floyd 알고리즘의 구현
연습문제
프로그래밍 프로젝트

CHAPTER 13 정렬
13.1 정렬이란?
정렬 알고리즘의 분류
13.2 선택 정렬
선택 정렬의 원리
선택 정렬 알고리즘
선택 정렬의 구현
전체 프로그램
선택 정렬의 시간 복잡도 분석
13.3 삽입 정렬
삽입 정렬의 원리
삽입 정렬의 알고리즘
삽입 정렬의 구현
삽입 정렬의 시간 복잡도 분석
함수 포인터를 사용한 정렬 알고리즘의 구현
13.4 버블 정렬
버블 정렬의 원리
버블 정렬의 알고리즘
버블 정렬의 구현
버블 정렬의 시간 복잡도 분석
13.5 셸 정렬
셸 정렬의 원리
셸 정렬의 구현
셸 정렬의 분석
13.6 합병 정렬
합병 정렬의 개념
합병 정렬 알고리즘
합병 정렬의 구현
합병 정렬의 복잡도 분석
13.7 퀵 정렬
퀵 정렬의 개념
퀵 정렬 알고리즘
partition 알고리즘
전체 프로그램
퀵 정렬의 복잡도 분석
퀵 정렬 라이브러리 함수의 사용
13.8 힙 정렬
힙 정렬의 개념
힙 정렬의 복잡도 분석
13.9 기수 정렬
기수 정렬의 원리
기수 정렬의 알고리즘
기수 정렬의 구현
기수 정렬의 분석
13.10 정렬 알고리즘의 비교
연습문제
프로그래밍 프로젝트

CHAPTER 14 탐색
14.1 탐색이란?
맵 이란?
14.2 정렬되지 않은 배열에서의 탐색
순차 탐색
14.3 정렬된 배열에서의 탐색
정렬된 배열에서의 개선된 순차 탐색
정렬된 배열에서의 이진 탐색
색인 순차 탐색
보간 탐색
14.4 균형 이진 탐색 트리
AVL 트리란?
AVL 트리의 삽입 연산
AVL 트리의 구현
14.5 해싱을 이용한 탐색
해싱이란?
이상적인 해싱과 실제의 해싱
해시 함수
14.6 해싱의 오버플로우 처리 방법
선형 조사법
이차 조사법
이중 해싱법
체이닝
해싱의 성능 분석
해싱과 다른 탐색 방법의 비교
14.7 STL 맵 클래스의 활용: 영어 단어장
연습문제
프로그래밍 프로젝트