Advanced Topics in C: Core Concepts in Data Structures (Expert's Voice in C)

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 Contents1. Sorting, Searching and Merging 2. Structures 3. Pointers 4. Linked Lists 5. Stacks and Queries 6. Recursion 7. Random Numbers, Games and Simulation 8. Working with Files 9. Introduction to Binary Trees 10. Advanced Sorting 11. Hash Tables Advanced Topics in C......Page 292 Contents at a Glance......Page 3 Contents......Page 295 About the Author......Page 301 About the Technical Reviewer......Page 302 Preface......Page 303 1.1 Sorting an Array: Selection Sort......Page 4 1.2 Sorting an Array: Insertion Sort......Page 8 1.3 Inserting an Element in Place......Page 14 1.4 Sorting an Array of Strings......Page 15 1.5 Sorting Parallel Arrays......Page 17 1.6 Binary Search......Page 18 1.7 Searching an Array of Strings......Page 20 1.8 Example: Word Frequency Count......Page 21 1.9 Merging Ordered Lists......Page 25 1.9.1 Implementing the Merge......Page 26 2.1 Defining Structures......Page 30 2.2 How to Declare a Structure......Page 31 2.2.1 typedef......Page 33 2.3 Working with an Array of Structures......Page 35 2.5 Sorting an Array of Structures......Page 36 2.6 How to Read, Search, and Sort a Structure......Page 37 2.7 Nested Structures......Page 41 2.8.1 Manipulating Fractions......Page 42 2.9 A Voting Problem......Page 44 2.10 Passing Structures to Functions......Page 50 3.1 Defining Pointers......Page 53 3.2 Passing Pointers as Arguments......Page 55 3.3 More on Passing an Array as an Argument......Page 57 3.4 Character Pointers......Page 59 3.5 Pointer Arithmetic......Page 60 3.6 Pointers to Structures......Page 62 3.7 Pointers to Functions......Page 64 3.8 Void Pointers......Page 67 4.1 Defining Linked Lists......Page 71 4.2.1 Counting the Nodes in a Linked List......Page 73 4.2.2 Searching a Linked List......Page 74 4.3 Dynamic Storage Allocation: malloc, calloc, sizeof, free......Page 75 4.3.1 malloc......Page 76 4.3.3 sizeof......Page 77 4.3.4 free......Page 78 4.4 Building a Linked List: Adding New Item at the Tail......Page 79 4.5 Insertion into a Linked List......Page 82 4.6 Building a Linked List: Adding a New Item at the Head......Page 84 4.7 Deletion from a Linked List......Page 85 4.8 Building a Sorted Linked List......Page 86 4.9 Example: Palindrome......Page 90 4.11 Arrays vs. Linked Lists......Page 93 4.12 Storing a Linked List Using Arrays......Page 94 4.13 Merging Two Sorted Linked Lists......Page 95 4.14.1 Circular Lists......Page 99 4.14.2 Two-Way (Doubly Linked) Lists......Page 102 5.2 Stacks......Page 105 5.2.1 Implementing a Stack Using an Array......Page 106 5.2.2 Implementing a Stack Using a Linked List......Page 110 5.3 Creating a Stack Header File......Page 113 5.4 A General Stack Type......Page 114 5.4.1 Example: Convert from Decimal to Binary......Page 118 5.5 Converting Infix to Postfix......Page 119 5.5.1 Evaluating a Postfix Expression......Page 123 5.6 Queues......Page 124 5.6.1 Implementing a Queue Using an Array......Page 125 5.6.2 Implementing a Queue Using a Linked List......Page 129 6.1 Recursive Definition......Page 135 6.2 Writing Recursive Functions in C......Page 136 6.3 Converting a Decimal Number to Binary Using Recursion......Page 139 6.4 Printing a Linked List in Reverse Order......Page 141 6.5 Towers of Hanoi......Page 142 6.6 Writing Power Functions......Page 144 6.7 Merge Sort......Page 145 6.8.2 External Static......Page 149 6.9 Counting Organisms......Page 150 6.10 Finding a Path Through a Maze......Page 154 6.10.1 Writing the Program......Page 156 7.1 Random Numbers......Page 160 7.3 Generating Random Numbers by Computer......Page 161 7.4 A Guessing Game......Page 164 7.5 Drills in Addition......Page 165 7.6 Nim......Page 167 7.7 Non-uniform Distributions......Page 170 7.7.1 Collecting Bottle Caps......Page 171 7.8 Simulation of Real-Life Problems......Page 173 7.9 Simulating a Queue......Page 174 7.9.1 Programming the Simulation......Page 176 7.10.1 Estimating......Page 178 7.10.2 Estimating p......Page 179 8.1 Reading Data from a File......Page 184 8.1.1 fscanf......Page 185 8.1.2 Finding the Average of Some Numbers in a File......Page 186 8.2.1 fprintf......Page 187 8.3 Text and Binary Files......Page 188 8.4 Internal vs. External File Name......Page 189 8.5 fopen and fclose......Page 190 8.6 getc and putc......Page 192 8.7 feof and ferror......Page 193 8.8.1 Example: Comparing Two Files......Page 194 8.9.1 fread and fwrite......Page 196 8.10.1 rewind and fseek......Page 199 8.11 Indexed Files......Page 203 8.12 Updating a Random Access File......Page 209 9.1 Trees......Page 214 9.2 Binary Trees......Page 216 9.3 Traversing a Binary Tree......Page 217 9.4 Representing a Binary Tree......Page 220 9.5 Building a Binary Tree......Page 221 9.6 Binary Search Trees......Page 225 9.7 Building a Binary Search Tree......Page 228 9.7.1 Example: Word Frequency Count......Page 229 9.8 An Array as a Binary Tree Representation......Page 232 9.9 Some Useful Binary Tree Functions......Page 235 9.10 Binary Search Tree Deletion......Page 236 10.1 Heapsort......Page 241 10.1.1 Converting a Binary Tree into a Max-Heap......Page 242 10.1.2 The Sorting Process......Page 243 10.2 Building a Heap Using siftUp......Page 247 10.3 Analysis of Heapsort......Page 250 10.5 Sorting a List of Items with Quicksort......Page 251 10.5.1 Another Way to Partition......Page 254 10.5.2 Nonrecursive Quicksort......Page 257 10.5.3 Finding the k th Smallest Number......Page 258 10.6 Shell (Diminishing Increment) Sort......Page 259 11.1.1 The Search and Insert Problem......Page 264 11.2 Solving the Search and Insert Problem by Hashing......Page 265 11.2.1 The Hash Function......Page 268 11.2.2 Deleting an Item from a Hash Table......Page 269 11.3.1 Linear Probing......Page 270 11.3.2 Quadratic Probing......Page 272 11.3.3 Chaining......Page 273 11.3.4 Linear Probing with Double Hashing 1......Page 279 11.4 Example: Word Frequency Count......Page 280 Index......Page 286 Apress Advanced Topics in C 292 Contents at a Glance 3 Contents 295 About the Author 301 About the Technical Reviewer 302 Preface 303 Chapter 1: Sorting, Searching, and Merging 4 1.1 Sorting an Array: Selection Sort 4 1.1.1 Analysis of Selection Sort 8 1.2 Sorting an Array: Insertion Sort 8 1.2.1 Analysis of Insertion Sort 14 1.3 Inserting an Element in Place 14 1.4 Sorting an Array of Strings 15 1.5 Sorting Parallel Arrays 17 1.6 Binary Search 18 1.7 Searching an Array of Strings 20 1.8 Example: Word Frequency Count 21 1.9 Merging Ordered Lists 25 1.9.1 Implementing the Merge 26 Chapter 2: Structures 30 2.1 Defining Structures 30 2.2 How to Declare a Structure 31 2.2.1 typedef 33 2.3 Working with an Array of Structures 35 2.4 Searching an Array of Structures 36 2.5 Sorting an Array of Structures 36 2.6 How to Read, Search, and Sort a Structure 37 2.7 Nested Structures 41 2.8 Working with Fractions 42 2.8.1 Manipulating Fractions 42 2.9 A Voting Problem 44 2.10 Passing Structures to Functions 50 Chapter 3: Pointers 53 3.1 Defining Pointers 53 3.2 Passing Pointers as Arguments 55 3.3 More on Passing an Array as an Argument 57 3.4 Character Pointers 59 3.5 Pointer Arithmetic 60 3.6 Pointers to Structures 62 3.7 Pointers to Functions 64 3.8 Void Pointers 67 Chapter 4: Linked Lists 71 4.1 Defining Linked Lists 71 4.2 Basic Operations on a Linked List 73 4.2.1 Counting the Nodes in a Linked List 73 4.2.2 Searching a Linked List 74 4.2.3 Finding the Last Node in a Linked List 75 4.3 Dynamic Storage Allocation: malloc, calloc, sizeof, free 75 4.3.1 malloc 76 4.3.2 calloc 77 4.3.3 sizeof 77 4.3.4 free 78 4.4 Building a Linked List: Adding New Item at the Tail 79 4.5 Insertion into a Linked List 82 4.6 Building a Linked List: Adding a New Item at the Head 84 4.7 Deletion from a Linked List 85 4.8 Building a Sorted Linked List 86 4.9 Example: Palindrome 90 4.10 Saving a Linked List 93 4.11 Arrays vs. Linked Lists 93 4.12 Storing a Linked List Using Arrays 94 4.13 Merging Two Sorted Linked Lists 95 4.14 Circular and Two-Way Linked Lists 99 4.14.1 Circular Lists 99 4.14.2 Two-Way (Doubly Linked) Lists 102 Chapter 5: Stacks and Queues 105 5.1 Abstract Data Types 105 5.2 Stacks 105 5.2.1 Implementing a Stack Using an Array 106 5.2.2 Implementing a Stack Using a Linked List 110 5.3 Creating a Stack Header File 113 5.4 A General Stack Type 114 5.4.1 Example: Convert from Decimal to Binary 118 5.5 Converting Infix to Postfix 119 5.5.1 Evaluating a Postfix Expression 123 5.6 Queues 124 5.6.1 Implementing a Queue Using an Array 125 5.6.2 Implementing a Queue Using a Linked List 129 Chapter 6: Recursion 135 6.1 Recursive Definition 135 6.2 Writing Recursive Functions in C 136 6.3 Converting a Decimal Number to Binary Using Recursion 139 6.4 Printing a Linked List in Reverse Order 141 6.5 Towers of Hanoi 142 6.6 Writing Power Functions 144 6.7 Merge Sort 145 6.8 static Variables 149 6.8.1 Internal Static 149 6.8.2 External Static 149 6.9 Counting Organisms 150 6.10 Finding a Path Through a Maze 154 6.10.1 Writing the Program 156 Chapter 7: Random Numbers, Games, and Simulation 160 7.1 Random Numbers 160 7.2 Random and Pseudorandom Numbers 161 7.3 Generating Random Numbers by Computer 161 7.4 A Guessing Game 164 7.5 Drills in Addition 165 7.6 Nim 167 7.7 Non-uniform Distributions 170 7.7.1 Collecting Bottle Caps 171 7.8 Simulation of Real-Life Problems 173 7.9 Simulating a Queue 174 7.9.1 Programming the Simulation 176 7.10 Estimating Numerical Values Using Random Numbers 178 7.10.1 Estimating 178 7.10.2 Estimating p 179 Chapter 8: Working with Files 184 8.1 Reading Data from a File 184 8.1.1 fscanf 185 8.1.2 Finding the Average of Some Numbers in a File 186 8.2 Sending Output to a File 187 8.2.1 fprintf 187 8.3 Text and Binary Files 188 8.4 Internal vs. External File Name 189 8.5 fopen and fclose 190 8.6 getc and putc 192 8.7 feof and ferror 193 8.8 fgets and fputs 194 8.8.1 Example: Comparing Two Files 194 8.9 Input/Output for Binary File 196 8.9.1 fread and fwrite 196 8.10 Random Access Files 199 8.10.1 rewind and fseek 199 8.11 Indexed Files 203 8.12 Updating a Random Access File 209 Chapter 9: Introduction to Binary Trees 214 9.1 Trees 214 9.2 Binary Trees 216 9.3 Traversing a Binary Tree 217 9.4 Representing a Binary Tree 220 9.5 Building a Binary Tree 221 9.6 Binary Search Trees 225 9.7 Building a Binary Search Tree 228 9.7.1 Example: Word Frequency Count 229 9.8 An Array as a Binary Tree Representation 232 9.9 Some Useful Binary Tree Functions 235 9.10 Binary Search Tree Deletion 236 Chapter 10: Advanced Sorting 241 10.1 Heapsort 241 10.1.1 Converting a Binary Tree into a Max-Heap 242 10.1.2 The Sorting Process 243 10.2 Building a Heap Using siftUp 247 10.3 Analysis of Heapsort 250 10.4 Heaps and Priority Queues 251 10.5 Sorting a List of Items with Quicksort 251 10.5.1 Another Way to Partition 254 10.5.2 Nonrecursive Quicksort 257 10.5.3 Finding the k th Smallest Number 258 10.6 Shell (Diminishing Increment) Sort 259 Chapter 11: Hashing 264 11.1 Hashing Fundamentals 264 11.1.1 The Search and Insert Problem 264 11.2 Solving the Search and Insert Problem by Hashing 265 11.2.1 The Hash Function 268 11.2.2 Deleting an Item from a Hash Table 269 11.3 Resolving Collisions 270 11.3.1 Linear Probing 270 11.3.2 Quadratic Probing 272 11.3.3 Chaining 273 11.3.4 Linear Probing with Double Hashing 1 279 11.4 Example: Word Frequency Count 280 Index 286