Mastering algorithms with C

•

Table of

Contents

• Index

• Reviews

• Examples

• Reader Reviews

• Errata

Mastering Algorithms with C

By Kyle Loudon

Publisher: O'Reilly

Pub Date: August 1999

ISBN: 1-56592-453-3

Pages: 560

This book offers robust solutions for everyday programming tasks,

providing all the necessary information to understand and use common

programming techniques. It includes implementations and real-world

examples of each data structure in the text and full source code on the

accompanying website (http://examples.oreilly.com/masteralgoc/).

Intended for anyone with a basic understanding of the C language.

•

Table of

Contents

• Index

• Reviews

• Examples

• Reader Reviews

• Errata

Mastering Algorithms with C

By Kyle Loudon

Publisher: O'Reilly

Pub Date: August 1999

ISBN: 1-56592-453-3

Pages: 560

This book offers robust solutions for everyday programming tasks,

providing all the necessary information to understand and use common

programming techniques. It includes implementations and real-world

examples of each data structure in the text and full source code on the

accompanying website (http://examples.oreilly.com/masteralgoc/).

Intended for anyone with a basic understanding of the C language.

•

Table of

Contents

• Index

• Reviews

• Examples

• Reader Reviews

• Errata

Mastering Algorithms with C

By Kyle Loudon

Publisher: O'Reilly

Pub Date: August 1999

ISBN: 1-56592-453-3

Pages: 560

Copyright

Preface

Organization

Key Features

About the Code

Conventions

How to Contact Us

Acknowledgments

Part I: Preliminaries

Chapter 1. Introduction

Section 1.1. An Introduction to Data Structures

Section 1.2. An Introduction to Algorithms

Section 1.3. A Bit About Software Engineering

Section 1.4. How to Use This Book

Chapter 2. Pointer Manipulation

Section 2.1. Pointer Fundamentals

Section 2.2. Storage Allocation

Section 2.3. Aggregates and Pointer Arithmetic

Section 2.4. Pointers as Parameters to Functions

Section 2.5. Generic Pointers and Casts

Section 2.6. Function Pointers

Section 2.7. Questions and Answers

Section 2.8. Related Topics

Chapter 3. Recursion

Section 3.1. Basic Recursion

Section 3.2. Tail Recursion

Section 3.3. Questions and Answers

Section 3.4. Related Topics

Chapter 4. Analysis of Algorithms

Section 4.1. Worst-Case Analysis

Section 4.2. O-Notation

Section 4.3. Computational Complexity

Section 4.4. Analysis Example: Insertion Sort

Section 4.5. Questions and Answers

Section 4.6. Related Topics

Part II: Data Structures

Chapter 5. Linked Lists

Section 5.1. Description of Linked Lists

Section 5.2. Interface for Linked Lists

Section 5.3. Implementation and Analysis of Linked Lists

Section 5.4. Linked List Example: Frame Management

Section 5.5. Description of Doubly-Linked Lists

Section 5.6. Interface for Doubly-Linked Lists

Section 5.7. Implementation and Analysis of Doubly Linked Lists

Section 5.8. Description of Circular Lists

Section 5.9. Interface for Circular Lists

Section 5.10. Implementation and Analysis of Circular Lists

Section 5.11. Circular List Example: Second-Chance Page Replacement

Section 5.12. Questions and Answers

Section 5.13. Related Topics

Chapter 6. Stacks and Queues

Section 6.1. Description of Stacks

Section 6.2. Interface for Stacks

Section 6.3. Implementation and Analysis of Stacks

Section 6.4. Description of Queues

Section 6.5. Interface for Queues

Section 6.6. Implementation and Analysis of Queues

Section 6.7. Queue Example: Event Handling

Section 6.8. Questions and Answers

Section 6.9. Related Topics

Chapter 7. Sets

Section 7.1. Description of Sets

Section 7.2. Interface for Sets

Section 7.3. Implementation and Analysis of Sets

Section 7.4. Set Example: Set Covering

Section 7.5. Questions and Answers

Section 7.6. Related Topics

Chapter 8. Hash Tables

Section 8.1. Description of Chained Hash Tables

Section 8.2. Interface for Chained Hash Tables

Section 8.3. Implementation and Analysis of Chained Hash Tables

Section 8.4. Chained Hash Table Example: Symbol Tables

Section 8.5. Description of Open-Addressed Hash Tables

Section 8.6. Interface for Open-Addressed Hash Tables

Section 8.7. Implementation and Analysisof Open Addressed Hash Tables

Section 8.8. Questions and Answers

Section 8.9. Related Topics

Chapter 9. Trees

Section 9.1. Description of Binary Trees

Section 9.2. Interface for Binary Trees

Section 9.3. Implementation and Analysis of Binary Trees

Section 9.4. Binary Tree Example: Expression Processing

Section 9.5. Description of Binary Search Trees

Section 9.6. Interface for Binary Search Trees

Section 9.7. Implementation and Analysis of Binary Search Trees

Section 9.8. Questions and Answers

Section 9.9. Related Topics

Chapter 10. Heaps and Priority Queues

Section 10.1. Description of Heaps

Section 10.2. Interface for Heaps

Section 10.3. Implementation and Analysis of Heaps

Section 10.4. Description of Priority Queues

Section 10.5. Interface for Priority Queues

Section 10.6. Implementation and Analysis of Priority Queues

Section 10.7. Priority Queue Example: Parcel Sorting

Section 10.8. Questions and Answers

Section 10.9. Related Topics

Chapter 11. Graphs

Section 11.1. Description of Graphs

Section 11.2. Interface for Graphs

Section 11.3. Implementation and Analysis of Graphs

Section 11.4. Graph Example: Counting Network Hops

Section 11.5. Graph Example: Topological Sorting

Section 11.6. Questions and Answers

Section 11.7. Related Topics

Part III: Algorithms

Chapter 12. Sorting and Searching

Section 12.1. Description of Insertion Sort

Section 12.2. Interface for Insertion Sort

Section 12.3. Implementation and Analysis of Insertion Sort

Section 12.4. Description of Quicksort

Section 12.5. Interface for Quicksort

Section 12.6. Implementation and Analysis of Quicksort

Section 12.7. Quicksort Example: Directory Listings

Section 12.8. Description of Merge Sort

Section 12.9. Interface for Merge Sort

Section 12.10. Implementation and Analysis of Merge Sort

Section 12.11. Description of Counting Sort

Section 12.12. Interface for Counting Sort

Section 12.13. Implementation and Analysis of Counting Sort

Section 12.14. Description of Radix Sort

Section 12.15. Interface for Radix Sort

Section 12.16. Implementation and Analysis of Radix Sort

Section 12.17. Description of Binary Search

Section 12.18. Interface for Binary Search

Section 12.19. Implementation and Analysis of Binary Search

Section 12.20. Binary Search Example: Spell Checking

Section 12.21. Questions and Answers

Section 12.22. Related Topics

Chapter 13. Numerical Methods

Section 13.1. Description of Polynomial Interpolation

Section 13.2. Interface for Polynomial Interpolation

Section 13.3. Implementation and Analysis of Polynomial Interpolation

Section 13.4. Description of Least-Squares Estimation

Section 13.5. Interface for Least-Squares Estimation

Section 13.6. Implementation and Analysis of Least-Squares Estimation

Section 13.7. Description of the Solution of Equations

Section 13.8. Interface for the Solution of Equations

Section 13.9. Implementation and Analysis of the Solution of Equations

Section 13.10. Questions and Answers

Section 13.11. Related Topics

Chapter 14. Data Compression

Section 14.1. Description of Bit Operations

Section 14.2. Interface for Bit Operations

Section 14.3. Implementation and Analysis of Bit Operations

Section 14.4. Description of Huffman Coding

Section 14.5. Interface for Huffman Coding

Section 14.6. Implementation and Analysis of Huffman Coding

Section 14.7. Huffman Coding Example: Optimized Networking

Section 14.8. Description of LZ77

Section 14.9. Interface for LZ77

Section 14.10. Implementation and Analysis of LZ77

Section 14.11. Questions and Answers

Section 14.12. Related Topics

Chapter 15. Data Encryption

Section 15.1. Description of DES

Section 15.2. Interface for DES

Section 15.3. Implementation and Analysis of DES

Section 15.4. DES Example: Block Cipher Modes

Section 15.5. Description of RSA

Section 15.6. Interface for RSA

Section 15.7. Implementation and Analysis of RSA

Section 15.8. Questions and Answers

Section 15.9. Related Topics

Chapter 16. Graph Algorithms

Section 16.1. Description of Minimum Spanning Trees

Section 16.2. Interface for Minimum Spanning Trees

Section 16.3. Implementation and Analysis of Minimum Spanning Trees

Section 16.4. Description of Shortest Paths

Section 16.5. Interface for Shortest Paths

Section 16.6. Implementation and Analysis of Shortest Paths

Section 16.7. Shortest Paths Example: Routing Tables

Section 16.8. Description of the Traveling-Salesman Problem

Section 16.9. Interface for the Traveling-Salesman Problem

Section 16.10. Implementation and Analysis of the Traveling-Salesman Problem

Section 16.11. Questions and Answers

Section 16.12. Related Topics

Chapter 17. Geometric Algorithms

Section 17.1. Description of Testing Whether Line Segments Intersect

Section 17.2. Interface for Testing Whether Line Segments Intersect

Section 17.3. Implementation and Analysis of Testing Whether Line Segments Intersect

Section 17.4. Description of Convex Hulls

Section 17.5. Interface for Convex Hulls

Section 17.6. Implementation and Analysis of Convex Hulls

Section 17.7. Description of Arc Length on Spherical Surfaces

Section 17.8. Interface for Arc Length on Spherical Surfaces

Section 17.9. Implementation and Analysis of Arc Length on Spherical Surfaces

Section 17.10. Arc Length Example: Approximating Distances on Earth

Section 17.11. Questions and Answers

Section 17.12. Related Topics

Colophon

Index

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Content

Copyright © 1999 O'Reilly & Associates, Inc. All rights reserved.

Printed in the United States of America.

Published by O'Reilly & Associates, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472.

O'Reilly & Associates books may be purchased for educational, business, or sales promotional use.

Online editions are also available for most titles (safari.oreilly.com). For more information, contact

our corporate/institutional sales department: (800) 998-9938 or [email protected].

Nutshell Handbook, the Nutshell Handbook logo, and the O'Reilly logo are registered trademarks of

O'Reilly & Associates, Inc. Many of the designations used by manufacturers and sellers to

distinguish their products are claimed as trademarks. Where those designations appear in this

book, and O'Reilly & Associates, Inc. was aware of a trademark claim, the designations have been

printed in caps or initial caps. The association between the image of sea horses and the topic of

algorithms with C is a trademark of O'Reilly & Associates, Inc.

While every precaution has been taken in the preparation of this book, the publisher assumes no

responsibility for errors or omissions, or for damages resulting from the use of the information

contained herein.

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Content

Preface

When I first thought about writing this book, I immediately thought of O'Reilly & Associates to

publish it. They were the first publisher I contacted, and the one I most wanted to work with

because of their tradition of books covering "just the facts." This approach is not what one normally

thinks of in connection with books on data structures and algorithms. When one studies data

structures and algorithms, normally there is a fair amount of time spent on proving their

correctness rigorously. Consequently, many books on this subject have an academic feel about

them, and real details such as implementation and application are left to be resolved elsewhere.

This book covers how and why certain data structures and algorithms work, real applications that

use them (including many examples), and their implementation. Mathematical rigor appears only

to the extent necessary in explanations.

Naturally, I was very happy that O'Reilly & Associates saw value in a book that covered this aspect

of the subject. This preface contains some of the reasons I think you will find this book valuable as

well. It also covers certain aspects of the code in the book, defines a few conventions, and

gratefully acknowledges the people who played a part in the book's creation.

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Preface

Content

Organization

This book is divided into three parts. The first part consists of introductory material that is useful

when working in the rest of the book. The second part presents a number of data structures

considered fundamental in the field of computer science. The third part presents an assortment of

algorithms for solving common problems. Each of these parts is described in more detail in the

following sections, including a summary of the chapters each part contains.

Part I

Part I contains Chapter 1 through Chapter 4. Chapter 1, introduces the concepts of data structures

and algorithms and presents reasons for using them. It also presents a few topics in software

engineering, which are applied throughout the rest of the book. Chapter 2 discusses a number of

topics on pointers. Pointers appear a great deal in this book, so this chapter serves as a refresher

on the subject. Chapter 3 covers recursion, a popular technique used with many data structures

and algorithms. Chapter 4 presents the analysis of algorithms. The techniques in this chapter are

used to analyze algorithms throughout the book.

Part II

Part II contains Chapter 5 through Chapter 11. Chapter 5 presents various forms of linked lists,

including singly-linked lists, doubly-linked lists, and circular lists. Chapter 6 presents stacks and

queues, data structures for sorting and returning data on a last-in, first-out and first-in, first-out

order respectively. Chapter 7 presents sets and the fundamental mathematics describing sets.

Chapter 8 presents chained and open-addressed hash tables, including material on how to select a

good hash function and how to resolve collisions. Chapter 9 presents binary and AVL trees. Chapter

9 also discusses various methods of tree traversal. Chapter 10 presents heaps and priority queues,

data structures that help to quickly determine the largest or smallest element in a set of data.

Chapter 11 presents graphs and two fundamental algorithms from which many graph algorithms

are derived: breadth-first and depth-first search.

Part III

Part III, contains Chapter 12 through Chapter 17. Chapter 12 covers various algorithms for

sorting, including insertion sort, quicksort, merge sort, counting sort, and radix sort. Chapter 12

also presents binary search. Chapter 13 covers numerical methods, including algorithms for

polynomial interpolation, least-squares estimation, and the solution of equations using Newton's

method. Chapter 14 presents algorithms for data compression, including Huffman coding and

LZ77. Chapter 15 discusses algorithms for DES and RSA encryption. Chapter 16 covers graph

algorithms, including Prim's algorithm for minimum spanning trees, Dijkstra's algorithm for

shortest paths, and an algorithm for solving the traveling-salesman problem. Chapter 17 presents

geometric algorithms, including methods for testing whether line segments intersect, computing

convex hulls, and computing arc lengths on spherical surfaces.

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Preface

Content

Key Features

There are a number of special features that I believe together make this book a unique approach to

covering the subject of data structures and algorithms:

Consistent format for every chapter

Every chapter (excluding those in the first part of the book) follows a consistent format. This

format allows most of the book to be read as a textbook or a reference, whichever is needed

at the moment.

Clearly identified topics and applications

Each chapter (except Chapter 1) begins with a brief introduction, followed by a list of clearly

identified topics and their relevance to real applications.

Analyses of every operation, algorithm, and example

An analysis is provided for every operation of abstract datatypes, every algorithm in the

algorithms chapters, and every example throughout the book. Each analysis uses the

techniques presented in Chapter 4.

Real examples, not just trivial exercises

All examples are from real applications, not just trivial exercises. Examples like these are

exciting and teach more than just the topic being demonstrated.

Real implementations using real code

All implementations are written in C, not pseudocode. The benefit of this is that when

implementing many data structures and algorithms, there are considerable details

pseudocode does not address.

Questions and answers for further thought

At the end of each chapter (except Chapter 1), there is a series of questions along with their

answers. These emphasize important ideas from the chapter and touch on additional topics.

Lists of related topics for further exploration

At the end of each chapter (except Chapter 1), there is a list of related topics for further

exploration. Each topic is presented with a brief description.

Numerous cross references and call-outs

Cross references and call-outs mark topics mentioned in one place that are introduced

elsewhere. Thus, it is easy to locate additional information.

Insightful organization and application of topics

Many of the data structures or algorithms in one chapter use data structures and algorithms

presented elsewhere in the book. Thus, they serve as examples of how to use other data

structures and algorithms themselves. All dependencies are carefully marked with a cross

reference or call-out.

Coverage of fundamental topics, plus more

This book covers the fundamental data structures and algorithms of computer science. It also

covers several topics not normally addressed in books on the subject. These include

numerical methods, data compression (in more detail), data encryption, and geometric

algorithms.

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Preface

Content

About the Code

All implementations in this book are in C. C was chosen because it is still the most general-purpose

language in use today. It is also one of the best languages in which to explore the details of data

structures and algorithms while still working at a fairly high level. It may be helpful to note a few

things about the code in this book.

All code focuses on pedagogy first

There is also a focus on efficiency, but the primary purpose of all code is to teach the topic it

addresses in a clear manner.

All code has been fully tested on four platforms

The platforms used for testing were HP-UX 10.20, SunOs 5.6, Red Hat Linux 5.1, and

DOS/Windows NT/95/98. See the readme file on the accompanying website

http://examples.oreilly.com/masteralgoc/) for additional information.

Headers document all public interfaces

Every implementation includes a header that documents the public interface. Most headers

are shown in this book. However, headers that contain only prototypes are not. (For instance,

Example 12.1 includes sort.h, but this header is not shown because it contains only

prototypes to various sorting functions.)

Static functions are used for private functions

Static functions have file scope, so this fact is used to keep private functions private.

Functions specific to a data structure or algorithm's implementation are thus kept out of its

public interface.

Naming conventions are applied throughout the code

Defined constants appear entirely in uppercase. Datatypes and global variables begin with an

uppercase character. Local variables begin with a lowercase character. Operations of abstract

datatypes begin with the name of the type in lowercase, followed by an underscore, then the

name of the operation in lowercase.

All code contains numerous comments

All comments are designed to let developers follow the logic of the code without reading

much of the code itself. This is useful when trying to make connections between the code and

explanations in the text.

Structures have typedefs as well as names themselves

The name of the structure is always the name in the typedef followed by an underscore.

Naming the structure itself is necessary for self-referential structures like the one used for

linked list elements (see Chapter 5). This approach is applied everywhere for consistency.

All void functions contain explicit returns

Although not required, this helps quickly identify where a void function returns rather than

having to match up braces.

Top

Mastering Algorithms with C

By Kyle Loudon

Slots : 1

Table of Contents

Preface

Content

Conventions

Most of the conventions used in this book should be recognizable to those who work with

computers to any extent. However, a few require some explanation.

Bold italic

Nonintrinsic mathematical functions and mathematical variables appear in this font.

Constant width italic

Variables from programs, names of datatypes (such as structure names), and defined

constants appear in this font.

Italic

Commands (as they would be typed in at a terminal), names of files and paths, operations of

abstract datatypes, and other functions from programs appear in this font.

lg x

This notation is used to represent the base-2 logarithm of x, log2 x. This is the notation used

commonly in computer science when discussing algorithms; therefore, it is used in this book.

Top