C++ 算法与数据结构 Algorithms_and_Data_Structures_in_C++[1]

  这是国外计算机专业一个学期的算法与数据结构教程，也可以把它当成 C++ 编程的参考书，本书还附带了非常丰富的以算法和数据结构为重点的例子。

  This text is designed for an introductory quarter or semester course in algorithms and data structures for students in engineering and computer science. It will also serve as a reference text for programmers in C++. The book presents algorithms and data structures with heavy emphasis on C++. Every C++ program presented is a stand-alone program. Except as noted, all of the programs in the book have been compiled and executed on multiple platforms.

  When used in a course, the students should have access to C++ reference manuals for their particular programming environment. The instructor of the course should strive to describe to the students every line of each program. The prerequisite knowledge for this course should be a minimal understanding of digital logic. A high-level programming language is desirable but not required for more advanced students.

  The study of algorithms is a massive field and no single text can do justice to every intricacy or application. The philosophy in this text is to choose an appropriate subset which exercises the unique and more modern aspects of the C++ programming language while providing a stimulating introduction to realistic problems.


详细目录

Preface

Chapter 1—Data Representations
1.1 Integer Representations
1.1.1 Unsigned Notation
1.1.2 Signed-Magnitude Notation
1.1.3 2’s Complement Notation
1.1.4 Sign Extension
1.1.4.1 Signed-Magnitude
1.1.4.2 Unsigned
1.1.4.3 2’s Complement
1.1.5 C++ Program Example
1.2 Floating Point Representation
1.2.1 IEEE 754 Standard Floating Point Representations
1.2.1.1 IEEE 32-Bit Standard
1.2.1.2 IEEE 64-bit Standard
1.2.1.3 C++ Example for IEEE Floating point
1.2.2 Bit Operators in C++
1.2.3 Examples
1.2.4 Conversion from Decimal to Binary
1.3 Character Formats—ASCII
1.4 Putting it All Together
1.5 Problems

Chapter 2—Algorithms
2.1 Order
2.1.1 Justification of Using Order as a Complexity Measure
2.2 Induction
2.3 Recursion
2.3.1 Factorial
2.3.2 Fibonacci Numbers
2.3.3 General Recurrence Relations
2.3.4 Tower of Hanoi
2.3.5 Boolean Function Implementation
2.4 Graphs and Trees
2.5 Parallel Algorithms
2.5.1 Speedup and Amdahls Law
2.5.2 Pipelining
2.5.3 Parallel Processing and Processor Topologies
2.5.3.1 Full Crossbar
2.5.3.2 Rectangular Mesh
2.5.3.3 Hypercube
2.5.3.4 Cube-Connected Cycles
2.6 The Hypercube Topology
2.6.1 Definitions
2.6.2 Message Passing
2.6.3 Efficient Hypercubes
2.6.3.1 Transitive Closure
2.6.3.2 Least-Weighted Path-Length
2.6.3.3 Hypercubes with Failed Nodes
2.6.3.4 Efficiency
2.6.3.5 Message Passing in Efficient Hypercubes
2.6.4 Visualizing the Hypercube: A C++ Example
2.7 Problems

Chapter 3—Data Structures and Searching
3.1 Pointers and Dynamic Memory Allocation
3.1.1 A Double Pointer Example
3.1.2 Dynamic Memory Allocation with New and Delete
3.1.3 Arrays
3.1.4 Overloading in C++
3.2 Arrays
3.3 Stacks
3.4 Linked Lists
3.4.1 Singly Linked Lists
3.4.2 Circular Lists
3.4.3 Doubly Linked Lists
3.5 Operations on Linked Lists
3.5.1 A Linked List Example
3.5.1.1 Bounding a Search Space
3.6 Linear Search
3.7 Binary Search
3.8 QuickSort
3.9 Binary Trees
3.9.1 Traversing the Tree
3.10 Hashing
3.11 Simulated Annealing
3.11.1 The Square Packing Problem
3.11.1.1 Program Description
3.12 Problems

Chapter 4—Algorithms for Computer Arithmetic
4.1 2’s Complement Addition
4.1.1 Full and Half Adder
4.1.2 Ripple Carry Addition
4.1.2.1 Overflow
4.1.3 Carry Lookahead Addition
4.2 A Simple Hardware Simulator in C++
4.3 2’s Complement Multiplication
4.3.1 Shift-Add Addition
4.3.2 Booth Algorithm
4.3.3 Bit-Pair Recoding
4.4 Fixed Point Division
4.4.1 Restoring Division
4.4.2 Nonrestoring Division
4.4.3 Shifting over 1’s and 0’s
4.4.4 Newton’s Method
4.5 Residue Number System
4.5.1 Representation in the Residue Number System
4.5.2 Data Conversion — Calculating the value of a Number
4.5.3 C++ Implementation