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

천인국

저자천인국은
1983년서울대학교전자공학과공학사
1985년한국과학기술원전기및전자공학과공학석사
1993년한국과학기술원전기및전자공학과공학박사
1985~1988년삼성전자종합연구소주임연구원
1993년~현재순천향대학교컴퓨터공학과교수
2005년캐나다UBC방문교수

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C++의복잡한문법이아니라자료구조에초점을맞춘기본서

자료구조(datastructure)는전산학및컴퓨터공학분야에서매우중요하고기초적인과목이다.하지만자료구조는학생들이상당히어려워하는과목이다.이책의특징은다음과같다.

-자료구조를구현하기위해이책에서는객체지향언어인C++를이용하였다.C++를잘모르면이책을공부할수없을까?물론아니다.이책에서는C++의복잡한문법이아니라자료구조에초점을맞추기위해기본적이고실용적인부분들만을이용하여설명하였다.따라서C언어를어느정도이해하고있다면C++를잘알지못한다고해서너무걱정할필요는없다.각장에서자료구조들을공부하면서C++문법도하나씩알아나가자.물론C++를이미잘알고있으면더욱좋다.이책이매우좋은C++복습서가될것이다.
-C++는다양한기능들을제공하는복잡한언어로때로는불필요해보이는기능들도포함한다.이책에서는C++의문법적인측면보다는Java와같은대부분의객체지향언어에서공통적으로사용하는유용한기법들을위주로예제코드를작성하였다.따라서이책의독자들이책의내용들을Java와같은다른객체지향언어에도쉽게적용할수있도록노력하였다.
-2장에서이책에서주로사용하는C++문법과그렇지않은문법을구분하였다.동적바인딩이나다중상속등다소복잡한문법은이책에서사용하지않는다.이책에서는템플릿에대해서도다루지않지만C++에서제공하는표준템플릿라이브러리(STL)를사용하는방법들은소개한다.STL은프로그래밍에서공통적으로사용되는자료구조와알고리즘을템플릿기반으로작성하여제공하는데,STL에서제공하는자료구조들을문제해결에적용해보는것은현실적으로매우유용할것으로생각된다.
-C언어를공부한학생들도포인터가어려웠을것이다.이책에서는포인터와연결리스트를5장에서설명하고있다.포인터가어렵지만포인터의개념이명확하지않더라도구현할수있는프로그램이많다는것을이야기하고싶다.
-각장의학습내용의양을가능하면균일하게배분하도록구성하였다.이를위해트리와그래프는각각두개의장으로나누었다.또한최대한연관된내용을인접장에배치하였다.
-이책에서는어떤자료구조를설명하기위해추상자료형,UML다이어그램그리고C++클래스를이용한다.먼저추상자료형으로그자료구조에서필요로하는데이터(객체)와연산들을알아보고,이것을UML다이어그램을이용해보다구체적으로설계한다.이것은추상자료형보다는구체화되었지만아직프로그래밍언어에는독립적인상태이다.마지막으로UML다이어그램을바탕으로해당자료구조를C++클래스로구현한예를보이고,main()함수에서구현된클래스를사용해문제를해결하는예를제시한다.
-가능한한완전한프로그램을제공하기위해노력하였다.책에서제시하고있는대부분의코드들은main함수를포함하여완전한코드이며프로그램의실제실행결과를함께제시하여학습자들이쉽게소스의동작을확인하고이해하며활용할수있도록하였다.