Mastering Algorithms with C: Useful Techniques from Sorting to Encryption

by Kyle Loudon

Overview

There are many books on data structures and algorithms, including some with useful libraries of C functions. Mastering Algorithms with C offers you a unique combination of theoretical background and working code. With robust solutions for everyday programming tasks, this book avoids the abstract style of most classic data structures and algorithms texts, but still provides all of the information you need to understand the purpose and use of common programming techniques.

Implementations, as well as interesting, real-world examples of each data structure and algorithm, are included.

Using both a programming style and a writing style that are exceptionally clean, Kyle Loudon shows you how to use such essential data structures as lists, stacks, queues, sets, trees, heaps, priority queues, and graphs. He explains how to use algorithms for sorting, searching, numerical analysis, data compression, data encryption, common graph problems, and computational geometry. And he describes the relative efficiency of all implementations. The compression and encryption chapters not only give you working code for reasonably efficient solutions, they offer explanations of concepts in an approachable manner for people who never have had the time or expertise to study them in depth.

Anyone with a basic understanding of the C language can use this book. In order to provide maintainable and extendible code, an extra level of abstraction (such as pointers to functions) is used in examples where appropriate. Understanding that these techniques may be unfamiliar to some programmers, Loudon explains them clearly in the introductory chapters.

Contents include:

• Pointers
• Recursion
• Analysis of algorithms
• Data structures (lists, stacks, queues, sets, hash tables, trees, heaps, priority queues, graphs)
• Sorting and searching
• Numerical methods
• Data compression
• Data encryption
• Graph algorithms
• Geometric algorithms

Product Details

ISBN-13:	9781565924536
Publisher:	O'Reilly Media, Incorporated
Publication date:	08/12/1999
Series:	Mastering
Pages:	560
Product dimensions:	7.00(w) x 9.19(h) x 1.17(d)

About the Author

Kyle Loudon is a software engineer at Matrix Semiconductor in Santa Clara, California, where he works with file systems and applications for memory chips. Prior to Matrix, Kyle developed platform software for embedded devices, including various wireless phones and the Apple iPod. He also led the graphical user interface group at Jeppesen Dataplan (now a part of Boeing), developed flight planning software, and created system software at IBM in the early 1990s. For the past several years, Kyle has taught object-oriented programming using C++ at the Universityof California, Santa Cruz Extension, and has worked with C++ since the beginning of its widespread use in 1990. Kyle is the author of Mastering Algorithms with C, also published by O'Reilly and Associates.

Table of Contents

Preface; Organization; Key Features; About the Code; Conventions; How to Contact Us; Acknowledgments; Part I: Preliminaries; Chapter 1: Introduction; 1.1 An Introduction to Data Structures; 1.2 An Introduction to Algorithms; 1.3 A Bit About Software Engineering; 1.4 How to Use This Book; Chapter 2: Pointer Manipulation; 2.1 Pointer Fundamentals; 2.2 Storage Allocation; 2.3 Aggregates and Pointer Arithmetic; 2.4 Pointers as Parameters to Functions; 2.5 Generic Pointers and Casts; 2.6 Function Pointers; 2.7 Questions and Answers; 2.8 Related Topics; Chapter 3: Recursion; 3.1 Basic Recursion; 3.2 Tail Recursion; 3.3 Questions and Answers; 3.4 Related Topics; Chapter 4: Analysis of Algorithms; 4.1 Worst-Case Analysis; 4.2 O-Notation; 4.3 Computational Complexity; 4.4 Analysis Example: Insertion Sort; 4.5 Questions and Answers; 4.6 Related Topics; Part II: Data Structures; Chapter 5: Linked Lists; 5.1 Description of Linked Lists; 5.2 Interface for Linked Lists; 5.3 Implementation and Analysis of Linked Lists; 5.4 Linked List Example: Frame Management; 5.5 Description of Doubly-Linked Lists; 5.6 Interface for Doubly-Linked Lists; 5.7 Implementation and Analysis of Doubly Linked Lists; 5.8 Description of Circular Lists; 5.9 Interface for Circular Lists; 5.10 Implementation and Analysis of Circular Lists; 5.11 Circular List Example: Second-Chance Page Replacement; 5.12 Questions and Answers; 5.13 Related Topics; Chapter 6: Stacks and Queues; 6.1 Description of Stacks; 6.2 Interface for Stacks; 6.3 Implementation and Analysis of Stacks; 6.4 Description of Queues; 6.5 Interface for Queues; 6.6 Implementation and Analysis of Queues; 6.7 Queue Example: Event Handling; 6.8 Questions and Answers; 6.9 Related Topics; Chapter 7: Sets; 7.1 Description of Sets; 7.2 Interface for Sets; 7.3 Implementation and Analysis of Sets; 7.4 Set Example: Set Covering; 7.5 Questions and Answers; 7.6 Related Topics; Chapter 8: Hash Tables; 8.1 Description of Chained Hash Tables; 8.2 Interface for Chained Hash Tables; 8.3 Implementation and Analysis of Chained Hash Tables; 8.4 Chained Hash Table Example: Symbol Tables; 8.5 Description of Open-Addressed Hash Tables; 8.6 Interface for Open-Addressed Hash Tables; 8.7 Implementation and Analysisof Open Addressed Hash Tables; 8.8 Questions and Answers; 8.9 Related Topics; Chapter 9: Trees; 9.1 Description of Binary Trees; 9.2 Interface for Binary Trees; 9.3 Implementation and Analysis of Binary Trees; 9.4 Binary Tree Example: Expression Processing; 9.5 Description of Binary Search Trees; 9.6 Interface for Binary Search Trees; 9.7 Implementation and Analysis of Binary Search Trees; 9.8 Questions and Answers; 9.9 Related Topics; Chapter 10: Heaps and Priority Queues; 10.1 Description of Heaps; 10.2 Interface for Heaps; 10.3 Implementation and Analysis of Heaps; 10.4 Description of Priority Queues; 10.5 Interface for Priority Queues; 10.6 Implementation and Analysis of Priority Queues; 10.7 Priority Queue Example: Parcel Sorting; 10.8 Questions and Answers; 10.9 Related Topics; Chapter 11: Graphs; 11.1 Description of Graphs; 11.2 Interface for Graphs; 11.3 Implementation and Analysis of Graphs; 11.4 Graph Example: Counting Network Hops; 11.5 Graph Example: Topological Sorting; 11.6 Questions and Answers; 11.7 Related Topics; Part III: Algorithms; Chapter 12: Sorting and Searching; 12.1 Description of Insertion Sort; 12.2 Interface for Insertion Sort; 12.3 Implementation and Analysis of Insertion Sort; 12.4 Description of Quicksort; 12.5 Interface for Quicksort; 12.6 Implementation and Analysis of Quicksort; 12.7 Quicksort Example: Directory Listings; 12.8 Description of Merge Sort; 12.9 Interface for Merge Sort; 12.10 Implementation and Analysis of Merge Sort; 12.11 Description of Counting Sort; 12.12 Interface for Counting Sort; 12.13 Implementation and Analysis of Counting Sort; 12.14 Description of Radix Sort; 12.15 Interface for Radix Sort; 12.16 Implementation and Analysis of Radix Sort; 12.17 Description of Binary Search; 12.18 Interface for Binary Search; 12.19 Implementation and Analysis of Binary Search; 12.20 Binary Search Example: Spell Checking; 12.21 Questions and Answers; 12.22 Related Topics; Chapter 13: Numerical Methods; 13.1 Description of Polynomial Interpolation; 13.2 Interface for Polynomial Interpolation; 13.3 Implementation and Analysis of Polynomial Interpolation; 13.4 Description of Least-Squares Estimation; 13.5 Interface for Least-Squares Estimation; 13.6 Implementation and Analysis of Least-Squares Estimation; 13.7 Description of the Solution of Equations; 13.8 Interface for the Solution of Equations; 13.9 Implementation and Analysis of the Solution of Equations; 13.10 Questions and Answers; 13.11 Related Topics; Chapter 14: Data Compression; 14.1 Description of Bit Operations; 14.2 Interface for Bit Operations; 14.3 Implementation and Analysis of Bit Operations; 14.4 Description of Huffman Coding; 14.5 Interface for Huffman Coding; 14.6 Implementation and Analysis of Huffman Coding; 14.7 Huffman Coding Example: Optimized Networking; 14.8 Description of LZ77; 14.9 Interface for LZ77; 14.10 Implementation and Analysis of LZ77; 14.11 Questions and Answers; 14.12 Related Topics; Chapter 15: Data Encryption; 15.1 Description of DES; 15.2 Interface for DES; 15.3 Implementation and Analysis of DES; 15.4 DES Example: Block Cipher Modes; 15.5 Description of RSA; 15.6 Interface for RSA; 15.7 Implementation and Analysis of RSA; 15.8 Questions and Answers; 15.9 Related Topics; Chapter 16: Graph Algorithms; 16.1 Description of Minimum Spanning Trees; 16.2 Interface for Minimum Spanning Trees; 16.3 Implementation and Analysis of Minimum Spanning Trees; 16.4 Description of Shortest Paths; 16.5 Interface for Shortest Paths; 16.6 Implementation and Analysis of Shortest Paths; 16.7 Shortest Paths Example: Routing Tables; 16.8 Description of the Traveling-Salesman Problem; 16.9 Interface for the Traveling-Salesman Problem; 16.10 Implementation and Analysis of the Traveling-Salesman Problem; 16.11 Questions and Answers; 16.12 Related Topics; Chapter 17: Geometric Algorithms; 17.1 Description of Testing Whether Line Segments Intersect; 17.2 Interface for Testing Whether Line Segments Intersect; 17.3 Implementation and Analysis of Testing Whether Line Segments Intersect; 17.4 Description of Convex Hulls; 17.5 Interface for Convex Hulls; 17.6 Implementation and Analysis of Convex Hulls; 17.7 Description of Arc Length on Spherical Surfaces; 17.8 Interface for Arc Length on Spherical Surfaces; 17.9 Implementation and Analysis of Arc Length on Spherical Surfaces; 17.10 Arc Length Example: Approximating Distances on Earth; 17.11 Questions and Answers; 17.12 Related Topics; Colophon;

Editorial Reviews

Although older than some of the current languages, C still is one of the best general purpose programming languages around. Loudon's book discusses C pointers, recursion, data structures from lists and stacks to trees and graphs, sorting and searching, and encryption. This is not a beginner's manual but will work well for programmers wanting to refresh their C techniques and for those moving from another language to C. Copyright 1999 Cahners Business Information.

Library Journal