You are previewing Mastering Algorithms with C.
O'Reilly logo
Mastering Algorithms with C

Book Description

There are many books on data structures and algorithms, and somebooks laying out useful libraries of C functions, but this bookaims to give you a unique combination of theoretical background andworking code. In offering robust solutions for everyday programmingtasks, Mastering Algorithms with C avoids the abstract styleof most classic data structures and algorithms texts but stillprovides all the information you need to understand the purpose anduse of common programming techniques. Implementations, as well asinteresting, real-world examples of each data structure andalgorithm, are shown in the text. Full source code appears on theaccompanying disk. Using both a programming style and a writingstyle that are exceptionally clean, Kyle Loudon shows you how touse such essential data structures as lists, stacks, queues, sets,trees, heaps, priority queues, and graphs. He shows you how to usealgorithms for sorting, searching, numerical analysis, datacompression, data encryption, common graph problems, andcomputational geometry. He also describes the relative efficiencyof all implementations. The compression and encryption chapters notonly give you working code for reasonably efficient solutions, theyexplain concepts in an approachable manner for people who neverhave had the time or expertise to study them in depth. Anyone witha basic understanding of the C language can use this book. In orderto provide maintainable and extendible code, an extra level ofabstraction (such as pointers to functions) is used in exampleswhere appropriate. Understanding that these techniques may beunfamiliar to some programmers, Loudon explains them clearly in theintroductory 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

Table of Contents

  1. Mastering Algorithms with C
  2. SPECIAL OFFER: Upgrade this ebook with O’Reilly
  3. A Note Regarding Supplemental Files
  4. Preface
    1. Organization
      1. Part I
      2. Part II
      3. Part III
    2. Key Features
    3. About the Code
    4. Conventions
    5. How to Contact Us
    6. Acknowledgments
  5. I. Preliminaries
    1. 1. Introduction
      1. 1.1. An Introduction to Data Structures
      2. 1.2. An Introduction to Algorithms
        1. 1.2.1. General Approaches in Algorithm Design
          1. 1.2.1.1. Randomized algorithms
          2. 1.2.1.2. Divide-and-conquer algorithms
          3. 1.2.1.3. Dynamic-programming solutions
          4. 1.2.1.4. Greedy algorithms
          5. 1.2.1.5. Approximation algorithms
      3. 1.3. A Bit About Software Engineering
      4. 1.4. How to Use This Book
    2. 2. Pointer Manipulation
      1. 2.1. Pointer Fundamentals
      2. 2.2. Storage Allocation
      3. 2.3. Aggregates and Pointer Arithmetic
        1. 2.3.1. Structures
        2. 2.3.2. Arrays
      4. 2.4. Pointers as Parameters to Functions
        1. 2.4.1. Call-by-Reference Parameter Passing
        2. 2.4.2. Pointers to Pointers as Parameters
      5. 2.5. Generic Pointers and Casts
        1. 2.5.1. Generic Pointers
        2. 2.5.2. Casts
      6. 2.6. Function Pointers
      7. 2.7. Questions and Answers
      8. 2.8. Related Topics
    3. 3. Recursion
      1. 3.1. Basic Recursion
      2. 3.2. Tail Recursion
      3. 3.3. Questions and Answers
      4. 3.4. Related Topics
    4. 4. Analysis of Algorithms
      1. 4.1. Worst-Case Analysis
        1. 4.1.1. Reasons for Worst-Case Analysis
      2. 4.2. O-Notation
        1. 4.2.1. Simple Rules for O-Notation
        2. 4.2.2. O-Notation Example and Why It Works
      3. 4.3. Computational Complexity
      4. 4.4. Analysis Example: Insertion Sort
      5. 4.5. Questions and Answers
      6. 4.6. Related Topics
  6. II. Data Structures
    1. 5. Linked Lists
      1. 5.1. Description of Linked Lists
      2. 5.2. Interface for Linked Lists
        1. list_init
        2. list_destroy
        3. list_ins_next
        4. list_rem_next
        5. list_size
        6. list_head
        7. list_tail
        8. list_is_head
        9. list_is_tail
        10. list_data
        11. list_next
      3. 5.3. Implementation and Analysis of Linked Lists
        1. 5.3.1. list_init
        2. 5.3.2. list_destroy
        3. 5.3.3. list_ins_next
        4. 5.3.4. list_rem_next
        5. 5.3.5. list_size, list_head, list_tail, list_is_tail,list_data, and list_next
      4. 5.4. Linked List Example: Frame Management
      5. 5.5. Description of Doubly-Linked Lists
      6. 5.6. Interface for Doubly-Linked Lists
        1. dlist_init
        2. dlist_destroy
        3. dlist_ins_next
        4. dlist_ins_prev
        5. dlist_remove
        6. dlist_size
        7. dlist_head
        8. dlist_tail
        9. dlist_is_head
        10. dlist_is_tail
        11. dlist_data
        12. dlist_next
        13. dlist_prev
      7. 5.7. Implementation and Analysis of Doubly Linked Lists
        1. 5.7.1. dlist_init
        2. 5.7.2. dlist_destroy
        3. 5.7.3. dlist_ins_next
        4. 5.7.4. dlist_ins_ prev
        5. 5.7.5. dlist_remove
        6. 5.7.6. dlist_size, dlist_head, dlist_tail, dlist_is_head, dlist_is_tail, dlist_data, dlist_next, and dlist_ prev
      8. 5.8. Description of Circular Lists
      9. 5.9. Interface for Circular Lists
        1. clist_init
        2. clist_destroy
        3. clist_ins_next
        4. clist_rem_next
        5. clist_size
        6. clist_head
        7. clist_data
        8. clist_next
      10. 5.10. Implementation and Analysis of Circular Lists
        1. 5.10.1. clist_init
        2. 5.10.2. clist_destroy
        3. 5.10.3. clist_ins_next
        4. 5.10.4. clist_rem_next
        5. 5.10.5. clist_size, clist_head, clist_data, and clist_next
      11. 5.11. Circular List Example: Second-Chance Page Replacement
      12. 5.12. Questions and Answers
      13. 5.13. Related Topics
    2. 6. Stacks and Queues
      1. 6.1. Description of Stacks
      2. 6.2. Interface for Stacks
        1. stack_init
        2. stack_destroy
        3. stack_ push
        4. stack_ pop
        5. stack_ peek
        6. stack_size
      3. 6.3. Implementation and Analysis of Stacks
        1. 6.3.1. stack_init
        2. 6.3.2. stack_destroy
        3. 6.3.3. stack_ push
        4. 6.3.4. stack_ pop
        5. 6.3.5. stack_ peek, stack_size
      4. 6.4. Description of Queues
      5. 6.5. Interface for Queues
        1. queue_init
        2. queue_destroy
        3. queue_enqueue
        4. queue_dequeue
        5. queue_ peek
        6. queue_size
      6. 6.6. Implementation and Analysis of Queues
        1. 6.6.1. queue_init
        2. 6.6.2. queue_destroy
        3. 6.6.3. queue_enqueue
        4. 6.6.4. queue_dequeue
        5. 6.6.5. queue_ peek, queue_size
      7. 6.7. Queue Example: Event Handling
      8. 6.8. Questions and Answers
      9. 6.9. Related Topics
    3. 7. Sets
      1. 7.1. Description of Sets
        1. 7.1.1. Definitions
        2. 7.1.2. Basic Operations
        3. 7.1.3. Properties
      2. 7.2. Interface for Sets
        1. set_init
        2. set_destroy
        3. set_insert
        4. set_remove
        5. set_union
        6. set_intersection
        7. set_difference
        8. set_is_member
        9. set_is_subset
        10. set_is_equal
        11. set_size
      3. 7.3. Implementation and Analysis of Sets
        1. 7.3.1. set_init
        2. 7.3.2. set_destroy
        3. 7.3.3. set_insert
        4. 7.3.4. set_remove
        5. 7.3.5. set_union
        6. 7.3.6. set_intersection
        7. 7.3.7. set_difference
        8. 7.3.8. set_is_member
        9. 7.3.9. set_is_subset
        10. 7.3.10. set_is_equal
        11. 7.3.11. set_size
      4. 7.4. Set Example: Set Covering
      5. 7.5. Questions and Answers
      6. 7.6. Related Topics
    4. 8. Hash Tables
      1. 8.1. Description of Chained Hash Tables
        1. 8.1.1. Collision Resolution
        2. 8.1.2. Selecting a Hash Function
          1. 8.1.2.1. Division method
          2. 8.1.2.2. Multiplication method
      2. 8.2. Interface for Chained Hash Tables
        1. chtbl_init
        2. chtbl_destroy
        3. chtbl_insert
        4. chtbl_remove
        5. chtbl_lookup
        6. chtbl_size
      3. 8.3. Implementation and Analysis of Chained Hash Tables
        1. 8.3.1. chtbl_init
        2. 8.3.2. chtbl_destroy
        3. 8.3.3. chtbl_insert
        4. 8.3.4. chtbl_remove
        5. 8.3.5. chtbl_lookup
        6. 8.3.6. chtbl_size
      4. 8.4. Chained Hash Table Example: Symbol Tables
      5. 8.5. Description of Open-Addressed Hash Tables
        1. 8.5.1. Collision Resolution
          1. 8.5.1.1. Linear probing
          2. 8.5.1.2. Double hashing
      6. 8.6. Interface for Open-Addressed Hash Tables
        1. ohtbl_init
        2. ohtbl_destroy
        3. ohtbl_insert
        4. ohtbl_remove
        5. ohtbl_lookup
        6. ohtbl_size
      7. 8.7. Implementation and Analysisof Open Addressed Hash Tables
        1. 8.7.1. ohtbl_init
        2. 8.7.2. ohtbl_destroy
        3. 8.7.3. ohtbl_insert
        4. 8.7.4. ohtbl_remove
        5. 8.7.5. ohtbl_lookup
        6. 8.7.6. ohtbl_size
      8. 8.8. Questions and Answers
      9. 8.9. Related Topics
    5. 9. Trees
      1. 9.1. Description of Binary Trees
        1. 9.1.1. Traversal Methods
          1. 9.1.1.1. Preorder traversal
          2. 9.1.1.2. Inorder traversal
          3. 9.1.1.3. Postorder traversal
          4. 9.1.1.4. Level-order traversal
        2. 9.1.2. Tree Balancing
      2. 9.2. Interface for Binary Trees
        1. bitree_init
        2. bitree_destroy
        3. bitree_ins_left
        4. bitree_ins_right
        5. bitree_rem_left
        6. bitree_rem_right
        7. bitree_merge
        8. bitree_size
        9. bitree_root
        10. bitree_is_eob
        11. bitree_is_leaf
        12. bitree_data
        13. bitree_left
        14. bitree_right
      3. 9.3. Implementation and Analysis of Binary Trees
        1. 9.3.1. bitree_init
        2. 9.3.2. bitree_destroy
        3. 9.3.3. bitree_ins_left
        4. 9.3.4. bitree_ins_right
        5. 9.3.5. bitree_rem_left
        6. 9.3.6. bitree_rem_right
        7. 9.3.7. bitree_merge
        8. 9.3.8. bitree_size, bitree_root, bitree_is_eob, bitree_is_leaf, bitree_data, bitree_left, bitree_right
      4. 9.4. Binary Tree Example: Expression Processing
      5. 9.5. Description of Binary Search Trees
      6. 9.6. Interface for Binary Search Trees
        1. bistree_init
        2. bistree_destroy
        3. bistree_insert
        4. bistree_remove
        5. bistree_lookup
        6. bistree_size
      7. 9.7. Implementation and Analysis of Binary Search Trees
        1. 9.7.1. Rotations in AVL Trees
          1. 9.7.1.1. LL rotation
          2. 9.7.1.2. LR rotation
          3. 9.7.1.3. RR rotation
          4. 9.7.1.4. RL rotation
        2. 9.7.2. bistree_init
        3. 9.7.3. bistree_destroy
        4. 9.7.4. bistree_insert
        5. 9.7.5. bistree_remove
        6. 9.7.6. bistree_lookup
        7. 9.7.7. bistree_size
      8. 9.8. Questions and Answers
      9. 9.9. Related Topics
    6. 10. Heaps and Priority Queues
      1. 10.1. Description of Heaps
      2. 10.2. Interface for Heaps
        1. heap_init
        2. heap_destroy
        3. heap_insert
        4. heap_extract
        5. heap_size
      3. 10.3. Implementation and Analysis of Heaps
        1. 10.3.1. heap_init
        2. 10.3.2. heap_destroy
        3. 10.3.3. heap_insert
        4. 10.3.4. heap_extract
        5. 10.3.5. heap_size
      4. 10.4. Description of Priority Queues
      5. 10.5. Interface for Priority Queues
        1. pqueue_init
        2. pqueue_destroy
        3. pqueue_insert
        4. pqueue_extract
        5. pqueue_ peek
        6. pqueue_size
      6. 10.6. Implementation and Analysis of Priority Queues
      7. 10.7. Priority Queue Example: Parcel Sorting
      8. 10.8. Questions and Answers
      9. 10.9. Related Topics
    7. 11. Graphs
      1. 11.1. Description of Graphs
        1. 11.1.1. Search Methods
          1. 11.1.1.1. Breadth-first search
          2. 11.1.1.2. Depth-first search
      2. 11.2. Interface for Graphs
        1. graph_init
        2. graph_destroy
        3. graph_ins_vertex
        4. graph_ins_edge
        5. graph_rem_vertex
        6. graph_rem_edge
        7. graph_adjlist
        8. graph_is_adjacent
        9. graph_adjlists
        10. graph_vcount
        11. graph_ecount
      3. 11.3. Implementation and Analysis of Graphs
        1. 11.3.1. graph_init
        2. 11.3.2. graph_destroy
        3. 11.3.3. graph_ins_vertex
        4. 11.3.4. graph_ins_edge
        5. 11.3.5. graph_rem_vertex
        6. 11.3.6. graph_rem_edge
        7. 11.3.7. graph_adjlist
        8. 11.3.8. graph_is_adjacent
        9. 11.3.9. graph_adjlists, graph_vcount, graph_ecount
      4. 11.4. Graph Example: Counting Network Hops
      5. 11.5. Graph Example: Topological Sorting
      6. 11.6. Questions and Answers
      7. 11.7. Related Topics
  7. III. Algorithms
    1. 12. Sorting and Searching
      1. 12.1. Description of Insertion Sort
      2. 12.2. Interface for Insertion Sort
        1. issort
      3. 12.3. Implementation and Analysis of Insertion Sort
      4. 12.4. Description of Quicksort
      5. 12.5. Interface for Quicksort
        1. qksort
      6. 12.6. Implementation and Analysis of Quicksort
      7. 12.7. Quicksort Example: Directory Listings
      8. 12.8. Description of Merge Sort
      9. 12.9. Interface for Merge Sort
        1. mgsort
      10. 12.10. Implementation and Analysis of Merge Sort
      11. 12.11. Description of Counting Sort
      12. 12.12. Interface for Counting Sort
        1. ctsort
      13. 12.13. Implementation and Analysis of Counting Sort
      14. 12.14. Description of Radix Sort
      15. 12.15. Interface for Radix Sort
        1. rxsort
      16. 12.16. Implementation and Analysis of Radix Sort
      17. 12.17. Description of Binary Search
      18. 12.18. Interface for Binary Search
        1. bisearch
      19. 12.19. Implementation and Analysis of Binary Search
      20. 12.20. Binary Search Example: Spell Checking
      21. 12.21. Questions and Answers
      22. 12.22. Related Topics
    2. 13. Numerical Methods
      1. 13.1. Description of Polynomial Interpolation
        1. 13.1.1. Constructing an Interpolating Polynomial
        2. 13.1.2. Evaluating an Interpolating Polynomial
      2. 13.2. Interface for Polynomial Interpolation
        1. interpol
      3. 13.3. Implementation and Analysis of Polynomial Interpolation
      4. 13.4. Description of Least-Squares Estimation
      5. 13.5. Interface for Least-Squares Estimation
        1. lsqe
      6. 13.6. Implementation and Analysis of Least-Squares Estimation
      7. 13.7. Description of the Solution of Equations
        1. 13.7.1. Finding Roots with Newton's Method
        2. 13.7.2. Computing the Derivative of a Polynomial
        3. 13.7.3. Understanding the First and Second Derivative
        4. 13.7.4. Selecting an Initial Point for Newton's Method
        5. 13.7.5. How Newton's Method Works
      8. 13.8. Interface for the Solution of Equations
        1. root
      9. 13.9. Implementation and Analysis of the Solution of Equations
      10. 13.10. Questions and Answers
      11. 13.11. Related Topics
    3. 14. Data Compression
      1. 14.1. Description of Bit Operations
      2. 14.2. Interface for Bit Operations
        1. bit_ get
        2. bit_set
        3. bit_xor
        4. bit_rot_left
      3. 14.3. Implementation and Analysis of Bit Operations
        1. 14.3.1. bit_ get
        2. 14.3.2. bit_set
        3. 14.3.3. bit_xor
        4. 14.3.4. bit_rot_left
      4. 14.4. Description of Huffman Coding
        1. 14.4.1. Entropy and Minimum Redundancy
        2. 14.4.2. Building a Huffman Tree
        3. 14.4.3. Compressing and Uncompressing Data
        4. 14.4.4. Effectiveness of Huffman Coding
      5. 14.5. Interface for Huffman Coding
        1. huffman_compress
        2. huffman_uncompress
      6. 14.6. Implementation and Analysis of Huffman Coding
        1. 14.6.1. huffman_compress
        2. 14.6.2. huffman_uncompress
      7. 14.7. Huffman Coding Example: Optimized Networking
      8. 14.8. Description of LZ77
        1. 14.8.1. Maintaining a Dictionary of Phrases
        2. 14.8.2. Compressing and Uncompressing Data
        3. 14.8.3. Effectiveness of LZ77
      9. 14.9. Interface for LZ77
        1. lz77_compress
        2. lz77_uncompress
      10. 14.10. Implementation and Analysis of LZ77
        1. 14.10.1. lz77_compress
        2. 14.10.2. lz77_uncompress
      11. 14.11. Questions and Answers
      12. 14.12. Related Topics
    4. 15. Data Encryption
      1. 15.1. Description of DES
        1. 15.1.1. Computing Subkeys
        2. 15.1.2. Enciphering and Deciphering Data Blocks
      2. 15.2. Interface for DES
        1. des_encipher
        2. des_decipher
      3. 15.3. Implementation and Analysis of DES
        1. 15.3.1. des_encipher
        2. 15.3.2. des_decipher
      4. 15.4. DES Example: Block Cipher Modes
      5. 15.5. Description of RSA
        1. 15.5.1. Computing Public and Private Keys
        2. 15.5.2. Enciphering and Deciphering Data Blocks
      6. 15.6. Interface for RSA
        1. rsa_encipher
        2. rsa_decipher
      7. 15.7. Implementation and Analysis of RSA
        1. 15.7.1. rsa_encipher
        2. 15.7.2. rsa_decipher
      8. 15.8. Questions and Answers
      9. 15.9. Related Topics
    5. 16. Graph Algorithms
      1. 16.1. Description of Minimum Spanning Trees
        1. 16.1.1. Prim's Algorithm
      2. 16.2. Interface for Minimum Spanning Trees
        1. mst
      3. 16.3. Implementation and Analysis of Minimum Spanning Trees
      4. 16.4. Description of Shortest Paths
        1. 16.4.1. Dijkstra's Algorithm
      5. 16.5. Interface for Shortest Paths
        1. shortest
      6. 16.6. Implementation and Analysis of Shortest Paths
      7. 16.7. Shortest Paths Example: Routing Tables
      8. 16.8. Description of the Traveling-Salesman Problem
        1. 16.8.1. Applying the Nearest-Neighbor Heuristic
      9. 16.9. Interface for the Traveling-Salesman Problem
        1. tsp
      10. 16.10. Implementation and Analysis of the Traveling-Salesman Problem
      11. 16.11. Questions and Answers
      12. 16.12. Related Topics
    6. 17. Geometric Algorithms
      1. 17.1. Description of Testing Whether Line Segments Intersect
        1. 17.1.1. Standard Test for Intersecting Line Segments
        2. 17.1.2. Computer Test for Intersecting Line Segments
      2. 17.2. Interface for Testing Whether Line Segments Intersect
        1. lint
      3. 17.3. Implementation and Analysis of Testing Whether Line Segments Intersect
      4. 17.4. Description of Convex Hulls
        1. 17.4.1. Jarvis's March
      5. 17.5. Interface for Convex Hulls
        1. cvxhull
      6. 17.6. Implementation and Analysis of Convex Hulls
      7. 17.7. Description of Arc Length on Spherical Surfaces
        1. 17.7.1. Rectilinear and Spherical Coordinates
        2. 17.7.2. Converting Between Coordinate Systems
        3. 17.7.3. Computing the Length of an Arc
      8. 17.8. Interface for Arc Length on Spherical Surfaces
        1. arclen
      9. 17.9. Implementation and Analysis of Arc Length on Spherical Surfaces
      10. 17.10. Arc Length Example: Approximating Distances on Earth
      11. 17.11. Questions and Answers
      12. 17.12. Related Topics
  8. Index
  9. About the Author
  10. Colophon
  11. SPECIAL OFFER: Upgrade this ebook with O’Reilly
  12. Copyright