Classic Data Structures in C++

Part 1 Terms, tools and technology: engineering software - responsibility-driven design, programming from reusable components, problem solving heuristics, chapter summary; creating software components - classes, streams, chapter summary; algorithms - descriptions of behaviour - recipes as algorithms, printing integers, integer exponents, greatest common divisor, chapter summary. Part 2 Analysis, algorithms and abstractions: strings - an example ADT - primitive strings, the string data abstraction, pattern matching, chapter summary; classification of collections; vectors and component reuse - templates, simple vectors, techniques for software reuse, other vector variations, function templates, chapter summary; inheritance - power through polymorphism - static and dynamic types, frameworks and virtual methods, varieties of inheritance, iterators, forms of polymorphism, the slicing problem, chapter summary; lists - a dynamic data structure - simple lists, list iterators, application - polynomial arithmetic, ordered lists, self-organizing lists, double ended lsits, other common variations, application - free lists, chapter summary; stacks and queues - higher level abstractions - the abstract classes stack and queue, stacks, application - RPN calculator, application - coversion of infix to postfix, queues, application - breadth first search, application - a framework for backtracking, chapter summary; trees - a nonlinear data structure - binary trees, operator precedence parsing, tree traversals, binary tree representation of general trees, chapter summary; searching - divide and conquer, binary search, ordered vectors, binary search trees, AVL trees, application - tree sort, finding the Nth largest, chapter summary; priority queues - heaps, skew heaps, application - discrete event-driven simulation, chapter summary; hash tables - collision resolution using buckets, asymptotic analysis of hash table operations, hash table iterators, application - bucket sorting, hash functions, chapter summary; sets and bags - unordered collections - set operations, bit vector sets, the abstract set operations, building sets from hash tables, chapter summary; dictionaries and tables - associations, dictionaries as lists of associations, ordered dictionaries, dictionaries as hash tables, chapter summary; graphs - adjacency matrix representation, edge list representation, weighted adjacency matrix, labelled edge list representation, finite automata, chapter summary; files - external collections.