SW 코딩 역량은 자료구조 구현 능력에 달려 있다. 어떤 자료구조를 사용하느냐에 따라 구현된 SW의 성능과 기능이 달라진다. SW 개발은 class와 함수를 만드는 것이다. main( ) 함수는 가능한 한 데이터 입력, insert, delete, search 등의 다른 함수 호출만 사용하는 것이 좋다. SW 코딩 능력은 class에 어떤 함수를 만들고 어떤 변수를 사용하여 알고리즘을 구현할 것에 대한 design choice를 잘하는 능력이다. 예를 들면 search 함수를 만들 때 class의 public member 함수로 만들 것인지 아니면 일반 함수로 만들 것인지를 선택(choice)해야 한다. C++ 언어를 구사할 수 있어야 C++로 된 자료구조를 공부할 수 있다. 이 책은 C++를 사용하여 구현된 소스 코드를 포함하고 있다. 자료구조는 이론 과목이 아니므로 각 자료구조에 대하여 소스 코드를 사용하여 구현하고 test하는 실습으로 습득해야 한다. 추천하는 자료구조 학습 방법은 단순히 제시된 소스 코드를 보지 말고 필요한 소스 코드를 작성하는 연습을 반복하는 것이다. 그리고 제시된 소스 코드에 새로운 기능을 추가하거나 성능을 개선하는 소스 코드 변경 작업을 통하여 구현 능력을 향상하는 것이 바람직하다. 이 책에서는 자료구조에 대한 insert, delete, search 등을 처리하기 위하여 입력 데이터를 받아 해당 자료구조를 만드는 방법에 중점을 두었다. 구현하고자 하는 자료구조를 동작시키기 위해 화면에서 데이터를 임의로 입력받거나 난수를 생성하여 자동으로 해당 자료구조를 만드는 방법으로 실습하는 것이 효과적이다. 자료구조와 알고리즘은 별개의 다른 주제가 아니고 매우 밀접하여 거의 하나의 topic이라고 생각해야 한다. 예를 들면 2개의 linked list를 merge 하는 알고리즘의 구현은 singly linked list, circular linked list, head node가 있는 circular linked list 등에 따라 달라진다. 즉, class의 data member 변수를 어떻게 사용하느냐에 따라 구현 알고리즘이 복잡해질 수도 있고 간단해질 수도 있다. 따라서 자료구조의 설계, 자료구조의 data representation에 따라 알고리즘의 성능도 달라질 수 있다. stack, queue, linked list, tree, hashing은 C++ STL에서 제공하므로 굳이 자료구조를 만들 필요가 없다고 오해할 수 있다. C++ STL을 사용하면 구현이 간단해질 수는 있으나 성능이 떨어질 수 있다. 응용에 따라 C++ STL을 가져다 사용하는 것이 좋을 수도 있고 직접 hash map, heap 등을 구현하여 사용하는 것이 더 우수할 수도 있다. 자료구조와 알고리즘 내용으로 이 책에서 다루지 못한 heap structure로서 leftist tree, binomial heaps, Fibonacci heaps와 search structures로서 AVL tree, 2-3 trees, 2-3-4 trees, red-black tree, B-tree, splay trees, digital search tree, trie를 학습하여 SW 코딩의 진정한 고수가 되기를 바란다.

1장 자료구조가 필요한 이유는? 1.1 행렬 연산을 하는 C 프로그래밍 문제 8 1.2 C++ class 프로그래밍 11 1.3 알고리즘 구현 25 2장 배열 기반 자료구조 2.1 Set과 Bag 자료구조 30 2.2 ArrayList와 Vector 자료구조 34 2.3 Polynomial class 37 3장 Stacks과 Queues 3.1 C++의 Templates 48 3.2 Adaptive containers: Stack과 Queue 50 3.3 Bag 자료구조 52 3.4 Stack 자료구조 56 3.5 Queue 자료구조 58 3.6 Deque 자료구조 62 3.7 미로 찾기 62 3.8 Stack을 이용한 Postfix expression 71 3.9 Queen 문제와 Knight tour 문제 76 4장 Linked List 4.1 Sinlgy linked lists 78 4.2 C++로 Linked List 표현 79 4.3 Template linked list 80 4.4 Linked list iterators 81 4.5 Circular lists 91 4.6 Linked stacks과 Queues 102 4.7 Linked list를 사용한 Polynomial 처리 106 4.8 Available list를 사용한 Polynomial 처리 114 4.9 Doubly linked lists 129 4.10 Generalized lists 136 4.11 Heterogeneous lists 146 5장 Trees 5.1 Tree 용어 160 5.2 Binary tree 표현 162 5.3 Binary tree traversal과 Tree iterations 165 5.4 Satisfiability 문제 179 5.5 Threaded binary trees 187 5.6 Heaps 198 5.7 Binary search trees 212 5.8 Sets 표현 220 5.9 C++ STL map과 Set 226 6장 Graphs 6.1 Graph 용어 228 6.2 Graph 표현 구조 229 6.3 DFS와 BFS 239 6.4 최소 비용 Spanning tree 240 6.5 Shortest paths 262 6.6 Activity networks 277 | 참고문헌 | 297