Advanced Topics in C: Core Concepts in Data Structures

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