Data Structures, Algorithms, & Software Principles in C
Thomas A. Standish
Using C, this book develops the concepts and theory of data structures and algorithm analysis in a gradual, step-by-step manner, proceeding from concrete examples to abstract principles. Standish covers a wide range of both traditional and contemporary software engineering topics. The text also includes an introduction to object-oriented programming using C++. By introducing recurring themes such as levels of abstraction, recursion, efficiency, representation and trade-offs, the author unifies the material throughout. Mathematical foundations can be incorporated at a variety of depths, allowing the appropriate amount of math for each user.
(All chapters, except Chapter 1, begin with an Introduction and Motivation.)
1. Preparing for the Journey.
Blending Mathematics, Science, and Engineering.
The Search for Enduring Principles in Computer Science.
Principles of Software System Structure.
Efficiency and Tradeoffs.
Software Engineering Principles.
Our Approach to Mathematics.
Some Notes on Programming Notation.
Preview of Coming Attractions.
2. Linked Data Representations.
Pointers in C—The Rudiments.
Pointer Diagramming Notation.
Linear Linked Lists.
Other Linked Data Structures.
3. Introduction to Recursion.
Common Pitfall—Infinite Regresses.
Quantitative Aspects of Recursive Algorithms.
4. Modularity and Data Abstraction.
Priority Queues—An Abstract Data Type.
A Pocket Calculator Interface.
How to Hide Data Representations.
Modularity and Information Hiding in Program Design.
5. Introduction to Software Engineering Concepts.
Proving Programs Correct.
Transforming and Optimizing Programs.
The Philosophy of Measurement and Tuning.
Software Reuse and Bottom-up Programming.
Program Structuring and Documentation.
6. Introduction to Analysis of Algorithms.
The Intuition Behind O-Notation.
O-Notation—Definition and Manipulation.
Analyzing Simple Algorithms.
What O-Notation Doesn't Tell You.
7. Linear Data Structures—Stacks and Queues.
ADTs for Stacks and Queues.
Using the Stack ADT to Check for Balanced Parentheses.
Using the Stack ADT to Evaluate Postfix Expressions.
Implementing the Stack ADT.
How C Implements Recursive Function Calls Using Stacks.
Implementations of the Queue ADT.
More Queue Applications.
8. Lists, Strings, and Dynamic Memory Allocation.
Applications of Generalized Lists.
Dynamic Memory Allocation.
A Sequential Binary Tree Representation.
An Application—Heaps and Priority Queues.
Traversing Binary Trees.
Binary Search Trees.
AVL Trees and Their Performance.
An Application—Huffman Codes.
Useful Background on Graphs.
11. Hashing and the Table ADT.
Introduction to Hashing by Simple Examples.
Collisions, Load Factors, and Clusters.
Algorithms for Hashing by Open Addressing.
Choosing a Hash Function.
Comparison of Searching Methods Using the Table ADT.
12. External Collections of Data.
Techniques That Don't Work Well.
Techniques That Work Well.
Information Retrieval and Databases.
Priority Queue Sorting Methods.
Methods That Insert Keys and Keep Them Sorted.
O(n) Methods—Address Calculation Sorting.
Comparison and Perspective.
14. Advanced Recursion.
Using Recursion to Build a Parser.
Translating from Infix to Postfix.
Recursion and Program Verification.
15. Object-Oriented Programming.
Building Systems Using Object-Oriented Programming.
Advantages and Disadvantages of Object-Oriented Programming.
16. Advanced Software Engineering Concepts.
Software Process Models.
Appendix Math Reference and Tutorial. 0201591189T04062001