Data Structures and C Programs

This book on data structures and the algorithms used to maintain them presents both the ideas and principles of data structures and algorithms and programs that use them. The programs are coded in the C language and have been compiled, executed, and tested; they provide a more concrete demonstration of important ideas than pseudo-code sketches.

Data Structures and C Programs uses formal techniques to analyze programs, but does not make them the principal focus of study. Instead, it presents data structures and algorithms as tools with which to build useful and interesting programs.

Highlights:

• Contains many working, tested example programs that illustrate ideas and a working application program that uses those ideas to solve a real-world problem.
• Uses measurements on some example programs to complement the traditional theoretical analysis of their behavior.
• Includes in appendices an introduction to the C programming language and an explanation of library functions used in the text.

• Part I: Fundamental Ideas
1. Charting Our Course
1. Problem: Summarizing Data
2. Solution I
3. Solution II
4. Measuring Performance
5. Summary and Perspective
2. The Complexity of Algorithms
1. The Idea of an Algorithm
2. Algorithms for Exponentiation
3. Asymptotic Analysis
4. Implementation Considerations
5. Summary and Perspective
3. Pointers and Dynamic Storage
1. Variables and Pointers
2. Character Strings and Arrays
3. Typedefs and Structures
4. Dynamic Storage Allocation
5. Summary and Perspective
4. Stacks and Queues
1. Two Disciplines for Paying Bills
2. The Stack Data Type
3. The Queue Data Type
4. Example Applications
5. Summary and Perspective
5. Linked Lists
1. Lists
2. Application: Sets
3. Miscellaneous Tools for Linked Structure
4. Multiply Linked Structures
5. Summary and Perspective
6. Memory Organization
1. More About Memory
2. Variables and the Runtime Stack
3. A Simple Heap Management Scheme
4. Physical Memory Organization
5. Summary and Perspective
• Part II: Efficient Algorithms
7. Searching
1. Aspects of Searching
2. Self-Organizing Linked Lists
3. Binary Search
4. Binary Trees
5. Binary Search Trees
6. Summary and Perspective
8. Hashing
1. Perfect Hashing
2. Collision Resolution Using a Probe Strategy
3. Collision Resolution Using Linked Lists
4. Summary and Perspective
9. Sorted Lists
1. AVL Trees
2. 2.4 Trees
3. Implementation: Red-Black Trees
4. Further Topics
5. Summary and Perspective
10. Priority Queues
1. The Data Type Priority Queue
2. Heaps
3. Implementation of Heaps
4. Huffman Trees
5. Other Operations
6. Summary and Perspective
11. Sorting
1. Settings for Sorting
2. Two Simple Sorting Algorithms
3. Two Efficient Sorting Algorithms
4. Two Useful Sorting Ideas
5. Summary and Perspective
12. Applying Data Structures
1. Double Entry Bookkeeping
2. Basic Solution
3. Solution I
4. Solution II
5. Summary and Perspective
• Part III: Advanced Topics
13. Acrylic Graphs
1. Rooted Trees
2. Disjoint Sets
3. Topological Sorting
4. Summary and Perspective
14. Graphs
1. Terminology
2. Data Structures
3. Shortest Paths
4. Minimum Spanning Trees
5. Traversal Orders and Graph Connectivity
6. Summary and Perspective
• Appendixes
1. C for Programmers
2. Library Functions
3. Our Header File
4. Solutions to Selected Exercises

A good book about the most basic data structures. Don't expect to learn C from this.