数据结构与算法——C++版（第2版·影印版）

.1.11 exercises
1.12 programming assignments
chapter 2 complexity analysis
2.1 computational and asymptotic complexity
2.2 big-o notation
2.3 properties of big-o notation
2.4 and notations
2.5 possible problems
2.6 examples of complexities
2.7 finding asymptotic complexity:examples
2.8 the best, average, and worst cases
2.9 amortized complexity
2.10 exercises
chapter 3 llinked lis+s
3.1 singly linked lists
3.1.1 insertion
3.1.2 deletion
3.1.3 search
3.2 doubly linked lists
3.3 circular lists
3.4 skip lists
3.5 self-organizing lists
3.6 sparse tables
3.7 lists in the standard template library
3.8 deques in the standard template library
3.9 concluding remarks
3.10 case study: a library
3.11 exercises
3.12 programming assignments
chapter 4 stacks and queues
4. 1 stacks
4.2 queues
4.3 priority queues
4.4 stacks in the standard template library
4.5 queues in the standard template library
4.6 priority queues in the standard template library
4.7 case study: exiting a maze
4.8 exercises
4.9 programming assignments
chapter 5 recursion
5.1 recursive definitions
5.2 function calls and recursion implementation
5.3 anatomy of a recursive call
5.4 tail recursion
5.5 nontail recursion
5.6 indirect recursion
5.7 nested recursion
5.8 excessive recursion
5.9 backtracking
5.10 concluding remarks
5.11 case study: a recursive descent interpreter
5.12 exercises
5.13 programming assignments
chapter 6 binary trees
6.1 trees, binary trees, and binary search trees
6.2 implementing binary trees
6.3 searching a binary search tree
6.4 tree traversal
6.4.1 breadth-first traversal
6.4.2 depth-first traversal
6.4.3 stackless depth-first traversal
6.5 insertion
6.6 deletion
6.6.1 deletion by merging
6.6.2 deletion by copying
6.7 balancing a tree
6.7.1 the dsw algorithm
6.7.2 avl trees
6.8 self-adjusting trees
6.8.1 self-restructuring trees
6.8.2 splaying
6.9 heaps
6.9.1 heaps as priority queues
6.9.2 organizing arrays as heaps
6.10 polish notation and expression trees
6.11 case study: computing word frequencies
6.12 exercises
6.13 programming assignments
chapter 7 multiway trees
7.1 the family of b-trees
7.1.1 b-trees
7.1.2 b*-trees
7.1.3 b+-trees
7.1.4 prefix b+-trees
7.1.5 bit-trees
7.1.6 r-trees
7.1.7 2-4 trees
7.1.8 sets and multisets in the standard template library
7.1.9 maps and multimaps in the standard template library
7.2 tries
7.3 concluding remarks
7.4 case study: spell checker
7.5 exercises
7.6 programming assignments
chapter 8 graphs
8.1 graph representation
8.2 graph traversals
8.3 shortest paths
8.4 cycle detection
8.5 spanning trees
8.5.1 borfivka's algorithm
8.5.2 kruskal's algorithm
8.5.3 jarnik-prim's algorithm
8.5.4 dijkstra's method
8.6 connectivity
8.6.1 connectivity in undirected graphs
8.6.2 connectivity in directed graphs
8.7 topological sort
8.8 networks
8.8.1 maximum flows
8.8.2 maximum flows of minimum cost
8.9 matching
8.9.1 assignment problem
8.9.2 matching in nonbipartite graphs
8.10 eulerian and hamiltonian graphs
8.10.1 eulerian graphs
8.10.2 hamiltonian graphs
8.11 case study: distinct representatives
8.12 exercises
8.13 programming assignments
chapter 9 sorting
9.1 elementary sorting algorithms
9.1.i insertion sort
9.1.2 selection sort
9.1.3 bubble sort
9.2 decision trees
9.3 efficient sorting algorithms
9.3.1 shell sort
9.3.2 heap sort
9.3.3 quicksort
9.3.4 mergesort
9.3.5 radix sort
9.4 sorting in the standard template library
9.5 concluding remarks
9.6 case study: adding polynomials
9.7 exercises
9.8 programming assignments
chapter 10 hashing
10.1 hash functions
10.1.1 division
t0.1.2 folding
10.1.3 mid-square function
10.1.4 extraction
10.1.5 radix transformation
10.2 collision resolution
10.2.1 open addressing
10.2.2 chaining
10.2.3 bucket addressing
10.3 deletion
10.4 perfect hash functions
10.4.1 cichelli's method
10.4.2 the fhcd algorithm
10.5 hash functions for extendible files
10.5.1 extendible hashing
10.5.2 linear hashing
10.6 case study:hashing with buckets
10.7 exercises
10.8 programming assignments
chapter 11 data compression
11.1 conditions for data compression
11.2 huffman coding
11.3 shannon-fano code
11.4 run-length encoding
11.5 ziv-lempel code
11.6 case study: huffman method with run-length encoding
11.7 exercises
11.8 programming assignments
chapter 12 memory management
12.1 the sequential-fit methods
12.2 the nonsequential-fit methods
12.3 garbage collection
12.3.1 mark-and-sweep
12.3.2 copying methods
12.3.3 incremental garbage collection
12.4 concluding remarks
12.5 case study: an in-place garbage collector
12.6 exercises
12.7 programming assignments
appendix a computing big-o
appendix b algorithms in the standard template library