You are previewing Advanced Topics in C: Core Concepts in Data Structures.
O'Reilly logo
Advanced Topics in C: Core Concepts in Data Structures

Book Description

C is the most widely used programming language of all time. It has been used to create almost every category of software imaginable and the list keeps growing every day. Cutting-edge applications, such as Arduino, embeddable and wearable computing are ready-made for C.

Advanced Topics In C teaches concepts that any budding programmer should know. You'll delve into topics such as sorting, searching, merging, recursion, random numbers and simulation, among others. You will increase the range of problems you can solve when you learn how to manipulate versatile and popular data structures such as binary trees and hash tables.

This book assumes you have a working knowledge of basic programming concepts such as variables, constants, assignment, selection (if..else) and looping (while, for). It also assumes you are comfortable with writing functions and working with arrays. If you study this book carefully and do the exercises conscientiously, you would become a better and more agile programmer, more prepared to code today's applications (such as the Internet of Things) in C.

What you'll learn

  • What are and how to use structures, pointers, and linked lists

  • How to manipulate and use stacks and queues

  • How to use random numbers to program games, and simulations

  • How to work with files, binary trees, and hash tables

  • Sophisticated sorting methods such as heapsort, quicksort, and mergesort

  • How to implement all of the above using C

Who this book is for

Those with a working knowledge of basic programming concepts, such as variables, constants, assignment, selection (if..else) and looping (while, for). It also assumes you are comfortable with writing functions and working with arrays.

Table of Contents

  1. Title Page
  2. Dedication
  3. Contents at a Glance
  4. Contents
  5. About the Author
  6. About the Technical Reviewer
  7. Preface
  8. CHAPTER 1: Sorting, Searching, and Merging
    1. 1.1 Sorting an Array: Selection Sort
    2. 1.2 Sorting an Array: Insertion Sort
    3. 1.3 Inserting an Element in Place
    4. 1.4 Sorting an Array of Strings
    5. 1.5 Sorting Parallel Arrays
    6. 1.6 Binary Search
    7. 1.7 Searching an Array of Strings
    8. 1.8 Example: Word Frequency Count
    9. 1.9 Merging Ordered Lists
  9. CHAPTER 2: Structures
    1. 2.1 Defining Structures
    2. 2.2 How to Declare a Structure
    3. 2.3 Working with an Array of Structures
    4. 2.4 Searching an Array of Structures
    5. 2.5 Sorting an Array of Structures
    6. 2.6 How to Read, Search, and Sort a Structure
    7. 2.7 Nested Structures
    8. 2.8 Working with Fractions
    9. 2.9 A Voting Problem
    10. 2.10 Passing Structures to Functions
  10. CHAPTER 3: Pointers
    1. 3.1 Defining Pointers
    2. 3.2 Passing Pointers as Arguments
    3. 3.3 More on Passing an Array as an Argument
    4. 3.4 Character Pointers
    5. 3.5 Pointer Arithmetic
    6. 3.6 Pointers to Structures
    7. 3.7 Pointers to Functions
    8. 3.8 Void Pointers
  11. CHAPTER 4: Linked Lists
    1. 4.1 Defining Linked Lists
    2. 4.2 Basic Operations on a Linked List
    3. 4.3 Dynamic Storage Allocation: malloc, calloc, sizeof, free
    4. 4.4 Building a Linked List: Adding New Item at the Tail
    5. 4.5 Insertion into a Linked List
    6. 4.6 Building a Linked List: Adding a New Item at the Head
    7. 4.7 Deletion from a Linked List
    8. 4.8 Building a Sorted Linked List
    9. 4.9 Example: Palindrome
    10. 4.10 Saving a Linked List
    11. 4.11 Arrays vs. Linked Lists
    12. 4.12 Storing a Linked List Using Arrays
    13. 4.13 Merging Two Sorted Linked Lists
    14. 4.14 Circular and Two-Way Linked Lists
  12. CHAPTER 5: Stacks and Queues
    1. 5.1 Abstract Data Types
    2. 5.2 Stacks
    3. 5.3 Creating a Stack Header File
    4. 5.4 A General Stack Type
    5. 5.5 Converting Infix to Postfix
    6. 5.6 Queues
  13. CHAPTER 6: Recursion
    1. 6.1 Recursive Definition
    2. 6.2 Writing Recursive Functions in C
    3. 6.3 Converting a Decimal Number to Binary Using Recursion
    4. 6.4 Printing a Linked List in Reverse Order
    5. 6.5 Towers of Hanoi
    6. 6.6 Writing Power Functions
    7. 6.7 Merge Sort
    8. 6.8 static Variables
    9. 6.9 Counting Organisms
    10. 6.10 Finding a Path Through a Maze
  14. CHAPTER 7: Random Numbers, Games, and Simulation
    1. 7.1 Random Numbers
    2. 7.2 Random and Pseudorandom Numbers
    3. 7.3 Generating Random Numbers by Computer
    4. 7.4 A Guessing Game
    5. 7.5 Drills in Addition
    6. 7.6 Nim
    7. 7.7 Non-uniform Distributions
    8. 7.8 Simulation of Real-Life Problems
    9. 7.9 Simulating a Queue
    10. 7.10 Estimating Numerical Values Using Random Numbers
  15. CHAPTER 8: Working with Files
    1. 8.1 Reading Data from a File
    2. 8.2 Sending Output to a File
    3. 8.3 Text and Binary Files
    4. 8.4 Internal vs. External File Name
    5. 8.5 fopen and fclose
    6. 8.6 getc and putc
    7. 8.7 feof and ferror
    8. 8.8 fgets and fputs
    9. 8.9 Input/Output for Binary File
    10. 8.10 Random Access Files
    11. 8.11 Indexed Files
    12. 8.12 Updating a Random Access File
  16. CHAPTER 9: Introduction to Binary Trees
    1. 9.1 Trees
    2. 9.2 Binary Trees
    3. 9.3 Traversing a Binary Tree
    4. 9.4 Representing a Binary Tree
    5. 9.5 Building a Binary Tree
    6. 9.6 Binary Search Trees
    7. 9.7 Building a Binary Search Tree
    8. 9.8 An Array as a Binary Tree Representation
    9. 9.9 Some Useful Binary Tree Functions
    10. 9.10 Binary Search Tree Deletion
  17. CHAPTER 10: Advanced Sorting
    1. 10.1 Heapsort
    2. 10.2 Building a Heap Using siftUp
    3. 10.3 Analysis of Heapsort
    4. 10.4 Heaps and Priority Queues
    5. 10.5 Sorting a List of Items with Quicksort
    6. 10.6 Shell (Diminishing Increment) Sort
  18. CHAPTER 11: Hashing
    1. 11.1 Hashing Fundamentals
    2. 11.2 Solving the Search and Insert Problem by Hashing
    3. 11.3 Resolving Collisions
    4. 11.4 Example: Word Frequency Count
  19. Index